TweetFollow Us on Twitter

Church Numerals
Volume Number:7
Issue Number:6
Column Tag:Lisp Listener

Going Back to Church

By André van Meulebrouck, Chatsworth, CA

“Scheme is a very clear language and its tutors follow a zen philosophy. Anything unessential or controversial (i.e. not so well understood) is thrown away. The latest Scheme report is an admirable document and as semantical analysis progresses, slicing molecules then atoms and after that quarks I dare say that the revised report on Scheme will converge to l-calculus.” Christian Queinnec [Queinnec, 1990].

This article will attempt to prompt interesting insights into recursive functions, and evaluation strategies via looking at an alternate numeric system (Church numerals). It also touches on various concepts such as object oriented programming, dynamic scoping, and lazy streams.

(Sneak preview: imagine a numeric system wherein the operations; addition, subtraction, multiplication, and exponentiation all take roughly the same amount of time to compute regardless of the size of the numeric arguments! Church numerals accomplish this by returning functions that “promise” to do the computation later, yet these “promises” are still bona fide Church numerals that can be used in further computations. There are of course trade-offs from such “laziness”. For instance, when Church numerals are converted to regular numbers, computations that weren’t done previously must be completed. Tools are provided for the reader to explore these trade-offs.)

A Hope for the Future?!?

Perhaps you might think of Alonzo Church’s l-calculus (and numerals) as impractical mental gymnastics, but consider: many times in the past, seemingly impractical theories became the underpinnings of future technologies (for instance: Boolean Algebra).

Perhaps the reader can imagine a future much brighter and more enlightened than today. For instance, imagine computer architectures that run combinators or l-calculus as their machine instruction sets.

Imagine further that different models will be available. For instance one might be a really cheap, simple chip that will implement only pure l-calculus as its instruction set. This is the chip that manufacturers might want to use for controlling toasters or electrical systems in your car (space ship?). Without numbers, and with only limited need of integers, perhaps Church numerals might have practical import! Of course, the more expensive chips would probably have an extended l-calculus and full numeric capabilities. Perhaps the trade-off between a pure l-calculus chip versus an extended l-calculus chip would be vaguely analogous to the RISC (Reduced Instruction Set Chip) versus CISC (Complex Instruction Set Chip) controversy. For instance, the pure l-calculus chip might be clocked faster by virtue of greater simplicity, and thereby might offer advantages over the extended l-calculus chip, there again tempting uses of Church numerals or other “soft” numeral systems. (“Soft” here meaning “software” as opposed to “hard” meaning “hardware” based.)

In reality, combinator reduction machines have been built already and research on them continues. [Peyton Jones, 1987] briefly describes various projects devoted to parallel (combinator) reduction machines. [Ramsdell, 1986] describes “the Curry Chip” which is a combinator reduction machine in VLSI.

The “Minimalist” Game

All conjectures aside, I think the most compelling motivation for studying l-calculus is the “minimalist” game.

I was introduced to a minimalist game by an ex-Soviet Russian instructor who would allow students a severely restricted set of words and grammatical constructs, then ask questions. The idea was that one’s expressive capability is not so much posited in how much one knows, but in how cleverly one wields what one knows. He was wont to point out that you are more likely to reveal yourself as a foreigner when you overextend your limits by trying to use grammatical constructs and words you aren’t comfortable with, than when you speak simply but correctly. Likewise, I propose l-calculus as a minimalist game for Computer Science.

One observation from playing the minimalist game in Russian: what makes this game hard or easy isn’t so much how limited the number of “primitives” is but rather how powerful they are. I claim l-calculus gives us (perhaps) the fewest possible primitives, and, they are of supreme quality.

Recap

In the last article we covered a lot of ground--(re)consider the following.

Object oriented programming: The combinator versions of car, cdr, and cons make use of message passing: cons making a tuple object, and car and cdr do their thing by passing in messages to that object. While this use of message passing might seem primitive, it’s actually quite flexible and powerful, because the object doesn’t have to have a static knowledge of what possible messages could be passed in: the messages could be arbitrary functions. (The action taken on the message is to run the message itself!)

Here’s how a message passing example of car, cdr, and cons could be implemented in Scheme (see [Abelson et al., 1985] for similar).

(Scheme’s case statement is basically like case statements in other languages, except that the selectors are enclosed in parens. set-car! and set-cdr! are destructive operators to change those respective fields [Rees, et al.,1986].)

;1

MacScheme™ Top Level 
>>> 
(define my-cons 
  (lambda (x y)
    (lambda (message . args)
      (case message
        ((car) x)
        ((cdr) y)
        ((set-car!)
         (set! x (car args)))
        ((set-cdr!)
         (set! y (car args)))
        ((?)
         ‘(car cdr set-car! set-cdr! ?))
        (else
         (error “my-cons:  bad message” message))))))
my-cons
>>> (define my-car
      (lambda (object)
        (object ‘car)))
my-car
>>> (define my-cdr
      (lambda (object)
        (object ‘cdr)))
my-cdr
>>> (define my-set-car!
      (lambda (object to-what)
        (object ‘set-car! to-what)))
my-set-car!
>>> (define my-set-cdr!
      (lambda (object to-what)
        (object ‘set-cdr! to-what)))
my-set-cdr!
>>> (define foo (my-cons ‘a ‘b))
foo
>>> (my-car foo)
a
>>> (my-cdr foo)
b
>>> (my-set-car! foo 3)
3
>>> (my-car foo)
3

(Note: What the user types at the MacScheme prompt >>> is shown in italics. MacScheme responses are in boldface.

Code alluded to but not described in the text can be found at the end of the article.)

Lazy evaluation: the ideas behind Scheme’s force and delay were shown via thunks (lambda forms of no arguments). Our delay consisted of thunkifying the object to be delayed, and our force consisted of the function force-a-thunk which simply invoked the thunk with no arguments. force and delay are important because they are used to create lazy streams [Abelson et al., 1985].

Closures, free variables, lexical scoping and higher-order functions: Combinators nicely motivate a tour de force introduction to these issues because combinators rely on them so heavily.

Unraveling the secrets of Church numerals

The slick thing about Church numerals is that they are essentially pre-initialized for loops ready to have a function and argument passed in.

Internally, a “canonical” Church numeral looks like:

;2

(lambda (f)
  (lambda (x)
    (f (f (f ... x))))))

wherein there can be any number of f’s (including none) applied to the argument x.

Since Church numerals are functions, they can be invoked (run). When invoked, a Church numeral will want to consume two arguments; the first being a function which will get bound with its parameter f. Then, it will return the function (lambda (x) ...) as its result. (lambda (x) ...) will then wait to be invoked on an argument, which it will bind to its parameter x. It will then run the (f (f (f ... x))) part, which is to say it will apply the function f to the argument x as many times as there are f’s. (The value of the Church numeral is determined by how many f’s get applied to the argument. If no f’s get applied, that represents 0.)

Note that there is nothing recursive about a Church numeral. It simply “iteratively” applies a function to an argument a predetermined number of times depending on how many nested f’s are specified in the (lambda (x) ...) part.

We can pass any function we want into a Church numeral! If we pass in the Scheme function 1+ for the function, then pass in 0 for the argument, the Church numeral will sum itself up: ((<Church numeral> 1+) 0) => <regular number>. (The process of running of a Church numeral on a function and an argument is herein called “unraveling”.)

Basically, Church numerals are a game of unraveling, using different things for the arguments.

For instance we can unravel, using a tuple maker for the function argument, or even another Church numeral! (Exercise for the reader: What arithmetic function gets implemented when we unravel using a Church numeral for the function argument? What happens if we “partially unravel” a Church numeral (invoke it on a function, but not on an argument) then use that as the function to some other Church numeral?)

To recurse, or not to recurse.

That is the question.

Previously, the use of recursion to express com-pred was likened to using a bulldozer to dig a hole for petunias. What about the recursion in com-fact itself?

It turns out recursion is unnecessary there too. The same style trick used in com-pred can be used in com-fact : create tuples that contain the result in the car field and the number we’re on in the cdr field. (See pred-style-fact in file “stuff.sch”.)

The initial tuple would be created by: (cons 1 1). The tuple maker would return a new tuple that has (* (car tuple) (cdr tuple)) in the car field and (succ (cdr tuple)) in the cdr field. The nesting of function calls in a Church numeral can then provide the correct number of function invocations of the tuple maker.

How about using the com-pred trick in implementing com-quo ? Although Church numerals are like for loops, they do have the number of iterations the loop can do “hard wired” into each numeral. In the case of computing a quotient, we want to find out how many times a divisor can be subtracted from a dividend. When we find out, we call the result the quotient. Unfortunately, we don’t know ahead of time how many times to perform the subtraction. (That’s precisely what we’re trying to find out.) Therefore, we need a way to get an unpredetermined number of iterations, or, we need to find a way to “blow out” of function calls prematurely--we could then attempt to do the subtractions dividend times and blow out when the remainder is less than the divisor. (Question for the Überprogrammer: do we have a way to blow out of recursive calls prematurely in l-calculus? How about in Scheme?)

Recursion: A problem that keeps coming back to you.

In the last article, I posed the question of other ways to get the effect of recursion other than the Y combinator and by using state (i.e. using set! plus let to get letrec).

Let’s consider the problem again. You want to know your own definition while you’re inside your own definition. How could we achieve that? For that to happen, we’d have to have our own definition inside our own definition. How can we get our own definition inside? How do we normally get information inside a function? By passing it in!

So, instead of (define fact (lambda (n) ...) we want (define fact (lambda (f n) ...) and we must pass the fact definition in so that it will get bound with f [Dertouzos et al., 1974] (Also [Gabriel, 1988]). The recursive call will now look like: (f f (1- n)) instead of (fact (1- n)). The initial call will get set in motion like this: (fact fact 5). (See recursionless-fact in file “stuff.sch”.)

Note that this method of recursion elimination requires actually tweaking the function we’re eliminating recursion on. Specifically, it makes an n-arity (“arity” refers to the number of arguments a function expects) function into an n+1 arity function. Y requires us to perform an abstraction on any function we want to eliminate recursion from, but abstraction merely encloses it in another lambda form; it doesn’t alter the “guts” of the function itself.

Note that neither this trick, nor Y alleviates the need for a stack (at some lower level). Invoking lambda forms on arguments requires a stack (at least the way we’re doing it). (Question for the reader: if we implement a l-calculus interpreter which does everything in a purely syntactic fashion would we still need a stack?)

Überprogrammer question: Are there any other ways to get recursion, or have we covered them all?

Dynamic Scoping

I know it’s hard to believe now, but once upon a time, LISPs scoped dynamically. That is to say free variables derived their meanings from their callers’ environments rather than parental environments (“environment of definition”).

Our minimalist game would be in grave danger with dynamic scoping because when you pass around a function that has free variables in it, there’s a good chance you’ll snag a variable of the same name in a caller’s environment rather than in the (usually) intended parent’s environment.

Here’s an example to illustrate the difference between dynamic and lexical scoping. Below returns 5 because Scheme scopes lexically, but would return 3 if scoping were dynamic.

;3

>>> (define x 5)
x
>>> (define foo 
      (lambda ()
        (fido 3)))
foo
>>> (define fido 
      (lambda (x)
        (fifi)))
fido
>>> (define fifi
      (lambda ()
        x))
fifi
>>> (foo)
5 

If you recall from the previous article, I mentioned how scoping behaves rather oddly once the global (top level) environment is reached. For instance, you can mention functions and/or variables that don’t exist when defining something as long as you define the missing things before you invoke anything that uses them. Do you think it’s fair to say that modern LISPs scope lexically until the top level, at which time scoping becomes dynamic?

Recursion via lazy evaluation?

In trying to answer the open-ended question of what other ways recursion can be expressed other than Y, assignment, and passing the needed function as an argument, one might be tempted to think lazy streams might help.

Consider for instance this lazy stream [Abelson et al., 1985].

;4

>>> (define ones (cons 1 (lambda () ones)))
ones
>>> (car ones)
1
>>> (car (force-a-thunk (cdr ones)))
1
>>> 
(car (force-a-thunk (cdr (force-a-thunk (cdr ones)))))
1

How about if we went back to the letrec via let plus set! example from the previous article, and thunkified the recursive call to try to get the same sort of behavior that the ones example exhibits. Will it work?

No, because the reason the ones example works is not entirely due to lazy evaluation. It relies on peculiarities of the top level. This can be shown more clearly by converting the ones example into a local (rather than global) piece of code and changing names (lest we inadvertently grab something that already exists).

;5

>>> (let ((my-ones (cons 1 (lambda () my-ones))))
     (car (force-a-thunk (cdr my-ones))))
ERROR:  Undefined global variable
my-ones

Entering debugger.  Enter ? for help.
debug:> 

Y curry?

Notice how applicative-order-y assumes that the function it’s going to be applied to is a function of one argument. What happens if we want to use Y to get rid recursion in functions that have more than one argument?

This is no problem--currying takes care of this, because all combinators only have one argument anyway. If there are additional arguments, they can’t be “seen” until one argument is consumed, at which time one more parameter will be ready to take an argument. In this way, they are like retractable claws! They stay out of the way until they are needed.

If we didn’t use currying we would have to have a different version of applicative-order-y for each arity we want to handle (i.e. one version for functions of one argument, another version for functions of two arguments, etc.).

(Another approach would be to make use of a variable argument mechanism as is present in Common LISP but that violates our draconian adherence to combinators and perhaps seems less uniform, elegant, and simple.)

Spatial considerations of Church numerals

An observation: Church numerals can take a lot of space if representing n requires n function calls.

Instead, we could find out what the prime factors of n are, then make a Church numeral from multiplying those primes together, with exponentiated factors exponentiated!

Plan: write a function primes that computes the prime factors of a number, then use it to make more space efficient Church numerals. (See file “primes.sch”.)

>>> (primes 32769)
(331 11 (3 . 2))

In the above example, we find 32,769 consists of prime factors 331, 11, and 3 to the 2nd power. Thus we could make the Church numeral for 32,769 by multiplying 331, 11 and the exponentiation of 3 to the 2nd power. The number of nested function calls will now be 331 + 11 + 3 + 2 = 347. Contrast this with 32,769 nested function calls.

To make these type of Church numerals, use the function number->compact-church (see file “primes.sch”).

Speeding up Exponentiation of Regular Numbers

An aside: Exponentiation can be made more efficient for regular numbers (in a way that’s vaguely reminiscent of Church numeral composition). Since 2^4 is really 2^2 * 2^2, we can compute 2^2 and multiply that result together, and likewise, 2^2 is really 2^1 * 2^1 , etc. [Abelson et al., 1985], [Knuth, 1981]. This saves having to do a lot of recomputations. For a number to an odd power, we do: m * m^(n - 1). For example, 2^5, that is nothing more than 2 * 2^4. So, in the general case of m^n, rather than multiplying m together n - 1 times, we can use a divide and conquer algorithm, whereby we divide n in half until n becomes 0, then multiply all the intermediate results together. (See function pow in file “primes.sch”.)

(Illustration: the divide and conquer strategy creates a tree, but only concerns itself with the encircled parts. When the recursion bottoms out, the multiplications begin; squaring 2^1 to give 2^2 which then gets squared to give 2^4.)

How many multiplications will the divide and conquer strategy require? The mathematical function that answers the question: “How many times can you divide a number by 2” is the log function wherein the base of the log is what you’re dividing by. So, for us it would be log to the base 2 of n: log2n . In the below example, the number of multiplications will be log2200. On a calculator that has an “ln” key but no “log” key, this can be computed using natural logarithms (logs to the base e) as follows: ln(n) / ln(base) = ln(200) / ln(2) = 7.x. Contrast that with 199 multiplications!

>>> (pow 2 200)
1606938044258990275541962092341162602522202993782792835301376

Temporal considerations of Church numerals

Whereas regular numbers do computations completely when an operation is requested, many Church numeral arithmetic operations are “lazy” in that they do as little work as possible until being forced into completing the job (i.e. when unraveling them). Specifically, they return a function which “promises” to do the computation should the numeral ever get unraveled.

Functions that don’t do any computation at computation time are efficient “computers” (herein, “computer” refers to a numeral’s behavior at computation time), and such functions take roughly the same amount of time to compute results, regardless of the size of the numerical arguments (which are simply pointer references within a closure).

The downside to this way of doing things is that Church numerals can be gluttons to “unravel”. And when we convert Church numerals to regular numbers, we are forced to unravel them. How efficiently they unravel can depend on how they were built--not all arithmetic routines build equally efficient numerals. (See file “stuff.sch” for the pathologically built: slow-three. Note that by calling normalize-church, any arbitrarily inefficient Church numeral can be converted to one of the same efficiency as those built by number->church. normalize-church simply unravels using com-succ as the function and com-zero as the argument. For all stats tests in file “stuff.sch”, the numerals used were created manually so that the statistics wouldn’t be thrown off. )

Perhaps the most interesting thing we can do with Church numerals is to unravel them, and that’s what takes the most time. So, let’s make a distinction between unraveling that takes place at computation time and unraveling that takes place at other times.

Herein, an “unraveler” or “unraveling <function>” will refer to a function or numeral that unravels at computation time, and an “unraveller” will refer to a numeral’s unraveling behavior at other than computation time.

com-pred is unraveler. At computation time, it “conses” (creates tuples, which require space) while unraveling. It conses n times where n is the value the Church numeral represents. It returns a result that is a “straight unraveller” (a straight unraveller is a numeral that’s built like number->church builds them). Note that straight unravellers aren’t as efficient as they would be if we had defined them “manually” (as is done near the bottom of the file “stuff.sch”). A straight unraveller will unravel n + 1 times. (One unravel is done for com-zero.)

com-sub is an efficient computer, however it is not being burdened with checking that m < n doesn’t happen when subtracting m - n. If it had to check for that case, it would probably be calling an unraveling predicate which would then make com-sub into an inefficient computer.

com-sub is an inefficient unraveller because it conses and has embedded unravellers. The consing in com-sub for m - n can be described by the expression:

The consing in com-quo (the quotient function) can be described by the expression: “YUK!” because com-quo compounds the inefficiencies of com-sub (which in turn compounds the inefficiencies of com-pred).

com-quo is an inefficient computer and unraveller. At computation time, it calls com-<? which makes use of the unraveling predicate com-zero? . At unraveling time, it conses and does embedded unravelings.

com-add is an efficient computer. For m + n, the result will consist of a straight unraveller for n and two unravelings for m. I.e. there will be (n + 1) + 2 unravelings.

com-mul is an efficient computer. As an unraveller, it results in 1 unravel and 2 partial unravels.

com-pow is almost an efficient computer. At computation time it does a partial unravel. As an unraveller, it does 1 unravel.

Notice that com-pow, com-mul, and com-add all basically do different forms of function composition. The definition of com-mul is simpler than com-add, and com-pow is simpler yet: it’s just directly composes two Church numerals! Basically the difference between these functions is a matter of how much unraveling takes place before composition.

Perhaps if one were to do a lot of computations and very few decodings of Church numerals to regular numbers, Church math might gain some efficiencies from its lazy style of doing things. Also, normalize-church could be used to convert poor unravellers to efficient unravellers before any math is done on them (lest existing inefficiencies get compounded).

(Code note: the objects used by function stats, including function stats, are message passing objects with local state, modelled after the cons example in the recap. The message ‘? can be used to find out what messages an object will accept.)

Sometimes it’s okay to be lazy!

Here’s an example of a form of laziness at work in some other numerical system. Consider the (Chinese) abacus.

There are three different ways to represent 10 (and powers of 10 beyond 1). While one could “normalize” every time a computation produced a result that needed to be normalized, perhaps it might be more efficient to wait until another computation forces normalization.

In fact, if one were to normalize at every chance, one might find that certain beads were pushed up and down more than once, whereas they might have been moved around only once if one weren’t so anxious to normalize. Sometimes the normalizations can be subsumed into future computations. Sometimes if you don’t do something right away, the need to do it may later go away. (I.e. Sometimes it pays to be lazy and only do work that is proven to be needed.)

(A trivial example: Imagine all the ones beads being pushed up, representing 5. This situation seems like having the bases loaded in baseball, so the temptation might be to “normalize” that by pushing all the ones beads back down and pushing up one of the fives beads. That would later enable trivially adding anything less than 5. However, if the ones beads were left pushed up, and the next number to be added was 3, we could push up a fives bead and push down 2 of the ones beads since 3 = 5 - 2. Contrast how many beads get moved around this way versus how many would have been moved around had we normalized before adding 3.

A parting observation: The abacus is so redundant that it often allows choices as to when and how to normalize, or not normalize. This allows room for personal style.)

Consumer oriented numerals

In file “stuff.sch”, (what are herein called) “consumer” numerals are introduced. Essentially, consumer numerals are a more formalized way of thinking about n-consumers (which might be a déjà vu for the reader as they were actually used in the last article to describe how com-zero? works).

Consumer numerals are not nearly as “verb” oriented as Church numerals (which are strongly function oriented as can be seen by the number of function invocations (“fireworks”) that can be set in motion when a numeral is invoked--consider the case of the powerful composition at work in com-pow for example). At the same time consumer numerals aren’t as “noun” oriented as list numerals (wherein n is represented by a list of n elements--list numerals are a treatment of numbers as passive data objects).

For consumer numerals, abstraction becomes the successor function and function application becomes the predecessor function. n is represented in terms of how many arguments the numeral is capable of consuming.

Odds and Ends

Note the following behavior:

>>> (com-null? ‘a)

ERROR:  Bad procedure
a

Entering debugger.  Enter ? for help.
debug:>

Is this due to evaluation differences between Scheme (applicative order) and l-calculus (normal order) like we encountered in implementing com-if ? Or, is com-null? designed to only accept com-nil or a tuple made by com-cons ?

Exercise: Compare and contrast the Révész version of com-add (see file “combinators.sch”) with the vanMeule version (which was designed in the style of com-sub). The unraveling in the Révész com-add should be made explicit via calls to unravel and/or partial-unravel if you want to use stats to analyze its performance. Could com-mul be written in terms of com-add, and com-pow in terms of com-mul ? (The question is really one of making use of an operator that wants two args versus a unary operator like com-succ.)

Exercise from last article: making thunks tow the line. If we want thunks to have one argument (as the rest of our combinators have) we can do the following.

To thunkify an expression <E> wrap a lambda of one argument around it like this: (lambda (x) <E>) where x does not “free occur” in <E>. I.e. x must not be a free variable in <E> lest we inadvertently snag the x of the thunk when <E> gets evaluated.

To force a thunk: notice that our new thunks are like consumer oriented numerals. We therefore want to take the predecessor, which is to say we want to force it by applying it to <anything>.

;6

(define new-force 
  (lambda (thunk) 
    (thunk ‘anything)))

Looking Ahead

In file “combinators.sch” the reader will find a goodly number of combinators defined.

The reader can now write sorting routines, mapping functions, and various other list oriented functions.

It might be interesting at this point to implement a “metacircular” interpreter using combinators (an evaluator written in the same language it evaluates is said to be metacircular [Abelson et al., 1985]). This could serve various purposes such as allowing us to:

1) See exactly what is required. Do we currently have everything we need to implement LISP? (How would we handle state?) How about a l-calculus interpreter?

2) Explore language and implementation issues--the restrictiveness of combinators might enable issues to come to light that might otherwise get missed.

3) Be able to see the guts of combinators! Unfortunately, the trend these days is towards abolishing interpreters. (MacScheme compiles everything when you press <enter>.) Using a metacircular interpreter to run our combinators, we could then see what they look like internally, for instance, it would be nice if identity evaluated to: (closed-lambda (x) x) . In Scheme it evaluates to #<PROCEDURE identity> because it gets compiled to some unprintable form.

4) Metacircular interpreters are useful for prototyping new languages--once we’ve got one we might want to tweak it to evaluate in normal order instead of applicative order. Thereafter, a tweak could be made to allow partial evaluation in order to evolve our metacircular interpreter closer to a l-calculus interpreter.

All these things are beyond the game plan for this article--I merely wanted to suggest possible directions that could be pursued.

“Thanks” to:

• Henry Baker for donating the title of this article (full well realizing that no good deed goes unpunished), and for showing me the (fact fact ...) trick.

• Verbosity buster John Koerber for valiant efforts against the Department of Redundancy Department.

• The jacuzzi in which this article was conjured.

Bugs/infelicities due to chlorine vapors.

Bibliography and References

[Abelson et al, 1985] Harold Abelson and Gerald Jay Sussman with Julie Sussman. Structure and Interpretation of Computer Programs. MIT Press, Cambridge, Massachusetts, USA, 1985.

[Dertouzos et al., 1974] Michael L. Dertouzos, .Stepehn A. Ward, Joseph Weizenbaum. Course 6.031 Structure and Interpretation of Computer Languages. MIT, Cambridge, MA 1974-75.

[Field et al., 1989] Anthony J. Field and Peter G. Harrison. Functional Programming. Addison-Wesley Publishing Company. First printed 1988. Reprinted 1989.

[Gabriel, 1988] Richard P. Gabriel. The Why of Y. LISP Pointers, vol. 2, no. 2 October-November-December, 1988.

[Katz, 1988] Morry J. Katz. Katz’s notes from Information Sciences Function sponsored lecture series on Computer Science. Rockwell International Science Center, Thousand Oaks, CA, March, 1988.

[Knuth, 1981] Donald E. Knuth. The Art of Computer Programming, second edition, vol. 2, Seminumerical Algorithms. Addison-Wesley Publishing Company, 1981.

[Michaelson, 1989] Greg Michaelson. An Introduction to Functional Programming through Lambda Calculus. Addison-Wesley Publishing Company, 1989.

[Peyton Jones, 1987] Simon L. Peyton Jones. The Implementation of Functional Programming Languages. Prentice-Hall International, 1987.

[Queinnec, 1990] Christian Queinnec. A Subjective view of Lisp. LISP Pointers; Volume 3, Number 1. ACM, NY, July 1989-March 1990.

[Ramsdell, 1986] John D. Ramsdell. The Curry Chip. In Proceedings of the 1986 ACM Conference on LISP and Functional Programming. Cambridge, MA, August 4-6, 1986.

[Rees et al, 1986] Jonathan Rees and William Clinger (editors). Revised3 Report on the Algorithmic Language Scheme; AI Memo 848a. MIT Artificial Intelligence Laboratory, Cambridge, Massachusetts, USA, September 1986.

[Révész, 1988] György E. Révész. Lambda-Calculus, Combinators, and Functional Programming. Cambridge University Press, Cambridge, England, 1988.

. . .

The Scheme combinators presented herein were derived from l-calculus versions. Except for Y and others where noted, the l-calculus versions are from [Révész, 1988].

MacScheme™ is put out by Lightship Software, P.O. Box 1636, Beaverton, OR 97075 USA. Phone: (503) 643-6909.

. . .

André can be reach on the Internet:

vanMeule@cup.portal.com

; File:  combinators.sch.  (Eval first.)
;
; Projection functions.
;
(define identity ; project-1st-of-1
  (lambda (x) x))
;
(define project-1st-of-2
  (lambda (x)
    (lambda (y)
      x)))
;
(define project-2nd-of-2
  (lambda (x)
    identity))
;
(define project-3rd-of-3
  (lambda (x)
    (lambda (y)
      identity)))
;
(define 3-consumer project-3rd-of-3)
;
; Booleans and conditionals.
;
(define com-true
  project-1st-of-2)
;
(define com-false
  project-2nd-of-2)
;
(define force-a-thunk ; used by com-if and others.
  (lambda (thunk)
    (thunk)))
;
(define com-if
  (lambda (condition)
    (lambda (then)
      (lambda (else)
        (force-a-thunk ((condition then) else))))))
;
(define com-not ; [Michaelson, 1989]
  (lambda (x)
    (((com-if x)
      (lambda () com-false))
     (lambda () com-true))))
;
(define com-and ; [Field, 1989]
  (lambda (x)
    (lambda (y)
      ((x y) com-false))))
;
(define com-or ; [Field, 1989]
  (lambda (x)
    (lambda (y)
      ((x com-true) y))))
;
; List primitives.
;
(define com-cons
  (lambda (x)
    (lambda (y)
      (lambda (selector)
        ((selector x) y)))))
;
(define com-car
  (lambda (object)
    (object project-1st-of-2)))
;
(define com-cdr
  (lambda (object)
    (object project-2nd-of-2)))
;
(define com-nil ; project-2nd-of-3
  (lambda (x)   ; [Field, 1989]
    com-true))  ;
;
(define com-null? ; [Field, 1989]
  (lambda (tuple)
    (tuple (lambda (head)
             (lambda (tail)
               com-false)))))
;
; Y combinator.
;
(define applicative-order-y
  (lambda (f)
    ((lambda (x) (f (lambda (arg) ((x x) arg))))
     (lambda (x) (f (lambda (arg) ((x x) arg)))))))
;
; The Mother of All Church numerals.
;
(define com-zero
  project-2nd-of-2)
;
; Church numeral predicates.
;
(define com-zero?
  (lambda (n)
    (((unravel n) 3-consumer) com-true)))
;
(define com-even? ; [Révész, 1988] (not in book)
  (lambda (n)
    (((unravel n) com-not) com-true)))
;
(define com-odd? ; [Révész, 1988] (not in book)
  (lambda (n)
    (((unravel n) com-not) com-false)))
;
(define com-<? ; [vanMeule]
  (applicative-order-y
   (lambda (less-than?)
     (lambda (x)
       (lambda (y)
         (((com-if (com-zero? x))
           (lambda () 
             (((com-if (com-zero? y))
               (lambda () com-false))
              (lambda () com-true))))
          (lambda () 
            (((com-if (com-zero? y))
              (lambda () com-false))
             (lambda () ((less-than? (com-pred x))
                         (com-pred y)))))))))))
;
; Church numeral operators.
;
(define com-succ
  (lambda (n)
    (lambda (f)
      (lambda (x)
        (f (((unravel n) f) x))))))
;
(define make-ascending-tuple ; part of pred
  (lambda (tuple)
    ((com-cons 
      (com-cdr tuple))
     (com-succ (com-cdr tuple)))))
;  
(define initial-pred-tuple ; part of pred
  ((com-cons "com-pred called on 0")
   com-zero))
;
(define com-pred
  (lambda (n)
    (com-car 
     (((unravel n) 
       make-ascending-tuple)
      initial-pred-tuple))))
;
(define com-add ; Révész version [Révész, 1988]
  (lambda (m)
    (lambda (n)
      (lambda (f)
        (lambda (x)
          ((m f)
           ((n f) x)))))))
;
(define com-add ; [vanMeule]
  (lambda (m)
    (lambda (n)
      (lambda (f)
        (lambda (x)
          (((unravel (((unravel n) com-succ) m)) 
            f) x))))))
;
(define com-sub ; [vanMeule]
  (lambda (m)
    (lambda (n)
      (lambda (f)
        (lambda (x)
          (((unravel (((unravel n) com-pred) m)) 
            f) x))))))
;
(define com-mul
  (lambda (m)
    (lambda (n)
      (lambda (f)
        ((partial-unravel m) 
         ((partial-unravel n) f))))))
;
(define com-quo ; [vanMeule]
  (applicative-order-y
   (lambda (the-quo)
     (lambda (dividend)
       (lambda (divisor)
         (((com-if ((com-<? dividend) divisor))
           (lambda () com-zero))
          (lambda () 
            (com-succ ((the-quo ((com-sub dividend) 
                                 divisor)) 
                       divisor)))))))))
;
(define com-rem) ; Reader defines remainder.
;
(define com-pow ; [Katz, 1988]
  (lambda (m)
    (lambda (n)
      ((partial-unravel n) m))))
;
; Church numeral utility functions.
;
(define number->church ; make-church-numeral
  (lambda (n)
    (if (zero? n)
        com-zero
        (com-succ 
         (number->church (- n 1))))))
;
(define unravel
  (lambda (n)
    (lambda (f)
      (lambda (x)
        ((n f) x)))))
;
(define partial-unravel
  (lambda (n)
    (lambda (f)
      (n f))))
;
(define church->number ; dechurchify-numeral
  (lambda (church-numeral)
    (((unravel church-numeral) 1+) 0)))
;
(define com-one 
  (lambda (f)
    (lambda (x)
      (f x))))
;
'done

 
AAPL
$99.02
Apple Inc.
+1.35
MSFT
$43.97
Microsoft Corpora
-0.53
GOOG
$590.60
Google Inc.
+1.58

MacTech Search:
Community Search:

Software Updates via MacUpdate

OS X Yosemite Wallpaper 1.0 - Desktop im...
OS X Yosemite Wallpaper is the gorgeous new background image for Apple's upcoming OS X 10.10 Yosemite. This wallpaper is available for all screen resolutions with a source file that measures 5,418... Read more
Acorn 4.4 - Bitmap image editor. (Demo)
Acorn is a new image editor built with one goal in mind - simplicity. Fast, easy, and fluid, Acorn provides the options you'll need without any overhead. Acorn feels right, and won't drain your bank... Read more
Bartender 1.2.20 - Organize your menu ba...
Bartender lets you organize your menu bar apps. Features: Lets you tidy your menu bar apps how you want. See your menu bar apps when you want. Hide the apps you need to run, but do not need to... Read more
TotalFinder 1.6.2 - Adds tabs, hotkeys,...
TotalFinder is a universally acclaimed navigational companion for your Mac. Enhance your Mac's Finder with features so smart and convenient, you won't believe you ever lived without them. Tab-based... Read more
Vienna 3.0.0 RC 2 :be5265e: - RSS and At...
Vienna is a freeware and Open-Source RSS/Atom newsreader with article storage and management via a SQLite database, written in Objective-C and Cocoa, for the OS X operating system. It provides... Read more
VLC Media Player 2.1.5 - Popular multime...
VLC Media Player is a highly portable multimedia player for various audio and video formats (MPEG-1, MPEG-2, MPEG-4, DivX, MP3, OGG, ...) as well as DVDs, VCDs, and various streaming protocols. It... Read more
Default Folder X 4.6.7 - Enhances Open a...
Default Folder X attaches a toolbar to the right side of the Open and Save dialogs in any OS X-native application. The toolbar gives you fast access to various folders and commands. You just click... Read more
TinkerTool 5.3 - Expanded preference set...
TinkerTool is an application that gives you access to additional preference settings Apple has built into Mac OS X. This allows to activate hidden features in the operating system and in some of the... Read more
Audio Hijack Pro 2.11.0 - Record and enh...
Audio Hijack Pro drastically changes the way you use audio on your computer, giving you the freedom to listen to audio when you want and how you want. Record and enhance any audio with Audio Hijack... Read more
Intermission 1.1.1 - Pause and rewind li...
Intermission allows you to pause and rewind live audio from any application on your Mac. Intermission will buffer up to 3 hours of audio, allowing users to skip through any assortment of audio... Read more

Latest Forum Discussions

See All

Traps n’ Gemstones Review
Traps n’ Gemstones Review By Campbell Bird on July 28th, 2014 Our Rating: :: CASTLEVANIA JONESUniversal App - Designed for iPhone and iPad Fight mummies, dig tunnels, and ride a runaway minecart to discover ancient secrets in this... | Read more »
The Phantom PI Mission Apparition Review
The Phantom PI Mission Apparition Review By Jordan Minor on July 28th, 2014 Our Rating: :: GHOSTS BUSTEDUniversal App - Designed for iPhone and iPad The Phantom PI is an exceedingly clever and well-crafted adventure game.   | Read more »
More Stubies Are Coming Your Way in a Ne...
More Stubies Are Coming Your Way in a New Update Posted by Jessica Fisher on July 28th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
The Great Prank War Review
The Great Prank War Review By Nadia Oxford on July 28th, 2014 Our Rating: :: PRANKING IS SERIOUS BUSINESSUniversal App - Designed for iPhone and iPad Though short, The Great Prank War offers an interesting and fun mix of action and... | Read more »
Marvel Contest of Champions Announced at...
Marvel Contest of Champions Announced at Comic-Con Posted by Jennifer Allen on July 28th, 2014 [ permalink ] Announced over the weekend at San Diego Comic-Con was the fairly exciting looking Marvel Contest of Champions. | Read more »
Teenage Mutant Ninja Turtles Review
Teenage Mutant Ninja Turtles Review By Jennifer Allen on July 28th, 2014 Our Rating: :: DULL SWIPINGUniversal App - Designed for iPhone and iPad The pizza power is weak when it comes to this Teenage Mutant Ninja Turtles game.   | Read more »
Exploration Focused Puzzle Game Beatbudd...
Exploration Focused Puzzle Game Beatbuddy Set to Make Transition from PC to iOS this September Posted by Jennifer Allen on July 28th, 2014 [ permalink ] | Read more »
PlanetHD
PlanetHD By Nadia Oxford on July 28th, 2014 Our Rating: :: SPACE MADNESSUniversal App - Designed for iPhone and iPad PlanetHD will keep players busy for a while, though its unpredictable physics are a handful to deal with.   | Read more »
This Week at 148Apps: July 21-25, 2014
Another Week of Expert App Reviews   At 148Apps, we help you sort through the great ocean of apps to find the ones we think you’ll like and the ones you’ll need. Our top picks become Editor’s Choice, our stamp of approval for apps with that little... | Read more »
Reddme for iPhone - The Reddit Client (...
Reddme for iPhone - The Reddit Client 1.0 Device: iOS iPhone Category: News Price: $.99, Version: 1.0 (iTunes) Description: Reddme for iPhone is an iOS 7-optimized Reddit client that offers a refreshing new way to experience Reddit... | Read more »

Price Scanner via MacPrices.net

13-inch 2.5GHz MacBook Pro on sale for $1099,...
Best Buy has the 13″ 2.5GHz MacBook Pro available for $1099.99 on their online store. Choose free shipping or free instant local store pickup (if available). Their price is $100 off MSRP. Price is... Read more
Roundup of Apple refurbished MacBook Pros, th...
The Apple Store has Apple Certified Refurbished 13″ and 15″ MacBook Pros available for up to $400 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free. Their prices... Read more
Record Mac Shipments In Q2/14 Confound Analys...
A Seeking Alpha Trefis commentary notes that Apple’s fiscal Q3 2014 results released July 22, beat market predictions on earnings, although revenues were slightly lower than anticipated. Apple’s Mac’... Read more
Intel To Launch Core M Silicon For Use In Not...
Digitimes’ Monica Chen and Joseph Tsai, report that Intel will launch 14nm-based Core M series processors specifically for use in fanless notebook/tablet 2-in-1 models in Q4 2014, with many models to... Read more
Apple’s 2014 Back to School promotion: $100 g...
 Apple’s 2014 Back to School promotion includes a free $100 App Store Gift Card with the purchase of any new Mac (Mac mini excluded), or a $50 Gift Card with the purchase of an iPad or iPhone,... Read more
iMacs on sale for $150 off MSRP, $250 off for...
Best Buy has iMacs on sale for up to $160 off MSRP for a limited time. Choose free home shipping or free instant local store pickup (if available). Prices are valid for online orders only, in-store... Read more
Mac minis on sale for $100 off MSRP, starting...
Best Buy has Mac minis on sale for $100 off MSRP. Choose free shipping or free instant local store pickup. Prices are for online orders only, in-store prices may vary: 2.5GHz Mac mini: $499.99 2.3GHz... Read more
Global Tablet Market Grows 11% in Q2/14 Notwi...
Worldwide tablet sales grew 11.0 percent year over year in the second quarter of 2014, with shipments reaching 49.3 million units according to preliminary data from the International Data Corporation... Read more
New iPhone 6 Models to Have Staggered Release...
Digitimes’ Cage Chao and Steve Shen report that according to unnamed sources in Apple’s upstream iPhone supply chain, the new 5.5-inch iPhone will be released several months later than the new 4.7-... Read more
New iOS App Helps People Feel Good About thei...
Mobile shoppers looking for big savings at their favorite stores can turn to the Goodshop app, a new iOS app with the latest coupons and deals at more than 5,000 online stores. In addition to being a... Read more

Jobs Board

Sr Software Lead Engineer, *Apple* Online S...
Sr Software Lead Engineer, Apple Online Store Publishing Systems Keywords: Company: Apple Job Code: E3PCAK8MgYYkw Location (City or ZIP): Santa Clara Status: Full Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Sr. Product Leader, *Apple* Store Apps - Ap...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.