Lisp interpreter implemented in 185 lines of Swift

Background

The original motivation for writing a Lisp interpreter in Swift originated in a blog article (in Japanese) I read written by @himara2, a programmer that I greatly respect, in which he claimed to have created a tiqav ^*1 viewer in Swift using only a hundred lines of code. Remembering that I once implemented Lisp in Ruby, which needed less than a hundred lines of code, I then wondered if it was also possible to write a Lisp interpreter in Swift in under one hundred lines of code.

What This Lisp Interpreter Can Do

(+ 0 (* 11 22) (- 333 30 3))
(first (1 2 3))
(let (a 2 b 3 c 4) (+ a b c))
(if (< 1 3) 2 3)
(map (list 1 2) (\ (x) (* 2 x)))
(defun calc (a b) (+ a b))
(calc 4 8)

• operate on integer values using arithmetic operators
• operate on lists using `first', `rest' and `list'
• bind values to local variables using `let'
• control flow using `if' and comparison operators
• create anonymous procedures using `\'
• apply procedure to values in a list using `map'
• define functions using `defun'

How to Use

1. download Xcode 6 beta from the Apple Developer Center
2. clone git repository of the Xcode project from GitHub github4484/sweme2 · GitHub
3. open the project by Xcode 6
4. run the App by pressing command-R
5. enter one lisp program and tap eval button
• Warning: there should not be multiple top level expressions

Sample Program

Here is code that lists the Fibonacci numbers.

(defun f (x) (if (= x 0) 1 (if (= x 1) 1 (+ (f (- x 1)) (f (- x 2))))))
(map (list 1 2 3 4 5 6 7 8 9 10) (\ (x) (f x)))

Implementation

To reduce the lines of codes, I fallowed these policies:

• simple and minimal functionality
• no error handling
• no performance consideration
• functional-programming-like coding style

Conclusion

knj4484$ wc -l Sweme2/{Evaluator,Expression}.swift
     153 Sweme2/Evaluator.swift
      32 Sweme2/Expression.swift
     185 total

It was impossible, at least for me at this time, to write a Lisp interpreter in Swift using less than a hundred lines of code.

Future Work

• implement macros/macro expantion, which is, I guess, the most important feature of Lisp
• implement operation of character strings and floating point numbers

References

• Structure and Interpretation of Computer Programs - 2nd Edition (MIT Electrical Engineering and Computer Science) , by Abelson, Sussman, and Sussman
• I learned how Lisp interpreter works from this book. If you want to know Lisp and functional programming more deeply, I highly recommend you to read this book.

*1 tiqav is one of the most popular image search services in Japan, which is run by some Yahoo!Japan engineers as their private project. Its aim is to provide you with images to use as responses in online chat.
c.f. see the photo at center bottom in http://hr.yahoo.co.jp/fresh/engineer/index.html

Japanese version of this page: ピュアSwiftコード100行でLispインタープリター作ろうとしたけど185行になったよ