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:
- Pure (no side-effects)
- Pattern matching
- Based on term-rewriting
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|
Execution stops when the runtime system cannot apply any further rules.
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.
What comes up next?
In the next part, we will take a look at the grammar of Simpla.