(A ((Pretty OK) Lisp) Interpreter {in SETL})

This post overviews a Common Lisp interpreter written in the Set Theoretic programming language SETL. Source code is here: https://bitbucket.org/NeuralOutlet/setlisp
A complete list of available functions can be found in the doc folder.

Originally developed in  the 1960s by Jack Schwartz, SETL (Set Language) is peculiar in that it feels old and new at the same time. You’re writing imperatively with these chunky procedures then suddenly doing aggressive set comprehension like generating a set of unique primorial numbers in one terse but coherent line:

-- This is a comment
pset := {*/{p in {2..n} | forall m in {2..p - 1} | p mod m > 0} : n in {0..20}};
print(pset); --prints: {2 6 30 210 2310 30030 510510 9699690}

David Bacon developed the GNU SETL version between 1989-2009, fantastically nice to use, it is extended somewhat by adding POSIX support. Though it should be noted the parts that feel new were in SETL from its inception, it is said to be the first language to include list comprehension.

SETL spawned many versions of itself (SETLB, SETL2, ISETL, SetlX, etc) and influenced two other Set Theoretical languages called ProSet and Slim. Though out of all these languages the only ones still kicking around are GNU SETL, ISETL, and SetlX. There was a non-Set Theoretic language influenced by SETL – ABC (the predecessor to Python).

A good taste of the language can be found in the GNU SETL Om, for a more in depth understanding there is David Bacon’s PhD thesis. A ton of useful and interesting example programs can be found at Håkan Kjellerstrand’s SETL page. Historically there is also an early paper by Jack Schwartz.

So far setlisp has about 60 functions (SETLisp documentation) and the datatypes: Boolean, Number, String, Symbol, Function, List, and Set.

Sets – Lisp has a function for making lists, it looks like (list 5 4 3 3) which produces the list (5 4 3 3). Pretty simple, the function ‘set’ already exists for setting the value of a symbol so I chose to use ‘setl’ as the set function (setl 5 4 3 3) which yields {3 4 5}. The curly brackets indicate it is a set not a list. In Set Theory the order or duplicity of elements in a set do not matter so SETL orders the elements of a set by value and removes duplicates.

Expressions – The use of sets is extended to set-expressions, these are more of a playful idea than anything useful. The arguments are automatically bagged up into a set instead of being mapped to variable names in a list. Here you can see addition used as an s-expression and a set-expression:


The add function specifically is just the ‘+’ operator cast over a set or list of elements, which means that unlike ‘+’ in Lisp this one will do numeric affirmation aswell as addition. It infact extends further to also perform set union and string or tuple concatenation. I added the functions ‘append’ and ‘concatenate’ but they just call ‘+’. The code itself uses the ‘/’ notation alongside the list comprehension:

-- (+ args...)
proc scl_add(sargs, env);
	return [+/sargs, env];
end proc;

-- {+ args...}
proc setl_add(sargs, env);
	return [+/sargs, env];
end proc;

There is a ‘mapchoice’ function which is a play on the ‘mapcar’ function in Lisp and the Choice Function in Set Theory. The function ‘cardinality’ does the same as ‘length’. Also any s-expressions I add with only one or zero arguments is done for both s/set-expressions. {quit} is the same as (quit) for example.

This does open up overloading, a function can be defined as s-exp or set-exp or both (requires two identical definitions). The defun function works slightly different for each, s-exp are defined just as they should be, but the set-exp hides all parameters in a named set. This needs to be accessed with set functions such as from or with looping:

;; S-Expression
(defun my-func (param1 param2 param3)
    (print param1)
    (print param2)
    (print param3))
(my-func 14 80 32) ; prints 14 80 32

;; SET-Expression
{defun my-func params
    (print (from params))  ;Note: 'from' is destructive to the set, but
    (print (from params))  ;      (loop for val in params do...) is not
    (print (from params))}
{my-func 14 80 32}         ; prints 14 32 80

Behind the Scenes – SETL has another useful type (although it is more of a mechanism) called maps. Obviously straight from Set Theory – maps, sets, and tuple are the core of the language. A map is defined as a set containing only 2-tuples. Below is a map called stuff that has ‘this’ mapped to 5 and ‘that’ mapped to a tuple of the numbers 1 to 100:

stuff := {['this', 5], ['that', [1..100]]};
print( stuff('this') );
print( stuff('that') );

In SETLisp the variables environment is constructed with maps and so is the function type. To create local scope a list of maps is treated as a stack – checking from the top down searching for a value to map to a variable, then popping that definition map off the stack when leaving scope. The addition of an implicit map type in setlisp was my favourite feature to add, check out the Fun with Maps example.

Lisp Reader/Printer – The largest leaps in clarity for me came from trying to emulate the print and read functionality of lisp. The Lisp Printer is alluded to in the HyperSpec but it’s not a function available to the user, it just takes an object and makes it string-ready. It has a comrade in the ‘read’ function.  Initially for my parser I was reading a line of code in and tokenising that and then I extended it to get more lines if the bracket count was uneven .i.e., more ‘(‘ than ‘)’. I stayed with this for most of the development then when I had enough basic functions I wanted to add macros. For a very long time I tried to add read macros at the already tokenised stage, it was horrible. After a hiatus I wrote a macro-safe read-line, with this I was able to write the ‘set-macro-character‘ functionality and it all became clear. I needed to write a ‘read’ function and then use that to read lisp objects in instead of parsing lines one character at a time. SETLisp has the following print and read functions:

Printing functions: write, print, princ, prin1, format.

Read functions: load, read, read-line, read-char, read-setl.

Obviously the last one is setlisp specific, it is a wrapper for evaluating a SETL variable or variable construcor. In the setlisp.rc file you can see it is, in conjuction with ‘eval-setl’, used to allow SETL list/set comprehension in the macros ${ … } and $( … ).

Nil vs Om – These are two very similar concepts that appear in a lot of programming situations. In SETL any function without a return value will return om (printed as an asterisk ‘*’), this is the same for nil in Lisp. Lists in Lisp are constructed by cons cells ending with a nil cdr (a . (b . (c . nil))), in SETL a tuple is hypothetically of infinite size with om in every leading index [a b c * * … *]. One problem this brings up is that (list nil nil nil) should evaluate to (NIL NIL NIL) but [om, om, om] creates an empty tuple instead of [* * *]. The boolean types in Common Lisp are ‘t’ and ‘nil’ although anything not nil is considered true – SETL has the standard true/false duality but then om is there being all interesting.

Types – SETL doesn’t have characters, it’s very weird to me but a character is the same as a string of length 1. But what are strings made of? Aren’t they ordered sets of characters? I don’t know why there isn’t a byte-friendly char type in SETL but they exist in Common Lisp so I added a type system for various things. There are types for: Function, List, Set, Character, Complex, and Symbol. The syntax for characters are setup in the runtime configuration file, but I never implemented complex numbers in the form #C(1 2).

Macros – I didn’t add the more powerful ‘defmacro’ to SETLisp but for some of the beloved Lisp syntax such as ‘quote and #’function I added ‘set-macro-character‘ and ‘set-dispatch-macro-character‘. The extra syntax is implemented in the setlisp.rc file (read in before anything else). It begins with adding single line comments:

"Strings are nice, but let's make comments!"
(defun comment-macro (s c)
	(read-line s)
(set-macro-character ";" (function comment-macro))
(format t "  Comment macro added.~%")

and builds up to this definition for multi-line comments:

; Multi-line comments
(defun multi-line-macro (s c n)
	(if (equal "|" (read-char s))
		(if (equal "#" (peek-char s))
				(read-char s)
			(multi-line-macro s c n))
		(multi-line-macro s c n)))
(set-dispatch-macro-character #\# #\| #'multi-line-macro)
(format t "  Multi-line Comments added.~%")

MuSh: Multi-Shebang Scripting

MuSh is a super simple meta-scripting language for parsing multiple shebang statements that invoke different interpretors. Why would you want to do this? I have no idea. Although there is no real reason to do this you might want to just for the fun of it.

How it works
MuSh is python based and has a linear approach, it splits up the script into smaller single-language scripts then runs them one after the other. Variables are transported between scripts using a register file (msb_register.json) and hook-in functions which add code to the scripts for interacting with the register. There are two important syntaxes (syntaces?) for separating languages, the first is:

#!! <interpretor> <passed-variables …>

A very simple Guess my Number game that uses Bash, Python and Common Lisp.

A little Guess my Number game that uses Shell, Python and Common Lisp. This example can be found at ‘examples/guess_my_num.msb‘ and uses the Vim syntax file found in the repo at editor_support/mush.vim.

The second separation syntax is for embedded use, it has open and close functionality:

#![ <interpretor> <passed-variables …>
#!] <passed-variables …>

MuSh uses the hook-in function inline_replace which replaces the embedded code with a call to a subscript (of that code). In the example below you can see how a python program might use subscripting to use Lisp. The left is the original, the right is after inline_replace has been called:

def fact_lisp(n):
        #![ clisp n
        (defun fact (n)
                (if (< n 2) 1
                (* n (fact(- n 1)))))
        (setf out (fact n))
        #!] out
        return out
def fact_lisp(n):
	# Get 'n' from register ...
	from subprocess import call
	call("./subscript_0", shell=True)
	# Get 'out' from register ...
	return out

The above code is from ‘examples/fact_speed_IO.msb from the repo. The meta-script starts with a python program that defines three factorial functions using subscripts to Python, Common Lisp, and Shell (sh). These three are called inside a python forloop 1000 times – calculating 10! each loop. Python timing methods are used giving:

 Subscripts Python Common Lisp Shell
Time (seconds) 25.4605309963 18.8304021358 21.1056499481

It also defines a pure python factorial function, which it also loops for. Next the meta-script moves to a Lisp program which has a Lisp forloop and factorial function, timing here is done with (get-internal-real-time) and (internal-time-units-per-second). Finally the meta-script moves to Shell and runs a while loop for its factorial function. These script results seem peculiar to me, Lisp shows to be slower than Python and Shell is almost as bad as subscripting:

 Scripts Python Common Lisp Shell
Time (seconds) 0.002014 0.009645 14

I find it strange that when using a python loop/timing – python was the slowest, but when using native loops/timing – python was the fastest. This could be because my implementation is incorrect somewhere or python just has great looping but bad recursive arithmetic. Maybe it’s a reflection of how python interacts with the register. I’m more confused by why shell is so slow.