XXIIVV — lisp

A common trait of all dialects of LISP is the S-expression.

In Lisp, a pair of parentheses indicates one step of calculation, operations use the prefix notation.

Programs in Lisp are made of symbols that are nested into trees using cons cells. A number is a signed integer represented by a sequence of decimal digits, optionally preceded by a sign.

45
+137
-27

A symbol is word represented by a sequence of characters, it cannot begin with a number or a sign, although these may appear later in a symbol.

Hello
Hello-world
x32

A cons cell is an allocation of memory made of two parts, a value(car) and a pointer(cdr), the cdr can point to another cell.

(123)
(hello 45)
(foo (bar baz))

A Lisp through the Looking Glass

Heol is a Lisp system for the Uxn virtual machine.

Heol is a 16-bit experimental Lisp inspired by TinyLisp and designed to be embedded inside of Uxn applications. It's currently under development.

Playground

Execution consists of reducing expressions, atoms return their value, lists are treated as function applications where the first element is a function name and the rest, arguments. Arguments are evaluated before being passed to the function.

Lists

The (cons value list) procedure constructs pairs, the (car list) procedure extracts the first elements of the list, and the (cdr list) procedure extracts the rest.

(cons 'a '(b c)) ; (a b c)
(car '(a b c)) ; a
(cdr '(a b c)) ; (b c)

Logic

The (eq? a b) procedure results in a flag either #t or () provided that the values of the expressions being compared are both atoms, and either they are both the same number, or they are both the same symbol:

(eq? 'a 'a) ; #t
(eq? 'a 'b) ; ()

Given three expressions, the (if flag when-true else) returns the value of the second if the value of the expression test is #t, otherwise returns the value of the third.

(if #t 
	123 
	456)

Arithmetic

Arithmetic operators follows the prefix notation:

(* (+ 3 5) 19) ; 152

Procedures

A (lambda args exp) expression evaluates to a procedure. The environment which is in effect when a lambda expression is evaluated is enclosed in the newly created procedure, this is referred to as a closure. Given an expression, the (quote exp) procedure returns that expression as a value.

((lambda (x) (* x x)) 3) ; 9

The (define name exp) expression binds an expression to a name, making it possible to utilize that reference throughout the code.

(define double
	(lambda (x) (+ x x)))

(double 5)  ; 10

Sequencing operations

Heol does not have an explicit way of sequencing reduction(progn, begin, etc..) instead it uses (and x1 x2 ... xk), which returns the non-nil value. One difference to be mindful of, is that and will not evaluate any argument after the first one that returns false. This can still be an efficient way, for example, of printing a value and returning another.

(and
	(print 'hello)
	42) ; Prints "Hello", but returns 42

Programs

If we put it all together now:

(define fac 
	(lambda (n)
		(if (< n 2)
			1 
			(* n (fac (- n 1))))))

(print (fac 5)) ; 120

Summary

(eval x) return evaluated x (such as when x was quoted)
(quote x) special form, returns x unevaluated "as is"
(cons x y) construct pair (x . y)
(car p) car of pair p
(cdr p) cdr of pair p
(if x y z) if x is non-() then y else z
(let* (v1 x1) (v2 x2) ... y) binds each variable vi to xi to evaluate y
(lambda v x) construct a closure
(define v x) define a named value globally
(+ n1 n2 ... nk) sum of n1 to nk
(- n1 n2 ... nk) n1 minus sum of n2 to nk
(* n1 n2 ... nk) product of n1 to nk
(/ n1 n2 ... nk) n1 divided by the product of n2 to nk
(< n1 n2) #t if n1<n2, otherwise ()
(eq? x y) #t if x equals y, otherwise ()
(pair? x) #t if x is a non-empty list, a cons cell or closure
(or x1 x2 ... xk) first x that is not (), otherwise ()
(and x1 x2 ... xk) last x if all x are not (), otherwise ()
(not x) #t if x is (), otherwise ()
(print x) print value of x, returns x

View Sources, Uxntal.
Repository, Uxntal

Lispkit is a Lisp system for the SECD virtual machine.

This page will document a portable, lexically scoped, purely functional subset of Lisp that compiles to the SECD virtual machine. I will use uppercase function names to indicate built-in functions, and lowercase for user-defined functions.

The self-hosted compiler source.
The virtual machine runtine.

The (ATOM exp) procedure return the symbol T if the value of the expression is an atom or F otherwise.

(ATOM (QUOTE 12)) ; T
(ATOM (CONS (QUOTE 12) (QUOTE 34))) ; F

Pairs

A pair joins two arbitrary values. The (CONS a d) procedure constructs pairs, the (CAR list) procedure extracts the first elements of the pair, and the (CDR list) procedure extracts the second.

(CONS (QUOTE foo) (QUOTE bar)) ; (foo.bar)
(CAR (CONS (QUOTE foo) (QUOTE bar))) ; foo
(CDR (CONS (QUOTE foo) (QUOTE bar))) ; bar

A list is a chain of pair that are cons-ed onto one another, ending with a nil.

(CONS (QUOTE a)
	(CONS (QUOTE b)
		(CONS (QUOTE c)
			(QUOTE NIL)))) ; (a b c.NIL)

Logic

The (EQ a b) procedure results in a value either T or F provided that the values of the expressions being compared are both atoms, and either they are both the same number, or they are both the same symbol:

(EQ (QUOTE (a)) (QUOTE (a))) ; F
(EQ (QUOTE 42) (QUOTE foo)) ; F
(EQ (QUOTE 42) (QUOTE 42)) ; T
(EQ (QUOTE foo) (QUOTE foo)) ; T

Given three expressions, the (IF test exp2 exp3) returns the value of the second if the value of the expression test is T, otherwise returns the value of the third.

(IF (EQ (QUOTE 16) X)
	(QUOTE EQUAL16)
	(QUOTE NOT-EQUAL16))

Arithmetic

Arithmetic operators follows the prefix notation:

(* (+ (QUOTE 3) (QUOTE 5)) (QUOTE 19)) ; 144

Procedures

A (LAMBDA args exp) expression evaluates to a procedure. The environment which is in effect when a lambda expression is evaluated is enclosed in the newly created procedure, this is referred to as a closure. Given an expression, the (QUOTE exp) procedure returns that expression as a value.

(LAMBDA (X) (ADD X (QUOTE 2))) ; the procedure itself
((LAMBDA (X) (ADD X (QUOTE 2))) (QUOTE 14)) ; 16

The (LET exp [pairs]), and (LETREC exp [pairs]), expressions can associate pairs of values to an expression, given an expression with declarations returns its value. The main difference between let and letrec is that letrec's definitions are also visible in the expression itself.

(LETREC name
	(name LAMBDA (X Y)
		(ADD value1 value2)
	)
	(value1 QUOTE 123)
	(value2 QUOTE 456)
	...
)

Programs

A program is either a LET, LETREC or LAMBDA expression. The program is given an expression from the outside world, that we will call INPUT to make explicit that this is our program entry procedure.

From here forward, I will use the λ shorthand for LAMBDA, which is part of the extended Lispkit compiler.

The (WRITE exp) procedure sends an expression to be dispatched to a device, by default, it is printing the expression in the console. If the symbol "Machiavelli" is used as argument, the program will evaluate to the following output:

(λ (INPUT)
	(WRITE (CONS (QUOTE Hello) INPUT))
) ; "(Hello.Machiavelli)"

Prefixing the WRITE expression with the :cli symbol routes the expression to the Command Line Interface, which handles printing text. The #\Newline sybol gets converted to a linebreak during printing.

(LETREC main
	(main λ (INPUT)
		(print-line (fib INPUT))
	)
	(fib λ (N)
		(IF (EQ N (QUOTE 0)) (QUOTE 0)
		(IF (EQ N (QUOTE 1)) (QUOTE 1)
			(ADD
				(fib (SUB N (QUOTE 1)))
				(fib (SUB N (QUOTE 2))))))
	)
	(print-line λ (text)
		(WRITE
			(CONS (QUOTE :cli)
			(CONS text
			(CONS (QUOTE #\Newline)
			(QUOTE NIL))))
		)
	)
)

Summary

(LAMBDA args exp) Result exp with args bindings.
(LET exp [pairs]) Result of exp with pairs bindings.
(LETREC exp [pairs]) Result of exp with rec. with pairs bindings.
(IF test exp2 exp3) Result of exp2 if test is T, else exp3.
(ATOM exp) Returns T when exp is atom, else F.
(QUOTE exp) Returns the exp as a value.
(CAR exp) Returns a pair's first value.
(CDR exp) Returns a pair's second value.
(CONS exp1 exp2) Returns a pair of exp1 consed on exp2.
(EQ atom atom) Returns T if two expressions are equal.
(ADD num num) Returns the sum of two numeric values.
(SUB num num) Returns the difference of two numeric values.
(MUL num num) Returns the product of two numeric values.
(DIV num num) Returns the quotient of two numeric values.
(REM num num) Returns the remainder of two numeric values.
(LEQ num num) Returns T if the first is less or equal to the second.
(WRITE exp) Sends expression to a device, returns expression.
(IMPLODE exp) Returns a symbol from a symbol.
(EXPLODE exp) Returns a list from a symbol.

Lispkit, SECD virtual machine in ANSI C.

Ronin is a graphical Lisp playground.

Ronin is a procedural graphics tool designed to automate simple graphical tasks, like resizing, cropping, coloring, and generating algorithmic images. It interprets a minimal dialect of Lisp, look at these examples to better understand how this all works.

The library updates is constantly revealing new applications to Ronin, you can see the list of available functions here.

Learn more by reading the manual, or have a look at some experiments on twitter. If you need help, visit the Community or watch the video tutorial.

incoming: functional heol lispkit lispkit library church encoding ronin bagel s-expressions secd 2023