TweetFollow Us on Twitter

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 Microsystems, 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 like

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 register.

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))
#<PROCEDURE>

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 (<? (string-length x) (string-length y))
("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)
                        1
                         (* n (fact  (- n 1))))))

#<PROCEDURE fact>

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)
(#<PROCEDURE> #<PROCEDURE> #<PROCEDURE> #<PROCEDURE> #<PROCEDURE> #<PROCEDURE> 
#<PROCEDURE> #<PROCEDURE> #<PROCEDURE> #<PROCEDURE> #<PROCEDURE>)

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 assignments to change the internal state of objects. Scheme currently provides no special support for object-oriented programming, but first class procedures can serve as objects with internal state.

Consider the problem of implementing a counter in Pascal as part of a simulation program. We could use a global variable as the counter, but that would make it hard to add new behavior to the counter later on. (For example, we might want to animate the counter in some way, so the counter should update the display every time it is incremented.) It would be better to implement the counter as a procedure. In Pascal, unfortunately, the state of the procedure must still be a global variable, as in the following Scheme code.

>>> (define n 0)
n
>>> (define counter
               (lambda ()
                     (set! n (+ n 1))
                    n))
counter
>>> (counter)
1
>>>(counter)
2
>>> (counter)
3
>>>(counter)
>>> n
3

One problem with using a global variable to hold the state of the counter is that we are likely to forget about it and then try to use a global variable with the same name for some other purpose. If we are lucky the compiler will complain. If unlucky, we will also forget to declare the other variable and will have a hard time finding out why the program won't work.

One reason we might forget to declare the other variable is that in Pascal the declaration, initialization, and use of a global variable are so widely separated. Ideally the state of the counter procedure should be a variable that is visible only within the procedure, is declared near the procedure, and is initialized near the procedure. We would like to have a syntax very much like:

>>> (define counter
           (let ((n 0))
                 (lambda  ()
                       (set! n (+ n 1))
                       n)))
counter

This actually works in Scheme. The (let ((n 0)) ...) syntax introduces a new variable n whose initial value is 0. The new variable is visible only within the lambda expression, and the value of that lambda expression -- an anonymous procedure -- is the value of the let expression. There's nothing special about the let expression; though Pascal has no equivalent, the let expression is roughly the same as block in Algol 60 or some of the newer C compilers. What's special is the lambda expression, because it evaluates to a first class procedure and first class procedures remember their non-local variables:

>>> (counter)
1
>>> (counter)
2
>>> (set! n 837)
837
>>> (counter)
3
>>> (counter)
4

As the assignment to n shows, the local state of the new counter procedure has nothing to do with the global variable n.

Suppose our simulation requires hundreds of counters. We could write hundreds of counter procedures, but then any change in the behavior of a counter would require us to change hundreds of lines of code. Why not write one procedure that creates new counter procedures? While we're at it, we'll make the initial state of the counter be a parameter to the procedure that creates counters.

>>> (define make-counter
             (lambda ()
                    (lambda ()
                         (set! n (+ n 1))
                                 n)))
make-counter
>>> (define c1 (make-counter 100))
c1
>>> (define c2 (make-counter  -5000))
c2

The local states of c1 and c2 are independent, because a new variable named n is created every time make-counter is called.

>>> (c1)
101
>>> (c1)
102
>>> (c1)
103
>>> (c1)
104
>>> (c2)
-4999
>>> (c2)
-4998
>>> (c2)
-4997
>>> (c1)

We have seen how to use first class procedures to implement objects with local state. The object we've been using as our example has a very simple behavior, however. What if there were several distinct operations on the object? One way to implement distinct operations is through message passing, which is similar to the way Smalltalk does it.

The code below introduces some new syntax. The case expression should be understandable. The (lambda (operation . args) ...) syntax is used to create a procedure that takes one or more arguments. The value of operation will be the first argument to the procedure, and the value of args will be a list of any remaining arguments. The car procedure extracts the first element of a list.

>>> (define make-counter
           (lambda (n)
              (rec self
                    (lambda (operation . args)
                         (case operation
                             ((count)  (set! n (+ n1) n)
                             ((report) n)
                             ((reset) (set! n (car args)) n)
                            (else (error "Bad operation on counter" self 
n)))))))

make-counter
>>> (define c3 (make-counter 40))
c3
>>> (c3 'count)
41
>>> (c3 'count)
42
>>> (c3 'report)
42
>>> (c3 'count)
43
>>> (c3 'reset 1000)
1000
>>> (c3 'report)
1000
>>> (c3 'count)
1001
>>> (c3 'count)
1002

Message-passing isn't the only way to implement objects with complex behaviors. It is sometimes more efficient to create a new procedure for each operation on an object. The make-counter procedure shown below returns a vector of three procedures.

>>> (define make-counter
           (lambda (n)
                 (vector
                 (rec count-method
                    (lambda  ()  (set! n (+ n 1)) n ))
                 (rec report-method)
                    (lambda () n))
                 (rec reset-method
                    (lambda (new-value)  (set! n new-value)   n)))))

make-counter
>>> (define c4  (make-counter 0)
c4
>>> c4
#(#<PROCEDURE count-method>   #<PROCEDURE report-method>  #<PROCEDURE 
reset-method>)

Scheme vectors are accessed using zero-origin addressing, so element 0 of the vector is the procedure corresponding to the count operation.

>>> (vector-ref c4 0)
#<PROCEDURE count-method>

The count operation takes no arguments. In Scheme we call a procedure of no arguments by enclosing it in parentheses:

>>> ((vector-ref c4 0))
1
>>> ((vector-ref c4 0)
2
>>> ((vector-ref c4 0)
3
>>> ((vector-ref c4 0)
4

Element 2 of the vector corresponds to the reset operation. It takes one argument:

>>> (vector-ref c4 2)
#<PROCEDURE reset-method>
>>> ((vector-ref c4 2) -100)
-100
>>> ((vector-ref c4 0))
-99
>>> ((vector-ref c4 0))
-98
>>>

The counter examples have shown that two features of object-oriented programming -- local state and message passing -- are provided for in Scheme without any special machinery, simply because procedures are first class citizens. Two other features of Smalltalk, namely inheritance and dynamic redefinition, can also be programmed in Scheme, but they are complicated enough to justify special machinery as in Smalltalk.

Numbers and procedures are not the only first class citizens of Scheme. Every Scheme value is first class. This is the ideal. Very few current programming languages achieve it.

Bibliography

Harold Abelson and Gerald Jay Sussman with Julie Sussman, Structure and Interpretation of Computer Programs, MIT Press and McGraw-Hill, 1985.

Abelson et al, "The Revised Revised Report on Scheme; or An Uncommon Lisp", MIT Artificial Intelligence Memo 848, August 1985.

Joseph Storey, Denstational Semantics; MIT Press, 1977.

Guy Steele Jr., Common Lisp, Digital Press, 1984.

Correction!

A couple of months ago we reported the capacity of cons cells the MacScheme environment can produce. Those numbers were slightly incorrect. Using a 512K Mac one may get 10,000 cons cells. With a 2 megabyte mac one can get over 100,000 cons cells.

MacScheme comes with a small spiral bound book containing the reference manual, while it is not intended to be a major reference for the language, it is very informative. Macsheme contains a debugger which allows the user to gain specific access to the "heap". When a procedure cannot be evaluated due to a mistake or typo, MacScheme goes to the debugger automatically. The user then analyzes the code using the debugger commands which are displayed after the debugger is entered. The user can turn this feature off if they want to. Parenthesis matching is done when entering the right side parenthesis. The corresponding left side blinks in inverted video once. There are lots of other nifty features in the editor and compiler and we hope to discuss them more in the near future.

MacScheme, we are told, has already been chosen as the standard Macintosh Lisp environment for the Computer Science departments of at least two major universities. The users at these schools have logged thousands of hours of use with only one (!) intentional bomb.

It is very ironic situation. MacScheme has what ExperLisp seems to be lacking, a somewhat object oriented environment, usable debugging facilities, a comparatively easy to get used to style of operation and best of all, extreme reliability. While ExperLisp allows the programmer to build windows, bunny and Quickdraw graphics, menu bars and all the other Mac (or Lisp Machine) like stuff into the programmers' product. These two environments will more than likely gravitate toward each other until they are complete. [When will one product combine both features?? -Ed. ]

ExperTelligence has been telling us since the release of ExperLisp that a developer's version will be released shortly (frankly, they should finish the current version first!!!). So far that hasn't happened and there seems to be no indication that it will. ExperTelligence seems more concerned with adding gimicks like Macintalk to ExperLisp. In the mean time Semantic Microsystems has told us that an add-on to MacScheme which will give access to Quickdraw is under developement. For the moment, I'd bet on MacScheme. [What about the rest of the toolbox? -Ed.]

In coming months... ExperOps5, NEXPERT (!) and more on Common Lisp procedures.

From Volume 2 Number 6:

Corrections

A couple of typos from the last column on MacScheme were identified by the author. The first was in one of the code samples using sort. The following is the correct code:

>>> (sort '("Even" "mathematicians" "are" "accustomed" "to" "treating" 
"functions" "as" "underprivileged" "objects")
 (lambda (x y)
 (or (<? (string-length x) (string-length y))
 (string<? x y))))

("as ...)

The second error was in the code defining the procedure make-counter. The code should have included the argument n as follows:

(define make-counter
 (lambda (n)
 (lambda ()
 (set! n (+ n 1))
 n)))

There was also an error in the third reference. The reference was supposed to read Joseph Stoy's Denotational Semantics of Programming Languages. Our thanks to Will Clinger of the Tektronix Computer Research Laboratory (and also of Semantic Microsystems).

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

BBEdit 11.1.1 - Powerful text and HTML e...
BBEdit is the leading professional HTML and text editor for the Mac. Specifically crafted in response to the needs of Web authors and software developers, this award-winning product provides a... Read more
CrossOver 14.1.3 - Run Windows apps on y...
CrossOver can get your Windows productivity applications and PC games up and running on your Mac quickly and easily. CrossOver runs the Windows software that you need on Mac at home, in the office,... Read more
Little Snitch 3.5.3 - Alerts you about o...
Little Snitch gives you control over your private outgoing data. Track background activity As soon as your computer connects to the Internet, applications often have permission to send any... Read more
OmniGraffle Pro 6.2.3 - Create diagrams,...
OmniGraffle Pro helps you draw beautiful diagrams, family trees, flow charts, org charts, layouts, and (mathematically speaking) any other directed or non-directed graphs. We've had people use... Read more
OmniFocus 2.2 - GTD task manager with iO...
OmniFocus helps you manage your tasks the way that you want, freeing you to focus your attention on the things that matter to you most. Capturing tasks and ideas is always a keyboard shortcut away in... Read more
Cocktail 8.4 - General maintenance and o...
Cocktail is a general purpose utility for OS X that lets you clean, repair and optimize your Mac. It is a powerful digital toolset that helps hundreds of thousands of Mac users around the world get... Read more
PDFKey Pro 4.3 - Edit and print password...
PDFKey Pro can unlock PDF documents protected for printing and copying when you've forgotten your password. It can now also protect your PDF files with a password to prevent unauthorized access and/... Read more
Kodi 15.0.beta1 - Powerful media center...
Kodi (was XBMC) is an award-winning free and open-source (GPL) software media player and entertainment hub that can be installed on Linux, OS X, Windows, iOS, and Android, featuring a 10-foot user... Read more
DiskCatalogMaker 6.4.12 - Catalog your d...
DiskCatalogMaker is a simple disk management tool which catalogs disks. Simple, light-weight, and fast. Finder-like intuitive look and feel. Super-fast search algorithm. Can compress catalog data... Read more
Macs Fan Control 1.3.0.0 - Monitor and c...
Macs Fan Control allows you to monitor and control almost any aspect of your computer's fans, with support for controlling fan speed, temperature sensors pane, menu-bar icon, and autostart with... Read more

Moleskine Timepage – Calendar for iCloud...
Moleskine Timepage – Calendar for iCloud, Google & Exchange 1.0 Device: iOS iPhone Category: Productivity Price: $4.99, Version: 1.0 (iTunes) Description: The most elegant calendar for your pocket and wrist, Timepage is a... | Read more »
QuizUp Gets Social in its New Update
Plain Vanilla Corp has released a new and improved version of their popular trivia game, QuizUp. The app now emphasizes social play so you can challenge friends from all over the world. [Read more] | Read more »
The Deep (Games)
The Deep 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Swipe Controls Delve into the deep in this retro rogue-like! Swipe to move your diver around and keep away from the enemies as you... | Read more »
Battle of Gods: Ascension (Games)
Battle of Gods: Ascension 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: TURN-BASED TACTICAL COMBATFight tactical battles against the forces of Hades! In Battle of Gods: Ascension you play... | Read more »
Shadowmatic's Latest Update Adds a...
Shadowmatic's shadowy shadow-ness is getting a little shadowy-er thanks to a recent update that adds an Arcade Mode. [Read more] | Read more »
Sunrise Calendar and Slack Have Assimila...
Wunderlist is perhaps one of the most populat and beloved productivity apps on the App Store - and now it's gone and incorporated itself into other useful services like Sunrise Calendar and Slack. [Read more] | Read more »
Crossy Road Devs Hipster Whale are Bring...
Hipster Whale, the minds behind the rather popular (and rather great) Crossy Road, have teamed-up with Bandai Namco to create PAC-MAN 256: an absolutely bonkers looking maze runner chaser thing. | Read more »
Meet the New Spotify Music
Spotify Music  has a lot going on. They're introducing 3 new modes to serve all your musical needs, with the "Now" start page  gives you curated playlists based on your particular tastes. As you listen the app will learn more about your tastes and... | Read more »
What the Apple Watch Gets Right, and Wha...
| Read more »
Celebrate PAC-MAN's 35th Birthday W...
BANDAI NAMCO Entertainment America is celebrating PAC-MAN's 35th anniversary by releasing updates for PAC-MAN and PAC-MAN Lite for iOS. [Read more] | Read more »

Price Scanner via MacPrices.net

Apple refurbished 2014 13-inch Retina MacBook...
The Apple Store has Apple Certified Refurbished 2014 13″ Retina MacBook Pros available for up to $400 off original MSRP, starting at $979. An Apple one-year warranty is included with each model, and... Read more
What Would the ideal Apple Productivity Platf...
For the past four years I’ve kept a foot in both the Mac and iPad camps respectively. my daily computing hours divided about 50/50 between the two devices with remarkable consistency. However, there’... Read more
PageMeUp 1.2.1 Ten Dollar Page Layout Applica...
Paris, France-based Softobe, an OS X software development company, has announced that their PageMeUp v. 1.2.1, is available on the Mac App Store for $9.99. The license can be installed on up to 5... Read more
Eight New Products For USB Type-C Application...
Fresco Logic, specialists in advanced connectivity technologies and ICs, has introduced two new product families targeting the Type-C connector recently introduced across a number of consumer... Read more
Scripps National Spelling Bee Launches Buzzwo...
Scripps National Spelling Bee fans can monitor the action at the 2015 Spelling Bee with the new Buzzworthy app for iOS, Android and Windows mobile devices. The free Buzzworthy app provides friendly... Read more
13-inch 2.5GHz MacBook Pro on sale for $120 o...
B&H Photo has the 13″ 2.5GHz MacBook Pro on sale for $979 including free shipping plus NY sales tax only. Their price is $120 off MSRP, and it’s the lowest price for this model (except for Apple’... Read more
27-inch 3.3GHz 5K iMac on sale for $1899, $10...
B&H Photo has the new 27″ 3.3GHz 5K iMac on sale for $1899.99 including free shipping plus NY tax only. Their price is $100 off MSRP. Read more
Save up to $50 on iPad Air 2, NY tax only, fr...
B&H Photo has iPad Air 2s on sale for up to $50 off MSRP including free shipping plus NY sales tax only: - 16GB iPad Air 2 WiFi: $469 $30 off - 64GB iPad Air 2 WiFi: $549.99 $50 off - 128GB iPad... Read more
Updated Mac Price Trackers
We’ve updated our Mac Price Trackers with the latest information on prices, bundles, and availability on systems from Apple’s authorized internet/catalog resellers: - 15″ MacBook Pros - 13″ MacBook... Read more
New 13-inch 2.9GHz Retina MacBook Pro on sale...
B&H Photo has the 13″ 2.9GHz/512GB Retina MacBook Pro on sale for $1699.99 including free shipping plus NY tax only. Their price is $100 off MSRP, and it’s the lowest price for this model from... Read more

Jobs Board

*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
*Apple* Watch SW Application Project Manager...
**Job Summary** The Apple Watch software team is looking for an Application Engineering Project Manager to work on new projects for Apple . The successful candidate Read more
Engineering Manager for *Apple* Maps on the...
…the Maps App Team get to take part in just about any new feature in Apple Maps, often contributing a majority of the feature work. In our day-to-day engineering work, we Read more
Senior Software Engineer - *Apple* SIM - Ap...
Changing the world is all in a day039s work at Apple . If you love innovation, here039s your chance to make a career of it. You039ll work hard. But the job comes with Read more
Lead *Apple* Solutions Consultant - Retail...
**Job Summary** Job Summary The Lead ASC is an Apple employee who serves as the Apple business manager and influencer in a hyper-business critical Reseller's store Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.