Implementing a Programming Language from Scratch - Part 1: Introduction

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:

TermRewritten TermApplied Rule
fact 3fact' 3 1Rule 1
fact' 3 1fact' (3 - 1) (3 * 1)Rule 2b
fact' (3 - 1) (3 * 1)fact' 2 3Internal
fact' 2 3fact' (2 - 1) (2 * 3)Rule 2b
fact' (2 - 1) (2 * 3)fact' 1 6Internal
fact' 1 6fact' (1 - 1) (1 * 6)Rule 2b
fact' (1 - 1) (1 * 6)fact' 0 6Internal
fact' 0 66Rule 2a
6n/an/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.