Using First-Class, Higher-Order, and Anonymous Procedures (Hunk L)

==================================================================
Hunk L starts here:
==================================================================

In this section, we'll play with Scheme's procedures, to illustrate

• first class procedures, which are normal data objects in the language,
• higher order procedures, which can take procedures as arguments and return them as values, and
• anonymous procedures, which can be created and referred to via pointers, without giving them names.

I'll just briefly demonstrate those ideas for now; later programming examples will show how they're really useful.

First-Class Procedures

Scheme procedures are first-class objects in the language; you refer to a procedure in the same way you refer to any other object, via a pointer. A "procedure name" is really just a variable name, and you can do the same things with "procedure" variables as with any other variable. There's really only one kind of variable in Scheme, and it's type is "pointer to anything."

When we "define a procedure" in Scheme, we're really just defining a variable and giving it an initial value that's (a pointer to) a procedure object.

The procedure defining syntax with parentheses around the procedure name (and argument names) is really just syntactic sugar, i.e., a convenient way of writing something that you could do in another way.

For example,

Scheme>(define (double x)
          (+ x x))
#void

is exactly equivalent to

Scheme>(define double
               (lambda (x)
                  (+ x x))
#void

Try this latter version in your system. Notice that what you're doing is just defining a variable named double and initializing it with the result of the second expression, a lambda expression.

lambda is the real procedure-creating operation. It's a special form, because it lets you define a new procedure rather than calling an existing procedure in the normal way. lambda creates a procedure object and returns a pointer to it.

(The predicate procedure? can be used to tell if an object is a procedure.)

You can call the double procedure created this way in exactly the same way as one created with the sugared procedure-definition syntax.

Scheme>(double 3)
6

Recall how procedure calls really work. When you call a named procedure, e.g., (double 3), the procedure name is really just a reference to a variable. The first position in the procedure call form is just an expression that's evaluated like any other. In this case, we're using the name double as an expression, effectively saying "look up the value of double."

Try this

Scheme>double
#<procedure>

Notice that we didn't put parentheses around double, so we're not calling it--we're fetching the value of the variable double. What you see on your screen may vary, but it's your system's printed representation of a procedure object. Take a look at it, because you'll want to be able to recognize procedure objects in data structures.

(The printed representation may include the name of the procedure; don't be misled by this. Procedures don't really have names--they're just data objects you can have pointers to, as I'll explain shortly. Your system your system may put a name inside the procedure when you use the procedure definition syntax, but it's just an annotation saying what the procedure's original name was--i.e., when it was first defined.)

We can call a procedure in other ways, though--the first subexpression of a procedure call can be any expression we want, as long as it returns a procedure. That expression is evaluated just like the argument expressions--after it and the argument expresssions are evalutated, the resulting procedure is called with those argument values.

Scheme>(define list-holding-double (list double))
#void

Scheme>list-holding-double
(#<procedure>)

Scheme>((car list-holding-double) 5)
10

What we did here was to create a list holding the procedure formerly known as double, and looked at that list. Then we called that procedure by using the expression (car list-holding-double) as its "name."

What this shows is that procedures are really anonymous, that is, a procedure doesn't have a name in a direct sense. There are just expressions we can refer to it by, if those expressions result in pointers to the procedure.

We can create procedures without normal names at all, by just using lambda. Let's create another doubling procedure by just evaluating a lambda expression:

Scheme>(lambda (x) (+ x x))
#<procedure>

The lambda expression just created a procedure and returned a pointer to it, and Scheme displayed it however your system does it. We didn't keep a pointer to the procedure, so we can't call it now. The procedure is gone and the garbage collector will clean it up.

We could try again, creating a procedure and keeping a pointer to it in a named variable. More interestingly, we can just hand the pointer to a procedure call, and call it without ever giving it a name.

Scheme>((lambda (x) (+ x x)) 6)
12

It may not look like it, but this is just a procedure call expression, where the "name" of the procedure is a lambda expression to create the procedure we need, and its argument is 6. Note the nesting of parentheses--this is just like (double 6), except that we give the "definition" of the procedure to call, instead of its name.

Later we'll show why using lambda directly is often much more convenient than having to name all of our procedures. I'll also explain why lambda is the most important special form in Scheme--it is so powerful that most of the special forms can easily be translated into it.

(You might be concerned that creating a procedure and just using it once is very expensive, but it turns out not to be--I'll explain that later, too. For now, don't worry about it.)