Mandelbrot: SETL & Lisp

SETL is a general-purpose programming language developed by Jack Schwartz back in the late 1960s. The language is multiparadigm – both Procedural (containing subroutines and control structures like if statements) and Set Theoretical. The latter is not often mentioned when talking about language paradigms – and is not to be confused with Logical Programming. The concept is outlined in the 1974 paper An Introduction to the Set Theoretical Language SETL. Importantly though data in SETL is of three main types: Atoms, Sets, and Sequences (also referred to as tuples or ordered sets).

A good overview of SETL can be found in the GNU SETL Om.

setl-mandelbrot

Pixels inside the Mandelbrot Set are marked in black, the code used to generate them (mandelbrot.setl) can be found here.

Generation of the Mandelbrot Set
On the Wikipedia page for the Mandelbrot Set you will find its formal definition, which looks like so: M = \left\{c\in \mathbb C : \exists s\in \mathbb R, \forall n\in \mathbb N, |P_c^n(0)| \le s \right\}.

The most fantastic thing about SETL is how powerful its Set Builder Notation is. Almost exactly as you would in the formal case (removing ‘there exists some real s’ for the practical application):

M := {c : c in image | forall num in {0..iterations} | cabs(pofc(c, num)) <= 2};

For some reason SETL doesn’t support complex numbers, but they are easily handled by writing the necessary procedures we need like cabs, ctimes, and cplus dealing with tuples in the form [x, y]. The variable ‘image’ is a sequence of these tuples. Another procedure is written, pofc, which is a more practical version of P_c^n(0).

Interaction with the Lisp graphical display
The goal of the SETL program is to produce a set of points that lie inside the Mandelbrot set. To actually display the image I used Common Lisp and displayed a widget with the image using CommonQt. In a very rudimentary way I had mandelbrot.setl take arguments about the image then print the set of pixel co-ordinates. All lisp had to do was swap and ‘{}’ or ‘[]’ for ‘()’ and read it as lisp code then update the image.

(setf in-set (read-from-string (parse-line (uiop:run-program "setl mandelbrot.setl -- -250 -250 250 8" :output :string))))
(draw-mandel instance in-set)

An after-thought was to make a Mandelbrot searcher where you could zoom and move using the mouse but the SETL code is such an inefficient way of doing it that it’s not worth it. As an attempt to mimic the formal definition it was highly successful and fun. Though much quicker SETL code could be written for generating the Mandelbrot Set.

Source file for mandelbrot.setl and the Lisp/CommonQt front end can be found here.

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.

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

AI: Conway Creatures!

Recently I’ve been reading up on Cellular Evolutionary Algorithms and on the use of Genetic Algorithms (GAs) to evolve Cellular Automata (CA). I want to try out all sorts of different things so I will be doing a series of posts where I explore different interpretations of a concept – Conway Creatures.

Get Involved!
I have a few programmers, logicians and AI enthusiasts that follow my blog so I wanted to see if I could make something of the concept. I’d like to see all your interpretations of what a Conway creature is. Given a rough description, which is essentially: creatures (2D,3D, etc) of which the properties are evolved in some way using a mix of CA and GAs. If I get any i’ll do posts dedicated to the entries. I would also like to see varied definitions of the concept such as the use of other works by John Conway (e.g., the growth rate of the Look and Say sequence – Conway’s Constant, the Surreal Numbers, Conway notation for polyhedra, etc), other CA rules and other Evolutionary methods.

The First Detour – Longevity in Game of Life:
I began to write the program and found myself wondering “What are the characteristics of longevity in CAs?” and I’m still not sure. I’ve been trying different takes on mutation and crossover where I take chunks of the board and flip them or turn them all on/off. It doesn’t seem to make much difference, I was hoping it would conserve locality. I also tried out Boltzmann selection (Simulated Annealing) but tournament selection (dueling) worked much better. Any ideas?

This is my program so far, I am taking a little detour to look into longevity, but in Issue 1 there will be a creature where the 3D terrain is. Probably not very complicated, I was thinking of making the creature some sort of shape, like an octahedron.