Monday, February 06, 2006


Why "Flan"?

For my university dissertation, I designed and implemented an experimental programming language. (Funny, but all my personal projects seem to end up implementing a language of some kind.)

Its main experimental feature was an unusual way for lists to work. The idea: what if every primitive value was effectively a single-element list, and the only way you had to combine them was concatenation via the comma operator?

a = 1 // the list [1]
b = 2,3,4 // the list [2,3,4]
c = a,b // the list [1,2,3,4]

There's one immediately obvious consequence: there's no way, syntactically, to express lists of lists. In a fit of cute, I called the language Flatlang, because all its lists were flat.
(In case you're wondering: lists of pointers to lists were legal. So in a sense, C works the same way.)

Flan, my spiritual successor to Flatlang, retains this concept as the core of the language, but unlike its predecessor, it actually (I hope to show) it makes this a useful feature. (In Flatlang it wasn't, really. The rest of the language didn't really harmonize with it; in my dissertation I called it a gimmick.)

To demonstrate the power of the flat list, I'm going to have to introduce some other features first. They're pretty cool, though, so I don't think you'll get bored.

@mylist = 1,2,3,2,1;

Oh, ok, this bit's not especially cool.
Not much to say here - I'm simply declaring that the identifier "mylist" corresponds to the list [1,2,3,2,1]. Recall that the @ prefix is my syntax for declaring a new identifier.

print(each in mylist);

This prints 12321. The "" operator is very powerful. It's derived from an idea in Jonathan Blow's language Lerp; essentially, it wraps an expression in a C#-style "foreach" loop. So this could be rewritten as:

foreach @x in mylist
..print( x );

(This is Flan, not C#, so when we declare a loop variable we use the @ syntax.)
There's more to come...

print(1 + each in mylist);

Now we're starting to get somewhere! The above prints 23432. It's equivalent to writing:

foreach @x in mylist
..print( 1+x );

Yes, that's a simple and (more importantly) natural syntax for map. (I mean the function, not the data structure). I think the unnaturalness of many higher-level functions is one of the key obstacles to the mainstream acceptance of languages like Lisp or Haskell. There's no question that map expresses an abstraction of something that we do all the time... but every time I do it, I have to rearrange what's in my head to match how map makes me express it.
With the syntax above, I can simply write down what I want to do.

So far all we've done is transform the individual items in a list. In the real world we're going to need the ability to operate on the whole list. Come up here and take a bow, sum:

print( sum( mylist ));

Not much to say there. sum takes a list, adds up its elements, and returns the total. This prints 9.

print( sum( 1+each in mylist ) );

And this prints... 23432 again? Oops. Well, every language has its gotchas.
Why does this happen? Let's do the rearranging thing:

foreach @x in mylist

Huh... when I said that "each" wraps a foreach loop around the whole statement, I really did mean the whole statement. We're calling sum five times, and passing it one number at a time. To control this we're going to need a bit more new syntax...

print( sum #( 1+each in mylist ));

There we go! This prints 14 as expected.
# means, essentially, "put the foreach loop here". It collects up an "each" loop into a list, so that the code outside can treat it as a whole. I'd prefer to use an english term that captured this (all?), but I don't think a clear one exists.
It's also not obvious how to rearrange this example. The nicest way to express it without using # or map is probably:

@temp = _; // temp is the empty list
foreach( @x in mylist )
..temp = temp,1+x; // append to temp
print( sum( temp ));

Anyway, one more new feature...

print( x*x foreach @x in mylist );

This prints the square of each number; 14941. This one can be rearranged to:

foreach( @x in mylist )
..print( x*x );

Or if you prefer, it can also be rearranged to

print(x*x) foreach @x in mylist;

Until now the "foreach" statements I've shown you have been laid out like a C# foreach loop, but Flan allows them to be rearranged to whatever feels more natural - much like if statements in perl.

Phew. Ok, I know I said I'd explain the advantage of flat lists, but I think this is enough for one post.
Thanks for reading; join me next time when I cover accumulate, and explain why flat lists are cool.

If you're interested, why not try these exercises? Then post a comment to let me know what I've failed to explain...

1) Print each number in mylist multiplied by 100.
2) Print each number in mylist divided by 2. (use the / operator.)
3) Print the sum of squares of the numbers in mylist. (i.e. 1*1 + 2*2 + 3*3 + 2*2 + 1*1.)
4) Print the length of mylist.
5) Generate a "stuttering" version of mylist, with each element repeated: [1,1,2,2,3,3,2,2,1,1].
(Recall that I defined the comma operator to mean "concatenate".)

Answers: (highlight to read)
1) print( 100*each in mylist );

2) print( (each in mylist)/2 );

3) print( sum#( x*x foreach @x in mylist ));

4) print( sum#( 1 foreach in mylist ));

5) x,x foreach @x in mylist;

This page is powered by Blogger. Isn't yours?