Lisp interpreter and compiler based on Haskell

REPL

• stack exec ki -- -repl

1. Interpret

Arithmetic expression

• (<operator> <expression> <expression>)
• Calculation: + - * /
• Logic: and or not
• Compare: > < >= <= = (Numbers only)

>>> (+ 1 2)
3
>>> (and True False)
False
>>> (and (or True False) True)
True

Assignment statement

• (set! <variable> <expression>)

>>> (set! x 1)
>>> x
1.0

Array statement

• (make-vector <variable> <expression>)
• (vector-set! <variable> <expression> <expression>)
• (vector-ref <variable> <expression>)

>>> (make-vector x 6)
>>> x
[Undefined, Undefined, Undefined, Undefined, Undefined, Undefined]
>>> (vector-set! x (+ 1 2) (+ 2 3))
>>> x
[Undefined, Undefined, Undefined, 5.0, Undefined, Undefined]
>>> (vector-ref x 3)
5.0

If statement

• (if <expression> <statement>)
• Expression should be logical

>>> (set! x 1)
>>> (if (< x 5) (set! x (+ x 1)))
>>> x
2.0

While statement

• (while <expression> <statement>)
• Expression should be logical

>>> (set! x 1)
>>> (while (< x 5) (set! x (+ x 1)))
>>> x
5.0

Statement block

• (begin <statement> [<statement>..])

>>> (begin (set! x 1.2) (set! y 3.2) (set! z (+ x y)))
>>> x
1.2
>>> y
3.2
>>> z
4.4

Let expression

• (let <variable> <expression> <expression>)
• Equals to (let var = expr in expr)
• Can be nested

>>> (let x (+ 1 2) (+ x 5))
8.0
>>> (let x 1 (let y 2 (+ x y)))
3.0
>>> (let x (lambda y (+ y 1)) (x 2))
3.0

Function definition

• (define (<variable> [<variable>..]) <statement>)

>>> (define (foo x y) (return (+ x y)))
>>> (foo 1 2)
3.0
>>> (define (bar x) (if (= x 5) (return 5) (return (bar (+ x 1)))))
>>> (bar 1)
5.0

Higher-order function / lambda expression

• (lambda <variable> <expression>)
• Can be nested

>>> (set! x (lambda y (+ y 1)))
>>> x
["y"] Return (+ y 1.0) fromList []
>>> (x 1)
2.0
>>> (set! foo (lambda x (lambda y (+ x y))))
>>> foo
["x"] (return (lambda y (+ x y))) fromList []
>>> (foo 2)
["y"] (return (+ x y)) fromList [("x",DoubleValue 2.0)]
>>> ((foo 2) 3)
5.0

2. Pretty-printer

• Using :t to prettify the most recent valid input

Arithmetic expression

>>> (+ 1 2) 
3.0
>>> :t
(+ 1.0 2.0)
>>> (+ (- 1 2) 1)
0.0
>>> :t
(+ (- 1.0 2.0)
   1.0)

If expression

>>> (if (> 1 2) skip (set! x 2)) 
>>> :t
(if (> 1.0 2.0)
    skip
  (set! x
        2.0))

While expression

>>> (while (> 1 2) (set! y 1)) 
>>> :t
(while (> 1.0 2.0)
  (set! y 
        1.0))

Let expression

>>> (let y (+ 1 x) (+ x y)) 
5.0
>>> :t
(let y
  (+ 1.0 x)
  (+ x y))

Function definition

>>> (define (foo x) (return (+ 1 x))) 
>>> :t
(define foo (x)
  (return (+ 1.0 x))
>>> (foo 1)
2.0

Interpreter

• stack exec ki -- -t <inFile> -o <outFile>
• stack exec ki -- -t <inFile> -o <outFile>

# Output AST
stack exec kc -- -t /Users/.../in.txt -o /Users/.../out.txt
# Interpreting executate
stack exec kc -- -i /Users/.../in.txt -o /Users/.../out.txt

Compiler

• stack exec kc -- <inFile> -o <outFile>
• stack exec kc -- <outFile> -ir

# Compile to IR
stack exec kc -- /Users/.../in.txt -o /Users/.../out.txt 
# Executate IR
stack exec kc -- /Users/.../out.txt -ir

Example

• KMP algorithm

(define (kmp text pattern m n)
  (begin
    (set! i 0)
    (set! j (- 0 1))
    (set! a 0)
    (make-vector answer 100)
    (make-vector next 100)
    (vector-set! next 0 (- 0 1))
    (while (< i n)
      (begin
        (while (and (> j (- 0 1)) (not (= (vector-ref pattern i) (vector-ref pattern j))))
          (set! j (vector-ref next j))
        )
        (set! i (+ 1 i))
        (set! j (+ 1 j))
        (if (and (and (not (= i n)) (not (= j m))) (= (vector-ref pattern i) (vector-ref pattern j)))
          (vector-set! next i (vector-ref next j))
          (if (and (= i n) (= j m))
            (vector-set! next i (vector-ref next j))
            (vector-set! next i j)
          )
        )
      )
    )
    (set! i 0)
    (set! j 0)
    (while (< j m)
      (begin
        (while (and (> i (- 1 0)) (not (= (vector-ref text j) (vector-ref pattern i))))
          (set! i (vector-ref next i))
        )
        (set! i (+ 1 i))
        (set! j (+ 1 j))
        (if (>= i n)
          (begin
            (vector-set! answer a (- j i))
            (set! a (+ 1 a))
            (set! i (vector-ref next i))
          )
        )
      )
    )
    (return answer)
  )
)

(define (main)
  (begin
    (make-vector text 8)
    (make-vector pattern 2)
    (vector-set! text 0 'a')
    (vector-set! text 1 'n')
    (vector-set! text 2 'p')
    (vector-set! text 3 'a')
    (vector-set! text 4 'n')
    (vector-set! text 5 'm')
    (vector-set! text 6 'a')
    (vector-set! text 7 'n')
    (vector-set! pattern 0 'a')
    (vector-set! pattern 0 'n')
    (return (kmp text pattern 8 2))
  )
)