Higher-Order Programming

Lecture Notes for Com Sci 221, Programming Languages

Last modified: Mon Nov 20 09:48:47 CST 2000

I haven't had time to type real notes for this section yet. Here are some examples to study.

Scheme Examples

Evaluation in Scheme

Here is a sequence of approximations to an old-fashioned LISP evaluator, written in Scheme. Think of them as LISP evaluation in LISP, where I chose the Scheme variant of LISP for the implementation just because it's available and familiar. I skipped lots of details that don't affect the structure much, and focused on the recursive structure of evaluation, and manipulations of the environment. For simplicity, I let all atomic symbols evaluate to themselves. Good old-fashioned LISP and Scheme have somewhat complicated rules for which atoms evaluate to themselves, and which produce error messages.

1. Version 1.1 deals with the basic list manipulations, quoting, and lambda, but it fails to evaluate a function. Find an example demonstrating this deficiency through a lambda expression one of whose arguments is used as a function.
2. Version 1.3 fixes quoting, using the mutually-recursive interaction of eval and apply.

• Demonstration inputs to explore the qualities of the different versions of eval above.

Miscellaneous higher-order functions

Here are some thought-provoking examples of higher-order programming in Scheme. They are not intended to be directly practical. Rather, they show what complex computations (demonstrated by the sizes of numbers that they compute) can be described very succinctly in a higher-order style.

• Definitions
• Demonstrations

Paradigmatic higher-order functions

Higher-order programming allows us to define certain patterns of computation once and for all, then reuse them with different particular operations. For example,

• reduce expresses the generic idea of recursion through a list;
• reduce-tree expresses the generic idea of recursion through a tree.

1. while loop as a higher-order function.
2. Powers of 2 calculated iteratively using the while loop.

Minimalist Scheme

All of the computational power of Scheme can be built on lambda and function application. car, cdr, cons, arithmetic, and even recursion can all be defined by the user, so they don't really need to be built in. In the following definitions, I implement the basic list operations, conditional (with an interesting subtlety), and integer arithmetic. I give a provisional implementation of recursion, but it doesn't quite work because it requires a different order of evaluation from the one implemented by Scheme. The trick that I used to fix the order of evaluation for conditional gives the essential hint, but it's a bit more complicated in recursion.

• Definitions using only lambda and application.