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:

```pikchr
boxht *= 0.5
box "load-st.fn"
arrow up 30% right
box "smalltalk.g"
arrow from last arrow.start down 30% right
box "st.st"
```

* [`load-st.fn`](https://github.com/gnoack/fn/blob/master/examples/load-st.fn) (113 lines) is the entry point and defines some prerequisites in Lisp
* [`smalltalk.g`](https://github.com/gnoack/fn/blob/master/examples/smalltalk.g) defines the grammar and how that grammar maps to Lisp.
* [`st.st`](https://github.com/gnoack/fn/blob/master/examples/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`](https://github.com/gnoack/fn/blob/master/examples/load-st.fn) Lisp file is the entry point.  It does the following steps in order:

1. Load the Smalltalk grammar
2. Define some Lisp macros used by the grammar
3. 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.
4. Load and parse the `st.st` file (see below)
5. Dynamically load the `libreadline` C library and create a Smalltalk binding.
   (This library provides the bash-like editing facility for the interactive prompt.)
6. 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`](https://github.com/gnoack/fn/blob/master/examples/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)](https://bford.info/pub/lang/peg/)
and on [OMeta](https://tinlizzie.org/VPRIPapers/tr2007003_ometa.pdf),
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 *DIGIT*s 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`](https://github.com/gnoack/fn/blob/master/examples/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.)