(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.

SETL
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.

SETLisp
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:

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)
	(values))
(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))
			(progn
				(read-char s)
				(values))
			(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.~%")

The RGB Universe

Three images bounded to the respective spaces: Colour, Chromaticity, and Hue.

One image bounded to three respective spaces: Colour, Chromaticity, and Hue.

The Colour-Space: RGB
Everyone is familiar with this, it is the additive model for colours that uses the primaries: red, green & blue. A 3D Model where each unique colour sits at position (x: r, y: g, z: b).

The Chromaticity-Space: RCGCBC
Some people will be familiar with this, it is RGB without luminance, the brightness is removed in a way that doesn’t effect the hue or saturation. It is referred to as rg-Chromaticity because it’s construction from RGB means only two elements are needed to represent all the chromaticity values:

Conversion to Conversion from (kind of*)
R_C= \frac{R}{R+G+B}
G_C= \frac{G}{R+G+B}
B_C= \frac{B}{R+G+B}
 R = \frac{R_C G}{G_C}
G = G
B = \frac{(1 - R_C - G_C) G}{G_C}

It will always be that R_C + G_C + B_C = 1 so by discarding the blue component we can have unique chromaticities as (x: r’, y: g’). This means that rg-Chromaticity is a 2D-Model and when converting to it from RGB we lose the luminance. So it is impossible to convert back. *An in-between for this is the colour-space rgG where the G component preserves luminance in the image.

The Hue-Space: RHGHBH
No one uses this, I just thought it would be fun to apply the same as above and extract the saturation from RCGCBC. Like RCGCBC it is a 2D Model, this seems strange because it is only representing one attribute –hue– but it is because the elements themselves have a ternary relationship (how much red, how much green, how much blue) and so to extrapolate one you must know the other two.

Conversion to 3-tuple Hue Normalise to 2D
M = \text{Max}(R,G,B)
m = \text{Min}(R,G,B)
\delta = 255/(M-m)
R_h = (R-m) \delta
G_h = (G-m) \delta
B_h = (B-m) \delta
R_H = \frac{R_h}{R_h + G_h + B_h}
G_H = \frac{G_h}{R_h + G_h + B_h}
B_H = \frac{B_h}{R_h + G_h + B_h}

Measuring Hue Distance
The HSL colour-space records hue as a single element, H, making measuring distance as easy as \Delta H = \sqrt{{H_a}^2 - {H_b}^2} where as in rg-Hue we have two elements so \Delta H = \sqrt{({R''_a}^2 - {R''_b}^2) + ({G''_a}^2 - {G''_b}^2)} where R'' = R_H and G'' = G_H for readability. What’s interesting here is it works almost the same. Though it should be noted that on a line only two distances are equidistant to zero at one time where as in rg-Hue, on a 2D plane, there are many equidistant points around circles.

Below are images of a RGB testcard where each pixel’s hue has been measured against a colour palette (60° Rainbow) and coloured with the closest match. The rg-Hue measure has a notable consistency to it and shows more red on the right hand side than HSL, but also between the yellow and red there is a tiny slither of purple. I believe this is from the equal distance hues and the nature of looking through a list for the lowest value when there are multiple lowest values:

Hue Distance (HSL) Hue Distance (RHGHBH)
HSL Measure rg-Hue Measure

Accuracy of Generated Fractals

Note: I refer to the Mandelbrot set in general as the M-set for short.

When I was writing the post on Rough Mandelbrot Sets I tried out some variations on the rough set. One variation was to measure the generated M-set against a previously calculated master M-set of high precision (100000 iterations of z = z^2 + C). In the image below the master M-set is in white and the generated M-sets are in green (increasing in accuracy):

50 Against MasterHere instead of approximating with tiles I measured the accuracy of the generated sets against the master set by pixel count. Where P = \{ \text{set of all pixels} \} the ratio of P_{master} / P_{generated} produced something that threw me, the generated sets made sudden but periodic jumps in accuracy:

Graph OneLooking at the data I saw the jumps were, very roughly, at multiples of 256. The size of the image being generated was 256 by 256 pixels so I changed it to N by N for N = {120, 360, 680} and the increment was still every ~256. So I’m not really sure why, it might be obvious, if you know tell me in the comments!

I am reminded of the images generated from Fractal Binary and other Complex Bases where large geometric entities can be represented on a plane by iteration through a number system. I’d really like to know what the Mandelbrot Number System is…

Below is a table of the jumps and their iteration index:

Iterations Accuracy measure
255
256
0.241929
0.397073
510
511
0.395135
0.510806
765
766
0.510157
0.579283
1020
1021
0.578861
0.644919
1275
1276
0.644919
0.679819
1530
1531
0.679696
0.718911

Rough Mandelbrot Sets

I’ve been reading up on Zdzisław Pawlak’s Rough Set Theory recently and wanted to play with them. They are used to address vagueness in data so fractals seem like a good subject.

Super Quick Intro to Rough Sets:
A rough set is a tuple (ordered pair) of sets R(S) = \langle R_*, R^* \rangle which is used to model some target set S. The set R_* has every element definitely in set S and set R^* has every element that is possibly in set S . It’s roughness can be measured by the accuracy function \alpha(S) = \frac{|R_*|}{|R^*|} . So when |R_*| = |R^*| then the set is known as crisp (not vague) with an accuracy of 1.

A more formal example can be found on the wiki page but we’ll move on to the Mandelbrot example because it is visually intuitive:

The tiles are 36x36 pixels, the Mandelbrot set is marked in yellow. The green and white tiles are possibly i the Mandelbrot set, but the white tiles are also definitely in the Mandelbrot set.

The tiles are 36×36 pixels, the Mandelbrot set is marked in yellow. The green and white tiles are possibly in the Mandelbrot set, but the white tiles are also definitely in it.

Here the target set S contains all the pixels inside the Mandelbrot set, but we are going to construct this set in terms of tiles. Let T_1, T_2, T_3,\dots , T_n be the tile sets that contain the pixels. R^* is the set of all tiles T_x where the set T_x contains at least one pixel that is inside the Mandelbrot set, R_* is the set of all tiles T_x that contain only Mandelbrot pixels. So in the above example there are 28 tiles possibly in the set including the 7 tiles definitely in the set. Giving R(S) an accuracy of 0.25.

Tile sizes: 90, 72, 60, 45, 40, 36, 30, 24, 20, 18, 15, 12, 10, 9, 8, 6, 5, 4.

Tile width: 90, 72, 60, 45, 40, 36, 30, 24, 20, 18, 15, 12, 10, 9, 8, 6, 5, 4. There seems to be a lack of symmetry but it’s probably from computational precision loss.

Obviously the smaller the tiles the better the approximation of the set. Here the largest tiles (90×90 pixels) are so big that there are no tiles definitely inside the target set and 10 tiles possibly in the set, making the accuracy 0. On the other hand, the 4×4 tiles give us |R_*| = 1211 and |R^*| = 1506 making a much nicer:

\alpha(S) = 0.8 \overline{04116865869853917662682602921646746347941567065073}

For much more useful applications of Rough Sets see this extensive paper by Pawlak covering the short history of Rough Sets, comparing them to Fuzzy Sets and showing uses in data analysis and Artificial Intelligence.

Almost UV Photography

For ages I have wanted to do full-spectrum photography, which captures light from Infrared (IR) all the way to ultraviolet (UV), but the UV aspect of it is bloody expensive! DSLR sensors, both CCD and CMOS, capture light slightly outside the visible spectrum (VIS) but use things like hot mirrors and UV filters to narrow the band closer to 390-700nm. The sensors use channeling methods like a Bayer filter to give us the very useful RGB channels, in this post we will work with extra channels for IR and UV.

I am always looking for cheap alternatives for UV and I thought I’d test out a bit of a long shot – using a UV filter to maths my way to a UV image. To do this I bought a daylight simulating bulb that emits UVA (400-315nm) and some flowers from the local gas station. It’s a simple idea, the extra light that the UV filter blocks must be UV light so if we subtract all the other light we are left with UV.

No Filter – UV Filter = UV ResidueFlowersG-B-U RGB mapI subtracted each colour separately for each pixel: [r1-r2, g1-g2, b1-b2], it was rather red so I used the red channel for the new R,G and B making a brighter grayscaled image (see below). Then I used that new “UV” image along with the colour image to map channels [GBU to RGB] like the images Infrachrome makes using this technique. For infrared and ultraviolet he uses an adapted camera specifically for full-spectrum, infact he uses two in a fantastical and magical set up. Unfortunately mine didn’t work very well, my first guess was that the lower range of blue light being reflected as there is no sign of a nectar guide. But after consulting a pro UV photographer I was told it is due to infrared-leakage.

Wideband FlowersI thought I’d do a full spectrum map whilst I had the camera set up so I put on a 950nm IR pass filter and took another shot. In the above image the far right is the channel map of the other three.

Fractal Binary

I have previously talked about Complex Bases but I wanted to look again at Base (-1+i). It’s a really hefty number system so the length of the bit-strings increase very quickly, I’d quite like to know if there is a way to assess Radix Economy for complex and negative bases, so if there are any mathematicians out there who know – Please tell me!

Base (-1+i) to Base 10.Visualising Numbers
Today I wrote a little C++ program to act on Base 2 arithmetic but convert to decimal as if it was Base (-1+i), this meant I could increment through the bits in an ‘ordered’ fashion. The image to the left is the text output of the program, it doesn’t have a very obvious pattern to it – infact the pattern-order we derive from it is somewhat an imposed one. This is because complex numbers do not have a linear order (or Total Order) and I’m trying to list them in a linear manner. They can, on the other hand, be Well-Ordered in correspondence with the natural numbers like we’re doing here.
If we take the real and imaginary values of each number and use them as the x and y co-ordinates (like I did for generating the Mandlebrot Set fractal) then the fractal “Twindragon” appears:

Colour maps of number length in Base (-1+i).

The program I wrote runs through binary numbers starting at 0 colouring the pixel (x=r, y=i) discretely depending on number length. The result shows all Gaussian integers representable by all possible 16,12 and 8 bit complex binary strings in base (-1+i). The colour mapping relates to the position of the Most Significant Bit (essentially the bitstring length). 0 and 1 are both of length one and are the dark blue in the center of the fractal. The 12-bit and 8-bit fractal maps have been zoomed in on to emphases  the self-similarity of the shape.

Colouring the fractals like this is a nice way of showing the distribution of numbers in the complex system but, going back to the math, a number system isn’t useful without arithmetic. Luckily the (-1+i) system is closed under addition, subtraction and multiplication. For addition and multiplication it is the same as normal binary with the difference being in the carry. Below is a table of all possible carry situations:

1+1 = 1100
1+1+1 = 1101
1+1+1+1 = 111010000
1+1+1+1+1 = 111010001
1+1+1+1+1+1 = 111011100
1+1+1+1+1+1+1 = 111011101
1+1+1+1+1+1+1+1 = 111000000

Division in the systems is rather complex, an explination of that and examples of addition/subtraction/multiplication can be found in a short paper called “Arithmetic in Complex Basis” by William Gilbert. The paper also talks about an equivalent to decimal which is base (-3+i) using the digits [0,1,2,3,4,5,6,7,8,9].

Complex Bases

Bellow is Donald Knuth, his most famous work is probably The Art of Computer Programming for which the content won him a Turing Award in 1974. He also came up with the Up Arrow notation used in my posts on Large Numbers and God. Those posts were inspired by one of Knuth’s books, this post was inspired by his number system.

The Quater-Imaginary System
As a student at High School he entered into a science talent search and his submission was the Quater-Imaginary system, or Base 2i. It’s interesting because it uses the digits {0,1,2,3} for representation so it would seem at first glance to be quaternary (Base 4) – but it’s not!

It is actually an imaginary base, as the complex version is (0r±2i). Like the decimal system, quater-imaginary can finitely reperesent all positive real integers -but it can do more- it can finitely represent all positive AND negative real AND imaginary integers without signs (i.e., 3i, -8). Which can be seen in this table:

Base 10 Base 2i Base 10 Base 2i Base 10 Base 2i Base 10 Base 2i
1 1 -1 103 1i 10.2 -1i 0.2
2 2 -2 102 2i 10.0 -2i 1030.0
3 3 -3 101 3i 20.0 -3i 1030.2
4 10300 -4 100 4i 20.0 -4i 1020.0
5 10301 -5 203 5i 30.2 -5i 1020.2

 

 

The Dragon System

The Twindragon also known as the Davis-Knuth dragon!

It’s not offically called that, but the second most known complex system is Base (−1±i) which has an associated fractal shape (twindragon). It uses the numbers {0,1} for representation. It’s a very clean and eligant number system that was created by Walter F. Penney in 1965. As with quater-imaginary, this number system can be used to finitely represnt the Gaussian Integers.

Interestingly the radix starts with a negative number, but this isn’t a problem, negative bases work just aswell as positive ones. Infact in 1957 a Polish computer called BINEG was designed using negabinary!

Base 10 Base (-1±i) Base -2 Base 2
1 1 1 1
2 1100 110 10
3 1101 111 11
4 111010000 100 100
5 111010001 101 101


Base (-1±i√7)/2 and Others

Here the length of the numbers don’t increase monotonically, for example 12(11001100) and 13(11001101) are shorter than their predecessor 11(11100110011) which is the same length as 14(11100010110). It isn’t the only base to hold this attribute but it’s one of the quickest to show it. Source and explination here.

As well as whole-number radix systems it is possible to use fractions and even irrational numbers, one example I go over is Phinary (Base 1.61803…) also known as the Golden Ratio Base. On my Research Page I am looking at a series of systems, starting with the golden ratio, which I call the Metallic Series that can all be used under the same rules.

I find number systems quite interesting and I have started messing around modelling them in different ways, in a previous post (Numeral Automata) I look at them using cellular automata.