Tuesday, April 22, 2008

First-Class Procedures, Part I: naming by a variable

In section 1.3.4 of SICP, the authors discuss (after Christopher Strachey) the rights and privileges of first-class citizens of a programming language, justifiably praising Lisp for awarding first-class status to procedures.

The first few real posts here will explore this topic as it relates to some other languages. Are procedures first-class citizens of Ruby? How about Erlang, or even JavaScript?


I'll start with Ruby, where the topic seems most controversial. I'll also start with the first condition that SICP suggests first-class citizens must satisfy: being nameable by a variable. Here's a sample irb session:

$ irb
irb(main):001:0> add1a = 1.method(:+)
=> #<Method: Fixnum#+>

On line 1, we identify a given procedure by the name add1a by using the method method to extract the action that is referred to when sending the :+ symbol as a message to the Fixnum 1. Ruby defines this operation as simple numeric addition, more or less, and the fact that we're grabbing this method from 1, as opposed to 42 or -6 acts as a closure, meaning that the extracted method remembers that the item to which its arguments should be added is 1, rather than 42 or any of the other instances from which we could have extracted our method. (Had we extracted the :+ method from a different instance, perhaps hello, world!, the operation wouldn't even have been defined as simple numeric addition, but that's another story).

irb(main):002:0> add1b = lambda { |x| 1 + x }
=> #<Proc:0xb7c8a638@(irb):2>

On line 2, we're identifying another procedure by the name add1b. This time, we're using lambda to construct the procedure, rather than extract a pre-existing method from an instance.

irb(main):003:0> add1c = Proc.new { |x| 1 + x }
=> #<Proc:0xb7c823c0@(irb):3>

On line 3, we're identifying yet another procedure by the name add1c. This time, we're using Proc.new rather than lambda, both of which create Proc objects.

None of these assignments of procedures into names would be terribly useful if they weren't callable.

irb(main):004:0> add1a.call(2)
=> 3
irb(main):005:0> add1b.call(2)
=> 3
irb(main):006:0> add1c.call(2)
=> 3

We see that all 3 of these named variables perform the expected operation when called. How does this compare with some other languages that are more definitively functional?


In deference to SICP, let's see how this operates in MIT Scheme:

$ mit-scheme
1 ]=> (define add1 (lambda (x) (+ x 1)))

;Value: add1

1 ]=> add1

;Value 11: #[compound-procedure 11 add1]

1 ]=> (add1 2)

;Value: 3

The theory is the same: we identify a procedure by the name (add1 in this case), and then call it (apply it to its arguments). Note, however, that calling the add1 procedure is slightly more straightforward in Scheme. We simply construct a list within parentheses such that the procedure to be called happens to be the first item, and the arguments to that procedure call are the remaining elements of the list. There is no need for a separate .call syntax. Ruby Procs can also be called without a .call method if one puts the arguments within [], rather than parentheses, but the main difference still stands, which is that the syntax of calling such a procedure differs (however slightly) from calling the built-in methods. Lisp fans who deride Ruby fans' claims of Ruby having first-class procedures point to this, not entirely without merit.


Another language that fits very well within the functional paradigm is Erlang:

$ erl
Erlang (BEAM) emulator version 5.5.5 [source] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.5.5 (abort with ^G)
1> Add1 = fun(X) -> 1 + X end.
2> Add1(5).

here, we define a named variable Add1 that holds the procedure functionally equivalent to all of our examples so far, the action of adding 1 to the argument. Here, the action of calling our new named variable as a function is more straightforward, reminiscent of Scheme. We simply provide the argument within parentheses, as one calls any function in Erlang. There is a slight difference, in that variables in Erlang are capitalized, while built-in functions are lowercase. Still, functions are clearly nameable in Erlang.


What about JavaScript? JavaScript is a language that has gotten a largely undeserved bad rap, largely due to some bad implementations and what is perhaps the worst and most misleading name in programming language history. None of this detracts from the language itself, which my good friend Aubrey Keus calls Scheme with syntax. JavaScript reminds me a great deal of Ruby, in that it makes heavy use of both object-oriented and functional paradigms. Let's take a look at some JavaScript code that Aubrey provided:

add1 = function(x) { return x + 1; }

Look at how trivial that is to do. All one has to do is call add1(2) and 3 is returned, as one would expect. Again, the act of calling such a function is closer to (indistinguishable from) calling a built-in function.

I would argue that in all of these languages, procedures (whether implemented under the hood as functions or methods) satisfy this first criterion of being a first-class citizen. You may disagree, thinking that the additional hoops to be jumped through in the Ruby calls are too egregious. I find that from a pragmatic perspective, it's not that big a deal for me.

I also think Hashes are more like functions than Arrays, but that's another story.

No comments: