Bluish Coder

ICFP Programming Contest 2006

Information on the ICFP Programming contest for 2006 are up. It's being held on July 21-24, 2006 and run by Carnegie Mellon University.

Factor and The Computer Language Shootout

I implemented one of the Computer Language Shootout benchmarks in Factor to see how it would compare. I wanted to get a gauge of the comparative performance of compiled Factor as well as seeing how the Factor implementations of the algorithms looked.

I started with the recursion benchmark. A darcs repository containing the Factor code and the C code for this can be obtained from the following command:

darcs get http://www.bluishcoder.co.nz/repos/computer-language-shootout

The Factor implementation is an almost direct translation of the C code.

To run the Factor code I created an image with the recursive.factor loaded and compiled:

./f factor.image -shell=tty
"recursive.factor" run-file
"recursive" words [ try-compile ] each
save

I then ran 'run-recursive.factor' which just calls the 'run' word in the recursive vocabulary and used the Unix 'time' command:

time ./f factor.image-shell=tty run-recursive.factor

The C code runs in 2.7 seconds with an argument of '11'. The Factor code runs in 31.8 seconds (it is hardcoded to use 11 as the argument). This is on my machine.

In the online recursive benchmarks the C code ran at 3.33 seconds. Assuming the speeds are relative this would mean that Factor would slot in at the benchmark at about 39.2 seconds ranking it slightly slower than GForth on the list.

The timing includes the starting up and relocating of the Factor image. Running the test within an already started image gives a 30.5 second runtime meaning the image startup takes about 1.3 seconds.

The code is written very much like the existing C code and I'll play around with it to see what a more concatenative style produces. Manfred Von Thun wrote an article on Nested Recursion for Joy that implemented Ackermann using a 'condnestrec' combinator. Trying a style like this in Factor to see the performance hit would be interesting.

Generators in Common Lisp

Matthew Swank posted an example of generators using Common Lisp in comp.lang.lisp.

His implementation contains a monadic implementation of continuations and call/cc which is quite nice, and the resulting thread has a dicussion on the some implementation variations. A simple example of using the call/cc implementation from later in the thread:

;; Scheme version
(call/cc (lambda (k) (k 42))) 

;; Common Lisp
(run (call/cc (lambda (k) (funcall k 42)))) 

Patent on continuation based web servers

It looks like Paul Graham has a patent on continuation based web servers: Patent 6,205,469&OS=AN/yahoo+AND+IN/graham&RS=(AN/yahoo+AND+IN/graham)).

In particular, the invention relates to the use of continuations to simulate subroutine calls in a program that interacts with the user through successive Web pages.

Paul Graham mentions it on his weblog. Found via Lambda the Ultimate.

Factor Partial Continuation Updates and Iterators

I've made some changes to the parser combinator library I wrote for Factor. The changes were to make the usage of the library to be more consistent with good Factor style.

The first change was to ensure that items on the stack are accessable in an intuitive manner from within the quotations passed to breset and bshift. When writing combinators in Factor it's important that the internals of the combinator implementation do not affect the callers view of items on the stack. For example:

20 [ drop 2 * ] breset

Recall that the quotation passed to breset has stack effect ( r -- v ). Once the 'r' is dropped the '*' should be expected to operate on the '2' and the '20'. The '20' is accessable as if it was directly under the 'r' on the stack from within the quotation.

In a prior implementation of breset I called the quotation using 'call' after creating a 'dup' of the 'r':

: breset 
  ... ( quot r -- )
  dup rot call ( r v -- )

The problem with this is that from within the quotation there is an extra 'r' above items on the stack before the quotation is called:

20 [ drop 2 * ] breset

The stack on entry to the quotation here is ( 20 r r -- ). Changing the breset implementation to use 'keep' instead of call fixes this problem:

: breset 
  ... ( quot r -- )
  swap keep ( v r -- )

Notice also that the return item from the quotation, 'v', is now below the 'r' and I didn't need to 'dup' it. In general, usage of words like 'keep' will enable combinators to more intuitively access stack items from outside the quotation.

Another way of solving this problem is to use the return stack words '>r' and 'r>' to move items temporarily off the stack so that the quotation being called is imediately above the relevant stack items supplied by the caller.

The second major change was to remove the use of 'with-scope' and namespaces to store the continuation delimiter. I previously stored this in a 'mark' and 'mark-old' variable. Now the implementations of breset and bshift manage these on the stack.

Storing variables in namespaces is seductive. It enables you to avoid sometimes complicated stack management by giving you named variables. Unfortunately it comes with a price. When setting the value of a variable in a namespace it is stored in the top most namespace on the namespace stack. This can be seen with code like this:

SYMBOL: myvar
5 myvar set
myvar get .
 => 5
10 [ myvar set ] keep drop myvar get .
 => 10

As expected setting the myvar variable in the quotation passed to 'keep' results in the global myvar value being set to 10. But if this is run inside a 'with-scope' you get caught by the fact that a new namespace is at the top of the stack:

myvar get .
  => 10
20 [ [ myvar set ] with-scope ] keep drop myvar get .
  => 10

Notice the value is still 10. This is because the variable is set in the new namespace which is dropped off the namespace stack when the 'with-scope' exits. Normally you would be aware of this when you write code, but if you use a combinator that uses 'with-scope' in its implementation, and it then calls your quotation from within that scope then all your variable sets will be lost at the end of the combinator call.

This may be desired, and the reason why the combinator is in a scope, but for many cases it's not the desired behaviour. So as a general rule I try to avoid using variables and with-scope in combinator implementations.

There was also a minor bug in my 'range' example in that it didn't give the correct range if the starting number was anything but '1'. The corrected 'range' implementation is:

: range ( r from to -- n )
 over - 1 + rot [ 
   -rot [ over + pick call drop ] each 2drop f  
 ]  bshift 2nip ;

Note the '2nip' at the end. 'bshift' and 'breset' operate like other continuation combinators in that they restore the stack to what they were before they were called. In this case the 'from' and 'to' were on the stack and we need to 'nip' them off. Simple usage works as before:

[ 1 5 range . f ] breset drop
 => 1
    2
    3
    4
    5

Nested usage works correctly now:

[ dup 1 3 range swap 10 12 range + . f ] breset drop
 => 11
    12
    13
    12
    13
    14
    13
    14
    15

It can be hard to reason about what usage of words like 'range' does. Think of it as returning a single value 'n', and calling the breset multiple times with the value of 'n' for each 'n' in the range. So you'll see that after the first 'range' call I 'swap' to swap the result of the range and get the continuation mark passed to breset back to the top of the stack to call the second 'range'.

You'll notice that the result of calling these snippets always returns 'f' on the stack. This is because the range implementation leaves 'f' on the stack at the end of the bshift quotation. This results in 'breset' exiting with that value.

A question was raised on the Factor mailing list about CLU-style iterators. An example of the usage from one of the links in that message is:

sum: INT := 0;
loop sum := sum + 1.upto!(10); end;
#OUT + sum + '\n'; -- Prints sum of integers from 1 to 10

This has a very direct translation in Factor using range and breset as:

SYMBOL: sum
0 sum set 
[ 1 10 range sum get + sum set f ] breset drop
sum get .
 => 55