Synchronization of abstract and concrete syntax in domain-specific modeling languages

Modern domain-specific modeling (DSM) frameworks provide refined techniques for developing new languages based on the clear separation of conceptual elements of the language (called abstract syntax) and their graphical visual representation (called concrete syntax). This separation is usually achieved by recording traceability information between the abstract and concrete syntax using mapping models. However, state-of-the-art DSM frameworks impose severe restrictions on traceability links between elements of the abstract syntax and the concrete syntax. In the current paper, we propose a mapping model which allows to define arbitrarily complex mappings between elements of the abstract and concrete syntax. Moreover, we demonstrate how live model transformations can complement mapping models in providing bidirectional synchronization and implicit traceability between models of the abstract and the concrete syntax. In addition, we introduce a novel architecture for DSM environments which enables these concepts, and provide an overview of the tool support.     

用于漏洞检测的中间语言表示方法

现有Web漏洞检测方法中使用的中间语言针对特定编程语言设计,在对多种编程语言源代码进行漏洞抽象表示时,无法将多语言下的同类型漏洞用统一的中间语言表示,增加了后续漏洞分析处理的难度。针对该问题提出了一种基于污点分析的中间语言表示方法,实现多编程语言下同类型漏洞信息的统一抽象表示。该中间语言设计过程中将漏洞发生过程抽象为三元组表示,将与三元组相关的代码元素抽象为中间语言的关键字,根据三元组间的语义关系设计了该中间语言的语法。在转义时,利用污点分析方法跟踪污染源的执行路径,对路径中的源代码进行转义得到中间语言表示。最后将该中间语言用于漏洞检测模型,实验结果表明该中间语言与对照中间语言相比对编程语言中漏洞信息的抽象表示更具普适性,对漏洞检测具有有效性。     

Object-oriented Tree Traversal with JJForester

We want to use the advanced language processing technology available in the asf+sdf Meta-Environment in combination with general purpose programming languages. In particular, we want to combine the syntax definition formalism sdf and the associated components that support generalized LR parsing, with the object-oriented language Java. To this end, we implemented JJForester, a tool that generates class structures from sdf grammar definitions. The generated class structures implement a number of design patterns to facilitate construction and traversal of parse trees represented by object structures. In a detailed case study, we demonstrate how program analyses and transformations can be constructed with JJForester.     

Implementation of visual languages using pattern‐based specifications

The implementation of visual languages requires a wide range of conceptual and technical knowledge from issues of user interface design and graphical implementation to aspects of analysis and transformation for languages in general. We present a powerful toolset that incorporates such knowledge. Our toolset generates editors from high‐level specifications. A language is specified by identifying certain patterns in the language structure and selecting a visual representation from a set of precoined solutions. Visual programs are represented by attributed abstract trees. Therefore, further phases of processing visual programs can be generated by state‐of‐the‐art tools for language implementation. We demonstrate that even challenging visual languages can be implemented with reasonably little effort and with rather limited technical knowledge. The approach is suitable for a large variety of visual language styles. Copyright © 2003 John Wiley & Sons, Ltd.     

Compiler Verification and Compiler Architecture

We study issues in verifying compilers for modern imperative and object-oriented languages. We take the view that it is not the compiler but the code generated by it which must be correct. It is this subtle difference that allows for reusing standard compiler architecture, construction methods and tools also in a verifying compiler.Program checking is the main technique for avoiding the cumbersome task of verifying most parts of a compiler and the tools by which they are generated. Program checking remaps the result of a compiler phase to its origin, the input of this phase, in a provably correct manner. We then only have to compare the actual input to its regenerated form, a basically syntactic process. The correctness proof of the generation of the result is replaced by the correctness proof of the remapping process. The latter turns out to be far easier than proving the generating process correct.The only part of a compiler where program checking does not seem to work is the transformation step which replaces source language constructs and their semantics, given, e.g., by an attributed syntax tree, by an intermediate representation, e.g., in SSA-form, which is expressing the same program but in terms of the target machine. This transformation phase must be directly proven using Hoare logic and/or theorem-provers. However, we can show that given the features of today's programming languages and hardware architectures this transformation is to a large extent universal: it can be reused for any pair of source and target language. To achieve this goal we investigate annotating the syntax tree as well as the intermediate representation with constraints for exhibiting specific properties of the source language. Such annotations are necessary during code optimization anyway.     

Defining the abstract syntax of visual languages with advanced graph grammars—A case study based on behavior trees

Diagrammatic visual languages can increase the ability of engineers to model and understand complex systems. However, to effectively use visual models, the syntax and semantics of these languages should be defined precisely. Since most diagrammatic visual models that are currently used to specify systems can be described as (directed) typed graphs, graph grammars have been identified as a suitable formalism to describe the abstract syntax of visual modeling languages. In this article, we investigate how advanced graph-transformation techniques, such as conditional, structure-generic and type-generic graph-transformation rules, can help to improve and simplify the specification of the abstract syntax of a visual modeling language. To demonstrate the practicability of an approach that unifies these advanced graph-transformation techniques, we define the abstract syntax of behavior trees (BTs), a graphical specification language for functional requirements. Additionally, we provide a translational semantics of BTs by formalizing a translation scheme to the input language of the SAL model checking tool for each of the graph-transformation rules.     

Fresh O'Caml: Nominal Abstract Syntax for the Masses

Nominal abstract syntax, as pioneered by the 'FreshML' series of metalanguages, provides first-order tools for the representation and manipulation of syntax involving bound names, binding operations and α-equivalence. Fresh O'Caml fuses nominal abstract syntax with the full Objective Caml language to yield a functional programming language with powerful facilities for representing and manipulating syntax. In this paper, we first provide an examples-driven overview of the language and its functionality. Then we proceed to comment on some of the difficult issues involved in implementing nominal abstract syntax and explain how they have been addressed in the latest version of the compiler.     

基于多模态对比学习的代码表征增强预训练方法

代码表征旨在融合源代码的特征,以获取其语义向量,在基于深度学习的代码智能中扮演着重要角色.传统基于手工的代码表征依赖领域专家的标注,繁重耗时,且无法灵活地复用于特定下游任务,这与绿色低碳的发展理念极不相符.因此,近年来,许多自监督学习的编程语言大规模预训练模型(如CodeBERT)应运而生,为获取通用代码表征提供了有效途径.这些模型通过预训练获得通用的代码表征,然后在具体任务上进行微调,取得了显著成果.但是,要准确表示代码的语义信息,需要融合所有抽象层次的特征(文本级、语义级、功能级和结构级).然而,现有模型将编程语言仅视为类似于自然语言的普通文本序列,忽略了它的功能级和结构级特征.因此,旨在进一步提高代码表征的准确性,提出了基于多模态对比学习的代码表征增强的预训练模型(representation enhanced contrastive multimodal pretraining, REcomp). REcomp设计了新的语义级-结构级特征融合算法,将它用于序列化抽象语法树,并通过多模态对比学习的方法将该复合特征与编程语言的文本级和功能级特征相融合,以实现更精准的语义建模.最后,...     

Hybrid

Combining higher-order abstract syntax and (co)-induction in a logical framework is well known to be problematic. We describe the theory and the practice of a tool called Hybrid, within Isabelle/HOL and Coq, which aims to address many of these difficulties. It allows object logics to be represented using higher-order abstract syntax, and reasoned about using tactical theorem proving and principles of (co)induction. Moreover, it is definitional, which guarantees consistency within a classical type theory. The idea is to have a de Bruijn representation of λ-terms providing a definitional layer that allows the user to represent object languages using higher-order abstract syntax, while offering tools for reasoning about them at the higher level. In this paper we describe how to use Hybrid in a multi-level reasoning fashion, similar in spirit to other systems such as Twelf and Abella. By explicitly referencing provability in a middle layer called a specification logic, we solve the problem of reasoning by (co)induction in the presence of non-stratifiable hypothetical judgments, which allow very elegant and succinct specifications of object logic inference rules. We first demonstrate the method on a simple example, formally proving type soundness (subject reduction) for a fragment of a pure functional language, using a minimal intuitionistic logic as the specification logic. We then prove an analogous result for a continuation-machine presentation of the operational semantics of the same language, encoded this time in an ordered linear logic that serves as the specification layer. This example demonstrates the ease with which we can incorporate new specification logics, and also illustrates a significantly more complex object logic whose encoding is elegantly expressed using features of the new specification logic.     

Language design for program manipulation

The design of procedural and object-oriented programming languages is considered with respect to how easily programs written in those languages can be formally manipulated. Current procedural languages such as Pascal, Modula-2 and Ada; generally support such program manipulations, except for some annoying anomalies and special cases. Three main areas of language design are identified as being of concern from a manipulation viewpoint: the interface between concrete and abstract syntax; the relationship between the abstract syntax and static semantics naming, scoping and typing; and the ability to express basic transformations (folding and unfolding). Design principles are suggested so that the problems identified for current languages can be avoided in the future     

一个重建GCC抽象语法树的方法

抽象语法树(AST)作为程序的一种中间表示形式,在程序分析等诸多领域有广泛的应用。传统的建立AST的方法是通过词法和语法分析的方法。该文提出了一种利用GCC前端结果建立AST的方法,这种方法将GCC编译源程序产生的AST文件,经过一定的格式转换变为XML文档,然后使用XML文档解析器读取该文档,重新建立AST。     

Effective strategic programming for Java developers

In object programming languages, the Visitor design pattern allows separation of algorithms and data structures. When applying this pattern to tree‐like structures, programmers are always confronted with the difficulty of making their code evolve. One reason is that the code implementing the algorithm is interwound with the code implementing the traversal inside the visitor. When implementing algorithms such as data analyses or transformations, encoding the traversal directly into the algorithm turns out to be cumbersome as this type of algorithm only focuses on a small part of the data‐structure model (e.g., program optimization). Unfortunately, typed programming languages like Java do not offer simple solutions for expressing generic traversals. Rewrite‐based languages like ELAN or Stratego have introduced the notion of strategies to express both generic traversal and rule application control in a declarative way. Starting from this approach, our goal was to make the notion of strategic programming available in a widely used language such as Java and thus to offer generic traversals in typed Java structures. In this paper, we present the strategy language SL that provides programming support for strategies in Java. Copyright © 2012 John Wiley & Sons, Ltd.     

A formal introduction to the compilation of Java

The term abstract machine is widely accepted to denote intermediate target languages and related architectures which serve as an intermediate stage in compiling programming languages. In this paper we explain how a considerable subset of Java is translated into Byte-Code for the Java Virtual Machine, an abstract machine used as a target for Java compilation. Using formal and precise notation we present the language concepts, the related byte-code instructions and the compilation schemes. Hitherto none of the existing literature on the JVM^1,2 describes how compilation is done, but present the JVM in isolation. © 1998 John Wiley & Sons, Ltd.     

Debugging mixed‐environment programs with Blink

Programmers build large‐scale systems with multiple languages to leverage legacy code and languages best suited to their problems. For instance, the same program may use Java for ease of programming and C to interface with the operating system. These programs pose significant debugging challenges, because programmers need to understand and control code across languages, which often execute in different environments. Unfortunately, traditional multilingual debuggers require a single execution environment. This paper presents a novel composition approach to building portable mixed‐environment debuggers, in which an intermediate agent interposes on language transitions, controlling and reusing single‐environment debuggers. We implement debugger composition in Blink, a debugger for Java, C, and the Jeannie programming language. We show that Blink is (i) simple: it requires modest amounts of new code; (ii) portable: it supports multiple Java virtual machines, C compilers, operating systems, and component debuggers; and (iii) powerful: composition eases debugging, while supporting new mixed‐language expression evaluation and Java native interface bug diagnostics. To demonstrate the generality of interposition, we build prototypes and demonstrate debugger language transitions with C for five of six other languages (Caml, Common Lisp, C#, Perl 5, Python, and Ruby) without modifications to their debuggers. Using real‐world case studies, we show that diagnosing language interface errors require prior single‐environment debuggers to restart execution multiple times, whereas Blink directly diagnoses them with one execution. Copyright © 2014 John Wiley & Sons, Ltd.     

On the reuse and recommendation of model refactoring specifications

Refactorings can be used to improve the structure of software artefacts while preserving the semantics of the encapsulated information. Various types of refactorings have been proposed and implemented for programming languages (e.g., Java or C#). With the advent of (MDSD), a wealth of modelling languages rises and the need for restructuring models similar to programs has emerged. Since parts of these modelling languages are often very similar, we consider it beneficial to reuse the core transformation steps of refactorings across languages. In this sense, reusing the abstract transformation steps and the abstract participating elements suggests itself. Previous work in this field indicates that refactorings can be specified generically to foster their reuse. However, existing approaches can handle certain types of modelling languages only and solely reuse refactorings once per language. In this paper, a novel approach based on role models to specify generic refactorings is presented. Role models are suitable for this problem since they support declaration of roles which have to be played in a certain context. Assigned to generic refactoring, contexts are different refactorings and roles are the participating elements. We discuss how this resolves the limitations of previous works, as well as how specific refactorings can be defined as extensions to generic ones. The approach was implemented in our tool Refactory based on the (EMF) and evaluated using multiple modelling languages and refactorings. In addition, this paper investigates on the recommendation of refactoring specifications. This is motivated by the fact that language designers have many possibilities to enable refactorings in their modelling languages with regard to the language structures. To overcome this problem and to support language designers in deciding which refactorings to enable, we propose a solution and a prototypical implementation.     

Empirical evaluation of clone detection using syntax suffix trees

Reusing software through copying and pasting is a continuous plague in software development despite the fact that it creates serious maintenance problems. Various techniques have been proposed to find duplicated redundant code (also known as software clones). A recent study has compared these techniques and shown that token-based clone detection based on suffix trees is fast but yields clone candidates that are often not syntactic units. Current techniques based on abstract syntax trees—on the other hand—find syntactic clones but are considerably less efficient. This paper describes how we can make use of suffix trees to find syntactic clones in abstract syntax trees. This new approach is able to find syntactic clones in linear time and space. The paper reports the results of a large case study in which we empirically compare the new technique to other techniques using the Bellon benchmark for clone detectors. The Bellon benchmark consists of clone pairs validated by humans for eight software systems written in C or Java from different application domains. The new contributions of this paper over the conference paper are the additional analysis of Java programs, the exploration of an alternative path that uses parse trees instead of abstract syntax trees, and the investigation of the impact on recall and precision when clone analyses insist on consistent parameter renaming.     

JastAdd—a Java-based system for implementing front ends

We describe JastAdd, a Java-based system for specifying and implementing the parts of compiler front ends that follow parsing. The system is built on top of a traditional Java parser generator which is used for parsing and tree building. JastAdd adds facilities for specifying and generating object-oriented abstract syntax trees with both declarative behavior (using Reference Attributed Grammars (RAGs)) and imperative behavior (using ordinary Java code). The behavior can be modularized into different aspects, e.g. name analysis, type checking, code generation, etc., that are woven together into classes. The class weaving technique has many advantages over the often used Visitor pattern in that it provides a safe and much simpler interface for many applications and in that it supports modularization of not only methods, but also data. Class weaving is also easy and useful to combine with Visitor techniques in order to achieve the best of both. We also describe the implementation of the RAG evaluator (optimal recursive evaluation) which is implemented very conveniently using Java classes, interfaces, and virtual methods.     

Static analysis of XML transformations in Java

XML documents generated dynamically by programs are typically represented as text strings or DOM trees. This is a low-level approach for several reasons: 1) traversing and modifying such structures can be tedious and error prone, 2) although schema languages, e.g., DTD, allow classes of XML documents to be defined, there are generally no automatic mechanisms for statically checking that a program transforms from one class to another as intended. We introduce XACT, a high-level approach for Java using XML templates as a first-class data type with operations for manipulating XML values based on XPath. In addition to an efficient runtime representation, the data type permits static type checking using DTD schemas as types. By specifying schemes for the input and output of a program, our analysis algorithm will statically verify that valid input data is always transformed into valid output data and that the operations are used consistently.