Computer Organization and Architecture

Institute of Computer Science and Applied Mathematics

Computer Organization and Architecture

Werner Kluge, Prof.(em.)

Phone: +49-(0)2204-867 512 (private)

E-Mail: wk@informatik.uni-kiel.de

After retiring in 2003, I have found the time to complete a monograph on Abstract Computing Machines which has been published in the Springer EATCS series (ISBN 3-540-21146-2).
This monograph is on the relationship between basic programming paradigms as they derive from Lambda calculus and the abstract machines featuring the runtime structures and mechanisms that are essential for program execution. It sets out with a brief discussion of an expression-oriented style of programming, addresses the problem of correctly dealing with free variables as a prerequisite for symbolic computations, and gives a brief introduction to Lambda calculus as the underlying theory.
In its main part, the book is primarily concerned with the description of what are called fully normalizing Lambda-calculus machines. They support the runtime structures and mechanisms necessary to correctly perform substitutions that may involve free variables, and to do symbolic self-optimizations under functions (abstractions), thus treating both functions and variables truly as first class objects.
These machines are related to various weakly normalizing counterparts which are the work horses for the implementation of functional languages. They rule out substitution and evaluation under abstractions to avoid problems with free variables, which considerably simplifies the machinery but at the same time also sacrifices many of the amenities of symbolic computations.
Abstract machines for imperative languages are shown to be direct descendants of weakly normalizing Lambda-calculus machines. They permit side-effecting substitutions on an otherwise nearly identical runtime environment which, however, destroy the Church-Rosser property of the Lambda calculus, merely keeping its scoping rules intact.
I used the material contained in this book in various graduate courses on basic concepts of computer organization/architecture; some of the material of the first five chapters I also used in undergraduate courses on function-based programming.

As it so happens if publication deadlines have to be met, the book contains a few errors, many of which are just typos. But it also includes a serious mistake concerning the definition in chapter 5 of the SE(M)CD machine, which I run across just recently. A correction of this and also of the typos can be found under errata

Current activities

Teaching on `Abstract Lambda Calculus Machines' at the
2nd Central European Functional Programminmg School CEFP 2007
Cluj-Napoca June 23 - 30 2007
This three-hour course addresses the conceptual design of a computing machine that realizes a fully normalizing Lambda calculus based on full-fledged beta-reductions that include the resolution of potential naming conflicts. In contrast to the weakly normalizing machinery underlying traditional functional language implementations this approach lifts the status of variables and functions to that of first class objects, permitting truly symbolic computations that involve free variables.
The machine that is being presented derives from Landin's SECD machine by the addition of a few more state transition rules that take care of subsitutions and reductions under abstractions. We will also give an outline of a fully normalizing graph reduction machine and of how this machine can be made to return high-level Lambda terms as output.
Some of the material used in the lecture is adopted from the afore-mentioned monograph on Abstract Computing Machines

here are the lecture notes and the lab_course material

and here are the slides/transparencies used in class

the problem identification slides work through various applications of two very simple functions to show some of the shortcomings of the classical functional programming approach;
the next sequence of slides gives the definitions of weakly normalizing SECD machines for both applicative and normal order evaluation of terms of a nameless (deBruijn) lambda calculus that is more appropriate for machine implementation;
another sequence of slights explains the idea of head-order reduction, of how the concept of environments can be directly derived from the manipulation of lambda terms, and it also gives the formal definition of a fully normalizin SECD machine;
the basics of head-order graph reduction are outlined in this sequence of slides;
the last sequence of slights highlights the reconstruction of normal forms of lambda terms in high-level notation (featuring variables) from nameless lambda terms.