Saturday, May 17, 2014

Boodew: a very small functional language in 250 lines of c++

I just published a very small language called "boodew" that you can find here:
https://github.com/bsegovia/boodew

The basic idea of it and its implementation is to have something as powerful and small as possible. As said in the readme, this is a variant of the scripting language used in sauerbraten (http://sauerbraten.org) and tesseract (http://tesseract.gg)

The basic idea is to rely only on string evaluation and string substitution prior to its evaluation. This leads to very good and simple patterns very similar to what Lisp can offer with lists.

Simple imperative example

Let's look at a very simple imperative example:

Here we simply write a loop that iterates 16 times and print something for the first 8 iterations. This line is one expression.
  • The first argument always defines the function or the builtin to call here "loop".
  • The next argument is the loop variable and the next one is the maximum loop counter. This loop goes from 0 to 15.
The last element enclosed in brackets in the expression to execute. Brackets mean that the expression evaluation is not done when parsing the loop expression but when loop builtin will decide to execute it. Let's break it into pieces:
  • "?" defines a condition statement made of the condition which is executed before "?" is run, the "then" expression and an optional "else" expression
  • "(< ($ i) 8)" is comparison. Here we use "$" that looks up a variable and replaces it by its value
  • The two last statements are the "then" expression and the "else" one. Note that loops support classical break and continue

Function definition and function call

Consider this example:

As you see, you define a function and use it. The function by itself is no more than a string i.e. a "[...]" expression. Calling it consists in looking up the function variable i.e. its string and to evaluate it. This example also shows a simple usage of dynamic scoping where the function can access the local variables of its caller(s). 

Function arguments are easy since they are just regular variables created on the fly by the interpreter. Consider this example:
We define a function called "fn" that implicitly has one argument. This argument can fetched by its name "0" using the regular "$" builtin. Extra arguments will be called "1", "2"...
This example will therefore print "boum"

String substitution

Look at the other example:

Here we use operator "@". This operator forces the evaluation inside a nested "[]" expression. Therefore "int ($ i)" will be evaluated just before echo is executed. Since i equals 4, echo will output "hop4"

Note that "@" also works as an escape character and can therefore be used to delay the string expansion. Consider this example:
It will print "[hop@($ i)]" since the first "@" will prevent the evaluation of the second "@". After the expansion, the "@" expression can then be evaluated as above.

Higher order programming

Function declaration and string substitution are enough to define a real functional language.

For example, consider this small code:

It defines a function currying function i.e. a function that partially applies arguments to another function, similar to what ML languages do or what you can do with std::bind in c++.
Let's examine it:

  • first, we define our higher-order bind function. As the rest in boodew, this is just a string. The basic idea of it is given a function (its first argument) and the argument to apply (its second argument), we build a new string that will define a function where the first argument is applied. To do so, we use operator "@". Note that we use the "double" version of it here, since we need to delay its evaluation once.
  • secondly, we use operator "^"  which is the identity function that simply returns its argument. That makes sense since the argument is a string i.e. this is the function we want to create. 
  • Both "^" and "@" can define a function of functions since "^" will return a string modified by the later application of "@"
  • We then apply this operator on builtin "+" applying the argument "2" and we create a new function (i.e. still a string) out of it
  • We finally call this function. Nothing special here. This is a regular function
Note that we could be even more brutal with this concept by making partial evaluation lazy. Using more operator "@", we can make the application both partial and lazy by letting the final evaluation being done at call time. Anything is possible since we just assemble strings.

What next

Boodew is a very simple but pretty powerful language at least compared to its size (250 line of c++ code). Right now, the number of builtins is limited but it is really easy to add more. Also, there is no real boodew context: everything is global. The first implementation aimed at being really small and straight to the point. Interesting addition (apart from more builtins and a stronger implementation) would be the addition of user data similarly to what other scripting languages do. This could offer more powerful constructs in particular if they embed a "to_string" method :-)

No comments: