Debugging hygienic macros

Over the past two decades, Scheme macros have evolved into a powerful API for the compiler front end. Like Lisp macros, their predecessors, Scheme macros expand source programs into a small core language; unlike Lisp systems, Scheme macro expanders preserve lexical scoping, and advanced Scheme macro systems handle other important properties such as source location. Using such macros, Scheme programmers now routinely develop the ultimate abstraction: embedded domain-specific programming languages.Unfortunately, a typical Scheme programming environment provides little support for macro development. This lack makes it difficult for programmers to debug their macros and for novices to study the behavior of macros. In response, we have developed a stepping debugger specialized to the concerns of macro expansion. This debugger presents the macro expansion process as a linear rewriting sequence of annotated terms; it graphically illustrates the binding structure of the program as expansion reveals it; and it adapts to the programmer’s level of abstraction, hiding details of syntactic forms that the programmer considers built-in.     

PIT: A macro-implemented implementation language

An implementation technique called PIT, for pseudo instructional technique, is described which utilizes the macro capabilities of most macro assemblers. A low level machine architecture is described via a set of macros that include some ‘high level’ features. Since the macros manipulate computer words, and refer to actual registers, their implementation in a system is relatively efficient, but since they do not reflect any one particular hardware design, they can be implemented by almost any macro assembler. Tests are built into the macros so that a PIT program will run without change on any machine that has defined these macros This technique should provide an alternative to using higher level languages as implementation languages if the object code produced by those compilers is deemed too slow (or too large) for the application that is being programmed.     

A sentence generator for a compiler for PT,a pascal subset

An implementation of a sentence generator system for a compiler for PT, a subset of Pascal, is discussed. Using the syntax definition of PT, the system automatically produces leftmost generations in a pseudorandom fashion. Syntactically correct as well as compile-time correct programs can be generated. In the generation of compile-time correct programs, only those statements that satisfy the contextual constraints imposed by the declarative part of the generated program are generated. The system also provides the facility of producing programs that have lexical or syntactic errors. All the generated programs are printed with appropriate indentations to show structural properties. Furthermore, the number of procedures in the generated program, the number of statements, identifier length and the number of generations can be controlled. The implementation has been successfully used for testing an error recovery parser as well as an intermediate code generator for PT.     

Global analysis and transformations in preprocessed languages

Tool support for refactoring code written in mainstream languages such as C and C++ is currently lacking due to the complexity introduced by the mandatory preprocessing phase that forms part of the C/C++ compilation cycle. The definition and use of macros complicates the notions of scope and of identifier boundaries. The concept of token equivalence classes can be used to bridge the gap between the language proper semantic analysis and the non-preprocessed source code. The CScout toolchest uses the developed theory to analyze large interdependent program families. A Web-based interactive front end allows the precise realization of rename and remove refactorings on the original C source code. In addition, CScout can convert programs into a portable obfuscated format or store a complete and accurate representation of the code and its identifiers in a relational database.     

Regression test selection for C++ software

Regression testing is an important but expensive software maintenance activity performed with the aim of providing confidence in modified software. Regression test selection techniques reduce the cost of regression testing by selecting test cases for a modified program from a previously existing test suite. Many researchers have addressed the regression test selection problem for procedural language software, but few have addressed the problem for object‐oriented software. This paper presents a regression test selection technique for use with object‐oriented software. The technique constructs graph representations for software, and uses these graphs to select test cases, from the original test suite, that execute code that has been changed for the new version of the software. The technique is strictly code based, and requires no assumptions about the approach used to specify or test the software initially. The technique applies to modified and derived classes, and to application programs that use modified classes. Copyright © 2000 John Wiley & Sons, Ltd.     

代码标识符归一化研究现状及发展趋势

作为代码分析和理解的重要内容,代码标识符及其归一化是国际学术界的前沿热点研究领域。标识符归一化旨在将标识符解析成自然语言词汇,以提高代码的可理解性和可维护性。标识符归一化主要包括两个极具挑战性的步骤,分别为组合词拆分和缩写词扩充。文中详细介绍了代码标识符归一化的研究现状,并进行了深入分析,总结出现有工作的困难和不足。同时,为了解决标识符归一化面临的困难和挑战,对该领域可行的解决思路和未来的发展趋势进行了归纳和展望,希望引导更多的研究者投入到这个重要的研究领域。     

Expressing checkable properties of dynamic systems: the Bandera Specification Language

Research on how to reason about correctness properties of software systems using model checking is advancing rapidly. Work on extracting finite-state models from program source code and on abstracting those models is focused on enabling the tractable checking of program properties such as freedom from deadlock and assertion violations. For the most part, the problem of specifying more general program properties has not been considered. In this paper, we report on the support for specifying properties of dynamic multi-threaded Java programs that we have built into the Bandera system. Bandera extracts finite-state models, in the input format of several existing model checkers, from Java code based on the property to be checked. The Bandera Specification Language (BSL) provides a language for defining general assertions and pre/post conditions on methods. It also supports the definition of observations that can be made of the state of program objects and the incorporation of those observations as predicates that can be instantiated in the scope of object quantifiers and used in describing common forms of state/event sequencing properties. We illustrate how BSL can be used to formulate a variety of system correctness properties for several multi-threaded Java applications. Published online: 2 October 2002     

An algebraic approach to the design of compilers for object-oriented languages

In this paper we describe an algebraic approach to construct provably correct compilers for object-oriented languages; this is illustrated for programs written in a language similar to a sequential subset of Java. It includes recursive classes, inheritance, dynamic binding, recursion, type casts and test, assignment, and class-based visibility, but a copy semantics. In our approach, we tackle the problem of compiler correctness by reducing the task of compilation to that of program refinement. Compilation is identified with the reduction of a source program to a normal form that models the execution of object code. The normal form is generated by a series of correctness-preserving transformations that are proved sound from the basic laws of the language; therefore it is correct by construction. The main advantages of our approach are the characterisation of compilation within a uniform framework, where comparisons and translations between semantics are avoided, and the modularity and extensibility of the resulting compiler.     

基于多特征的静态软件胎记提取算法

针对使用现有软件胎记进行程序抄袭检测结果不准确的问题,提出一种新的静态软件胎记提取算法。该算法产生的程序胎记由软件的两个方面特征综合生成。算法对源程序和可疑程序进行预处理得到程序元信息,然后通过元信息获取程序的应用程序接口（API）调用集合和指令序列作为两个特征,综合这两项特征生成软件胎记;接着,计算源程序与可疑程序的软件胎记之间的相似度,通过相似度判定两程序之间是否存在抄袭行为。实验验证了该算法得到的软件胎记具有可信性和弹性,与传统的k-gram软件胎记相比更具有弹性。     

Dynamic analysis of Java program concepts for visualization and profiling

Concept assignment identifies units of source code that are functionally related, even if this is not apparent from a syntactic point of view. Until now, the results of concept assignment have only been used for static analysis, mostly of program source code. This paper investigates the possibility of using concept information within a framework for dynamic analysis of programs. The paper presents two case studies involving a small Java program used in a previous research exercise, and a large Java virtual machine (the popular Jikes RVM system). These studies investigate two applications of dynamic concept information: visualization and profiling. The paper demonstrates two different styles of concept visualization, which show the proportion of overall time spent in each concept and the sequence of concept execution, respectively. The profiling study concerns the interaction between runtime compilation and garbage collection in Jikes RVM. For some benchmark cases, we are able to obtain a significant reduction in garbage collection time. We discuss how this phenomenon might be harnessed to optimize the scheduling of garbage collection in Jikes RVM.     

Handle系统与域名系统互联互通机制:一种基于标记语言描述协议数据单元的实现

基于对理论和实践两个层面的认识，Handle系统和域名系统将在未来很长一段时间内共存，而两种标志解析系统的解析协议和编码规则并不兼容，导致两者之间的数据空间无法共享，信息无法流通，降低了用户体验。因此，两种标志符解析系统的互联互通是当前亟需解决的一个问题。通过分析已有解决方案的利弊，发现协议数据单元与协议本身的分离可解决两个系统的解析协议和编码规则不兼容问题。利用这一分离机制，设计并实现了一种基于代理服务器的Handle系统与域名系统互联互通机制。实验结果表明，相对于传统客户端-服务器模式而言，该机制在不同应用场景下解析响应时间增量占比小，均在可接受范围内。     

Reusability Through Program Transformations

We describe a methodology and supporting programming environment that provide for reuse of abstract programs. Abstract programs are written using notations and constructs natural to the problem domain in a language realized by syntactic extension of a base language. Program transformations are employed to refine an abstract program into its concrete counterpart. We discuss the use of the methodology in the setting of rapid prototyping and custom tailoring.     

Semantic clustering: Identifying topics in source code

Many of the existing approaches in Software Comprehension focus on program structure or external documentation. However, by analyzing formal information the informal semantics contained in the vocabulary of source code are overlooked. To understand software as a whole, we need to enrich software analysis with the developer knowledge hidden in the code naming. This paper proposes the use of information retrieval to exploit linguistic information found in source code, such as identifier names and comments. We introduce Semantic Clustering, a technique based on Latent Semantic Indexing and clustering to group source artifacts that use similar vocabulary. We call these groups semantic clusters and we interpret them as linguistic topics that reveal the intention of the code. We compare the topics to each other, identify links between them, provide automatically retrieved labels, and use a visualization to illustrate how they are distributed over the system. Our approach is language independent as it works at the level of identifier names. To validate our approach we applied it on several case studies, two of which we present in this paper.Note: Some of the visualizations presented make heavy use of colors. Please obtain a color copy of the article for better understanding.     

Compiling communication-efficient programs for massively parallelmachines

A method of generating parallel target code with explicit communication for massively parallel distributed-memory machines is presented. The source programs are shared-memory parallel programs with explicit control structures. The method extracts syntactic reference patterns from a program with shared address space, selects appropriate communication routines, places these routines in appropriate locations in the target program text and sets up correct conditions for invoking these routines. An explicit communication metric is used to guide the selection of data layout strategies     

Static test case prioritization using topic models

Software development teams use test suites to test changes to their source code. In many situations, the test suites are so large that executing every test for every source code change is infeasible, due to time and resource constraints. Development teams need to prioritize their test suite so that as many distinct faults as possible are detected early in the execution of the test suite. We consider the problem of static black-box test case prioritization (TCP), where test suites are prioritized without the availability of the source code of the system under test (SUT). We propose a new static black-box TCP technique that represents test cases using a previously unused data source in the test suite: the linguistic data of the test cases, i.e., their identifier names, comments, and string literals. Our technique applies a text analysis algorithm called topic modeling to the linguistic data to approximate the functionality of each test case, allowing our technique to give high priority to test cases that test different functionalities of the SUT. We compare our proposed technique with existing static black-box TCP techniques in a case study of multiple real-world open source systems: several versions of Apache Ant and Apache Derby. We find that our static black-box TCP technique outperforms existing static black-box TCP techniques, and has comparable or better performance than two existing execution-based TCP techniques. Static black-box TCP methods are widely applicable because the only input they require is the source code of the test cases themselves. This contrasts with other TCP techniques which require access to the SUT runtime behavior, to the SUT specification models, or to the SUT source code.     

Concise and consistent naming

Approximately 70% of the source code of a software system consists of identifiers. Hence, the names chosen as identifiers are of paramount importance for the readability of computer programs and therewith their comprehensibility. However, virtually every programming language allows programmers to use almost arbitrary sequences of characters as identifiers which far too often results in more or less meaningless or even misleading naming. Coding style guides somehow address this problem but are usually limited to general and hard to enforce rules like “identifiers should be self-describing”. This paper renders adequate identifier naming far more precisely. A formal model, based on bijective mappings between concepts and names, provides a solid foundation for the definition of precise rules for concise and consistent naming. The enforcement of these rules is supported by a tool that incrementally builds and maintains a complete identifier dictionary while the system is being developed. The identifier dictionary explains the language used in the software system, aids in consistent naming, and supports programmers by proposing suitable names depending on the current context.     

Biomac: Block structured programming using PDP-11 assembler language

Users of small computers must often program in assembler language. Macros are described which assist in the construction of block structured programs in assembler language. The macros are used in practical day-to-day programming in a cardiac electrophysiology laboratory in which the coarse grained control provided by the local FORTRAN compiler is not sufficient for, and even hinders, the writing of clear, easy to understand programs. The macros provide nestable control structures in place of the less structured transfers of conventional assembler language. The arithmetic and input/output control provided by the architecture of the machine is left fully available. The control structures implemented include conditional (IF, CASE), iteration (WHILE, REPEAT/UNTIL, FOR) and subroutine (PROC, CALL, etc.) constructs. No control of variable scope is provided. The macro implementation is discussed along with the code generated. There is a discussion of architectural features which allow the macros to be independent of specific register usage and addressing mode. Experience with use of the macros in a high-speed, real-time data acquisition and display environment is presented. We conclude that these macros are easy to use and assist in program readability and documentation.     

Extensions to the C programming language for enhanced fault detection

The acceptance of the C programming language by academia and industry is partially responsible for the ‘software crisis’. The simple, trusting semantics of C mask many common faults, such as range violations, which would be detected and reported at run-time by programs coded in a robust language such as Ada.

1 Ada is a registered trademark of the U.S. Government (Ada Joint Program Office)

This needlessly complicates the debugging of C programs. Although the assert macro lets programmers add run-time consistency checks to their programs, the number of instantiations of this macro needed to make a C program robust makes it highly unlikely that any programmer could correctly perform the task. We make some unobtrusive extensions to the C language which support the efficient detection of faults at run-time without reducing the readability of the source code. Examples of the extensions are automatic checking of error codes returned by library routines, constrained subtypes and detection of references to uninitialized and/or non-existent array elements.     

A support system for interactive languages

The implementation of a support system for interactive languages is described, which include a controlling routine, a macro processor, lexical and syntactic analysis routines, semantic actions, error handling and analysis, log and code generation routines. There are also utility programs for generating the state tables for the syntax analysis. By using a structured programming approach these routines have been developed very quickly, but can still be developed and enhanced due to a well-defined working environment, a simple approach to coding and reasonable internal documentation.     

Deriving correctness properties of compiled code

When developing safety-critical software, it is the correctness of the object code that is paramount. However, it is desirable to perform formal verification on the source program. To ensure that correctness results proved about the source program do apply to the object code, the compiler used can be formally verified. However, care must be taken to ensure that the compiler correctness theorem proved is suitable. We have combined a derived programming logic with a verified compiler for a generic subset of the Vista structured assembly language. We show how correctness properties of object code can be formally derived from corresponding correctness properties of the source program which have been proved using the programming logic. Thus we can be sure the results do apply to the object code. The work described has been performed using the HOL system and so is machine-checked.