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)
  owner.method(name_as_sym)
end

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

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#+>
>> add1.call(2)
=> 3
>> greet = get_method_that_does_name('hello, ', :+)
=> #<Method: String#+>
>> greet.call('world')
=> "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>
>> dp1.call(4)

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.
#Fun<erl_eval.6.49591080>
2> GetAdder(2).
#Fun<erl_eval.6.49591080>
3> Add1 = GetAdder(1).
#Fun<erl_eval.6.49591080>
4> Add1(2).
3

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: http://www.haskell.org/ghc/  :? for help
Loading package base ... linking ... done.
Prelude> let getAdder x = \y -> (y + x)
Prelude> let add1 = getAdder 1
Prelude> add1 2
3 
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
3

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);
};

call_proc_arg_on_2(add1);
Number(100).call_proc_arg_on_self(add1);

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.

First-Class Procedures, Part II: passing as an argument

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. The second requirements is the ability to be passed as an argument to another function, which is the topic of this post.

I'll just dive in, again showing multiples languages: Ruby, SICP's original Scheme, Erlang, and Haskell. Again, my friend Aubrey Keus has provided some JavaScript, as well.

This post is fairly Ruby-heavy. A lot of them are likely to be, as it's the language I know best among those being discussed, as well as the the one I use to earn my Yankee Dollars.

In Ruby:

$ irb

irb(main):001:0> def call_proc_arg_on_2(first_class_proc)
irb(main):002:1> first_class_proc.call 2
irb(main):003:1> end 
=> nil 
irb(main):004:0> add1 = lambda { |x| 1 + x } 
=> #
irb(main):005:0> call_proc_arg_on_2(add1)
=> 3

Here we've defined a method that expects an argument called first_class_proc, which is (as you might expect) a Proc. add1 is such a Proc which adds 1 to its argument - hence the name. When we pass that in as the argument for call_proc_arg_on_2, we get the expected value of 3.

Proc & block syntax

Ruby has a curious subtlety in its treatment of Procs. Notice that we need to use the call method in order to make the Proc do its thing. Not true for some other languages below. Why would anyone do this when designing a language?

Below we see a more typical way of passing a procedure as an argument to a higher-order method.

irb(main):006:0> def call_block_on_2()
irb(main):007:1> yield 2
irb(main):008:1> end 
=> nil 
irb(main):009:0> call_block_on_2 { |x| 1 + x } 
=> 3

The main differences between this and the previous example are as follows:

1. The name of the method reflects the differences in expected arguments: a Proc vs. a block


2. call_block_on_2 does not have a parameter in its declaration, just the empty parentheses


3. When we call call_block_on_2, we don't pass a variable with a name (like add1), instead we just give it a block, which is the business between the {} braces. Note that this block is what we give to the lambda method to create a full-fledged Proc in the earlier example.


4. The yield method is roughly akin to the call method, except that it automatically knows that it should operate on whatever block was given, without having to refer to it by name.

So what's the deal with this? Standard Ruby style is to call methods with blocks for operations like iteration (with each), list transformation (map) and filtering (select, partition), and so on. This is so common that the syntactic sugar of being able to easily do this outweighed the consistency of being able to call function arguments without needing the call method.

In MIT Scheme:

$ mit-scheme

1 ]=> (define call-on-2 (lambda (x) (x 2)))

;Value: call-on-2

1 ]=> (define add1 (lambda (x) (+ x 1)))

;Value: add1

1 ]=> (call-on-2 add1)

;Value: 3

Check it out. Simple procedure declarations, and procedures that can be passed as args with no special syntax. Some would say no syntax at all, both among the pro- and anti-Lisp communities. Not wishing to add to an old flame war, I'll move on.

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> Add1 = fun(X) -> 1 + X end.
#Fun
2> CallOn2 = fun(F) -> F(2) end.
#Fun
3> CallOn2(Add1).
3

I'm becoming a pretty big Erlang fan. Note that the variable Add1 is in all caps - this serves a semantic purpose in Erlang. User-defined entities in Erlang that are in lower-case are generally either straightforward functions or atoms, which are essentially just values. They're very similar to Ruby's Symbols, for example.

This Erlang example lets the coder define a function as a variable which is then usable as an argument to another function without any special syntax tricks. CallOn2 just applies the function arg F to the literal number 2 and returns the result, which is just what we want in all these examples.

In Haskell:

(I haven't written about Haskell before now. It's purely functional, strongly typed with inferencing, and offers lazy (non-strict/non-eager) evaluation. Check it out. It has several implementations - I'll show it in hugs, a REPL shell.

Assuming this file CallOnTwo.hs:

add1 = (+) 1
callOnTwo f = f 2 

Executing hugs as follows:

$ hugs CallOnTwo.hs 
__   __ __  __  ____   ___      _________________________________________
||   || ||  || ||  || ||__      Hugs 98: Based on the Haskell 98 standard
||___|| ||__|| ||__||  __||     Copyright (c) 1994-2005
||---||         ___||           World Wide Web: http://haskell.org/hugs
||   ||                         Bugs: http://hackage.haskell.org/trac/hugs
||   || Version: September 2006 _________________________________________

Haskell 98 mode: Restart with command line option -98 to enable extensions

Type :? for help
Main> callOnTwo add1
3

What's going on here? The actual use of callOnTwo in the REPL example should be readable enough - it's quite similar to all of the other examples.

The lib file CallOnTwo.hs is a bit more interesting. Note the definition of add1 as (+) 1 - it leaves off the argument to add1. Rather than saying the equivalent of add1 of x is x plus one, it says (in Haskell) add1 is the function that adds one to whatever it gets.

This is what Haskell calls pointfree style. In the pointfree style, a coder leaves off terms from a definition when able. The resulting code is generally thought to be cleaner and more compact. It also lends itself well to groking function composition.

One further complication is that the + is in parentheses. This is because + is most commonly used as an infix operator, such that its arguments appear on either side, as opposed to Scheme's (+ x 1), where the function appears first (as is usual in Scheme), and the arguments follow. The wrapping in parentheses converts the traditionally infix + into a prefix function.

One could argue that this slight syntax massaging is roughly similar to Ruby's need for call, thereby angering fans of Ruby, Haskell, and Scheme simultaneously. Probably others too. Maybe F# fans. Who knows?

More Ruby:

In Ruby again, following the Object-Oriented nature of the language, we can do similar operations in which the functions are explicitly understood to be methods attached to specific objects. In this case, the Integer 1.

Assuming the existence of this file func_as_arg.rb:

class Integer
  def call_symbol_arg_on_2(first_class_proc_as_sym)
    2.send(first_class_proc_as_sym, self)
  end
end

We can then do operations in irb again.

$ irb -r func_as_arg.rb
irb(main):001:0> 1.call_symbol_arg_on_2(:+)
=> 3
irb(main):002:0> 1.call_symbol_arg_on_2(:-)
=> 1

With the results that you'd expect.

In JavaScript:

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

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

call_proc_arg_on_2(add1);
Number(100).call_proc_arg_on_2(add1);

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.

---

I split infinitives. If such things get you riled up, I suggest you read about scientific linguistics a bit more. A good starting point is Language Myths, edited by Laurie Bauer. In this particular case, the splitting was to clarify that easily modifies the use the use of the more-common block syntax in Ruby, rather than suggesting that easily modified the strength of the outweighing. Embedding the adverb within the verb is excellent for disamgiuation of this sort. Try it - you'll like it. Trust me.

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?

Ruby

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?

Lisp/Scheme

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.

Erlang

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.
#Fun
2> Add1(5).
6

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.

JavaScript

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.

So what's with the name?

I'm about to start writing a series of short posts, each about the question of whether procedures are first-class citizens in Ruby, as well as some other languages. Look for those starting in a few days. However, some folks might not be aware of the pun that inspired the name of this blog.

There may or may not be a legendary organization called The Knights of the λ Calculus. I wouldn't claim to call myself a wizard, nor do I primarily work in Lisp or Scheme, so I'm clearly not a member of such an illustrious group. However, I'll make frequent references to topics discussed in SICP, the Wizard Book, so I equally clearly have certain aspirations in this direction. Hence the blog name.