Tag Archives: compiler

A cryptoweaving experiment

Archaeologists can read a woven artifact created thousands of years ago, and from its structure determine the actions performed in the right order by the weaver who created it. They can then recreate the weaving, following in their ancestor’s ‘footsteps’ exactly.

This is possible because a woven artifact encodes time digitally, weft by weft. In most other forms of human endeavor, reverse engineering is still possible (e.g. in a car or a cake) but instructions are not encoded in the object’s fundamental structure – they need to be inferred by experiment or indirect means. Similarly, a text does not quite represent its writing process in a time encoded manner, but the end result. Interestingly, one possible self describing artifact could be a musical performance.

Looked at this way, any woven pattern can be seen as a digital record of movement performed by the weaver. We can create the pattern with a notation that describes this series of actions (a handweaver following a lift plan), or move in the other direction like the archaeologist, recording a given notation from an existing weave.

example
A weaving and its executable code equivalent.

One of the potentials of weaving I’m most interested in is being able to demonstrate fundamentals of software in threads – partly to make the physical nature of computation self evident, but also as a way of designing new ways of learning and understanding what computers are.

If we take the code required to make the pattern in the weaving above:

(twist 3 4 5 14 15 16)
(weave-forward 3)
(twist 4 15)
(weave-forward 1)
(twist 4 8 11 15)

(repeat 2
 (weave-back 4)
 (twist 8 11)
 (weave-forward 2)
 (twist 9 10)
 (weave-forward 2)
 (twist 9 10)
 (weave-back 2)
 (twist 9 10)
 (weave-back 2)
 (twist 8 11)
 (weave-forward 4))

We can “compile” it into a binary form which describes each instruction – the exact process for this is irrelevant, but here it is anyway – an 8 bit encoding, packing instructions and data together:

8bit instruction encoding:

Action  Direction  Count/Tablet ID (5 bit number)
0 1         2              3 4 5 6 7 

Action types
weave:    01 (1)
rotate:   10 (2)
twist:    11 (3)

Direction
forward: 0
backward: 1

If we compile the code notation above with this binary system, we can then read the binary as a series of tablet weaving card flip rotations (I’m using 20 tablets, so we can fit in two instructions per weft):

0 1 6 7 10 11 15
0 1 5 7 10 11 14 15 16
0 1 4 5 6 7 10 11 13
1 6 7 10 11 15
0 1 5 7 11 17
0 1 5 10 11 14
0 1 4 6 7 10 11 14 15 16 17
0 1 2 3 4 5 6 7 11 12 15
0 1 4 10 11 14 16
1 6 10 11 14 17
0 1 4 6 11 16
0 1 4 7 10 11 14 16
1 2 6 10 11 14 17
0 1 4 6 11 12 16
0 1 4 7 10 11 14 16
1 5

If we actually try weaving this (by advancing two turns forward/backward at a time) we get this mess:

close

The point is that (assuming we’ve made no mistakes) this weave represents *exactly* the same information as the pattern does – you could extract the program from the messy encoded weave, follow it and recreate the original pattern exactly.

The messy pattern represents both an executable, as well as a compressed form of the weave – taking up less space than the original pattern, but looking a lot worse. Possibly this is a clue too, as it contains a higher density of information – higher entropy, and therefore closer to randomness than the pattern.

Procedural landscape demo on OUYA/Android

A glitchy procedural, infinite-ish landscape demo running on Android and OUYA. Use the left joystick to move around on OUYA, or swiping on Android devices with touchscreens. Here’s the apk, and the source is here.

Screenshot_2014-01-06-07-18-45

It’s great to be able to have a single binary that works across all these devices – from OUYA’s TV screen sizes to phones, and using the standard gesture interface at the same time as the OUYA controller.

The graphics are programmed in Jellyfish Lisp, using Perlin noise to create the landscape. The language is probably still a bit too close to the underlying bytecode in places, but the function calling is working and it’s getting easier to write and experiment with the code.

(define terrain
  '(let ((vertex positions-start)
         (flingdamp (vector 0 0 0))
         (world (vector 0 0 0)))

     ;; recycle a triangle which is off the screen
     (define recycle 
       (lambda (dir)         
         ;; shift along x and y coordinates:
         ;; set z to zero for each vertex
         (write! vertex       
                 (+ (*v (read vertex) 
                        (vector 1 1 0)) dir))
         (write! (+ vertex 1) 
                 (+ (*v (read (+ vertex 1)) 
                        (vector 1 1 0)) dir))
         (write! (+ vertex 2) 
                 (+ (*v (read (+ vertex 2)) 
                        (vector 1 1 0)) dir))

         ;; get the perlin noise values for each vertex
         (let ((a (noise (* (- (read vertex) world) 0.2)))
               (b (noise (* (- (read (+ vertex 1)) 
                               world) 0.2)))
               (c (noise (* (- (read (+ vertex 2))
                               world) 0.2))))

           ;; set the z coordinate for height
           (write! vertex 
                   (+ (read vertex) 
                      (+ (*v a (vector 0 0 8)) 
                         (vector 0 0 -4))))
           (write! (+ vertex 1) 
                   (+ (read (+ vertex 1)) 
                      (+ (*v b (vector 0 0 8)) 
                         (vector 0 0 -4))))
           (write! (+ vertex 2) 
                   (+ (read (+ vertex 2)) 
                      (+ (*v c (vector 0 0 8)) 
                         (vector 0 0 -4))))

           ;; recalculate normals
           (define n (normalise 
                      (cross (- (read vertex)
                                (read (+ vertex 2)))
                             (- (read vertex)
                                (read (+ vertex 1))))))

           ;; write to normal data
           (write! (+ vertex 512) n)
           (write! (+ vertex 513) n)
           (write! (+ vertex 514) n)

           ;; write the z height as texture coordinates
           (write! (+ vertex 1536) 
                   (*v (swizzle zzz a) (vector 0 5 0)))          
           (write! (+ vertex 1537) 
                   (*v (swizzle zzz b) (vector 0 5 0)))          
           (write! (+ vertex 1538) 
                   (*v (swizzle zzz c) (vector 0 5 0))))))

     ;; forever
     (loop 1
       ;; add inertia to the fling/gamepad joystick input
       (set! flingdamp (+ (* flingdamp 0.99)
                          (*v
                           (read reg-fling)
                           (vector 0.01 -0.01 0))))

       (define vel (* flingdamp 0.002))
       ;; update the world coordinates
       (set! world (+ world vel))

       ;; for each vertex
       (loop (< vertex positions-end)         

         ;; update the vertex position
         (write! vertex (+ (read vertex) vel))
         (write! (+ vertex 1) (+ (read (+ vertex 1)) vel))
         (write! (+ vertex 2) (+ (read (+ vertex 2)) vel))

         ;; check for out of area polygons to recycle 
         (cond
          ((> (read vertex) 5.0)
           (recycle (vector -10 0 0)))         
          ((< (read vertex) -5.0)
           (recycle (vector 10 0 0))))
         
         (cond
          ((> (swizzle yzz (read vertex)) 4.0)
           (recycle (vector 0 -8 0)))
          ((< (swizzle yzz (read vertex)) -4.0)
           (recycle (vector 0 8 0))))

         (set! vertex (+ vertex 3)))
       (set! vertex positions-start))))

This lisp program compiles to 362 vectors of bytecode at startup, and runs well even on my cheap Android tablet. The speed seems close enough to native C++ to be worth the effort, and it’s much more flexible (i.e. future livecoding/JIT compilation possibilities). The memory layout is shown below, it’s packing executable instructions and model data into the same address space and doesn’t use any memory allocation while it’s running (no garbage collection and not even any C mallocs). The memory size is configurable but the nature of the system is such that it would be possible to put executable data into unused graphics sections (eg. normals or vertex colours), if appropriate.

jvm

Jellyfish: A daft new language is born

After trying, and failing, to write a flocking system in jellyfish bytecode I wrote a compiler using the prototype betablocker one. It reads a scheme-ish imperative language and generates bytecode (which is also invented, and implemented in C++) it only took a couple evenings and a train journey to write, and it even seems to work.

jellyfish

The basic idea is to walk through the code tree described by the scheme lists generating bits of bytecode that fit together. Let’s take logical “not” as an example. Like GPU processors, the only datatype is vectors of 3 floats, and we define false as 0 in the x position and anything else in x to be true (ignoring what’s in y or z). There is no single instruction for “not” so we have to build it from the other instructions. For example this bit of code:

(not (vector 0 0 0))

should return (vector 1 0 0). When we are walking the tree of lists we check the first element and dispatch to a set of functions, one for each type of (higher level) instruction which ’emit’s a list containing the bytecode required. The one for ‘not’ looks like this, where x is the expression, e.g. ‘(not (vector 0 0 0))’:

(define (emit-not x)
  (append
   (emit-expr (cadr x))
   (emit (vector jmz 3 0))
   (emit (vector ldl 0 0))
   (emit (vector jmr 2 0))
   (emit (vector ldl 1 0))))

The first thing it does is return all the instructions required for the expression we pass in the second element of ‘x’ with ’emit-expr’. With our simple example it will just push (vector 0 0 0) onto the stack, but it could be a whole load of complicated nested expressions, and it will work the same.

After that we have some bytecode:

jmz 3 0 ;; if top of stack is 0, jump forward 3 instructions (ldl 1 0)
ldl 0 0 ;; load 0 onto the stack
jmr 2 0 ;; jump forward 2 instructions (skip to next code section)
ldl 1 0 ;; load 1 onto the stack

So this just checks (and removes) the top element on the stack and pushes the opposite logical value. Pushing a single float like the ‘ldl’ (load literal) instructions above expands to a vector value internally, it’s just a convenience. Some instructions (such as those involving vector maths) are just a single instruction, others like conditionals or loops are a bit trickier as they need to count instructions to skip over variable length sections of program.

We add variables in the form of ‘let’ that map to addresses a the start of memory, read and write for accessing model memory like array lookups. The full flocking system looks like this, and animates a points primitive in OpenGL:

(let ((vertex 512) 
      (accum-vertex 512)  
      (closest 9999)
      (closest-dist 9999)
      (diff 0)
      (vel 1024))
      (loop 1 ;; infinite loop
        (loop (< vertex 532) ;; for every vertex
          ;; find the closest vertex
          (loop (< accum-vertex 532) 
            (cond 
              ;; if they're not the same vert
              ((not (eq? accum-vertex vertex))
              ;; get vector between the points
              (set! diff (- (read vertex) (read accum-vertex)))
              (cond 
                ;; if it's closer so far
                ((< (mag diff) closest-dist)
                ;; record vector and distance
                (set! closest diff)
                (set! closest-dist (mag closest))))))
              (set! accum-vertex (+ accum-vertex 1)))
              ;; reset accum-vertex for next time
              (set! accum-vertex 512)

              ;; use closest to do the flocking, add new velocity 
              ;; to old (to add some inertia)
              (write! vel (+ (* (read vel) 0.99)
                   ;; attract to centre
                   (* (+ (* (- (read vertex) (vector 0 0 0)) 0.05)
                         ;; repel from closest vertex
                         (* (normalise closest) -0.15)) 0.01)))
              ;; add velocity to vertex position
              (write! vertex (+ (read vel) (read vertex))) 
                
              ;; reset and increment stuff
              (set! closest-dist 9999)
              (set! vel (+ vel 1))
              (set! vertex (+ vertex 1)))
            ;; reset for main loop
            (set! vertex 512)
            (set! vel 1024)))

This compiles to 112 vectors of bytecode (I should call it vectorcode really) with extra debugging information added so we can see the start and the end of each higher level instruction. It all looks like this – which most importantly I didn’t need to write by hand!

10 30000 0 ;; top memory positions are for registers controlling 
512 2 1    ;; program and graphics state (primitive type and number of verts)
nop 0 0    ;; space
nop 0 0    ;; for all
nop 0 0    ;; the variables
nop 0 0    ;; we use 
nop 0 0    ;; in the program
nop 0 0
nop 0 0
nop 0 0
;; starting let  <- program starts here
ldl 512 0        ;; load all the 'let' variable data up
sta 4 0
ldl 512 0
sta 5 0
ldl 9999 0
sta 6 0
ldl 9999 0
sta 7 0
ldl 0 0
sta 8 0
ldl 1024 0
sta 9 0
;; starting loop  <- start the main loop
;; starting loop
;; starting loop
;; starting cond
;; starting not
;; starting eq?
lda 5 0
lda 4 0
sub 0 0
jmz 3 0
ldl 0 0
jmr 2 0
ldl 1 0
;; ending eq?
jmz 3 0
ldl 0 0
jmr 2 0
ldl 1 0
;; ending not
jmz 38 0
;; starting set!
;; starting -
;; starting read
ldi 4 0
;; ending read
;; starting read
ldi 5 0
;; ending read
sub 0 0
;; ending -
sta 8 0
;; ending set!
;; starting cond
;; starting <
;; starting mag
lda 8 0
len 0 0
;; ending mag
lda 7 0
jlt 3 0
ldl 1 0
jmr 2 0
ldl 0 0
;; ending <
jmz 12 0
;; starting set!
lda 8 0
sta 6 0
;; ending set!
;; starting set!
;; starting mag
lda 6 0
len 0 0
;; ending mag
sta 7 0
;; ending set!
;; ending cond
;; ending cond
;; starting set!
;; starting +
lda 5 0
ldl 1 0
add 0 0
;; ending +
sta 5 0
;; ending set!
;; starting <
lda 5 0
ldl 532 0
jlt 3 0
ldl 1 0
jmr 2 0
ldl 0 0
;; ending <
jmz 2 0
jmr -72 0
;; ending loop
;; starting set!
ldl 512 0
sta 5 0
;; ending set!
;; starting write!
;; starting +
;; starting *
;; starting read
ldi 9 0
;; ending read
ldl 0.9900000095 0
mul 0 0
;; ending *
;; starting *
;; starting +
;; starting *
;; starting -
;; starting read
ldi 4 0
;; ending read
ldlv 0 0
nop 0 0
sub 0 0
;; ending -
ldl 0.05000000075 0
mul 0 0
;; ending *
;; starting *
;; starting normalise
lda 6 0
nrm 0 0
;; ending normalise
ldl -0.150000006 0
mul 0 0
;; ending *
add 0 0
;; ending +
ldl 0.009999999776 0
mul 0 0
;; ending *
add 0 0
;; ending +
sti 9 0
;; ending write!
;; starting write!
;; starting +
;; starting read
ldi 9 0
;; ending read
;; starting read
ldi 4 0
;; ending read
add 0 0
;; ending +
sti 4 0
;; ending write!
;; starting set!
ldl 9999 0
sta 7 0
;; ending set!
;; starting set!
;; starting +
lda 9 0
ldl 1 0
add 0 0
;; ending +
sta 9 0
;; ending set!
;; starting set!
;; starting +
lda 4 0
ldl 1 0
add 0 0
;; ending +
sta 4 0
;; ending set!
;; starting <
lda 4 0
ldl 532 0
jlt 3 0
ldl 1 0
jmr 2 0
ldl 0 0
;; ending <
jmz 2 0
jmr -160 0
;; ending loop
;; starting set!
ldl 512 0
sta 4 0
;; ending set!
;; starting set!
ldl 1024 0
sta 9 0
;; ending set!
ldl 1 0
jmz 2 0
jmr -173 0
;; ending loop
;; ending let

Compiling Scheme to Javascript

Recently I’ve been continuing my experiments with compilers by writing a Scheme to Javascript compiler. This is fairly simple as the languages are very similar, both have garbage collection and first class functions so it’s largely a case of reusing these features directly. There are some caveats though – here is an example of the canonical factorial example in Scheme:

(define factorial
  (lambda (n)
    (if (= n 0) 1
        (* n (factorial (- n 1))))))

The Javascript code generated by the compiler:

var factorial = function (n)
{
    if ((n == 0)) {
        return 1
    } else {
        return (n * factorial((n - 1)))
    }
}

Scheme has tail call optimisation, meaning that recursive calls are as fast as iterative ones – in Javascript however, a function that calls itself will gradually use up the stack. The factorial example above breaks with larger numbers so we need to do some work to make things easier for Javascript interpreters. When considering list processing, fold can be considered a core form that abstracts all other list processing. If we make that fast, we can reuse it to define higher order list processing such as filter, which takes a function and a list and returns another list. The function is called on each element, if it returns false it’s filtered out of the resulting list.

(define filter
  (lambda (fn l)
    (foldl
     (lambda (i r)
       (if (fn i) (append r (list i)) r))
     ()
     l)))

Compiling this with an iterative version of fold – which uses a for loop in Javascript, we generate this code:

var filter = function (fn,l)
{
    return (function() {
        var _foldl_fn=function (i,r) {
            if (fn(i)) {
                return r.concat([i])
            } else {
                return r
            }
        };

        var _foldl_val=[];
        var _foldl_src=l;
        for (var _foldl_i=0; _foldl_i<_foldl_src.length; _foldl_i++) {
            _foldl_val = _foldl_fn(_foldl_src[_foldl_i], _foldl_val); 
        }
        return _foldl_val; })()
    }
}

We have to be a little bit careful that variables created by the compiler don’t clash with those of the user’s code, so we have to make really ugly variable names. You also need to be careful to wrap code in closures as much as possible to control the scope. The problem with this is that there is probably a limit to the amount of nesting possible, especially comparing different implementations of Javascript. A interesting project that has got much further than this is Spock. More context to this work and some actual source code soon…