Introducing MUPLEx

I've been taking one of Dan Grossman's courses on programming languages and it was one of the most illuminating I've ever taken. While teaching, he used a made up programming language called MUPL. This MUPL had higher order functions, pairs, conditionals and the addition operation - this is the bare minimum with which you can teach how to build interpreters but also enough on which you can further build a high level functional language.

MUPLEx is basically an extensions of MUPL. It adds some syntactic sugar as well as new features. Here's a list:

• Functions with an arbitrary number of arguments
• Currying by default
• Mutability - yes, I know mutability is the source of all evil (most of it, at least) but in some cases it makes sense, like having lazy evaluation or memoization
• Records - to be able to build meaningful data structures
• More math operations
• Letrec - the equivalent of forward declaration in C (this way you can have mutually recursive functions, or other useful constructs)
• Cond - syntactic sugar for nested conditionals
• Lists - syntactic sugar for nested pairs
• A way to print out stuff
• Booleans

It also has some primitive type checking to catch some errors as you type. But, unfortunately, at this stage the errors are not too explicit.

I can't include the interpreter in this post because it's a pretty hefty beast, but I can point you to the github HTML preview thingie or directly to the repository.
*the preview may not work in Chrome/Safary

Spring updates, RU invades the GPU

Spring has come! (for most at least, Sweden is actually a bit behind). So here's some spring news:

Firstly, I've updated the stochastic optimization framework. The plugin system is now fully functional - yes, you can pack your favourite algorithm into a .jar, drop it in the plug-ins folder and see how it performs. The usual bug fixes here and there also come with this update.

Secondly, I've updated and shared Particle48 on github. It's a particle systems library (for JS & the HTML5 canvas) I made a while ago for use at LD events (and I've actually used it in Homo Vermes). I expect to update it before every LD compo and add new types of particles. If I get fellow ludumers to contribute, things will really start rolling.

And last but not least, OCLEx got 2 new additions: 1. a simple demo to the bundle to show how to set things up to start doing some image manipulation on the GPU and 2. RU on the GPU - this basically means that every Executor is a separate "process" running on the GPU and doing its duty. It started as an experiment to see how one would simulate a MIMD architecture in a SIMD environment and then got disguised in a nice RU uniform. Early OpenCL capable video cards have terrible performance penalties if the kernels are not executing the same instruction. This is a big bummer if you have any sorts of branches in the kernels. With this simulation you don't get any performance penalties (everything runs slower, but it's independent of the instructions the kernels are executing). I'll come back with more details after I do some more work and prettify it. In the mean time you can find it here.

The screenshot looks like that not because it's a work in progress but because it uses the GL_UGLY texture filter.

Return of the Four Fours

In an attempt to get faster results for the four fours problem mentioned earlier, I've come up with a simpler algorithm that does even more number crunching but somehow computes the precious list faster. Despite being sillier because it computes the same thing twice (or even worse), it'll use waaay less memory.
Oh, and since the algorithm encodes the solutions as stacks of operations, it'll print them accordingly (in reverse polish notation).

I want to see all three four five six seven ones twos threes fours fives sixes sevens eights nines tens

Four fours

The "Four fours" problem has probably wasted many people's time... As I recently rediscovered the fun in solving this, but I didn't have the patience to figure out how to get more than 2 or 3 values, I started writing a program for it instead. Supposedly, computers are better at number crunching.

It takes about 2 15 seconds to compute five fours on my super-speedy 1.0 GHz AMD not-even-sure-it's-Turing-complete thing. However, trying with seven fours is only for the brave and the patient. The algorithm stores partial results in some huge matrix to reduce computation time, but I have a feeling that this has consequences (especially in JavaScript).

I want to see all three four five six seven ones twos threes fours fives sixes sevens eights nines tens

The long journey from character to AST... begins elsewhere

Since we're in full compiler-compiler season I thought it would be appropriate for me to also provide a more educational example. This example illustrates how a very rudimentary* compiler works. In more detail, it shows what happens to your code after it's been chopped into nice tokens. Then, it shows how, based on these tokens and the language's grammar an AST is built and then decorated and, finally, how this tree is fed to an interpreter and results start popping up.

By rudimentary I mean that the language consists of simple arithmetic expressions. Below, you can find the compiler-demo. Just type stuff and be amazed!

If you want to find out more about the inner workings of this nifty thing, check this very nicely written article on CodeProject.

Your input code:
7 + pi * (x - 10)
The environment:
{ "x" : 5, "pi" : 3 }
Output:

Melc

Every life form wants to live, naturally, but as our lifespan is limited the next best thing we can do is making sure our species survives. This applies to programmers too, as a species. For some time I've been haunted by the thought that I'll never be a real programmer until I write a compiler and the species metaphor I've come up with 5 minutes ago made a lot of sense. Joking aside, now I'm going to present Melc, a compiler-compiler.

Melc is a compiler-compiler or compiler generator that builds a recursive descent parser corresponding to whatever grammar it's been given. The grammar is written in SEBNF, which is a variation on EBNF. The specification including some examples is available on GitHub. I'm going to go on developing this and writing more examples in the year to come.

Petri dish party

Here's a seak peek of what I'm working on