In "Structure and Interpretation of Computer Languages" the authors show you how you can form pairs of integers in Lisp using cons (concatenate two values), extract the first using car, and so on, so beginning the start of a path to data structures.
They then go on to show you how you could encapsulate a pair of integers in a function instead, and proceed to rewrite cons and car in this manner...
(define (cons x y)
(lambda (m) (m x y)))
(define (car z)
(z (lambda (p q) p)))
Took me a while to get my head around these two, but if I got it right, the new version of cons returns a function that encapsulates the two integers, and allows you to pass in another function that will do something with them. In the case of the rewritten car that second function merely returns the first integer.
Being a C# programmer by day, I wondered if it would be possible to do something similar in C#. Not that I can see much practical use for this, but more that it seemed like an interesting challenge.
However, I can't seem to find a way to define a Cons(int x, int y) method in C# that achieves the same as the SICP cons rewrite. Every time I think I've worked out what it needs to return, I then decide I got it wrong.
As far as I can understand, the m in the lambda in cons is a function that acts on the pair of integers, presumably returning another integer. This implies the return type of my C# Cons should be Func<int, int, int>. However, on second thoughts, it looked like it should return a function that takes a function of two integers and returns another integer, meaning it should be Func<Func<int, int>, int>.
However, I'm not convinced that either of these are correct, and even if they are, I haven't managed to write a method that compiles.
Anyone able to advise?
The static types make this slightly more awkward, but you can pretty much straightforwardly translate the Scheme to CSharp. The return type of cons needs to be Func<int, int, Func<Func<int, int, int>, int>>: It is a function that takes two integers and returns a function that takes a function which takes two integers and returns one and returns an integer. To wrap your head around it, it helps to give the subtypes names:
(int, int) -> int a selector: Given two integers, this selects one (first or last).(selector) -> int a pair: Given a selector, this returns the result of the selector applied to itself.(int, int) -> pair.Func<int, int, Func<Func<int, int, int>, int>> cons = (int x, int y) => (Func<int, int, int> f) => f(x, y);
Func<Func<Func<int, int, int>, int>, int> car = (Func<Func<int, int, int>, int> z) => z((int p, int q) => p);
Func<Func<Func<int, int, int>, int>, int> cdr = (Func<Func<int, int, int>, int> z) => z((int p, int q) => q);
To turn these into methods, you basically just have to convert a "variable" of Func<T1, T2, ..., R> f = (T1 x, T2 y, ...) => ... into R f(T1 x, T2 y, ...) { return ...; }. Exemplary for cons:
Func<Func<int, int, int>, int> cons(int x, int y) {
return (Func<int, int, int> f) => f(x, y);
}
For the true main use case of cons, you will want to plaster dynamic everywhere, which enables you to build singly linked lists based on cons pairs:
Func<dynamic, dynamic, Func<Func<dynamic, dynamic, dynamic>, dynamic>> cons = (dynamic x, dynamic y) => (Func<dynamic, dynamic, dynamic> f) => f(x, y);
Func<Func<Func<dynamic, dynamic, dynamic>, dynamic>, dynamic> car = (Func<Func<dynamic, dynamic, dynamic>, dynamic> z) => z((dynamic p, dynamic q) => p);
Func<Func<Func<dynamic, dynamic, dynamic>, dynamic>, dynamic> cdr = (Func<Func<dynamic, dynamic, dynamic>, dynamic> z) => z((dynamic p, dynamic q) => q);
var list = cons(1, cons(2, cons(3, null)));
var first = car(list);
var second = car(cdr(list));
var third = car(cdr(cdr(list)));
Console.WriteLine(first + " " + second + " " + third); // 1 2 3