In the upcoming series of blog posts, I will implement a simple functional programming language from scratch. This language, let’s call it SIMPLA or Simpla, for “Simple Language”, will have the following features:
- Dynamically-typed
- Interpreted
- Functional
- Pure (no side-effects)
- Pattern matching
- Based on term-rewriting
Overview
Programs written in Simpla will roughly look like Haskell programs without type definitions. Here is an example of the factorial function specified in Simpla using tail recursion:
fact n = fact' n 1 -- Rule 1
fact' 0 a = a -- Rule 2a
fact' n a = fact' (n - 1) (n * a) -- Rule 2b
Functions in Simpla are rewrite rules! For instance, the term fact 3
will be rewritten to the final term 6
by going through the following
intermediate forms:
Term | Rewritten Term | Applied Rule |
---|---|---|
fact 3 | fact' 3 1 | Rule 1 |
fact' 3 1 | fact' (3 - 1) (3 * 1) | Rule 2b |
fact' (3 - 1) (3 * 1) | fact' 2 3 | Internal |
fact' 2 3 | fact' (2 - 1) (2 * 3) | Rule 2b |
fact' (2 - 1) (2 * 3) | fact' 1 6 | Internal |
fact' 1 6 | fact' (1 - 1) (1 * 6) | Rule 2b |
fact' (1 - 1) (1 * 6) | fact' 0 6 | Internal |
fact' 0 6 | 6 | Rule 2a |
6 | n/a | n/a |
Execution stops when the runtime system cannot apply any further rules.
Implementation choices
As for the choice of languages, I plan to use Javascript to implement the initial version of the Simpla interpreter and runtime. The reason for this decision is simple: Javascript is omnipresent!
This choice will allow everyone to load up the Simpla interpreter in their browsers and start playing with it immediately. It is also a good choice when it comes to visualizing the term rewriting.
If possible and time permits, I will, later on, rewrite Simpla in Simpla itself
and add a code generator that emits Javascript (or if you wish, C
).
What comes up next?
In the next part, we will take a look at the grammar of Simpla.