Tag Archives: scheme

Livecoding UAVs for environmental research

Some screenshots of the UAV livecoding visual programming language. Weather being on our side, we’re planning some test flights later this week! The first program uses GPS to take photos with an overlap of 50% at 300 metres altitude, based on the vertical camera angle as reported from the device. It assumes the the flight orientation is level:

Screenshot_2015-01-20-23-17-49

The blocks are all drag and drop and get converted into Scheme code which is run by a modified tinyscheme interpreter. The code can be saved and loaded, and I’m planning to make it possible for people to share code via email.
This is a simpler program which takes a photo every 3 seconds and records a handful of sensor data to the database:

Screenshot_2015-01-20-23-18-44

At the bottom you can see a squashed camera preview – I’ve tried various approaches (hiding, scaling to 0 pixels etc) but android requires that there is a preview somewhere in order to take a photo properly. You can view the recorded data on the device too, for checking. There is also a ‘flight mode’ which locks and turns off the screen, and ignores all button events. On some phones you need to take out the battery to stop the program running but unfortunately on others you can still use the power button to close the program.

Screenshot_2015-01-21-01-09-56

Butterfly wing pattern evolution

I’ve been working lately with the Heliconius research group at the University of Cambridge on a game to explain the evolution of mimicry in butterfly wing patterns. It’s for use at the Summer Science Exhibition at the Royal Society in London, where it’ll be run on a large touch screen for school children and visiting academics to play.

game

This is my first game to merge the WebGL fluxus port (for rendering the butterflies) and the nightjar HTML5 canvas game engine – which takes care of the 2D elements. Both are making use of my ad-hoc Scheme to Javascript compiler and are rendered as two canvas elements on top of each other, which seems to work really well.

The game models biological processes for education purposes (as opposed to the genetic programming as used on the camouflage egg game), and the process of testing this, and deciding what simplifications are required has become a fascinating part of the design process.

end

In biosciences, genetics are modelled as frequencies of specific alleles in a given population. An allele is a choice (a bit like a switch) encoded by a gene, so a population can be represented as a list of genes where each gene is a list of frequencies of each allele. In this case the genetics consists of choices of wing patterns. The game is designed to demonstrate the evolution of an edible species mimicking a toxic one – we’ll be publishing the game after the event. A disclaimer, my terminology is probably misaligned in the following code, still working on that.

;; an allele is just a string id and a probability value
(define (allele id probability)
  (list id probability))

;; a gene is simply a list of alleles

;; return the id of an allele chosen based on probability
(define (gene-express gene)
  (let ((v (rndf)))
    (car
     (cadr
      (foldl
       (lambda (allele r)
         (let ((segment (+ (car r) (allele-probability allele))))
           (if (and (not (cadr r))
                    (< v segment))
               (list segment allele)
               (list segment (cadr r)))))
       (list 0 #f)
       gene)))))

;; a chromosome is simple list of genes
;; returns a list of allele ids from the chromosome based on probability
(define (chromosome-express chromo)
  (map gene-express chromo))

When an individual is removed from the population, we need to adjust the probabilities by subtracting based on the genetics of the eaten individual, and the adding to the other alleles to keep the probabilities summing to one:

;; prevents the probability from 'fixing' at 0% or 100%
;; min(p,(1-p))*0.1
(define (calc-decrease p)
  (* (min p (- 1 p)) allele-decrease))

;; remove this genome from the population
(define (gene-remove-expression gene genome)
  (let ((dec (calc-decrease (allele-probability (car gene)))))
    (let ((inc (allele-increase dec (length gene))))
      (map
       (lambda (allele)
         (if (eq? (allele-id allele) genome)
             (allele-modify-probability 
                allele (- (allele-probability allele) dec))
             (allele-modify-probability 
                allele (+ (allele-probability allele) inc))))
       gene))))

Raspberry Pi: Built for graphics livecoding

I’m working on a top secret project for Sam Aaron of Meta-eX fame involving the Raspberry Pi, and at the same time thinking of my upcoming CodeClub lessons this term – we have a bunch of new Raspberry Pi’s to use and the kids are at the point where they want to move on from Scratch.

This is a screenshot of the same procedural landscape demo previously running on Android/OUYA running on the Raspberry Pi, with mangled texture colours and a cube added via a new livecoding repl:

IMG_20140108_232857

Based on my previous experiments, this program uses the GPU for the Raspberry Pi (the VideoCore IV bit of the BCM2835). It’s fast, allows compositing on top of whatever else you are running at the time, and you can run it without X windows for more CPU and memory, sounds like a great graphics livecoding GPU to me!

Here’s a close up of the nice dithering on the texture – not sure yet why the colours are so different from the OUYA version, perhaps a dodgy blend mode or a PNG format reading difference:

IMG_20140108_232914

The code is here (bit of a mess, I’m in the process of cleaning it all up). You can build in the jni folder by calling “scons TARGET=RPI”. This is another attempt – looks like my objects are inside out:

IMG_20140109_004111

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

Functions, abstraction and compiling

More puzzles from my compiler writing experiments – this time figuring out how function calls work. They are so ingrained as part of computer languages – it seems somehow surprising to me that they are quite challenging to implement as bytecode.

Conceptually, functions are primarily a means for humans to break problems down into smaller parts in order to better reason about them – the process of doing this is called abstraction. What is good for human reasoning, is also good for efficient use of finite space in memory – so good functions will be able to be reused in as many places as possible (to be general, in other words).

At the low level, when a function is called we jump to a new location of the code, do some stuff, and then return to where we came from. We also need to deal with arguments passed to the function (giving it different values to work on), and then we need to keep things like the return address and result of the function somewhere safe.

The Jellyfish Virtual Machine is a stack machine – so everything needs to be stored on a single stack we can push and pop values to and from (vectors in this case). Calling a function is a case of:

1. Calculating and pushing the return address to the stack.
2. Calculating and pushing all the arguments onto the stack in order.
3. Jump to the function pointer.

;; return a list of vector instructions to generate 
;; a function call to an existing function pointer
(define (emit-fncall x addr)
  ;; generate instructions to eval and push all the arguments
  (let ((args (emit-expr-list (cdr x))))
    (append
     ;; first push the address we want to return to to the stack
     ;; skip the argument pushing code and the following function jump
     ;; we need to tell the linker to fix the address later on:
     (emit (list 'add-abs-loc 'this 1
                 ;; adds absolute location to the offset
                 (vector ldl (+ (length args) 2) 0)))
     args ;; code to push arguments to stack
     (emit (vector jmp addr 0))))) ;; jump to the function pointer

One complexity is that we won’t know the exact address of the function until the compilation process is finished, so we need to tag the relevant instruction to be modified in a second pass later on – this is called linking, which stitches the addresses together properly after compiling.

When we are in the function with the stack set up correctly we need to:

1. Pop all the arguments from the stack and put them somewhere where they can be referred to by name.
2. Do the body of the function.
3. Store the end result on the stack.
4. Jump back to the return address.

When finished, the only thing should be the result of the function call at the top of the stack. The code to generate this is provided by the core “lambda” function (which can be assigned to a name for calling later or called directly – anonymously).

;; lambda - create a function, and return the pointer to it
(define (emit-lambda x)
  (let* ((body
          ;; first we need to get all the arguments out of the
          ;; stack so the function body can refer to them
          (append
           (map ;; map over the argument names
            (lambda (arg)
              (make-variable! arg)
              ;; store the value where it can be looked up by the name
              (vector sta (variable-address arg) 0))
            (cadr x))
           ;; now args are stored, do the body
           (emit-expr-list (cddr x))
           ;; swap ret pointer with the result 
           ;; so it's the top of the stack
           (emit (vector swp 0 0))
           ;; jump to the address on the stack
           (emit (vector jms 0 0))))
         ;; make-function! stores the code in a table 
         ;; and returns the address the function will exist at
         (loc (make-function! body)))
    (append
     (emit
      ;; use the linker again to offset 
      ;; from function code section start
      (list 'add-abs-loc 'function-code 1
            (vector ldl loc 0))))))

Mongoose 2000

A screen shot from the Mongoose 2000 project, we now have most of the ‘pup focal’ interfaces working and syncing their data via the Raspberry Pi. This is the interface for recording a pup aggression event – including the identity of the aggressive mongoose and some information on the cause and severity. Each mongoose has a code, and we’re using sliding toggle button interfaces for quickly picking them – these can be filtered to restrict them to adults, pups, males or females where required.

pupaggr

The interface was written using “starwisp” – my system for building android applications in Scheme. The Mongoose 2000 app has lots of reusable interfaces, so it’s mostly constructed from fragments. There are no specialised database tables, so I can simply add or modify the widgets here and the data automagically appears in the Raspberry Pi export, which makes it very fast to build. I’ve abstracted the mongoose button grid selectors and tristate buttons (yes/no/maybe) as they are used in a lot of places. Here is the entire definition of the fragment for the interface above, the code includes everything for creating and recording the database entity for this event and all the android callbacks it needs to respond to external events.

(fragment
   "ev-pupaggr"
   
   ;; define the interface layout first
   (linear-layout
    (make-id "") 'vertical fillwrap pf-col
    (list
     (mtitle "title" "Event: Pup aggression")
     (build-grid-selector "pf-pupaggr-partner" 
                          "single" "Aggressive mongoose")
     (linear-layout
      (make-id "") 'horizontal 
      (layout 'fill-parent 100 '1 'left 0) trans-col
      (list
       (vert
        (mtext "" "Fighting over")
        (spinner (make-id "pf-pupaggr-over") 
                 (list "Food" "Escort" "Nothing" "Other") fillwrap
                 (lambda (v)
                   (entity-add-value! "over" "varchar" v) '())))
       (vert
        (mtext "" "Level")
        (spinner (make-id "pf-pupaggr-level") 
                 (list "Block" "Snap" "Chase" "Push" "Fight") fillwrap
                 (lambda (v)
                   (entity-add-value! "level" "varchar" v) '())))
       (tri-state "pf-pupaggr-in" "Initiate?" "initiate")
       (tri-state "pf-pupaggr-win" "Win?" "win")))
     (spacer 20)
     (horiz
      (mbutton "pf-pupaggr-done" "Done"
        (lambda ()
          (entity-add-value! "parent" "varchar" 
            (get-current 'pup-focal-id ""))
            (entity-record-values db "stream" "pup-focal-pupaggr")
            (list (replace-fragment (get-id "event-holder") 
                                    "events"))))
      (mbutton "pf-pupaggr-cancel" "Cancel"
        (lambda ()
          (list (replace-fragment (get-id "event-holder") 
                                  "events")))))))

   ;; define the fragment's event callbacks 
   (lambda (fragment arg) ;; on create, return layout for building
     (activity-layout fragment))

   ;; on start - update contents from the db
   (lambda (fragment arg)  
     (entity-reset!)
     (list
      (populate-grid-selector
       "pf-pupaggr-partner" "single" ;; select single mongoose
       (db-mongooses-by-pack) #t     ;; from the whole pack 
       (lambda (individual)          ;; <- called when selected
         (entity-add-value! "id-with" "varchar" 
           (ktv-get individual "unique_id")) 
         (list)))
      ))

   (lambda (fragment) '()) ;; on stop
   (lambda (fragment) '()) ;; on resume
   (lambda (fragment) '()) ;; on pause
   (lambda (fragment) '())) ;; on destroy

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

Genetic programming egg patterns in HTML5 canvas

Part of the ‘Project Nightjar’ camouflage work I’m doing for the Sensory Ecology group at Exeter University is to design citizen science games we can build to do some research. One plan is to create lots of patterns in the browser that we can run perceptual models on for different predator animals, and use an online game to compare them with human perception.

The problem is that using per-pixel processing in order to generate the variety of patterns we need is hard to do quickly in Javascript, so I’m looking at using genetic programming to build image processing trees using the HTML5 canvas image composition modes. You can see it in action here, and the source is here. Here are some example eggs built from very simple test images blended together, these are just random programs, but a couple of them are pretty good:

random-eggs

A nice aspect of this is that it’s easy to artistically control the patterns by changing the starting images, for example much more naturalistic patterns would result from noisier, less geometric base images and more earthy colours. This way we can have different ‘themes’ for levels in a game, for example.

I’m using the scheme compiler I wrote for planet fluxus to do this, and building trees that look like this:


'("op"
  "lighter"
  ("op"
   "source-in"
   ("op"
    "source-out"
    ("terminal" (124 57 0 1) "stripe-6")
    ("terminal" (42 23 0 1) "dots-6"))
   ("op"
    "copy"
    ("terminal" (36 47 0 1) "stripe-7")
    ("terminal" (8 90 1.5705 1) "red")))
  ("terminal" (108 69 0 1) "green"))

Ops are the blend mode operations, and terminals are images, which include translation and scale (not currently used). The egg trees get drawn with the function below, which shows the curious hybrid mix of HTML5 canvas and Scheme I’m using these days (and some people may find offensive :) Next up is to actually do the genetic programming part, so mutating and doing crossover on the trees.


(define (draw-egg ctx x y program)
  (if (eq? (program-type program) "terminal")
      (begin
        (set! ctx.fillStyle
              (ctx.createPattern
               (find-image (terminal-image program) 
                           image-lib) "repeat"))

        ;; centre the rotation
        (ctx.translate 64 64)
        (ctx.rotate 
            (transform-rotate (terminal-transform program)))
        (ctx.translate -64 -64)

        ;; make the pattern translate by moving, 
        ;; drawing then moving back
        (ctx.translate 
            (transform-x (terminal-transform program))
             (transform-y (terminal-transform program)))

        (ctx.fillRect 
            (- 0 (transform-x (terminal-transform program)))
            (- 0 (transform-y (terminal-transform program)))
            (* 127 2) (* 127 2))

        (ctx.translate 
            (- 0 (transform-x (terminal-transform program)))
            (- 0 (transform-y (terminal-transform program)))))
      (begin
        ;; slightly overzealous context saving/restoring
        (ctx.save)
        ;; set the composite operation
        (set! ctx.globalCompositeOperation (operator-type program))
        (ctx.save)
        (draw-egg ctx x y (operator-operand-a program))
        (ctx.restore)
        (ctx.save)
        (draw-egg ctx x y (operator-operand-b program))
        (ctx.restore)
        (ctx.restore))))

Planet Fluxus

Fluxus now runs in a browser using WebGL. Not much is working yet – (draw-cube), basic transforms, colours and textures. I’ve also built a small site in django so people can share (or perhaps more likely, corrupt) each other’s scripts. Also much inspired by seeing a load of great live coding at the algoraves by Davide Della Casa and Guy John using livecodelab.

fluxuswebgl2

fluxuswebgl

This is a spin off from the work I did a few weeks ago on a silly Scheme to Javascript compiler. It’s still pretty silly, but in order to explain better, first we take a scheme program like this:

;; a tree
(define (render n)
    (when (not (zero? n))
        (translate (vector 0 1 0))
        (with-state
            (scale (vector 0.1 1 0.1))
            (draw-cube))
        (scale (vector 0.8 0.8 0.8))
        (with-state
            (rotate (vector 0 0 25))
            (render (- n 1)))
        (with-state
            (rotate (vector 0 0 -25))
            (render (- n 1)))))

(every-frame 
    (with-state
        (translate (vector 0 -3 0))
        (render 8)))

Then parse it straight into JSON, so lists become Javascript arrays and everything else is a string, also doing minor things like switching “-” to “_”:

[["define",["render","n"],
    ["when",["not",["zero_q","n"]],
        ["translate",["vector","0","1","0"]],
        ["with_state",
            ["scale",["vector","0.1","1","0.1"]],
            ["draw_cube"]],
        ["scale",["vector","0.8","0.8","0.8"]],
        ["with_state",
            ["rotate",["vector","0","0","25"]],
            ["render",["-","n","1"]]],
        ["with_state",
            ["rotate",["vector","0","0","-25"]],
            ["render",["-","n","1"]]]]],

["every_frame",
    ["with_state",
    ["translate",["vector","0","-3","0"]],
    ["render","8"]]]]

Next we do some syntax expansion, so functions become full lambda definitions, and custom fluxus syntax forms like (with-state) get turned into lets and begins wrapped with state (push) and (pop). These transformations are actually written in Scheme (not quite as define-macros yet), and are compiled at an earlier stage. It now starts to increase in size:

[["define","render",
    ["lambda",["n"],
        ["when",["not",["zero_q","n"]],
            ["translate",["vector","0","1","0"]],
            ["begin",
                ["push"],
                ["let",[["r",["begin",
                        ["scale",["vector","0.1","1","0.1"]],
                        ["draw_cube"]]]],
                    ["pop"],"r"]],
            ["scale",["vector","0.8","0.8","0.8"]],
            ["begin",
                ["push"],
                ["let",[["r",["begin",
                        ["rotate",["vector","0","0","25"]],
                        ["render",["-","n","1"]]]]],
                    ["pop"],"r"]],
            ["begin",
                ["push"],
                ["let",[["r",["begin",
                        ["rotate",["vector","0","0","-25"]],
                        ["render",["-","n","1"]]]]],
                ["pop"],"r"]]]]],

["every_frame_impl",
    ["lambda",[],
        [["begin",
            ["push"],
            ["let",[["r",["begin",
                    ["translate",["vector","0","-3","0"]],
                    ["render","8"]]]],
            ["pop"],"r"]]]]]

Then, finally, we convert this into a bunch of Javascript closures. It’s pretty hard to unpick what’s going on at this point, I’m sure there is quite a bit of optimisation possible, though it does seem to work quite well:

var render = function (n) {
    if (!(zero_q(n))) {
        return (function () {
            translate(vector(0,1,0));
            (function () {
                push()
                return (function (r) {
                    pop()
                    return r
                }((function () {
                    scale(vector(0.1,1,0.1))
                    return draw_cube()
                })()))})();
        scale(vector(0.8,0.8,0.8));
        (function () {
            push()
            return (function (r) {
                pop()
                return r
            }((function () {
                rotate(vector(0,0,25))
                return render((n - 1))
            })()))})()
        return (function () {
            push()
            return (function (r) {
                pop()
                return r
            }((function () {
                rotate(vector(0,0,-25))
                return render((n - 1))
            })()))})()})()}};

every_frame_impl(function () {
    return (function () {
        push()
        return (function (r) {
            pop()
            return r
        }((function () {
            translate(vector(0,-3,0))
            return render(8)
        })()))})()})

Then all that’s needed are definitions for all the fluxus 3D graphics calls – the great thing is that these are also written in Scheme, right down to the low level WebGL stuff, so the only Javascript code needed is half of the compiler (eventually this also can be replaced). I was quite surprised at how easy this is, although it is greatly helped by the similarity of the two languages.

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…