Universal Function

Lisp was an early language. These days everyone and his brother has a new language, but Lisp was the first of its kind. John McCarthy, mathematician that he was, wanted to prove that his new language was universal. He broke this down into two steps.

First, he showed that S-expressions — the list structure representation of Lisp — could faithfully represent Church’s lambda expressions. This is kind of taken for granted now, but McCarthy made the effort to prove it. Church had already proven that lambda expressions could represent any computable function, so McCarthy had a proof that S-expressions, too, could represent any computable function.

Then, he showed that his language could implement a universal function. A universal function is a function that can emulate any other function. If you have a universal function, you can emulate any other function, so you can compute any computable function. A universal function takes two arguments, a specification of what function to emulate and (a list of) some inputs. It returns the same value as if the function had been called with those inputs.

McCarthy’s universal function took a function specification in the form of a lambda expression and a list of arguments. It binds the arguments to the formal parameters of the lambda expression, the performs a recursive descent evaluation of the body of the body of the lambda expression. McCarthy called his universal function APPLY. By writing APPLY in Lisp, McCarthy showed that Lisp was universal. (EVAL began its existance as a helper function for APPLY).

To tell the truth, this is pretty studly: McCarthy proved that his new language was universal by writing the first meta-circular evaluator in it. These days, people invent languages by throwing together enough features until they have something that looks like a language. It’ll probably be universal — universality turns out to be fairly easy to achieve — but how do you know? If you can write a Lisp interpreter in your language, it’s universal.