Software and Computer Engineering

Design Document for a Lispy Language

Lisp is an exercise in simplicity. Let's design our own.


These are the tokens allowed:

Everything else matching /\s/ is whitespace, which is discarded by the tokenizer.


The grammar goes as follows:

program := [ expressions ]

expressions := expression [ expressions ]

expression := "(" atoms ")"

atoms := atom [ atoms ]

atom := scalar-literal | list-literal | expression

scalar-literal := unquoted-literal | double-quoted-literal | single-quoted-literal

list-literal := "'(" atoms ")"

Data Types

Value types -- Every value is either a scalar or a list. A scalar is always represented as a string, so there is no dedicated data type for numbers, characters or booleans. A list is a finite sequence of values, meaning that it can contain other lists.

Null value -- There is a special value for nil, intended for expressions that do not return a value.

Truthiness and falseness -- The only values considered to be false are: nil, the empty string "" and the empty list '(). All other values are true.

Equality -- The nil value is only equal to itself. A string is equal to another string iff they are both empty or they have the same contents (despite being unquoted, double-quoted or single-quoted). A list is equal to another list if they are both empty or have the same contents. The nil value, a string or a list are never equal to another.

Functions and Macros

Functions are defined as follows:

(defun function-name (arg1 arg2 [...] argn)

A function may be called from an expression:

(function-name expr1 expr2 expr3 [...] exprn)

On execution, this expression will be the result of evaluating the function-body by substituting the values of arg1 for the evaluation of the expr1 expression, arg2 for the evaluation of the expr2 expression, and so on.

Macro are similar, but each of the parameters are passed as-is, without being evaluated first. They may be evaluated within an macro by calling eval.

(defmacro my-if (condition if-true if-false)
	(if (eval condition)
		(eval if-true)
		(eval if-false)))

The macro above my-if would have an equivalent behavior to the built-in if. If that were defined as a function, it both if-true and if-false would each be evaluated before being passed into the if, despite the truth value of the condition.