GEDANKEN
Paul McJones, editor - paul@mcjones.org - http://www.mcjones.org/dustydecks/
Software Preservation Group
Computer History Museum
Introduction
The goal of this project is to preserve and present primary source materials from GEDANKEN, a language designed by John C. Reynolds.
"GEDANKEN is a simple, idealized programming language with the following characteristics: (1) Any value which is permitted in some context of the language is permissible in any other meaningful context. In particular, procedures and labels are permissible results of functions and values of variables. (2) Assignment and indirect addressing are formalized by introducing values, called references, which in turn possess other values. The assignment operation always affects the relation between some reference and its value. (3) All compound data structures are treated as functions. (4) Type declarations are not permitted." [Reynolds 1969]
"A few historical notes: The genesis of the language was my realizing the functional encodings of CONS, CAR, and CDR. (In fact, one can execute such encodings in (at least early) LISP interpreters, but not in any LISP compiler.) Most of the development of the language was done before I became familiar with PAL. But then I heard Arthur Evans, Jr. talk about PAL at the 1968 ACM conference, and invited him to talk at Argonne, and borrowed a feature or two from PAL (something about the treatment of vectors, as I remember). In the (probably early) 70's, after I'd moved to Syracuse University, I made a more serious attempt to implement GEDANKEN. But I neglected to notice that, if the function used to initialize a vector is nondeterminate, the vector initialization can lead to a huge and highly inefficient tree of vectors. When I realized this, it demoralized me so much that I abandoned the attempt at implementation. Once SCHEME appeared, there was little justification for pursuing GEDANKEN, and once ML appeared there was even less. (I always felt that the weak point of GEDANKEN was its lack of a type system.) But even as a language just to think about, it made clear the potential of higher-order functions in programming." [John C. Reynold, personal communication, March 13, 2012]
Contents
Acknowledgments
Thanks to:
- John C. Reynolds for donating the listings to the Computer History Museum and explaining to me about the how the code came to be;
- Günther Görz for including a copy of Reynolds' 1969 technical report on Gedanken as part of the Stoyan collection on LISP programming.
Source code
GEDANKEN translator
"When I first submitted the CACM paper on GEDANKEN, when I was working at Argonne National Laboratory, I was worried that there might be some mistake lurking in the language design or definition. (The original submission contained an operational definition that was eventually deleted from the published version, but retained in the Argonne report.) So I took the operational definition, translated it into LISP, and combined it with a parser, to obtain a implementation in the Stanford University version of LISP360, which was very similar to LISP 1.5. My goal was to stay as close to the operational definition as possible, so there were no optimizations, and the runtimes were glacial, as were the storage requirements. It was not a practical system.
At the end, the computer output contains "DATE = 69.119, which I think means the 119th day of 1969, which would be April 29.
I haven't had time to decipher much of this material. I notice that, in the translator listing, I used a kind of abstract syntax, passed as an argument to the LISP function DEFINESYN. For example, EXP (expression) is a union, one component of which is a FUNCTDES, which consist of an EXP called the FUNCTPART and an EXP called the ARGPART. Also, note that, in the GEDANKEN programs, # is used to denote lambda, which makes it easy to spot text that is in GEDANKEN." [John C. Reynold, personal communication, 13 March 2012]
- John C. Reynolds. Gedanken implementation in Stanford LISP360. April 1969. Scanned source listing. PDF
GEDANKEN test programs
"Fairly early in the computer output, I define some 3 x 3 arrays: M, in which each element is independent, MT which is the transpose of M, so that MT(i,j) is the same reference as M(j,i), and S, which is symmetric, so that S(i,j) and S(j,i) are the same reference. I also define the three-element vector MD such that MD(i) is the same reference as M(i,i). The test program sets each independent array element, and then prints out all the values. Note that this took 12.25 seconds on an IBM 360/75 (and nearly, as I remember, exhausted storage). I then went on to test most of the nontrivial functions defined in the paper on GEDANKEN: MAKERLIST PSEUDOCOPY COMPILE and ASSEMBLE (coroutines) PARSE (nondeterministically) CONS, CAR, and CDR (a functional realization of basic LISP) LISTLENGTH, LISTELEM, APPEND VECTOR PROPVAL and MAKEPROPLIST" [John C. Reynold, personal communication, March 13, 2012]
- John C. Reynolds. Test programs for Gedanken implementation in Stanford LISP360. April 1969.
Documentation
- John C. Reynolds. GEDANKEN: A Simple Typeless Language Which Permits Functional Data Structures and Coroutines. Technical Report ANL-7621, Argone National Laboratory, September 1969. PDF
Papers
- John C. Reynolds. GEDANKEN—a simple typeless language based on the principle of completeness and the reference concept. Commun. ACM, Volume 13, Number 5, May 1970, pages 308-319. ACM Digital Library / Online at kilthub.cmu.edu
Related papers
The GEDANKEN CACM paper has 73 citations in the ACM Digital Library. Of particular relevance is Reynolds' later paper:
- John C. Reynolds. Definitional interpreters for higher-order programming languages.
- In Proceedings of the ACM annual conference - Volume 2 (ACM '72), Rosemary Shields (Ed.), Vol. 2. ACM, New York, NY, USA, pages 717-740. ACM Digital Library
- Corrected version republished in: Higher Order Symbol. Comput. 11, 4 (December 1998), pages 363-397. SpringerLink
- Reprint at Syracuse University. surface.syr.edu