Darth Vader, Darth Sidious, Darth Ternal, Darth…

Darth Vader, Darth Sidious, Darth Ternal, Darth Trovert, Darth Spector, Darth Guinal.

Have I mentioned lately that I really like working…

Have I mentioned lately that I really like working with Qt? I really like working with Qt.

Prototype for the bicolor LED Arduino shield some…

Prototype for the bicolor LED Arduino shield some lucky @AberCompSci freshers will be getting. There are others… http://t.co/FL2I8xeEH8

ByUUnhMCQAAZp7d

“@AcademicsSay: The importance of stupidity. http:…

@AcademicsSay: The importance of stupidity. http://t.co/sCadCUAgoY” Utter genius.

BpeYjR0IEAANQjg

Aaaaaghhh too many things to do!

Aaaaaghhh too many things to do!

Just saw @squarecircus tremendous aerialist/acroba…

Just saw @squarecircus tremendous aerialist/acrobat/dance piece “Rime” in probably the best weather – as close to stormy as was safe! Wow!

Come on Geraint!

Come on Geraint!

Just finished The Rhesus Chart. Sadface.

Just finished The Rhesus Chart. Sadface.

Watching the BBC coverage of Biffy Clyro at T. Som…

Watching the BBC coverage of Biffy Clyro at T. Someone holds up a sign saying “I’m OK Gran.” We like to think it’s Prince William.

A little bit of Angort

Those of you who know me will know that I have a tendency to expand all my projects until they contain a crap programming language. It’s just common sense – I like my stuff to be infinitely reconfigurable, and the only way to guarantee the “infinite” part is to make it Turing-complete.

Also, programming languages fascinate me, and I don’t trust them. How does garbage collection work exactly? How does lexical closure work? As an old-school low-level programmer, I had to have answers to these questions before I could work in the languages with these facilities. So one on-going project over the last couple of years has been Angort, a language which does those things.

In fact, I wrote the code for my final year project in Angort. I kept thinking this was silly, and tried to write it in C or C++ a few times, but it got really messy. It was so much easier in Angort.

What Angort does

  • Fully garbage collected: minor garbage collection works by reference counting, while major garbage collection checks for cycles. If it’s good enough for Python, it’s good enough for me.
  • Functions are first-class objects.
  • Full lexical closure and anonymous functions.
  • A fair few functional programming facilities.
  • Hash tables and lists.
  • Plugins are written as shared libraries.
  • No dependencies (although the command line interpreter won’t be fun without GNU readline, and the optional plugins, provided as examples of what can be done, do need various libraries)
  • Pretty small executable – about 200K

What Angort doesn’t do

Parsing is boring (and I’d already written an earlier language, Lana, with lots of syntax), so Angort has a very simple – almost nonexistent – parser, in that 90% of the time each token encountered is directly compiled to an instruction. Angort is therefore a postfix language, rather like Forth or Postscript. This has disadvantages: notably that bugs are pretty easy to write, and code can be hard to read unless you’re used to it. But it does have some advantages too: understanding the compiler is easy, very little optimisation is required (which is good, because Angort doesn’t do any) and the code is incredibly compact.

As I said, Angort doesn’t optimise the bytecode it generates. This means you may end up writing some pretty suboptimal code, unless you’re smart – you’ll need to eliminate common subexpressions and fold your own constants.

Quick examples

Here’s a program to print the sum of all the squares of all the numbers from 1 to 100:

    0 1 101 range each {i dup* +}.

This does the following:

  • Stack the number zero
  • Stack a range from 1 to 101 (not including the 101)
  • Iterate over this range, doing:
    • stack the current item
    • duplicate it
    • multiply the top two stack items (effectively squaring)
    • add to the top item on the stack (initially the zero we put right at the start)
  • Finally, print the accumulated sum.

We could also have done it this way:

    0 1 101 range (dup *) map (+) reduce .

which works like this:

  • Stack the number zero
  • Stack a range from 1 to 101
  • map the range through the anonymous function (dup *) (which squares the number passed in) producing a list of all the squares
  • Use the functional programming technique “reduce” with the initial zero as the accumulator, the list we already have, and the anonymous function (+) to combine pairs of items
  • Print the result, which is the sum of all the items in the list.

And, of course, you can write functions. A lot of Angort is based on Forth, but Angort makes life much easier by providing straightforward parameters and local variables:

:lengthOfVector |x,y,z:|
    ?x dup *
    ?y dup * +
    ?z dup * +
    sqrt
;

The local definition block, delimited by vertical bars, describes the parameters (before the colon) and the locals (after the colon). Internally, parameters are exactly the same as locals. The only difference is that parameters are popped off the stack and stored in the variables before the function runs. We can access variables by using ?name to get a variable, and !name to store.

Values are returned from functions simply by leaving them on the stack.

 

Big example

So now I’m going to show a fairly big example. This is a graphical program, using the fairly crude interface to SDL I knocked up over the weekend. It generates about 1500 particles (little square blobs) and explodes them out from the centre of the screen at random velocities, bouncing them off the screen sides. I’ll go through it bit by bit to demonstrate the fun.

First we’ll import the SDL plugin.

`sdl library import

The `sdl stacks the symbol “sdl” – a symbol is a single-word string which is manipulated internally as an integer for efficiency – this makes hash table indexing much faster. The library word then searches for a library of that name, loads it, and then stacks a reference to the namespace created. Then import will import that namespace, so we don’t need to refer to the stuff defined inside it by putting sdl$ in front of everything.

Now we’ve got SDL loaded, we can start work. First we’ll turn full garbage collection off – normally this happens every 100000 or so instructions, but we’re going to be processing a lot of GC-able objects. This is a graphics demo, so even an imperceptible delay is undesirable. We’ll just set the autogc interval to a negative number to disable it:

-1 !autogc

Now we define a function (often called a word, after the Forth terminology) called frand. This generates a random floating pointer number from 0 to 1. The first line ends with a comment (starting with a hash). This comment is in the form of a stack picture: this commenting convention shows in brackets the stack both before and after the function is called, separated by a long dash.

:frand # (max -- random float from 0 to max)
    rand 50000 % 50000.0 / *;

The word itself takes a large random integer, finds it mod 50000, divides it by 50000 (converting to a float in the process, because it’s dividing by a float) so giving a random number from 0.0 to 1.0, and then multiplies that by the number that’s still lying around on the stack from being passed in.

Now we just define a couple of constants:

3.1415927 const PI
PI 2 * const TWOPI

Now for a couple more words. The first takes a parameter len and uses it to generate a random vector of that length:

 # return x,y on the stack - a random vector of length len
:randv |len:| TWOPI frand dup cos ?len * swap sin ?len *;

It does this by:

  • stacking a random angle from 0 to TWOPI
  • duplicating this on the stack
  • finding the cosine of the angle and multiplying it by len
  • swapping the top two stack items (so we now have the other copy of the angle on top)
  • finding the sine of the angle and multiplying it by len

so we end up with the sine and cosine of the angle, each multiplied by the length, on the top of the stack. This is probably the hairiest piece of code in the entire example, because I’m being a bit clever with the stack to get more speed.

Now we write a word to generate a random colour, in the form of a list containing three integers from 128 to 255.

First we start the word definition, this time specifying no parameters but a local variable called f. We then define an anonymous function which generates a value from 128 to 255, and store this in the local variable. Finally, we build the list by calling this anonymous function three times – ?f@ fetches the value of f (using ?f) and then runs it (using @):

# random colour
:randc |:f| 
    (rand 128 % 128+)!f
    [?f@,?f@,?f@];

The square brackets delimit a list. Actually, it’s cleverer than that – the [ word puts a new list on the stack. Then both , and ] put the topmost stack item onto the list below it on the stack, leaving the list there. There are a few little bits of hackery – the close bracket is ignored if it immediately follows an open bracket, and it also works with hash tables as we’ll see below.

Now we have the most complex piece of code. This is a function called mkthingy, which returns a new “object” which flies around the screen. This object is in the form of a hash table.

First, we start the definition. No parameters, but three local variables: this, dx and dy.

:mkthingy |:this,dx,dy|

Now the code. We generate a random number from 0 to 2, and then square it. Then we generate a random vector of that length and store the vector in dx and dy:

    2 frand dup* randv !dy !dx

Now we put a new hash on the stack, ready to add things to – but first we copy the hash reference into the this local, ready for use later. We remember to leave a copy behind on the stack so we can still add things!

    [% dup!this

Next we add the "object's" fields' initial values to the hash - this consists of stacking the key (always a symbol here) followed by the value, and using a comma operator to write to the hash. These values consist of its position at the centre of the screen (determined from the screen size globals we'll set up on initialisation) and the random vector we generated earlier, which will be the velocity. We also set a random colour using the randc function.

        `x ?Width 2/,
        `y ?Height 2/,
        `dx ?dx,
        `dy ?dy,
        `col randc,

Now we add an anonymous function to the hash. This is a method which will move the thingy by its velocity, and reflect it off the sides of the screen. Anonymous functions are delimited by parentheses and can take parameters and local variables - in this case we have the locals x and y.

       `move (|:x,y|

The first thing the function does is add the x member to the dx member and store the result in the x local.

            ?this?`x ?this?`dx + !x

A few things to note: firstly, we can get access to a value in a hash table which has been stored using a symbol key using a bit of syntactic sugar: ?`symbol. So here, ?this?`x means "get the local variable this, then get the value of x stored within it (assuming it's a hash)".
Secondly, the this local variable is defined in the context of the outer function mkthingy -  it will therefore be stored in a closure, so this anonymous function will remember its value when the outer function exits. It contains a reference to the hash itself, so this "method" always manipulates the right "object." (As an aside, this effectively makes this anonymous function akin to a C# delegate: it contains both a reference to an object and the method to call on it. Useful!) We repeat the process for the Y coordinate:

            ?this?`y ?this?`dy + !y

Now we do a little bit of maths, to check to see if the new coordinates are going to out of range next time round. If they are, we negate the appropriate component of the velocity.

            ?x ?Width > ?x 0 < or if
                ?this?`dx neg ?this!`dx
            then
            ?y ?Height > ?y 0 < or if
                ?this?`dy neg ?this!`dy
            then

The "if...then" syntax in Angort is a little odd: rather than the more traditional if (condition) then (code) endif, Angort has (condition) if (code) then.

Finally, we write the local copies of the coordinates into the hash:

            ?x ?this!`x
            ?y ?this!`y
        ),

Now we add another method, or delegate, to the hash. This one draws the item.

    `draw (

Firstly, it iterates over the colour member (which is a list) to unpack the three items (r,g,b values) onto the stack. It then calls the SDL plugin's col function, which will set those values as the foreground colour.

        ?this?`col each{i} col

Then we simply draw a 10x10 rectangle in the current foreground colour at the x,y position stored in the hash.

        ?this?`x ?this?`y 10 10 fillrect
    )

That completes the hash, and also the mkthingy function, which returns the new hash on the stack:

];

Next we come to the event handlers. First, we define what happens when a key is pressed:

(
    |x:|
    ?x "q" asc = if done then
) onkeydown

Here, we have defined an anonymous function which takes a single argument x. If this is equal to the ASCII value of “q” (for “quit”), then we call the done function in the plugin, which will end the main loop. We then call onkeydown in the plugin, which sets the callback to call when a keydown event occurs.
Similarly, we define the draw callback. This will clear the screen, move and draw all the thingies in the global list Thingies, and then flip the front and back buffers:

(
    clear
    ?Thingies each { i?`move@ i?`draw@ }
    flip
) ondraw

Note how we call the methods: i ?`move @ (to write it with spaces) will get the current hash (Thingies will be a list of hashes), fetch the `move value from it (which will be a method/delegate/closure or whatever) and call it.
Now we can initialise SDL, opening a full screen application at whatever the current resolution is:

-1 -1 fullscreenopen

We store the screen width and height (minus 10 so we don’t have to do that calculation in each move call) in globals called Width and Height:

scr width 10 - !Width
scr height 10 - !Height

Now we do a little bit of clever trickery with lists to make a list of 1500 thingies, storing it in the global Thingies:

[] 0 1500 range each {mkthingy,} !Thingies

Finally we start the main loop, and when it exits we close SDL and quit Angort:

loop close quit

Installation

Angort is available from this link here. The documentation is incomplete (in some places hilariously so), but there is some. To install it:

  • clone the repo and cd into it
  • mkdir build; cd build; cmake ..; make
  • then (if that works) run sudo make install to install Angort into /usr/local
  • if you want the plugins, make sure you have the required dependencies:
    • IO plugin has no dependencies and is probably the most useful example
    • SDL plugin (which the code described above uses) requires libsdl and libsdl-image development libraries (available as libsdl1.2-dev and libsdl-image1.2-dev packages in Ubuntu)
    • and the two plugins in MPC, which control Music Player Daemon and allow ID3 tagging of MP3 files, require libmpdclient and libtag. You probably won’t want them; I use them to control my music system.
  • to build a plugin, just cd to angort/plugins/(plugin name) and run ./build (once you’ve done the install make). This will build the plugin’s .angso file in the angort/libs directory. Running sudo make install from the angort/build directory again will install any plugins there into /usr/local/share/angort

UPDATED 23/7/14: Because of a recent language change (the self keyword for recursive anonymous function definitions), the local variable previously called self is now called this.

 

 

Copyright © Found
Jim Finnis' personal blog

Built on Notes Blog Core
Powered by WordPress