BYU - Spring 2013 - CS 630 - 6/6 - Review
Matthew Ashcraft
Languages as Libraries
The main motivation behind this paper is the experimentation of new sub-languages, or modifications to host languages that become indistinguishable from the host language. A quote they offer from Guy Steele sums up their intentions; “I need to design a language that can grow.” For this to work, an extensible host language is needed that supports linguistic reuse. The language extension must be able to use the scoping mechanisms and namespace features of the host language. Providing all of these features to an experimental language is a difficult task, and requires a wide range of extension mechanisms. Fortunately the Racket platform offers all of these features to the user. The Racket platform uses a virtual machine and JIT compiler with a programming language that has all of these abilities. Due to the power and versatility of Racket, a user may change any aspect of their language to support their desired features. Some of the features provided by Racket are: lexicographical and parsed notation, static semantics, module linking, and optimization.
Racket derives its power from the Scheme macro language. One of the things Racket implemented on top of Scheme was making the language choice specific to each module. This means that each individual module may be implemented in different languages. In this case each language used has complete control over the modules using them. They can heavily rely upon the base language, or they can use completely different libraries they have developed themselves as the main language. Racket macro expander recursively traverses the syntax inputs, and the macro transformer turns syntax into syntax as it goes along. The macros may use either Racket libraries or primitives to compute desired syntax results. The authors state that Racket syntax objects come with three different types of APIs: constructors and accessors, syntax properties, and local expansion. They list a few examples within each of these. Racket supports importing and exporting language extensions using a first-order module system. There are two crucial parts of this module system. First, modules can export static bindings and value bindings without requiring the users to distinguish between them. Additionally the value bindings may be replace by static bindings without breaking the users. Secondly, the modules are compiled with fresh stores, meaning mutations to the state that occur during one compilation do not affect other compilations.
Typed Racket provides a type system and a mechanism for linking typed and untyped modules. This type system benefits from as much linguistic reuse as possible, and is done through the compiler. Linguistic reuse poses additional challenges on top of the type system. The six main challenges they faced were annotating bindings with type specifications, checking type correctness in a context sensitive fashion, type checking programs written in extensible languages, integrating type checking with separate compilation modules, providing safe interaction with untyped modules, and optimizing programs based upon type information. As a solution to the first challenge, they show how an untyped operation such as define may be typed. Next that point out that type checking is inherently context-sensitive, so that issue is taken care of. The next challenge of type checking extensible programs has two solutions: he type checker may be extended to handle new operations, or the new operation could be translated into a simpler form. Though the first solution works for all currently working operations in the Racket Libraries, it would be nearly impossible to keep up with day to day extensions. For this reason the second solution of making them easier is the better choice. The challenge of supporting modular programs is addressed by ensuring that compilation of Typed Racket always produces the same record of the types of exported bindings. The integration of untyped modules is handled by checking the value flow across the boundaries between typed and untyped modules. The last challenge is addressed by providing the type information to the compiler backed for better optimization to occur.
The initial explanation of their actual work revolves around a single-module typechecker. Because of the ability of macro writers to introduce new syntactic extensions, they work they present only covers a small set of core forms, and all other forms are reduced to these before they are type checked. They have constructed a driver to connect their typechecker to the program. They typechecker typechecks each form of the expanded body of the modules, then raises an error when an untypeable form arises. The resulting module is then constructed from the new core forms. Additionally they provide the initial environment for the program, and the define and lambda functions to bind syntax properties to bound variables. The typecheckers syntax is then briefly explained. They state that there are two distinctive parts of their syntax. The first is that the environment uses mutable table mapping identifiers to types based upon their bindings. The second is the type-of function, which reads the syntax properties attached to the syntax by define and lambda. This single-module type system may be scaled to the full typed Racket, with a few modifications of course. These modifications revolve around mutual recursion and complex definition forms, and is explained more thoroughly there.
In order to deal with multiple modules, the type information must be passed between them and ensure that the type information doesn't change based upon separate compilation. Racket namespaces are used to solve some of these problems. During expansion, identifiers in Racket are given globally unique names so that they are stable across multiple modules during the expansion process. This allows for identifiers to be imported without any scoping issues. One of the issues that Racket actually faces is that mutations to the type environment do not persist between modules. To fix this the writers included code in every module that propagates environment information every time the module is used. They also do work to wrap untyped programs to allow them to interact with the typed programs without causing damage to one another. These are explained as imports and exports to untyped macros. The exports from typed to untyped macros are more of a problem because the Typed Racket cannot control where the typed value is used in the untyped programs. Because of this dynamic checks are inserted to check that the typed values are used correctly in the untyped programs. The authors then sum up their results, which show Typed Racket to provide significant improvements over Racket.
The main contribution put forth by this paper is the thought that Racket is the ideal language to be used to experiment with new languages because of the language extension features it provides. As an example they demonstrate how Typed Racket is implemented, in an effort to show how other features could be implemented. These extensions are done through libraries, which provides great power and portability. This paper was fairly straight-forward, though by the end I forgot they were trying to show that Racket is a good language for experimenting on because it was so focused on Typed Racket. I had trouble understanding their driver syntax, but I'm sure that will be explained tomorrow. There were questions I had earlier on in the paper, but I forgot what they were.