Building Lispy: A Step‑by‑Step Guide to Crafting a Lisp Interpreter in C

Previous Articles

C Language Quick Start (0) C Family History

C Language Quick Start (1) HelloWorld

C Language Quick Start (2) Basic Data Types

C Language Quick Start (3) Pointer Types

C Language Quick Start (4) Arrays and Strings

C Language Quick Start (5) Structures and Bitfields

C Language Quick Start (6) Enums and Unions

C Language Quick Start (7) Variables, Constants and Scope

C Language Quick Start (8) Operators and Control Flow

C Language Quick Start (9) Functions and Macros

Using C to Write a Programming Language (0) Compilation Basics

Lispy

Lispy is the parsing‑style programming language we develop in this series, inspired by the book “Build Your Own Lisp”.

Full source code: https://github.com/JmilkFan/Lispy

The practice has two goals: applying C programming and understanding the design and implementation of a programming language.

Basic Function Demonstration

Numeric Operations

lispy> + 4 5  // 4+5
9
lispy> - 8 3  // 8-3
5
lispy> * 6 2  // 6 * 2
12
lispy> / 10 5  // 10/5
2
lispy> / 10 0  // 10/0
Division By Zero!
lispy> - (* 10 10) (+ 1 1 1)  // (10*10) - (1+1+1)
97

Variables and Algebraic Operations

lispy> def {x} 1
()
lispy> + x 1
2
lispy> def {y} 2
()
lispy> + x y
3
lispy> def {a b} 2 3
()
lispy> + a b
5
lispy> + x (* a b) y  // x + (a * b) + y
9
lispy> def {arglist} {a b c d}
()
lispy> def arglist 1 2 3 4
()
lispy> list a b c d
{1 2 3 4}

List Processing

lispy> def { l1 } {1 2 3}
()
lispy> def { l2 } {4 5 6}
()
lispy> head l1
{1}
lispy> tail l1
{2 3}
lispy> join l1 l2
{1 2 3 4 5 6}
lispy> list l1 l1
{{1 2 3} {1 2 3}}
lispy> eval {+ 1 2 3}
6

Lambda Functions

lispy>  def {add-mul} (\ {x y} {+ x (* x y)})
()
lispy> add-mul 10 20
210
lispy> add-mul 30 40
1230
lispy> def {add-mul-ten} (add-mul 10)
()
lispy> add-mul-ten 50
510

Conditional Branch Control

lispy> def {x y} 100 200
()
lispy> if (== x y) {+ x y} {- x y}
-100
lispy> if (< x y) {+ x y} {- x y}
300

String Handling

lispy> print "Hello World!"
"Hello World!"
()
lispy> error "This is an error!"
This is an error!

Source File Loading

$ cat hello.lspy
(print "hello world.")

$ main hello.lspy
"hello world."

Function Library Demonstration

List Processing Library (list.lspylib)

; empty type
(def {nil} {})

; boolean type
(def {true} 1)
(def {false} 0)

; Lambda function definition
(def {fun} (\ {f b} {
  def (head f) (\ (tail f) b)
}))

; first, second, third element helpers
(fun {fst l} { eval (head l) })
(fun {snd l} { eval (head (tail l)) })
(fun {trd l} { eval (head (tail (tail l))) })

; length of a list
(fun {len l} {
  if (== l nil)
    {0}
    {+ 1 (len (tail l))}
})

; nth element
(fun {nth n l} {
  if (== n 0)
    {fst l}
    {nth (- n 1) (tail l)}
})

; last element
(fun {last l} {nth (- (len l) 1) l})

; take first n elements
(fun {take n l} {
  if (== n 0)
    {nil}
    {join (head l) (take (- n 1) (tail l))}
})

; drop first n elements
(fun {drop n l} {
  if (== n 0)
    {l}
    {drop (- n 1) (tail l)}
})

; split list at n
(fun {split n l} {list (take n l) (drop n l)})

; element membership test
(fun {elem x l} {
  if (== l nil)
    {false}
    {if (== x (fst l)) {true} {elem x (tail l)}}
})

; map function over list
(fun {map f l} {
  if (== l nil)
    {nil}
    {join (list (f (fst l))) (map f (tail l))}
})

; filter function
(fun {filter f l} {
  if (== l nil)
    {nil}
    {join (if (f (fst l)) (head l) {nil}) (filter f (tail l))}
})

; fold left
(fun {foldl f z l} {
  if (== l nil)
    {z}
    {foldl f (f z (fst l)) (tail l)}
})

; sum of list
(fun {sum l} {foldl + 0 l})
; product of list
(fun {product l} {foldl * 1 l})

Application: list processing.

lispy> load "./samples/list.lspylib"
()
lispy> def {l1} {1 2 3 4 5 6}
()
lispy> len l1
6
lispy> nth 2 l1
3
lispy> last l1
6
lispy> take 3 l1
{1 2 3}
lispy> def {l2} (drop 4 l1)
()
lispy> l2
{5 6}
lispy> split 5 l1
{{1 2 3 4 5} {6}}
lispy> elem 1 l1
1
lispy> elem 7 l1
0
lispy> map (\ {x} {+ x 10}) {5 2 11}
{15 12 21}
lispy> filter (\ {x} {> x 2}) {5 2 11 -7 8 1}
{5 11 8}
lispy> sum l1
21
lispy> product l1
720

Conditional Branch Library (condition.lspylib)

; empty type
(def {nil} {})

; boolean type
(def {true} 1)
(def {false} 0)

; Lambda function definition
(def {fun} (\ {f b} {
  def (head f) (\ (tail f) b)
}))

; first, second, third helpers (same as list library)
(fun {fst l} { eval (head l) })
(fun {snd l} { eval (head (tail l)) })
(fun {trd l} { eval (head (tail (tail l))) })

; unpack list for function call
(fun {unpack f l} { eval (join (list f) l) })

; pack list for function call
(fun {pack f & xs} { f xs })

; switch keyword
(fun {switch & cs} {
  if (== cs nil)
    {error "No Selection Found"}
    {if (== (fst (fst cs)) true) {snd (fst cs)} {unpack switch (tail cs)}}
})

; default keyword
(def {default} true)

; case keyword
(fun {case x & cs} {
  if (== cs nil)
    {error "No Case Found"}
    {if (== x (fst (fst cs))) {snd (fst cs)} {unpack case (join (list x) (tail cs))}}
})

; month‑day suffix selector
(fun {month-day-suffix i} {
  switch
    {(== i 0) "st"}
    {(== i 1) "nd"}
    {(== i 3) "rd"}
    {default "th"}
})

; day‑name selector
(fun {day-name x} {
  case x
    {0 "Monday"}
    {1 "Tuesday"}
    {2 "Wednesday"}
    {3 "Thursday"}
    {4 "Friday"}
    {5 "Saturday"}
    {6 "Sunday"}
})

lispy> load "./samples/condition.lspylib"
()
lispy> month-day-suffix 1
"nd"
lispy> month-day-suffix 2
"th"
lispy> day-name 0
"Monday"
lispy> day-name 1
"Tuesday"

Mathematics Library (fibonacci.lspylib)

; empty type
(def {nil} {})

; boolean type
(def {true} 1)
(def {false} 0)

; Lambda function definition (same as above)
(def {fun} (\ {f b} {
  def (head f) (\ (tail f) b)
}))

; Fibonacci implementation
(fun {fib n} {
  switch
    {(== n 0) 0}
    {(== n 1) 1}
    {default (+ (fib (- n 1)) (fib (- n 2)))}
})

lispy> load "./samples/fibonacci.lspylib"
()
lispy> fib 10
55
lispy> fib 20
6765