CSAIL Publications and Digital Archive header
bullet Technical Reports bullet Work Products bullet Historical Collections bullet

link to publications.csail.mit.edu link to www.csail.mit.edu horizontal line

CSAIL Digital Archive - Artificial Intelligence Laboratory Series
Publications 0 through 99

AI PublicationsLast update Sun Mar 19 05:05:02 2006


Author[s]: S. Russell

Writing and Debugging Programs

no date listed



A subroutine is a fixed set of instructions that is used many times. The kind most often used explicitly are closed subroutines such MAPLIST which are set up so that they may be used by any part of a program.


Author[s]: J. McCarthy

Notes on the Compiler

no date listed



We will start with a very modest compiler. Our first major goal is a compiler that will compile recursive function definitions. Its input will be LISP statements in restricted notation and its output will be a SAP tape. However we will start with an even simpler compiler that will only compile programs to evaluate expressions and at first we will print rather than punch them.


Author[s]: J. McCarthy

Recursive Functions of Symbolic Expressions and Their Computation by Machine

March 13, 1959



The attached paper is a description of the LISP system starting with the machine-independent system of recursive functions of symbolic expressions. This seems to be a better point of view for looking at the system than the original programming approach. After revision, the paper will be submitted for publication in a logic or computing journal. This memorandum contains only the machine independent parts of the system. The representation of S-expressions in the computer and the system for representing S-functions by computer subroutines will be added.


Author[s]: S. R. Russell

Explanation of Big "P" as of March 20, 1959

March 1959



ERROR is a routine to provide a common location for all routines. Its celling sequence is: SXD SERROR,4 TSX SERROR+1,4 The above is normally followed immediately by up to 20 registers of BCD remarks terminated by a word of 1’s. This may be left out, however. ERROR prints out the remark, if any, the location of the TSX that entered error, restores the console except for the AC overflow, and transfers to the user’s error routine specified by the calling sequence of SETUP.


Author[s]: K. Maling

The LISP Differentiation Demonstration Program

no date listed



This program is a byproduct of the machine language which is being developed for the Artificial Intelligence project. It was written because the process of differentiation and to some extent that of simplification, turned out to be very conveniently expressable in LISP. There are two main reasons for this: one is the fact that algebraic expressions are most easily represented in a computer by means of a list language and the other is the ability of LISP to describe recursive processes.


Author[s]: J. McCarthy

Recursive Functions of Symbolic Expressions and Their Computation

March 30, 1959



This memorandum is a continuation of Memo 8.


Author[s]: John McCarthy

Programs in LISP

no date listed



?pends only on the RLE QPR No. 53 discussion of LISP. Its objective is to add to the system of that report a program feature. This takes the form of allowing functions to be defined by programs including sequences of Fortran-like statements, e.g. Y= cons[ff[subst[A;y;z]]; (A,B)] Such a feature was included in the informal version of LISP from which we hand-compiled into SAP and is also available in the latest version of the apply operator. The version in the present apply operator is added merely as a convenience and does not have the mathematical elegance that we require. In the present memorandum, I will try to add a program feature to the system in a systematic way. It may be some time before this version is available in the programming system.


Author[s]: K. Maling

Symbol Manipulating Language - The Maling-Silver Read Program

no date listed



Three types of expressions can read (1) m – expressions (2) s - expressions (3) algebraic expressions The program uses RDB, which means that single embedded blanks may be part of a print name; that a left parenthesis followed by, or a right parenthesis preceded by, any combination of periods and commas is treated as a special parenthesis; and that any combination of + - = * 1 is an "operation" group.


Author[s]: J. McCarthy

The Wang Algorithm for the Propositional Calculus Programmed in LISP

no date listed



This memorandum describes a LISP program for deciding whether an expression in the propositional calculus is a tautology according to Wang’s algorithm. Wang’s algorithm is an excellent example of the kind of algorithm which is conveniently programmed in LISP, and the main purpose of this memorandum is to help would-be users of LISP see how to use it.


Author[s]: John McCarthy

SML-Examples of Proofs by Recursion Induction

no date listed



Recursion induction has turned out to have certain bugs and some restrictions have to be imposed. The proofs given in the sections of my notes reproduced below probably will turn out to satisfy whatever restrictions have to be imposed.


Author[s]: Anthony Valliant Phillips

A Question-Answering Routine

no date listed



A program has been written in the LISP programming language to answer English- language questions by consulting an English- language text. The program can handle questions about the subject, verb, place and time of simple sentences. The program proceeds in two steps. In the first, the machine analyzes the question and the sentences of the text, puts them into a form in which they can be compared. For this analysis the machine must have as input a dictionary of part-of-speech tags, and a set of rules, analogous to phrase-structure rules, according to shich it will organize the sentences. This analysis organizes the sentences into noun-phrases, verbs, and prepositional phrases. The machine then picks from the sentence a subject, a verb, an object, and prepositional phrases relating to place and time. This is the "canonical form" of the sentence. The next part of the program compares the question with each of the sentences in the text. Those that match, i.e. contain the information the question is asking for, are stored and the answer is made up from them. If none are found, an appropriate negative answer is given.


Author[s]: John McCarthy

Programs with Common Sense

no date listed



Interesting work is being done in programming computers to solve problems which require a high degree of intelligence in humans. However, certain elementary verbal reasoning processes so simple that they can be carried out by any non-feeble-minded human have yet to be simulated by machine programs. This paper will discuss programs to manipulate in a suitable formal language (most likely a part of the predicate calculus) common instrumental statements. The basic program will draw immediate conclusions from a list of premises. These conclusions will be either declarative or imperative sentences. When an imperative sentence is deduced the program takes a corresponding action. These actions may include printing sentences, moving sentences on lists, and reinitiating the basic deduction process on these lists. Facilities will be provided for communication with humans in the system via manual intervention and display devices connected to the computer.


Author[s]: Louis Hodes

Some Results from a Pattern Recognition Program Using LISP

no date listed



This paper describes some aspects of an elaborate pattern recognition system being programmed by the author under the supervision of Marvin Minsky. A more detailed discussion is forthcoming as a Lincoln Laboratory group report.


Author[s]: Daniel J. Edwards

LISP II Garbage Collector

no date listed



The present LISP free storage control program, the garbage collector, has a severe limitation in that it can handle well only list structure. LISP II will be able to handle arrays, binary progras and other quantitites, therefore the garbage collector will have to be able to recognize these quantities and control free storage accordingly. Since arrays and binary programs require blocks of contiguous free storage, the garbage collector must be able to relocate items to be saved in order to coalesce the isolated blocks of items discarded into one contiguous block.


Author[s]: John McCarthy

Puzzle Solving Program in LISP

no date listed



In this note we give as an example of LISP programming a function for solving a class of puzzles in a recent prize contest.


Author[s]: Paul Abrahams

The Proofchecker

January 1961



The Proofchecker is a heuristically oriented computer program for checking mathematical proofs, with the checking of textbook proofs as its ultimate goal. It constructs, from each proof step given to it, a corresponding sequence of formal steps, if possible. It records the current state of the proof in the form of what it is sufficient to prove. There are two logical rules of inference: modus powers and insertion (if it is sufficient to prove B, and A is the theorem, then it is sufficient to prove A implies B). The permissible formal steps include these rules of inference as well as provision for handling definitions, lemmas, calculations, and reversion to previous states. As of now, most of the formalisms are programmed and partially debugged, but the heuristic aspects have yet to be programmed.


Author[s]: Paul Abrahams

Character-Handling Facilities in the LISP System

January 1961



Because of the new read program, a number of facilities are being added to the LISP system to permit manipulation of single characters and print names. Machine-language functions have been provided for breaking print names down into a list of their characters, for forming a list of characters into a print name, for creating a numerical object from a list of its characters, for reading in characters one by one from an input medium, and for testing characters to see whether they are letters, numbers, operation characters, etc. A number of auxiliary objects and sub-routines are also described in this memo.


Author[s]: Robert Brayton

Trace Printing for Compiled Programs

no date listed



The compiler now has a tracing feature which is equivalent to the TRACLIS feature of the interpreter. COMPILE MODE is a function of one argument which must be either TRACE or NORMAL.


Author[s]: Michael Levin

Arithmetic in LISP 1.5

April 1961



As of the present, the following parts of LISP 1.5 are working. This is an excerpt from the forth coming LISP 1.5 Programmer’s Manual.


Author[s]: No author

LISP Error Stops as of May 10, 1961

May 1961



no abstract


Author[s]: Michael Levin


no date listed



Errorset is a function available to the interpreter and compiler for making a graceful retreat from an error condition encountered during a subroutine.


Author[s]: Timothy Hart


no date listed



Simplify is a compilable set of 45 8- expression-defined functions which simplify algebraic expressions. The expressions which are appropriate for simplify are defined recursively as follows: P= all atoms, fixed and floating point numbers, Q= all expressions of the form: (PLUS, s1, s2,…,Sn), (PRDCT, s1,s2,…Sn), (MINUS, . s), (RECIP . s), (DIVIDE. S1, s2), (POWER, s 1, s2), (SUBT, s1 , s2), where s, s1, s2, …, Sn E P UQ. Simplify is a function, not a pseudo-func tion, that is, the list structure of an expressio n is not modified by simplify. Simplify takes 6 000 words of free storage when stored as ** S-expression and about 9000 words whe n compiled. It takes about 5 minutes to read all the functions into the 709 using the online card reader, and about 4 minutes from tape.


Author[s]: Michael Levin

Information About the LISP 1.5 Programmer's Manual

no date listed



This memo is to be issued simultaneously with the new LISP 1.5 Programmer's Manual. At the present time, the manual is without a general index and without any appendicies. Appendix A is planned as a complete list of functions within the LISP system, and will be issued shortly. Other appendices will contain detailed information about the interpreter, input-output, and system operation. The manual is intended to apply to a version of LISP 1.5 called "LISP 1.5 Export A" which has not yet been issued. LISP 1.5 systems preceding this version differ in certain details.


Author[s]: Bertram Raphael

Introduction to the Calculus of Knowledge

November 1961



This paper deals with the "Calculus of Knowledge", an extension of the propositional calculus in which one may reason about what other people know. Semantic and Syntactic systems are developed, certain theorems are proven, and a formal solution in the system of a well-known reasoning problem is presented.


Author[s]: D.J. Richards and T.P. Hart

The Alpha-Beta Heuristic

December 1961



The Alpha-Beta heuristic is a method for pruning unneeded branches from the move tree of a game. The algorithm makes use of information gained about part of the tree to reject those branches which will not affect the principle variation.


Author[s]: John McCarthy

A Basis for a Mathematical Theory of Computation

January 1962



This paper is a corrected version of the paper of the same title given at the Western Joint Computer Conference, May 1961. A tenth section discussing the relations between mathematical logic and computation has been added. Programs that learn to modify their own behaviors require a way of representing algorithms so that interesting properties and interesting transformations of algorithms are simply represented. Theories of computability have been based on Turing machines, recursive factions of integers and computer programs. Each of these has artificialities which make it difficult to manipulate algorithms or to prove things about them. The present paper presents a formalism based on conditional forms and recursive functions whereby the functions computable in terms of certain base functions can be simply expressed. We also describe some of the formal properties of conditional forms and a method called recursion induction for proving facts about algorithms. A final section in the relations between computation and mathematical logic is included.


Author[s]: John McCarthy

On Efficient Ways of Evaluating Certain Recursive Functions

no date listed



The purpose of this memorandum is to illustrate a method for evaluating a recursive function when the same subexpression may occur many times during the evaluation and should be evaluated only once.


Author[s]: Marvin L. Minsky

Universality of (p=2) Tag Systems and a 4 Symbol 7 State Universal Turing Machine

no date listed



This report describes (1) an improvement and great simplification of the proof that the "Tag" systems of Post can represent any computable process, and (2) a Universal Turing machine with just four symbols and seven states -- the smallest yet reported.


Author[s]: John McCarthy

A New Eval Function

no date listed



The actual working definition of eval describes how the LISP system determines what, if anything, is denoted by a given S-expression. As things now stand, there are two versions of eval: the theoretical version, given in RFSE, and the system version. Neither of these behaves in the most desirable way; and there exist S-expressions which will be handled correctly by the theoretical version but not by the system version, and conversely. The chief defect of the system eval lies in its handling of functional arguments; the chief defect of the RFSE eval lies in its ignorance of property lists. If we wish to have a theory about how LISP really works, then it is necessary to have a version of eval which is satisfactory both theoretically and practically. I will propose a definition for eval, and then illustrate how this eval differs from the existing system and RFSE definitions by means of examples.


Author[s]: None listed

LAP (LISP Assembly program)

no date listed



LAP is an internal two pass assembler for LISP 1.5. It is a pseudo-function with two arguments called the listing and the symbol table.


Author[s]: Michael Levin, Marvin Minsky and Roland Silver

On the Effective Definition of "Random Sequence"

no date listed



Mathematicians have always had difficulty in coming to agreement over what is meant by "randomness". In order to agree on a formal model for a "random process", we have to agree on what intuitive aspects of the matter we want to build into our system. The most prominent point of agreement is that the process should be unpredictable, but this is in itself is a very small beginning. The solution that has become conventional in modern mathematics is based on the notion of "random variable", a highly technical notion in which the basic process is represented as a certain kind of infinite function-space. This space contains all possible observed behavior sequences together with a "measure" structure which enables one to calculate the relative frequency of certain ("measurable") complex events. "Event" here usually refers to a whole class of behaviors


Author[s]: Lewis M. Norton

Some Identities Concerning the Function Subst [x; y; z]

January 1962 (Revised March 1962)



The purpose of this paper is two-fold; 1) to explore the use of recursion induction in proving theorem about functions of symbolic expressions, in particular. 2) to investigate thoroughly the algebraic properties of the LISP function subst [x; y; z] by this method. The main result is embodied in Theorem 8.


Author[s]: Bert Raphael

Machine Understanding of Linguistic Information: A Survey and Proposal

no date listed



For the past few months I have been studying the problem of how to make a computer understand linguistic information (in some generally accepted sense of "understand". I have listened to courses on Linguistic Structure (Dr. Chomsky) and Mechanical Translation (Dr. Yngve), and read the works of various linguists, ranging through semantics, information retrieval, and mechanical translation. The remainder of this paper is divided into two parts: a survey of various ideas and results appearing in the current literature (with some editorial comment); and a proposal for future work to include a computer system for storing and extracting semantic information.


Author[s]: T. Hart and M. Levin

The New Compiler

no date listed



This memo introduces the brand new LISP 1.5 Compiler designed and programmed by Tim Hart and Mike Levin. It is written entirely in LISP and is the first compiler that has ever compiled itself by being executed interpretively.


Author[s]: Donald Dawson

A Note on the Possibility of Application of the Davis Putnam Proof Procedure to Elementary Number Theory

no date listed



In ref.1 Davis and Putnam present a computational proof procedure for quantification theory which they suggest might be applied to obtain proofs in mathematical domains. In ref.2 they give a finite axiom system for elementary number theory with the aim of applying the computational proof procedure to it. In ref.3 Wang points out that as it stands this procedure would be far too inefficient to prove non trivial theorems and discusses how it might be made more efficient. In this note we will indicate that even the type of modification that Wang considered would not be sufficient to enable the system to prove non trivial theorems.


Author[s]: A. Kotok

A Chess Playing Program

no date listed



This paper covers the development of a chess playing program. The preliminary planning led to the decision to use a variable depth search, terminating at either an arbitrary maximum, or at a stable position. Two schemes of controlling material balance are discussed. Or major significance is the use of the "alpha- beta" heuristic, a method of pruning the tree of moves. This heuristic makes use of values obtained at previous branches in the tree to eliminate the necessity to search obviously worse branches later. The program has played four long game fragments in which it played chess comparable to an amateur with about 100 games experience.


Author[s]: Bert Raphael

Proposal for a General Learning Machine

no date listed



This memo proposes the development of a computer system which is capable of learning certain facts about arbitrary subject matter with an arbitrary vocabulary. It is believed by most researchers in this field that some sort of general learning machine is essential for the ultimate solution of the "Artificial Intelligence Problem." I believe that the system described below, which will be programmed to construct internal models based on the concepts indicated by the syntactic structure of the input text (but not on the specific subject area), will constitute a significant step toward such a machine.


Author[s]: Marvin Minsky

A Simple Direct Proof of Post's Normal Form Theorem

no date listed



The theorem proved in this note is the Normal Form Theorem proved in Post"s 1943 paper, "Formal Reductions of the General Combinatorial Decision Problem". We have long felt that this result is one of the most beautiful in mathematics. The fact that any formal systems can be reduced to Post canonical systems with a single axiom and productions of the restricted form.


Author[s]: Daniel G. Bobrow

A Question-Answerer for Algebra Word Problems

no date listed



This is a proposal to write a program which, starting from input statements of problems in a restricted English, will be able to formulate problems symbolically and then solve problems from elementary algebra.


Author[s]: T.G. Evans

A Heuristic Program to Solve Geometric Analogy Problems

October 1962



A program to solve a wide class of intelligence-test problems of the "geometric-analogy" type ("figure A is to figure B as figure C is to which of the following figures?") is being constructed. The program, which is written in LISP, uses heuristic methods to (a) calculate, from relatively primitive input descriptions, "articular" (cf. Minsky, Steps Toward Artificial Intelligence) descriptions of the figures, then (b) utilize these descriptions in finding an appropriate transformation rule and applying it, modifying it as necessary, to arrive at an answer. The current version has solved a number of geometric-analogy problems and is now being modified in several ways and run on further test cases.


Author[s]: Burton H. Bloom

A Proposal to Investigate the Application of a Heuristic Theory of Tree Searching to a Chess Playing Program

February 1963



The problem of devising a mechanical procedure for playing chess is fundamentally the problem of searching the very large move-tree associated with a chess position. This tree-searching problem is representative of a large class of problems. Consequently, we will first present briefly a general theory of tree-searching problems. This theory will be useful in clarifying the intention of our proposed research.


Author[s]: Marvin Minsky

Neural Nets and Theories of Memory

March 1963



A number of models developed in work often called "neural-net" research may be of interest to physiologists working on the problem of memory. From this work comes a variety of ideas on how networks of neuron-like elements can be made to act as learning machines. Some of these may suggest ways in which memory may be stored in nervous systems. It is important, perhaps, to recognize that these models were not founded at all on physiological ideas; they really stem from psychological and introspective notions. They all involve some form of alteration of synaptic transmission properties contingent on the pre- and post-synaptic activity during and after the relevant behavior. This notion is suggested not so much by actual observation of synapses as by the introspective simile of wearing down a path -- the "ingraining" of a frequently-traveled route. Below we shall argue that this idea is useful and suggestive, but not sufficient. These models can be made to account for learning connections between stimuli and responses on a low level, but do not seem to account for higher, symbolic behavior. We will argue that the latter suggests a return to the search for localization of memory, a topic that has been unpopular for many years.


Author[s]: Bertram Raphael

Computer Representation of Semantic Information

April 1963



A major obstacle in the development of learning machines, mechanical translation, advanced information retrieval systems, and other areas of artificial intelligence, has been the problem of defining, encoding, and representing within a computer the "meaning" of the text data being processed. Various devices have been used to avoid this problem, but very little work has been done toward solving it. The purpose of this memo (and the thesis research with which it is associated) is to describe one possible solution, and report on a computer program which demonstrates its feasibility.


Author[s]: Richard A. Robnett

Suggested Conventions for LISP Time-Sharing System

April 1963



Below is a list of suggested Conventions and De-bugging aids for LISP time-sharing. Any and all suggestions are encouraged and should be submitted in writing to R. A. Robnett in a hurry.


Author[s]: Daniel G. Bobrow

METEOR: A LISP Interpreter for String Transformations

April 1963



Conditional expressions, composition and recursion are the basic operations used in LISP to define functions on list structures. Any computable function of arbitrarily complex list structures may be described using these operations, but certain simple transformations of linear lists (strings) are awkward to define in this notation. Such transformations may be characterized (and caricaturized) by the following instructions for a transformation: "Take that substring there, and that other one starting with "Black", which has the substring mentioned third as the first; then inserts the second substring mentioned; omit the first and leave the unmentioned parts of the original string unchanged."


Author[s]: John Cooke and Marvin Minsky

Universality of TAG Systems with P-2

April 1963



In the following sections we show, by a simple direct construction, that computations done by Turing machines can be duplicated by a very simple symbol manipulation process. The process is described by a simple form of Post Canonical system with some very strong restrictions. First, the system is monogenic; each formula (string of symbols) of the system can be affected by one and only one production (rule of inference) to yield a unique result. Accordingly, if we begin with a single axiom (initial string) the system generates a simply ordered sequence of formulas, and this operation of a monogenic system brings to mind the idea of a machine. The Post canonical system is further restricted to be of the "Tag" variety, described briefly below. It was shown in [1] that Tag systems are equivalent to Turing machines. The proof in [1] is very complicated and uses lemmas concerned with a variety of two-tape non-writing Turing machines. Our proof here avoids these otherwise interesting machines and strengthens the main result, obtaining the theorem with a best possible "deletion number" P – 2. Also, the representation of the Turing machine in the present system has a lower degree of exponentiation, which may be of significance in applications. These systems seem to be of value in establishing unsolvability of combinatorial problems.


Author[s]: Warren Teitelman


no date listed



This report describes the use of ARGUS, a program that recognizes hand-drawn characters in real time. The program is a result of research reported in "New Methods for Real-Time Recognition of Hand-Drawn Characters", submitted in partial fulfillment of the requirements for the degree of Master of Science. The report does not assume any previous knowledge of the theory behind ARGUS, but some of the discussion may be more meaningful if the reader refers to the thesis mentioned above.


Author[s]: Joel Winett

Proposal for a FAP Language Debugging Program

June 1963



A time-sharing system for the 7090 computer is being developed at the M.I.T. Computation Center whereby many users can communicate simultaneously with the computer through individual consoles. In the time-sharing system a time-sharing supervisor (TSS) program directs the running of each user’s program in such a manner that each user’s program is run in short bursts of computation. The effect is that the user sitting at his console has complete control over his program with unrestricted use of a large computing machine. Through the use of commands in the time-sharing system a user who writes a program in the FAP language can assemble his program, load it into core, and start the program. In order to make the most use of the time-sharing facility the user during the debugging stages of his program will want to dynamically monitor his running program and make changes as necessary. The proposed FAP language debugging program gives the user the facility to communicate with his program using the symbols defined within his program.


Author[s]: Michael Levin

Primitive Recursion

July 1963



This is one of a series of memos concerning a logical system for proof-checking. It is not self-contained, but belongs with future memos which will describe a complete formal system with its intended interpretation and application. This memo also assumes familiarity with LISP and with "A Basis for a Mathematical Theory of Computation" by John McCarthy.


Author[s]: Timothy P. Hart

A Proposal for a Geometry Theorem Proving Program

September 1963



During the last half of the nineteenth century the need for formal methods of proof became evident to mathematicians who were making such confidence-shaking discoveries as non-Euclidean geometry. The demand is not to be denied; every jump must be barred from our deductions. That it is hard to satisfy must be set down to the tediousness of proceeding step by step. Every proof which is even a little complicated threatens to become inordinately long. [M1] G. Frege, 1884 This general desire for rigor has persisted since that time, and a great deal has been learned about formal methods. But, for the reason noted by Frege, very little of real mathematics has been done with full formal treatment. Our present hope is to use computers to take the drudgery out of formal demonstrations, just as they are taking it out of accounting. Toward this end, several programs are under way. They vary in purpose; the Proofchecker [H8, H9] is to be capable of filling the gaps of a proof; the work of Mott et. al. [H10] aims to achieve the equivalent of a desk calculator ability as an aid to a mathematician doing formal proofs. The most intriguing prospect, however, is that computers can eventually be made to both devise and prove interesting non-trivial theorems wholly on their own. The first of these desires, the devising of interesting conjectures, has not even been attempted. I believe, however, that we are on the verge of achieving the second of these ends, the mechanical proof of non-trivial theorems, a belief which I hope I can justify in the sequel.


Author[s]: Timothy P. Hart

MACRO Definitions for LISP

October 1963



In LISP 1.5 special forms are used for three logically separate purposes: a) to reach the alist, b) to allow functions to have an indefinite number of arguments, and c) to keep arguments from being evaluated. New LISP interpreters can easily satisfy need (a) by making the alist a SPECIAL-type or APVAL-type entity. Uses (b) and (c) can be replaced by incorporating a MACRO instruction expander in define. I am proposing such an expander.


Author[s]: M.L. Minsky

A LISP Garbage Collector Algorithm Using Serial Secondary Storage

December 27, 1963



This paper presents an algorithm for reclaiming unused free storage memory cells in LISP. It depends on availability of a fast secondary storage device, or a large block of available temporary storage. For this price, we get: 1.) Packing of free-storage into a solidly packed block. 2.) Smooth packing of arbitrary linear blocks and arrays. 3.) The collector will handle arbitrarily complex re-entrant list structure with no introduction of spurious copies. 4.) The algorithm is quite efficient; the marking pass visits words at most twice and usually once, and the loading pass is linear. 5.) The system is easily modified to allow for increase in size of already fixed consecutive blocks, provided one can afford to initiate a collection pass or use a modified array while waiting for such a pass to occur.


Author[s]: Bertram Raphael

Operation of a Semantic Question-Answering System

November 1963



A computer program has been written in the LISP programming language which accepts information and answers questions presented to it in a restricted form of natural English language. The program achieves its effects by automatically creating, adding to, and searching a relational model for factual information. The purpose of this memo is to describe and explain the behavior of the program. The remainder of this section briefly describes the structure of the model. Section II presents sample conversations illustrating various features of the program, and describes the implementation of those features. Section III is a brief survey of conclusions drawn from this research. It is assumed throughout that the reader is at least somewhat familiar with the LISP programming system (and its meta-language notation), the concept of property (description) lists, and the usual notations of Mathematical Logic.


Author[s]: D.J. Edwards and M.L. Minsky

Recent Improvements in DDT

November 1963



This paper will report new developments and recent improvements to DDT. "Window DDT" now will remember undefined symbols and define them on a later command. Using sequence breaks, it can change the contents of memory while a program is running, and the contents of memory can be displayed in symbolic form on the scope.


Author[s]: Marvin Minsky

MATHSCOPE Part I: A Proposal for a Mathematical Manipulation-Display System

November 1963



Mathscope: A compiler for two-dimensional mathematical picture syntax. Mathscope is a proposed program for displaying publication-quality mathematical expressions given symbolic (list-structure) representations of the expressions. The goal is to produce 'portraits' of expressions that are sufficiently close to conventional typographic conventions that mathematicians will be able to work with without much effort -- so that they do not have to learn much in the way of a new language, so far as the representation of mathematical formulae is concerned


Author[s]: Marvin Minsky

DERIVATOR I: A Program for Visual Inspection of Solutions to First-Order Non-Linear Differential Equations

December 1963



Derivator is a PDP-1 program for examining the solutions to differential equations by inspection of a visual display of trajectories. Because fixed-point arithmetic is used (in order to maintain visual display speeds), Derivator must be regarded as a qualitative tool. It is subject to truncation error in the trajectory-following program, and round-off error due to 'underflow' in the function-definition programs for dy and dx. Still it appears to be very suitable for studying topology of solutions around singularities, etc. The display shows the solution curves ('characteristics') in the x-y plane. They are generated parametrically.


Author[s]: Daniel J. Edwards

Secondary Storage in LISP

December 1963



A principal limitation of LISP processors in many computations is that of inadequate primary random-access storage. This paper explores several methods of using a secondary storage medum (such as drums, disk files or magetic tape) to augment primary storage capacity and points out some limitations of these methods


Author[s]: Timothy P. Hart and Michael Levin

LISP Exercises

January 1964



The following exercises are carefully graded to mesh with the sections in Chapter I, "The LISP Language", in the LISP 1.5 Programmer's Manual. Each exercise should be worked immediately after reading the manual section indicated.


Author[s]: Marvin Minsky

The Graphical Typewriter: A Versatile Remote Console Idea

January 1964



It would be useful to develop a combination typewriter-plotter along the lines described below. The device could be coupled to a telephone line with a reasonably small amount of electronics -- mostly relays.


Author[s]: Daniel G. Bobrow

Natural Language Input for a Computer Problem Solving System

March 1964



This paper describes a computer program which accepts and "understands" a comfortable, but restricted set of one natural language, English. Certain difficulties are inherent in this problem of making a machine "understand" English. Within the limited framework of the subject matter understood by the program, many of these problems are solved or circumvented. I shall describe these problems and my solutions, and point out those solutions which I feel have general applicability. I will also indicate which must be replaced by more general methods to be really useful, and give my ideas about what general solutions to these particular problems might entail.


Author[s]: William Martin and Timothy Hart


April 1964



This memo describes changes to the LISP system by several people. The changes reduce printout and give the user more control over it. They also make it possible for LISP to communicate with the teletype and the disk. The last sections describe programs available in the public files which are useful for printing, editing, and debugging LISP functions.


Author[s]: Michael Levin

Syntax of the New Language

May 1964



This is a definition of the syntax of the *** language. It consists of modifications and extensions of the "Revised Report on the Algorithmic Language ALGOL 60" which is printed in the "Communications of the ACM", January 1963. The paragraph numbering of that report is used in this paper. The corrections and additions are made partially in Backus normal form, and partially in English, and the choice has been made on the basis of convenience. For example, the use of the weak separator is described readily in a few sentences, whereas the modification to incorporate this into the syntax as described in Backus normal form would have been extensive.


Author[s]: Michael Levin

New Language Storage Conventions

May 1964



These conventions are for the implementation of the new language on a large computer on which time-sharing is the standard role of operation. Each user is at any time asigned a certain amount of primary storage. This can eb the entire memory of the machine for non time-shared operation. When this quota is filled, then it is necessary either to extend it, or to have the reclaimer routine compact the user's storage. This decision can be made at run time and may be based on the user's storage requirements, and on the cost of primary memory at that particular instant. This may in turn depend on the degree of saturation of the system.


Author[s]: William A. Martin

Hash-Coding Functions of a Complex Variable

June 25, 1964



A common operation in non-numerical analysis is the comparison of symbolic mathematical expressions. Often equivalence under the algebraic and trigonometric relations can be determined with the high probability by hash-coding the expressions using finite field arithmetic and then comparing the resulting hash-code numbers. The use of this scheme in a program for algebraic simplification is discussed.


Author[s]: Daniel G. Bobrow

String Manipulation in the New Language

July 1964



String manipulation can be made convenient within the *** language by implementing two functions: 1) match [workspace; pattern] and 2) construct {format;pmatch]. In this memo I describe how I think these two functions can be implemented, and how they might be used to express operations now conveniently denoted in string manipulation languages such as COMIT, SNOBOL, and METEOR.


Author[s]: Michael Levin

Proposed Instructions on the GE 635 for List Processing and Push Down Stacks

September 1964



The instructions that transmit data between the index registers and the memory work only on the left half (address) portion of memory. These instructions are LDXn (load index n from address of storage word). And STXn (store the contents of index n in address of storage word). The effective address of both of these instructions includes modification by index registers. A corresponding set of instructions for transmitting data to or from the right half of memory would facilitate list structure operations. The present order code makes it impossible to so list-chaining operations (car or cdr) without disturbing the A or Q registers.


Author[s]: Marvin Minsky and Seymour Papert

Unrecognizable Sets of Numbers

November 1964



When is a set A of positive integers, represented as binary numbers, "regular" in the sense that it is a set of sequences that can be recognized by a finite-state machine? Let pie A(n) be the number of members of A less than the integer n. It is shown that the asymptotic behavior of pie A(n) is subject to severe restraints if A is regular. These constraints are violated by many important natural numerical sets whose distribution functions can be calculated, at least asymptotically. These include the set P of prime numbers for which pie P(n)~n/log n for large n, the set of integers A (k) of the form n to the power k for which pie A(k)(n)1/k, and many others. The technique cannot, however, yield a decision procedure for regularity since for every infinite regular set A there is a nonregular set A for which /pie Z(n)-pie A(n)/is less than or equal to 1, so that the asymptotic behaviors of the two distribution functions are essentially identical.


Author[s]: T. Hart

CTSS LISP Notice-Supplement to A.I. Memo No. 67

December 1964



The LISP system (command version) has been updated. Bugs are corrected include: 1. out of pushdown list in compiled function will not transfer to 77777. 2. with compiler printing turned off by comprint, it is truly off. 3. "ERROR54A/" when running comiled program no longer occurs. 5. CSET and CSETQ have their proper values. 6. the public versions of PRINT DATA and EDIT DATA have been improved. In particular, the function DEFINELIST has been removed from PRINT; EDIT has had a minor bug in filelistadd corrected, and the functions filelistdelete [1; x; y] and extract [1; n; m] added. The former deletes the function on the list 1, from file n m and writes a new file n EDIT with these changes made. The latter extracts the function 1 from the file n DATA and adds them to the file m DATA, updating the disc by writing appropriate EDIT class files.


Author[s]: Marvin Minsky

Television Camera-To-Computer Adapter: PDP-6 Device 770

January 1965



The TVA (Television Adaptor) is a data-input device just completed. Any standard Closed-Circuit Television Camera can be connected to the PDP-6, without modification, by a single BNC connector. Then a simple program can make a digitized image of selected size and position appear in core memory. Operation is automatically controlled by the PDP-6 priority-interrupt system so that, to the programmer, the core-image is automatically read-in and maintained. This is an open invitation to come in and discuss applications. We are particularly interested in (i) projects leading to a working page-reader system, first for teletype character sets and later to include recognition of larger alphabets and hand-written corrections, and (ii) projects leading to recognition functions that will be useful in coordination with the mechanical hand system.


Author[s]: Daniel G. Bobrow

The COMIT Feature in LISP II

February 1965



The purpose of COMIT feature is to facilitate certain types of list manipulations in LISP II. This feature is a syntactic convenience, rather than an extension of the semantics of LISP. It permits the programmer to test directly whether a piece of list structure matches a certain pattern, and if so, to construct another structure utilizing subsegments of the original structure which matched parts of the given pattern.


Author[s]: Marvin Minsky

Matter, Mind and Models

March 1965



This paper attempts to explain why people become confused by questions about the relation between menal and physical events. When a question leads to confused, inconsistent answers, this may be (1) because the question is ultimately meaningless or at least unanswerable, but it may also be (2) because an adequate answer requires a powerful analytical apparatus. My view is that many important questions about relation between mind and brain are of this latter kind, and that some of the necessary technical and conceptual tools are becoming available as a result of work on he problems of making computer programs behave intelligently. In this paper we suggest a theory of why introspection does not give clear answers to these questions. The paper does not go very far toward finding technical solutions to the questions, but there is probably some value in finding at least a clear explanation of why we are confused.


Author[s]: Michael Levin

Topics in Model Theory

May 1965



The concept of "free" as in free group and free semi-group is extended to arbitrary first order theories. Every consistent theory has free models. Some problems of obtaining a categorical theory of models are discussed.


Author[s]: William A. Martin

PDP-6 LISP Input-Output for the Dataphone

June 1965



A version of LISP 1.5 for the PDP-6 Computer has been extended to include IO through the dataphone. This makes possible communication between programs running in Project MAC time sharing and LISP programs running on the PDP-6. The method of handling input-output for the dataphone is similar to that for the typewriter, paper tape punch, and paper tape reader. Three useful LISP functions are presented as examples of dataphone programming.


Author[s]: William Martin

PDP-6 LISP Input-Output for the Display

June 1965



An intermediate level language for display programming has been embedded in LISP 1.5 The language is intended as a basis for higher analysis of display information. Through the construction of a hierarchy of LISP functions it will be possible to assign a complicated meaning to a series of simple light pen motions, or to construct a complex picture. The intermediate level of language should abstract from the light pen trajectory the information which these LISP functions require and provide basis for time, and programming effort. The first section of this memo discusses the system and gives programming examples. The details of the examples can be understood by reading the second section which discusses the implementation and the LISP functions available.


Author[s]: Peter Samson


July 1965



TECO is a scope-keyboard text- editor. It uses an on-line command language (which permits macro-definitions, corditional, etc.) as well as text operations. The macro language permits the most sophisticated search, match, and substitution operations as well as simple typographical corrections to text.


Author[s]: Peter Samson

MAC PDP-6 DECtape File Structure

July 1965



The MAC system programs, MACDMP, TECO, and MIDAS, assume a certain data structure on DECtapes which they handle. Each DECtape has 1100 blocks of 200 words, numbered 0 through 1077. Block 0 and blocks 1070 through 1077 are not used by the MAC system. Block 100 of each tape contains the File Directory: a 200-word table describing the current contents of blocks 1 through 1067. The data on the tape is organized into files, each file consisting of one or more blocks. Each file has a name and a mode: the name is composed of 2 six-character subnames, and the mode is a two-bit number. The File Directory has space for 27 files.


Author[s]: Peter Samson


July 1965



MACIMP is a PDP-6 program which can load from DECtape to core memory, dump core onto DECtape, or verify a previously dumped filel against memory. Normally, just before it loads, it clears all of memory to 0 (except itself and locations 0 through 37); and, in general, it does not dump locations containing 0. (It also does not dump itself, or locations 0 through 37.) In this way, a short program uses only a few blocks on tape. MACIMP uses the MAC PDP-6 file structure and directory scheme, and writes files in mode 1.


Author[s]: Warren Teitelman

EDIT and BREAK Functions for LISP

no date listed



This memo describes some LISP functions which have been found to be extremely useful in easing the often painful process of converting the initial versions of LISP programs into final debugged code. They are part of a much larger system currently being developed but may be used as two independent packages. The break package contains a more sophisticated break function than that in the current CTSS version of LISP, which includes facilities for breaking on undefined functions as well as SUBRS and FEXPS, plus a selective TRACE feature.


Author[s]: William Martin

Syntax and Display of Mathematical Expressions

July 1965



A LISP program converts a mathematical expression stored in list structure form, into a text-book style visual display. To do this, requires the selection and positioning of the individual symbols which make up the expression, using a combination of global and local information. This memo describes a table-driven picture-compiler which makes the necessary information available. Syntax rules have been written for a large class of mathematical expressions. These rules are simplified by the introduction of concepts concerning the relative position of symbols. In addition to the symbols and their coordinates the program sends a parsing of the symbols to the display. This program is a refinement of the system proposed by M.L. Minsky in Artificial Intelligence Memo 61, 'Mathscope: Part I'.


Author[s]: Marvin Minsky

Design of the Hand

August 1965



The following scheme for designing a general-purpose manipulator organ has many theoretical attractions. The basic idea is perhaps best conceived as a theoretical, or mathematical, idea. While it is unlikely that the actual system will be very much like it, it may have value as a sort of ideal against whose elegance we can match engineering and practical compromise.


Author[s]: Warren Teitelman

FLIP - A Format List Processor

July 1967



This memo describes a notion of programming language for expressing, from within a LISP system, string manipulation such as those performed in COMIT. The COMIT formalism has been extended in several ways: the patterns (the left-half constituents of COMIT terminology) can be variable names of the results of computation; predicates can be associated with these elementary patterns allowing more precise specifications of the segments they match; the names of elementary patterns themselves may be variable or the results if computation; it is no longer necessary to restrict the operations to a linear string of characters (or words) since elementary patterns can themselves match structures; etc. Similar generalizations exist for formats, i.e. what corresponds to the right-half of the COMIT rule.


Author[s]: Peter Samson

MACTAP: A PDP-6 DECtape Handling Package

September 1965



MACTAP is a set of PDP-6 subroutines to read and write DECtape in the MAC file format (see MAC-M-249). Programmers can call these subroutines for input or output of ASCII data, which will be compatible with TECO files; or for binary (36. -bit word) data. They were extracted mainly from PDP-6 TECO and arranged and checked out in their present form by Jack Holloway.


Author[s]: W.D. Maurer

Computer Experiments in Finite Algebra-II

December 1965



In a previous memo (Computer Experiments in Finite Algebra, MAC-M-245) we described a computer system for the handling of finite groups, semigroups, subsets, finite maps, and constants. This system has been extended to read and write disk files; a mechanical procedure has been developed for extending the system; and a program (the inferential Compiler) has been written which accepts a source language consisting of mathematical statements in a standard format and compiles code which verifies these statements over a file or files of special cases (including possible counterexamples). Three limitations of the system were mentioned in the previous memo. Of these, (1) and (3) have been effectively eliminated in the current system. Limitation (2) still exists and will be overcome only in ALGEBRA III, which is briefly described in section 4.


Author[s]: W.D. Maurer

Computer Experiments in Finite Algebra

June 1965



The experiments described here concern an initial design for a computer system specifically for the handling of finite groups, rings, fields, semigroups, and vector spaces. The usefulness of such a system was discussed in (1). The system has been coded MAD, with certain subroutines in FAP, for the IBM 7094, and is designed to operate in a time-sharing environment.


Author[s]: Ward Douglas Maurer

A Theory of Computer Instructions

September 1965



This paper has arisen from an attempt to determine the nature of computer instructions from a viewpoint of general function and set theory. Mathematical machines, however the term is understood, are not adequate models for the computers of today; this is true whether we are talking about Turning machines, sequential machines, push-down automata, generalized sequential machines, or any of the other numerous machine models that have been formulated I the last fifteen years. Most of these models are either not general enough, as the sequential or Turning machines with their single input and output devices; or capable of accurately reproducing only one important programming feature; or in a sense too general (see discussion of sequential machines in Chapter 10 below). On the other hand, modern computers, whether they are binary, decimal, or mixed, whether they have one or two instructions per word, or one instruction covering several words, have several important common features, All of their instructions have input, output, and affected regions (in the sense of Definitions B and K below). The study of the input and output regions and the structure of affected regions of all the instructions on a given computer can provide a key to its logical efficiency.


Author[s]: Peter Samson


October 1968



The MIDAS linking loader is a PDP-6 program to load relocatable-format output from the MIDAS assemblers, with facilities to handle symbolic cross-reference between independently assembled programs. Although it is arranged primarily to load from DECtape, the loader is able also to load paper-tape relocatable programs. To use the loader, load it off the MACDMOP SYSTEM tape as the file STINK (A file STINK NEW may exist, repairing old bugs or introducing new features.) Then the loader expects commands to be typed in on the on-line Teletype; two successive ALT MODE characters terminate the string of commands. The commands in a string are not performed until the string is thus terminated. While a command in a string has not been terminated, RUBOUT will erase the last typed-in character (and type it out again as a reminder). A command string may contain any number of commands, and the effect is the same whether the commands are together in one string or are in successively typed-in strings each delimited by two ALT MODES.


Author[s]: Timothy Hart

A Useful Algebraic Property of Robinson's Unification Algorithm

November 1965



This memo presupposes some acquaintance with "A Machine Oriented Logic Based on the Resolution Principle", J.A. Robinson, JACM Jan65. The reader unfamiliar with this paper should be able to get a general idea of the theorem if he knows that OA is a post operator indicating a minimal set of substitutions (most general substitution) necessary to transform all elements of the set of formulae, A, into the same element (to "unify" A), so that when OA exists AOA is a set with one element (a "unit"). Example: A={f(x),y f(g(u)), f(g(z))} UA= {g(u)/x, f(g(u))/y, u/z} AOA= {f(g(u))} Another most general unifier of A is {g(z)/x, f(g(z))/y, z/u}.


Author[s]: Michael Levin

Topics in Model Theory

January 1966



The concept of free as in "free group" is generalized to any first order theory. An interesting class of homomorphisms between models is discussed. Relations between model theory and abelian categories are discussed speculatively. This paper represents an incomplete study and may contain serious errors. A knowledge of model theory, and of MIT course 18.892 in particular is assumed.


Author[s]: Robert R. Fenichel and Joel Moses

A New Version of CTSS LISP

February 1966



A new version of the CTSS LISP is now available. The new system provides additional data storage and several new functions and constants. The I/O capabilities, EXCISE, the error comments, and several routines have been improved. Musch irrelevant code and many bugs have all been removed. FAP source decks and BOD listings are available. The decks are organized so as to ease the job of assembling private LISP systems in which uneeded features are absent. Without reassembling, the user can create a private LISP system in which the data storage space has been arbitrarily allocated among binary program space, the push-down list, full word space, and free storage.


Author[s]: Arnold Griffith

A New Machine-Learning Technique Applied to the Game of Checkers

March 1966



This paper described a recent refinement of the machine--learning process employed by Samuel (1) in connection with his development of a checker playing program. Samuels checker player operates in much the same way a human player does; by looking ahead, and by making a qualitative judgment of the strength of the board positions it encounters. A machine learning process is applied to the development of an accurate procedure for making this strength evaluation of board positions. Before discussing my modifications to Samuels learning process, I should like to describe briefly Samuel’s strength evaluation procedure, and the associated learning process.


Author[s]: Adolfo Guzman and Harold McIntosh

A Program Feature for CONVERT

April 1966



A program feature has been constructed for CONVERT, closely modeled after the similar facility found in many versions of LISP. Since it is functional or operational in nature, it has been included as a skeleton form, together with a number of related operator skeletons. This Memo describes them, and also the RUL mode, which allows the user to specify arbitrary components of a pattern as the result of a computation performed while the matching process is taking place.


Author[s]: Adolfo Guzman

POLYBRICK: Adventures in the Domain of Parallelepipeds

May 1966



A collection of programs tries to recognize, which one more successfully than its predecessor, 3-dimensional parallelepipeds (solids limited by 6 planes, parallel two-by-two), using as data 2-dimensional idealized projections. Special attention is given to the last of those programs; the method used is discussed in some detail and, in the light of its success and failures, a more general one is proposed.


Author[s]: Joel Moses

Symbolic Integration

June 1966



A program has been written which is capable of integrating all but two of the problems solved by the Siagle's symbollic integration program SAINT. In contrast to SAINT, it is a purely algorithmic program and it has achieved running times two to three orders of magnitude faster than SAINT. This program and some of the basic routines which it uses are described. A heuristic for integration, called the Edge heuristic, is presented. It is claimed that this heuristic with the aid of a few algorithms is capapble of solving all the problems solved by the algorithmic program and many others as well.


Author[s]: Joel Moses

Symbolic Integration II

October 1966



In this memo we describe the current state of the integration program originally described in AI Memo 97 (MAC-M-310). Familiarity with Memo 97 is assumed. Some of the algorithms described in that memo have been extended. Certain new algorithms and a simple integration by parts routine have been added. The current program can integrate all the problems which were solved by SAINT and also the two problems which were solved. Due to the addition of a decision procedure the program is capable of identifying certain integrands (such as e or e/ x) as not integrable in closed form.


Author[s]: Peter Samson


June 1966



This is a mosaic description of PDP-6 LISP, intended for readers familiar with the LISP 1.5 Programmer’s Manual or who have used LISP on some other computer. Some of the newer features (e.g. the display) are experimental and subject to change; in such respects this should not be regarded as a final document. Some Distinctive characteristics: Top-level type in is to EVAL. There is no EVALQUOTE. EQUAL will not correctly compare fixed-point numbers to floating-point. Also (ZEROP 0.0) is NIL. T and NIL evaluate to T and NIL. There are not *T* and F. Interpreted variables, and variable used free in compiled functions, are automatically SPECIAL and may be used without restriction to communicate values. Also any PROG and LAMBDA variables in a compiled function may be declared SPECIAL, and will be bound and restored correctly. COMMON does not exist. Flags are not allowed; elements on a property list of an atom are expected to be paired. MAP, MAPCAR, etc. assume the first argument is the function, and the second is the list. Defining of functions is usually done with DEFPROP.


Author[s]: Adolfo Guzman and Harold McIntosh


June 1966



A programming language is described which is applicable to problems conveniently described by transformation rules. By this we mean that patterns may be prescribed, each being associated with a skeleton, so that a series of such pairs may be searched until a pattern is found which matches an expression to be transformed. The conditions for a match are governed by a code which allows sub-expressions to be identified and eventually substituted into the corresponding skeleton. The primitive patterns and primitive skeletons are described, as well as the principles which allow their elaboration into more complicated patterns and skeletons. The advantages of the language are that it allows one to apply transformation rules to lists and arrays as easily as strings, that both patterns and skeletons may be defined recursively, and that as a consequence programs may be stated quite concisely.

horizontal line

MIT logo Computer Science and Artificial Intelligence Laboratory (CSAIL)
The Stata Center, Building 32 - 32 Vassar Street - Cambridge, MA 02139 - USA
tel:+1-617-253-0073 - publications@csail.mit.edu