First, a demo! Overview: How does this work? The entry point (load-st.fn) Some Smalltalk bindings The Grammar (smalltalk.g) What does this parse to in practice? The Smalltalk base library (st.st) One of the example programs in the FN programming language is a tiny Smalltalk implementation, in about 400 lines of code. I wrote FN and this example over a decade ago, but it wasn’t open source until 2020, so I failed to write it all up so far. But as it came up in a discussion over beers on the side of the Open Source Summit, I figured it might be a good idea to explain a bit how this works, because it’s a very succinct (but also dense) way to define a language. First, a demo! Start up the interactive Smalltalk interpreter with: ./fn -S examples/load-st.fn It brings up an interactive prompt like this: ST> 1 methods (isOdd > = < upto: / - + * isEven asString %) ST> ', ' join: ((1 upto: 10) map: #asString) "1, 2, 3, 4, 5, 6, 7, 8, 9" ST> The Smalltalk expression ', ' join: ((1 upto: 10) map: #asString) formats the numbers 1 to 10 as strings and joins all these strings into a comma-delimited list. Overview: How does this work? The magic that makes this work is a PEG-based grammar definition language in which each nonterminal rule translates directly into a Lisp expression. The implementation is split up into these three files: load-st.fn smalltalk.g st.st load-st.fn (113 lines) is the entry point and defines some prerequisites in Lisp smalltalk.g defines the grammar and how that grammar maps to Lisp. st.st is implemented in Smalltalk and defines several methods for existing types (booleans, dictionaries, etc.). It also has bindings for GNU libreadline and implements the interactive REPL’s main loop. The following three sections go into detail about each of these three files. The entry point (load-st.fn) The load-st.fn Lisp file is the entry point. It does the following steps in order: Load the Smalltalk grammar Define some Lisp macros used by the grammar Create Smalltalk bindings (methods) for some basic existing Lisp functionality like evaluating closures, and basic operators that FN otherwise just has free-standing functions for. Load and parse the st.st file (see below) Dynamically load the libreadline C library and create a Smalltalk binding. (This library provides the bash-like editing facility for the interactive prompt.) Create a Main class with a main function, run the code from st.st (which defines the Main>>main method) and invoke the Main>>main method. Some Smalltalk bindings For example, we slap a few methods with Smalltalk-flavoured names onto the preexisting Array type: (defm (type-of Array) 'newWithCapacity: (capacity) (make-array capacity)) (defm Array 'size () (array-size self)) (defm Array 'asList () (array->list self)) (defm Array 'at: (pos) (array-ref self pos)) (defm Array 'set:at: (value pos) (array-set! self pos value)) When the method name contains a colon (e.g., set:at:), that is a place where Smalltalk’s interleaved method call notation expects an argument, so the method needs to have that same number of arguments. In this object model, methods are single-dispatch and attached to a single type (unlike in other Lisps, where a multimethod can specialize on multiple types). And this is the Readline type, which exposes the Lisp readline binding in a Smalltalky way: (deftype Readline) (defm Readline 'addToHistory: (str) (add-history str)) ; from readline module (defm Readline 'readline: (prompt) (readline prompt)) (def RL ($make Readline nil)) The file also loads st.st and evaluates it, before calling the main method on the Main object. (main is defined in st.st and implemented in Smalltalk, so it has to be done in that order.) The Grammar (smalltalk.g) The grammar in smalltalk.g is spelled out in FN’s grammar definition language. This file defines how to parse Smalltalk, and constructs Lisp source code directly. There is no intermediate definition of an Abstract Syntax Tree, as Lisp’s S-Expressions already have the necessary structure required to run the code. Where more significant transformations are needed, these are implemented as Lisp macros. The grammar definition language is based on Bryan Ford’s Parsing Expression Grammars (PEGs) and on OMeta, developed by Allessandro Warth and Ian Piumarta at Alan Kay’s VPRI. It has a different syntax, but OMeta semantics were the goal. Here is an example rule from the smalltalk.g file: literal-number ::= DIGIT+:ds => (string->int (list->string ds)); The literal-number rule accepts one or more DIGITs in a sequence. The + operator in DIGIT+ makes it a list and puts the individual characters produced by DIGIT into a Lisp list. For instance, the string “123” becomes the Lisp value (#\1 #\2 #\3). This list value is then captured in the variable ds, using the :ds notation. On the right hand side, we have a Lisp expression (string->int (list->string ds)) that transforms the (#\1 #\2 #\3) value into the value that the literal-number rule should produce: It first turns it into the string "123" with list->string, then into an integer using string->int. The grammar definition language also supports meta-rules: tk P ::= WHITESPACE* P:t WHITESPACE* => t; literal-expr ::= tk(literal-number) | tk(literal-character) | tk(string) | tk(literal-symbol); tk is the “token” meta-rule which is parametrized over P. It is almost the same as a bare P, but accepts an arbitrary number of whitespace on either side of it, discarding the whitespace and producing whatever P produces. The literal-expr rule makes use of this by transforming other rules like literal-number into a variant that accepts surrounding whitespace. With this trick, there is no need for a separate tokenization step. A more complicated example for meta-rules is listof: listof item sep ::= item:a (sep item:it => it)*:as => (cons a as); statements ::= listof(statement, tk(".")); listof accepts a sequence of alternating item and sep, where the list needs to both start and end with an item. What does this parse to in practice? ST> Smalltalk parse: '(1 < 2) ifTrue: [ 42 ]' (send (send 1 (quote <) 2) (quote ifTrue:) (lambda nil 42)) As you can see, the expression (1 < 2) ifTrue: [ 42 ] is being parsed into the following Lisp expression (in slightly more conventional notation): (send (send 1 '< 2) 'ifTrue: (lambda () 42)) As Smalltalk is a purely object oriented language, almost everything is a “message send”, which more contemporary languages would usually call a “method invocation”. The function (send RECEIVER METHOD ARGS+) invokes the method with the name METHOD (usually given as a quoted symbol) on the RECEIVER object, passing the ARGS arguments. (It looks up the type for RECEIVER, looks up a closure for that method name in the type’s method table and invokes it with the right arguments.) We have two message sends here because both < and ifTrue: are messages which are being sent in this Smalltalk snippet. In the inner message send, the RECEIVER is 1, the MESSAGE is the symbol < and the only argument is 2. In the outer message send, the RECEIVER is true (because 1 < 2), the MESSAGE is ifTrue: and the argument is the closure which evaluates to 42. The Smalltalk base library (st.st) The st.st file defines a minimal “base library” that you would expect like this or in a similar form in a Smalltalk system. An interesting pair of methods are these two implementations of the ifTrue: method on the types True and False: True>>ifTrue: aBlock [ aBlock value ] False>>ifTrue: aBlock [ ^ false ] True>>ifTrue: aBlock [ ... ] is the syntax for declaring the method ifTrue: on the type True with the argument aBlock and the body as indicated between the square brackets. When ifTrue: is called on True, it evaluates the aBlock closure by calling value on it. When ifTrue: is called on False, nothing happens. This simple definition shows how control flow constructs are regular methods in this Smalltalk variant: You can invoke ifTrue: on a boolean and pass the code to run in that case as a closure: (n % 5 = 0) ifTrue: [ 'Fizz' println ] Within a method body, square brackets denote a lambda expression. More complicated control flow constructs like loops are created with the same technique. This puts users in the position where they can invent their own loop constructs. (Because this Smalltalk dialect compiles to Lisp and inherits Lisp’s tail call optimization, loops can be defined recursively.)