SICP in C# 3.0 – Higher-Order Procedures

Your DisplayName here! — Mon, 03 Dec 2007 00:01:16 GMT

One of my favorite sections in SICP so far has been section 1.3 Formulating Abstractions with Higher-Order Procedures. Higher-Order Procedures are procedures that deal with other procedures. They can take a procedure as an argument and/or return a procedure as a result.

Though it is somewhat academic, I really like the example that Abelson and Sussman use in section 1.3.1 to explain the “procedures as arguments” scenario. To illustrate this concept they implement summation using Scheme. They implement a higher-order procedure called “sum” that takes two procedures and a range of numbers as arguments. One procedure is used for computing the value that is added to the sum and the other is used to determine the next value to compute. The Scheme code can be seen here.

It’s not as useful as map and reduce, but those are not discussed until Chapter 2.

As some of you may know C# 3.0 adds a whole slew of functional/dynamic features. Whether this is an effort to keep up with the cool kids or merely a necessity for making LINQ work is not important to me. What I’m curious to know is if the features make it easier to implement the concepts in SICP using C# 3.0.

Implementing “Sum” in C# 3.0

Following along with the example from SICP - let’s say that you have defined the following methods.

I decided to break with the book here and use iteration instead of recursion to make the code a little more digestible.

Common to each method is the idea of iterating over a range of numbers and adding the result of each computation to the total. If we create a higher-order procedure called “Sum” to abstract out this behavior we can then redefine each method.

The “=>” and “Func” constructs come from the new Lambda expressions feature in C#. Lambda expressions are a great new aspect of the language and they make implementing higher-order procedures a lot easier. In this case the "term" and "next" arguments can be passed as Lambda expressions.

I had to cheat and do some casting shenanigans because the division operation in "PiSum()" brings floating point numbers into the mix, but I feel like this code does capture the essence of the original Scheme implementation. Implementing "Sum" as a generic method might be a way to make the code more elegant.

If subverting the type system does not appeal to you, the following JavaScript implementation might be of interest.

JavaScript is more similar to Scheme (dynamic typing/first class functions) so it makes sense that the translation is smoother.

It turns out that there are other people interested in implementing SICP in different languages. Chris Rathman has translated parts of SICP into 19 other languages. One disturbing thing to note about Chris’s C# translation is that it doesn’t go beyond chapter 1. Does that mean that it is not possible to implement the code from the rest of the book in C#?

Eric Tobia's Blog - SICP

SICP in C# 3.0 – Higher-Order Procedures