Basic Lisp/Scheme Intepreter

Minimalistic Scheme Interpreter

This is a basic interpreter that evaluates Lisp and Scheme-like syntax, written in C/C++ Programming Language, mainly for educational purposes.

The source code contains documentation, you can either read it in each file, reading the man pages or extract the documentation using Doxygen as HTML or LaTex. Compilation requires make:

$ make         # compile the code
$ make clean   # removes the objects and the executable
$ make build   # same as make clean && make

The interpreter is powered by a it’s own standard library written in Scheme, which is stdlib.scm , the other files are just for testings.

Lisp as a Programming Language

LISP is a really old functional programming language that stands for literally for LISt Processing because it is based on a data structure called List. It was invented by Mr. John McCarthy (a genius) and the first time lisp was mentioned was in a paper published in 1959 called Recursive Functions of Symbolic Expressions and Their Computation by Machine. Also, a nice paper published in 2002 by Mr. Paul Graham called Roots of Lisp contains some useful information based on what Lisp did while being around since the first appearance in the 1959’s paper as well as basic lisp functionalities and syntax.

Generally, Lisp is based on s-exps i.e. symbolic expressions. An expression is either an atom – sequence of characters, or a list of more s-expressions

;;; Comments start with ';'.
;;; anything from the ';' to '\n' is ignored
;;; This is an example of syntax supported by this interpreter

;; Basic Arithmetic
(* (+ 3 (/ 4 2)) (- 3 4))			; -5
(sqrt (square 2))		    		; 2

;; Build lists and pairs using cons
(define pair-one (cons 'a 'b))			; (a . b)

;; Defining symbols as s-expressions or lambdas
(define foo (+ 1 (* 2 5)))			; 11
(define bar '(+ 1 4))				; (+ 1 4)
(define baz (eval bar))	    			; 5

(define list-two (list a b c))			; (a b c)
(define list-three '(a b c))	    		; (a b c)
;; Applying car/cdr operations
(cdr list-two)					; (b c)
(cadr list-three)		    		; b

;; Recursion with factorial
(define fact
  (lambda (n)
    (if (<= n 1) 1
      (* n (fact (- n 1))))))
(fact baz)					; 120

;; Recursion with fibonacci
(define fib
  (lambda (n)
    (if (= n 0) 1
      (if (= n 1) 1
	(+ (fib (- n 2))
	  (fib (- n 1)))))))
(fib foo)					; 144

;; let operator
(let ((foo (list 1 2 3)))
  (cadr foo))		      			; 2

;; loop using labeled let
(let loop ((n 0))
  (if (> n 5)
    '()
    (cons n
      (loop (+ n 1)))))				; (0 1 2 3 4 5)

;; map operator
(map fib (let ((x '(1 2 3)))
	   (let ((y 9))
	     (append-to x y))))			 ; (1 2 3 55)

;; for more library functions check stdlib.scm

A Basic interpreter

To interpret a Lisp code, we have to pass through three fundamental phases, that goes from reading the source code and identify special tokens to assembling those tokens as a single s-expression. And finally evaluating that s-expression and print the result.

• Lexing: source code → vector of tokens
• Parsing: vector of tokens → parsed s-expression
• Evaluation: s-expression → result

Lexing

The phase of lexing is where we extract tokens from the input, i.e. source code. Each token has an associated value-buffer that holds additional information about the token, e.g. the content of a string.

NOTE: See lexer.{h,c} for additional information on possible token types and their meaning.

Parsing

The phase of parsing is where the tokens get converted into a s-expression. This is done by checking token, one after the other and based on the token type we create the correspondent s-expression until we reach the last token.

NOTE: See parser.{h,c} for additional information on the parsing process and related functions.

Evaluation

The phase of evaluating a s-expression is basically a recursive process. Starts by identifying the operator and pass the arguments so that we could apply the operator to those arguments. a typical s-expression would look like this:

(operator s-exprs...)
(define x y "ssss")
;;; comment
;; examples
(define expr '(* 7 8))
(eval expr)
((lambda (n) (* n n)) 5)
(lambda (a b) (+ a b))

while the s-exprs could range from a single atom to another s-expr with it’s own operator.

NOTE: See eval.{h,c} for additional information on the evaluation process and related function definitions.