Archive for December, 2009

Exceptions in a functional language

December 29, 2009

Joel has really a bad opinion about exceptions.  He prefers to return errors as return values instead.

Now, most of this error value method / exceptions discussion seems to occur in the C++ world. In my design for my new, mostly functional programming language Babel-17, I would like to have exception handling built into the language. The reason is simply that explicit checking for error values creates messy code which is very hard to read.

So, what are the challenges of introducing exceptions into the language? A major source of problems is that Babel-17 supports lazy and concurrent evaluation. Look at the following code fragment:


val p = (10, lazy(exception "hello"))

val x = fst p

val y = try (if (snd p == 0) then 0 else 1 end) catch _ => 2

val q = (10, exception "hello")

val z = p == q

Here p is a pair that has as second element a lazy computation. Evaluation of this second element is delayed until its value is needed for the computation of y. Not clear are the answers to these questions:

  • Should computing the value x throw an exception, or should x just be assigned the value 10
  • Should computing the value q throw an exception, or should exceptions be allowed to be part of data structures?
  • After computing  y, should p == q hold? What about before y has been computed?

Instinctively, my answers to these questions would be:

  • computing x should not throw an exception, x will be assigned the value 10
  • Computing q should propagate the exception and not compute a pair. Exceptions in data structures are odd, and I normally do not want that.
  • q does not really exist, because its computation throws an exception. p on the other hand really exists. Also, p should not change its value depending on whether y has already been evaluated or not.

There are similar issues with concurrency:


val p = (10, concurrent(exception "hello"))

val x = fst p

One could argue that concurrency should be semantically just the identity function. Then p does not exist, because calculating p throws an exception.
One could also argue that x should evaluate to 10. This would actually be nice for the implementation of concurrency, because evaluation could then proceed in parallel.

Finally, exceptions introduce even without concurrency or laziness the question of non-determinism, if the evaluation order is not fixed:


(exception "A", exception "B")

Should this throw exception “A” or exception “B” ?

Our approach in Babel-17 is as follows: First, we introduce two new types, exceptions and errors. Exceptions can be thrown via “throw p”, where p is an arbitrary expression (note that “throw (throw p)” is legal notation, but does just the same as “throw p”). Values of type exceptions cannot be stored in data structures and propagate automatically to the top of the call stack unless they are

  • caught via try/catch
  • turned into errors by hitting a lazy/concurrent boundary from the inside

Values of type error on the other hand behave very much like normal data; what is special about error values is that they can be created only from exceptions or via the function constructor “error”. Otherwise error values can be passed around and stored in data structures just like any other data.

Lets revisit above sourcecode and see what this means:


val p = (10, lazy(exception "hello"))
/* semantically, p == (10, error "hello") */

val x = fst p
/* x == 10 */

val y = try (if (snd p == 0) then 0 else 1 end) catch _ => 2
/* y == 1, because error "hello" is not equal to 0 */

val q = (10, exception "hello")
/* results in an exception */

val z = p == q
/* will fail, because q is not even defined */

val p = (10, concurrent(exception "hello"))
/* Again, p is semantically the same as "(10, error "hello"). */

val q = (10, error "hello")

val z = p == q
/* z will evaluate to "true" */

Is (Probabilistic) Non-Determinism Pure ?

December 28, 2009

What exactly is a purely functional programming language? Here is the Wikipedia definition of a pure function:

In computer programming, a function may be described as pure if both these statements about the function hold:

  1. The function always evaluates the same result value given the same argument value(s). The function result value cannot depend on any hidden information or state that may change as program execution proceeds or between different executions of the program, nor can it depend on any external input from I/O devices.
  2. Evaluation of the result does not cause any semantically observable side effect or output, such as mutation of mutable objects or output to I/O devices.

The result value need not depend on all (or any) of the argument values. However, it must depend on nothing other than the argument values.

Note the sentence that I deleted from the original Wikipedia definition. Let us call a function that obeys all of the above definition (including the deleted sentence) strongly pure, and a function that obeys all of the above definition except maybe the deleted sentence weakly pure.

The two functions random and choice cannot be considered strongly pure. Let us look at these two functions. The meaning of “choice a b” is to return a or b. In particular, sometimes it might return a, sometimes it might return b when called. Similarly, the meaning of “random a b” is to randomly return a or b, giving both a and b equal chances of getting returned.

But can these functions be considered weakly pure ? IMHO, the answer is yes. Both functions do not exhibit any side effects, do not depend on hidden state, and do not depend on anything else than their arguments. Note that nevertheless some people might refuse to call choice or random even only weakly pure, because they will not separate the abstract semantics of a function from its practical implementation. For example, how would you implement random for a real language running on a real computer? Two real-world implementations are in use:

  1. A pseudo random number generator. The current seed of the pseudo number generator can be viewed as hidden state / additional argument, making random not even weakly pure.
  2. An extra device is used which generates random numbers based on certain physical stochastic processes. Using such a device clearly violates the “no I/O” part of weakly pure.

Weakly pure functions are not necessarily referentially transparent. What implications does this have? Two things come to mind:

  1. Caching (memoizing) a weakly pure function can change the meaning of that function. Note that while caching weakly pure functions which rely only on choice is perfectly fine (but may reduce the number of possible outcomes of this function), caching a weakly pure function which also relies on random generally changes the meaning of that function.
  2. Reasoning about weakly pure functions is harder because the application of a function cannot simply be replaced by its result.

The first issue cannot be helped; but is there any reason why it should be helped?

It seems that the second issue can be dealt with. Because if weakly pure functions do not have side effects, and do only depend on their arguments, it should be possible to replace reasoning about a weakly pure function by reasoning about an induced strongly pure function with a lifted result range. Instead of reasoning about “choice a b” one could reason about “Choice a b”, where “Choice a b” evaluates to the set “{a, b}”. And instead of reasoning about “random a b” one could reason about “Random a b” where “Random a b” evaluates to the measure “(50% : a, 50% : b)”. Of course all weakly pure functions in a functional program then need to be lifted that way, even those which were strongly pure to begin with. And because the output of one function is the input of another, not only the result range of all functions would need lifting, but also the input domain. It is not clear if this is always possible, and deserves more thought.

Note that an important aspect of strong purity is preserved even by weak purity: weakly pure functions are particularly well suited for parallelization on multi-core and distributed computers.

I Hate Monads

December 28, 2009

Every time I read a paper whose abstract mentions the term “monad” my brain shuts down. Monads? Really? IMHO, monads are there just for making something look greater and more complicated than it really is. It is funny, I wonder why I don’t feel the same about the term “group” in mathematics. Anyway. If you want me to read your paper, DO NOT MENTION MONADS!

National Heads-Up Championship, Round 1

December 24, 2009

The phlegmatic programmer just qualified for round 2 of the National Heads-Up Championship at Full-tilt. Round 1 consisted of  180 players battling for one of the two top spots. Despite the name, no heads-up so far, just ring games with 9 players. Easy cruising, no serious bad beats, and a great last hand:

Only three players are left. The phlegmatic programmer (P) has 120.000 in chips. To the left sits A with 90.000 and to the right B with 60.000 in chips. Blinds are 1200/2400. P has the button and Q J off-suit, bets 7200. A folds, B calls. Flop is Q Q 10. P bets again 7200, B calls. Turn is a 5. P pushes all-in, B insta-calls and shows pocket-fives !! River is a J. Happy Christmas, P 😀

Registering for Freerolls

December 22, 2009

These days the phlegmatic programmer participates in the National Headsup Poker Championship at Fulltilt Poker. They run lots of qualifiers. The good thing: these qualifiers are free, and they run every 3 minutes. The bad thing: there are only 180 entries in a first round qualifier, so you have to hit the button which registers you for the tournament basically as soon as it appears. Yep, these qualifier tournaments are filled within about 1 second.  Jesus.

Luckily, the phlegmatic programmer speaks Java. Here is his solution to the problem 🙂


package autoclick;

import java.awt.*;
import java.awt.event.InputEvent;

public class Main {

  public static void main(String[] args) throws Exception {
    int x = Integer.parseInt(args[0]);
    int y = Integer.parseInt(args[1]);
    Robot robot = new Robot();
    Color color = null;
    do {
      Color c = robot.getPixelColor(x, y);
      if (color == null) {
        color = c;
      } else {
        if (!color.equals(c)) {
          robot.mouseMove(x, y);
          robot.mousePress(InputEvent.BUTTON1_MASK);
          System.exit(0);
        }
      }
      try {
        Thread.sleep(1);
      } catch (Exception e) {}
    } while(true);
  }

}

Are phlegmatic programmers mostly lazy or rather eager?

December 17, 2009

While designing Babel-17 I stumbled, of course, over the question what rôle lazy evaluation has in Babel-17. Is lazy evaluation the default case, just as in Haskell? Or should eager/strict evaluation be the standard mode of evaluation, just like in Standard ML?

I already sort of had made up my mind that I would root for strict evaluation, and that lazy evaluation will only survive in the way object messaging works. This point of view is also taken by the V0.1 reference implementation of Babel-17.

But is it  phlegmatic to choose strictness over laziness?  Only if this choice is based on convincing arguments. So I again digged into the evaluation order jungle, read “lamba the ultimate” posts, watched Simon Peyton Jones videos, looked at Scalas “lazy vals” and found interesting papers about lazy and strict and “lenient” evaluation orders.

Here are the arguments often given in favor of lazy evaluation:

  1. Lazy evaluation terminates for expressions that would just diverge if evaluated strictly.
  2. Lazy evaluation gives you infinite data structures.
  3. Lazy evaluation and concurrency are a great match.
  4. Lazy evaluation lets you be imprecise about the order expressions should be evaluated, as long as there is a sensible order.
  5. Lazy evaluation is “more mathematical” than strict evaluation.
  6. Laziness keeps you pure. If you use lazy evaluation, effects are difficult to deal with, because the order in which these effects manifest is not clear; therefore you will not allow side effects at all, keeping your language pure.
  7. You need laziness to define your own custom control structures.
  8. Lazy evaluation can be much better performing than strict evaluation because expressions which do not need evaluation will not be evaluated, thereby saving the time that these useless evaluations would take.

Argument 6 seems to be rather an argument against laziness in Babel-17 because Babel-17 is supposed to support effects, in particular exceptions. Argument 3 is just not true, as it is purity which is a good fit for concurrency. Laziness is rather a handicap for concurrency, as eager evaluation of expressions in parallel might lead to non-termination for certain expressions which terminate when evaluated lazily. And while argument 8 is true in principle it is a fact that actually existing strict languages like OCaml perform much better than lazy languages like Haskell.

But arguments 1, 2, 4, 5 and 7 are truly heavy-weight arguments when pitched to a phlegmatic programmer. And although strictness and concurrency are a better match than laziness and concurrency, it is purity that is most important for concurrency, not evaluation order. So why not just use lazy evaluation in Babel-17 and forget about strict evaluation?

These are the reasons:

  • Strict evaluation is sufficient for the overwhelming majority of programs. Even programs which do need lazy evaluation do so only in a few easy to identify spots and can be evaluated strictly in the remaining majority of the program.
  • Strict evaluation can be implemented more efficiently than lazy evaluation; at least so seems practical evidence to suggest.
  • The space/time consumption of lazy programs is (much) harder to understand than the consumption of strict programs. Remember, as phlegmatic programmers we not only want to create stuff, we also want to understand it.

Here is a good example of how lazy evaluation is counter-intuitive when it comes to space consumption:


def sumlist' [] acc = acc
def sumlist' (x:xs) acc = sumlist' xs (x+acc)
def sumlist xs = sumlist' xs 0

The above code uses the well-known accumulator technique to make folding over a list tail-recursive. But beware! Lazily evaluated, the accumulator will eventually take as much space as the original list you want to sum up.

So the decision regarding evaluation order in Babel-17 is as follows: Babel-17 is strict by default. But because laziness can be so useful, it will be possible to introduce laziness in those spots where it is needed. More on this in a later post.

Pure Babel-17: Built-in Types

December 11, 2009

As you have seen in the previous post, the wish list for the features and properties of Babel-17 is quite long.

My ideas of how to combine all these different requirements are not firmly established yet, so let’s start with the easy stuff first: Pure Babel-17. Pure Babel-17 does not take the imperative features into account.

A word of warning: if later on I see that something said here or in later parts of the Babel-17 discussion does not fit together with features introduced later, I will freely edit stuff to get a consistent whole.

Like any other programming language, Babel-17 manipulates data. A unit of data is called an object. Every object has a type.

Pure Babel-17 knows the following two built-in simple types:

  • INTEGER : this is the type of all positive, zero, and negative integer numbers. Integer constants can be written down in decimal (10), binary (0b1010), hexadecimal (0xA or 0xa) and octal (0o12) notation.
  • STRING : this is the type of all legal Unicode strings. String constants are written between quotation marks (“Hello world!”). All valid unicode characters can appear between quotation marks except the backslash character, the quotation mark character, or a newline character. There are special character sequences to encode even these characters in a string.

There are four built-in composite types:

  • LIST: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] is the same as (0, 1, 2, 3, 4, 5, 6, 7, 8, 9), but [0] is a list and (0) is just another notation for 0. Also, [ ] and ( ) both denote the empty list.
  • SET : {} is the empty set, and {0, 1, 2, 3} is the same set as {0, 1, 2, 0, 3}.
  • MAP : {->} is the empty map, and {0 -> 1, 3 -> 10} is the map that sends 0 to 1 and 3 to 10.
  • TAGEXPR: If T is a tagid, and p is an object, then T p  is a TAGEXPR. A tagid starts with a capital letter and continues with capital letters, digits or underscores. For example, BABEL_17 is a tagid, but BABEL-17 is not, neither is Babel17. Just writing T also gives you a TAGEXPR; it is a synonym for T ( ) .

Furthermore there is the FUNCTION type. FUNCTION literals are written like this: x => x*x. This particular literal for example can be used as square function on integers.

There are more ways to define functions. And while these are really ALL built-in types, it IS possible to define custom types. More about both topics will be said in later posts.

Babel-17

December 9, 2009

In 1966, Samuel R. Delany published a novel called Babel-17.  Here is an excerpt from its Wiki description:

During an interstellar war one side develops a language, Babel-17, that can be used as a weapon. Learning it turns one into an unwilling traitor as it alters perception and thought. The change is made more dangerous by the language’s seductive enhancement of other abilities.

I decided that Babel-17 is a good name for my new phlegmatic programming language. There is already a first reference implementation V 0.1 out there, but before Babel-17 approaches V 1.0, many changes are bound to happen. My current vision for Babel-17 can be broken down into the following goals:

  • Babel-17 does purely functional programming.
  • Babel-17 does object-oriented programming and encapsulation.
  • Babel-17 does imperative programming.
  • Babel-17 does exceptions.
  • Babel-17 does dynamic typing.
  • Babel-17 does strict, lazy and concurrent programming.
  • The different programming paradigms it supports should be designed to integrate with each other as neatly as possible.
  • Babel-17 is based on simple concepts most easily understood by the mathematical mind.

The first goal seems to be somewhat at odds with the second goal, and totally contrary to the third goal. But I believe that object-oriented programming and purely functional programming can coexist happily in one program. And although a truly imperative program certainly isn’t a purely functional program (and it should be possible in Babel-17 to write truly imperative programs), there are many programs that seem to be imperative, but really can  just as well be understood as functional programs (I will describe this point in a later post).

What is so phlegmatic about Babel-17? First comes to mind the last (but not least) of the above goals:

  • Babel-17 is based on simple concepts most easily understood by the mathematical mind.

Second, I’d like to use Babel-17 to write down many useful algorithms and programs of varying size. Structuring big programs calls for object-oriented design and encapsulation. Many algorithms and programs are best understood as purely functional programs. But other algorithms like Quicksort are best understood  in their full brilliance in an imperative setting. In general, an elegant solution to a problem may rely on a combination of different programming paradigms; Babel-17 should be powerful enough to make using such a combination not only possible but also easy and unproblematic.

Mastering the Art of Phlegmatic Programming

December 1, 2009

So what exactly IS phlegmatic programming? And is it for you?

The second question is probably the easiest to answer. If you are somebody who just always makes the best out of the tools he or she is given (for the sake of shortness and because I like the image of that sexy, sexy programmer, I will use “she” in the rest of this post and all future posts), and if you have the natural ability to quickly work around the bugs in the conception and implementation of these tools, then phlegmatic programming is probably not for you.

This is because phlegmatic programming deals with the following problem: How do I shape my environment of programming languages and tools such that I can most easily express my solution ideas in these programming languages and tools?

Most of the time, the solutions to this problem  are very different from the solutions to the problem: How do I solve my current problem such that I can write down a concise solution given the current programming language and tool constraints?

Normally, as a programmer, you are asked to solve the latter problem. Normally, as a phlegmatic programmer, you enjoy solving the former problem.

The phlegmatic programmer does not strive to find the best solution given the current pragmatic real-world constraints. Instead, the only constraints she accepts are those of the physical and logical world. Everything else is up for discussion. If this discussion lasts several years, then so be it. The journey is its own reward.

The promise of phlegmatic programming is that if your solutions are the product of extensive reflection of the problem domain taking into account your whole imagination, then the solutions will inherit the properties of mature mathematics: they will be as easy to understand as possible given the complexity of the given problem, and they will be useful even 10 or 100 or 1000 years after their original conception.

This is year 0 of phlegmatic programming.