G/EDANKEN—a simple typeless language based on the principle of completeness and the reference concept

ABSTRACT

GEDANKEN is an experimental 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, functions 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. The functional approach to data structures and the use of references insure that any process which accepts some data structure will accept any logically equivalent structure, regardless of its internal representation. More generally, any data structure may be implicit; i.e. it may be specified by giving an arbitrary algorithm for computing or accessing its components. The existence of label variables permits the construction of co-routines, quasi-parallel processes, and other unorthodox control mechanisms. A variety of programming examples illustrates the generality of the language. Limitations and possible extensions are discussed briefly.

REFERENCES

• 1a: John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
• 1b: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 2: P. J. Landin, The next 700 programming languages, Communications of the ACM, v.9 n.3, p.157-166, March 1966 [doi>10.1145/365230.365257]
• 3: Arthur Evans, Jr., PAL—a language designed for teaching programming linguistics, Proceedings of the 1968 23rd ACM national conference, p.395-403, August 27-29, 1968 [doi>10.1145/800186.810604]
• 4: A. van Wijngaarden, Report on the algorithmic language ALGOL 68, Printing by the Mathematisch Centrum, 1969
• 5: CHEATHAM, T. E., JR., FISCHER, A., AND JORRAND, P. On basis for ELF--An extensible language facility. Proc. AFIPS 1968 Fall Joint Comput. Conf., Vol. 33 Pt. 2, MDI Publications, Wayne, Pa., pp. 937-948.
• 6: BALZER, R. M. Dataless programming. Proc. AFIPS 1967 Fall Joint Comput. Conf. Vol. 31, MDI Publications, Wayne, Pa., pp. 535-544.
• 7: REYNOLDS, J .C . GEDANKEN--A simple typeless language which permits functional data structures and coroutines. ANL-7621, Argonne Nat. Lab., Argonne, Ill., Sept. 1969.
• 8: Niklaus Wirth , Helmut Weber, EULER: a generalization of ALGOL, and its formal definition: Part II, Communications of the ACM, v.9 n.2, p.89-99, Feb. 1966 [doi>10.1145/365170.365202]
• 9: Niklaus Wirth , C. A. R. Hoare, A contribution to the development of ALGOL, Communications of the ACM, v.9 n.6, p.413-432, June 1966 [doi>10.1145/365696.365702]
• 10: FARBER, D. J., GRISWOLD, R. E., AND POLONSKY, L P. The SNOBOL3 programming language. Bell Syst. Tech. J. 45 (July-Aug. 1966), 895--944.
• 11: R. Y. Kain, Block structures, indirect addressing, and garbage collection, Communications of the ACM, v.12 n.7, p.395-398, July 1969 [doi>10.1145/363156.363175]
• 12: BURSTALL, R. M., AND POPPLESTONE, R .J . POP-2 reference manual. In Machine Intelligence g, E. Dale and D. Michie (Eds.), American Elsevier, New York, 1968, pp. 205-246.
• 13a: Ole-Johan Dahl , Kristen Nygaard, SIMULA: an ALGOL-based simulation language, Communications of the ACM, v.9 n.9, p.671-678, Sept. 1966 [doi>10.1145/365813.365819]
• 13b: Ole-Johan Dahl, SIMULA 67 common base language, (Norwegian Computing Center. Publication), 1968
• 14: Robert W. Floyd, Nondeterministic Algorithms, Journal of the ACM (JACM), v.14 n.4, p.636-644, Oct. 1967 [doi>10.1145/321420.321422]
• 15a: REYNOr,DS, J.C. An introduction to the COGENT programming system. Proc. ACM 20th Natl. Conf., 1965, pp. 422- 436.
• 15b: --, COGENT programming manual. ANL-7022, Argonne Nat. Lab., Argonne, Ill., Mar. 1965.
• 16: Jay Earley, An efficient context-free parsing algorithm, Communications of the ACM, v.13 n.2, p.94-102, Feb 1970 [doi>10.1145/362007.362035]
• 17: REYNOLDS, J. C. A set-theoretic approach to the concept of type. Working paper, NATO Conf. on Techniques in Software Engineering, Rome, Oct. 1969.
• 18a: EVANS, A. Private communication.
• 18b: MORRIS, J. H. Lambda-calculus models of programming languages. MAC-TR-57, Project MAC, MIT, Cambridge, Mass., Dec. 1968.

INDEX TERMS

Keywords:
applicative language, assignment, coroutine, data structure, lambda calculus, list processing, nondeterministic algorithm, programming language, quasi-parallel process, reference, typeless language