Coding Challenge #30 - Lisp Interpreter

This challenge is to build your own Lisp interpreter.

Lisp is a general-purpose, multi-paradigm programming language suited for a wide variety of industry applications. It is probably most widely know for being the programming language built into Emacs. As well as that it was used to build Hacker News (Paul Graham is a Lisp fan), Grammarly, Circle CI (actually using the modern dialect Clojure) and Boeing.

Intermission!

Two quick announcements:

1. The Coding Challenges GitHub repository for Shared Solutions to previous challenges is now taking part in HacktoberFest.
2. Coding Challenges Live - Become a Better Software Developer by Building Your Own Redis Server?is returning in November. Sign up to the waitlist if you’d like to be notified when admission opens.

The Challenge - Building Your Own Lisp Interpreter

In this Coding Challenge you are going to build your own simple Lisp interpreter. Like all the challenges, you can tackle it in any programming language you like. Bonus points if you go all Inception on it and build the interpreter in a modern version of Lisp, like Clojure or Racket!

If you want to learn a little Lisp (which is a fun thing to do), I pulled together some tutorial material in a LinkedIn post: 10 ways to learn Lisp. In the meantime here’s a very brief introduction.

There are two fundamental elements to Lisp syntax, atoms and s-expressions. 1, :cc and t are all atoms, where as (+ 1 2) and (defun hello () "Hello Coding Challenges") are s-expressions. In these examples 1 and 2 are integers, :cc is a symbol and t is an atom denoting true.

An s-expression is either an atom or an expression, for example (a b c). Where a, b, and c can all then be either atoms or s-expressions. Mathematical operations are in prefix notation.

Step Zero

Coding Challenges like the majority of common programming languages arrays is zero based, we start with Step 0! For this step please setup your IDE / editor of choice and programming language of choice.

Step 1

In this step your goal is to tokenise the expressions in a string. My personal approach to this would be to use?test-driven development?(TDD) to build tests for some example Lisp, i.e.:

• 1 this will give you the atom with a value of 1.
• "Hello, Coding Challenges” This is a string atom.
• :CC this should be an atom (which will evaluate to the symbol :CC).
• (format t "Hello, Coding Challenge World World") this is an s-expression which should tokenise as a list comprising of a symbol followed by a list.
• (defun hello () "Hello, Coding Challenge World").

Be sure to add your own test cases too.

Continued...

You can find Step 2 and beyond on the?Coding Challenges?website as Build Your Own Lisp Interpreter.

Or if you'd rather get the whole challenge delivered to you inbox every week, you can subscribe on the?Coding Challenges Substack.