Go implementations of FP language interpreters

My go-machines repo gathers various interpreter-coding experimentations and explorations, some of them based on certain classic papers, such as Pascal's P-Code or the timeless Brainf*ck.

More substantive is the from-scratch ToyLam interpreter for a vaguely-ML-like-looking functional programming language with plenty of examples, including a fully-functioning JSON Parser!

Also quite elaborate are these two:


The SAPL interpreter implementation follows "Efficient Interpretation by Transforming Data Types and Patterns to Functions" (Jan Martin Jansen, Pieter Koopman, Rinus Plasmeijer).

More specifically, this implementation in Go is of the elegantly slim spec on pages 8-9 (chapter 1.4), excluding all the optimizations starting from section 1.4.1 (p.9ff). No GC / heap / dump etc, stack-only. Go does GC anyway.

Divergence from the paper: NumArgs is not carried around with the Func Ref but stored in the top-level-funcs array together with that func's expression.


Exploratory slow-paced walk through:

A minimal (aka. lacking higher-level syntactic sugars) Functional Language named Core is implemented in various interpreter VMs.

To play, you run cmd/corelang-dummyrepl that picks up the most essential definitions from prelude.go (SKI++ basically) and parses various playful extra definitions from its dummy-mod-src.go, also readlines ad-hoc user definitions and invokes evaluation runs when prompted.

Lexing + parsing (in syn) is from scratch, not 'by the book'. But the above materials were then followed closely to approach implementing these graph-reduction machines as follows:

  • Template Instantiation Machine: evaluation by ad-hoc graph construction/instantiation and traversal/reduction, no real separate pre-processing / compilation stage

    incomplete: lacking (functioning) arithmetic, conditionals, and constructors, but the prelude-defs work — had to move on to the cooler stuff below, given the template-instantiation machine's real-world uselessness (except for newcomers testing the waters)

  • G-Machine: completed all levels (mark 7 — but somehow still failed to do proper lambdas / lambda-lifting / non-nilary local LET defs — still, one must move on) — involves fairly intricate compilation schemes to this virtual reduction-machine's rather convoluted (essentially) byte-code — better (than above one, but still atrocious) execution characteristics (linear pre-generated instruction stream instead of graph traversal)
  • Three-Instruction Machine: — skipped entirely
  • Spineless Tagless G-Machine: — in progress