Domain: Programming Language Design and Implementation (Lisp, JVM Architecture)
Abstract:
This presentation introduces Murmel, a Lisp dialect designed as a manageable subset of Common Lisp (CL) intended for experimentation, and its accompanying implementation, JMurmel. JMurmel is written in Java, runs on the JVM, and is characterized by a deliberate design choice prioritizing simplicity and small size over full CL compatibility.
Murmel deviates from CL by adopting a Lisp-1 structure, distinct handling of dynamic variable binding, and the inclusion of Clojure-like threading macros, generators, and integrated hash tables/vectors. The core language is limited to 182 primitives. The JMurmel implementation (currently a single 13,000-line Java file) includes both a naïve, classic interpreter and a compiler that generates Java source code before invoking the JDK compiler. The system addresses the JVM’s lack of native tail call elimination by transforming self-recursion into loops and utilizing a trampoline for general tail calls. Benchmarks suggest performance comparable to ABCL and ECL. The utility of JMurmel is primarily situated in contexts requiring a small, teachable scripting or embedded language that integrates seamlessly within a Java ecosystem, leveraging the portability of the JVM and, through WebAssembly (Wasm) compilation, running directly in a browser environment.
Summary of the Transcript:
0:00 Project Introduction: Robert Mayer introduces Murmel, a Lisp dialect based on a subset of Common Lisp, and JMurmel, its implementation written in Java for the JVM. Both are noted as ongoing hobby projects.
3:46 Murmel Language Overview: Murmel is based on a CL subset and includes extensions like threading macros (known from Clojure), generators, and utilities (stolen from Alexandria and Serapeum).
4:11 Language Structure and Size: The design principle was to create a manageable language size for experimentation. The core language, which includes letrec and omits several CL special forms, consists of 182 total symbols (Primitives, constants, global variables). The library is separate, totaling close to 1,600 lines of code written in Murmel itself.
7:12 Key Differences from Common Lisp: Murmel is a Lisp-1 (a unified namespace for functions and variables). Special/dynamic variables are handled differently, allowing users to explicitly specify dynamic binding when rebinding a global variable (lexical is the default). It currently lacks a package system, records, closures, and object-oriented programming features.
8:31 Numerical Types: Murmel is limited to fixed numbers and double floats. All math functions currently return doubles, which is noted as a potential limitation for future correction.
10:34 Data Structures and Looping: Hash tables are integrated into the core language and support sorted maps and literal notation. Looping constructs are limited to recursion and the named let macro (endl, stolen from Scheme), as all looping can be achieved through recursion.
11:34 JMurmel Implementation Details: The current implementation is written in Java, delivering a single JAR file (under 1MB, excluding the JVM). This JAR contains both an interpreter and a compiler, developed intentionally as a single file (13,000 lines of code) as an exercise in architectural contrast to typical development practices.
12:53 Design Philosophy of JMurmel: JMurmel is lightweight in terms of features, making it easy to understand. The total implementation size depends on whether the JVM (10 million lines, 50MB) is included in the size calculation.
14:31 Performance Benchmarks: Initial, simple benchmarks show JMurmel performance to be generally comparable in magnitude to ABCL (Armed Bear Common Lisp) and ECL (Embedded Common Lisp), though slower than SBCL (Steel Bank Common Lisp).
14:48 Interpreter Architecture: The interpreter uses a super naïve, classic implementation style (eval/apply/parse). The internal eval function utilizes a switch statement wrapped in a loop, enabling the last form of a list to jump to the beginning of the switch statement without consuming host stack.
16:20 Compiler Strategy: The compiler strategy is naïve; it does not directly emit bytecode like ABCL. Instead, it generates readable (decipherable) Java source code, then invokes the JDK compiler.
17:05 Tail Call Elimination (TCE): Since the JVM lacks native TCE, self-recursion is trivially transformed into standard Java loops. General tail calls are managed using a trampoline mechanism, which is noted as critical for performance.
18:02 Use Cases: Murmel is positioned for environments where full industrial-strength Lisp is impractical, such as embedded systems, scripting for other applications where simplicity is key, and within the Java ecosystem (e.g., build tools). Its simplicity is also suited for teaching programming.
22:53 Web Capability: JMurmel can run in a browser (online REPL) and on phones. This functionality is achieved by compiling the JVM to WebAssembly (Wasm), allowing Java programs to run on Wasm-supporting platforms.
25:08 Experimentation and Lambda Calculus: Demonstrations show the ability to disable features (e.g., cons cells) and implement them manually, illustrating cons cells, CDR, and CAR being implemented using lambda calculus.