All Databases MacTech Vol 02-1986

MacScheme

Volume Number: 2

Issue Number: 1

Column Tag: Lisp Listener

First Class Citizens in MacScheme

By Andy Cohen, Hughes Aircraft, MacTutor Contributing Editor

This month the Lisp Listener will feature an in depth description of MacScheme.

This description comes from William Clinger of Semantic Micro systems, the developers

of MacScheme.

Imagine a programming language in which every number must be given before it

can be used in an expression. For example, you could not print the circumference of a

unit circle by saying "write (2 * 3.14159)"; you would instead have to say something

let two = 2

let pi = 3.14159

two_pi = two * pi

foo (two_pi)

Of course, such a language would be very clumsy. Nobody would want to use it. A

student of programming languages would say that the problem with the language is that

it treats numbers as second class citizens.

First class citizens have the right to remain anonymous. They have an identity

that is independent of any names by which they may be known. Further more they have

the right to participate in any activity sponsored by the language. If the language has

arrays, then any first class citizen can be an element; if the language has assignments,

any first class citizen can be stored in a variable. If the language can pass arguments to

procedures, any first class citizen can be passed; if procedures can return results, any

first class citizen can be returned.

Numbers are so important that they are first class citizens of nearly all

programming languages. In some languages numbers are the only first class citizens. In

many languages the only first class citizens are those that are easy to fit into a machine

Arrays are important and have been around a long time, but how many

programming languages really treat arrays as first class citizens? Also, how many

languages allow you to create a new array without giving it a name? Do they allow you

to return an array (not just a pointer to the array) as the result of a procedure call?

Do they allow arrays to appear on the right hand side of an assignment statement? First

class arrays as in APL have a radical impact on programming style.

Procedures have been around a long time also, and most programming languages

allow procedures to be passed as arguments to other procedures. Do they allow you to

create a new procedure without giving it a name? Can you return a procedure as the

result of a procedure call? Can a procedure appear on the right hand side of an

assignment?

The most accessible of the languages with first class procedures are the two

modern dialects of Lisp known as Scheme and Common Lisp. The following contains

samples of First Class procedures using MacScheme.

An anonymous procedure is written as a lambda expression beginning with the

keyword lambda, followed by a list of arguments, followed by the procedure body. The

lambda expression evaluates to a procedure.

>>> (lambda (x) (+ X 12))

What can you do with an anonymous procedure? Anything you can do with a

named procedure. For example, the second argument to the sort procedure that defines

an ordering on the objects to be sorted. If you already have a procedure that defines the

ordering you want, you can refer to it by one of its names:

>>>(sort '(1 3 5 7 9 8 6 4 2 0) >?)

(9 8 7 6 5 4 3 2 1 0)

>>>(sort '(1 3 5 7 9 8 6 4 2 0) >)

(9 8 7 6 5 4 3 2 1 0)

If you don't already have the procedure you want, you can create one with a

lambda expression. There's no reason why you should have to think up a name for it:

>>> (sort '("Even" "mathematicians" "are" "accustomed" "to

"treating" "functions" "as" underprivileged" "objects")

(lambda (x y)

(or (

("as" "to" "are" "Even" "objects" "treating" "functions"

"accustomed" "mathematicians" "underprivileged")

Names come in handy when you want to write a recursive procedure, however.

The rec expression is convenient for that purpose. In the example below, the (rec fact

...) syntax introduces a new variable named fact whose value is the value of the lambda

expression.

>>> (rec fact

(lambda (n)

(if (zero? n)

(* n (fact (- n 1))))))

The variable named fact is visible only within the lambda expression, however.

If we were now to ask for the value of fact, Scheme would say that fact is an undefined

variable. Thus the result of the rec expression is just as anonymous as the result of a

lambda expression. Admittedly its printed representation includes a name, but that

name is nothing more than a comment generated by the Scheme system as it attempts to

be helpful.

We can use the recursively defined anonymous procedure as the first argument

to the map procedure, which will call the procedure on every element of its second

argument and return a list of the results:

>>> (map (rec fact (lambda (n) (if (zero? n) 1 (* n (fact (- n

1))))))

'(0 1 2 3 4 5 6 7 8 9 10 11 12))

(1 1 2 6 24 120 720 5040 40320 3629880 3628800 39916800 479001600)

In MacScheme, the map procedure is also called by its traditional name mapcar.

The define expression below creates a new global variable named call-on-every whose

initial value is the contents of the old variable map -- that is, the map procedure.

>>> (define call-on-every map)

call-on-every

If we want to create a procedure and a variable to hold it, we create the

procedure using lambda expression and we create the variable using a define

expression:

>>> (define cube (lambda) (x) (expt x 3)))

cube

>>> cube

#,PROCEDURE cube>

>>> (map cube '(o 1 2 3 4 5 6 7 8 9 10))

(0 1 9 27 64 125 216 343 512 729 1000)

If you don't like writing (define cube (lambda (x) (expt x 3))) when other

dialects of Lisp will let you suppress the lambda by writing (define (cube x) (expt x

3)), don't despair. Scheme also allows the alternative syntax. I am avoiding the

alternative syntax because it obscures the distinction between the anonymous

procedure and the name of the variable in which it is stored.

Since procedures are first class citizens, they can be returned as the results of

calls to other procedures. The power procedure defined below takes an argument y and

returns an anonymous new procedure. The new procedure takes an argument x and

returns x raised to the y-th power.

>>> (define power

(lambda (y)

(lambda (x)

(expt x y ))))

power

>>> (power 3)

#>PROCEDURE>

>>> (map (power 3) '(0 1 2 3 4 5 6 7 8 9 10))

(0 1 8 27 64 125 216 343 512 729 1000)

>>> (map (power .5) '(0 1 2 3 4 5 6 7 8 9 10))

(0.0 1.0 1.41421 1.73205 2.0 2.23607 3.44949 2.64575 3.82843 3.0

3.16228)

The cube procedure could have been defined using power.

>>> (define square (power 2))

square

>>> (map square ' (0 1 2 3 4 5 6 7 8 9 10)(0 1 444 9 16 25 36 49 64

81 100)

Since procedures are first class citizens, we can create a list of anonymous

procedures that will raise their argument to one of the powers 0 through 10:

>>> (map power '(0 1 2 3 4 5 6 7 8 9 10)

(# # # # #

# # # # #

We can apply every procedure in that list to the integer 2:

>>> (map (lambda (f) (f 2))

(map power ' (0 1 2 3 4 5 6 7 8 9 10)))

(1 2 4 8 16 32 64 128 256 512 1024)

I hope that this extremely simple and artificial example has suggested the new

programming styles that become possible when a language treats procedures as first

class citizens. The possibilities are both liberating and dizzying. There is no reason to

be fancy for the sake of fanciness, but it is often true that intelligent use of first class

procedures will simplify an otherwise intimidating program.

So far none of the examples have used any assignment statements. Assignments

are used far less often in Scheme and Lisp than in mainstream programming languages

like Pascal. It is quite practical to write major programs in Scheme without using a

single assignment statement. Such programs are said to be written in the functional

style. When a program is written in the functional style, every procedure can be

specified entirely by the relationship between its arguments and its results. In the

absence of assignments (and other side effects such as I/O), that relationship is a

simple mathematical function -- it never changes.

Object-oriented programming, as epitomized by Smalltalk, relies heavily on

Referenced by (16):