TEXC.DOC[206,LMM] - www.SailDart.org

perm filename TEXC.DOC[206,LMM] blob sn#096402 filedate 1974-04-05 generic text, type T, neo UTF8
␈↓␈↓ εP␈↓ Oi


␈↓␈↓ ∧Q␈↓&T A B L E   O F   C O N T E N T S␈↓'β




␈↓SECTION␈↓ αPAGE




␈↓I␈↓ α8INTRODUCTION TO LISP

␈↓␈↓ βλ1␈↓ ∧(Lists.␈↓ ¬_∀∀∀∀∀∀∀∀∀∀∀∀␈↓ α
␈↓ ? 1

␈↓␈↓ βλ2␈↓ ∧(Atoms.␈↓ ¬_∀∀∀∀∀∀∀∀∀∀∀∀␈↓ α
␈↓ ? 3

␈↓␈↓ βλ3␈↓ ∧(List structures.␈↓ ¬x∀∀∀∀∀∀∀∀∀∀␈↓ α
␈↓ ? 3

␈↓␈↓ βλ4␈↓ ∧(S-expressions.␈↓ ¬x∀∀∀∀∀∀∀∀∀∀␈↓ α
␈↓ ? 4

␈↓␈↓ βλ5␈↓ ∧(The basic functions and predicates of LISP.␈↓ λx∀∀␈↓ α
␈↓ ? 6

␈↓␈↓ βλ6␈↓ ∧(Conditional expressions.␈↓ εX∀∀∀∀∀∀∀∀␈↓ α
␈↓ ? 8

␈↓␈↓ βλ7␈↓ ∧(Boolean expressions.␈↓ ε(∀∀∀∀∀∀∀∀∀␈↓ α
␈↓ ? 9

␈↓␈↓ βλ8␈↓ ∧(Recursive function definitions.␈↓ π8∀∀∀∀∀∀␈↓ α
␈↓ 0 10

␈↓␈↓ βλ9␈↓ ∧(Lambda expressions and functions with functions as
␈↓␈↓ ¬(arguments.␈↓ ε(∀∀∀∀∀∀∀∀∀␈↓ α
␈↓ 0 15

␈↓␈↓ βλ10␈↓ ∧(Label.␈↓ ¬_∀∀∀∀∀∀∀∀∀∀∀∀␈↓ α
␈↓ 0 17


␈↓II␈↓ α8HOW TO WRITE RECURSIVE FUNCTION DEFINITIONS

␈↓␈↓ βλ1␈↓ ∧(Static and dynamic ways of programming.␈↓ λH∀∀∀␈↓ α
␈↓ 0 18

␈↓␈↓ βλ2␈↓ ∧(Simple list recursion.␈↓ ε(∀∀∀∀∀∀∀∀∀␈↓ α
␈↓ 0 19

␈↓␈↓ βλ3␈↓ ∧(Simple S-expression recursion.␈↓ π8∀∀∀∀∀∀␈↓ α
␈↓ 0 21

␈↓␈↓ βλ4␈↓ ∧(Other structural recursions.␈↓ πλ∀∀∀∀∀∀∀␈↓ α
␈↓ 0 22

␈↓␈↓ βλ5␈↓ ∧(Tree search.␈↓ ¬H∀∀∀∀∀∀∀∀∀∀∀␈↓ α
␈↓ 0 23

␈↓␈↓ βλ6␈↓ ∧(Game trees.␈↓ ¬H∀∀∀∀∀∀∀∀∀∀∀␈↓ α
␈↓ 0 27
␈↓␈↓ εP␈↓ I1


␈↓β␈↓ ¬yCHAPTER I

␈↓β␈↓ ¬∞INTRODUCTION TO LISP






␈↓1.  ␈↓βLists.␈↓


␈↓        Symbolic␈α
information␈α
in␈α∞LISP␈α
is␈α
 expressed␈α
 by␈α∞ S-expressions␈α
and␈α
 these␈α∞ are␈α
 represented
␈↓in␈α∂ the␈α∂ memory␈α∞of␈α∂the␈α∂computer␈α∂by␈α∞list␈α∂structures.␈α∂Before␈α∞giving␈α∂formal␈α∂ definitions,␈α∂ we␈α∞ shall
␈↓give␈α
 some␈α
examples.

␈↓        The␈α
most␈α
common␈α
form␈α
of␈α
S-expression␈α
is␈α
the␈α
 list,␈α
 and␈α
 here␈α
are␈α
some␈α
lists:

␈↓The list
␈↓        ␈↓∧(A B C E)
␈↓∧␈↓has four elements.

␈↓The list
␈↓        ␈↓∧(A B (C D) E)
␈↓∧␈↓has four elements one of which is itself a list.

␈↓The list
␈↓        ␈↓∧(A)
␈↓∧␈↓has one element.

␈↓The list
␈↓        ␈↓∧((A B C D))
␈↓∧␈↓also has one element which itself is a list.

␈↓The list
␈↓        ␈↓∧()
␈↓∧␈↓has no elements; it is also written
␈↓        ␈↓∧NIL.
␈↓∧␈↓The list
␈↓        ␈↓∧(PLUS X Y)
␈↓∧␈↓has three elements and may be used to represent the expression
␈↓        ␈↓αx␈↓↓ + ␈↓αy.

␈↓α␈↓The list
␈↓        ␈↓∧(PLUS (TIMES X Y) X 3)
␈↓∧␈↓has four elements and may be used to represent the expression
␈↓        ␈↓αxy␈↓↓ + ␈↓αx␈↓↓ + ␈↓∧3.
␈↓␈↓ ¬xCHAPTER I␈↓ I2


␈↓∧␈↓The list
␈↓        ␈↓∧(EXIST X (ALL Y (IMPLIES (P X) (P Y))))
␈↓∧␈↓may be used to represent the logical expression
␈↓        ␈↓↓(∃␈↓αx␈↓↓)(∀␈↓αy␈↓↓).␈↓αP␈↓↓(␈↓αx␈↓↓)⊃␈↓αP␈↓↓(␈↓αy␈↓↓).

␈↓↓␈↓The list
␈↓        ␈↓∧(INTEGRAL 0 ∞ (TIMES (EXP (TIMES I X Y)) (F X)) X)
␈↓∧␈↓may be used to represent the expression

␈↓        ␈↓	␈␈↓αe␈↓εixy␈↓αf␈↓↓(␈↓αx␈↓↓)␈↓αdx.

␈↓α␈↓The list
␈↓        ␈↓∧((A B) (B A C D) (C B D E) (D B C E) (E C D F) (F E))

␈↓is␈α
used␈αto␈α
represent␈α
the␈αnetwork␈α
of␈α
Figure␈α1␈α
according␈α
 to␈α a␈α
 scheme␈α
whereby␈α there␈α
 is␈α
a␈αsublist
␈↓for␈α
each␈α
vertex␈α
consisting␈α
of␈α
the␈α
vertex␈α
itself␈α
followed␈α
by␈α
the␈α
vertices␈α
to␈α
which␈α
it␈α
is␈α
connected.











␈↓                              Figure␈α
1

␈↓        The␈α∞ elements␈α∂ of␈α∞ a␈α∂ list␈α∞ are␈α∂surrounded␈α∞by␈α∞parentheses␈α∂and␈α∞separated␈α∂by␈α∞spaces.␈α∂ A␈α∞list
␈↓may␈αhave␈αany␈αnumber␈αof␈αterms␈αand␈αany␈α of␈αthese␈α terms␈α may␈α themselves␈α be␈α lists.␈α  In␈α this␈αcase,
␈↓the␈αspaces␈αsurrounding␈αa␈α
sublist␈α may␈α be␈α omitted,␈α and␈α
 extra␈α spaces␈α between␈αelements␈αof␈α
a␈αlist
␈↓are␈α
allowed.␈α
 Thus␈α
the␈α
lists

␈↓        ␈↓∧(A␈αB(C␈α D)␈α   E)

␈↓∧␈↓and

␈↓        ␈↓∧(A␈αB␈α(C␈αD)␈αE)

␈↓∧␈↓are␈α
regarded␈α
as␈α
the␈α
same.
␈↓␈↓ ¬xCHAPTER I␈↓ I3


␈↓2.  ␈↓βAtoms.␈↓


␈↓        The␈αexpressions␈α␈↓∧A,␈αB,␈αX,␈αY,␈α3,␈αPLUS,␈α␈↓and␈α␈↓∧ALL␈↓␈αoccurring␈αin␈αthe␈αabove␈α lists␈αare␈αcalled␈αatoms.
␈↓In␈α
general,␈α∞an␈α
atom␈α
is␈α∞expressed␈α
by␈α
a␈α∞sequence␈α
of␈α
capital␈α∞letters,␈α
 digits,␈α
 and␈α∞ special␈α
 characters
␈↓with␈α∩certain␈α∪ exclusions.␈α∩  The␈α∪exclusions␈α∩are␈α∩<space>,␈α∪<carriage␈α∩return>,␈α∪and␈α∩the␈α∪other␈α∩non-
␈↓printing␈α
 characters,␈α
 and␈α
 also␈α
 the␈α
 parentheses,␈α
brackets,␈α
 semi-colon,␈α
 and␈α
 comma.␈α
  Numbers␈α
are
␈↓expressed␈α∃as␈α∃signed␈α∃decimal␈α∀or␈α∃octal␈α∃numbers,␈α∃ the␈α∀ exact␈α∃ convention␈α∃ depending␈α∃ on␈α∀ the
␈↓implementation.␈α~ Floating␈α~ point␈α~ numbers␈α~ are␈α~ written␈α~ with␈α~decimal␈α~points␈α~and,␈α~when
␈↓appropriate,␈α∪an␈α∪exponent␈α∪notation␈α∪depending␈α∪ on␈α∪ the␈α∪implementation.␈α∪  The␈α∪ reader␈α∩ should
␈↓consult␈α
the␈α
programmer's␈α
manual␈α
for␈α
the␈α
LISP␈α
implementation␈α
he␈α
intends␈α
to␈α
use.

␈↓        Some␈α
examples␈α
of␈α
atoms␈α
are

␈↓        ␈↓∧THE-LAST-TRUMP
␈↓∧␈↓        ␈↓∧A307B
␈↓∧␈↓        ␈↓∧345
␈↓∧␈↓        ␈↓∧3.14159,

␈↓∧␈↓and␈α
from␈α
these␈α
we␈α
can␈α
form␈α
lists␈α
like

␈↓        ((345␈α
3.14159␈α
-47)␈α
A307B␈α
THE-LAST-TRUMP␈α
-45.21).␈α
 



␈↓3.  ␈↓βList␈α
structures.␈↓


␈↓        Lists␈α
 are␈α
 represented␈α
in␈α
the␈αmemory␈α
of␈α
the␈α
computer␈α
by␈αlist␈α
structures.␈α
   A␈α
list␈α
structure␈αis␈α
a
␈↓collection␈αof␈αmemory␈αwords␈α each␈αof␈α which␈α is␈α divided␈α into␈α two␈α parts,␈αand␈αeach␈αpart␈αis␈αcapable
␈↓of␈αcontaining␈αan␈αaddress␈αin␈αmemory.␈αThe␈αtwo␈αparts␈αare␈αcalled␈αare␈α called␈αthe␈α a-part␈α and␈α the␈α d-
␈↓part.␈α⊂ There␈α⊃ is␈α⊂ one␈α⊃computer␈α⊂word␈α⊃for␈α⊂each␈α⊃element␈α⊂of␈α⊃the␈α⊂list,␈α⊃and␈α⊂the␈α⊃a-part␈α⊂of␈α⊃the␈α⊂word
␈↓contains␈α⊂the␈α⊂ address␈α⊂of␈α⊂the␈α⊂list␈α⊂or␈α∂atom␈α⊂representing␈α⊂the␈α⊂element,␈α⊂and␈α⊂the␈α⊂d-part␈α⊂contains␈α∂the
␈↓address␈α
of␈α
the␈α
word␈α
representing␈α
the␈α
next␈α
element␈α
 of␈α
 the␈α
 list.␈α
 If␈α
the␈α
list␈α
element␈α
is␈α
itself␈α
a␈α
list,
␈↓then,␈α
of␈α
course,␈α
the␈α
address␈α
of␈αthe␈α
first␈α
word␈α
of␈α
its␈α
list␈α
structure␈αis␈α
given␈α
in␈α
the␈α
 a-part␈α
 of␈α the␈α
word
␈↓representing␈α
 that␈α element.␈α
 A␈α
diagram␈αshows␈α
this␈α
more␈αclearly␈α
than␈α
words,␈αand␈α
the␈α
list␈αstructure
␈↓corresponding␈αto␈αthe␈α list␈α  ␈↓∧(PLUS␈α(TIMES␈α X␈α Y)␈α X␈α 3)␈↓␈α  which␈αmay␈αrepresent␈αthe␈αexpression␈α ␈↓αxy␈↓↓␈α
+
␈↓↓␈↓αx␈↓↓␈α+␈α␈↓∧3␈α is␈αshown␈αin␈αfigure␈α2.
␈↓␈↓ ¬xCHAPTER I␈↓ I4














␈↓∧                              Figure␈α2.

␈↓∧␈↓        ␈↓∧Atoms␈α⊗ are␈α↔ represented␈α⊗ by␈α↔ the␈α⊗ addresses␈α⊗of␈α↔their␈α⊗property␈α↔lists␈α⊗which␈α↔are␈α⊗list
␈↓∧structures␈αof␈αa␈αspecial␈αkind␈α depending␈α on␈α the␈αimplementation.␈α  (In␈α some␈α implementations,␈α the
␈↓∧first␈α∪ word␈α∪ of␈α∪a␈α∪property␈α∪list␈α∪is␈α∪in␈α∪a␈α∪special␈α∪are␈α∪of␈α∪memory,␈α∪in␈α∪others␈α∪the␈α∪first␈α∀word␈α∪is
␈↓∧distinguished␈α∂ by␈α∞ sign,␈α∂in␈α∞still␈α∂others␈α∞it␈α∂has␈α∂a␈α∞special␈α∂a-part.␈α∞ For␈α∂basic␈α∞LISP␈α∂programming,␈α∂it␈α∞is
␈↓∧enough␈α
 to␈α
 know␈α
 that␈α∞ atoms␈α
 are␈α
distinguishable␈α
 from␈α∞ other␈α
 list␈α
 structures␈α
 by␈α∞a␈α
predicate
␈↓∧called␈α␈↓βat␈↓.)

␈↓        The␈α
 last␈α
 word␈α of␈α
 a␈α
list␈α
cannot␈αhave␈α
the␈α
address␈αof␈α
a␈α
next␈α
word␈αin␈α
its␈α
d-part␈α
since␈αthere
␈↓isn't␈α
any␈α
next␈α
word,␈α
 so␈α
 it␈α
 has␈α
 the␈α
address␈α
of␈α
a␈α
special␈α
atom␈α
called␈α
 ␈↓∧NIL␈↓.

␈↓        A␈α∪ list␈α∪ is␈α∀ referred␈α∪ to␈α∪ by␈α∪giving␈α∀the␈α∪address␈α∪of␈α∪its␈α∀first␈α∪element.␈α∪ According␈α∀to␈α∪this
␈↓convention,␈α⊂we␈α∂see␈α⊂that␈α∂the␈α⊂a-part␈α∂ of␈α⊂ a␈α⊂list␈α∂ word␈α⊂ is␈α∂ the␈α⊂ list␈α∂ element␈α⊂ and␈α∂ the␈α⊂d-part␈α⊂is␈α∂a
␈↓pointer␈αto␈αa␈αsublist␈αformed␈αby␈αdeleting␈αthe␈αfirst␈αelement.␈α Thus␈αthe␈αfirst␈αword␈αof␈αthe␈α list␈α structure
␈↓of␈α figure␈α 2␈α contains␈α a␈α pointer␈αto␈αthe␈αlist␈αstructure␈αrepresenting␈αthe␈αatom␈α ␈↓∧PLUS␈↓,␈αwhile␈αits␈αd-part
␈↓points␈α∂to␈α∂the␈α∞list␈α∂ ␈↓∧((TIMES␈α∂X␈α∞Y)␈α∂X␈α∂3)␈↓.␈α∞ The␈α∂second␈α∂word␈α∞contains␈α∂the␈α∂list␈α∂structure␈α∞representing
␈↓␈↓∧(TIMES␈α∞X␈α
Y)␈↓␈α∞ in␈α∞ its␈α
 a-part␈α∞ and␈α∞ the␈α
 list␈α∞ structure␈α∞representing␈α
 ␈↓∧(X␈α∞3)␈↓␈α∞ in␈α
its␈α∞d-part.␈α∞ The␈α
last
␈↓word␈αpoints␈αto␈αthe␈αatom␈α␈↓∧3␈↓␈α in␈αits␈αa-part␈αand␈αhas␈αa␈αpointer␈αto␈αthe␈αatom␈α ␈↓∧NIL␈↓␈α in␈αits␈α d-part.␈α This␈αis
␈↓consistent␈α
with␈α
the␈α
convention␈α
that␈α
 ␈↓∧NIL␈↓␈α
 represents␈α
the␈α
null␈α
list.



␈↓4.  ␈↓βS-expressions.␈↓


␈↓        When␈α∂we␈α∂examine␈α⊂the␈α∂way␈α∂list␈α⊂structures␈α∂ represent␈α∂ lists␈α⊂ we␈α∂see␈α∂ a␈α⊂ curious␈α∂ asymmetry.
␈↓Namely,␈α the␈α a-part␈αof␈αa␈αlist␈αword␈αcan␈αcontain␈αan␈αatom␈αor␈αa␈αlist,␈αbut␈αthe␈αd-part␈αcan␈αcontain␈αonly␈αa
␈↓list␈α∂ or␈α∂the␈α∞special␈α∂atom␈α∂ ␈↓∧NIL␈↓.␈α∂  This␈α∞restriction␈α∂is␈α∂quite␈α∂unnatural␈α∞from␈α∂the␈α∂computing␈α∂point␈α∞of
␈↓view,␈α and␈α
 we␈α shall␈α allow␈α
 arbitrary␈α atoms␈α to␈α
inhabit␈α the␈α
 d-parts␈α of␈α words,␈α
but␈αthen␈αwe␈α
must
␈↓generalize␈αthe␈αway␈αlist␈αstructures␈αare␈αexpressed␈αas␈αcharacter␈αstrings.␈αTo␈α do␈α this,␈α we␈αintroduce␈αthe
␈↓notion␈α
of␈α
S-expression.

␈↓        An␈α∀ S-expression␈α∪is␈α∀either␈α∪an␈α∀atom␈α∀or␈α∪a␈α∀pair␈α∪of␈α∀S-expressions␈α∪separated␈α∀by␈α∀" . "␈α∪and
␈↓surrounded␈α
by␈α
parentheses.␈α
  In␈α
 BNF,␈α
 we␈α
 can␈α
write
␈↓␈↓ ¬xCHAPTER I␈↓ I5


␈↓<S-expression>␈α
::=␈α
<atom>␈α
|␈α
(<S-expression>␈α
.␈α
<S-expression>).

␈↓Examples␈α
of␈α
S-expressions␈α
are

␈↓        ␈↓∧A
␈↓∧␈↓        ␈↓∧(A . B)
␈↓∧␈↓        ␈↓∧(A . (B . A))
␈↓∧␈↓        ␈↓∧(PLUS (X . (Y . NIL)))
␈↓∧␈↓        ␈↓∧(3 . 3.4)

␈↓∧␈↓        ␈↓∧In␈α
the␈α
memory␈αof␈α
a␈α
computer,␈αan␈α
S-expression␈α
 is␈α represented␈α
by␈α
 the␈α address␈α
of␈α
a␈αword
␈↓∧whose␈αa-part␈αcontains␈αthe␈αfirst␈αelement␈αof␈αthe␈αpair␈αand␈αwhose␈αd-part␈αcontains␈αthe␈αsecond␈αelement
␈↓∧of␈α the␈α pair.␈α
 Thus,␈α the␈αS-expressions␈α (A.B),␈α
 (A.(B.A))␈↓,␈αand␈α ␈↓∧(PLUS.(X.(Y.NIL)))␈α␈↓␈α
are␈αrepresented
␈↓by␈α
the␈α
list␈α
structures␈α
of␈α
figure␈α
3.
















␈↓                              Figure␈α
3.

␈↓        Note␈αthat␈αthe␈αlist␈α␈↓∧(PLUS␈αX␈αY)␈↓␈αand␈αthe␈αS-expression␈α␈↓∧␈α(PLUS␈α.␈α(X␈α.␈α(Y␈α.␈αNIL)))␈↓␈α are␈αrepresented
␈↓in␈α memory␈α by␈α the␈α same␈α list␈αstructure.␈α The␈αsimplest␈αway␈αto␈αtreat␈αthis␈αis␈αto␈αregard␈αS-expressions
␈↓as␈α
primary␈α
and␈α
lists␈α∞ as␈α
 abbreviations␈α
 for␈α
 certain␈α∞ S-expressions,␈α
namely␈α
those␈α
that␈α∞never␈α
have
␈↓any␈αatom␈αbut␈α NIL␈α
 as␈αthe␈αsecond␈αpart␈αof␈α
a␈αpair.␈αIn␈αgiving␈α input␈α
 to␈α LISP,␈α either␈α the␈α list␈α
 form
␈↓or␈α
 the␈αS-expression␈α
 form␈α
may␈αbe␈α
used␈αfor␈α
lists.␈α
 On␈αoutput,␈α
LISP␈αwill␈α
print␈α
a␈αlist␈α
structure␈α
as␈αa
␈↓list␈α as␈α far␈α as␈α it␈α can,␈α otherwise␈α as␈α an␈αS-expression.␈α Thus,␈α some␈αlist␈αstructures␈αwill␈αbe␈αprinted
␈↓in␈αa␈α
mixed␈αnotation,␈α
e.g.␈α␈↓∧((A␈α
.␈αB)␈α
(C␈α.␈αD)␈α
(3))␈↓.

␈↓        In␈αgeneral,␈αthe␈α
list␈α␈↓↓(␈↓αa␈αb␈α
.␈α.␈α.␈α
 z␈↓↓)␈↓␈αmay␈αbe␈α
regarded␈αas␈αan␈α
abbreviation␈αof␈αthe␈α
S-expression␈α␈↓↓(␈↓αa␈↓↓␈α.␈α
(␈↓αb␈↓↓
␈↓↓.␈α(␈↓αc␈↓↓␈α.␈α
(...␈α(␈↓αz␈α.␈α␈↓∧NIL␈↓↓)␈α
...)))␈↓.



␈↓                                      Exercises
␈↓␈↓ ¬xCHAPTER I␈↓ I6


␈↓        1.␈α
If␈αwe␈α
represent␈α
sums␈αand␈α
products␈α
as␈αindicated␈α
 above␈α
 and␈αuse␈α
 ␈↓∧(MINUS␈αX),␈α
 (QUOTIENT
␈↓∧X␈α
Y)␈↓,␈α
and␈α
 ␈↓∧(POWER␈αX␈α
Y)␈↓␈α
 as␈α
representations␈α
of␈α ␈↓↓-␈↓αx␈↓,␈α
 ␈↓αx␈↓↓/␈↓αy␈↓,␈α
and␈α
 ␈↓αx␈↓↓↑␈↓αy␈↓␈α respectively,␈α
then

␈↓        a.␈α
What␈α
do␈α
the␈α
lists

␈↓        ␈↓∧(QUOTIENT␈α2␈α(POWER␈α(PLUS␈αX␈α(MINUS␈αY))␈α3))

␈↓∧␈↓and

␈↓        ␈↓∧(PLUS␈α-2␈α(MINUS␈α2)␈α(TIMES␈αX␈α(POWER␈αY␈α3.3)))

␈↓∧␈↓represent?

␈↓        b.␈α≥   How␈α≤   are␈α≥   the␈α≤  expressions␈α≥  ␈↓αxyz␈↓↓+␈↓∧3␈↓↓(␈↓αu␈↓↓+␈↓αv␈↓↓)↑(-␈↓∧3␈↓↓)␈↓␈α≤  and␈α≥␈↓↓(␈↓αxy␈↓↓-␈↓αyx␈↓↓)/(␈↓αxy␈↓↓+␈↓αyx␈↓↓)␈↓␈α≥to␈α≤be
␈↓represented?

␈↓        2.␈α
In␈α
the␈α
above␈α
 mentioned␈α
 graph␈α
 notation,␈α
 what␈α
 graph␈α
 is␈α
represented␈α
by␈α
the␈α
list

␈↓        ␈↓∧((A␈αD␈αE␈αF)(B␈αD␈αE␈αF)(C␈αD␈αE␈αF)(D␈αA␈αB␈αC)(E␈αA␈αB␈αC)(F␈αA␈αB␈αC))?

␈↓∧␈↓        ␈↓∧␈↓3.␈αWrite␈αthe␈αlist␈α␈↓∧((PLUS␈α(TIMES␈αX␈αY)␈αX␈α3)␈↓␈αas␈αan␈αS-expression.␈α This␈αis␈αsometimes␈αreferred␈αto
␈↓as␈α
"dot-notation".

␈↓        4.␈α
 Write␈α
 the␈α
 following␈α
 S-expressions␈α
 in␈α
list␈α
notation␈α
to␈α
whatever␈α
extent␈α
is␈α
possible:
␈↓        a. (A . NIL)
␈↓        b. (A . B)
␈↓        c. ((A . NIL) . B)
␈↓        d. ((A . B) . ((C . D) . NIL).



␈↓5.  ␈↓βThe␈α
basic␈α
functions␈α
and␈α
predicates␈α
of␈α
LISP.␈↓


␈↓        Just␈α∂as␈α∂numerical␈α∂computer␈α∂programs␈α⊂are␈α∂ based␈α∂ on␈α∂ the␈α∂ four␈α∂arithmetic␈α⊂ operations␈α∂ of
␈↓addition␈α⊂subtraction,␈α⊃multiplication,␈α⊂and␈α⊃division,␈α⊂and␈α⊃the␈α⊂arthmetic␈α⊃predicates␈α⊂of␈α⊃equality␈α⊂and
␈↓comparison,␈α⊂so␈α⊂symbolic␈α⊂ computation␈α⊂ has␈α⊂ its␈α⊂basic␈α⊂predicates␈α⊂and␈α⊂functions.␈α⊂ LISP␈α⊃has␈α⊂three
␈↓basic␈α
functions␈α
and␈α
two␈α
predicates.

␈↓        First,␈α we␈αhave␈αtwo␈αfunctions␈α␈↓βa␈↓␈αand␈α␈↓βd␈↓.␈α ␈↓βa␈α␈↓αx␈↓␈αis␈αthe␈αa-part␈αof␈αthe␈αS-expression␈α␈↓∧x␈↓.␈α Thus,␈α ␈↓βa␈↓∧(A␈α.
␈↓∧B)␈α␈↓↓=␈α␈↓∧A␈↓,␈αand␈α␈↓βa␈↓∧((A␈α.␈αB)␈α.␈αA)␈α␈↓↓=␈α␈↓∧(A␈α.␈αB)␈↓.␈α␈↓βd␈α␈↓αx␈↓␈αis␈αthe␈αd-part␈αof␈αthe␈αS-expression␈α␈↓αx␈↓.␈αThus␈α␈↓βd␈↓∧(A␈α.␈αB)␈α␈↓↓=␈α␈↓∧B␈↓,␈αand
␈↓␈↓βd␈↓∧((A␈α
.␈α
B)␈α.␈α
A)␈α
␈↓↓=␈α␈↓∧A␈↓.␈α
 ␈↓βa␈α
␈↓αx␈↓␈αand␈α
␈↓βd␈α
␈↓αx␈↓␈αare␈α
undefined␈α
in␈αbasic␈α
LISP␈α
when␈α␈↓αx␈↓␈α
is␈α
an␈αatom,␈α
but␈α
they␈αmay␈α
have
␈↓a␈α
meaning␈α
in␈α
some␈α
implementations.

␈↓        Since␈α
 lists␈α
 are␈α a␈α
 particular␈α
 kind␈α
 of␈α S-expression,␈α
the␈α
meanings␈α
of␈α ␈↓βa␈↓␈α
 and␈α
 ␈↓βd␈↓␈α
 for␈αlists␈α
are
␈↓also␈α
determined␈α
 by␈α
 the␈α
 above␈α
definitions.␈α
 Thus,␈α
we␈α
have

␈↓        ␈↓βa␈↓∧(A␈αB␈αC␈αD)␈α␈↓↓=␈↓β␈α
A
␈↓␈↓ ¬xCHAPTER I␈↓ I7


␈↓β␈↓and

␈↓        ␈↓βd␈↓∧(A␈αB␈αC␈αD)␈α␈↓↓=␈α␈↓∧(B␈αC␈αD),

␈↓∧␈↓and␈αwe␈αsee␈αthat,␈αin␈αgeneral,␈α ␈↓βa␈α␈↓αx␈↓␈α is␈αthe␈αfirst␈αelement␈αof␈α the␈α list␈α ␈↓αx␈↓,␈αand␈α ␈↓βd␈α␈↓αx␈↓␈α is␈αthe␈αrest␈αof␈αthe␈αlist,
␈↓deleting␈α
that␈α
first␈α
element.

␈↓        Notice␈α
 that␈α∞ for␈α
S-expressions,␈α
the␈α∞definitions␈α
of␈α
 ␈↓βa␈α∞␈↓αx␈↓␈α
 and␈α
␈↓βd␈α∞␈↓αx␈↓␈α
 are␈α
symmetrical,␈α∞while␈α
for
␈↓lists␈α∞the␈α∞symmetry␈α∞is␈α∞lost.␈α
 This␈α∞is␈α∞because␈α∞ of␈α∞ the␈α
 unsymmetrical␈α∞nature␈α∞of␈α∞the␈α∞convention␈α
that
␈↓defines␈α
lists␈α
in␈α
terms␈α
of␈α
S-expressions.

␈↓        Notice,␈α
further,␈α
 our␈α
 convention␈α
 of␈α∞ writing␈α
  ␈↓βa␈↓␈α
  and␈α
  ␈↓βd␈↓  ␈α
without␈α∞ brackets␈α
 surrounding
␈↓the␈α
argument.␈α Also,␈α
we␈αuse␈α
lower␈αcase␈α
letters␈αfor␈α
our␈αfunction␈α
names␈αand␈α
for␈α
variables,␈αreserving
␈↓the␈α
upper␈α
case␈α
letters␈α
for␈α
the␈α
S-expressions␈α
themselves.

␈↓        The␈α third␈α function␈α ␈↓αcons␈↓↓[␈↓αx␈↓↓,␈α␈↓αy␈↓↓]␈↓␈α forms␈αthe␈αS-expression␈αwhose␈αa-part␈αand␈αd-part␈αare␈α ␈↓αx␈↓␈α and
␈↓␈↓αy␈↓␈α
 respectively.␈α
 Thus

␈↓        ␈↓αcons␈↓↓[␈↓∧(A.B),␈αA␈↓↓]␈α=␈α␈↓∧((A.B).A).

␈↓∧␈↓        ␈↓∧␈↓We␈α⊂ see␈α⊂ that␈α⊂ for␈α⊂ lists,␈α⊂  ␈↓αcons␈↓␈α⊂  is␈α⊂a␈α⊂prefixing␈α⊂operation.␈α⊂ Namely,␈α⊂ ␈↓αcons␈↓↓[␈↓αx␈↓↓,␈α⊂␈↓αy␈↓↓]␈↓␈α⊂ is␈α⊃the␈α⊂list
␈↓obtained␈α
by␈α
putting␈α
the␈α
 element␈α
  ␈↓αx␈↓  ␈α
onto␈α
the␈α
front␈α
of␈α
the␈α
list␈α
 ␈↓αy␈↓.␈α
 Thus

␈↓        ␈↓αcons␈↓↓[␈↓∧A,␈α(B␈αC␈αD␈αE)␈↓↓]␈α=␈α␈↓∧(A␈αB␈αC␈αD␈αE).

␈↓∧␈↓If␈αwe␈αwant␈α ␈↓αcons␈↓↓[␈↓αx␈↓↓,␈α␈↓αy␈↓↓]␈↓␈α to␈α be␈α a␈α list,␈α then␈α  ␈↓αy␈↓␈α  must␈α be␈α a␈α list␈α(possibly␈αthe␈αnull␈αlist␈α ␈↓∧NIL␈↓),␈αand␈α ␈↓αx␈↓
␈↓must␈α
be␈α
a␈α
list␈α
or␈α
an␈α
atom.␈α
 In␈α
the␈α
case␈α
of␈α
S-expressions␈α
in␈α
general,␈α
there␈α
is␈α
no␈α
restriction␈α
on␈α the
␈↓arguments␈α
 of␈α
  ␈↓αcons␈↓.␈α
  Usually,␈α
 we␈α
 shall␈α
 write␈α
  ␈↓αx␈α
.␈α
y␈↓␈α
  instead␈α
of␈α
␈↓αcons␈↓↓[␈↓αx␈↓↓,␈α
␈↓αy␈↓↓]␈↓␈α
 since␈α
this␈αis␈α
briefer.

␈↓        The␈α
 first␈α
 predicate␈α
 is␈α  ␈↓βat␈α
␈↓αx␈↓.␈α
  ␈↓βat␈α
␈↓αx␈↓␈α  is␈α
 true␈α
 if␈α
  the␈αS-expression␈α
 ␈↓αx␈↓␈α
 is␈α
atomic␈α
and␈αfalse
␈↓otherwise.

␈↓        The␈α∀ second␈α∀ predicate␈α∀ is␈α∃equality␈α∀of␈α∀atomic␈α∀symbols␈α∀written␈α∃␈↓αx␈α∀␈↓βeq␈α∀␈↓αy␈↓.␈α∀Equality␈α∃of␈α∀S-
␈↓expressions␈α∂is␈α∞tested␈α∂by␈α∂a␈α∞ program␈α∂ based␈α∂ on␈α∞␈↓βeq␈↓.␈α∂  Actually␈α∞  ␈↓βeq␈↓␈α∂ does␈α∂a␈α∞bit␈α∂more␈α∂than␈α∞testing
␈↓equality␈αof␈α
atoms.␈α Namely,␈α ␈↓αx␈α
␈↓βeq␈α␈↓αy␈↓␈α
 is␈αtrue␈αif␈α
and␈αonly␈α
if␈αthe␈αaddresses␈α
 of␈α the␈α
 first␈αwords␈α of␈α
 the
␈↓S-expressions␈α  ␈↓αx␈↓␈α  and␈α ␈↓αy␈↓␈α are␈αequal.␈α Therefore,␈αif␈α␈↓αx␈α␈↓βeq␈α␈↓αy␈↓,␈αthen␈α ␈↓αx␈↓␈α and␈α␈↓αy␈↓␈αare␈αcertainly␈α the␈α same
␈↓S-expression␈α since␈αthey␈α are␈α represented␈αby␈α
the␈αsame␈αstructure␈αin␈αmemory.␈α The␈αconverse␈α
is␈αfalse
␈↓because␈αthere␈αis␈αno␈α guarantee␈α in␈α general␈α that␈α the␈α same␈αS-expression␈αis␈αnot␈αrepresented␈αby␈αtwo
␈↓different␈αlist␈αstructures.␈α In␈αthe␈αparticular␈αcase␈αwhere␈αat␈αleast␈αone␈αof␈αthe␈αS-expressions␈αis␈α known␈αto
␈↓be␈α
 an␈α
atom,␈α
this␈α
guarantee␈α
can␈α
be␈α
given,␈α
because␈α
LISP␈α
represents␈α
atoms␈α
uniquely␈α
in␈α
memory.

␈↓        The␈αabove␈αare␈αall␈α
the␈αbasic␈αfunctions␈αof␈α
LISP;␈αall␈αother␈αLISP␈α
functions␈α can␈α be␈α built␈α
 from
␈↓them␈α∞ using␈α∞ recursive␈α
 conditional␈α∞expressions␈α∞as␈α
will␈α∞shortly␈α∞be␈α
explained.␈α∞However,␈α∞the␈α∞use␈α
of
␈↓certain␈α
abbreviations␈α
makes␈α
LISP␈α
programs␈α
easier␈α
to␈α
write␈α
and␈α
understand.

␈↓        ␈↓βn␈α
␈↓αx␈↓␈α
  is␈α an␈α
 abbreviation␈α
for␈α ␈↓αx␈α
␈↓βeq␈α
␈↓∧NIL␈↓.␈α
 It␈αrates␈α
a␈α
special␈αnotation␈α
because␈α
 ␈↓∧NIL␈↓␈α
 plays␈αthe
␈↓same␈α∞ role␈α∞ among␈α∂ lists␈α∞ that␈α∞ zero␈α∞plays␈α∂ among␈α∞ numbers,␈α∞ and␈α∞list␈α∂variables␈α∞often␈α∞have␈α∂to␈α∞be
␈↓tested␈α
to␈α
see␈α
if␈α
their␈α
value␈α
is␈α
 ␈↓∧NIL␈↓.
␈↓␈↓ ¬xCHAPTER I␈↓ I8


␈↓        The␈αnotation␈α  ␈↓αlist␈↓↓[␈↓αx1,␈α
x2,␈α.␈α.␈α.␈α
,␈αxn␈↓↓]␈↓␈α  is␈α
 used␈α to␈α denote␈α the␈α
composition␈αof␈α␈↓αcons␈↓'s␈αthat␈α
forms
␈↓a␈α
list␈α
from␈α
its␈α
elements.␈α
 Thus

␈↓        ␈↓αlist␈↓↓[␈↓αx,␈α
y,␈α
z␈↓↓]␈α=␈α
␈↓αcons␈↓↓[␈↓αx,␈α
cons␈↓↓[␈↓αy,␈αcons␈↓↓[␈↓αz,␈α
␈↓∧NIL␈↓↓]]]

␈↓↓␈↓and␈αforms␈αa␈αlist␈αof␈αthree␈αelements␈αout␈αof␈αthe␈αquantities␈α ␈↓αx,␈α y,␈α␈↓␈α and␈α␈↓αz␈↓.␈α We␈α often␈α write␈α ␈↓↓<␈↓αx␈αy␈α.␈α.␈α.
␈↓αz␈↓↓>␈↓␈α
 instead␈α
of␈α
 ␈↓αlist␈↓↓[␈↓αx,␈α
y,␈α
.␈α
.␈α
.␈α
,␈α
z␈↓↓]␈↓␈α
when␈α
this␈α
will␈α
not␈α
cause␈α
 confusion.

␈↓        Compositions␈αof␈α ␈↓βa␈↓␈α and␈α ␈↓βd␈↓␈α are␈αwritten␈αby␈αconcatenating␈α the␈αletters␈α  ␈↓βa␈↓␈α and␈α ␈↓βd␈↓.␈α Thus,␈αit␈αis
␈↓easily␈α∂seen␈α∂that␈α∂ ␈↓βad␈α∂␈↓αx␈↓␈α⊂ denotes␈α∂the␈α∂second␈α∂element␈α∂of␈α∂the␈α⊂list␈α∂ ␈↓αx␈↓,␈α∂and␈α∂ ␈↓βadd␈α∂␈↓αx␈↓␈α∂ denotes␈α⊂the␈α∂third
␈↓element␈α
of␈α
that␈α
list.



␈↓6.  ␈↓βConditional␈α
expressions.␈↓


␈↓        When␈αthe␈αform␈αthat␈αrepresents␈αa␈αfunction␈αdepends␈αon␈αwhether␈αa␈αcertain␈α predicate␈αis␈αtrue␈αof
␈↓the␈α
arguments,␈α
conditional␈α
expressions.␈α
 are␈α
used.␈α
 The␈α
conditional␈α
expression

␈↓        ␈↓βif␈α
␈↓αp␈α
␈↓βthen␈α
␈↓αa␈α
␈↓βelse␈α
␈↓αb

␈↓α␈↓is␈α∞evaluated␈α
as␈α∞follows:␈α
 First␈α∞ ␈↓αp␈↓␈α
 is␈α∞evaluated␈α∞and␈α
determined␈α∞to␈α
be␈α∞true␈α
or␈α∞false.␈α
 If␈α∞ ␈↓αp␈↓␈α∞ is␈α
true,
␈↓then␈α ␈↓αa␈↓␈α is␈αevaluated␈αand␈α its␈α value␈αis␈α the␈α value␈α of␈α the␈α expression.␈α  If␈α  ␈↓αp␈↓␈α  is␈αfalse,␈αthen␈α ␈↓αb␈↓␈α is
␈↓evaluated␈α∩and␈α⊃its␈α∩value␈α⊃is␈α∩the␈α⊃value␈α∩of␈α∩the␈α⊃expression.␈α∩ Note␈α⊃that␈α∩if␈α⊃␈↓αp␈↓␈α∩ is␈α⊃true,␈α∩ ␈↓αb␈↓␈α∩ is␈α⊃never
␈↓evaluated,␈αand␈α
if␈α ␈↓αp␈↓␈α
 is␈αfalse,␈α
then␈α ␈↓αa␈↓␈α
 is␈αnever␈α
evaluated.␈α The␈α
importance␈αof␈α
this␈αwill␈αbe␈α
explained
␈↓later.␈α∞ A␈α∂familiar␈α∞ function␈α∞that␈α∂can␈α∞be␈α∂written␈α∞conveniently␈α∞using␈α∂conditional␈α∞expressions␈α∂is␈α∞the
␈↓absolute␈α
value␈α
of␈α
a␈α
real␈α
number.␈α
 We␈α
have

␈↓        ␈↓↓|␈↓αx␈↓↓|␈α
=␈α␈↓βif␈α
␈↓αx␈↓↓<␈↓∧0␈α␈↓βthen␈α
␈↓↓-␈↓αx␈α␈↓βelse␈α
␈↓αx.

␈↓α␈↓A␈α
more␈α
general␈α
form␈α
of␈α
conditional␈α
expression␈α
is

␈↓        ␈↓βif␈α
␈↓αp␈α
␈↓βthen␈α
␈↓αa␈α
␈↓βelse␈α
if␈α
␈↓αq␈α
␈↓βthen␈α
␈↓αb␈α
.␈α
.␈α
.␈α
 ␈↓βelse␈α
if␈α
␈↓αs␈α
␈↓βthen␈α
␈↓αd␈α
␈↓βelse␈α
␈↓αe.

␈↓α␈↓There␈α can␈α be␈α any␈α number␈α of␈α terms;␈α the␈α value␈α is␈αdetermined␈αby␈αevaluating␈αthe␈αpropositional
␈↓terms␈α ␈↓αp,␈α q␈↓,␈αetc.␈αuntil␈αa␈αtrue␈αterm␈α is␈αfound;␈α the␈αvalue␈αis␈αthen␈αthat␈αof␈αthe␈αterm␈αfollowing␈αthe␈αnext
␈↓␈↓βthen␈↓.␈α
 If␈α
none␈α
of␈α
the␈α
propositional␈α
terms␈α
is␈α
true,␈α
then␈α
the␈α
value␈α
is␈α
that␈α
of␈α
the␈α
term␈α∞following␈α
the
␈↓␈↓βelse␈↓.

␈↓        The␈α
function␈α
graphed␈α
in␈α
figure␈α
4␈α
is␈α
described␈α
by␈α
the␈α
equation

␈↓        ␈↓αtri␈↓↓[␈↓αx␈↓↓]␈α
=␈α␈↓βif␈α
␈↓αx␈↓↓<-␈↓∧1␈α
␈↓βthen␈α␈↓∧0␈α
␈↓βelse␈α
if␈α␈↓αx␈↓↓<␈↓∧0␈α
␈↓βthen␈α
␈↓∧1␈↓↓+␈↓αx␈α␈↓βelse␈α
if␈α
␈↓αx␈↓↓<␈↓∧1␈α␈↓βthen␈α
␈↓∧1␈↓↓-␈↓αx␈α␈↓βelse␈α
␈↓∧0.
␈↓␈↓ ¬xCHAPTER I␈↓ I9













␈↓∧␈↓                              Figure␈α
4.



␈↓7.  ␈↓βBoolean␈α
expressions.␈↓


␈↓        In␈α∩ making␈α∩ up␈α∪ the␈α∩ propositional␈α∩  parts␈α∩  of␈α∪  conditional␈α∩expressions,␈α∩  it␈α∪  is␈α∩  often
␈↓necessary␈α∂  to␈α∞  combine␈α∂ elementary␈α∂propositional␈α∞expressions␈α∂using␈α∞the␈α∂Boolean␈α∂operators␈α∞ and,
␈↓or,␈α and␈α
not.␈α  We␈α
 use␈α the␈α symbols␈α
  ␈↓↓∧␈↓,␈α ␈↓↓∨␈↓,␈α
and␈α ␈↓↓¬␈↓␈α respectively,␈α
for␈αthese␈α
operators.␈α In␈αLISP,␈α
the
␈↓atoms␈α∂ ␈↓∧T␈↓␈α∂ and␈α∂ ␈↓∧NIL␈↓␈α∂ are␈α∂used␈α∂for␈α⊂ the␈α∂ truth␈α∂values.␈α∂ The␈α∂Boolean␈α∂operators␈α∂may␈α⊂be␈α∂described
␈↓simply␈α∀by␈α∪listing␈α∀the␈α∀values␈α∪of␈α∀the␈α∀elementary␈α∪Boolean␈α∀expressions␈α∀for␈α∪ each␈α∀ case␈α∀ of␈α∪ the
␈↓arguments.␈α
 Thus␈α
we␈α
have:

␈↓        ␈↓∧T␈↓↓∧␈↓∧T ␈↓↓= ␈↓∧T
␈↓∧␈↓        ␈↓∧T␈↓↓∧␈↓∧F ␈↓↓= ␈↓∧F
␈↓∧␈↓        ␈↓∧F␈↓↓∧␈↓∧T ␈↓↓= ␈↓∧F
␈↓∧␈↓        ␈↓∧F␈↓↓∧␈↓∧F ␈↓↓= ␈↓∧F

␈↓∧␈↓        ␈↓∧T␈↓↓∨␈↓∧T ␈↓↓= ␈↓∧T
␈↓∧␈↓        ␈↓∧T␈↓↓∨␈↓∧F ␈↓↓= ␈↓∧T
␈↓∧␈↓        ␈↓∧F␈↓↓∨␈↓∧T ␈↓↓= ␈↓∧T
␈↓∧␈↓        ␈↓∧F␈↓↓∨␈↓∧F ␈↓↓= ␈↓∧F

␈↓∧␈↓        ␈↓∧␈↓↓¬␈↓∧T ␈↓↓= ␈↓∧F
␈↓∧␈↓        ␈↓∧␈↓↓¬␈↓∧F ␈↓↓= ␈↓∧T.

␈↓∧␈↓        ␈↓∧␈↓The␈α∞ Boolean␈α∂ operators␈α∞ can␈α∞ be␈α∂ described␈α∞ by␈α∞  conditional␈α∂expressions␈α∞in␈α∂the␈α∞following
␈↓way:

␈↓        ␈↓αp␈↓↓∧␈↓αq ␈↓↓= ␈↓βif ␈↓αp ␈↓βthen ␈↓αq ␈↓βelse ␈↓∧F
␈↓∧␈↓        ␈↓∧␈↓αp␈↓↓∨␈↓αq ␈↓↓= ␈↓βif ␈↓αp ␈↓βthen ␈↓∧T ␈↓βelse ␈↓αq
␈↓α␈↓        ␈↓α␈↓↓¬␈↓αp ␈↓↓= ␈↓βif ␈↓αp ␈↓βthen ␈↓∧F ␈↓βelse ␈↓∧T.

␈↓∧␈↓Note␈αthat␈αif␈α ␈↓αp␈↓␈α is␈αfalse␈α ␈↓αp␈↓↓∧␈↓αq␈↓␈α is␈αfalse␈αindependent␈αof␈αthe␈αvalue␈α of␈α␈↓αq␈↓,␈α and␈α likewise␈α if␈α ␈↓αp␈↓␈α is␈αtrue,
␈↓then␈α∞ ␈↓αp␈↓↓∨␈↓αq␈↓␈α∂ is␈α∞true␈α∞independent␈α∂of␈α∞␈↓αq␈↓.␈α∂ If␈α∞ ␈↓αp␈↓␈α∞ has␈α∂been␈α∞evaluated␈α∂and␈α∞found␈α∞to␈α∂be␈α∞false,␈α∂then␈α∞  ␈↓αq␈↓
␈↓␈↓ ¬xCHAPTER I␈↓ :10


␈↓does␈α∂not␈α∂ have␈α⊂ to␈α∂ be␈α∂evaluated␈α⊂at␈α∂all␈α∂to␈α⊂find␈α∂the␈α∂value␈α⊂of␈α∂ ␈↓αp␈↓↓∧␈↓αq␈↓,␈α∂and,␈α⊂in␈α∂fact,␈α∂LISP␈α⊂does␈α∂not
␈↓evaluate␈α
 ␈↓αq␈↓␈α
 in␈αthis␈α
case.␈α
 Similarly,␈α ␈↓αq␈↓␈α
 is␈α
not␈α
evaluated␈α in␈α
 evaluating␈α
  ␈↓αp␈↓↓∨␈↓αq␈↓␈α if␈α
 ␈↓αp␈↓␈α
 is␈α
true.␈αThis
␈↓procedure␈α⊂is␈α⊃in␈α⊂accordance␈α⊃with␈α⊂the␈α⊂above␈α⊃conditional␈α⊂expression␈α⊃descriptions␈α⊂of␈α⊃ the␈α⊂Boolean
␈↓operators.␈α The␈α
importance␈αof␈αthis␈α
convention␈αwhich␈αcontrasts␈α
with␈αthat␈αof␈α
ALGOL␈α 60,␈α
 will␈α be
␈↓apparent␈α
 later␈α
 when␈α
 we␈α
 discuss␈α
recursive␈α
definitions␈α
of␈α
functions␈α
and␈α
predicates.



␈↓8.  ␈↓βRecursive␈α
function␈α
definitions.␈↓


␈↓        In␈α∞such␈α∞languages␈α∞as␈α∞FORTRAN␈α∞and␈α
 Algol,␈α∞ computer␈α∞ progrrams␈α∞are␈α∞ expressed␈α∞ in␈α
the
␈↓main␈αas␈αsequences␈αof␈αassignment␈αstatements␈αand␈αconditional␈αgo␈αto's.␈α In␈αLISP,␈αprograms␈αare␈αmainly
␈↓expressed␈α
 in␈α
 the␈α
form␈α
of␈α
recursively␈α
defined␈α
functions.␈α
 We␈α
begin␈α
with␈α
an␈α
example.

␈↓        The␈α∞ function␈α∞  ␈↓αalt␈↓↓[␈↓αx␈↓↓]␈↓␈α∞  gives␈α∞ a␈α∞ list␈α∂ whose␈α∞ elements␈α∞ are␈α∞alternate␈α∞elements␈α∞of␈α∞the␈α∂list␈α∞ ␈↓αx␈↓
␈↓beginning␈α
with␈α
the␈α
first.␈α
 Thus

␈↓        ␈↓αalt␈↓↓[␈↓∧(A B C D E)␈↓↓] = ␈↓∧(A C E),

␈↓∧␈↓        ␈↓∧␈↓αalt␈↓↓[␈↓∧(((A B) (C D))␈↓↓] = ␈↓∧((A B)),

␈↓∧␈↓        ␈↓∧␈↓αalt␈↓↓[␈↓∧(A)␈↓↓] = ␈↓∧(A),
␈↓∧␈↓and
␈↓        ␈↓αalt␈↓↓[␈↓∧NIL␈↓↓] = ␈↓∧NIL.

␈↓∧␈↓        ␈↓∧The function  ␈↓αalt␈↓  is defined by the equation

␈↓        alt␈↓↓[␈↓αx␈↓↓] ← ␈↓βif n ␈↓αx ␈↓↓∨ ␈↓βn d ␈↓αx ␈↓βthen ␈↓αx ␈↓βelse a ␈↓αx . alt␈↓↓[␈↓βdd ␈↓αx␈↓↓].

␈↓↓␈↓        ␈↓↓␈↓The␈α
 above␈α
 definition␈α is␈α
 best␈α
 explained␈α by␈α
 using␈α
 it␈αto␈α
evaluate␈α
some␈α
expressions.␈α We
␈↓start␈αwith␈α ␈↓αalt␈↓↓[␈↓∧NIL␈↓↓]␈↓.␈αTo␈αevaluate␈αthis␈αexpression␈α we␈α evaluate␈α the␈αexpression␈αto␈αthe␈αright␈αof␈αthe␈α
 ␈↓↓←␈↓
␈↓sign␈α
remembering␈α
that␈α
the␈αvariable␈α
 ␈↓αx␈↓␈α
 has␈α
the␈α
value␈α ␈↓∧NIL␈↓.␈α
 A␈α
 conditional␈α
expression␈α is␈α
 evaluated
␈↓by␈α
first␈α
evaluating␈α
the␈α
first␈α
propositional␈α∞term␈α
¬␈α
in␈α
this␈α
case␈α
 ␈↓βn␈α
␈↓αx␈α∞␈↓↓∨␈α
␈↓βn␈α
d␈α
␈↓αx␈↓.␈α
This␈α
expression␈α∞is␈α
a
␈↓disjunction␈αand␈αin␈α its␈αevaluation␈αwe␈αfirst␈αevaluate␈αthe␈αfirst␈αdisjunct,␈αnamely␈α ␈↓βn ␈↓αx␈↓.␈α Since␈α ␈↓αx␈α␈↓↓=␈α␈↓∧NIL,
␈↓∧␈↓βn␈α␈↓αx␈↓␈α is␈αtrue,␈αthe␈αdisjunction␈αis␈αtrue,␈αand␈αthe␈αvalue␈αof␈α the␈α conditional␈α expression␈α is␈α the␈αvalue␈αof
␈↓the␈α∞term␈α
after␈α∞the␈α
first␈α∞true␈α
propositiional␈α∞term.␈α∞The␈α
term␈α∞is␈α
  ␈↓αx␈↓,␈α∞ and␈α
 its␈α∞ value␈α
 is␈α∞␈↓∧NIL␈↓,␈α∞ so␈α
the
␈↓value␈α
of␈α
 ␈↓αalt␈↓↓[␈↓∧NIL␈↓↓]␈↓␈α∞ is␈α
 ␈↓∧NIL␈↓␈α
 as␈α
stated␈α∞above.␈α
  Obeying␈α
the␈α
rules␈α∞about␈α
the␈α
order␈α
of␈α∞evaluation␈α
of
␈↓terms␈α∞in␈α∂ conditional␈α∞ and␈α∂Boolean␈α∞expressions␈α∂is␈α∞important␈α∂in␈α∞this␈α∂case␈α∞since␈α∂if␈α∞we␈α∂didn't␈α∞obey
␈↓these␈αrules,␈αwe␈αmight␈αfind␈αourselves␈αtrying␈αto␈α evaluate␈α  ␈↓βn␈αd␈α␈↓αx␈↓␈α  or␈α␈↓αalt␈↓↓[␈↓βdd␈α␈↓αx␈↓↓]␈↓,␈αand␈αsince␈α ␈↓αx␈↓␈α
is␈α ␈↓∧NIL␈↓,
␈↓neither␈α∞of␈α∞these␈α∞has␈α∞a␈α∞value.␈α
 An␈α∞attempt␈α∞to␈α∞evaluate␈α∞them␈α∞in␈α
LISP␈α∞would␈α∞give␈α∞rise␈α∞to␈α∞an␈α
error
␈↓return.

␈↓        As␈αa␈α
second␈αexample,␈α
consider␈α  ␈↓αalt␈↓↓[␈↓∧(A␈α
 B)␈↓↓]␈↓.␈α  Since␈α
 neither␈α␈↓βn␈α
␈↓αx␈↓␈αnor␈α
␈↓βn␈αd␈α
␈↓αx␈↓␈αis␈α
true␈αin␈αthis␈α
case,
␈↓the␈αdisjunction␈α␈↓βn␈α␈↓αx␈α␈↓↓∨␈α␈↓βn␈αd␈α␈↓αx␈α␈↓is␈α false␈α and␈α the␈α value␈α of␈α the␈α expression␈α is␈α the␈α  value␈α  of␈α␈↓βa␈α␈↓αx␈α.
␈↓αalt␈↓↓[␈↓βdd␈α␈↓αx␈↓↓].␈α    ␈↓βa␈α␈↓αx␈↓␈αhas␈αthe␈αvalue␈α ␈↓∧A␈↓,␈αand␈α␈↓βdd␈α␈↓αx␈↓␈αhas␈αthe␈αvalue␈α␈↓∧NIL␈↓,␈αso␈αwe␈αmust␈αnow␈αevaluate␈α ␈↓αalt␈↓↓[␈↓∧NIL␈↓↓]␈↓,
␈↓and␈α∞we␈α∞already␈α∞know␈α∞that␈α
the␈α∞value␈α∞  of␈α∞  this␈α∞  expression␈α
 is␈α∞  ␈↓∧NIL␈↓.␈α∞ Therefore,␈α∞ the␈α∞ value␈α
 of
␈↓␈↓αalt␈↓↓[␈↓∧(A␈α
B)␈↓↓]␈↓␈α
 is␈α
that␈α
of␈α
 ␈↓∧A.NIL␈↓␈α
 which␈αis␈α
 ␈↓∧(A)␈↓.
␈↓␈↓ ¬xCHAPTER I␈↓ :11


␈↓        We␈α
can␈α
describe␈α
this␈α
 evaluation␈α
 in␈α
 a␈α
 less␈α
 wordy␈α
 way␈α
 by␈α
writing

␈↓        ␈↓αalt␈↓↓[␈↓∧(A B)␈↓↓] = ␈↓βif n␈↓∧(A B) ␈↓↓∨ ␈↓βn d␈↓∧(A B) ␈↓βthen ␈↓∧(A B) ␈↓βelse
␈↓β                        a␈↓∧(A B).␈↓αalt␈↓↓[␈↓βdd␈↓∧(A B)␈↓↓]

␈↓↓                   = ␈↓βif ␈↓∧NIL ␈↓↓∨ ␈↓βn d␈↓∧(A B) ␈↓βthen ␈↓∧(A B) ␈↓βelse
␈↓β                        a␈↓∧(A B).␈↓αalt␈↓↓[␈↓βdd␈↓∧(A B)␈↓↓]

␈↓↓                   = ␈↓βif ␈↓∧NIL ␈↓βthen ␈↓∧(A B) ␈↓βelse
␈↓β                        a␈↓∧(A B).␈↓αalt␈↓↓[␈↓βdd␈↓∧(A B)␈↓↓]

␈↓↓                   = ␈↓βa␈↓∧(A B).␈↓αalt␈↓↓[␈↓βdd␈↓∧(A B)␈↓↓]

␈↓↓                   = ␈↓∧A.␈↓αalt␈↓↓[␈↓∧NIL␈↓↓]

␈↓↓                   = ␈↓∧A␈↓↓.[␈↓βif n␈↓∧NIL ␈↓↓∨ ␈↓βnd␈↓∧NIL ␈↓βthen ␈↓∧NIL ␈↓βelse
␈↓β                        a␈↓∧NIL.␈↓αalt␈↓↓[␈↓βdd␈↓∧NIL␈↓↓]]

␈↓↓                   = ␈↓∧A␈↓↓.[␈↓βif ␈↓∧T ␈↓↓∨ ␈↓βnd␈↓∧NIL ␈↓βthen ␈↓∧NIL ␈↓βelse
␈↓β                        a␈↓∧NIL.␈↓αalt␈↓↓[␈↓βdd␈↓∧NIL␈↓↓]]

␈↓↓                   = ␈↓∧A␈↓↓.[␈↓βif ␈↓∧T ␈↓βthen ␈↓∧NIL ␈↓βelse
␈↓β                        a␈↓∧NIL.␈↓αalt␈↓↓[␈↓βdd␈↓∧NIL␈↓↓]]

␈↓↓                   = ␈↓∧A␈↓↓.[␈↓∧NIL␈↓↓]

␈↓↓                   = ␈↓∧(A).

␈↓∧␈↓        ␈↓∧␈↓This␈α⊂is␈α⊃still␈α⊂very␈α⊃ long-winded,␈α⊂ and␈α⊃ now␈α⊂ that␈α⊃ the␈α⊂ reader␈α⊃understands␈α⊂ the␈α⊃ order␈α⊂ of
␈↓evaluation␈α
 of␈α
 conditional␈α
 and␈α
Boolean␈α
expressions,␈α
we␈α
can␈α
proceed␈α
more␈α
briefly␈α
to␈α
evaluate

␈↓        ␈↓αalt␈↓↓[␈↓∧(A␈αB␈αC␈αD␈αE)␈↓↓]␈α=␈α␈↓∧A.␈↓αalt␈↓↓[␈↓∧(C␈αD␈αE)␈↓↓]

␈↓↓                        =␈α␈↓∧A␈↓↓.[␈↓∧C.␈↓αalt␈↓↓[␈↓∧(E)␈↓↓]]

␈↓↓                        =␈α␈↓∧A.␈↓↓[␈↓∧C.(E)␈↓↓]

␈↓↓                        =␈α␈↓∧(A␈αC␈αE).

␈↓∧␈↓        ␈↓∧␈↓Here␈α
are␈α
three␈α
more␈α
examples␈α
of␈αrecursive␈α
functions␈α
and␈α
their␈α
application:␈α
We␈α
define␈α ␈↓αlast␈↓
␈↓by

␈↓        ␈↓αlast␈↓↓[␈↓αx␈↓↓]␈α
←␈α
␈↓βif␈α
n␈α
d␈α␈↓αx␈α
␈↓βthen␈α
a␈α
␈↓αx␈α
␈↓βelse␈α␈↓αlast␈↓↓[␈↓βd␈α
␈↓αx␈↓↓],

␈↓↓␈↓and␈α
we␈α
compute

␈↓        ␈↓αlast␈↓↓[␈↓∧(A␈αB␈αC)␈↓↓]␈α=␈α␈↓βif␈α
nd␈↓∧(A␈αB␈αC)␈α␈↓βthen␈αa␈↓∧(A␈α
B␈αC)␈α␈↓βelse␈α␈↓αlast␈↓↓[␈↓βd␈↓∧(A␈αB␈α
C)␈↓↓]
␈↓␈↓ ¬xCHAPTER I␈↓ :12


␈↓↓                      =␈α␈↓αlast␈↓↓[␈↓∧(B␈αC)␈↓↓]

␈↓↓                      =␈α␈↓αlast␈↓↓[␈↓∧(C)␈↓↓]

␈↓↓                      =␈α␈↓∧C.

␈↓∧␈↓Clearly␈α
  ␈↓αlast␈↓␈α
  computes␈α the␈α
 last␈α
element␈αof␈α
a␈α
list.␈α ␈↓αlast␈↓↓[␈↓∧NIL␈↓↓]␈↓␈α
is␈α
undefined␈αin␈α
the␈α
LISP␈αlanguage;
␈↓the␈α⊃result␈α⊂of␈α⊃trying␈α⊂ to␈α⊃ compute␈α⊂ it␈α⊃may␈α⊂be␈α⊃an␈α⊂error␈α⊃message␈α⊂or␈α⊃may␈α⊂be␈α⊃some␈α⊃random␈α⊂result
␈↓depending␈α
on␈α
the␈α
implementation.

␈↓        The␈α
function␈α
 ␈↓αsubst␈↓␈α
 is␈α
defined␈α
by

␈↓        ␈↓αsubst␈↓↓[␈↓αx, y, z␈↓↓] ← ␈↓βif at ␈↓αz ␈↓βthen ␈↓↓[␈↓βif ␈↓αz ␈↓βeq ␈↓αy ␈↓βthen ␈↓αx ␈↓βelse ␈↓αz␈↓↓]
␈↓↓                        ␈↓βelse ␈↓αsubst␈↓↓[␈↓αx, y, ␈↓βa ␈↓αz␈↓↓].␈↓αsubst␈↓↓[␈↓αx, y, ␈↓βd ␈↓αz␈↓↓].

␈↓↓␈↓We have

␈↓        ␈↓αsubst␈↓↓[␈↓∧(A.B), X, ((X.A).X)␈↓↓] =

␈↓↓␈↓                ␈↓↓= ␈↓αsubst␈↓↓[␈↓∧(A.B), X, (X.A)␈↓↓]␈↓αsubst␈↓↓[␈↓∧(A.B), X, X␈↓↓]

␈↓↓␈↓                ␈↓↓= [␈↓αsubst␈↓↓[␈↓∧(A.B), X, X␈↓↓].␈↓αsubst␈↓↓[␈↓∧(A.B), X, A␈↓↓]].␈↓∧(A.B)

␈↓∧␈↓                ␈↓∧␈↓↓= [[␈↓∧(A.B)␈↓↓].␈↓∧A␈↓↓].␈↓∧(A.B)␈↓↓]

␈↓↓␈↓                ␈↓↓= ␈↓∧(((A.B).A).(A.B)).

␈↓∧␈↓αsubst␈↓␈α
 computes␈α
the␈α
result␈α
of␈α
substituting␈α
the␈αS-expression␈α
  ␈↓αx␈↓␈α
  for␈α
the␈α
 atom␈α
 ␈↓αy␈↓␈α
 in␈αthe␈α
S-expression
␈↓␈↓αz␈↓.␈α
 This␈α
is␈α
an␈α
important␈α
operation␈α
in␈α
all␈α
kinds␈α
of␈α
symbolic␈α
computation.

␈↓        Another␈α
important␈α
operation␈α
is␈α∞the␈α
 concatenation␈α
 of␈α
 lists,␈α∞and␈α
 it␈α
is␈α
generally␈α∞denoted␈α
by
␈↓the␈α
infixed␈α
expression␈α
 ␈↓αx␈↓↓*␈↓αy␈↓␈α
 since␈α
it␈α
is␈α
associative.␈α
 We␈α
have␈α
the␈α
examples

␈↓        ␈↓∧(A␈αB␈αC)␈↓↓*␈↓∧(D␈αE␈αF)␈α␈↓↓=␈α␈↓∧(A␈αB␈αC␈αD␈αE␈αF),

␈↓∧␈↓and

␈↓        ␈↓∧NIL␈↓↓*␈↓∧(A␈αB)␈α␈↓↓=␈α␈↓∧(A␈αB)␈α␈↓↓=␈α␈↓∧(A␈αB)␈↓↓*␈↓∧NIL,

␈↓∧␈↓and␈α
the␈α
formal␈α
definition

␈↓        ␈↓αx␈↓↓*␈↓αy␈α
␈↓↓←␈α
␈↓βif␈α
n␈α
␈↓αx␈α
␈↓βthen␈α
␈↓αy␈α
␈↓βelse␈α
␈↓↓[␈↓βa␈α␈↓αx␈↓↓].[[␈↓βd␈α
␈↓αx␈↓↓]*␈↓αy␈↓↓].

␈↓↓␈↓        ␈↓↓␈↓The␈α∂ Boolean␈α∂ operations␈α∂can␈α∞also␈α∂be␈α∂used␈α∂in␈α∞making␈α∂recursive␈α∂definitions␈α∂ provided␈α∞ we
␈↓observe␈α
 the␈α
 order␈α
  of␈α
  evaluation␈α
  of␈α
constituents.␈α
First,␈α
we␈α
define␈α
a␈α
predicate␈α
 ␈↓αequal␈↓␈α
 by

␈↓        ␈↓αequal␈↓↓[␈↓αx, y␈↓↓] ← ␈↓αx ␈↓βeq ␈↓αy ␈↓↓∨ [¬␈↓βat ␈↓αx ␈↓↓∧ ¬␈↓βat ␈↓αy ␈↓↓∧
␈↓↓                        ␈↓αequal␈↓↓[␈↓βa ␈↓αx, ␈↓βa ␈↓αy␈↓↓] ∧ ␈↓αequal␈↓↓[␈↓βd ␈↓αx, ␈↓βd ␈↓αy␈↓↓]].
␈↓␈↓ ¬xCHAPTER I␈↓ :13


␈↓↓␈↓αequal␈↓↓[␈↓αx,␈α
y␈↓↓]␈↓␈α
 is␈α
true␈α
 if␈α
 and␈α only␈α
 if␈α
  ␈↓αx␈↓␈α
  and␈α
  ␈↓αy␈↓␈α
  are␈α the␈α
 same␈α
S-expression,␈α
 and␈α
 the␈α
 use␈α of
␈↓this␈α
predicate␈α
makes␈α
up␈α
for␈α∞the␈α
fact␈α
that␈α
the␈α
basic␈α∞predicate␈α
 ␈↓βeq␈↓␈α
 is␈α
guaranteed␈α
 to␈α∞ test␈α
 equality
␈↓only␈α
when␈α
 one␈α
 of␈α
the␈α
operands␈α
is␈α
known␈α
to␈α
be␈α
an␈α
atom.␈α
 We␈α
shall␈α
also␈α
use␈α
the␈α
infixes␈α
 ␈↓↓=␈↓␈α
 and␈α
 ␈↓↓≠␈↓.

␈↓        Membership␈α
of␈α
an␈α
S-expression␈α
 ␈↓αx␈↓␈α
 in␈α
a␈α
list␈α
 ␈↓αy␈↓␈α
 is␈α
tested␈α
by

␈↓        ␈↓αmember␈↓↓[␈↓αx,␈α
y␈↓↓]␈α←␈α
¬␈↓βn␈α␈↓αy␈α
␈↓↓∧␈α[[␈↓αx␈α
␈↓↓=␈α␈↓βa␈α
␈↓αy␈↓↓]␈α∨␈α
␈↓αmember␈↓↓[␈↓αx,␈α␈↓βd␈α
␈↓αy␈↓↓]].

␈↓↓␈↓This␈α
relation␈α
is␈α
also␈α
denoted␈α
by␈α
 ␈↓αx␈↓↓ε␈↓αy.␈α
 Here␈α
are␈α
some␈α
computations:

␈↓α␈↓        ␈↓αmember␈↓↓[␈↓∧B, (A B)␈↓↓] = ¬␈↓βn ␈↓∧(A B) ␈↓↓∧ [[␈↓∧B ␈↓↓= ␈↓βa ␈↓∧(A B)␈↓↓]
␈↓↓                            ∨ ␈↓αmember␈↓↓[␈↓∧B, ␈↓βd ␈↓∧(A B)␈↓↓]],

␈↓↓                        = ␈↓αmember␈↓↓[␈↓∧B, (B)␈↓↓]

␈↓↓                        = ␈↓∧T.

␈↓∧␈↓        ␈↓∧␈↓Sometimes␈α a␈α function␈α is␈α
defined␈αwith␈αthe␈αhelp␈αof␈α
auxiliary␈αfunctions.␈α Thus,␈αthe␈αreverse␈α
of
␈↓a␈αlist␈α
 ␈↓αx␈↓␈α,␈α
(e.g.␈α  ␈↓αreverse␈↓↓[␈↓∧(A␈α
B␈αC␈α
D)␈↓↓]␈α=␈α
␈↓∧(D␈αC␈α
B␈αA)␈↓),␈α
is␈αgiven␈α
by

␈↓        ␈↓αreverse␈↓↓[␈↓αx␈↓↓] ← ␈↓αrev␈↓↓[␈↓αx, ␈↓∧NIL␈↓↓]

␈↓↓␈↓where

␈↓        ␈↓αrev␈↓↓[␈↓αx, y␈↓↓]   ← ␈↓βif n ␈↓αx ␈↓βthen ␈↓αy ␈↓βelse ␈↓αrev␈↓↓[␈↓βd ␈↓αx␈↓↓, [␈↓βa ␈↓αx␈↓↓].␈↓αy␈↓↓].

␈↓↓␈↓A computation is

␈↓        ␈↓αreverse␈↓↓[␈↓∧(A B C)␈↓↓] = ␈↓αrev␈↓↓[␈↓∧(A B C), NIL␈↓↓]

␈↓↓                         = ␈↓αrev␈↓↓[␈↓∧(B C), (A)␈↓↓]

␈↓↓                         = ␈↓αrev␈↓↓[␈↓∧(C), (B A)␈↓↓]

␈↓↓                         = ␈↓αrev␈↓↓[␈↓∧NIL, (C B A)␈↓↓]

␈↓↓                         = ␈↓∧(C B A).

␈↓∧␈↓        ␈↓∧␈↓A more elaborate example of recursive definition is given by

␈↓        ␈↓αflatten␈↓↓[␈↓αx␈↓↓] ← ␈↓αflat␈↓↓[␈↓αx, ␈↓∧NIL␈↓↓]

␈↓↓␈↓        ␈↓↓␈↓αflat␈↓↓[␈↓αx, y␈↓↓] ← ␈↓βif at ␈↓αx ␈↓βthen ␈↓αx.y
␈↓α                              ␈↓βelse ␈↓αflat␈↓↓[␈↓βa ␈↓αx, flat␈↓↓[␈↓βd ␈↓αx, y␈↓↓]].

␈↓↓␈↓We have

␈↓        ␈↓αflatten␈↓↓[␈↓∧((A.B).C)␈↓↓] = ␈↓αflat␈↓↓[␈↓∧((A.B).C), NIL␈↓↓]
␈↓␈↓ ¬xCHAPTER I␈↓ :14


␈↓↓                           = ␈↓αflat␈↓↓[␈↓∧(A.B), ␈↓αflat␈↓↓[␈↓∧C, NIL␈↓↓]]

␈↓↓                           = ␈↓αflat␈↓↓[␈↓∧(A.B), (C)␈↓↓]

␈↓↓                           = ␈↓αflat␈↓↓[␈↓∧A, ␈↓αflat␈↓↓[␈↓∧B, (C)␈↓↓]]

␈↓↓                           = ␈↓αflat␈↓↓[␈↓∧A, (B C)␈↓↓]

␈↓↓                           = ␈↓∧(A B C).

␈↓∧␈↓The␈α
 reader␈α
 will␈αsee␈α
that␈α
the␈αvalue␈α
of␈α
 ␈↓αflatten␈↓↓[␈↓αx␈↓↓]␈↓␈α is␈α
a␈α
list␈αof␈α
the␈α
atoms␈α of␈α
 the␈α
 S-expression␈α  ␈↓αx␈↓
␈↓from␈α  left␈α
  to␈α  write.␈α   Thus␈α
␈↓αflatten␈↓↓[␈↓∧((A␈αB)␈α
A)␈↓↓]␈α=␈α␈↓∧(A␈α
B␈αNIL␈αA␈α
NIL)␈↓.

␈↓        Many␈α⊃ functions␈α⊃ can␈α⊃be␈α⊃conveniently␈α⊃written␈α⊃in␈α⊃more␈α⊃than␈α⊃one␈α⊃way.␈α⊃ For␈α⊃example,␈α⊂the
␈↓function␈α
  ␈↓αreverse␈↓␈α
  mentioned␈α
 above␈α
 can␈α
 be␈α
written␈α
without␈α
an␈α
auxiliary␈α
function␈α
as␈α
follows:

␈↓        ␈↓αreverse␈↓↓[␈↓αx␈↓↓]␈α
←␈α␈↓βif␈α
n␈α␈↓αx␈α
␈↓βthen␈α
␈↓∧NIL␈α␈↓βelse␈α
␈↓αreverse␈↓↓[␈↓βd␈α␈↓αx␈↓↓]*␈↓∧<a␈α
x>

␈↓∧␈↓but␈α
it␈α
will␈α
be␈α
explained␈α
later␈α
that␈α
the␈α
earlier␈α
 definition␈α
 involves␈α
less␈α
computation.

␈↓        The␈α∞use␈α∞of␈α∞conditional␈α
 expressions␈α∞ for␈α∞ recursive␈α∞ function␈α
definition␈α∞ is␈α∞ not␈α∞ limited␈α
 to
␈↓functions␈α of␈α S-expressions.␈α  For␈αexample,␈αthe␈αfactorial␈αfunction␈αand␈αthe␈αEuclidean␈αalgorithm␈α for
␈↓the␈α
greatest␈α
common␈α
divisor␈α
are␈α
expressed␈α
as␈α
follows:

␈↓        ␈↓αn␈↓↓! ← ␈↓βif ␈↓αn␈↓↓=␈↓∧0 ␈↓βthen ␈↓∧1 ␈↓βelse ␈↓αn␈↓↓(␈↓αn␈↓↓-␈↓∧1␈↓↓)!

␈↓↓␈↓and

␈↓        ␈↓αgcd␈↓↓(␈↓αm, n␈↓↓) ← ␈↓βif ␈↓αm␈↓↓>␈↓αn ␈↓βthen ␈↓αgcd␈↓↓(␈↓αn, m␈↓↓) ␈↓βelse if ␈↓αm␈↓↓=␈↓∧0 ␈↓βthen ␈↓αn
␈↓α                        ␈↓βelse ␈↓αgcd␈↓↓(␈↓αn mod m, m␈↓↓)

␈↓↓␈↓where␈α
 ␈↓αn␈α
mod␈α
m␈↓␈α
 denotes␈αthe␈α
remainder␈α
when␈α
 ␈↓αn␈↓␈α
 is␈α
divided␈αby␈α
 ␈↓αm␈↓␈α
  and␈α
may␈α
itself␈α
be␈αexpressed
␈↓recursively␈α
by

␈↓        ␈↓αn␈α
mod␈α
m␈α
␈↓↓←␈α
␈↓βif␈α␈↓αn␈↓↓<␈↓αm␈α
␈↓βthen␈α
␈↓αn␈α
␈↓βelse␈α
␈↓↓(␈↓αn␈↓↓-␈↓αm␈↓↓)␈α␈↓αmod␈α
m.

␈↓α␈↓                              Exercises

␈↓        1.␈α
Consider␈α
the␈α
function␈α
 ␈↓αdrop␈↓␈α
 defined␈α
by

␈↓        ␈↓αdrop␈↓↓[␈↓αx␈↓↓]␈α
←␈α
␈↓βif␈αn␈α
␈↓αx␈α
␈↓βthen␈α␈↓∧NIL␈α
␈↓βelse␈α
␈↓↓<␈↓βa␈α␈↓αx␈↓↓>.␈↓αdrop␈↓↓[␈↓βd␈α
␈↓αx␈↓↓].

␈↓↓␈↓Compute␈α
(by␈α
hand)␈α
 ␈↓αdrop␈↓↓[␈↓∧(A␈α
B␈α
C)␈↓↓]␈↓.␈α What␈α
does␈α
 ␈↓αdrop␈↓␈α
 do␈α
 to␈α
 lists␈α in␈α
general?

␈↓        2.␈α
What␈α
does␈α
the␈α
function

␈↓        ␈↓αr2␈↓↓[␈↓αx␈↓↓]␈α
←␈α
␈↓βif␈αn␈α
␈↓αx␈α
␈↓βthen␈α␈↓∧NIL␈α
␈↓βelse␈α
␈↓αreverse␈↓↓[␈↓βa␈α␈↓αx␈↓↓].␈↓αr2␈↓↓[␈↓βd␈α
␈↓αx␈↓↓]
␈↓␈↓ ¬xCHAPTER I␈↓ :15


␈↓↓␈↓do␈α
to␈α
lists␈α
of␈α
lists?␈α
 How␈α
about

␈↓        ␈↓αr3␈↓↓[␈↓αx␈↓↓]␈α
←␈α
␈↓βif␈αat␈α
␈↓αx␈α
␈↓βthen␈α
␈↓αx␈α␈↓βelse␈α
␈↓αreverse␈↓↓[␈↓αr4␈↓↓[␈↓αx␈↓↓]]

␈↓↓␈↓        ␈↓↓␈↓αr4␈↓↓[␈↓αx␈↓↓]␈α
←␈α
␈↓βif␈αn␈α
␈↓αx␈α
␈↓βthen␈α␈↓∧NIL␈α
␈↓βelse␈α
␈↓αr3␈↓↓[␈↓βa␈α␈↓αx␈↓↓].␈↓αr4␈↓↓[␈↓βd␈α
␈↓αx␈↓↓]?

␈↓↓␈↓        ␈↓↓␈↓3.␈α
Compare

␈↓        ␈↓αr3'␈↓↓[␈↓αx␈↓↓]␈α
←␈α
␈↓βif␈α
at␈α␈↓αx␈α
␈↓βthen␈α
␈↓αx␈α
␈↓βelse␈α
␈↓αr3'␈↓↓[␈↓βd␈α␈↓αx␈↓↓]*<␈↓αr3'␈↓↓[␈↓βa␈α
␈↓αx␈↓↓]>

␈↓↓␈↓with␈α
the␈α
function␈α
 ␈↓αr3␈↓␈α
 of␈α
the␈α
preceding␈α
example.

␈↓        4.␈α
Consider␈α
 ␈↓αr5␈↓␈α
 defined␈α
by

␈↓        ␈↓αr5␈↓↓[␈↓αx␈↓↓] ← ␈↓βif n ␈↓αx ␈↓↓∨ ␈↓βn d ␈↓αx ␈↓βthen ␈↓αx
␈↓α␈↓                ␈↓α␈↓βelse ␈↓↓[␈↓βa ␈↓αr5␈↓↓[␈↓βd ␈↓αx␈↓↓]]
␈↓↓                        . ␈↓αr5␈↓↓[␈↓βa ␈↓αx . r5␈↓↓[␈↓βd ␈↓αr5␈↓↓[␈↓βd ␈↓αx␈↓↓]]].

␈↓↓␈↓Compute␈α ␈↓αr5␈↓↓[␈↓∧(A␈αB␈αC␈αD)␈↓↓]␈↓.␈α What␈αdoes␈α ␈↓∧r5␈↓␈α do␈αin␈αgeneral?␈α  Needless␈α to␈αsay,␈αthis␈αis␈αnot␈αa␈αgood␈αway
␈↓of␈α
computing␈α
this␈α
function␈α
even␈α
though␈α
it␈α
involves␈α
no␈α
auxiliary␈α
functions.



␈↓9.  ␈↓βLambda␈α
expressions␈α
and␈α
functions␈α
with␈α
functions␈α
as␈α
arguments.␈↓


␈↓        It␈α
is␈α
common␈α
to␈α
use␈α
phrases␈α
like␈α
"the␈α
function␈α
 2␈↓αx␈↓↓+␈↓αy␈↓".␈α
  This␈α
is␈α
 not␈α
a␈α
precise␈αnotation␈α
because
␈↓we␈α
cannot␈αsay␈α
 2␈↓αx␈↓↓+␈↓αy␈↓↓(␈↓∧3,␈α
4␈↓↓)␈↓␈α and␈α
know␈α
whether␈αthe␈α
desired␈α
 result␈α is␈α
  2␈↓
␈␈↓3+4␈α
  or␈α  2␈↓
␈␈↓4+3␈α
  regarding
␈↓the␈α∞expression␈α∞ as␈α∞a␈α∞function␈α∞of␈α∞two␈α∞variables.␈α∞ Worse␈α∞yet,␈α∞we␈α∞might␈α∞have␈α∞meant␈α∞a␈α∞one-variable
␈↓function␈α
of␈α
 ␈↓αx␈↓␈α
 wherein␈α
 ␈↓αy␈↓␈α
  is␈α
 regarded␈α
 as␈α
 a␈α
parameter.

␈↓        The␈α∂problem␈α∂ of␈α⊂ giving␈α∂ names␈α∂ to␈α∂ functions␈α⊂ is␈α∂ solved␈α∂ by␈α∂Church's␈α⊂  λ-notation.␈α∂   In
␈↓the␈α∂ above␈α∂ example,␈α∂ we␈α∂ would␈α∂ write␈α∂␈↓↓λ␈↓αx␈α⊂y␈↓↓:␈α∂␈↓∧2␈↓αx␈↓↓+␈↓αy␈↓␈α∂ to␈α∂denote␈α∂ the␈α∂ function␈α∂ of␈α⊂ two␈α∂ variables
␈↓with␈α first␈αargument␈α  ␈↓αx␈↓␈α  and␈α second␈α argument␈α
  ␈↓αy␈↓␈α whose␈αvalue␈αis␈αgiven␈αby␈αthe␈αexpression␈α
 2␈↓αx␈↓↓+␈↓αy␈↓.
␈↓Thus,

␈↓        ␈↓↓[λ␈↓αx␈αy␈↓↓:␈α␈↓∧2␈↓αx␈↓↓+␈↓αy␈↓↓][␈↓∧3,␈α4␈↓↓]␈α=␈α
␈↓∧10␈↓.

␈↓Likewise,␈α∩  ␈↓↓[λ␈↓αy␈α⊃x␈↓↓:␈α∩␈↓∧2␈↓αx␈↓↓+␈↓αy␈↓↓][␈↓∧3,␈α⊃4␈↓↓]␈α∩=␈α⊃␈↓∧11␈↓.␈α∩ Like␈α⊃variables␈α∩of␈α⊃integration␈α∩and␈α⊃the␈α∩bound␈α∩variables␈α⊃of
␈↓quantifiers␈αin␈α
logic,␈αvariables␈α
following␈α  λ␈α
are␈α bound␈α
 or␈αdummy␈α
and␈αthe␈α
expression␈αas␈α
a␈αwhole
␈↓may␈α
be␈α∞replaced␈α
by␈α
any␈α∞others␈α
provided␈α
the␈α∞replacement␈α
is␈α
done␈α∞consistently␈α
and␈α
does␈α∞not␈α
make
␈↓any␈α∂ variable␈α∞ bound␈α∂ by␈α∂ λ␈α∞ the␈α∂same␈α∂as␈α∞a␈α∂free␈α∂variable␈α∞in␈α∂the␈α∂expression.␈α∞ Thus␈α∂  ␈↓↓λ␈↓αx␈α∂y␈↓↓:␈α∞␈↓∧2␈↓αx␈↓↓+␈↓αy␈↓
␈↓represents␈α the␈α same␈α
  function␈α  as␈α␈↓↓λ␈↓αy␈αx␈↓↓:␈α
␈↓∧2␈↓αy␈↓↓+␈↓αx␈↓␈αor␈α␈↓↓λ␈↓αu␈αv␈↓↓:␈α
␈↓∧2␈↓αu␈↓↓+␈↓αv␈↓␈α,␈αbut␈αin␈α
the␈αfunction␈αof␈αone␈α
argument
␈↓␈↓↓λ␈↓αx␈↓↓:␈α
␈↓∧2␈↓αx␈↓↓+␈↓αy␈↓␈α
,␈α
we␈α
cannot␈α
replace␈α
the␈α
variable␈α
 ␈↓αx␈↓␈α
 by␈α
␈↓αy␈↓␈α
,␈α
though␈α
we␈α
could␈α
replace␈α
it␈αby␈α
 ␈↓αu␈↓.

␈↓        λ-notation␈αplays␈αtwo␈αimportant␈α roles␈α in␈α LISP.␈α  First,␈α it␈αallows␈αus␈αto␈αrewrite␈αan␈αexpression
␈↓containing␈αtwo␈αor␈αmore␈αoccurrences␈αof␈αthe␈αsame␈αsub-expression␈αin␈αsuch␈αa␈αway␈αthat␈αthe␈α expression
␈↓␈↓ ¬xCHAPTER I␈↓ :16


␈↓occurs␈α∞only␈α∞once.␈α∞Thus␈α∞  ␈↓↓(␈↓∧2␈↓αx␈↓↓+␈↓∧1␈↓↓)↑␈↓∧4␈↓↓+␈↓∧3␈↓↓(␈↓∧2␈↓αx␈↓↓+␈↓∧1␈↓↓)↑␈↓∧3␈↓␈α∞ can␈α∞be␈α∞written␈α∞␈↓↓[λ␈↓αw␈↓↓:␈α∞␈↓αw␈↓↓↑␈↓∧4␈↓↓+␈↓∧3␈↓αw␈↓↓↑␈↓∧3␈↓↓][␈↓∧2␈↓αx␈↓↓+␈↓∧1␈↓↓]␈↓.␈α∞This␈α∂can␈α∞save
␈↓considerable␈αcomputation,␈α
and␈αcorresponds␈α
to␈αthe␈αpractice␈α
in␈αordinary␈α
programming␈αof␈αassigning␈α
to
␈↓a␈αvariable␈αthe␈αvalue␈αof␈αa␈αsub-expression␈αthat␈αoccurs␈αmore␈αthan␈αonce␈α in␈αan␈α expression␈α and␈α then
␈↓writing␈α
 the␈α
 expression␈α
 in␈α
 terms␈α
of␈α
the␈α
variable.

␈↓        The␈α∂second␈α∞use␈α∂of␈α∞λ-expressions␈α∂is␈α∞in␈α∂ using␈α∞ functions␈α∂ that␈α∞take␈α∂functions␈α∂as␈α∞arguments.
␈↓Suppose␈αwe␈α
want␈αto␈αform␈α
a␈αnew␈αlist␈α
from␈αan␈αold␈α
one␈αby␈αapplying␈α
a␈αfunction␈α ␈↓αf␈↓␈α
 to␈αeach␈αelement␈α
 of
␈↓the␈α
 list.␈α
 This␈α
can␈α
be␈α
done␈α
using␈α
the␈α
function␈α
 ␈↓αmapcar␈↓␈α
 defined␈α
by

␈↓        ␈↓αmapcar␈↓↓[␈↓αx,␈α
f␈↓↓]␈α←␈α
␈↓βif␈α
n␈α␈↓αx␈α
␈↓βthen␈α
␈↓∧NIL␈α␈↓βelse␈α
␈↓αf␈↓↓[␈↓βa␈α
␈↓αx␈↓↓]␈α .␈α
␈↓αmapcar␈↓↓[␈↓βd␈α␈↓αx,␈α
f␈↓↓].

␈↓↓␈↓Suppose␈α
the␈αoperation␈α
we␈αwant␈α
to␈αperform␈α
is␈α
squaring,␈αand␈α
we␈αwant␈α
 to␈αapply␈α
it␈α
to␈αthe␈α
list␈α ␈↓∧(1␈α
2␈α3␈α
4
␈↓∧5␈α6␈α
7)␈↓.␈α We␈α
have

␈↓        ␈↓αmapcar␈↓↓[␈↓∧(1␈α2␈α3␈α4␈α5␈α6␈α7),␈α␈↓↓λ␈↓αx␈↓↓:␈α␈↓αx␈↓↓↑␈↓∧2␈↓↓]␈α=␈α␈↓∧(1␈α4␈α9␈α16␈α25␈α36␈α49).

␈↓∧␈↓        ␈↓∧␈↓A␈α
more␈α
generally␈α
useful␈α
operation␈α
than␈α ␈↓αmapcar␈↓␈α
is␈α
␈↓αmaplist␈↓␈α
in␈α
 which␈α
 the␈α
 function␈αis␈α
applied
␈↓to␈α
the␈α
successive␈α
sublists␈α
of␈α
the␈α
list␈α
rather␈α
than␈α
to␈α
the␈α
elements.␈α
 ␈↓αmaplist␈↓␈α
 is␈α
defined␈α
by

␈↓        ␈↓αmaplist␈↓↓[␈↓αx,␈α
f␈↓↓]␈α←␈α
␈↓βif␈α
n␈α␈↓αx␈α
␈↓βthen␈α␈↓∧NIL␈α
␈↓βelse␈α
␈↓αf␈↓↓[␈↓αx␈↓↓]␈α .␈α
␈↓αmaplist␈↓↓[␈↓βd␈α␈↓αx,␈α
f␈↓↓].

␈↓↓␈↓        ␈↓↓␈↓As␈α∞ an␈α∞ application␈α∞ of␈α∂ ␈↓αmaplist␈↓␈α∞and␈α∞functional␈α∞arguments,␈α∂we␈α∞shall␈α∞define␈α∞a␈α∂function␈α∞ for
␈↓differentiating␈α algebraic␈α expressions␈αinvolving␈αsums␈αand␈αproducts.␈α The␈αexpressions␈αare␈αbuilt␈αup
␈↓from␈α
atoms␈α
denoting␈α
variables␈α
and␈α
integer␈α
constants␈α
according␈α
to␈α
the␈α
syntax

␈↓        <expression> ::= <variable> | <integer> |
␈↓                         (PLUS <explist>) | (TIMES <explist>)

␈↓        <explist>    ::= <expression> | <expression><explist>

␈↓Here,␈α∂ ␈↓∧PLUS␈↓␈α⊂ followed␈α∂by␈α⊂a␈α∂list␈α⊂of␈α∂arguments␈α⊂denotes␈α∂the␈α⊂sum␈α∂of␈α⊂these␈α∂arguments␈α⊂and␈α∂ ␈↓∧TIMES␈↓
␈↓followed␈α
by␈αa␈α
list␈α
of␈αarguments␈α
 denotes␈α
 their␈αproduct.␈α
  The␈α
 function␈α  ␈↓αdiff␈↓↓[␈↓αe,␈α
v␈↓↓]␈↓␈α
 gives␈αthe␈α
partial
␈↓derivative␈α
of␈α
the␈α
expression␈α
 ␈↓αe␈↓␈α
 with␈α
respect␈α
to␈α
the␈α
variable␈α
 ␈↓αv␈↓.␈α
We␈α
have

␈↓        ␈↓αdiff␈↓↓[␈↓αe, v␈↓↓] ← ␈↓βif at ␈↓αe ␈↓βthen ␈↓↓[␈↓βif ␈↓αe ␈↓βeq ␈↓αv ␈↓βthen ␈↓∧1 ␈↓βelse ␈↓∧0␈↓↓]
␈↓↓␈↓                ␈↓↓␈↓βelse if a ␈↓αe ␈↓βeq ␈↓∧PLUS ␈↓βthen
␈↓β                        ␈↓∧PLUS . ␈↓αmapcar␈↓↓[␈↓βd ␈↓αe␈↓↓, λ␈↓αx␈↓↓: ␈↓αdiff␈↓↓[␈↓αx, v␈↓↓]_]
␈↓↓␈↓                ␈↓↓␈↓βelse if a ␈↓αe ␈↓βeq ␈↓∧TIMES ␈↓αthen
␈↓α                        ␈↓∧PLUS.␈↓αmaplist␈↓↓[␈↓βd ␈↓αe␈↓↓, λ␈↓αx␈↓↓: ␈↓∧TIMES
␈↓∧                              . ␈↓αmaplist␈↓↓[␈↓βd ␈↓αe␈↓↓, λ␈↓αy␈↓↓: ␈↓βif ␈↓αx ␈↓βeq ␈↓αy ␈↓βthen
␈↓β                                        ␈↓αdiff␈↓↓[␈↓βa ␈↓αy, v␈↓↓] ␈↓βelse a ␈↓αy␈↓↓]].

␈↓↓␈↓The␈α
 term␈α
 that␈α
 describes␈α
 the␈α
 rule␈α
 for␈α
 differentiating␈α
 products␈α
corresponds␈α
to␈α
the␈α
rule

␈↓        ␈↓↓∂/∂␈↓αv    e␈↓¬i␈↓↓ =       [␈↓βif ␈↓αi␈↓↓=␈↓αj ␈↓βthen ␈↓↓∂␈↓αe␈↓¬j␈↓↓/∂␈↓αv ␈↓βelse ␈↓αe␈↓¬j␈↓↓].
␈↓␈↓ ¬xCHAPTER I␈↓ :17


␈↓↓and␈α  ␈↓αmaplist␈↓␈α  has␈α to␈αbe␈αused␈αrather␈α
than␈α ␈↓αmapcar␈↓␈α since␈αwhether␈αto␈αdifferentiate␈αin␈α
forming␈αthe
␈↓product␈αis␈αdetermined␈αby␈αequality␈αof␈αthe␈αindices␈α  ␈↓αi␈↓␈α  and␈α  ␈↓αj␈↓␈α  rather␈α than␈αequality␈αof␈αthe␈αterms␈α ␈↓αe␈↓¬i␈↓
␈↓and␈α
␈↓αe␈↓¬j␈↓.

␈↓        Two␈αmore␈αuseful␈αfunctions␈αwith␈αfunctions␈αas␈αarguments␈αare␈αthe␈αpredicates␈α ␈↓αandlis␈↓␈α and␈α ␈↓αorlis␈↓
␈↓defined␈α
by␈α
the␈α
equations

␈↓        ␈↓αandlis␈↓↓[␈↓αu,␈α
p␈↓↓]␈α←␈α
␈↓βn␈α␈↓αu␈α
␈↓↓∨␈α[␈↓αp␈↓↓[␈↓βa␈α
␈↓αu␈↓↓]␈α∧␈α
␈↓αandlis␈↓↓[␈↓βd␈α␈↓αu,␈α
p␈↓↓]]

␈↓↓␈↓and

␈↓        ␈↓αorlis␈↓↓[␈↓αu,␈α
p␈↓↓]␈α←␈α
¬␈↓βn␈α␈↓αu␈α
␈↓↓∧␈α[␈↓αp␈↓↓[␈↓βa␈α
␈↓αu␈↓↓]␈α∨␈α
␈↓αorlis␈↓↓[␈↓βd␈α␈↓αu,␈α
p␈↓↓]].

␈↓↓␈↓                              Exercises

␈↓        1.␈α
Compute␈α ␈↓αdiff␈↓↓[␈↓∧(TIMES␈α
X␈α
(PLUS␈αY␈α
1)␈α3),␈α
X␈↓↓]␈↓␈α
 using␈α the␈α
 above␈α
definition␈α of␈α
 ␈↓αdiff␈↓.␈α Now␈α
do
␈↓you␈α
see␈α
why␈α
algebraic␈α
simplification␈α
is␈α
important?

␈↓        2.␈αCompute␈α ␈↓αorlis␈↓↓[␈↓∧((A␈α
B)␈α(C␈αD)␈αE),␈α
␈↓βat␈↓↓]␈↓.



␈↓10.  ␈↓βLabel.␈↓


␈↓        The␈α
λ␈αmechanism␈α
is␈α
 not␈α adequate␈α
 for␈α
 providing␈α names␈α
 for␈α
recursive␈α functions,␈α
 because
␈↓in␈α∪this␈α∪case␈α∩there␈α∪has␈α∪to␈α∩be␈α∪a␈α∪way␈α∪of␈α∩referring␈α∪to␈α∪the␈α∩function␈α∪name␈α∪within␈α∪the␈α∩ function.
␈↓Therefore,␈α we␈αuse␈α the␈αnotation␈α ␈↓βlabel␈↓↓[␈↓αf,␈αe␈↓↓]␈↓␈α to␈αdenote␈αthe␈αexpression␈α ␈↓αe␈↓␈α but␈αwhere␈α
occurrences␈αof
␈↓␈↓αf␈↓␈α⊃ within␈α⊃ ␈↓αe␈↓␈α⊃ refer␈α⊃ to␈α⊃ the␈α⊃ whole␈α∩ expression.␈α⊃ For␈α⊃example,␈α⊃ suppose␈α⊃we␈α⊃wished␈α⊃to␈α∩define␈α⊃a
␈↓function␈αthat␈α
takes␈αalternate␈αelements␈α
of␈αeach␈α
element␈αof␈αa␈α
list␈αand␈α
makes␈αa␈αlist␈α
of␈αthese.␈α  Thus,␈α
we
␈↓want

␈↓        ␈↓αglub␈↓↓[␈↓∧((A␈αB␈αC)␈α(A␈αB␈αC␈αD)␈α(X␈αY␈αZ))␈↓↓]␈α=␈α␈↓∧((A␈αC)␈α(A␈αC)␈α(X␈αZ)).

␈↓∧␈↓We␈α
can␈α
make␈α
the␈α
definition

␈↓        ␈↓αglub␈↓↓[␈↓αx␈↓↓] ← ␈↓αmapcar␈↓↓[␈↓αx, ␈↓βlabel␈↓↓[␈↓αalt␈↓↓, λ␈↓αx␈↓↓: ␈↓βif n ␈↓αx ␈↓↓∨ ␈↓βn d ␈↓αx ␈↓βthen ␈↓αx
␈↓α                                        ␈↓βelse a ␈↓αx . alt␈↓↓[␈↓βdd ␈↓αx␈↓↓]]].

␈↓↓␈↓The␈αidentifier␈α
 ␈↓αalt␈↓␈α in␈αthe␈α
above␈αexample␈αis␈α
bound␈αby␈αthe␈α
 label␈α and␈αis␈α
 local␈α to␈α that␈α
 expression,
␈↓and␈α∞ this␈α∞is␈α∞the␈α∞general␈α∞rule.␈α
 The␈α∞label␈α∞ construction␈α∞is␈α∞not␈α∞often␈α
used␈α∞in␈α∞LISP␈α∞since␈α∞it␈α∞is␈α
more
␈↓usual␈αto␈α give␈αfunctions␈αglobal␈αdefinitions.␈αD.␈αM.␈αR.␈αPark␈αpointed␈αout␈αthat␈αif␈αwe␈αallow␈αvariables␈αto
␈↓represent␈α
functions␈α
and␈α
use␈α
a␈α
 suitable␈α
  λ␈α
construction,␈α
the␈α
use␈α
of␈α
 label␈α
 could␈α
be␈α
avoided.
␈↓␈↓ εP␈↓ :18


␈↓β␈↓ ¬rCHAPTER II

␈↓β␈↓ β.HOW TO WRITE RECURSIVE FUNCTION DEFINITIONS






␈↓1.  ␈↓βStatic␈α
and␈α
dynamic␈α
ways␈α
of␈α
programming.␈↓


␈↓        In␈α∪ order␈α∪ to␈α∀ write␈α∪recursive␈α∪function␈α∪definitions,␈α∀one␈α∪must␈α∪think␈α∀about␈α∪programming
␈↓differently␈α
than␈α
is␈α customary␈α
 when␈α
 writing␈α
programs␈α in␈α
 languages␈α
like␈αFortran␈α
or␈α
Algol␈α
or␈αin
␈↓machine␈α∀language.␈α∀ In␈α∀these␈α∃languages,␈α∀one␈α∀has␈α∀in␈α∀mind␈α∃the␈α∀state␈α∀of␈α∀the␈α∃ computation␈α∀ as
␈↓represented␈α
 by␈α∞ the␈α
 values␈α∞of␈α
certain␈α∞variables␈α
or␈α∞locations␈α
in␈α∞the␈α
memory␈α∞of␈α
the␈α∞machine,␈α
and
␈↓then␈α∂ one␈α∂ writes␈α∂ statements␈α∂ or␈α∂ machine␈α∂instructions␈α∞in␈α∂order␈α∂to␈α∂make␈α∂the␈α∂state␈α∂change␈α∂in␈α∞an
␈↓appropriate␈α
way.

␈↓        When␈αwriting␈α
LISP␈αrecursive␈α
functions␈αone␈α
thinks␈αdifferently.␈α
 Namely,␈αone␈α
thinks␈αabout␈α
the
␈↓value␈α⊂of␈α⊂the␈α⊃ function,␈α⊂ asks␈α⊂ for␈α⊂ what␈α⊃values␈α⊂ of␈α⊂the␈α⊂arguments␈α⊃the␈α⊂value␈α⊂of␈α⊂the␈α⊃function␈α⊂is
␈↓immediate,␈α∂and,␈α∂given␈α∂ an␈α∂ arbitrary␈α∂ values␈α∂ of␈α∂ the␈α∂ arguments,␈α∂ for␈α∂ what␈α∂ simpler␈α∂arguments
␈↓must␈α
 the␈α function␈α
be␈αknown␈α
in␈αorder␈α
to␈αgive␈α
the␈αvalue␈α
of␈αthe␈α
function␈αfor␈α
 the␈α given␈α
 arguments.
␈↓Let␈α us␈α take␈α a␈α numerical␈αexample;␈α namely,␈α suppose␈α we␈αwant␈αto␈αcompute␈αthe␈αfunction␈α ␈↓αn␈↓↓!␈↓.␈α For
␈↓what␈αargument␈αis␈αthe␈αvalue␈αof␈αthe␈αfunction␈αimmediate.␈α  Clearly,␈α for␈α␈↓αn␈α␈↓↓=␈α␈↓∧0␈α or␈α ␈↓αn␈α␈↓↓=␈α␈↓∧1␈↓,␈αthe␈αvalue␈αis
␈↓immediately␈α
seen␈α∞to␈α
be␈α
 1.␈α∞ Moreover,␈α
we␈α
can␈α∞get␈α
the␈α
value␈α∞for␈α
an␈α
arbitrary␈α∞ ␈↓αn␈↓␈α
 if␈α
we␈α∞know␈α
 the
␈↓value␈α∞ for␈α∞␈↓αn␈↓↓-␈↓∧1.␈α∞  Also,␈α∂we␈α∞see␈α∞that␈α∞knowing␈α∞the␈α∂value␈α∞for␈α∞ ␈↓αn␈α∞␈↓↓=␈α∞␈↓∧1␈α∂ is␈α∞redundant,␈α∞since␈α∞it␈α∂can␈α∞be
␈↓∧obtained␈αfrom␈αthe␈α ␈↓αn␈α
␈↓↓=␈α␈↓∧0␈α case␈αby␈αthe␈α
 same␈α rule␈α as␈αgets␈α it␈α
 for␈α a␈α general␈α ␈↓αn␈↓∧␈α from␈α
the␈αvalue
␈↓∧for␈α
 ␈↓αn␈↓↓-␈↓∧1␈↓.␈α
 All␈α
this␈α
talk␈α
leads␈α
to␈α
the␈α
simple␈αrecursive␈α
formula:

␈↓        ␈↓αn␈↓↓!␈α←␈α
␈↓βif␈α␈↓αn␈α
␈↓↓=␈α␈↓∧0␈α
␈↓βthen␈α␈↓∧1␈α␈↓βelse␈α
␈↓αn␈↓↓(␈↓αn␈↓↓-␈↓∧1␈↓↓)!.

␈↓↓␈↓        ␈↓↓␈↓We␈αmay␈αregard␈αthis␈αas␈αa␈αstatic␈αway␈αof␈αlooking␈αat␈αprogramming.␈α We␈αask␈αwhat␈αsimpler␈αcases
␈↓the␈α
general␈αcase␈α
of␈α
our␈αfunction␈α
depends␈α
on␈αrather␈α
 than␈α
 how␈α we␈α
 build␈α
up␈αthe␈α
desired␈α
state␈αof
␈↓the␈αcomputation.␈α
 One␈αoften␈α
is␈αled␈α
to␈αbelieve␈αthat␈α
 static␈α=␈α
bad␈α and␈α
  dynamic␈α=␈α
good,␈αbut␈α in␈α
 this
␈↓case,␈α the␈α
static␈αway␈αis␈α
often␈αbetter␈α
than␈αthe␈αdynamic␈α
way.␈α LISP␈α
offers␈α both,␈α but␈α
 since␈α it␈α is␈α
 less
␈↓usual,␈α
 we␈α
 shall␈α
concentrate␈α
on␈α
the␈α
static␈α
way␈α
for␈α
now.

␈↓        Compare␈α∂ the␈α∂ above␈α∂ recursive␈α∂ definition␈α∂with␈α∂the␈α∂following␈α∂obvious␈α∂Algol␈α⊂program␈α∂for
␈↓computing␈α
 ␈↓αn␈↓↓!:

␈↓↓␈↓        ␈↓↓␈↓βinteger procedure ␈↓αfactorial␈↓↓(␈↓αn␈↓↓); ␈↓βinteger ␈↓αs␈↓↓;
␈↓↓␈↓βbegin
␈↓β␈↓        ␈↓β␈↓αs ␈↓↓:= ␈↓∧1␈↓↓;
␈↓↓␈↓αloop␈↓↓:       ␈↓βif ␈↓αn ␈↓↓= ␈↓∧0 ␈↓βthen go to ␈↓αdone␈↓↓;
␈↓↓␈↓        ␈↓↓␈↓αs ␈↓↓:= ␈↓αn␈↓↓*␈↓αs␈↓↓;
␈↓↓␈↓        ␈↓↓␈↓αn ␈↓↓:= ␈↓αn␈↓↓-␈↓∧1␈↓↓;
␈↓↓␈↓        ␈↓↓␈↓βgo to ␈↓αloop␈↓↓;
␈↓␈↓ ¬sCHAPTER II␈↓ :19


␈↓↓␈↓αdone␈↓↓:       ␈↓αfactorial ␈↓↓:= ␈↓αs␈↓↓;
␈↓↓␈↓βend␈↓↓;

␈↓↓␈↓        ␈↓↓␈↓The␈α⊂ LISP␈α⊂program␈α∂is␈α⊂shorter␈α⊂and␈α∂clearer␈α⊂in␈α⊂this␈α∂particularly␈α⊂favorable␈α⊂ case.␈α∂  Actually,
␈↓when␈α we␈α discuss␈α
 the␈α  mechanism␈α  of␈α
recursion,␈αit␈αwill␈α
turn␈αout␈αthat␈α
the␈αLISP␈αprogram␈α
will␈αbe
␈↓inefficient␈α∪in␈α∩using␈α∪the␈α∩pushdown␈α∪mechanism␈α∪unnecessarily␈α∩and␈α∪should␈α∩be␈α∪ replaced␈α∪by␈α∩ the
␈↓following␈α∃ somewhat␈α∃ longer␈α∃ program␈α∃that␈α∃corresponds␈α∃to␈α∃the␈α∃above␈α∃Algol␈α∃program␈α∀rather
␈↓precisely:

␈↓        ␈↓αn␈↓↓!␈α←␈α␈↓αfact␈↓↓(␈↓αn␈↓↓,␈α␈↓αs␈↓↓),

␈↓↓␈↓where

␈↓        ␈↓αfact␈↓↓(␈↓αn␈↓↓,␈α␈↓αs␈↓↓)␈α
←␈α␈↓βif␈α
␈↓αn␈α␈↓↓=␈α
␈↓∧0␈α␈↓βthen␈α
␈↓αs␈α␈↓βelse␈α␈↓αfact␈↓↓(␈↓αn␈↓↓-␈↓∧1␈↓↓,␈α
␈↓αn␈↓↓*␈↓αs␈↓↓).

␈↓↓␈↓In␈α
 fact,␈α
 compilers␈α
should␈α
produce␈α
the␈α
same␈α
object␈α
code␈α
from␈α
the␈α
two␈α
programs.



␈↓2.  ␈↓βSimple␈α
list␈α
recursion.␈↓


␈↓        About␈α
the␈α
simplest␈α
form␈αof␈α
recursion␈α
in␈α
LISP␈αoccurs␈α
when␈α
 one␈α
of␈αthe␈α
arguments␈α
is␈α
a␈αlist,␈α
the
␈↓result␈αis␈αimmediate␈αwhen␈αthe␈αargument␈αis␈αnull,␈αand␈αotherwise␈αwe␈αneed␈αonly␈αknow␈αthe␈αresult␈αfor␈αthe
␈↓␈↓βd␈↓-part␈α
of␈α
that␈αargument.␈α
 Consider,␈α
for␈α
example,␈α ␈↓αu␈↓↓*␈↓αv␈↓,␈α
the␈α
concatenation␈α
of␈αthe␈α
lists␈α
 ␈↓αu␈↓␈α
 and␈α␈↓αv␈↓.␈α
 The
␈↓result␈α
is␈αimmediate␈α
for␈α the␈α
 case␈α  ␈↓βn␈α
␈↓αu␈↓␈α
  and␈αotherwise␈α
depends␈αon␈α
the␈αresult␈α
for␈α ␈↓βd␈α
␈↓αu␈↓.␈α
 Thus,␈αwe
␈↓have

␈↓        ␈↓αu␈↓↓*␈↓αv␈α
␈↓↓←␈α
␈↓βif␈α
n␈α␈↓αu␈α
␈↓βthen␈α
␈↓αv␈α
␈↓βelse␈α
a␈α␈↓αu␈α
␈↓↓.␈α
[␈↓βd␈α
␈↓αu␈α␈↓↓*␈α
␈↓αv␈↓↓].

␈↓↓␈↓On␈α∞the␈α∞other␈α∞hand,␈α∞if␈α∞we␈α∞had␈α∞tried␈α∞to␈α∞recur␈α∞on␈α∞ ␈↓αv␈↓␈α∞ rather␈α∞than␈α∞on␈α∞ ␈↓αu␈↓␈α∞we␈α∞would␈α∞not␈α∞have␈α∞been
␈↓successful.␈α The␈α
result␈αwould␈α
be␈αimmediate␈α
for␈α␈↓βn␈α␈↓αv␈↓,␈α
but␈α ␈↓αu␈↓↓*␈↓αv␈↓␈α
 cannot␈αbe␈α
constructed␈αin␈α
any␈αdirect
␈↓way␈α∞from␈α∞  ␈↓αu␈↓↓*␈↓βd␈α∞␈↓αv␈↓␈α∞without␈α∞ a␈α∞ function␈α∞ that␈α∞ puts␈α∞ an␈α∞ element␈α∞onto␈α∞the␈α∞end␈α∞of␈α∞a␈α∞list.␈α∂ (From␈α∞a
␈↓strictly␈α∂list␈α∂point␈α∂of␈α∂view,␈α∂such␈α∂ a␈α⊂ function␈α∂ would␈α∂ be␈α∂ as␈α∂elementary␈α∂ as␈α∂ ␈↓αcons␈↓␈α∂ which␈α⊂puts␈α∂an
␈↓element␈αonto␈αthe␈αfront␈αof␈αa␈αlist,␈αbut,␈αwhen␈αwe␈αconsider␈αthe␈αimplementation␈αof␈αlists␈αby␈αlist␈αstructures,
␈↓we␈α see␈α that␈α the␈α function␈αis␈αnot␈αso␈αelementary.␈α This␈αhas␈αled␈αsome␈αpeople␈αto␈αconstruct␈αsystems␈αin
␈↓which␈αlists␈αare␈α bi-directional,␈α but,␈αin␈α the␈α main,␈α this␈αhas␈αturned␈αout␈αto␈αbe␈αa␈αbad␈αidea).␈α Anyway,
␈↓it␈α
is␈α
usually␈α
easier␈α
to␈α
recur␈α
on␈α
one␈α
argument␈α
of␈α
a␈α
function␈α
than␈α
 to␈α
 recur␈α
on␈α
the␈α
other.

␈↓        It␈α∞ is␈α
 often␈α∞necessary␈α∞to␈α
represent␈α∞a␈α
correspondence␈α∞between␈α∞the␈α
elements␈α∞of␈α
a␈α∞small␈α∞set␈α
of
␈↓atoms␈α
and␈α∞certain␈α
 S-expressions␈α
 by␈α∞ a␈α
list␈α
structure.␈α∞ This␈α
is␈α
conveniently␈α∞done␈α
by␈α
means␈α∞of␈α
an
␈↓association␈αlist␈αwhich␈αis␈αa␈αlist␈αof␈αpairs,␈αeach␈αpair␈αconsisting␈αof␈α an␈α atom␈α and␈αthe␈αcorresponding␈αS-
␈↓expression.␈α
Thus␈α
the␈α
association␈α
list

␈↓        ␈↓∧((X␈α.␈α(PLUS␈αA␈αB))␈α(Y␈α.␈αC)␈α(Z␈α.␈α(TIMES␈αU␈αV)),

␈↓∧␈↓which␈α
would␈α
print␈α
as
␈↓␈↓ ¬sCHAPTER II␈↓ :20


␈↓        ␈↓∧((X␈αPLUS␈αA␈αB))␈α(Y␈α.␈αC)␈α(Z␈αTIMES␈αU␈αV)),

␈↓∧␈↓pairs␈α
 ␈↓∧X␈↓␈α∞ with␈α
 ␈↓∧(PLUS␈α
A␈α∞B),␈α
 Y␈↓␈α∞ with␈α
 ␈↓∧C␈↓,␈α
etc.␈α∞We␈α
need␈α∞a␈α
 function␈α
 to␈α∞tell␈α
 whether␈α∞ anything␈α
 is
␈↓associated␈α
 with␈α
 the␈α
 atom␈α
  ␈↓αx␈↓␈α
  in␈α
the␈α
association␈α
list␈α
 ␈↓αa␈↓,␈α
and,␈α
if␈α
so,␈α
to␈α
tell␈α
us␈α
what.␈α
We␈α
have

␈↓        ␈↓αassoc␈↓↓[␈↓αx, a␈↓↓] ← ␈↓βif n ␈↓αa ␈↓βthen ␈↓∧NIL ␈↓βelse if ␈↓αx ␈↓βeq aa ␈↓αa ␈↓βthen a ␈↓αa
␈↓α␈↓                ␈↓α␈↓βelse ␈↓αassoc␈↓↓[␈↓αx, ␈↓βd ␈↓αa␈↓↓].

␈↓↓␈↓Its␈α
value␈α
is␈α
  ␈↓∧NIL␈↓␈α
  if␈α
 nothing␈α
 is␈α
 associated␈α
 with␈α
  ␈↓αx␈↓␈α
  and␈α
 the␈α
association␈α
pair␈α∞otherwise.␈α
 E.g.
␈↓␈↓αassoc␈↓↓[␈↓∧X,␈α((X.W)␈α(Y.V))␈↓↓]␈α=␈α␈↓∧(X.W)␈↓.

␈↓        It␈α
 commonly␈α
happens␈α
that␈α
a␈α
function␈α
has␈α
no␈α
simple␈α
recursion,␈α
but␈α
there␈α
is␈α
a␈αsimple␈α
recursion
␈↓for␈α⊃a␈α∩function␈α⊃with␈α⊃one␈α∩more␈α⊃variable␈α⊃that␈α∩ reduces␈α⊃ to␈α⊃the␈α∩desired␈α⊃function␈α⊃when␈α∩the␈α⊃extra
␈↓variable␈α
is␈α
set␈α
to␈α
␈↓∧NIL␈↓.␈α
 Thus

␈↓        ␈↓αreverse␈↓↓[␈↓αu␈↓↓]␈α←␈α␈↓αrev1␈↓↓[␈↓αx,␈α
␈↓∧NIL␈↓↓],

␈↓↓␈↓where

␈↓        ␈↓αrev1␈↓↓[␈↓αu,␈α
v␈↓↓]␈α
←␈α
␈↓βif␈α
n␈α
␈↓αu␈α␈↓βthen␈α
␈↓αv␈α
␈↓βelse␈α
␈↓αrev1␈↓↓[␈↓βd␈α
␈↓αu,␈α
␈↓βa␈α
␈↓αu␈α.␈α
v␈↓↓].

␈↓↓␈↓αreverse␈↓␈αhas␈αa␈α
direct␈αrecursive␈αdefinition␈α
as␈αdiscovered␈αby␈αS.␈α
Ness,␈αbut␈αno-one␈α
would␈αwant␈αto␈αuse␈α
the
␈↓following␈α∞in␈α∞actual␈α∞computation␈α∞ nor␈α∞does␈α∞ it␈α∞generate␈α∞much␈α∞understanding,␈α∞only␈α∞appreciation␈α∞of
␈↓Mr.␈α
Ness's␈α
ingenuity:

␈↓        ␈↓αreverse␈↓↓[␈↓αu␈↓↓] ← ␈↓βif n ␈↓αu ␈↓↓∨ ␈↓βn d ␈↓αu ␈↓βthen ␈↓αu ␈↓βelse
␈↓β␈↓                ␈↓βa ␈↓αreverse␈↓↓[␈↓βd ␈↓αu␈↓↓] . ␈↓αreverse␈↓↓[␈↓βa ␈↓αu. reverse␈↓↓[␈↓βd ␈↓αreverse␈↓↓[␈↓βd ␈↓αu␈↓↓]]].



␈↓                              Exercises

␈↓        1.␈αUsing␈αthe␈αfunction␈α ␈↓αmember␈↓↓[␈↓αx,␈αu␈↓↓]␈↓␈α defined␈αin␈αChapter␈αI␈αwhich␈α may␈αalso␈αbe␈αwritten␈α ␈↓αx␈α␈↓↓ε␈α␈↓αu␈↓,
␈↓write␈αfunction␈αdefinitions␈αfor␈αthe␈αunion␈α ␈↓αu␈α␈↓↓∪␈α␈↓αv␈↓␈α of␈αlists␈α ␈↓αu␈↓␈α and␈α ␈↓αv␈↓,␈αthe␈αintersection␈α ␈↓αu␈α␈↓↓∩␈α␈↓αv␈↓,␈α and␈α the
␈↓set␈α
 difference␈α
  ␈↓αu␈↓↓-␈↓αv␈↓.␈α
   What␈α
 is␈α
 wanted␈α
 should␈α
 be␈α
clear␈α
from␈α
the␈α
examples:

␈↓        ␈↓∧(A␈αB␈αC)␈α␈↓↓∪␈↓∧␈α(B␈αC␈αD)␈α␈↓↓=␈↓∧␈α(A␈αB␈αC␈αD),

␈↓∧␈↓        ␈↓∧(A␈αB␈αC)␈α␈↓↓∩␈↓∧␈α(B␈αC␈αD)␈α␈↓↓=␈↓∧␈α(B␈αC),

␈↓∧␈↓and

␈↓        ␈↓∧(A␈αB␈αC)␈α␈↓↓-␈↓∧␈α(B␈αC␈αD)␈α␈↓↓=␈↓∧␈α(A).

␈↓∧␈↓Pay␈α∂ attention␈α∂ to␈α∂getting␈α∂correct␈α∂the␈α∂trivial␈α∂cases␈α∂in␈α∂which␈α∂some␈α∂of␈α∂the␈α∂arguments␈α∂are␈α⊂␈↓∧NIL␈↓.␈α∂ In
␈↓general,␈α
it␈α
 is␈α
 important␈α
 to␈α
 understand␈α
clearly␈α
the␈α
trivial␈α
cases␈α
of␈α
functions.
␈↓␈↓ ¬sCHAPTER II␈↓ :21


␈↓        2.␈α⊂ Suppose␈α⊂  ␈↓αx␈↓␈α⊂  takes␈α⊃ numbers␈α⊂ as␈α⊂ values␈α⊂and␈α⊂ ␈↓αu␈↓␈α⊃ takes␈α⊂as␈α⊂values␈α⊂lists␈α⊂of␈α⊃numbers␈α⊂in
␈↓ascending␈αorder,␈α
e.g.␈α ␈↓∧(2␈α
4␈α7)␈↓.␈α
  Write␈α a␈α
function␈α  ␈↓αmerge␈↓↓[␈↓αx,␈α
u␈↓↓]␈↓␈α  whose␈α
 value␈α is␈α
obtained␈αfrom␈α
that
␈↓of␈α
 ␈↓αu␈↓␈α
 by␈α
putting␈α
    ␈↓αx␈↓␈α∞    in␈α
    ␈↓αu␈↓␈α
    in␈α
   its␈α
   proper␈α
   place.␈α∞    Thus␈α
␈↓αmerge␈↓↓[␈↓∧3,␈α
(2␈α
4)␈↓↓]␈α
=␈α
␈↓∧(2␈α∞3␈α
4)␈↓,
␈↓and␈α ␈↓αmerge␈↓↓[␈↓∧3,␈α(2␈α3)␈↓↓]␈α=␈α␈↓∧(2␈α3␈α
3)␈↓.

␈↓        3.␈α∂ Write␈α∞ functions␈α∂ giving␈α∞the␈α∂union,␈α∞intersection,␈α∂and␈α∞set␈α∂difference␈α∞of␈α∂ordered␈α∂lists;␈α∞the
␈↓result␈α
is␈α
wanted␈α
as␈α
an␈α
ordered␈α
list.

␈↓        Note␈α⊂that␈α∂computing␈α⊂these␈α∂functions␈α⊂of␈α⊂unordered␈α∂lists␈α⊂ takes␈α∂a␈α⊂ number␈α⊂ of␈α∂comparisons
␈↓proportional␈αto␈αthe␈αsquare␈α
of␈αthe␈αnumber␈αof␈α
elements␈αof␈αa␈αtypical␈α
list,␈αwhile␈αfor␈αordered␈α
lists,␈α the
␈↓number␈α
 of␈α
comparisons␈α
is␈α
proportional␈α
to␈α
the␈α
number␈α
of␈α
elements.

␈↓        4.␈α
 Using␈α
  ␈↓αmerge␈↓,␈α∞write␈α
a␈α
function␈α∞ ␈↓αsort␈↓␈α
 that␈α
transforms␈α
an␈α∞unordered␈α
list␈α
into␈α∞an␈α
ordered
␈↓list.

␈↓        5.␈α∃Write␈α⊗a␈α∃function␈α∃ ␈↓αgoodsort␈↓␈α⊗ that␈α∃ sorts␈α⊗ a␈α∃ list␈α∃ using␈α⊗ a␈α∃number␈α⊗ of␈α∃ comparisons
␈↓proportional␈α
 to␈α
  ␈↓αn␈α
log␈α
n␈↓,␈α
where␈α
 ␈↓αn␈↓␈α
 is␈α
the␈α
length␈α
of␈α
the␈α
list␈α
to␈α
be␈α
sorted.



␈↓3.  ␈↓βSimple␈α
S-expression␈α
recursion.␈↓


␈↓        In␈αanother␈αclass␈αof␈αproblems,␈αthe␈αvalue␈αof␈α the␈α function␈α is␈αimmediate␈α for␈α
 atomic␈αsymbols,
␈↓and␈α∂for␈α∞non␈α∂atoms␈α∞depends␈α∂only␈α∞on␈α∂the␈α∞values␈α∂for␈α∞ the␈α∂a-part␈α∞and␈α∂the␈α∞d-part␈α∂of␈α∂the␈α∞argument.
␈↓Thus␈α
  ␈↓αsubst␈↓␈α
was␈α
defined␈α
by

␈↓        ␈↓αsubst␈↓↓[␈↓αx, y, z␈↓↓] ← ␈↓βif at ␈↓αz ␈↓βthen ␈↓↓[␈↓βif ␈↓αz ␈↓βeq ␈↓αy ␈↓βthen ␈↓αx ␈↓βelse ␈↓αz␈↓↓]
␈↓↓                        ␈↓βelse ␈↓αsubst␈↓↓[␈↓αx, y, ␈↓βa ␈↓αz␈↓↓] . ␈↓αsubst␈↓↓[␈↓αx , y , ␈↓βd ␈↓αz␈↓↓].

␈↓↓␈↓        ␈↓↓␈↓Two␈α⊃other␈α∩examples␈α⊃are␈α⊃ ␈↓αequal␈↓␈α∩ which␈α⊃gives␈α⊃ the␈α∩ equality␈α⊃ of␈α⊃S-expressions␈α∩ and␈α⊃  ␈↓αflat␈↓
␈↓which␈α
spreads␈α
an␈α
S-expression␈α
into␈α
a␈α
list␈α
of␈α
atoms:␈α
 They␈α
are␈α
defined␈α
by

␈↓        ␈↓αx␈↓↓=␈↓αy␈α
␈↓↓←␈α
␈↓αx␈α␈↓βeq␈α
␈↓αy␈α
␈↓↓∨␈α[¬␈↓βat␈α
␈↓αx␈α
␈↓↓∧␈α¬␈↓βat␈α
␈↓αy␈α
␈↓↓∧␈α␈↓βa␈α
␈↓αx␈α
␈↓↓=␈α␈↓βa␈α
␈↓αy␈α
␈↓↓∧␈α␈↓βd␈α
␈↓αx␈α
␈↓↓=␈α␈↓βd␈α
␈↓αy␈↓↓],

␈↓↓␈↓and

␈↓        ␈↓αflat␈↓↓[␈↓αx␈↓↓]␈α←␈α␈↓αflata␈↓↓[␈↓αx,␈α
␈↓∧NIL␈↓↓]

␈↓↓␈↓where

␈↓        ␈↓αflata␈↓↓[␈↓αx,␈α
u␈↓↓]␈α
←␈α
␈↓βif␈α
at␈α
␈↓αx␈α␈↓βthen␈α
␈↓αx.y␈α
␈↓βelse␈α
␈↓αflata␈↓↓[␈↓βa␈α
␈↓αx,␈α
flata␈↓↓[␈↓βd␈α␈↓αx,␈α
y␈↓↓]].

␈↓↓␈↓                              EXERCISES

␈↓        1.␈αWrite␈α
a␈αpredicate␈αto␈α
tell␈αwhether␈αa␈α
given␈αatom␈α
occurs␈αin␈αa␈α
given␈αS-expression,␈αe.g.␈α
 ␈↓αoccur␈↓↓[␈↓∧B,
␈↓∧((A.B).C)␈↓↓]␈α=␈α␈↓∧T␈↓.
␈↓␈↓ ¬sCHAPTER II␈↓ :22


␈↓        2.␈α
Write␈α
a␈α
predicate␈α
to␈α
tell␈α
how␈α
 many␈α
 times␈α
 a␈α
 given␈α
 atom␈α
occurs␈α
in␈α
an␈α
S-expression.

␈↓        3.␈α∞ Write␈α∞ a␈α∞ function␈α∞to␈α∞make␈α∞a␈α∂list␈α∞without␈α∞duplications␈α∞of␈α∞the␈α∞atoms␈α∞occurring␈α∞in␈α∂an␈α∞S-
␈↓expression.

␈↓        4.␈αWrite␈αa␈α
function␈αto␈αmake␈αa␈α
list␈αof␈αall␈α
 atoms␈α that␈α occur␈αmore␈α
  than␈α  once␈α  in␈α  a␈α
 given
␈↓S-expression␈α
 paired␈α
 with␈α
 their␈α
multiplicities.

␈↓        5.␈αWrite␈αa␈α
predicate␈αto␈αtell␈α
whether␈αan␈αS-expression␈α
has␈αmore␈αthan␈α
one␈αoccurrence␈αof␈αa␈α
given
␈↓S-expression␈α
as␈α
a␈α
sub-expression.



␈↓4.  ␈↓βOther␈α
structural␈α
recursions.␈↓


␈↓        When␈α↔lists␈α_are␈α↔used␈α_to␈α↔represent␈α_algebraic␈α↔expressions,␈α_functions␈α↔of␈α_these␈α↔algebraic
␈↓expressions␈α⊗often␈α⊗have␈α⊗a␈α⊗recursive␈α⊗form␈α⊗closely␈α⊗related␈α⊗to␈α⊗the␈α⊗inductive␈α⊗definition␈α⊗of␈α∃the
␈↓expressions.␈α⊂ Suppose,␈α⊂for␈α⊂example,␈α⊂that␈α⊂sums␈α⊂and␈α⊂products␈α⊂are␈α⊂represented␈α⊂respectively␈α⊂by␈α∂the
␈↓forms␈α ␈↓∧(PLUS␈α
X␈αY)␈↓␈α
 and␈α ␈↓∧(TIMES␈α
X␈αY)␈↓␈α
 and␈αthat␈α
the␈αvalues␈α
of␈αvariables␈α
are␈αgiven␈α
on␈αan␈αa-list.␈α
 We
␈↓can␈α
write␈α
a␈α
recursive␈α
formula␈α
for␈α
the␈α
value␈α
of␈α
an␈α
expression␈α
as␈α
follows:

␈↓        ␈↓αvalue␈↓↓[␈↓αe, a␈↓↓] ← ␈↓βif at ␈↓αe ␈↓βthen d ␈↓αassoc␈↓↓[␈↓αe, a␈↓↓]
␈↓↓␈↓                ␈↓↓␈↓βelse if a ␈↓αe ␈↓βeq ␈↓∧PLUS ␈↓βthen ␈↓αvalue␈↓↓[␈↓βad ␈↓αe, a␈↓↓] + ␈↓αvalue␈↓↓[␈↓βadd ␈↓αe, a␈↓↓]
␈↓↓␈↓                ␈↓↓␈↓βelse if a ␈↓αe ␈↓βeq ␈↓∧TIMES ␈↓βthen ␈↓αvalue␈↓↓[␈↓βad ␈↓αe, a␈↓↓] * ␈↓αvalue␈↓↓[␈↓βadd ␈↓αe, a␈↓↓].

␈↓↓␈↓On␈αthe␈αother␈αhand,␈αsuppose␈αthat␈αsums␈αand␈αproducts␈αare␈αnot␈αrestricted␈αto␈αhave␈αjust␈αtwo␈αarguments;
␈↓then␈α
we␈α
must␈α
use␈α
auxiliary␈α
functions␈α
to␈α
define␈α
the␈α
value␈α
of␈α
an␈α
expression,␈α
as␈α
follows:

␈↓        ␈↓αvalue␈↓↓[␈↓αe, a␈↓↓] ← ␈↓βif at ␈↓αe ␈↓βthen d ␈↓αassoc␈↓↓[␈↓αe, a␈↓↓]
␈↓↓                        ␈↓βelse if a ␈↓αe ␈↓βeq ␈↓∧PLUS ␈↓βthen ␈↓αvplus␈↓↓[␈↓βd ␈↓αe, a␈↓↓]
␈↓↓                        ␈↓βelse if a ␈↓αe ␈↓βeq ␈↓∧TIMES ␈↓βthen ␈↓αvtimes␈↓↓[␈↓βd ␈↓αe, a␈↓↓].

␈↓↓␈↓where

␈↓        ␈↓αvplus␈↓↓[␈↓αu, a␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓∧0 ␈↓βelse ␈↓αvalue␈↓↓[␈↓βa ␈↓αu, a␈↓↓] + ␈↓αvplus␈↓↓[␈↓βd ␈↓αu, a␈↓↓],

␈↓↓␈↓and

␈↓        ␈↓αvtimes␈↓↓[␈↓αu, a␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓∧1 ␈↓βelse ␈↓αvalue␈↓↓[␈↓βa ␈↓αu, a␈↓↓] * ␈↓αvtimes␈↓↓[␈↓βd ␈↓αu, a␈↓↓].

␈↓↓␈↓In␈α
both␈α
cases,␈αthe␈α
recursion␈α
form␈αis␈α
related␈α
to␈αthe␈α
structure␈α
of␈αthe␈α
algebraic␈α
expressions␈αmore␈α
closely
␈↓than␈α
to␈α
the␈α
structure␈α
of␈α
S-expressions␈α
or␈α
lists.
␈↓␈↓ ¬sCHAPTER II␈↓ :23


␈↓5.  ␈↓βTree␈α
search.␈↓


␈↓      We␈α
begin␈α
with␈α
a␈α
general␈α
depth␈α
first␈α
tree␈α
search␈α
function.␈α
 It␈α
can␈α
be␈α
used␈α
to␈α
search␈α
specific␈α
trees
␈↓of␈αpossibilities␈αby␈αdefining␈αthree␈α
auxiliary␈αfunctions␈αin␈αa␈αway␈α
that␈αdepends␈αon␈αthe␈αapplication.␈α
 We
␈↓have

␈↓        ␈↓αsearch p ␈↓↓← ␈↓βif ␈↓αlose p ␈↓βthen ␈↓LOSE
␈↓                         ␈↓βelse if ␈↓αter p ␈↓βthen ␈↓αp ␈↓βelse ␈↓αsearchlis␈↓↓[␈↓αsuccessors p␈↓↓]␈↓

␈↓where


␈↓      ␈↓αsearchlis␈α
u␈α
␈↓↓←␈α
␈↓β␈α
if␈α
n␈α
␈↓αu␈α
␈↓βthen␈α
␈↓LOSE␈α
␈↓βelse␈α␈↓α␈↓↓{␈↓αsearch␈α
␈↓βa␈α
 ␈↓αu␈↓↓}[␈↓αλx␈↓↓:␈↓α␈α
␈↓βif␈α
␈↓αx␈α
␈↓↓=␈α
␈↓LOSE␈α
␈↓βthen␈α
␈↓αsearchlis␈α
␈↓βd␈α
␈↓αu␈α␈↓βelse␈α
␈↓αx␈↓↓]␈↓α.␈↓


␈↓In␈α
the␈α
applications,␈α
we␈α
 start␈α
with␈α
a␈α
position␈α
␈↓αp␈↓¬0␈↓,␈α and␈α
we␈α
are␈α
looking␈α
for␈α
 a␈α
win␈α
in␈α
the␈αsuccessor␈α
tree
␈↓of␈α␈↓αp␈↓¬0␈↓.␈α Certain␈αpositions␈αlose␈αand␈α there␈αis␈α no␈αpoint␈αlooking␈α at␈αtheir␈α successors.␈α This␈α
is␈αdecided
␈↓by␈α
the␈α
predicate␈α
␈↓αlose␈↓.␈α
A␈α
position␈α
 is␈α
a␈α
win␈α
if␈α
it␈α
 doesn't␈α
 lose␈α
 and␈α
 it␈α
 satisfies␈α
 the␈α∞ predicate␈α
␈↓αter␈↓.
␈↓The␈αsuccessors␈αof␈αa␈αposition␈α is␈αgiven␈αby␈α
the␈α function␈α␈↓αsuccessors␈↓,␈αand␈α the␈α value␈α of␈α␈↓αsearch␈α
 p␈↓␈α is
␈↓the␈α⊂ winning␈α⊂position.␈α∂   No␈α⊂non-losing␈α⊂position␈α∂should␈α⊂have␈α⊂the␈α∂ name␈α⊂LOSE␈α⊂or␈α⊂the␈α∂function
␈↓won't␈α
work␈α
properly.

␈↓        Our␈α⊂first␈α⊂example␈α⊂is␈α⊂ finding␈α⊂a␈α⊂path␈α⊂from␈α⊂an␈α⊂ initial␈α⊂node␈α⊂to␈α⊂a␈α⊂final␈α⊂node␈α⊂ in␈α⊂a␈α⊂graph
␈↓represented␈α
by␈α
a␈α
list␈α
structure␈α
as␈α
described␈α
in␈α
chapter␈α
I.␈α
  A␈α
position␈α
is␈α
a␈α
path␈α
 starting␈α
from␈α
the
␈↓initial␈α
 node␈αand␈α
 continuing␈α
to␈α some␈α
intermediate␈α node␈α
and␈α
 is␈αrepresented␈α
 by␈α
a␈αlist␈α
 of␈αits␈α
nodes
␈↓in␈α
reverse␈α
order.␈α
  The␈α
three␈α
 functions␈α
for␈α
this␈α
application␈α
are

␈↓        ␈↓αlose p ␈↓↓← ␈↓βa ␈↓αp ␈↓↓ε ␈↓βd ␈↓αp,

␈↓α␈↓        ␈↓αter p ␈↓↓← [␈↓βa ␈↓αp ␈↓↓=␈↓α final␈↓↓]␈↓α, ␈↓

␈↓and

␈↓        ␈↓αsuccessors p ␈↓↓←␈↓α mapcar␈↓↓[␈↓βd ␈↓αassoc␈↓↓[␈↓βa ␈↓αp, graph␈↓↓]␈↓α, λx␈↓↓:␈↓α x.p␈↓↓]␈↓α.␈↓


␈↓      Another␈αexample␈α
is␈αthe␈α
so-called␈α␈↓αInstant␈α
Insanity␈↓␈αpuzzle.␈α
 There␈αare␈α
four␈αcubical␈α
blocks,␈αand
␈↓each␈αface␈αof␈α
each␈αblock␈αis␈α
colored␈αwith␈αone␈α
of␈αfour␈αcolors.␈α The␈α
object␈αof␈αthe␈α
puzzle␈αis␈αto␈α
build␈αa
␈↓tower␈αof␈αall␈αfour␈αblocks␈αsuch␈αthat␈αeach␈αvertical␈αface␈αof␈αthe␈αtower␈αinvolves␈αall␈αfour␈αcolors.␈α In␈αorder
␈↓to␈α∞use␈α∂the␈α∞above␈α∂defined␈α∞function␈α∂␈↓αsearch␈↓␈α∞for␈α∂this␈α∞purpose,␈α∂we␈α∞must␈α∂define␈α∞the␈α∂representation␈α∞of
␈↓positions␈αand␈αgive␈αthe␈αfunctions␈α␈↓αlose,␈αter,␈α␈↓and␈α␈↓αsuccessors␈↓.␈α A␈αposition␈αis␈αrepresented␈αby␈αa␈αlist␈αof␈αlists
␈↓¬␈α⊂one␈α⊂for␈α⊂each␈α∂face␈α⊂of␈α⊂the␈α⊂tower.␈α∂ Each␈α⊂sublist␈α⊂is␈α⊂the␈α∂list␈α⊂of␈α⊂colors␈α⊂of␈α∂the␈α⊂faces␈α⊂of␈α⊂the␈α∂blocks
␈↓showing␈αin␈α
that␈αface.␈α
 We␈αshall␈αassume␈α
that␈αthe␈α
blocks␈αare␈αdescribed␈α
in␈αthe␈α
following␈αlongwinded
␈↓but␈αconvenient␈αway.␈α (We'll␈αtake␈αup␈αprecomputing␈αthis␈αdescription␈αlater.)␈α For␈αeach␈αblock␈αthere␈αis␈αa
␈↓list␈α∞of␈α
the␈α∞24␈α∞orientations␈α
of␈α∞the␈α
block␈α∞where␈α∞each␈α
orientation␈α∞is␈α
described␈α∞as␈α∞a␈α
list␈α∞of␈α∞the␈α
colors
␈↓around␈αthe␈αvertical␈αfaces␈αof␈αthe␈αblock␈αwhen␈αit␈αis␈αin␈αthat␈αorientation.␈α Thus␈αthe␈αpuzzle␈αis␈αdescribed
␈↓by␈α
a␈α
list␈α
of␈α
lists␈α
of␈α
lists␈α
which␈α
we␈α
shall␈α
call␈α
␈↓αpuzz␈↓.
␈↓␈↓ ¬sCHAPTER II␈↓ :24


␈↓        We now have

␈↓        ␈↓αp␈↓¬0␈↓ ␈↓↓=␈↓ (NIL NIL NIL NIL),

␈↓        ␈↓αlose p ␈↓↓←␈↓α orlis␈↓↓[␈↓αp, λu␈↓↓:␈↓α ␈↓βa ␈↓αu ␈↓↓ε ␈↓βd ␈↓αu␈↓↓]␈↓α,

␈↓α␈↓        ␈↓αter p ␈↓↓← [␈↓αlength ␈↓βa ␈↓αp ␈↓↓=␈↓α 4␈↓↓]␈↓,

␈↓and


␈↓      ␈↓αsuccessors␈α
p␈α
␈↓↓←␈↓α␈α
mapcar␈↓↓[␈↓βa␈α
␈↓αnth␈↓↓[␈↓αpuzz,␈α
1␈α
+␈α
length␈α
␈↓βa␈α
␈↓αp␈↓↓]␈↓α␈α
,␈α
λx␈↓↓:␈↓α␈α
mapcar2␈↓↓[␈↓αp,␈α
x,␈α
λyz␈↓↓:␈↓α␈α
z.y␈↓↓]]␈↓α,␈α
␈↓

␈↓where


␈↓      ␈↓αmapcar2␈↓↓[␈↓αu,␈α
v,␈α
f␈↓↓]␈α
←␈α
␈↓αif␈α
n␈α
u␈α
␈↓βthen␈α
␈↓NIL␈α␈↓βelse␈α
f␈↓↓[␈↓βa␈α
␈↓αu,␈α
␈↓βa␈α
␈↓αv␈↓↓]␈↓α␈α
.␈α
mapcar2␈↓↓[␈↓βd␈α
␈↓αu,␈α
␈↓βd␈α␈↓αv,␈α
f␈↓↓]␈↓α.␈↓


␈↓      Getting␈α
the␈αinitial␈α
position␈α
in␈αthe␈α
desired␈αform␈α
is␈α
as␈αcomplicated␈α
a␈αcomputation␈α
as␈α
the␈αactual
␈↓tree␈α∞search.␈α∞ It␈α∞can␈α∞be␈α∞conveniently␈α∞done␈α∞by␈α∞a␈α∞sequence␈α∞of␈α∞assignment␈α∞statements␈α∞starting␈α∞with␈α
a
␈↓description␈α
of␈α
the␈α
blocks:

␈↓        ␈↓αpuzz1 ␈↓↓← ␈↓((G B B W R G) (G G B G W R) (G W W R B R) (G G R B W W)).


␈↓Here␈αeach␈αblock␈αis␈αrepresented␈αby␈αa␈αlist␈αof␈αthe␈αcolors␈αof␈αthe␈αfaces␈αstarting␈αwith␈αthe␈αtop␈αface,␈αgoing
␈↓around␈α
the␈α
sides␈α
in␈α
a␈α
clockwise␈α
direction␈α
and␈α
finishing␈α
with␈α
the␈α
bottom␈α
face.

␈↓        We␈αneed␈αto␈αgo␈αfrom␈αthis␈αdescription␈αof␈αthe␈αblocks␈αto␈αa␈αlist␈αof␈αthe␈αpossible␈αcycles␈αof␈αcolors␈αon
␈↓the␈α
vertical␈α
faces␈α
for␈αthe␈α
24␈α
orientations␈α
of␈αthe␈α
block.␈α
 This␈α
not␈α
easy,␈αbecause␈α
the␈α
order␈α
in␈αwhich␈α
we
␈↓have␈α
given␈α
the␈α
colors␈α
is␈α
not␈α
invariant␈α
under␈α
rotations␈α
of␈α
the␈α
block.␈α
 An␈α
easy␈α
way␈α
out␈α
is␈α
to␈α
start␈α
with
␈↓a␈α⊂block␈α⊂whose␈α⊂faces␈α⊂are␈α⊃assigned␈α⊂the␈α⊂numbers␈α⊂1␈α⊂thru␈α⊃6␈α⊂starting␈α⊂with␈α⊂the␈α⊂top,␈α⊃going␈α⊂clockwise
␈↓around␈αthe␈αsides␈αand␈α
finishing␈αwith␈αthe␈αbottom.␈α
 We␈αwrite␈αdown␈αone␈α
cycle␈αof␈αside␈αcolors␈α
for␈αeach
␈↓choice␈αof␈αthe␈α
face␈αput␈αon␈α
top␈αand␈αget␈αthe␈α
list␈αof␈αall␈α
24␈αcycles␈αby␈α
appending␈αthe␈αresults␈αof␈α
generating
␈↓the␈α
cyclic␈α
permutations␈α
of␈α
the␈α
cycles.␈α
 All␈α
this␈α
is␈α
accomplished␈α
by␈α
the␈α
assignment



␈↓      ␈↓αpuzz2␈α
␈↓↓←␈↓α␈α
cycles␈↓↓[␈↓(2␈α
3␈α
4␈α
5)␈↓↓]␈↓␈↓↓*␈↓␈↓αcycles␈↓↓[␈↓α(␈↓(2␈α
5␈α
4␈α
3)␈↓↓]␈↓␈↓↓*␈↓␈α
␈↓αcycles␈↓↓[␈↓α(1␈α
2␈α
6␈α
4)␈↓↓]␈↓α
␈↓α                  ␈↓↓*␈↓αcycles␈↓↓[␈↓α(1 4 6 2)␈↓↓]␈↓α␈↓↓*␈↓αcycles␈↓↓[␈↓α(1 3 6 5)␈↓↓]␈↓α␈↓↓*␈↓αcycles␈↓↓[␈↓α(1 5 6 3)␈↓↓]␈↓α, ␈↓

␈↓where the function ␈↓αcycles␈↓ is defined by

␈↓        ␈↓αcycles u ␈↓↓←␈↓α maplist␈↓↓[␈↓αu, λx␈↓↓:␈↓α x␈↓↓*␈↓αupto␈↓↓[␈↓αu, x␈↓↓]]␈↓

␈↓with the auxiliary function
␈↓␈↓ ¬sCHAPTER II␈↓ :25


␈↓      ␈↓αupto␈↓↓[␈↓αu,␈α
x␈↓↓]␈α
←␈α
␈↓βif␈α
␈↓αx␈α
␈↓βeq␈α
␈↓αu␈α␈↓βthen␈α
␈↓NIL␈α
␈↓βelse␈α
a␈α
 ␈↓αu␈α
.␈α
upto␈↓↓[␈↓βd␈α␈↓αu,␈α
x␈↓↓]␈↓α.␈↓


␈↓Next␈α
we␈α
create␈α
for␈α
each␈αblock␈α
a␈α
list␈α
of␈α
substitutions␈α
expressing␈αthe␈α
colors␈α
of␈α
the␈α
six␈αnumbered␈α
faces.
␈↓We␈α
have

␈↓        ␈↓αpuzz3 ␈↓↓←␈↓α mapcar␈↓↓[␈↓αpuzz1, λx␈↓↓:␈↓α prup␈↓↓[␈↓(1 2 3 4 5 6), ␈↓αx␈↓↓]]␈↓α, ␈↓


␈↓and␈α
we␈α
use␈α
these␈α
substitutions␈α
to␈α
get␈α
for␈α
each␈α
block␈α
the␈α
list␈α
of␈α
24␈α
orientations␈α
of␈α
the␈α
block.␈α
Thus

␈↓        ␈↓αpuzz4 ␈↓↓←␈↓α mapcar␈↓↓[␈↓αpuzz3, λs␈↓↓:␈↓α sublis␈↓↓[␈↓αs, puzz3␈↓↓]]␈↓α.


␈↓αpuzz4␈↓␈α
has␈αall␈α
24␈α
orientations␈αof␈α
the␈α
first␈αblock␈α
while␈αfor␈α
symmetry␈α
reasons␈αwe␈α
need␈α
only␈αconsider
␈↓three␈α
as␈α
distinct,␈α
say␈α
the␈α
first,␈α
ninth,␈α
and␈α
seventeen.␈α
 So␈α
we␈α
finally␈α
get


␈↓      ␈↓αpuzz␈α
␈↓↓←␈↓α␈α
(␈↓βa␈α
␈↓αnth␈↓↓[␈↓βa␈α
␈↓αpuzz4,␈α
1␈↓↓]␈α
␈↓βa␈α
␈↓αnth␈↓↓[␈↓βa␈α
␈↓αpuzz4,␈α
9␈↓↓]␈↓α␈α
␈↓βa␈α
␈↓αnth␈↓↓[␈↓βa␈α
␈↓αpuzz4,␈α
17␈↓↓]␈↓α)␈α
.␈α␈↓βd␈α
␈↓αpuzz4.␈↓


␈↓The␈α
program␈α
when␈α
compiled␈α
runs␈α
about␈α
11␈α
seconds␈α
on␈α
the␈α
PDP-10.

␈↓        A␈α
more␈α∞sophisticated␈α
representation␈α∞of␈α
face␈α∞cycles␈α
and␈α
partial␈α∞towers␈α
makes␈α∞a␈α
factor␈α∞of␈α
ten
␈↓speedup␈α
without␈αchanging␈α
the␈α
basic␈αsearch␈α
algorithm.␈α
 A␈αface␈α
cycle␈αis␈α
represented␈α
by␈α16␈α
bits␈α
in␈αa
␈↓word␈αfour␈αfor␈αeach␈αface␈αa␈α
particular␈αone␈αof␈αwhich␈αbeing␈αturned␈αon␈α
tells␈αus␈αthe␈αcolor␈αof␈αthe␈αface.␈α
 If
␈↓we␈α␈↓βor␈↓␈αthese␈αwords␈αtogether␈αfor␈αthe␈αblocks␈αin␈αa␈αpartial␈αtower␈αwe␈αget␈αa␈αword␈αwhich␈αtells␈αus␈αfor␈αeach
␈↓face␈αof␈αthe␈αtower␈αwhat␈αcolors␈αhave␈αbeen␈α
used.␈α A␈αparticular␈αface␈αcycle␈αfrom␈αthe␈αnext␈αblock␈α
can␈αbe
␈↓added␈α⊂to␈α⊂the␈α⊂tower␈α⊂if␈α⊃the␈α⊂␈↓βand␈↓␈α⊂of␈α⊂its␈α⊂word␈α⊂with␈α⊃the␈α⊂word␈α⊂representing␈α⊂the␈α⊂tower␈α⊂is␈α⊃zero.␈α⊂ We
␈↓represent␈αa␈αposition␈αby␈αa␈αlist␈αof␈αwords␈αrepresenting␈αits␈αpartial␈αtowers␈αwith␈α0␈αas␈αthe␈αlast␈αelement␈α
and
␈↓the␈αhighest␈αpartial␈αtower␈α
as␈αthe␈αfirst␈αelement.␈α
 The␈αvirtue␈αof␈αthis␈α
representation␈αis␈αthat␈αit␈αmakes␈α
the
␈↓description␈αof␈αthe␈αalgorithm␈αshort.␈α The␈αinitial␈αposition␈αis␈α(0).␈α The␈αnew␈α␈↓αpuzz␈↓␈αcan␈αbe␈αformed␈αfrom
␈↓the␈α
old␈α
one␈α
by␈α
the␈α
assignment

␈↓        ␈↓αpuzza ␈↓↓←␈↓α mapcar␈↓↓[␈↓αpuzz, λx␈↓↓:␈↓α mapcar␈↓↓[␈↓αx, zap␈↓↓]]␈↓α, ␈↓

␈↓where


␈↓      ␈↓αzap␈α
v␈α
␈↓↓←␈α
␈↓βif␈α
n␈α
␈↓αv␈α
␈↓βthen␈α
␈↓α0␈α
␈↓βelse␈α
␈↓αpoo␈α
␈↓βa␈α
␈↓αv␈α
+␈α
16zap␈α
␈↓βd␈α␈↓αv,␈α
␈↓

␈↓and


␈↓      ␈↓αpoo␈α
x␈α
␈↓↓←␈α
␈↓βif␈α
␈↓αx␈↓↓=␈↓R␈α
␈↓βthen␈α
␈↓α1␈α
␈↓βelse␈α
if␈α
␈↓αx␈↓↓=␈↓W␈α
␈↓βthen␈α
 ␈↓2␈α
␈↓βelse␈α
if␈α
␈↓αx␈↓↓=␈↓G␈α
␈↓βthen␈α
␈↓4␈α␈↓βelse␈α
␈↓8.


␈↓Now␈α
we␈α
need␈α
the␈α
new␈α
functions␈α
␈↓αlose,␈α
ter,␈α
␈↓and␈α
␈↓αsuccessors␈↓.␈α
 These␈α
are
␈↓␈↓ ¬sCHAPTER II␈↓ :26


␈↓        ␈↓αlose p ␈↓↓← ␈↓βfalse␈↓α,

␈↓α␈↓        ␈↓αter p ␈↓↓← [␈↓αlength p ␈↓↓=␈↓α 5␈↓↓]␈↓α, ␈↓

␈↓and


␈↓      ␈↓αsuccessors␈α
p␈α
␈↓↓←␈↓α␈α
mapchoose␈↓↓[␈↓βa␈α
␈↓αnth␈↓↓[␈↓αpuzza,␈α
length␈α
p␈↓↓]␈↓α,␈α
λx␈↓↓:␈↓α␈α
␈↓βa␈α
␈↓αp␈α
␈↓βand␈α
␈↓αx␈α
␈↓↓=␈↓α␈α
0,␈α
λx␈↓↓:␈↓α␈α
␈↓↓[␈↓βa␈α
␈↓αp␈α
␈↓βor␈α
␈↓αx␈↓↓]␈↓α␈α
.␈α
p␈↓↓]␈↓α.␈↓

␈↓where

␈↓        ␈↓αmapchoose␈↓↓[␈↓αu, pred, fn␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓NIL

␈↓              ␈↓βelse␈α
if␈α
␈↓αpred␈α
␈↓βa␈α
␈↓αu␈α
␈↓βthen␈α
␈↓αfn␈↓↓[␈↓βa␈α
␈↓αu␈↓↓]␈↓α␈α
.␈α
mapchoose␈↓↓[␈↓βd␈α
␈↓αu␈α
,␈α
pred,␈αfn␈↓↓]␈α
␈↓β
␈↓β␈↓                ␈↓βelse ␈↓αmapchoose␈↓↓[␈↓βd ␈↓αu, pred, fn␈↓↓]␈↓α.␈↓


␈↓␈↓αlose␈↓␈α
is␈α∞trivial,␈α
because␈α
the␈α∞␈↓αmapchoose␈↓␈α
is␈α∞used␈α
to␈α
make␈α∞sure␈α
that␈α
only␈α∞non-losing␈α
new␈α∞positions␈α
are
␈↓generated␈α⊂by␈α∂␈↓αsuccessors␈↓.␈α⊂ This␈α∂version␈α⊂runs␈α∂in␈α⊂a␈α⊂little␈α∂less␈α⊂than␈α∂one␈α⊂second␈α∂on␈α⊂the␈α⊂PDP-10.␈α∂ A
␈↓greater␈α∩speedup␈α∩can␈α⊃be␈α∩made␈α∩by␈α∩the␈α⊃application␈α∩of␈α∩some␈α⊃mathematics.␈α∩ In␈α∩fact,␈α∩with␈α⊃enough
␈↓mathematics,␈α
extensive␈α
tree␈α
search␈α
is␈α
unnecessary␈α
in␈α
this␈α
problem.

␈↓        ␈↓αsearch␈↓␈α∂is␈α∂used␈α∞when␈α∂we␈α∂want␈α∞to␈α∂search␈α∂a␈α∂tree␈α∞of␈α∂possibilities␈α∂for␈α∞a␈α∂solution␈α∂to␈α∂a␈α∞problem.
␈↓What␈αif␈αwe␈αwant␈αto␈αfind␈αall␈αsolutions␈αto␈αa␈αproblem?␈α This␈αcan␈αbe␈αdone␈αwith␈αa␈αfunction␈α␈↓αallsol␈↓␈αthat
␈↓uses␈α
the␈α
same␈α
␈↓αlose,␈α
ter,␈α
␈↓and␈α
␈↓αsuccessors␈↓␈α
functions␈α
as␈α
does␈α
␈↓αsearch␈↓.␈α
 The␈α
simplest␈α
way␈α
to␈α
write␈α
␈↓αallsol␈↓␈α
is


␈↓      ␈↓αallsol␈α
p␈α
␈↓↓←␈α
␈↓βif␈α
␈↓αlose␈α
p␈α
␈↓βthen␈α
␈↓NIL␈α
␈↓βelse␈α
if␈α
␈↓αter␈α
p␈α
 ␈↓βthen␈α
␈↓α(p)␈α
␈↓βelse␈α
␈↓αmapapp␈↓↓[␈↓αsuccessors␈α
p,␈αallsol␈↓↓]␈↓α,␈α
␈↓

␈↓where

␈↓      ␈↓αmapapp␈↓↓[␈↓αu,␈α
fn␈↓↓]␈α
←␈α
␈↓βif␈α
n␈α
␈↓αu␈α␈↓βthen␈α
␈↓NIL␈α
␈↓βelse␈α
␈↓αfn␈↓↓[␈↓βa␈α
␈↓αu␈↓↓]␈↓α␈α
.␈α
mappap␈↓↓[␈↓βd␈α␈↓αu,␈α
fn␈↓↓]␈↓α.␈↓


␈↓This␈αform␈α
of␈αthe␈α
function␈αis␈αsomewhat␈α
inefficient␈αbecause␈α
of␈αall␈αthe␈α
␈↓αappend␈↓ing.␈α A␈α
more␈αefficient
␈↓form␈α
uses␈α
an␈α
auxiliary␈α
function␈α
as␈α
follows:

␈↓        ␈↓αallsol p ␈↓↓←␈↓α allsola␈↓↓[␈↓αp, ␈↓NIL␈↓↓]␈↓

␈↓        ␈↓αallsola␈↓↓[␈↓αp, found␈↓↓] ← ␈↓βif ␈↓αlose p ␈↓βthen ␈↓αfound
␈↓α                                        ␈↓βelse if ␈↓αter p ␈↓βthen ␈↓αp . found
␈↓α                                        ␈↓βelse ␈↓αallsolb␈↓↓[␈↓αsuccessors p, found␈↓↓]␈↓α,


␈↓α      allsolb␈↓↓[␈↓αu,␈α
found␈↓↓]␈α
←␈α
␈↓βif␈α
n␈α
␈↓αu␈α␈↓βthen␈α
␈↓αfound␈α
␈↓βelse␈α
␈↓αallsolb␈↓↓[␈↓βd␈α
␈↓αu,␈α
allsola␈↓↓[␈↓βa␈α␈↓αu,␈α
found␈↓↓]]␈↓α.␈↓
␈↓␈↓ ¬sCHAPTER II␈↓ :27


␈↓The␈α∩recursive␈α⊃program␈α∩structure␈α⊃that␈α∩arises␈α⊃here␈α∩is␈α∩common␈α⊃when␈α∩a␈α⊃list␈α∩is␈α⊃to␈α∩be␈α∩formed␈α⊃by
␈↓recurring␈α
through␈α
a␈α
list␈α
structure.



␈↓6.  ␈↓βGame␈α
trees.␈↓


␈↓      The␈α∂positions␈α∂that␈α⊂can␈α∂be␈α∂reached␈α⊂from␈α∂an␈α∂initial␈α⊂position␈α∂in␈α∂a␈α⊂ game␈α∂ form␈α∂ a␈α⊂ tree,␈α∂and
␈↓deciding␈αwhat␈αmove␈αto␈αmake␈αoften␈αinvolves␈αsearching␈αthis␈αtree.␈α However,␈αgame␈αtrees␈αare␈αsearched
␈↓in␈αa␈αdifferent␈αway␈α than␈αthe␈αtrees␈αwe␈αhave␈αlooked␈αat,␈αbecause␈αthe␈αopposing␈αinterests␈αof␈αthe␈αplayers
␈↓makes␈α
it␈α
not␈αa␈α
search␈α
for␈α
a␈αjoint␈α
line␈α
 of␈α
 play␈α that␈α
will␈α
 lead␈α
 to␈α the␈α
 first␈α
 player␈α
winning,␈αbut
␈↓rather␈α
a␈α
search␈α
for␈α
a␈α
strategy␈α
that␈α
will␈α
lead␈α
to␈α
a␈α
win␈α
regardless␈α
of␈α
what␈α
the␈α
other␈α
 player␈α
does.

␈↓        The␈α  simplest␈α situation␈α is␈α characterized␈α by␈α a␈α function␈α␈↓αsuccessors␈↓␈αthat␈αgives␈αthe␈αpositions
␈↓that␈αcan␈αbe␈αreached␈αin␈α one␈αmove,␈α a␈α predicate␈α ␈↓αter␈↓␈α that␈α tells␈α when␈αa␈αposition␈αis␈αto␈αbe␈αregarded
␈↓as␈α_ terminal␈α↔ for␈α_ the␈α_ given␈α↔ analysis,␈α_ and␈α↔ a␈α_  function␈α_␈↓αimval␈↓␈α↔ that␈α_ gives␈α_ a␈α↔ number
␈↓approximating␈α the␈α value␈α of␈αthe␈α
position␈αto␈αone␈αof␈αthe␈α
 players.␈α  We␈α shall␈α call␈α this␈α player␈α
 the
␈↓maximizing␈α player␈α and␈α his␈αopponent␈αthe␈αminimizing␈αplayer.␈αUsually,␈αthe␈αnumerical␈αvalues␈αarise,
␈↓because␈α∂the␈α⊂search␈α∂cannot␈α⊂be␈α∂carried␈α∂ out␈α⊂to␈α∂the␈α⊂end␈α∂of␈α∂the␈α⊂game,␈α∂and␈α⊂the␈α∂analysis␈α⊂stops␈α∂with
␈↓reasonably␈αstatic␈α
positions␈αthat␈α can␈α
 be␈α evaluated␈α
 by␈α some␈α rule.␈α
  Naturally,␈α the␈αfunction␈α
 ␈↓αimval␈↓
␈↓is␈α
 chosen␈α to␈α
 be␈α
 easy␈α to␈α
 calculate␈αand␈α
to␈α
correlate␈αwell␈α
with␈α
the␈αprobability␈α
that␈αthe␈α
 maximizing
␈↓player␈α
 can␈α
win␈α
the␈α
position.

␈↓        The␈αsimplest␈αrule␈αfor␈αfinding␈αthe␈αcorrect␈αmove␈αin␈αa␈αposition␈αuses␈αauxiliary␈αfunctions␈α␈↓αvalmax␈↓
␈↓and␈α␈↓αvalmin␈↓␈α
that␈αgive␈αa␈α
value␈αto␈αa␈α
position␈αby␈α
using␈α␈↓αimval␈↓␈αif␈α
the␈αposition␈αis␈α
terminal␈αand␈αtaking␈α
the
␈↓max␈α
or␈α
min␈α
of␈α
the␈α
successor␈α
positions␈α
otherwise.

␈↓        For␈αthis␈αwe␈αwant␈αfunctions␈αfor␈αgetting␈αthe␈αmaximum␈αor␈αthe␈αminimum␈αof␈αa␈αfunction␈αon␈αa␈α
list,
␈↓and␈α
they␈α
are␈α
defined␈α
as␈α
follows:


␈↓      ␈↓αmaxlis␈↓↓[␈↓αu,␈α
f␈↓↓]␈α
←␈α
␈↓βif␈α
n␈α
␈↓αu␈α
␈↓βthen␈α␈↓α-␈↓↓∞␈↓α␈α
␈↓βelse␈α
␈↓α␈α
max␈↓↓[␈↓αf␈↓↓[␈↓βa␈α
␈↓αu␈↓↓]␈↓α,␈α
maxlis␈↓↓[␈↓βd␈α
␈↓αu,␈αf␈↓↓]]␈↓α,␈α
␈↓

␈↓and


␈↓      ␈↓αminlis␈↓↓[␈↓αu,␈α
f␈↓↓]␈α
←␈α
␈↓βif␈α
n␈α
␈↓αu␈α␈↓βthen␈α
␈↓α␈↓↓∞␈↓α␈α
␈↓βelse␈α
␈↓α␈α
min␈↓↓[␈↓αf␈↓↓[␈↓βa␈α
␈↓αu␈↓↓]␈↓α,␈α
minlis␈↓↓[␈↓βd␈α␈↓αu,␈α
f␈↓↓]]␈↓α.␈↓


␈↓In␈αthese␈α
functions,␈α-␈↓↓∞␈↓␈αand␈α
␈↓↓∞␈↓␈αrepresent␈αnumbers␈α
that␈αare␈α
smaller␈αand␈αlarger␈α
than␈αany␈αactual␈α
values
␈↓that␈αwill␈α
occur␈αin␈α
evaluating␈α␈↓αf␈↓.␈α
 If␈αthese␈α
numbers␈αare␈α
not␈αavailable,␈α
then␈αit␈α
is␈αnecessary␈α
to␈αprime␈α
the
␈↓function␈α∩with␈α∩the␈α∩values␈α∩of␈α∩␈↓αf␈↓␈α∩applied␈α∩to␈α∪the␈α∩first␈α∩element␈α∩of␈α∩the␈α∩list,␈α∩and␈α∩the␈α∪functions␈α∩are
␈↓meaningless␈αfor␈αnull␈αlists.␈α Iterative␈αversions␈αof␈αthe␈αfunctions␈αare␈αgenerally␈αbetter;␈αwe␈αgive␈αonly␈αthe
␈↓iterative␈α
version␈α
of␈α
␈↓αmaxlis␈↓,␈α
namely

␈↓        ␈↓αmaxlis␈↓↓[␈↓αu, f␈↓↓] ←␈↓α maxlisa␈↓↓[␈↓αu, -␈↓↓∞␈↓α, f␈↓↓]␈↓α, ␈↓
␈↓␈↓ ¬sCHAPTER II␈↓ :28


␈↓where


␈↓      ␈↓αmaxlisa␈↓↓[␈↓αu,␈α
x,␈α
f␈↓↓]␈α
←␈α
␈↓αif␈α
n␈α
u␈α␈↓βthen␈α
␈↓αx␈α
␈↓βelse␈α
␈↓αmaxlisa␈↓↓[␈↓βd␈α
␈↓αu,␈α
max␈↓↓[␈↓αx,␈α
f␈↓↓[␈↓βa␈α␈↓αu␈↓↓]]␈↓α,␈α
f␈↓↓]␈↓α.␈↓

␈↓We now have


␈↓      ␈↓αvalmax␈α
p␈α
␈↓↓←␈α
␈↓βif␈α
␈↓αter␈α
p␈α
␈↓βthen␈α
␈↓αimval␈α
p␈α
␈↓βelse␈α
␈↓αmaxlis␈↓↓[␈↓αsuccessors␈αp,␈α
valmin␈↓↓]␈↓,

␈↓and


␈↓      ␈↓αvalmin␈α
p␈α
␈↓↓←␈α
␈↓βif␈α
␈↓αter␈α
p␈α
␈↓βthen␈α
␈↓αimval␈α
p␈α
␈↓βelse␈α
␈↓αminlis␈↓↓[␈↓αsuccessors␈αp,␈α
valmax␈↓↓]␈↓.

␈↓The best move is now chosen by

␈↓        ␈↓αmovemax p ␈↓↓←␈↓α bestmax␈↓↓[␈↓αsuccesors p, valmin␈↓↓]␈↓α, ␈↓

␈↓or

␈↓        ␈↓αmovemin p ␈↓↓←␈↓α bestmin␈↓↓[␈↓αsuccesors p, valmax␈↓↓]␈↓α, ␈↓

␈↓where

␈↓        ␈↓αbestmax␈↓↓[␈↓αu, f␈↓↓] ←␈↓α bestmaxa␈↓↓[␈↓βd ␈↓αu, ␈↓βa ␈↓αu, f␈↓↓[␈↓βa ␈↓αu␈↓↓]␈↓α, f␈↓↓]␈↓α,

␈↓α␈↓        ␈↓αbestmaxa␈↓↓[␈↓αu, sofar, valsofar, f␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓αsofar

␈↓α              ␈↓βelse␈α
if␈α
␈↓αf␈↓↓[␈↓βa␈α
␈↓αu␈↓↓]␈α
≤␈α␈↓αbestsofar␈α
␈↓βthen␈α
␈↓αbestmaxa␈↓↓[␈↓βd␈α
␈↓αu,␈α
sofar,␈αbestsofar,␈α
f␈↓↓]␈↓α
␈↓α␈↓                ␈↓α␈↓βelse ␈↓αbestmaxa␈↓↓[␈↓βd ␈↓αu, ␈↓βa ␈↓αu, f␈↓↓[␈↓βa ␈↓αu␈↓↓]␈↓α, f␈↓↓]␈↓α,

␈↓α␈↓        ␈↓αbestmin␈↓↓[␈↓αu, f␈↓↓] ←␈↓α bestmina␈↓↓[␈↓βd ␈↓αu, ␈↓βa ␈↓αu, f␈↓↓[␈↓βa ␈↓αu␈↓↓]␈↓α, f␈↓↓]␈↓α, ␈↓

␈↓and

␈↓        ␈↓αbestmina␈↓↓[␈↓αu, sofar, valsofar, f␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓αsofar

␈↓α              ␈↓βelse␈α
if␈α
␈↓αf␈↓↓[␈↓βa␈α
␈↓αu␈↓↓]␈α
≥␈α␈↓αbestsofar␈α
␈↓βthen␈α
␈↓αbestmina␈↓↓[␈↓βd␈α
␈↓αu,␈α
sofar,␈αbestsofar,␈α
f␈↓↓]␈↓α
␈↓α␈↓                ␈↓α␈↓βelse ␈↓αbestmina␈↓↓[␈↓βd ␈↓αu, ␈↓βa ␈↓αu, f␈↓↓[␈↓βa ␈↓αu␈↓↓]␈↓α, f␈↓↓]␈↓α.␈↓


␈↓      However,␈α
this␈α
straight␈αminimax␈α
computation␈α
of␈αthe␈α
best␈α
move␈αdoes␈α
much␈α
more␈αcomputation␈α
in
␈↓general␈α
than␈α
is␈α
usually␈α
necessary.␈α
 The␈α
simplest␈α
way␈α
to␈α
see␈α
this␈α
is␈α
from␈α
the␈α
move␈α
tree␈α
of␈α
Figure␈α
2.6.
␈↓␈↓ ¬sCHAPTER II␈↓ :29













␈↓␈↓ ε∂Figure 2.6

␈↓We␈α
see␈αfrom␈α
this␈α
figure␈αthat␈α
it␈α
is␈αunnecessary␈α
to␈α
examine␈αthe␈α
moves␈α
marked␈αx,␈α
because␈αtheir␈α
values
␈↓have␈α∂no␈α∞effect␈α∂on␈α∂the␈α∞value␈α∂of␈α∂the␈α∞game␈α∂or␈α∂on␈α∞the␈α∂correct␈α∂move␈α∞since␈α∂the␈α∂presence␈α∞of␈α∂the␈α∂9␈α∞is
␈↓sufficient␈αinformation␈α
at␈αthis␈α
point␈αto␈α
show␈αthat␈αthe␈α
move␈αleading␈α
to␈αthe␈α
vertex␈αpreceding␈αit␈α
should
␈↓not␈α
be␈α
chosen␈α
by␈α
the␈α
minimizing␈α
player.

␈↓        The␈αgeneral␈αsituation␈αis␈αthat␈αit␈αis␈αunnecessary␈αto␈αexamine␈αfurther␈αmoves␈αin␈αa␈αposition␈αonce␈αa
␈↓move␈α
is␈α∞found␈α
that␈α∞refutes␈α
moving␈α∞to␈α
the␈α∞position␈α
in␈α
the␈α∞first␈α
place.␈α∞ This␈α
idea␈α∞is␈α
called␈α∞the␈α
αβ-
␈↓heuristic␈α
and␈α
expressed␈α
in␈α
the␈α
following␈α
recursive␈α
definitions:

␈↓        ␈↓αmaxval p ␈↓↓←␈↓α maxval1␈↓↓[␈↓αp, -␈↓↓∞␈↓α, ␈↓↓∞␈↓α␈↓↓]␈↓α,


␈↓α        maxval1␈↓↓[␈↓αp,␈α
α,␈α
β␈↓↓]␈α
←␈α
␈↓βif␈α
␈↓αter␈α
p␈α␈↓βthen␈α
␈↓αmax␈↓↓[␈↓αα,␈α
min␈↓↓[␈↓αβ,␈α
imval␈α
p␈↓↓]]␈↓α␈α
 ␈↓βelse␈α
␈↓αmaxval2␈↓↓[␈↓αsuccessors␈α
p,␈αα,␈α
β␈↓↓]␈↓α,


␈↓α        maxval2␈↓↓[␈↓αu,␈α
α,␈α
β␈↓↓]␈α
←␈α
{␈↓αminval1␈↓↓[␈↓βa␈α
␈↓αu,␈α
α,␈α
β␈↓↓]}[␈↓αλw␈↓↓:␈↓α␈α␈↓βif␈α
␈↓αw␈α
␈↓↓=␈↓α␈α
β␈α
␈↓βthen␈α
 ␈↓αβ␈α
␈↓βelse␈α
␈↓αmaxval2␈↓↓[␈↓βd␈α
␈↓αu,␈αw,␈α
β␈↓↓]]␈↓α,

␈↓α␈↓        ␈↓αminval p ␈↓↓←␈↓α minval1␈↓↓[␈↓αp, -␈↓↓∞␈↓α, ␈↓↓∞␈↓α␈↓↓]␈↓α,


␈↓α        minval1␈↓↓[␈↓αp,␈α
α,␈α
β␈↓↓]␈α
←␈α
␈↓βif␈α
␈↓αter␈α
p␈α␈↓βthen␈α
␈↓αmax␈↓↓[␈↓αα,␈α
min␈↓↓[␈↓αβ,␈α
imval␈α
p␈↓↓]]␈↓α␈α
 ␈↓βelse␈α
␈↓αminval2␈↓↓[␈↓αsuccessors␈α
p,␈αα,␈α
β␈↓↓]␈↓α,


␈↓α        minval2␈↓↓[␈↓αu,␈α
α,␈α
β␈↓↓]␈α
←␈α
{␈↓αmaxval1␈↓↓[␈↓βa␈α
␈↓αu,␈α
α,␈α
β␈↓↓]}[␈↓αλw␈↓↓:␈↓α␈α␈↓βif␈α
␈↓αw␈α
␈↓↓=␈↓α␈α
α␈α
␈↓βthen␈α
 ␈↓αα␈α
␈↓βelse␈α
␈↓αminval2␈↓↓[␈↓βd␈α
␈↓αu,␈αα,␈α
w␈↓↓]␈↓α.␈↓


␈↓      The␈α∞reduction␈α∞in␈α∞number␈α
of␈α∞positions␈α∞examined␈α∞given␈α∞by␈α
the␈α∞αβ␈α∞algorithm␈α∞over␈α∞the␈α
simple
␈↓minimax␈αalgorithm␈αdepends␈αon␈α
the␈αorder␈αin␈αwhich␈α
the␈αmoves␈αare␈αexamined.␈α
 In␈αthe␈αworst␈αcase,␈α
the
␈↓moves␈αhappen␈αto␈αbe␈αexamined␈αin␈αinverse␈αorder␈αof␈α
merit␈αin␈αevery␈αposition␈αon␈αthe␈αtree,␈αi.e.␈αthe␈α
worst
␈↓move␈α
first.␈α
 In␈α
that␈αcase,␈α
there␈α
is␈α
no␈αimprovement␈α
over␈α
minimax.␈α
 The␈α
best␈αcase␈α
is␈α
the␈α
one␈αin␈α
which
␈↓the␈α
best␈α
move␈α
in␈α
every␈α
position␈αis␈α
examined␈α
first.␈α
 If␈α
we␈α
look␈α
␈↓αn␈↓␈αmoves␈α
deep␈α
on␈α
a␈α
tree␈α
that␈α
has␈α␈↓αk␈↓
␈↓successors␈α
to␈α
each␈α
position,␈α
then␈α∞minimax␈α
looks␈α
at␈α
␈↓αk␈↓εn␈↓␈α
positions␈α∞while␈α
αβ␈α
looks␈α
at␈α
about␈α∞only␈α
␈↓αk␈↓εn/2␈↓.
␈↓Thus␈α
a␈α
program␈α
that␈α
looks␈α
at␈α
10␈↓ε4␈↓␈α
moves␈α
with␈α
αβ␈α
might␈α
have␈α
to␈α
look␈α
at␈α
10␈↓ε8␈↓␈α
with␈α
minimax.␈α
 For
␈↓this␈α
reason,␈α
game␈α
playing␈αprograms␈α
using␈α
αβ␈α
make␈αa␈α
big␈α
effort␈α
to␈αinclude␈α
as␈α
good␈α
as␈α
possible␈αan
␈↓␈↓ ¬sCHAPTER II␈↓ :30


␈↓ordering␈α
of␈αmoves␈α
into␈α
the␈α␈↓αsuccessors␈↓␈α
function.␈α
 When␈αthere␈α
is␈α
a␈αdeep␈α
tree␈α
search␈αto␈α
be␈α
done,␈αthe
␈↓way␈α
to␈α
make␈α
the␈α
ordering␈α
is␈α
with␈α
a␈α
short␈α
look-ahead␈α
to␈α
a␈α
much␈α
smaller␈α
depth␈α
than␈α
the␈α
main␈α
search.
␈↓Still␈α
shorter␈α
look-aheads␈αare␈α
used␈α
deeper␈α
in␈αthe␈α
tree,␈α
and␈αbeyond␈α
a␈α
certain␈α
depth,␈αnon-look-ahead
␈↓ordering␈α
methods␈α
are␈α
of␈α
decreasing␈α
complexity.

␈↓        A␈α∂version␈α∂of␈α∞αβ␈α∂incorporating␈α∂optimistic␈α∞and␈α∂pessimistic␈α∂evaluations␈α∞of␈α∂positions␈α∂was␈α∞first
␈↓proposed␈α⊂by␈α⊂McCarthy␈α⊂about␈α⊂1958.␈α⊂ Edwards␈α⊂and␈α⊂Hart␈α⊂at␈α⊂M.I.T.␈α⊂about␈α⊂1959␈α⊂proved␈α⊃that␈α⊂the
␈↓present␈α∂version␈α⊂of␈α∂αβ␈α∂works␈α⊂and␈α∂calculated␈α∂the␈α⊂improvement␈α∂it␈α∂gives␈α⊂over␈α∂minimax.␈α⊂ The␈α∂first
␈↓publication,␈α
however,␈α
was␈α
Brudno␈α
(1963).␈α
 It␈α
is␈α
worth␈α
noting␈α
that␈α
αβ␈α
was␈α
not␈α
used␈α
in␈α
the␈α
early␈α
chess
␈↓playing␈α⊃programs␈α⊃in␈α⊂spite␈α⊃of␈α⊃the␈α⊂fact␈α⊃that␈α⊃it␈α⊃is␈α⊂clearly␈α⊃used␈α⊃in␈α⊂any␈α⊃human␈α⊃play.␈α⊃ Its␈α⊂non-use,
␈↓therefore,␈α∪represents␈α∪a␈α∀failure␈α∪of␈α∪self-observation.␈α∀ Very␈α∪likely,␈α∪there␈α∀are␈α∪a␈α∪number␈α∀of␈α∪other
␈↓algorithms␈αused␈αin␈αhuman␈αthought␈αthat␈αwe␈α
have␈αnot␈αnoticed␈αan␈αincorporated␈αin␈αour␈αprograms.␈α
 To
␈↓the␈αextent␈α
that␈αthis␈α
is␈αso,␈α
artificial␈αintelligence␈α
will␈αbe␈α
␈↓αa␈αposteriori␈↓␈α
obvious␈αeven␈α
though␈αit␈α
is␈α␈↓αa␈α
priori␈↓
␈↓very␈α
difficult.