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/mitscheme/)
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
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 ]=>
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
Why we can't add much more list to our addition procedure. Now also we need to modify our grammer and introduce new nonterminal.
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
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
getoperator
function.
(define getoperator
(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 (getoperator (car e)))
(operands (map s5 (cdr e)))
)
(apply operator operands)
)
)
)
)))
Currently we're using MIT interpreter but why we don't have our own promt. We want to have:
We need to know some other procudures to achieve this. Thanks to MIT scheme we have a builtin 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 redesign 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 getvalue (lambda (var env)
(cond
((null? env) (error "undefined variable"))
((eq? (caar env) var) (cadr env))
( else (getvalue var (cdr env)))
)
))