Monday, July 21, 2008

First-Class Procedures, Part III: being returned as values of procedures

SICP demands that for functions to qualify as First Class Citizens,
they must satisfy several requirements. I've written about this before in reference to the first requirement: being able to assign names to procedures, and the second requirement: the ability to be passed as an argument to another function. Next on the list is being returned as a value from a procedure. Here we go with that.

Again: Ruby, SICP's original Scheme, Erlang, and Haskell, with JavaScript by my friend Aubrey Keus.

In Ruby:

def get_method_that_does_name(owner, name_as_sym)

def get_double_plus_one
lambda { |x| (x*2) + 1 }

Here we've defined a method called get_method_that_does_name. It expects a Symbol argument preceded by an owning object, and returns a Method object, created via the aptly-named method method. The owning object provides the context for the method, similar to a closure in a purely-functional language. Here's an example of how get_method_that_does_name might be used in irb:

>> add1 = get_method_that_does_name(1, :+)
=> #<Method: Fixnum#+>
=> 3
>> greet = get_method_that_does_name('hello, ', :+)
=> #<Method: String#+>
=> "hello, world"

The method identified by + means something different when called on 1 than when called on hello, , as shown in the example.

The other example uses the more-familiar lambda keyword to generate a Proc.

>> dp1 = get_double_plus_one
=> #<Proc:0xb7cb2458@./first_class_functions_in_ruby.rb:39>

In either case, the returned value from the method (whether
get_method_that_does_name or get_double_plus_one) is a procedure-like object callable with the call method.

In MIT Scheme:

$ mit-scheme

1 ]=> (define get-adder (lambda (x) (lambda (y) (+ x y))))
;Value: get-adder
1 ]=> (get-adder 2)
;Value 11: #[compound-procedure 11]
1 ]=> ((get-adder 2) 1)
;Value: 3

Thi sample code demonstrates a typical Scheme example of a procedure that returns another procedure. This particular syntax uses two lambdas, but note that the first line could have been expressed alternately in this manner:

1 ]=> (define (get-adder x) (lambda (y) (+ x y)))
;Value: get-adder

Usage in the 2nd and 3rd lines remain the same in either case. Line 2 shows us that calling (get-adder 2) returns a compound-procedure value, and line 3 shows us that that returned procedure takes an argument (y in our definition code), and adds it to the value of x that was used in the get-adder call that created the returned procedure in the first place.

One could argue that Scheme provides the most canonical syntax for defining a procedure that returns another procedure. This is unsurprising, given the roots of the language, especially in education.

In 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> GetAdder = fun(X) -> (fun(Y) -> X + Y end) end.
2> GetAdder(2).
3> Add1 = GetAdder(1).
4> Add1(2).

This Erlang example differs slightly, of course. Erlang's variables are uppercase, and it uses the fun keyword rather than lambda. This particular example also happens to assign the value of GetAdder(1) into a variable called Add1, which erl dutifully reports back to us is of the type Fun. Calling Add1(2) then produces the expected result.

In Haskell:

Last time on this topic I used hugs, a REPL shell. This time I'll use GHCi.

$ ghci
GHCi, version 6.8.2: :? for help
Loading package base ... linking ... done.
Prelude> let getAdder x = \y -> (y + x)
Prelude> let add1 = getAdder 1
Prelude> add1 2
Prelude> :quit

This actually uses Haskell's equivalent of lambda in the \, apparently chosen for its visual resemblance to the letter λ without a lower-left leg. If we wanted to use the pointfree style mentioned in the hugs portion of my previous post on this topic, we could replace the first line with

Prelude> let getAdder = \y -> (y +)

Notice how it leaves the x variable out entirely.

We can use Haskell's type system to reveal some other things of interest.

Prelude> :t getAdder
getAdder :: Integer -> Integer -> Integer
Prelude> :t (getAdder 1)
(getAdder 1) :: Integer -> Integer

The :t command in GHCi reports the type of its argument. getAdder has the type Integer -> Integer -> Integer. This means that it can either take two Integer arguments and return a single Integer, or it can take one Integer and return a function of type Integer -> Integer. This means that the returned function takes one Integer and returns one Integer. When we check the type of the expression (getAdder 1), it reports, as expected, that the expression takes a single Integer, returning another. This type system is crucial to understanding Hashkell's handling of currying, which I hope to get into in greater detail in a later post.

If we want to eliminate middle variables entirely, we can simply feed two Integers directly to getAdder, as in

Prelude> getAdder 1 2

In JavaScript:

function call_proc_arg_on_2(first_class_proc) {
return first_class_proc(2);

Number.prototype.call_proc_arg_on_self = function(first_class_proc) {
return first_class_proc(this);


Aubrey's JavaScript code demonstrates both the initial example common across all the languages, as well as the equivalent of my second Ruby example, in which the desired behavior is attached to existing number objects within your language's existing workspace.

So that's it. I think all of these languages satisfy the requirement of returning procedures (however defined) as values from other procedures, at least from a practical perspective. The next (and final) post in this series will be about incorporating procedures into data structures. I'll get to the post when I can.

No comments: