31 Oct 2021 - Sourav Datta
Once upon a time I had a chance encounter with a book named Structure And Interpretation of Computer Programs, and after struggling with the first chapter it blew my mind in the first couple pages of the second chapter.
The book starts with a quote that looks like:
“Computer Science is neither about computers nor is it about science”
And it follows that quote with a phrase that equates computer programming with magic - programming is like uttering a set of incantations to the computer to make it do something for you. If you utter it wrong it won’t do that something and in the worst case it would do something completely different! However, around the time when I read this the aspect of magic did not fully sink in. I was already programming in several imperative languages - C, C++, Python, Java and C#. Although, I dabbled enough with Common Lisp from college days to appreciate programming with functions, I mostly used imperative approaches. That completely changed when in the second chapter of that book I saw a piece of code that, after thinking about it a bit, really felt like magic.
Before describing the code lets talk talk about what it is about. It is about creating a pair of two objects. When we think about creating a pair, the fist thing that comes to mind is, well it is a data structure that holds two things. And going by the OO principles, this data structure soon turns into an Abstract Data Type(ADT) with associated methods that work on it. The pair ADT will in most cases have a method to construct and access first and second objects from it. It might also have ways to update those values, but lets stick to immutable data structures for now. A typical implementation would be:
class Pair:
def __init__(self, x, y):
self.first = x
self.second = y
def get_first(self):
return self.first
def get_second(self):
return self.second
p1 = Pair(2, 'hello')
print(p1.first(), p1.second())
In a typed language, this would be a little more verbose as we would have to create a generic type Pair<S, T> which can hold any type of objects in it. But overall, this is what I would have done.
The code that the book had for creating a pair is this:
(define (make-pair x y)
(lambda (choice)
(cond
((= choice 0) x)
(else y))))
(define (pair-first p)
(p 0))
(define (pair-second p)
(p 1))
(define p1 (make-pair 2 "hello"))
(displayln (pair-first p1))
(displayln (pair-second p1))
To those who are not familiar with reading Lisp, here’s a version of the exact same code in Javascript:
const make_pair = (x, y) => choice => (choice === 0)? x : y
const pair_first = p => p(0)
const pair_second = p => p(1)
const p1 = make_pair(2, "hello")
console.log(pair_first(p1), pair_second(p1))
Now the magical parts that struck me coming from a purely imperative view of programming:
x and y in instance variables so that they can be referred back when accessing. While this version does not!closures. When a function is defined in a language that supports lexical scoping, the function contains with it an environment. That environment not only has the details about the objects/variables/functions etc. available within the scope of that function, but it also carries information about the environment where the function is defined. And that is why, the inner lambda function that takes a choice argument can freely access the x and y variables which are defined above it. This creates the same effect of a class which stores this information explicitly in instance variables.thing that has some data bound to it (x and y) and also few methods (first and second) that auto-magically works on that data via a self parameter. In higher order programming, this complex thing simply becomes another function, which can then access its lexically scoped environment to make use of variables defined outside of it! Thus the SICP version removes that auto-magical self and makes it uniform via just functions. And that in turn creates the magic!This way of thinking completely changed my mind about how flexible it is to program with higher order functions, closures and in general immutable data with functional programming. In fact after looking around a bit I found the programming language Racket defines its object oriented interfaces as a thin layer on top of exactly the same concepts as above. What’s more interesting, there is an ongoing argument that closures are poor person’s objects! But at the same time some would argue that objects and classes, when taken in their full dynamic power, as is perhaps found in Smalltalk dialects (Pharo, Squeak etc.) are indeed more powerful than just closures and higher order functions. So they would argue that, objects are poor person’s closures. :-) Check out this SO link for more entertaining thoughts.