Programming languages and software engineering - The Computing Universe: A Journey through a Revolution - page 64

for a program or subroutine to call itself, and dynamic data structures , for which
the memory space required is not set in advance but can change size as the
program runs. The newly developed FORTRAN language did not support either
of these requirements.
When he returned to MIT, McCarthy set about devising a language suitable
for the types of symbolic and AI applications he had in mind. His LISP language
focused on the manipulation of dynamic lists that could grow or shrink as the
program was running. The style of programming was very different from that
of an imperative language like FORTRAN. There were no assignment statements
in LISP and no implicit model of state in the background, tied to the physical
implementation of a “pigeonhole” model of computer memory. Instead, in LISP
everything is a mathematical function. For example, the expression x 2 is a func-
tion : applying this function to the variable x returns the value of x 2 . In LISP, com-
putation is achieved by just applying functions to arguments. This feature makes
it easier to reason mathematically about the behavior and correctness of LISP
programs. It removes the possibility of dangerous “side effects” - situations in an
imperative program where, unsuspected by the programmer, some part of the
program has altered the value of a variable in memory from the value that the
programmer had intended. Memory allocation for McCarthy's dynamic lists was
not performed in advance of running the program. It was therefore necessary
to regularly clean up the memory space by removing from the list of assigned
storage locations any locations that were no longer being used. McCarthy's team
called this process of reclaiming memory space garbage collection . These ideas
have been influential in the implementation of modern languages like Java and
C# (C Sharp).
McCarthy's ideas about recursion and dynamic data structures are not
limited to declarative languages like LISP. They are now essential compo-
nents of almost all imperative languages, such as FORTRAN, BASIC, and C.
We can illustrate the idea of recursion through the problem of calculating
the factorial of the number n - that is, the product of the whole number n
and all the whole numbers below it. The factorial of n is written as n! and is
defined to be the product n × (n - 1) × (n - 2) . . . × 2 × 1. We could calculate
this using a for loop, but we can also perform the calculation using recur-
sion, a process in which the function repeatedly calls itself with smaller and
smaller arguments until it reaches a termination condition , a state in which
it will stop calling itself. The pseudocode for the recursive calculation of
factorial n is:
factorial (n)
if n <= 1:
return 1
else:
return n * factorial (n - 1)
The expression “n <= 1” is an integer check to see if the value of n is less than
(<) or equal (=) to 1. The calculation of the factorial starts with n and multiplies
this by factorial (n - 1). This repetition continues until (n - 1) equals 1.
As an example of dynamic data structures we consider linked lists . In scien-
tific calculations, the size of the array structures that store related groups of