We rebuilt Racket on Chez Scheme, and it works well—as long as we're allowed a few patches to Chez Scheme. DrRacket runs, the Racket distribution can build itself, and nearly all of the core Racket test suite passes. Maintainability and performance of the resulting implementation are good, although some work remains to improve end-to-end performance. The least predictable part of our effort was how big the differences between Racket and Chez Scheme would turn out to be and how we would manage those differences. We expect Racket on Chez Scheme to become the main Racket implementation, and we encourage other language implementers to consider Chez Scheme as a target virtual machine.

The Revised⁶ Report on the Algorithmic Language Scheme added a mechanism to the Scheme programming language for creating new record types procedurally. While many programming languages support user defined, structured data types, these are usually handled syntactically, so that the compiler can make choices at compile time about the memory layout of these data types. The procedural record types in Scheme, however, can be constructed at run time, making the efficient run-time representation of record types important to ensure good run-time performance. The run-time representation used in our implementation provides an extended model for record types allowing record types to represent foreign scalar data types, e.g., machine word integers, and allows the base record type to be extended to create non-R6RS record-type systems. This article describes our run-time representation for record types, how the garbage collector handles foreign scalar data types, and includes extended record type systems both for an object-oriented programming model and a representation of foreign structured data types.

Statically reasoning in the presence of exceptions and about the effects of exceptions is challenging: exception-flows are mutually determined by traditional control-flow and points-to analyses. We tackle the challenge of analyzing exception-flows from two angles. First, from the angle of pruning control-flows (both normal and exceptional), we derive a pushdown framework for an object-oriented language with full-featured exceptions. Unlike traditional analyses, it allows precise matching of throwers to catchers. Second, from the angle of pruning points-to information, we generalize abstract garbage collection to object-oriented programs and enhance it with liveness analysis. We then seamlessly weave the techniques into enhanced reachability computation, yielding highly precise exception-flow analysis, without becoming intractable, even for large applications. We evaluate our pruned, pushdown exception-flow analysis, comparing it with an established analysis on large scale standard Java benchmarks. The results show that our analysis significantly improves analysis precision over traditional analysis within a reasonable analysis time.

Sound malware analysis of Android applications is challenging. First, object-oriented programs exhibit highly interprocedural, dynamically dispatched control structure. Second, the Android programming paradigm relies heavily on the asynchronous execution of multiple entry points. Existing analysis techniques focus more on the second challenge, while relying on traditional analytic techniques that suffer from inherent imprecision or unsoundness to solve the first.

We present Anadroid, a static malware analysis framework for Android apps. Anadroid exploits two techniques to soundly raise precision: (1) it uses a pushdown system to precisely model dynamically dispatched interprocedural and exception-driven control-flow; (2) it uses Entry-Point Saturation (EPS) to soundly approximate all possible interleavings of asynchronous entry points in Android applications. (It also integrates static taint-flow analysis and least permissions analysis to expand the class of malicious behaviors which it can catch.) Anadroid provides rich user interface support for human analysts which must ultimately rule on the “maliciousness” of a behavior.

To demonstrate the effectiveness of Anadroid's malware analysis, we had teams of analysts analyze a challenge suite of 52 Android applications released as part of the Automated Program Analysis for Cybersecurity (APAC) DARPA program. The first team analyzed the apps using a version of Anadroid that uses traditional (finite-state-machine-based) control-flow-analysis found in existing malware analysis tools; the second team analyzed the apps using a version of Anadroid that uses our enhanced pushdown-based control-flow-analysis. We measured machine analysis time, human analyst time, and their accuracy in flagging malicious applications. With pushdown analysis, we found statistically significant (p < 0.05) decreases in time: from 85 minutes per app to 35 minutes per app in human plus machine analysis time; and statistically significant (p < 0.05) increases in accuracy with the pushdown-driven analyzer: from 71% correct identification to 95% correct identification.

The library construct added to Scheme by the Revised6 Report on Scheme (R6RS) provides a natural boundary for compilation units, particularly for separate compilation. Unfortunately, using the library as the compilation unit for Scheme programs can interfere with optimizations such as inlining that are important for good performance of compiled programs. Our Scheme system provides a way for specifying larger compilation units, the library group, which allows the source code from several libraries and, optionally, a program to be compiled as a single compilation unit. The library group form works well, but is not a good fit for situations where all of the source code is not available at compile time, particularly in the case where a library is distributed in binary form to be used by other library or application developers. In order to handle situations like this, we have introduced a new, automatic, cross-library optimization mechanism. The automatic cross-library optimization mechanism provides some of the benefits of the library group form without requiring modifications to the program and without requiring libraries to be compiled together. Cross-library optimization is supported by recording additional information in the library binary that can be used when the library is imported by another library or program. This paper describes our automatic cross-library optimization and compares it with the existing library group system.

Contemporary compilers must typically handle sophisticated high-level source languages, generate efficient code for multiple hardware architectures and operating systems, and support source-level debugging, profiling, and other program development tools. As a result, compilers tend to be among the most complex of software systems. Nanopass frameworks are designed to help manage this complexity. A nanopass compiler is comprised of many single-task passes with formally defined intermediate languages. The perceived downside of a nanopass compiler is that the extra passes will lead to substantially longer compilation times. To determine whether this is the case, we have created a plug replacement for the commercial Chez Scheme compiler, implemented using an updated nanopass framework, and we have compared the speed of the new compiler and the code it generates against the original compiler for a large set of benchmark programs. This paper describes the updated nanopass framework, the new compiler, and the results of our experiments. The compiler produces faster code than the original, averaging 15–27% depending on architecture and optimization level, due to a more sophisticated but slower register allocator and improvements to several optimizations. Compilation times average well within a factor of two of the original compiler, despite the slower register allocator and the replacement of five passes of the original 10 with over 50 nanopasses.

Many languages include a syntax for declaring programmer-defined structured data types, i.e., structs or records. R6RS supports syntactic record definitions but also allows records to be defined procedurally, i.e., via a set of run-time operations. Indeed, the procedural interface is considered to be the primitive interface, and the syntactic interface is designed to be macro expandable into code that uses the procedural interface. Run-time creation of record types has a potentially significant impact. In particular, record creation, field access, and field mutation cannot generally be open coded, as it can be with syntactically specified records. Often, however, the shape of a record type can be determined statically, and in such a case, performance equivalent to that of syntactically specified record types can be attained. This paper describes an efficient run-time implementation of procedural record types, discusses its overhead, and describes a set of compiler optimizations that eliminate the overhead when record-type information can be determined statically. The optimizations improve the performance of a set of representative benchmark programs by over 20% on average.

The flat-closure model for the representation of first-class procedures is simple, safe-for-space, and efficient, allowing the values or locations of free variables to be accessed with a single memory indirect. It is a straightforward model for programmers to understand, allowing programmers to predict the worst-case behavior of their programs. This paper presents a set of optimizations that improve upon the flat-closure model along with an algorithm that implements them, and it shows that the optimizations together eliminate over 50% of run-time closure-creation and free-variable access overhead in practice, with insignificant compile-time overhead. The optimizations never add overhead and remain safe-for-space, thus preserving the benefits of the flat-closure model.

The flexibility of dynamically typed languages such as JavaScript, Python, Ruby, and Scheme comes at the cost of run-time type checks. Some of these checks can be eliminated via control-flow analysis. However, traditional control-flow analysis (CFA) is not ideal for this task as it ignores flow-sensitive information that can be gained from dynamic type predicates, such as JavaScript’s instanceof and Scheme’s pair?, and from type-restricted operators, such as Scheme’s car. Yet, adding flow-sensitivity to a traditional CFA worsens the already significant compile-time cost of traditional CFA. This makes it unsuitable for use in just-in-time compilers.

In response, we have developed a fast, flow-sensitive type-recovery algorithm based on the linear-time, flow-insensitive sub-0CFA. The algorithm has been implemented as an experimental optimization for the commercial Chez Scheme compiler, where it has proven to be effective, justifying the elimination of about 60% of run-time type checks in a large set of benchmarks. The algorithm processes on average over 100,000 lines of code per second and scales well asymptotically, running in only O(n log n) time. We achieve this compile-time performance and scalability through a novel combination of data structures and algorithms.

High-level programming languages, like Scheme, typically represent data in ways that differ from the host platform to support consistent behavior across platforms and automatic storage management, i.e., garbage collection. While crucial to the programming model, differences in data representation can complicate interaction with foreign programs and libraries that employ machine-dependent data structures that do not readily support garbage collection. To bridge this gap, many high-level languages feature foreign function interfaces that include some ability to interact with foreign data, though they often do not provide complete control over the structure of foreign data, are not always fully integrated into the language and run-time system, and are often not as efficient as possible. This paper describes a Scheme syntactic abstraction for describing foreign data, a set of operators for interacting with that data, and an implementation that together provide a complete, well integrated, and efficient solution for handling structured data outside the Scheme heap.

Libraries and top-level programs are the basic units of portable code in the language defined by the Revised⁶ Report on Scheme. As such, they are naturally treated as compilation units, with source optimization and certain forms of compile-time error checking occurring within but not across library and program boundaries. This paper describes a library-group form that can be used to turn a group of libraries and optionally a top-level program into a single compilation unit, allowing whole programs to be constructed from groups of independent pieces and enabling cross-library optimization and compile-time error checking. The paper also describes the implementation, which is challenging partly because of the need to support the use of one library’s run-time exports when another library in the same group is compiled. The implementation does so without expanding any library in the group more than once, since doing so is expensive in some cases and, more importantly, semantically unsound in general. While described in the context of Scheme, the techniques presented in this paper are applicable to any language that supports both procedural macros and libraries, and might be adaptable to dependently typed languages or template meta-programming languages that provide full compile-time access to the source language.

In this paper we present two implementations of the pattern-matching macros λ^e and match^e for αKanren. The first implementation generates clean code, but our use of CPS-macros in its implementation leads to a problem in determining when a new binding needs to be introduced for a pattern variable. This problem stems from our delayed creation of bindings, where the comparison of identifiers is done first and then binders created in a later step. This may lead to an issue when macros generating λ^e or match^e expressions may appear to break hygiene because the CPS-macros incorrectly identify two identifiers as being the same. The second implementation addresses these concerns by using more traditional macros, generating bindings as new variables are encountered.

Software tools have become a central part of the scientific researchers’ toolbox, but developing them can prove a distraction from the central focus of a research team’s investigation. Dynamic languages, like Ruby, can provide an easy platform for rapid development and deployment of software that can be easily shared through SOAP, REST, or even RPC-style API interfaces with fellow researchers across the globe. In this extended abstract we present progress in addressing one of Ruby’s biggest shortcomings, performance. Our technique uses compiler analysis of Ruby’s C-based interpreter and core libraries in order to provide a basis for partial evaluation. The partial evaluator makes use of the results of this analysis along with a running Ruby session in order to evaluate more complex expressions than could normally be handled by traditional partial evaluation techniques, while ensuring that “unsafe” expressions are left for evaluation during run-time.

RubyWrite is a Domain Specific Language (DSL), embedded within Ruby, with the goal of providing an extensible, effective, portable, and easy to use framework for encoding source-level transformations. Embedding within Ruby provides access to the powerful features of Ruby, including its meta-programming capabilities. Ruby’s multi-paradigm programming model and flexible syntax drove our decision to use it as a host language. Easy integration with C interfaces lets us move performance critical operations to C, or link with external libraries. RubyWrite consists of three components, a tree builder, an unparser, and a tree rewriter. It has been used in multiple compiler research projects and as a teaching aid in a graduate-level compilers course. We expect RubyWrite to be widely applicable and a proof of concept in leveraging a modern language to write a portable compiler infrastructure core.

Contemporary commercial compilers typically handle sophisticated high-level source languages, generate efficient assembly or machine code for multiple hardware architectures, run under and generate code to run under multiple operating systems, and support source-level debugging, profiling, and other program development tools. As a result, commercial compilers tend to be among the most complex of software systems.

Nanopass frameworks are designed to help make this complexity manageable. A nanopass framework is a domain-specific language, embedded in a general purpose programming language, to aid in compiler development. A nanopass compiler is comprised of many small passes, each of which performs a single task and specifies only the interesting transformations to be performed by the pass. Intermediate languages are formally specified by the compiler writer, which allows the infrastructure both to verify that the output of each pass is well-formed and to fill in the uninteresting boilerplate parts of each pass.

Prior nanopass frameworks were prototype systems aimed at educational use, but we believe that a suitable nanopass framework can be used to support the development of commercial compilers. We have created such a framework and have demonstrated its effectiveness by using the framework to create a new commercial compiler that is a “plug replacement” for an existing commercial compiler. The new compiler uses a more sophisticated, although slower, register allocator and implements nearly all of the optimizations of the original compiler, along with several “new and improved” optimizations. When compared to the original compiler on a set of benchmarks, code generated by the new compiler runs, on average, 21.5% faster. The average compile time for these benchmarks is less than twice as long as with the original compiler. This dissertation provides a description of the new framework, the new compiler, and several experiments that demonstrate the performance and effectiveness of both, as well as a presentation of several optimizations performed by the new compiler and facilitated by the infrastructure.