Archive for April, 2011


April 25, 2011

Trying to introduce typedef into the new Babel-17 grammar, I noticed that there was a problem with the combination of blocks and commas in the grammar. I then realized that I had hit this problem earlier but had been able to circumvent it: the memoize construct is currently used like this:

memoize a b c

and NOT like this:

memoize a, b, c

With typedef such a hack was not possible anymore, so I had to track down the cause of this problem. After hours of examining the grammar with ANTLRWorks, which is by the way one of the greatest software tools I have worked with (the up-side: now I finally completely understand the alternative display of ANTLRWorks), the problem turned out to be the block part of lambda expressions:

(x => memoize a, b)

could be understood as

((x => memoize a), b)

but also as

(x => memoize a; memoize b)

After pondering the different ways of resolving this dilemma for a while, I decided that a clean solution is to distinguish between lambda expressions that are surrounded by round brackets, and those that are not. Basically, for those that are protected by surrounding brackets, the rule is

lambda_expr_1 := pattern => block

for those that are not the rule is

lambda_expr_2 := pattern => expr

This means that the expression

(x => memoize a, b)

is now interpreted as

(x => memoize a; memoize b)

As a consequence, both memoize and private will use commas instead of just spaces as separators of their multiple arguments.



April 24, 2011

Currently the pattern

f ? p

has two different meanings, depending on whether f is a function or not. If f is not a function, then the message deconstruct_ is sent to the value to be matched, the result is applied to f, and then result of this application is matched against p.

This, so I thought, should enable pattern matching against cexprs even for values that are no cexprs.

In the light of how types are going to work in Babel-17, this does not seem to be so useful anymore. Instead of the pattern

Plus ? p

why not write directly the pattern

Plus p

All that is needed for this to work is to modify the semantics of above pattern such that code like

match v
  case Plus p => ...

leads to the result of v.deconstruct_ Plus being matched against p. Original cexprs have an obvious default implementation of deconstruct_, and other values can optionally implement it.

This is a good place to also announce another change: the pattern

match v
  case Plus => ...

will not any longer be synonym with

match v
  case (Plus nil) => ...

but instead with

match v
  case Plus _ => ...

The reason for this is that especially exception handling becomes more robust and streamlined, for example the code

  exception MyError "my bad"
case (exception MyError) => "hello"

will now result in the value "hello".

On Types, Part VII: Automatic Type Conversions

April 24, 2011

Sometimes you’d like that a value automatically transforms into a value of a certain type. For example, it would be handy if strings could turn automatically into integers when the situation demands this. For this purpose, automatic type conversions will be added to Babel-17. These automatic type conversions are triggered when matching the type pattern. For example, in the expression

match y
  case x : string => x

first we try to match y to x : string. If y is a string, this match succeeds and x is bound to y. If it isn’t, then we check if y has an automatic type conversion for string. If it does and the conversion produces no exception, then x is bound to the result of converting y. If it doesn’t or if there is an exception during conversion, then the pattern doesn’t match.

Any object ... end expression can be equipped with an automatic conversion to type sometype via

def this : sometype = ...

On Types, Part VI: Abstract Datatypes

April 24, 2011

So far we have only had examples for type definitions where outer values and inner values were the same. For abstract datatypes, this is usually not the case: the inner value determines the internal representation of the datatype, and the outer value determines how the datatype looks like to its clients.

To examine abstract datatypes in Babel-17, let us define a new type orderedSet which represents sets that are ordered by a given order:

module com.obua.util.orderedSet

private (orderedSet), ins

typedef orderedSet (leq, list) = nil

def empty leq = (leq, [])
def insert (orderedSet (leq, list), y) = (orderedSet (leq, ins (leq, list, y))
def toList (orderedSet (leq, list)) = list

def ins (leq, [], y) = [y]
def ins (leq, x::xs, y) =
    if leq (y, x) then
        if leq (x, y) then x::xs else y::x::xs end
        x::(ins (leq, xs, y))

To use this module somewhere else in our code, we first import it via

import com.obua.util.orderedSet

Now we can play around with orderedSets:

val r = empty ((x, y) => x <= y)
for i in 1 to 10 do
  r = insert r (random i)
toList r

Note that the only way for us to create values of type orderedSet is by calling empty and insert, because of the declaration private (orderedSet). Note also that there is no other way to see the elements of an orderedSet except via the toList function.

There may be other types around which also have an empty function to create empty versions of them. If we want to use these types together, it will be inconvenient to import the com.obua.util.orderedSet module. It is then more convenient to import com.obua.util and to write orderedSet.empty and orderedSet.insert. The only thing that is somewhat ugly is that now we have to refer to the type via orderedSet.orderedSet. But we can remedy this by introducing the following rule into Babel-17: if the name of a type is the same as the name of the module it is defined in, then the name of the module can be used as a synonym for the name of the type. In our case this means that the type com.obua.util.orderedSet.orderedSet is also accessible as com.obua.util.orderedSet.

We would like to add the following features to orderedSet

  1. ordered sets should be comparable in a way that makes sense; right now, the expression
    insert (empty leq, 1) == insert (empty leq, 2) evaluates to true because both values have outer value nil.

  2. Instead of insert (r, x) we just want to write r + x.
  3. Instead of toList r it should be OK to write r.list.
  4. We want to be able to write for x in r do ... end
  5. We want to be able to write
    with empty leq do 
      yield a 
      yield b 
      yield c 

We can achieve this (and much more, see section 25.8 in the Babel-17 reference) by replacing the outer value nil with an object that implements the desired functionality. Therefore we replace the line typedef orderedSet (leq, list) = nil by the following:

typedef orderedSet (leq, mylist) = object

/* 1. */
def rank_ = mylist

/* 2. */
def plus_ x = insert (this, x)

/* 3. */
def list x = mylist

/* 4. */
def iterate_ = 
    match mylist 
        case [] => () 
        case (x::xs) => (x, orderedSet (leq, xs))

/* 5. */
def collector_close_ = this
def collector_add_ x = this + x
def empty = orderedSet (leq, [])


Note that we reintroduced the keyword this into the Babel-17 language, and also note that the above code only works if this does not refer to the original object definition, but to the object definition that has been retyped as an orderedSet. Applying the same reasoning to object inheritance, we can resolve our earlier beef with this that led to the temporary removal of this from Babel-17.

On Types, Part V: Algebraic Datatypes

April 23, 2011

Let’s go a step further and try to do more with types than just simple enumerations. How about a type for binary trees?

typedef bintree (LeafNode _), (InnerNode (_, _ : bintree, _ : bintree))

Now all bintrees are wellformed binary trees. The tree

   / \
  2   3

can be created like this:

bintree (InnerNode (1, bintree (LeafNode 2), bintree (LeafNode 3)))

Note that for example the expression

bintree (InnerNode (1, 2, 3))

would result in an exception TypeError. If you prefer binary trees such that the above expression is also OK, you can define bintree like this instead:

typedef bintree (LeafNode _), (InnerNode ( _ , _ , _ ))

On Types, Part IV: Simple Enumerations

April 23, 2011

Before starting to code the module and type system of Babel-17, lets look at a few examples and see if everything works out. Lets first define the type suit:

module com.potsized.card
typedef suit Spades = Spades
typedef suit Hearts = Hearts
typedef suit Diamonds = Diamonds
typedef suit Clubs = Clubs

Somewhere in your code, in order to use the type suit, you would usually first import the module where it is defined:

import com.potsized.card

You could then write code like this:

val x = suit Spades
match x 
  case Spades => "matches Spades"
  case _ => "doesn't match Spades"

The above would evaluate to “matches Spades”. Note that if we would change the first line to

val x = Spades

the whole thing would of course still evaluate to “matches Spades”. The expression

Spades == suit Spades

evaluates to false. The expression

match Spades 
  case Spades : suit => "matches Spades : suit"
  case _ => "doesn't match Spades : suit"

evaluates to “doesn’t match Spades : suit”.

The code for the definition of the type suit is nice and clean, but a little bit verbose. Therefore we introduce two abbreviations. First,

typedef name pattern

is short for

typedef name (x as pattern) = x

where x is supposed to be fresh. Second, several typedefs referring to the same name can be contracted to a single typedef, where the various cases are separated by commas.

Taking both rules together, we can write the typedef for the type suit shorter, like this:

typedef suit Spades, Hearts, Diamonds, Clubs

RxOL and Cocina

April 23, 2011

I was looking on the internet for things that are similar to what I envision for Applied Cuisine, and I found something that made me very excited: A little book from 1985, Computerized Cooking, that has already worked out a lot of the things that I was about to research!! The author of the book, David A. Mundie, seems to have a similar background to mine (Logic in Computer Science), and when I compared his book with my private notes that I have obtained brainstorming about Applied Cuisine, the amount of overlap was uncanny. He has developed a program called Cocina which denotes recipes in a functional programming language called RxOL. The program doesn’t seem to be around anymore. Recently, the concept of RxOL has been revived by the website Cooking For Engineers, using a patent pending graphical successor of RxOL called Tabular Recipe Notation. It seems though that the site no longer uses this notation on a regular basis.

I am now convinced that my vision for Applied Cuisine is the right one, as I seem not to be the only one to have had it and acted upon it. Basically, you could say

Applied Cuisine = Cocina + 2011 .

Don’t forget to register for early access to Applied Cuisine!

On Types, Part III: typedef

April 23, 2011

So I had some time to think about if the stuff I have written previously about types in Babel-17 makes sense. I came to the conclusion that most of it does, but that I’d like to make a couple of major changes to how I described it previously. Like before, types live within modules. Unlike before, there is no (pattern) operator :>. Also, the syntax for typedef is different. Its syntax now is:

typedef name pattern = expr

You can see that a type definition via typedef looks quite a bit like a normal definition via def. The analogy stretches even further: You can have multiple definitions for the same type:

typedef name pattern_1 = expr_1
typedef name pattern_2 = expr_2
typedef name pattern_n = expr_n

The semantics of the above is that a new function name is defined which allows you to create new values of type name. This new function takes an argument x and returns a value that has type name and inner value x and outer value expr_i where i is the smallest index such that pattern_i matches x. In case no pattern matches, the exception TypeError is thrown.

Note therefore that in general a value in Babel-17 has three components: a type, an outer value, and an inner value. With respect to all messages except the rank_ message, a value behaves just like its outer value.

The type name of a value v is accessible via

typeof v

Alternatively, you can test if v has type name via the pattern

v : name

Note that types are ordinary values in Babel-17. If you have such a value t which is a type, you can test if v has type t via

v : val t

The value that denotes the type name can be obtained via

(: name)

Therefore, the following two patterns are identical:

v : name
v : val (: name)

The outer value of v is accessible only indirectly via the messages that are sent to v and handled by its outer value.
The inner value of v is directly accessible, but only in the same scope in which name has been defined, via the pattern

name x

This pattern matches if the inner value of v matches x.

To make encapsulation possible, a new statement is introduced which can be used in both module and object blocks:

private name_1, … , name_n

declares the definitions name_1, …, name_n to be private to that module or object block. Note that when name_i belongs to a type definition, the type itself is also private. To make the type itself public (= non-private), use (name_i) instead.
Finally, there is the import statement, which allows to import modules and use their non-private definitions and types without the module prefix.

There is the question left on how order is handled for our new types defined via typedef.
To allow for true encapsulation, values of a type t defined via typedef are only comparable with other values of type t. The order among values of type t is the one induced by the order among their respective outer values.

Mad World

April 22, 2011

I was just cleaning up (no, don’t worry, not Taxi Driver style :-)) my apartment. As always on these rare occasions, I enjoyed my iTunes song rotation. When I arrived at “Mad World” by Tears for Fears, I wondered why I associated so much emotion with it. Yes, the world is sometimes mad, but that couldn’t be the source of these emotions. I checked iTunes and saw that I had it as part of the “Ashes to Ashes” TV show soundtrack. But there had to be something deeper behind this, this couldn’t it be either. Finally I checked Wikipedia and discovered why this song sounded so familiar to me: a cover version of it was part of the sound track of the movie “Donnie Darko”, a pretty deep and inspirational movie. Funny how associative memory works.

Modernist Cuisine

April 19, 2011

A very interesting book is going to be available on the market soon, it is called Modernist Cuisine and will be available soon, for example at Amazon Germany for more than €400.

I guess I will get me a copy of this as the name is eerily similar to my Applied Cuisine. The intriguing thing about Modernist Cuisine is that it applies the principles of science to cooking. The goal of Applied Cuisine is to describe recipes as accurately and simply as possible so that they can be used on a daily basis in an affordable way. So it seems that Applied Cuisine can learn a lot from Modernist Cuisine and it is something I will continue to closely watch.

Edit: I found an interesting article talking about that precise methods in cooking as championed by Modernist Cuisine are nice, but that the real problem is in finding the right ingredients. I could not agree more 🙂