Recently I have been working in the area of Educational Programming that is defined to be the intersection between Education and Programming, i.e. not a special kind of Programming. It addresses challenging issues including the following: How do people program? How can people be educated to program better? What kind of technology can help people program? I.e., the challenge involves understanding complex interacting processes: Educational, Programming, and System Execution.
In order to make progress we need to address issues on many fronts including better understanding the structure of programs. Better understanding the structure of programs will not solve or even address most of the difficult issues of Educational Programming. Making progress on Educational Programming requires a large scale multi-disciplinary effort involving collaborative contributions from Social Science, Media, and Information Science. This talk is about a narrow highly technical topic in the area of understanding control structure archetypes of programs.
For the purposes of this seminar, define Program Integrity to mean firm adherence to a code of engineering, scientific, and aesthetic values in programs. In this seminar I use program schemas (explained below) to precisely state and in some cases prove some control structure program integrity results. The use of schemas enables us to avoid what Alan Perlis called the Turing machine tar pit, i.e., every class of programs is more or less equivalent to every other class of programs.
A program schema is defined to be a program with uninterpreted primitive procedures. Program schemas provide an important tool for precisely stating and proving some control structure integrity properties. We use participations that are 4-dimensional regions of space-time to structure computations. Participation analysis is concerned not just with the amount of space and time of a computation but also with its structure. For example, given two classes of program schemas, X and Y, X will be defined to be participation less powerful than Y (written X < Y) if and only if the following two conditions hold:
1. For every program schema f in X, there is an equivalent program schema g in Y such that g computes f in the participations of f.
2. There is a program schema g in Y for which there is no equivalent program schema f in X that computes g in the participations of g.
We present the following results (two of these are strengthened results cf. [Paterson and Hewitt 1970], etc.) for classes of program schemas such that each of the classes of program schema listed below is participation less powerful than its successor:
1. linear recursive class that are recursive program schemas such that each control path trough the program has at most one recursive call which is top level and at the end. This class is strongly equivalent to iterative (nonrecursive) programs using assignment + goto.
2. sequential recursive class that are recursive program schemas with left to right sequential evaluation of arguments to procedures.
3. parallel recursive class that are recursive programs schemas augmented with future [Baker and Hewitt]
4. parallel coroutine class of that are parallel recursive schemas augmented with coroutines.
5. λ calculus + assignment class that are lambda calculus schemas augmented with assignment.
6. concurrent class of programs are recursive programs augmented with the ability to dynamically create actors that asynchronously send messages that are processed by (other) actors to dynamically change their own local state, create more actors and send more messages (such as Java, C#, etc).
Participation equivalence frees us from the λ calculus tar pit, i.e., every programming language is more or less equivalent to the λ calculus + assignment.
At end of the talk, I discuss how the material in the talk relates to the larger goals of Educational Programming.