Recursive.pdf

Recursive Functions of Symbolic Expressions

and Their Computation by Machine, Part I

John McCarthy, Massachusetts Institute of Technology, Cambridge, Mass.

April 1960

1 Introduction

A programming system called LISP (for LISt Processor) has been developed

for the IBM 704 computer by the Artiﬁcial Intelligence group at M.I.T. The

system was designed to facilitate experiments with a proposed system called

the Advice Taker, whereby a machine could be instructed to handle declarative

as well as imperative sentences and could exhibit “common sense” in carrying

out its instructions. The original proposal [1] for the Advice Taker was made

in November 1958. The main requirement was a programming system for

manipulating expressions representing formalized declarative and imperative

sentences so that the Advice Taker system could make deductions.

In the course of its development the LISP system went through several

stages of simpliﬁcation and eventually came to be based on a scheme for rep-

resenting the partial recursive functions of a certain class of symbolic expres-

sions. This representation is independent of the IBM 704 computer, or of any

other electronic computer, and it now seems expedient to expound the system

by starting with the class of expressions called S-expressions and the functions

called S-functions.

Putting this paper in L A T E Xpartly supported by ARPA (ONR) grant N00014-94-1-0775

to Stanford University where John McCarthy has been since 1962. Copied with minor nota-

tional changes from CACM , April 1960. If you want the exact typography, look there. Cur-

rent address, John McCarthy, Computer Science Department, Stanford, CA 94305, (email:

jmc@cs.stanford.edu), (URL: http://www-formal.stanford.edu/jmc/ )

In this article, we ﬁrst describe a formalism for deﬁning functions recur-

sively. We believe this formalism has advantages both as a programming

language and as a vehicle for developing a theory of computation. Next, we

describe S-expressions and S-functions, give some examples, and then describe

the universal S-function apply which plays the theoretical role of a universal

Turing machine and the practical role of an interpreter. Then we describe the

representation of S-expressions in the memory of the IBM 704 by list structures

similar to those used by Newell, Shaw and Simon [2], and the representation

of S-functions by program. Then we mention the main features of the LISP

programming system for the IBM 704. Next comes another way of describ-

ing computations with symbolic expressions, and ﬁnally we give a recursive

function interpretation of ﬂow charts.

We hope to describe some of the symbolic computations for which LISP

has been used in another paper, and also to give elsewhere some applications

of our recursive function formalism to mathematical logic and to the problem

of mechanical theorem proving.

2 Functions and Function Deﬁnitions

We shall need a number of mathematical ideas and notations concerning func-

tions in general. Most of the ideas are well known, but the notion of conditional

expression is believed to be new 1 , and the use of conditional expressions per-

mits functions to be deﬁned recursively in a new and convenient way.

a. Partial Functions. A partial function is a function that is deﬁned only

on part of its domain. Partial functions necessarily arise when functions are

deﬁned by computations because for some values of the arguments the com-

putation deﬁning the value of the function may not terminate. However, some

of our elementary functions will be deﬁned as partial functions.

b. Propositional Expressions and Predicates. A propositional expression is

an expression whose possible values are T (for truth) and F (for falsity). We

shall assume that the reader is familiar with the propositional connectives^

(“and”),_(“or”), and¬(“not”). Typical propositional expressions are:

1 reference Kleene

x < y

(x < y)^(b = c)

x is prime

A predicate is a function whose range consists of the truth values T and F.

c. Conditional Expressions. The dependence of truth values on the values

of quantities of other kinds is expressed in mathematics by predicates, and the

dependence of truth values on other truth values by logical connectives. How-

ever, the notations for expressing symbolically the dependence of quantities of

other kinds on truth values is inadequate, so that English words and phrases

are generally used for expressing these dependences in texts that describe other

dependences symbolically. For example, the function|x|is usually deﬁned in

words. Conditional expressions are a device for expressing the dependence of

quantities on propositional quantities. A conditional expression has the form

(p 1 !e 1 ,···,p n !e n )

where the p’s are propositional expressions and the e’s are expressions of any

kind. It may be read, “If p 1

otherwise if p 2

then e 2 ,···, otherwise if

p n then e n ,” or “p 1 yields e 1 ,···,p n yields e n .” 2

We now give the rules for determining whether the value of

(p 1 !e 1 ,···,p n !e n )

is deﬁned, and if so what its value is. Examine the p’s from left to right. If

a p whose value is T is encountered before any p whose value is undeﬁned is

encountered then the value of the conditional expression is the value of the

corresponding e (if this is deﬁned). If any undeﬁned p is encountered before

2 I sent a proposal for conditional expressions to a CACM forum on what should be

included in Algol 60. Because the item was short, the editor demoted it to a letter to the

editor, for which CACM subsequently apologized. The notation given here was rejected for

Algol 60, because it had been decided that no new mathematical notation should be allowed

in Algol 60, and everything new had to be English. The if . . . then . . . else that Algol 60

adopted was suggested by John Backus.

then e 1

a true p, or if all p’s are false, or if the e corresponding to the ﬁrst true p is

undeﬁned, then the value of the conditional expression is undeﬁned. We now

give examples.

(1 < 2!4, 1 > 2!3) = 4

(2 < 1!4, 2 > 1!3, 2 > 1!2) = 3

(2 < 1!4,T!3) = 3

0 ,T!3) = 3

(2 < 1!3,T! 0

0 ) is undeﬁned

(2 < 1!3, 4 < 1!4) is undeﬁned

Some of the simplest applications of conditional expressions are in giving

such deﬁnitions as

|x|= (x < 0!−x,T!x)

ij = (i = j!1,T!0)

sgn(x) = (x < 0!−1,x = 0!0,T!1)

d. Recursive Function Deﬁnitions. By using conditional expressions we

can, without circularity, deﬁne functions by formulas in which the deﬁned

function occurs. For example, we write

n! = (n = 0!1,T!n·(n−1)!)

When we use this formula to evaluate 0! we get the answer 1; because of the

way in which the value of a conditional expression was deﬁned, the meaningless

(2 < 1! 0

expression 0·(0 - 1)! does not arise. The evaluation of 2! according to this

deﬁnition proceeds as follows:

2! = (2 = 0!1,T!2·(2−1)!)

= 2·1!

= 2·(1 = 0!1T!·(1−1)!)

= 2·1·0!

= 2·1·(0 = 0!1,T!0·(0−1)!)

= 2·1·1

= 2

We now give two other applications of recursive function deﬁnitions. The

greatest common divisor, gcd(m,n), of two positive integers m and n is com-

puted by means of the Euclidean algorithm. This algorithm is expressed by

the recursive function deﬁnition:

gcd(m,n) = (m > n!gcd(n,m),rem(n,m) = 0!m,T!gcd(rem(n,m),m))

where rem(n,m) denotes the remainder left when n is divided by m.

The Newtonian algorithm for obtaining an approximate square root of a

number a, starting with an initial approximation x and requiring that an

acceptable approximation y satisfy|y 2 −a|< , may be written as

sqrt(a, x, )

= (|x 2 −a|< !x,T!sqrt (a,

2 (x +

x ), ))

The simultaneous recursive deﬁnition of several functions is also possible,

and we shall use such deﬁnitions if they are required.

There is no guarantee that the computation determined by a recursive

deﬁnition will ever terminate and, for example, an attempt to compute n!

from our deﬁnition will only succeed if n is a non-negative integer. If the

computation does not terminate, the function must be regarded as undeﬁned

for the given arguments.

The propositional connectives themselves can be deﬁned by conditional

expressions. We write

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: