Search |  Contact |  SRI Home Do not follow this link, or your host will be blocked from this site. This is a spider trap. Do not follow this link, or your host will be blocked from this site. This is a spider trap. Do not follow this link, or your host will be blocked from this site. This is a spider trap.A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A ASRI International.  333 Ravenswood Avenue.  Menlo Park, CA 94025-3493. SRI International is a nonprofit corporation.

AIC Seminar Series

Program Control Structure Integrity Archetypes

Carl HewittMIT

Date:  2005-05-03 at 14:30

Location:  EJ228  (Directions)

   Abstract

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.

   Bio for Carl Hewitt

Carl Hewitt is an emeritus professor from MIT. He is known for his design of Planner of which a subset Micro Planner implemented by Gerry Sussman, Eugene Charniak and Terry Winograd was used in Terry’s famous SHRDLU program. PROLOG subsequently reinvented some of the capabilities of Micro Planner. Carl and his students are also known for their work on Actors that are the universal primitives of concurrent computation. The Actor work built on Lisp, Simula-67, Smalltalk, and capability-based systems. History then repeated itself and concurrent PROLOGs reinvented some of the capabilities of Actors. All of this work was not very practical because the transistors in processor chips were devoted mainly to making sequential programs run faster. Now Moore’s law has taken a "right hand turn" and massive concurrency lies in the future with multi-core chips and multi-chip modules, Web Services with binary XML, 10Tb Ethernet, WiMAX and Wi-Fi. Even the instruction sets of the microprocessors of our PCs will need to be augmented with new instructions because of concurrency.

   Note for Visitors to SRI

Please arrive at least 10 minutes early as you will need to sign in by following instructions by the lobby phone at Building E. SRI is located at 333 Ravenswood Avenue in Menlo Park. Visitors may park in the parking lots off Fourth Street. Detailed directions to SRI, as well as maps, are available from the Visiting AIC web page. There are two entrances to SRI International located on Ravenswood Ave. Please check the Builing E entrance signage.

SRI International
©2014 SRI International 333 Ravenswood Avenue, Menlo Park, CA 94025-3493
SRI International is an independent, nonprofit corporation. Privacy policy