Independent Study: Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I

(This is one of a series of posts about papers I'm reading for an independent study with Prof. Evan Chang at the University of Colorado, Boulder. The format of this and subsequent papers will be similar to that of a review of a paper submitted to a conference. These are already-published papers, so I'll be writing with the obvious benefit of hindsight.)

Submission: Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part 1

Reviewer: Nicholas Dronen

Please give a brief, 2-3 sentence summary of the main ideas of this paper:

The author presents the basic symbols, syntax, and semantics of a Turing-complete programming language, LISP, providing compelling examples of the language's expressiveness. He then discusses how it is implemented on the IBM 704 computer.

What is the strength of this paper (1-3 sentences):

It describes a new programming language based in part on Church's lambda calculus which can be applied in both practical and theoretical domains.

What is the weakness of this paper (1-3 sentences):

Being such a seminal paper in the PL literature, it's hard to find fault with it. It is interesting that the author doesn't himself discuss deficiencies in the language or its implementation.

Evaluation

This paper is excellent. The author explains his ideas clearly and comprehensively.

The contemporary reader does have to adjust his vocabulary at times, because McCarthy's terminology is outdated — for example, where a contemporary paper would use the term memory cells, McCarthy says registers.

Novelty

To my knowledge, there was only one other functional programming language at the time of publication, IPL, but LISP was a big improvement. LISP's garbage collection is extremely useful to programmers, freeing them from having to manage memory explicitly.

Convincing

Extremely.

Worth Solving

This paper is seminal in part because it solves several problems at once.

Confidence

How confident are you in your evaluation of this paper?

Detailed Comments

This paper is exemplary in the literature of programming languages. It sets the standard for the formal definition of a programming language: present the basic symbols and syntax, define the semantics, discuss implementation issues.

I'm fascinated by the fact that the LISP function apply "plays the theoretical role of a universal Turing machine and the practical role of an interpreter." Since LISP is based at least in part on the lambda calculus, and the untyped lambda calculus is Turing-complete, it's fair to assume that the universality of apply follows as a consequence, but I'm not capable of providing a proof, nor, if I were capable of such, would I have time to do so. However, it's clear that the built-in substitution function subst has the same role as substitution in the lambda calculus. Another connection between LISP and formal representations of programming languages is that the function eval seems to be a handmaiden of the operational semantics of the language. The signature of the function is eval[e; a], where e is an expression to be evaluated, and a is list consisting of pairs, the items of which are, first, an atomic symbol, second, the expression for which the symbol stands.

And, practically speaking, apply is a function implemented in LISP that interprets LISP — highlighting the bootstrap problem that early computer science students grapple with, if only briefly: how do you compile a compiler? But further, one can view it as a virtual machine for LISP. The language's use of Polish notation reminds me of the stack-oriented nature of the Java virtual machine.

One of the questions I had from last week's paper is whether LISP was, as the paper described, actually capable of performing symbolic differentiation of functions. This paper provides a concrete answer. LISP is indeed capable of evaluating the derivative of a symbolic expression with respect to a variable. It's surprisingly simple, amounting approximately to replacing occurrences of the variable with ZERO or ONE, depending on whether they are being added or multiplied, respectively. So, for, example, the derivative of (PLUS 9 y) with respect to y is (PLUS 9 0) and the derivative of (TIMES 5 z) with respect to z is (TIMES 5 1).

Some of the built-in functions are named poorly: car is a mnemonic for "contents of the address part of register" and cdr stands for "contents of the decrement part of register." Today a language designer would give those functions names in harmony with their semantics, not their implementation. I believe this deficiency in early LISP was corrected at some point (with car replaced by first and cdr by rest), but I don't know what Scheme or Common LISP use.

Garbage collection does not occur intermittently. Rather, it occurs when the program needs memory but free memory has been exhausted. It does a simple reachability analysis. In the IBM 704, characters are 6 bits, and a machine word is 36 bits. A string of characters like "DIFFERENTIATE" is represented by a linked list of structures. The first field of each structure is a pointer to a 6-character memory cell. The second is a pointer to the cell of the next structure. The string "DIFFERENTIATE" decomposes to cells containing "DIFFER", "ENTIAT", and "E."

Internet of Things

Some quick thoughts on machine-generated and -consumed data (as opposed to documents) being the next phase of the development of the web. First thing that comes to mind is, this will require our infrastructure to be more intelligent, such as using feedback control systems to regulate the machine-to-machine flow of data. See, for example, "Black-Box Performance Control for High-Volume Non-Interactive Systems". Also, a human user navigating pages on the web (or using a search engine to go directly to the desired content) is a request-response style of interaction. HTTP does this quite well. However, data being generated by machines in the real world and consumed by machines suggests a publish-subscribe or at least a hybrid request-response, publish-subscribe style of interaction, a task for which protocols like XMPP are suited.

Independent Study: Early LISP History

(This is one in a series of posts about papers I'm reading for an independent study with Prof. Evan Chang at the University of Colorado, Boulder. I'll try to follow the same format in each post — a general discussion, followed by specific points of interest, and finally questions.)

Discussion

Herbert Stoyan's version of the early history of LISP faces hagiographic challenges. Some of the source material from which he works is undated, giving him the task of having to deduce its significance in the conception and development of LISP. The second of the AI Memos that John McCarthy, Nathaniel Rochester, and perhaps others wrote at the MIT AI Lab in the late 1950's is undated. In another case, a graduate student enrolled in one of Minsky's courses wrote the following during a guest lecture by McCarthy:

FORTRAN plus variable functions, composite functions (Church lambda), multiple functions, several valued functions of several variables, direct sum of functions, label portion of program with facility to make symbolic substitutions therein ...

This rather sketchy note, however, contains information of use to one of Stoyan's opening arguments. Citing this note, Stoyan mentions that this guest lecture is the first time that the lambda calculus appears in relation to the language that was to become LISP, reinforcing the point he makes at the beginning of his history — to wit, that LISP was not, as some believe, originally 'a clean "pure" language design in the functional direction which was comprised by AI-programmers in search of efficiency.' The original goal was simply a language to serve the ends of the Artificial Intelligence Laboratory at MIT. Indeed, Stoyan's history of the language shows that McCarthy arrived as the design of early LISP in a somewhat ad hoc manner. The language's built-in functions car (first element of list) and cdr (rest of list) were first implemented on top of an imperative FORTRAN. Furthermore, a language that inspired LISP was imperative, not functional. Quoting Stoyan,

It is one of the most important events in the history of programming that McCarthy, who was looking for a mathematical-logical programming language, found interesting elements of it in FORTRAN. He was fascinated by the idea of writing programs with "algebraic" means, i.e. mathematical expressions.

(The expressions McCarthy eventually settled on were symbolic expressions, or S-expressions, the subject of next week's paper.)

LISP as a Functional Language

While McCarthy didn't conceive LISP simply as an implementation of the lambda calculus, it is a mixed-paradigm language, containing both functional and non-functional features. A brief examination of the functional features of early LISP follows:

• Higher-order functions: early LISP has a built-in functions maplist, which takes a function as an argument, so clearly it has higher-order functions.
  
• Pure functions: I can't tell from the history whether invoking a function in early LISP could have side effects.
  
• Recursion: definitely.
  
• Strict vs. non-strict (lazy) evaluation: the implementation of LISP discussed by Stoyan used lazy evaluation, judging by the following sentence: "If we imagine a correct substitution function and accept the necessity for quoting all constants then there remains the well-known problem of free variables moved to wrong environments because of the lazy evaluation."
• Type systems and pattern matching: it's hard to determine based on the contents of the history, but my impression is that early LISP was untyped.
  

LISP as a Dynamic Language

Dynamic programming languages are loosely defined, more like one of Wittgenstein's family resemblances than one of Aristotle's essences. What follows are some characteristics of dynamic programming languages, and whether and/or how they exist in LISP:

• Eval: the ability to take a string representation of a program and execute (or evaluate) it. This concept originated with LISP. The fact that eval converts data (a string) into code (an execution) seems to be essential to dynamic programming languages in one respect — to wit, that what is executed does not exist at the beginning of a program's execution in a form that is directly executable by the underlying hardware. This is a characteristic of any language that executes in a virtual machine.
  
• Higher-order functions: Yes (covered above).
  
• Object runtime alteration: Objects do not exist in LISP, so this item does not apply.
  
• Closures: In contemporary usage, a "closure" requires lexical (i.e. static) scope. Scoping in early LISP was dynamic, a wildly different beast, so these don't exist.
  
• Continuations: Early LISP isn't purely functional, and the first paper on continuations was delivered in 1964 (a few years before the first implementation of LISP), so continuations were likely not part of early LISP. Further evidence for this is the fact that it had labels and iteration constructs: "Besides the `arithmentical (sic.) or replacement statement' the following kinds of statements were thought to be available.: A GO-statements (sic. -- likely "GOTO statement"), compound statements, statements for iteration, declarative statements (describing property lists) and statements for the definition of subprograms (and functions)."
• Reflection: it's not clear from the history whether early LISP had anything like Common Lisp's find-symbol.

Points of Interest

• One of the features of early LISP was symbolic differentiation and integration of functions? This might become clearer with next week's reading.
  
• Dynamic scoping — not carried over to Common LISP or Scheme.
  
• Parentheses determined by external constraint: "Therefore, the reason for selecting parentheses ... instead of brackets or braces was only a matter of chance because in 1958 the usual devices had only parentheses and nothing else."
• "It turned out that the realization of recursive function was the most complicate (sic) problem in translating the LISP-programs into SAP-routines." The question was how to implement the runtime stack. McCarthy considered following the example of IPL and — as implied by the history — implementing the stack as lists. He also considered implementing the stack as something private to each function. He finally settled on using a "public push-down list" for the runtime stack.
  

Questions

• The difference between maplist and apply is not obvious from Stoyan's discussion. I know that maplist takes a list L and a function F as arguments, applies F to each element of L, and returns a list L' containing of the return value of each invocation of F. In more recent languages (e.g. Python), maplist is called map. The meaning of apply is likely found in recent languages as well. Python has a (deprecated) apply function, which takes two arguments — a function F and a list A containing arguments to be passed as separate actual parameters to F. JavaScript's apply method (which is a callable property of a Function object, not a function properly speaking) with essentially the same signature. (JavaScript's Function object also has a call method, but unlike JavaScript's apply it takes a variable number of actual parameters instead of a single actual parameter. (I answered this question for myself before writing the discussion.)
  

Independent Study Schedule

This semester I'll be doing an independent study -- a survey of "dynamic languages" -- with Evan Chang. Each week I'll read a paper, and write a discussion of it, which he and I will use as a starting point for an hour-long weekly meeting. I'll post the discussion notes on this blog. The papers are listed here. Some of them are quite long and may have to be covered in halves.

1. Herbert Stoyan, "Early LISP History", date unknown, pages unknown
2. John McCarthy, "Recursive functions of symbolic expressions and their computation by machine, Part I", 1960, 34 pages
3. Carl Hewitt, Peter Bishop and Richard Steiger, "A Universal Modular Actor Formalism for Artificial Intelligence", 1973, 11 pages.
4. John Backus, "Can programming be liberated from the von Neumann style?", 1978, 28 pages
   
5. Ken Iverson, "Notation as a tool of thought", 1980, 22 pages
6. Pattie Maes, "Concepts and experiments in computational reflection", 1987, 8 pages
7. Alan C. Kay, "An Early History of Smalltalk", 1993, 40 pages
8. L. Peter Deutsch and Allan M. Schiffman, "Efficient implementation of the Smalltalk-80 system", 1984, 5 pages
9. David Ungar and Randall B. Smith, "SELF: The power of simplicity", 1991, 18 pages
10. Craig Chambers, David Ungar, and Elgin Lee, "An efficient implementation of SELF, a dynamically-typed object-oriented language based on prototypes", 1991, 38 pages.
11. Cartwright and Fagan. "Soft Typing", 1991, 16 pages.
12. Aiken, Wimmers, and Lakshman. "Soft Typing with Conditional Types", 1994, 10 pages.
    

Ten papers to read

For future reference, ten papers from the programming languages and programming canon.

My "Playtime"

In the mid- to late-60s, Jacques Tati produced and directed a kind of slapstick comedy about modern architecture, "Playtime." It was a commercial bomb, and bankrupted his family, but it's truly a great film. After seeing it a few times, it dawned on me that the office where I work -- which is all metal and glitter and glass -- could have been a set for the film. Compare Tati's set to mine.

Lonesome Prairie Dog

I got some cables and things today so I could start recording music in beginner's style, sitting at my kitchen table playing things into my laptop. The first song I wrote, probably two years ago, is "Lonesome Prairie Dog," a kind of cowboy song with some irregular meter, so far as I remember. It's the only thing I've written that I've bothered to name.

You can't upload MP3s to blogger, so I made a video of this using a recent photo. There's not a hidden musical gem at the end; GarageBand just padded the last forty-five seconds with silence. I've found that I've had to click the play button a few times to get it working, too, so don't give up.

I hope you like it.

Summer, Night

DSC_0004
Originally uploaded by ndronen

I was stunned by the shadow cast by a tree onto the sidewalk tonight. A few blocks away I was thinking about the shadows and about movies, and how the movies I enjoy most assume not that this is a world of objects, but that this is a world of light. Those directors and cinematographers and set designers and lighting people seem to understand that light pays objects courtesy by making it possible for them to manifest themselves to us. So I turned around and visited that tree again.

Functional Programming is Fun(ctional Programming)

The ball keeps rolling. Microsoft has has F#, a functional language for the Common Language Runtime (CLR, the .NET virtual machine) for a while. Then there's LINQ, the functionally-inspired generic data query mechanism built into C# 3.0. Now Microsoft is involved with Haskell, one of the better-known purely functional languages of recent vintage.

One reason for the increasing interest in and support of functional programming languages is that they have some characteristics that are very beneficial when attempting to scale to a large number of cores. In particular, since all data is immutable, there are no locks. Also, unlike imperative languages (which includes Java, despite its object-orientedness), programs written in functional languages say what to do, not how to do it, which gives the compiler and runtime system freedom to, say, run parts of a loop on different cores. Anders Hejlsberg, one of the designers of C#, talks about that aspect of functional languages here (starting around 20:45).

For applications that need to run efficiently on many cores, the general migration path I see is from using threads explicitly, to using tasks (e.g. Java's Executor framework, where the application doesn't explicity create threads itself), to writing in a concurrency-oriented fashion, whether in a purely functional language using some hybrid approach. For the hybrid approach, here's a write up of some ways to do concurrency-oriented programming in Java.

(This post is based on an email I sent to my group at work. It's a Java shop.)

Hang 'Em High

For such a crisp thinker as Willem Buiter, these words, with which I agree, are extremely harsh:

Too many bank insiders have exploited their monopoly of information and the control it bestows on them, to enrich themselves by robbing their shareholders blind. There has been a spectacular failure of corporate governance. Boards have foresaken their fiduciary duties. Surely, even the liability insurance taken out by board members ought not to shelter those who are guilty of, at best, such willfull negligence and dereliction of duty? Where are the class actions suits by disgruntled shareholders? Where are the board members in handcuffs?

Now that there is no meat left on the shareholder drumstick, the rogue managers and employees are going after a piece of the really juicy bird - the ever-patient tax payer. I hope they choke on it.

Governance lies as the heart of the mess. It was broken before the house of cards collapsed, and it's broken now, too, because the people responsible for the status quo are either still in power, or not on trial, or both.

I'm Looking Forward to This

Be Honest But Mysterious

Your boss wants to know where the reports that you were supposed to have on his desk are? Be honest with him: "I don't have them." But, instead of full disclosure, leave a little to the imagination: "And I'm not sure why." If he presses, be nice but firm: "I don't feel comfortable giving them to you yet, but I'm flattered that you're looking for them." "Who is this wild creature who doesn't have the reports?" he'll be wondering. Sure, it will feel uncomfortable for you at first, but, trust us, it'll drive him crazy. He'll probably have to contact you every hour. You won't be able to get rid of him!

First Impressions of Structural Computing

A lot of research is computer science is sort of boilerplate. Like when a graduate student incrementally improves a known solution to a given problem in an established area of research. Even when it's hard, that's the easy stuff, it seems. The hard stuff involves creating a new area of research altogether. That's what Peter J. Nürnberg is up to with his idea of "structural computing." So far, a couple of pages into a couple of his papers, and really not being familiar with the hypermedia corpus, the first thing that comes to mind is a data structure in which every element is connected to every other element by way of common data structures -- e.g. array, list, hash table -- so as to enable on-the-fly views of the data to be created. And this suggests the need to transform one view into another view arbitrarily, which in turn reminds me of category theory, data provenance, and the stuff that Benjamin Pierce has been working on, but not necessarily in that order and not to imply a relationship among those things that doesn't exist.

What was Universal thinking?

I love The Big Lebowski as much as the next guy, but the marketing department at Universal Studios really went too far with the their 10th Anniversary Limited Edition DVD. Come on. A bowling ball as a DVD case? Why not just give us the two disks with the bonus materials, etc, etc, and be done with it? What value does the bowling ball add exactly? What's worse, there's not even a symbol on the bottom of the plastic ball indicating how to recycle it.

And on the occasion of my 39th birthday, a colleague sent me this:

Once a cuckoo told me it was my birthday and flew away.
I asked myself Have you no regard for yourself to celebrate your birthday?
Then the cuckoo came back and told my brain Birthdays are for fathers and mothers.

Yesterday I turned 39. No surprises or revelations, just a sense of what it's like to keep growing older, an understanding that the tired phrase life goes on is tired because it's true. Of course, one's sense of time fluctuates, expanding and contracting, depending on the intensity of experience at that moment, depending on how much the world is defying or agreeing with you, but in all cases, things keep happening. Somewhat like no matter where you go, there you are. Both phrases are trivially true in an all-too-universal way. Perhaps the thing that distinguishes the old from the young is the knowledge that the truth of these phrases isn't trivial, because having a sense of how they are true only comes with experience, and experience only comes with age, and age implies death.

Back when Todd Mytkowitz and I were looking into the feasibility of using Amazon Web Services to run a not-for-profit scientific compute service, Todd explained the idea of the service to some scientists at a conference at the Santa Fe Institute. The most surprising part of their response was that a pay-as-you-go model doesn't always fit well with the way researchers spend money, since grant money comes with an expiration date; the money must be spent within some window of time. Since it's easy to justify the purchase of computing equipment, research money sometimes goes into a new, albeit small, compute cluster. Utility compute services like AWS are metered; using them doesn't require a large initial capital outlay. So it's not possible -- or at least hasn't been possible -- to park your money there. I think a similar dynamic is at work with corporate managers and directors, who are the marketing target of Amazon's push into the enterprise: the pay-as-you-go model just doesn't fit well with the budgeting practices of large institutions. Hence, ladies and gentelmen, Amazon's new pricing model.

The scary thing is I almost actually understood this.

Better Gmail is Not Better

CPU consumption by Firefox 3.0.7 with:

No pages loaded 1-3%
Old version of Gmail 1-3%
New version of Gmail 4-5%
New version of Gmail (with Better Gmail 2) 73-85%

It turns out that TestNG has built-in support for the functionality I just implemented for our JUnit tests.