An undergraduate compilers course poses significant challenges to students, in both the conceptual richness of the major components and in the programming effort necessary to implement them. In this paper, I argue that a related architecture, the interpreter, serves as an effective conceptual framework in which to teach some of the later stages of the compiler pipeline. This framework can serve both to unify some of the major concepts that are taught in a typical undergraduate course and to structure the implementation of a semester-long compiler project.
On the other hand, the construction of interpreters plays a prominent role in many courses on programming language design. The simplicity of an interpreter's core structure and the close correspondence to a language's semantics makes this a natural teaching tool, both for conceptual organization and for prototypical implementation of various language features @cite_7 @cite_12 . Abelson and Sussman's classic CS1 text @cite_11 even uses this structure to introduce the structure of a simple compiler, though the correspondence between the two is quickly buried in the details of code generation, and their compiler lacks many real-world features such as a semantic analysis phase.
@cite_12 @cite_7 @cite_11
109232922 2029065308 1507377794 2028053566
As a textbook suitable for the classroom or self-study, Michael Scott's Programming Language Pragmatics provides a worthy tour of the theory and practice of how programming languages are run on today's computers. Clearly organized and filled with a wide-ranging perspective on over 40 different languages, this book will be appreciated for its depth and breadth of coverage on an essential topic in computer science. With references to dozens of programming languages, from Ada to Turing and everything in between (including C, C++, Java, and Perl), this book is a truly in-depth guide to how code is compiled (or interpreted) and executed on computer hardware. Early chapters tend to be slightly more theoretical (with coverage of regular expressions and context-free grammars) and will be most valuable to the computer science student, but much of this book is accessible to anyone seeking to widen their knowledge (especially since recent standards surrounding XML make use of some of the same vocabulary presented here). The book has a comprehensive discussion of compilation and linking, as well as how data types are implemented in memory. Sections on functional and logical programming (illustrated with Scheme and Prolog, which are often used in AI research) can expand your understanding of how programming languages work. Final sections on the advantages--and complexities--of concurrent processing, plus a nice treatment of code optimization techniques, round out the text here. Each chapter provides numerous exercises, so you can try out the ideas on your own. Students will benefit from the practical examples here, drawn from a wide range of languages. If you are a self-taught developer, the very approachable tutorial can give you perspective on the formal definitions of many computer languages, which can help you master new ones more effectively. --Richard Dragan Topics covered: A survey of today's programming languages, compilation vs. interpretation, the compilation process, regular expression and context-free grammars, scanners and parsers, names, scopes and bindings, scope rules, overloading, semantic analysis, introduction to computer architecture, representing data, instruction sets, 680x0 and MIPs architectures, control flow and expression evaluation, iteration and recursion, data types, type checking, records, arrays, strings, sets, pointers, lists, file I O, subroutines, calling sequences and parameter passing, exception handling, coroutines, compile back-end processing, code generation, linking, object-oriented programming basics, encapsulation and inheritance, late binding, multiple inheritance, functional and logical languages, Scheme and Prolog, programming with concurrency, shared memory and message passing, and code optimization techniques. A brief account of the concept of partial computation is given in the context of the Pascal language. The manual conversion of programs into generating extensions is explained using examples of gradually increasing complexity. This culminates in a readily applicable but too-little known technique of converting interpreters into compilers without dealing directly with machine language. Students taking courses in language processing should be taught this technique and perhaps also the general principles underlying it. A simple example of the application of the technique is presented. Human agents are extremely flexible in dealing with Natural Language instructions. I argue that most instructions don't exactly mirror the agent's knowledge, but are understood by accommodating them in the context of the general plan the agent is considering; the accommodation process is guided by the goal(s) that the agent is trying to achieve. Therefore a NL system which interprets instructions must be able to recognize and or hypothesize goals; it must make use of a flexible knowledge representation system, able to support the specialized inferences necessary to deal with input action descriptions that do not exactly match the stored knowledge. The data that support my claim are Purpose Clauses (PCs), infinitival constructions as in @math , and Negative Imperatives. I present a pragmatic analysis of both PCs and Negative Imperatives. Furthermore, I analyze the computational consequences of PCs, in terms of the relations between actions PCs express, and of the inferences an agent has to perform to understand PCs. I propose an action representation formalism that provides the required flexibility. It has two components. The Terminological Box (TBox) encodes linguistic knowledge about actions, and is expressed by means of the hybrid system CLASSIC. To guarantee that the primitives of the representation are linguistically motivated, I derive them from Jackendoff's work on Conceptual Structures. The Action Library encodes planning knowledge about actions. The action terms used in the plans are those defined in the TBox. Finally, I present an algorithm that implements inferences necessary to understand @math , and supported by the formalism I propose. In particular, I show how the TBox classifier is used to infer whether @math can be assumed to match one of the substeps in the plan for @math , and how expectations necessary for the match to hold are computed. In this paper, we compose six di erent Python and Prolog VMs into 4 pairwise compositions: one using C interpreters; one running on the JVM; one using meta-tracing interpreters; and one using a C interpreter and a meta-tracing interpreter. We show that programs that cross the language barrier frequently execute faster in a meta-tracing composition, and that meta-tracing imposes a significantly lower overhead on composed programs relative to mono-language programs. 1. Overview Programming language composition aims to allow the mixing of programming languages in a fine-grained manner. This vision brings many challenging problems, from the interaction of language semantics to performance. In this paper, we investigate the runtime performance of composed programs in high-level languages. We start from the assumption that execution of such programs is most likely to be through composing language implementations that use interpreters and VMs, rather than traditional compilers. This raises the question: how do di erent styles of composition a ect performance? Clearly, such a question cannot have a single answer but, to the best of our knowledge, this issue has not been explored in the past. This paper's hypothesis is that meta-tracing - a relatively new technique used to produce JIT (Just-In-Time) compilers from interpreters (1) - will lead to faster interpreter composition than traditional approaches. To test this hypothesis, we present a Python and Prolog composition which allows Python programs to embed and call Prolog programs. We then implement the composition in four di erent ways, comparing the absolute times and the relative cross-language costs of each. In addition to the 'traditional' approaches to composing interpreters (in C and upon the JVM), we also investigate the application of meta-tracing to interpreter composition. The experiments we then carry out confirm our initial hypothesis. There is a long tradition of composing Prolog with other languages (with e.g. Icon (2), Lisp (3), and Smalltalk (4)) because one can express certain types of programs far easier in Prolog than in other languages. We have two additional reasons for choosing this pairing. First, these languages represent very di erent points in the language design space: Prolog's inherently