Lisp lectures IIa - Higher-order functions

I'm done with lesson IIa. That one was pretty hard. In Lisp it would be probably quite easy, but not in C#.
First thing, you need to switch from delegates to expression trees. There is no major problem to wrap delegates from my last article using Expression<>. Only problem is funtion folding. Consider this:

Expression<Func<double, double, double>> average = (y, x) => (x + y) / 2;
Expression<Func<double, double, double>> newGuess = 
  (guess, x) => average(guess, x / guess);

It will not work, compiler will say: "'average' is a 'variable' but is used like a 'method'". I believe that C# is missing some sugar here, does anyone know why ? And there is quick and ugly solution to the problem:

Expression<Func<double, double, double>> average = (y, x) => (x + y) / 2;
Expression<Func<double, double, double>> newGuess =
  (guess, x) =>  average.Compile().Invoke(guess, x / guess);

I implemented smart trick for expression folding. Let's have static helper class ExComp and this folding method Fold() with this signature:

public static TResult Fold<T1, TResult>(Expression<Func<T1, TResult>> expr, T1 param1)

Of course it could be implemented with Compile().Invoke(), but instead I'm post-processing the expression tree to get rid of method call and folding inner tree in place using InvocationExpression. So whole usage looks like this:

Expression<Func<double, double>> abs = (a) => a < 0 ? -a : a;
Expression<Func<double, double, double>> distance = 
    (a, b) => ExComp.Fold(abs, a - b);
double dist = distance.Process().Compile().Invoke(9,1);

And the tree after processing looks like this:

(a, b) => Invoke(a => IIF((a < 0), -a, a),(a - b))

Next we will hit problem with recursion, which works perfectly for delegates. This is factorial as simpler example of it :

Func<int, int> fact = null;
fact = (y) => y > 1 ? (y) * fact(y - 1) : 1;

Now serious troubles starting with expression trees. Emphasis on TREES. So, there is no good way how to turn expression tree into oriented graph of expressions. Only thing you could do is to use some external variable which has pointer back to root of the tree. For this I'm using similar trick as with folding above, fake method Self() and post-processing.

Back to the Lisp lecture. Now there is introduced idea of higher-order function. The function which creates and returns function, or could compose given function and return composition. Now when we have friendly expression folding, it's a piece of cake.

Expression<Func<double, double>> abs = (a) => a < 0 ? -a : a;
//folding function
Expression<Func<
    Expression<Func<double, double>>, //absFn
    Expression<Func<double, double, double>> //resultFn
    >> foldFn = ( absFn ) => ( a, b ) => ExComp.Fold(absFn, a - b);
//we are passing abs to get abs(a-b)
Expression<Func<double, double, double>> 
  distance = foldFn.Process().Compile().Invoke(abs);
double dist = distance.Compile().Invoke(9, 25);

So now we have foundation for completing square root function using reusable functions.

Expression<Func<double, double, double>> average = (a, b) => (a + b) / 2;
Expression<Func<double, double>> abs = (a) => a < 0 ? -a : a;
Expression<Func<double, double, double>> distance = (a, b) => ExComp.Fold(abs, a - b);

Expression<Func<
    Expression<Func<double, double, double>>, //stepFn
    Expression<Func<double, double, double>> //resultFn
>> avgDamp = (stepFn) =>
    (old, data) =>
        ExComp.Fold(average, old, ExComp.Fold(stepFn, old, data));

Expression<Func<
    Expression<Func<double, double>>, //testFn
    Expression<Func<double, double, double, bool>> //resultFn
>> test = (testFn) =>
    (guess, data, tolerance) =>
        ExComp.Fold(distance, ExComp.Fold(testFn, guess), data) < tolerance;

Expression<Func<double, double, double, double>> sqrtFixedPoint = null;

Expression<Func<
    Expression<Func<double, double, double, bool>>, //goodEnough
    Expression<Func<double, double, double>>, //newGuess
    Expression<Func<double, double, double, double>> //resultFn
>> fixedPoint =
   (goodEnough, newGuess) =>
        (oldGuess, data, tolerance) =>
                (ExComp.Fold(goodEnough, oldGuess, data, tolerance)) ? oldGuess
                    : ExComp.Self(sqrtFixedPoint,
                          ExComp.Fold(newGuess, oldGuess, data), data, tolerance);


Expression<Func<double, double>> square = a => a * a;
Expression<Func<double, double, double>> step = (old, data) => data / old;

sqrtFixedPoint =
    fixedPoint.Process().Compile().Invoke(
        test.Process().Compile().Invoke(square),
        avgDamp.Process().Compile().Invoke(step)
    );


Expression<Func<double, double>> squareRoot = 
  (x) => ExComp.Fold(sqrtFixedPoint, 1, x, 0.000000000000001);

double root = squareRoot.Invoke(25);

Code as well as post-processing helper class could be downloaded here

Lisp lectures

In the last months I'm thinking about dynamic languages and trying to understand what's the good part of it. Driven by this curiosity I've came to Lisp lectures by Abelson and Sussman. Yesterday I watched first lecture which is introduction to prefix notation, expressions and functional concept.
As a exercise they model and implement function for computation of square root. My attention was attracted by functional concept, so I tried to implement it. But I was too lazy to get and install any Lisp. Instead of it I implemented it in C# 3.0 using lambda expressions.
I'm curious how far I could get with this approach and whether it will be possible to convert most of the concepts of Lisp and do them in C#. I guess that I will hit the barrier as soon as more dynamic features of Lisp will be shown in next lectures. I will see.

Func<double, double, double> average = (y, x) => (x + y) / 2;
Func<double, double> square = x => x * x;
Func<double, double> abs = (x) => x < 0 ? -x : x;
Func<double, double, double> newGuess = 
  (guess, x) => average(guess, x / guess);
Func<double, double, double, bool> goodEnough = 
  (guess, x, tolerance) => (abs(square(guess) - x) < tolerance);
Func<double, double, double, double> tryGuess = null;
tryGuess = ( guess, x, tolerance ) => 
  goodEnough(guess, x, tolerance)
    ? guess
    : tryGuess(newGuess(guess, x), x, tolerance);
Func<double, double> squareRoot = ( x ) => tryGuess(1, x, 0.001);

double root = squareRoot(2);

Pragmatic programmer

I've finished reading Pragmatic Programmer, book from Andrew Hunt and David Thomas. The book is non-technical, philosophical attitude to programming as a craft. It is full of wisdom and knowledge about how to do your work to keep productive and happy. There are also grains about project management and some motivating articles.
It was published in 1999. I wish I had had chance to read the book those days instead of learning some parts of it the harder way.