Implementing Function Calls

I've been busy lately adding the concept of function calls to my H2D2 programming language. It hasn't been as hard as I thought, but there has been a reasonable amount of code to write. I have added the notion of scope as well, so that when a function returns, any local variables go out of scope and the H2D2 virtual machine can free the memory allocated to them. Currently, functions can return a value (although it's possible in H2D2 to return nothing from a function too) ... but I can't yet pass parameters to functions, that's on my TODO list, I'll work on that next.

So here is the current test program that I'm using to see if it all works:

test()
loop(s=48)
  print 10
  print 13
  print s
  print 32
  x=test()
repeat (s=s+1 if s<58)
print x
return

function test()
  loop (s=65)
    print s
  repeat (s=s+1 if s<91)
return 42

This program simply outputs some ASCII characters, the result comes out like this:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
0 ABCDEFGHIJKLMNOPQRSTUVWXYZ
1 ABCDEFGHIJKLMNOPQRSTUVWXYZ
2 ABCDEFGHIJKLMNOPQRSTUVWXYZ
3 ABCDEFGHIJKLMNOPQRSTUVWXYZ
4 ABCDEFGHIJKLMNOPQRSTUVWXYZ
5 ABCDEFGHIJKLMNOPQRSTUVWXYZ
6 ABCDEFGHIJKLMNOPQRSTUVWXYZ
7 ABCDEFGHIJKLMNOPQRSTUVWXYZ
8 ABCDEFGHIJKLMNOPQRSTUVWXYZ
9 ABCDEFGHIJKLMNOPQRSTUVWXYZ*

Simple stuff, but it demonstrates calling the "test()" function like a statement (ignoring the return value) and also assigns its return value to a variable too. I have also done some work allowing this type of code to be written out as labelled bracket notation. Essentially I'm treating each function like a seperate program, starting with its own root node, and then each call to that function simply points to the correct root node. This is how the above program looks if I render the labelled bracket notation generated from the bytecode:

Currently, when I parse the source code, I simply scan for function definitions and emit the code for them and then go back to a 'bootstrap' node which is the programs entry point. The starting point of the source code is pointed to from the 'bootstrap' node. It seems to work fine, and it means that programs always execute from node zero (which I'm making sure is always the bootstrap node).

In other news, I compiled H2D2 as a Windows dll, and used Interoperability to call it from C#, this worked a treat and was extremely fast. With the dll version, any output that the H2D2 program creates is returned as a pointer to a string, so after the program has been run the C# code needs to make an additional call the dll and tell it to free the string containing the output. But, my mandelbrot test program runs in about 200ms this way, since it doesn't have to muck about with writing to the screen. Once the C# program has all the output it can write it in one go rather than a character at a time, which is much quicker.

Now that I have installed Visual Studio 2012 I might be able to hide H2D2 behind a websocket interface. This should allow for a 'chatty' interface to H2D2 where you can ask it to run programs and get the results returned. This is also on my TODO list :-)

H2D2: Something to do with Pi

After having success with moving running H2D2 programs between platforms, I wanted to try running H2D2 on the Raspberry Pi. I was pretty confident that it would work, having already compiled H2D2 from source on Debian on another machine. What I wanted to do this time was run some H2D2 code on the Raspberry Pi and then transplant the program to Windows and allow the code to run to completion. So here goes:

...well that seems to work OK. But that was pretty much expected. You can see that I ran the demo code for 500ms this time. But the real trick is to see if the file which has been generated is binary compatible with other platforms. If I move the output file to my Windows machine, will the H2D2 program continue exactly where it left off? Drum roll please.

Yay! After putting all that effort in it's nice to know that H2D2 bytecode is Raspberry Pi compatible, I hope that it goes a long way towards my efforts at crossplatformness. Of course, this also means that I have a means to fork a running program, since I could go back to the file that I copied off the Raspberry Pi and start again from that exact point as many times as I like.

...umm and I also need to write a different example program, all these mandelbrots are starting to get boring again. Trouble is, it is quite a good piece of test code. Anyway, I'm off to implement number arrays in H2D2 now.

Running H2D2 cross platform

So one of my goals in developing DALIS/H2D2 was to make it possible to run a single instance of a program on multiple platforms. Since the H2D2 virtual machine can run code for a timeslice and then persist the entire state of the running program, it should be possible to put an executing H2D2 program into hibernation, move it to a different platform (ie a machine with an entirely different type of OS or processor) and then carry on running the same program. No matter what point the program was frozen at, the code should be able to carry on where it left off.

Well I've now gotten to the point where I can test that theory. The first experiment is to run a program on Windows for a few milliseconds and then complete the execution on Linux. To make this work I needed to make sure that all my data was persisted in sizes that are the same on different platforms, so I need to use int32_t instead of int, that type of thing. Since I've written my code in a cross-platform way and since I'm using data sizes that will be the same on different platforms everything should just work. So here we go, I'm running my mandelbrot program on Windows for 200ms:

...so that outputs a file called 'demo.hby' which is the H2D2 bytecode including its persisted state (all the program instructions, the call and data stacks and the values of all variables). Now I need to move that file to my Linux box and run the code from where it stopped. On the Linux machine I have already compiled the H2D2 virtual machine from source using GCC of course. Here goes:

Awesome! It works! I guess it's not much more than a neat trick at the moment, but I think it's an achievement of sorts. If you had some kind of long running process, it might be handy to be able to wake it, run it on whatever machine was available, and then put it back into hibernation. Okay, you can't start re-writing all your business logic in H2D2 just yet... but it's early days. This is why I always imagined DALIS / H2D2 to be a cloud based language, where you don't care what type of platform or processor is being used from one moment to the next.

So the next obvious experiment is to do the same thing, but on the Raspberry Pi... maybe I'll do it in reverse, by starting the program on the Raspberry Pi and then finishing it on Windows.

H2D2 running on Linux

Well, I tried running my H2D2 programming language / virtual machine thingy on the Fez Panda II by means of RLP, but I wasn't successful. Alas, the amount of memory left for running native code is not big enough for it. If I was really brave I could use the board as a native ARM development board I think, but I'd rather do other stuff...

Speaking of which, I've gotten round to hacking up a makefile for H2D2 so I can compile it on Linux with GCC. It was easy really, I've just created the simplest makefile you can imagine. But here is my usual victory dance running on Debian Squeeze emulated in VirtualBox:

Which is awesome, and 440 milliseconds is rather quick - especially because it's running in an emulator. I also tried it on the machine I built from an Intel D410PT motherboard and it managed to do it in 400ms flat. These rather unscientific benchmarks seem to indicate that GCC on Linux is more efficient than Pelles C generating code for Windows.

So I guess the only logical step now is to compile it on the Raspberry Pi. It would be rude not to.

Compiling the H2D2 programming language for AVR micros

I've been trying to make my latest attempt at writing a programming language (which I'm currently calling H2D2) as portable as possible. So I decided to try and recompile it for AVR microprocessors using WinAVR. It worked fine with just some very minor tweaks (and the odd bug fix). So here's a simple H2D2 program running on a (simulated) AVR microprocessor:

Specifically, it's a simulated ATmega128 running inside VMLAB. The program just writes out a series of ASCII characters in a loop, like this:

loop
  loop (c=65)
    print c
  repeat (c=c+1 if c<91)
repeat

There have also been some more improvements to the syntax, where I'm continuing to draw on DALIS for inspiration. This time round I seem to be making more use of brackets. More things are coming out looking like C functions, which is why we have loop() and repeat(). I'll probably enforce brackets with if() as well I expect.

Currently, the microprocessor is parsing the source code, generating the syntax tree (i.e. compiling to H2D2 bytecode) and then running it in the H2D2 Virtual Machine. It might be better to just have the VM on a microprocessor and somehow get the bytecode onto the device pre-compiled.

But at least this microprocessor example demonstrates that my C code is reasonably portable, hopefully I can keep it like this. In reality running a Virtual Machine on top of a small microprocessor might not be very practical, but I'm just trying to make sure that my code can target other devices really...

I'm tempted to try running this code on my Fez Panda II by means of RLP, which should allow me to run H2D2 as native ARM code (being called from inside the .Net Micro Framework), that might have to be tried out.

Speed testing the son of DALIS

So I did some timings with H2D2 (which is written in C) versus my original proof of concept, DALIS, which was written in C#. It isn't a comparison of the speed of C programs compared to .Net ones, because H2D2 is written totally differently - there's no parsing of source code going on when I'm running my H2D2 code for example. So I'm not trying to prove the .Net framework is slow, I'm just trying to compare DALIS with its offspring. Plus I've been more careful writing H2D2 because I have already proved the theory, this time I'd like to take my time, so the code is hopefully more efficient.

Having said that, I know that I could further optimise H2D2 if I wanted to. I've already gotten a few ideas to make loops faster, and there's still some debugging code that I could remove yet.

But I was shocked when I used my Mandelbrot set drawing program as a benchmark. Running DALIS from the command line, it took 11.8 seconds to draw the ASCII Mandelbrot set. Doing exactly the same thing in H2D2 took just 650 milliseconds. Wow. That's a big difference. It was worth the rewrite.

What I'd like to do now is take a single H2D2 program - one that I have compiled to bytecode - and run it for a timeslice on Windows and then execute the remainder of the program on Linux. I would like to prove that will work. Even better if I can do it on the Raspberry Pi... because then it will demonstrate different OSes and different processor types. Let's see what happens...

I don't know if there are many practical uses for sharing programs between devices and operating systems whilst they're actually being executed, but it seems like a neat trick anyway.

More work on H2D2

Since I've been writing the parser for H2D2 - the continuation of my work on DALIS, I thought that it might be useful to see the syntax trees that are being generated. So I found a nifty tool called phpSyntaxTree which is a website that will draw a graphical version of a tree from bracketed notation.

So I added some code to H2D2 which will output the syntax tree created by the parser in bracketed notation, and now I can paste the resulting text into phpSyntaxTree and see what the results look like.

Whilst the H2D2 language doesn't have much of a syntax yet, I have been able to parse things like this example code:

an = 99
PRINT an
mynum = 88
PRINT mynum
PRINT 1 + 2*3
IF 1 PRINT 1 PRINT 0
PRINT (1+2)*3

That program tests the majority of things that I have written so far, simple things like branching, expression parsing and assigning numeric variables. This is how that program comes out:

You can see the difference between the two expressions, one with brackets and the other without, and when I run the program, the first result is 7 and the second result is 9, so it seems to be working fine. When H2D2 programs are executed I'm using a non-recursive algorithm, which means that the code can be frozen at any point and then resumed - even if the code was part way through evaluating an expression there's no problem in carrying on exactly where the code was paused. So far I've only tested all this in Pelles C on Windows, but I will put a quick makefile together soon so that I can compile it with GCC (on linux), I want to keep the C code for H2D2 as portable as I can. The next thing that I'm going to try and build is a loop, which is kinda important.

DALIS Reloaded: H2D2

I've recently been thinking that my DALIS programming language may have gone as far as I'm prepared to take it in its current incarnation. It was only supposed to be a proof of concept, so I probably went way past that stage some time ago. But some of the most recent features have been hard to implement because of decisions (and shortcuts) which I made at the start. Also, I've learned more about programming language implementation now, so I'd like to go back and change some things.

And since I've had the Raspberry Pi I've been reminded how much I really like programming in C, so I've decided that this time round I'll do the language in C and try to make it portable. I suppose there's an outside chance it may fit on a small microprocessor like one of the AVR ATMegas that I have lying around.

So... I've started again from scratch, bringing with me the things I learned from the DALIS proof of concept. This time round I'm not sure if I'll stick to the same syntax as the original DALIS or not. In my head the codename for this new language is H2D2.

Because the re-write is in C I'm hopeful that it will be easier to port and that it will be somewhat faster - even if speed isn't one of my main aims. At some point you *know* I'm going to render the Mandelbrot set as a benchmark don't you... be warned :-)

But many of the original ideas from DALIS are coming with me, programs should be able to be paused and resumed, and a paused program should be capable of being serialised before being restarted. This should allow me to continue running H2D2 programs on the cloud.

This time I'm going to generate syntax trees - my current thinking is that the source code can generate a syntax tree, and what I'm really building is a Virtual Machine which is capable of executing the syntax tree directly. The virtual machine can save the running state (the stack and the value of all variables) after any instruction which could become a resume point. The original DALIS didn't use syntax trees, it interpreted one line of source code at a time and used recursive functions to parse expressions. My new approach means that running a program won't need to keep parsing the source code, which will hopefully be more efficient.

So I've started all this from an empty project in the Pelles C IDE. I've not used any non-standard libraries, and I've written my own implementations of things like the stack and the tree traversal algorithm. So far I've implemented instructions like IF, ELSE, ADD, SUBTRACT, MULTIPLY, as well as something that will print an integer on the screen (which will eventually become PRINT or WRITE or whatever I call it). I can't assign variables yet though (but constant number values can be coded in the H2D2 source).

So currently I'm building the parser to see if I can construct the syntax trees from little bits of H2D2 source code. It's looking positive, I have some simple programs running, evaluating expressions and printing results, that type of thing. I've even been able to save a running program to disk and then resume the same program afterwards, which is cool.

The next big step has to be assigning variables because then I'll be able to try some more interesting stuff...

A trivial Neural Network in DALIS

Recently I've been working on adding arrays and functions to my DALIS programming language. To test this stuff out I decided to write a very simple Artificial Neural Network. I've hard-coded the weights between a 5 neuron feed-forward 3 layer network. It's a classic XOR example with 2 inputs and one output. The output should be 1 if the two inputs are different, otherwise the output will be zero. This is the output from the program:

Trivial Neural Network Example
Input 0,0 Output 1 is: 0
Input 1,0 Output 1 is: 1
Input 0,1 Output 1 is: 1
Input 1,1 Output 1 is: 0

...and this is the DALIS source code that I used:

:<b>Trivial Neural Network Example</b><br/>
ann(a=0, b=0)
ann(a=1, b=0)
ann(a=0, b=1)
ann(a=1, b=1)

FUNCTION ann()
  sizeL1=2, sizeL2=2, sizeL3=1
  L1[sizeL1]=0, L2[sizeL2]=0, L3[sizeL3]=0
  W2[sizeL1*sizeL2]=0, W3[sizeL2*sizeL3]=0
  W2[1]=2, W2[2]=-1, W2[3]=-1, W2[4]=2
  W3[1]=2, W3[2]=2

  L1[1]=a, L1[2]=b
  WRITE "Input "+TEXT(a,0)+","+TEXT(b,0)

  LOOP j=1, size = sizeL2
    LOOP i=1
      w=weightindex(b=i,f=j,s=size)
      L2[j] = L2[j] + L1[i] * W2[w]
    REPEAT i=i+1 IF i<=sizeL1
    L2[j]=output(x=L2[j], threshold=2)
  REPEAT j=j+1 IF j<=sizeL2

  LOOP j=1, size=sizeL3
    LOOP i=1
      w=weightindex(b=i,f=j,s=size)
      L3[j] = L3[j] + L2[i] * W3[w]
    REPEAT i=i+1 IF i<=sizeL2
    L3[j]=output(x=L3[j], threshold=2)
    WRITE " Output "+TEXT(j,0)+" is: "+TEXT(L3[j],0)+EOL
  REPEAT j=j+1 IF j<=sizeL3

VALUE = 0

FUNCTION weightindex()
VALUE = (f*s)+b-s

FUNCTION output()
  IF x>=threshold
    retval=1
  OTHERWISE
    retval=0
  END
VALUE = retval

So I'm now starting to think about genetic programming in DALIS, there's no real reason why DALIS programs couldn't write other DALIS programs and run them by posting them to the server.

A load balancer written in DALIS

I mentioned to a friend of mine that I wanted to slap together a quick load balancer to demonstrate that DALIS programs can bounce between different servers without the need for any shared state. Being able to do that was my original aim for writing a cloud based language, and a demo showing DALIS in action would be nice to have. Of course, I had intended to simply extend my C# webserver example and make a simple load-balancer out of that. But my friend happened to say “why don’t you write the load balancer in DALIS?”. Damn him, putting ideas in my head like that. Still I got my own back when I showed him the Esoteric Programming Languages site and he spent way too much time reading it :-) So ... here is my (very simple) load balancer written in DALIS:

TRANSPARENT
IF ISASSIGNED("arg0")
   IF (RANDOM >= 0.5)
      newUrl = REPLACE arg0, "DALIS", "DALIS1"
   OTHERWISE
      newUrl = REPLACE arg0, "DALIS", "DALIS2"
   END
   IF ISASSIGNED("arg1")
      newUrl = REPLACE newUrl, "balance", arg1
   END
   IF RAWCONTENT = ""
      WRITE WEBGET newUrl
   OTHERWISE
      WRITE WEBPOST newUrl, RAWCONTENT
   END
END

I had to add a few new things to the language to make this work (it is great when you’re the boss of the programming language and you can add whatever you like):

  • RANDOM – generate a pseudo random number between 0.0 and 1.0
  • RAWCONTENT – allows your program to access the data in the raw http request
  • TRANSPARENT – tells DALIS that you don’t want it to add anything to the output
  • WEBPOST – does an http POST with the data you specify
  • REPLACE – replace a value in some text with some new value

Anyway, this seems to work a treat, it means that you can run 3 separate DALIS servers (called DALIS, DALIS1 and DALIS2 in this example), one being the load-balancer, along with two others. You can then run a DALIS program via the load-balancer and it will route it randomly to one of the other two DALIS servers. Using the TRANSPARENT keyword in the load-balancer code is critical, since it allows stuff to simply pass through without any interference.

The trouble is, I’m actually starting to enjoy programming in DALIS now. What have I done?