Random Thoughts

It's quite final - the house has been emptied and packed up, and the contents are now hopefully somewhere East of Adelaide, ready to arrive in Hobart on 2nd/Nov. Edward was running around the empty house last night just saying 'Wow' - opening and closing cupboard doors with complete freedom (there is nothing there for him to wreck!). The past few months have been really busy - I've certainly not had time for blog posts - and now there is time for a bit of relaxation. Phew!

Heather and I are delighted to announce the birth of Poppy Sapphire on April 21st. She weighed in a 3.9kg (8lbs, 10ozs) - almost a full pound heavier than Edward. Both mother and daughter are doing well. Pictures will follow soon, as will monosyllabic sentences caused by severe sleep deprivation ;-)

After much pondering I finally sat down and wrote some λ-expressions for infinite lists of integers, factorials, and Fibonacci numbers - it was a fun exercise, and didn't take long. A fundamental requirement I had was that the standard list operators (car and cdr) could be applied to both normal lists (constructed by cons) and the infinite lists, and not have to create separate stream-car and stream-cdr operators (as is done in Scheme). Before embarking on the exercise I thought this requirement would cause some difficulty, but after starting it became apparent that with lazy evaluation it was a complete furphy. I think that I'm beginning to develop a taste for laziness, at least when comes to evaluation of expressions!

Below are the expressions I came up with (written in Elle). The use of the paradoxical operator Y makes the expressions look more complicated than they really are, but the use of recursion is essential in obtaining the infinite list behaviour.

(define car (lambda(p)(p(lambda(h t)h))))
(define cdr (lambda(p)(p(lambda(h t)t))))
(define Y(lambda (f)(lambda(x)f(x x))(lambda(x)f(x x))))
(define integers (Y (lambda (f n p) p n (f (+ n 1))) 0))
(define factorial (Y (lambda (f n v p) p v (f (+ n 1) (* v n))) 1 1))
(define fibonacci (Y (lambda (f m n p) p n (f n (+ m n))) 0 1))

You might like to verify the following identities:

(car integers) -> 1
(car (cdr integers)) -> 2
(car (cdr (cdr integers))) -> 3
(car (cdr (cdr factorial))) -> 6
(car (cdr (cdr (cdr (cdr fibonacci))))) -> 5

It looks like I've got a Python monad working in the Simple Lambda Evaluator:

E:\work\lambda>python elle.py
------------------------------------------------------------------------------
((#pyseq((#pycall "print")((#cons "hello")((#cons "world")#nil))))(\x.((#pycall
"print")((#cons "wow")#nil))))
------------------------------------------------------------------------------
hello world
wow
['#', None]

So far I've only tested output - input will have to wait a while. The significant changes made to the evaluator include:

1. A new cell type (#) containing a raw python value;
2. Builtin functions #pyseq and #pycall. The #pycall function accepts two arguments: the name of the Python function, and a list of arguments;
3. Additional builtin functions #cons etc... that aren't strictly required, but ensure that the handling of lists by elle and the evaluator is consistent.

I must admit to having had great reluctance in introducing these builtin functions, but am relieved that the implementation is quite clean. For example, below is an snippet of code:

_car = [ '\\', 'c', [ '@', [ 'V', 'c' ], [ '\\', 'h', [ '\\', 't', [ 'V', 'h' ] ] ] ] ]
_cdr = [ '\\', 'c', [ '@', [ 'V', 'c' ], [ '\\', 'h', [ '\\', 't', [ 'V', 't' ] ] ] ] ]
_true = [ '\\', 'x', [ '\\', 'y', [ 'V', 'x' ] ] ]
_false = [ '\\', 'x', [ '\\', 'y', [ 'V', 'y' ] ] ]
_nil = [ '\\', 'c', _true ]
_nullq = [ '\\', 'c', [ '@', [ 'V', 'c' ], [ '\\', 'h', [ '\\', 't', _false ] ] ] ]

def nullq( cell ):
    """Return True if at the end of the list, else False
    """
    return bool( _arg( [ '@', [ '@', [ '@', _nullq, cell ], [ 'N', 1 ] ], [ 'N', 0 ] ], 'N' ) )

def car( cell ):
    "First element of a list"
    root = [ '@', _car, cell ]
    reduce( root )
    return root

def pyval( cell ):
    "Extract python value from cell"
    if cell[ 0 ] in 'N"#':
        return cell[ 1 ]
    else:
        raise "Bad python cell '%s'" % cell[ 0 ]

def _pycall( stack ):
    "(#pycall  )"
    if len( stack ) < 3:
        raise "Not enough arguments"
    fn = _arg( stack[ -2 ][ 2 ], '"' )
    el = stack[ -3 ][ 2 ]

    args = []
    while not nullq( el ):
        args.append( pyval( car( el ) ) )
        el = cdr( el )
    stack[ -3 ][ 0 ] = "#"
    stack[ -3 ][ 1 ] = pyfunc( fn )( *tuple( args ) )

Now that is not too bad - the function nullq() (testing for the end of the list) builds a cell representation of an expression, and uses the evaluator to calculate a (Python) boolean (True if at the end of the list). A similar trick is used by car() and cdr(). The pyval() function is also quite simple: if the cell can be interpreted by Python its value gets extracted.

In essence, all that the builtin implementations of #car, #cdr etc... do is enforce a lambda expression. The underlying evaluation does not take any short cuts - the lambda expressions are still evaluated.

I'm trying really hard to get my head around monads, and I thought it might be a good idea to try and implement the array monad in C to solve a simple problem: initialise an array of 5 elements (say 5 down to 1), and calculate the sum. The C code for doing this directly is trivial:

void init( int a[ 5 ] )
{
  int i;
  for( i = 0 ; i < 5 ; ++i )
    a[ i ] = 5 - i;
}

int sum( int a[ 5 ] )
{
  int i, s;
  for( i = s = 0 ; i < 5 ; ++i )
    s += a[ i ];
  return s;
}

After two hours and over 200 lines of code I've now got a monad implementation that doesn't yet sum the array entries, and leaks memory like a sieve. You can find the C code here - any feedback is most welcome!

Updated: 21/March
Now have a working monad implementation that does sum the array entries! It is only 439 lines of code, and still leaks memory like a sieve. Actually, there is a full implementation of not one, but two monads in this code! Both the array transformer and array reader monads are implemented, along with the coercion operator for mapping a reader into a transformer. I apologise for using #include <stdio.h> instead of writing a monad for I/O, but I was keen to get this code out and didn't have time to write another 2000 lines of C code for the pure implementation. Otherwise the implementation is purely functional, with the entire computation being performed by

printf( "The sum is: %d\n", xblock( 0, xbind( build( ), summer( ) ) ) );

The function build() creates an array transformer monad that initialises the array, and the function summer() creates the object that performs the actual summation. These are combined using the binding xbind(), and finally the computation is performed using xblock(). Note that the actual array is not created until control is passed to xblock(), so one interpretation of the array transformer monad is that it is the intention to perform an action at a later stage, when xblock() is invoked.

There is also a cutdown implementation using just the array transformer monad. It is 'just' 347 lines of code ;-)

Updated: 22/March
Here is a Python implementation of the array transformer monad. The code is much simpler, given that python supports closures. All of the cruft that was necessary in the C implementation just disappears. The function summer() could be rewritten to use lambda functions (left as an exercise for the reader!).

In many circles it is considered best practice to avoid the use of global variables when writing code. I've certainly adhered to this viewpoint for a long time, but as with all things this year it is time for questioning this! As a long time C/C++ programmer, I've thought that I've had a good understanding of the different approaches to structuring code, but the freedom afforded by a block structured language that treats functions as first class objects (e.g. Scheme, but not Pascal) is really amazing. The key idea is that variables can be lexically nested, and access to them can be controlled by functions passed back to the client. This is Parnas' data hiding to the max! Add a bit of garbage collection and much of the minutiae hindering code development has just evaporated.

The elegance of this approach, as opposed to OO, is that it is completely uniform - there is just a single mechanism being used. This is in complete contrast to the multiplicity of data hiding mechanisms available in C, C++ or Java. C is the simplest (or I've got no intention of discussing member access privileges, the differences between module/function/class scope, all the different uses of 'static' in C++, nor namespaces) so lets discuss C's mechanisms for data hiding: void pointers (or security by obscurity); and static variable scope (in functions or modules). Not much can be said about security by obscurity - it's a good idea for as long as you can get away with it ;-) There is almost no good reason to ever declare static variables within a function; indeed, it should never be done within a library function, as suddenly that entire library can no longer be simply used in a threaded or reenterant environment. Similarly, there are few good reasons to allow static module variables, as doing so makes a strong assumption about how that module is used. Inevitably I do end up using static module variables to avoid the programming overhead of declaring a structure to hold all of the module variables, and then adding an additional argument to every function in the module to reference this structure, and then adding indirections (->) to access the data etc... and then to find that after three revisions of the code two of the members are no longer referenced by any of the functions and can be removed, but that to add further functionality another four members, each highly stateful and closely replicating (but not identical to) existing members, must be added to the structure etc... There is just so much pain in trying to write good code!

A lot of this pain can be alleviated by allowing nested functions, and taking advantage of lexical scoping. Pascal allows this (and I'm kind of embarrassed to say that after 15 years of hard core C I'd forgotten this), but what Pascal lacks is the ability to return functions as results of a computation. This imposes a big limitation on what can be expressed in the language - it is certainly not possible to process code and data interchangably - and arguably it forces a multiplicity of mechanisms for data access to be built into the language. C does allow (pointers to) functions to be returned by a function, but it is necessary to manually define and manage the function environment (and hence a lot of the pain of programming).

What is really disturbing is that these problems have been well understood since the 1960's (see The Function of FUNCTION in LISP, or Why the FUNARG Problem Should be Called the Environment Problem, AI Memo 199). Why do we keep persisting, after 35 years, with languages that are so limited?

I'm going to keep on writing programs in C. But I'm going to stop trying to force abstraction and composibility. I'm going to stop pretending that every program I write will be reused or extended arbitrarily. I'm going to use more global variables when it is reasonable to do so, particularly if it allows me to write less code. I'm going to place all the code in a single file; when it becomes unmanagable the complexity of the program has most probably reached a natural bound, and further development should not occur until the complexity has been removed. And when I have the opportunity I'm going to throw away more code, and rewrite it in a better language where the minutiae look after themselves...

I've just written a simple lambda calculus parser/evaluator in python - it has been rather fun! You can download it from laurasia. The code is rather raw, but comes with a money back guarantee ;-)

Updated: 28/March
An improved evaluator is now available. Note that the name of the evaluator code file has been changed from lambda.py to leval.py. This change was required since lambda is a reserved word in Python. I have also written a simple Lisp-ish front-end for the lambda evaluator - I'm calling this language elle. So far I've been able to calculate 3! (factorial) - all done using the Y combinator (of course!).

I gave a talk on Monday about the lambda calculus, and have put the powerpoint slides online. The talk went well. The main point that I wanted to get across was that there are alternative approaches for programming beyond the world of C, C++, and Java. But the audience wasn't too interested in the λ-calculus formalism, and maybe it would have been better to give a more practical talk focusing on a real functional programming language.