Developing Scheme Interpreter

2021-12-22 |

In this post, we will develop simple scheme interpeter for our very basic language. So we will create a simple repl based interpreter using mit scheme. (https://www.gnu.org/software/mit-scheme/)

Stage 1 - Hello World

We will pass number to our interpreter and interpreter will directly prints the number.

Syntax :

<s1> -> tNUMBER

(define s1 (lambda (e)
    (cond 
      ((number? e) e)
      ( else (error "s1: can not evaluate =>" e))
    )
))

Results:

;Value: s1

1 ]=> (s1 2)

;Value: 2

1 ]=> (s1 -5)

;Value: -5

1 ]=> (s1 'a)

;s1: can not evaluate => a

Stage 2 - Adding Procedure

Now we will add 'add' funcionality.

Grammer :

<s2> -> tNUMBER 
      | (+ tNUMBER tNUMBER)

(define s2 (lambda (e)
    (cond 
      ((number? e) e)
      ((not (list? e))          (error "s1: can not evaluate =>" e))
      ((not (= (length e) 3))   (error "s1: can not evaluate =>" e))
      ((not (number? (cadr e))) (error "s1: can not evaluate =>" e))
      ((not (number? (caddr e)))(error "s1: can not evaluate =>" e))

      ((eq? (car e) '+)         (+ (cadr e) (caddr e)))

      ( else (error "s1: can not evaluate =>" e))
    )
))

Results:

1 ]=> (s2 '(+ 1 2)) 

;Value: 3

1 ]=>

Stage 3 - N

Now we will have nested expressions in this example. So we need to modify our grammer for that.

(+ (+ 2 -3) (+ 1 2))

Grammer : So now we can go into deeper.

<s3> -> tNUMBER 
      | (+ <s3> <s3>)

Now we will delete our check mechnasim because our first check will handle these errors.

(define s3 (lambda (e)
    (cond 
      ((number? e) e)
      ((not (list? e))          (error "s1: can not evaluate =>" e))
      ((not (= (length e) 3))   (error "s1: can not evaluate =>" e))
      ((eq? (car e) '+)         (+ (s3 (cadr e)) (s3 (caddr e))))
      ( else (error "s1: can not evaluate =>" e))
    )
))

Output:

1 ]=> (s3 '(+ (+ 1 2) (+ 1 1))) 

;Value: 5

Stage 4

Why we can't add much more list to our addition procedure. Now also we need to modify our grammer and introduce new non-terminal.

Grammer :

<s4> -> tNUM
      | (+ <s4_list>)

<s4_list> -> tNUM <s4_list>
      |

Let's implement our interpreter for this subset. First of all we need to delete our length check. After that we need to modify addition section. So we need to use some important functions like map and apply .

(define s4 (lambda (e)
    (cond 
      ((number? e) e)
      ((not (list? e))          (error "s1: can not evaluate =>" e))
      ((null? e)                (error "s1: can not evaluate =>" e))
      ((eq? (car e) '+)         (apply + (map s4 (cdr e))))
      ( else (error "s1: can not evaluate =>" e))
    )
))

1 ]=> (s4 '(+ 1 2 3))

;Value: 6

Stage 5 (Adding New Operators)

Now our aim is to add new operators to our interpreter.

Grammer :

<s5> -> tNUM
      | (+ <s5_expressions>)
      | (- <s5_expressions>)
      | (* <s5_expressions>)
      | (/ <s5_expressions>)

We can modify our interpreter just adding few more.

(define s4 (lambda (e)
    (cond 
      ((number? e) e)
      ((not (list? e))          (error "s1: can not evaluate =>" e))
      ((null? e)                (error "s1: can not evaluate =>" e))
      ((eq? (car e) '+)         (apply + (map s4 (cdr e))))
      ((eq? (car e) '-)         (apply - (map s4 (cdr e))))
      ((eq? (car e) '*)         (apply * (map s4 (cdr e))))
      ((eq? (car e) '/)         (apply / (map s4 (cdr e))))
      ( else (error "s1: can not evaluate =>" e))    
    )
))

also we can extend our code by adding a get-operator function.

(define get-operator 
  (lambda (operator)
    (cond
      ( (eq? operator '+) +)
      ( (eq? operator '-) -) 
      ( (eq? operator '*) *)
      ( (eq? operator '/) /)
      ( else (error "unknow operator ==>" op))
    )  
  )
)

Now we can beautify our interpreter code like that:

(define s5 (lambda (e)
    (cond 
      ((number? e) e)
      ((not (list? e))          (error "s1: can not evaluate =>" e))
      ((null? e)                (error "s1: can not evaluate =>" e))
      ( else 
          (let 
            (
              (operator (get-operator (car e)))
              (operands (map s5 (cdr e)))
            )
            (apply operator operands)
          )
      )
    )
)))

Stage 6 (Improving Experience)

Currently we're using MIT interpreter but why we don't have our own promt. We want to have:

R ead
E vaulate
P rint
L oop

We need to know some other procudures to achieve this. Thanks to MIT scheme we have a built-in procedure for reading from user which is read . Easy huh? Also we need to have loops. But as we know in scheme we don't have loops. So we can use recursions for that!

(define repl (lambda ()
  (let * (
      (console (display "inntt >"))
      (expr (read))
      (val (s5 expr))
      (console2 (display "inntt :"))
      (console3 (display val))
      (console4 (newline))
    )
    (repl)
  )
))

Now we have a new prompt!

1 ]=> (repl)
inntt > 
inntt > (+ 1 2)
inntt : 3

Let's add variables to our interpreter. So first re-design our grammer.

<s6> -> <s6_expr>
      |  <define>

<define> -> (define tIDENT <s6_expr>)

<s6_expr> -> tNUM
          | tIDENT
          | ( + <s6_expr> <s6_expr> <s6_exps> )
          | ( * <s6_expr> <s6_expr> <s6_exps> )
          | ( / <s6_expr> <s6_expr> <s6_exps> )
          | ( - <s6_expr> <s6_expr> <s6_exps> )

<s6_exprs> -> <s6_expr> <s6_exprs>
          |

There is an important concept of how we can bind variables. To achieve this we need to store each variable. We need to create environment for key and values for variables. Can we use cons cell to achieve this ?? Why not, hence we have cdr and cdr we can easily manage this.

         +--+--+   +--+--+
env.---->|* |  +--->  | /|
         ++-+--+   +--+--+
          |
         ++-+--+
         |x |1 |
         +--+--+

So to get variable let's write our procedure.

(define get-value (lambda (var env)
  (cond
    ((null? env) (error "undefined variable"))
    ((eq? (caar env) var) (cadr env))
    ( else (get-value var (cdr env)))
  )
))

This was the end of the blog post. You can reach me via email umusasadik at gmail com