Programming for me is a passion, sort of art, thus; this is just for fun and learning new stuff. And what could be more wonderful than writing your own lisp interpreter. For the purpose learning more, Lisp and Scheme are the same for the moment, so the code written in here is a mix between the two languages. There might be an undefined number of bugs in here, I’m aware of some and some remain unknown.
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 and done as follows:
$ make # compile the code
$ make clean # removes the objects and the executable
$ make build # same as make clean && makeThe intepreter’s standard library function are stored in stdlib.scm, the other files are just for testings
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 contain 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 expressions
;;; Comments start with ';'.
;;; anything form 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 a list using cons
(cons 'a (cons 'b (cons 'c nil))) ; (a b c)
;; Defining symbols and lambdas
(define foo (+ 1 (* 2 5))) ; 11
(define bar '(+ 1 4)) ; (+ 1 4)
(define baz (eval bar)) ; 5
(define list-one (cons
'a (cons
'b (cons
'c nil)))) ; (a b c)
(define list-two (list a b c)) ; (a b c)
(define list-three '(a b c)) ; (a b c)
;; Applying car/cdr operations
(car list-one) ; a
(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 usign 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)
;; more examples
(let ((tmp '(1 2)))
(map square (append '(1 2 3) tmp))) ; 1 4 9 1 4
(let ((foo '+))
(let ((+ *))
(eval (list foo 2 3)))) ; 6
;; for more library functions check stdlib.scmTo 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
The process of lexing is where the input, i.e. source code, is splited into a Vector of tokens. Each token have 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.=.
The process 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.
The process 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 on those arguments. a typical s-expression would look like this:
(operator s-exprs...)
;; 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.
This is a basic Lisp (technically Scheme) interpreter that was written in C for educational purposes with the following features:
- [X] Lexing Phase
- [X]
read and split text containing Scheme/Lisp syntax into tokens - [X]
extract values like strings and numerical literals
- [X]
- [-] Parsing Phase
- [X]
parse the tokens into a s-expression object - [-]
replace some syntactic sugar while parsing- [X]
(quote expr) and ‘expr - [X]
(define (f args) (body)) - [-]
(defun f (args) (body))
- [X]
- [X]
- [X] Evaluation Phase
- [X]
evaluate the parsed s-expression object - [X]
support recursion
- [X]
- [-] Syntax support
- [X]
arithmetic operator - [X]
arithmetic comparison operators - [X]
cons-pairs operators- [X]
using undefined number of nested car/cdr operators
- [X]
- [X]
logical operators - [X]
defining symbols that hold values using- [X]
remove them using - [X]
modify their value
- [X]
- [X]
conditional expressions - [X]
support lambda expressions - [ ] (define-syntax …)
- [ ] (define-macro …)
- [X]
- [-] Memory and GC
- [X]
memory is handled via a garbage collector- [X]
optimizing teh evaluation by using an evaluation stack
- [X]
- [ ] support simple objects with properties
- [X]