Limits of
Computation
10 – Partial evaluation & self-referencing programs Bernhard Reus
1
So far …
• … we have seen how programs can be encoded as objects to be used as input to other programs.
• Example: self-interpreter to show semi- decidability of Halting Problem.
2
Question:
Can we write a Java program that prints itself or a While program that returns its own AST (without using its input)?
3
•Other uses of programs-as-data
public class Quine {
public static void main(String[] args) {
char q = 34; // Quotation mark character String[] l = { // Array of source code “public class Quine”,
“{“,
Partial Evaluation (Kleene’s
S-m-n Theorem)
•
” public static void
” {“,
” charq=34;
” String[] l = {
” “,
main(String[] args)”,
// Quotation mark character”, // Array of source code”,
Use of partial evaluation for Optimisation and Compiler Generation
” };”,
” for(inti=0;i < 6; i++)
" System.out.println(l[i]);",
" for(int i = 0; i < l.length; i++)
" System.out.println(l[6] + q + l[i] + q + ',');",
•
Recursion Theorem)
// Print opening code", // Print string array", // Print this code",
Self-referencing Programs (Kleene’s
" for(int i = 7; i < l.length; i++)
" System.out.println(l[i]);",
" }", "}",
•
Use of Recursion Theorem for Recursion
};
for(int i = 0; i < 6; i++)
System.out.println(l[i]); for(int i = 0; i < l.length; i++)
// Print opening code
// Print string array
System.out.println(l[6] + q + l[i] + q + ',');
for(int i = 7; i < l.length; i++) System.out.println(l[i]);
} }
// Print this code
an interesting Java program: what does it do?
4
THIS TIME
cations in its own right:
10.1 The S-m-n Theorem
The so-called “S-m-n” theorem, sometimes also called parameterization theorem,
can be regarded as justification for partial evaluation as an optimisation technique.
The reasons for the strange name will be explained soon. In terms of metaprogram-
Simple Version of S-m-n Theorem
ming (i.e. programming with programs) the theorem basically states the existence
of specialisers.
Theorem 10.1 (S-1-1 Theorem). For any programming language L with pairing
and programs-as-data there exists a program spec such that rJspecKL(p,s)zL(d) = JpKL(s,d)
(_,_) notation for generic pairing
both inputs as pair
where ( , ) denotes pairing for a general language L.3
program
with 2 inputs partial
remaining
This program spec is a specia(1lsits)eirnpfurtom L(2ntdo) Linpaust first mentioned in Chap. 6. (as pair)
Recall from Chap. 6 that a specialiser takes a program and some of its input and
It can be generalised to programs with m+1
p•roduces a new program that needs “fewer input parameters”. The above equation
(not just 2) input and providing n concrete
specifies the resulting program’s behaviour. The specialiser “applies” the one argu-
menvtatolutehse(gnivoetnjupsrotg1r)amthuthsathreqnuairmesetw(Kolaeregnuem’se)nts, using it as its first argument. IndoSi-nmg-snoTithceonrsetrmuc.tstheresultprogramwithoneremainingargument,otherwise
preserving the program’s semantics. One might say the specialiser is “freezing the
first argument of the given program”.
We can easily prove the S-1-1 theorem for L = WHILE by simply constructing
Stephen Cole Kleene (1909-1994) American mathematician
(also did regular expressions!)
the program specWHILE as given in Fig. 10.1. The program in Fig. 10.1 performs the 5
specialisation, but it does not do any partial evaluation as it does not look into the code (kept in variable code) of the given program. Such optimisations by partial evaluation are sometimes possible.
Imagine a program p to be specialised that has two arguments encoded by in- put variable XY where X has been assigned hd XY and Y been assigned hd tl
XY using the standard list encoding of tuples. After p has been “specialised” with 3 In WHILE we know how to express pairing, namely as a list via p[ , ]q since we know the
datatype is D.
S-m-n describes Specialiser
118
• The resulting program spec is a specialiser (that takes programs as input and returns a new program).
• The concrete code for spec is relatively straightforward and will be given in notes / as program on Canvas site.
• The partial input provides opportunities for optimisations in the code of program p.
6
The so-called “S-m-n” Theorem, sometimes also ca v
b r
is D.
(
H h
u t
e . p
o
c u t s
u
(
rem, can be regarded as justification for partial e technique. The reasons for the strange name will of metaprogramming (i.e. programming with prog states the existence of specializers.
S-1-1 Theorem: Optimisation Example
FmminglanguageLwithpairingan
... read XY{ A:=7
} write A
or any progra
p read XY {
X := hd XY;
xists a program
Y := hd tl XY;
A :=
}
write A
tes pairing.3 XY:= [3,XY];
newp read XY
spec is a spe X:= hd XY;
s that might
Y:= hd tl XY;
A:=
e argument to
write A
e
p
X:= 3;
spec such that
r L zL L
JspecK (p,s) (d) = JpK where ( , ) deno
cialiser from L to L. be possible with t
the program that req
as its first argument, and produces a program wi
otherwise preserving the program’s semantics. On
“freezing the first argument of the given program” We can prove this theorem for L = While by sim
specWhile as follows in WIDE notation:
t and sec
This program
[p,3]
any optimisation
A:=
“applies” the on
A := 7
7
read PS
// PS = (P.S) so compute firs
P:= hd PS;
“Efficient program
S:= tl PS;
// P = ((var i) C (var j)) so inputVar := hd P;
specialisation
code := hd tl P; outputVar := hd tl tl P;
=
// compute specialised newPr
partial evaluation”
// assignment “inputVar := c expression := (list “cons” ( newAssign := (list “:=” input newCode := (list “;” newAssig
newProgram := (list inputVar
8
write newProgram
destruct
ogram whi
ons S inp
list “quo
Var expre
n code);
newCode o
3In WHILE we know how to express pairing, namely as
Self-referencing Programs
• Can we write programs that refer to their own source or Abstract syntax tree?
• Can we give them a well-defined semantics?
• For instance, a program that prints its own source or returns its own AST?
• Try it, it’s not that simple!! What is the problem here?
9
Acceptable Prog. Language
A programming language as discussed before, defined by syntax, data type, and semantics, having also programs- as-data and pairing, is called “acceptable” iff
• it has a universal program
• it has specialisers (S-m-n theorem holds)
• all functions computed by Turing machines or While-programs are also computed by one of its programs.
10
putability and complexity we leave the exploration of partial evaluation to the reader
For instance, to compute the factorial of n, self application leads to a self-interpreter
and swiftly move on.
10.2 Kleene’s Recursion Theorem
The following theorem guarantees the existence of self-referencing programs, that
we can also call “recursive” since with the help of self-reference one can implement
Recursion Theorem
recursion. This will be discussed in more detail later. Let us first state Kleene’s
theorem[5].Recalltheforagenericlanguageweusenotation(, )forpairs.
Theorem 10.2 (Kleene’s Recursion Theorem [5]). Let L be an acceptable pro- gramming language. For any L-program p, there is a L-program q such that for all
input d 2 L-data we have
10.3. RECURSION ELIMINATION CHAPTER 10. SELF-REFERENCE
JqKL(d) = JpKL(q,d)
How does this deal with reflective programs and what is an acceptable program-
Now we simply define the program q we are looking for as another self-application, ming language? The reflective program q is defined via the help of p which has an
this time of pself.
extra parameter to represent “self”. So p may regard q as its own metadata repre-
•
q = JspecKL (pself, pself) (10.3) | {z }
sentation.
•
q is the self-referential program
self application of p
self
Definition 10.1. An acceptable programming language is a programming language This program q returns a L-program and this is actually what we will choose for the
defined by program p that has extra parameter q 4 n the sense we have already provided earlier) for which the following holds :
L (i
program required by the theorem. We have to show that it has the required property.
•
beforerwe prove it, lookzat example usage L
1. L has a self-interpreter (or universal program in the sense of Def. 7.1) and there-
fore must have programs-as-data as well as pairing;
JqKL (d) = JspecKL (pself, pself) (d) use Eq. 10.3, the definition of q
qy
2. The S-m-n theorem L(see Sect. 10.1) holds for L;
4
= f(pself,d)
= pself (pself,d)
use S-1-1 Thm. 10.1 with p and s = pself use Eq 10.2, definition pself
following Neil Jones and Rodgers
= JpKL(JspecKL(pself,pself),d) use Eq. 10.1, definition of f 11
= JpKL(q,d) 120 use Eq. 10.3, definition q backwards This is yet another neat proof achieved with self-application9, two helpings of self-
application actually.
10.3 Recursion Elimination
E
m
n
e
R
l
i
i
a
n
CHAPTER 10. SELF-REFERENCE
i
There are
ma
n
y
applic
a
tion
s of
th
t
c
r
is the
orem
So let us return to the specific language WHILE (so L := WHILE). Figure 10.2 shows
fac rFeadctno{rial
an attempt of implementing the factor
uisself- fac that
interpreter
definition
supported
if n {
makes use of a macro call to mult and
recursively:
A :=
We have seen already that in WHILE Res0:!==
directly, even in extensions of WHILE }
n! = n*(n-1)!
e
u
o
.A
cla
ssic
on
s
10.3. RECURSION ELIMINATION
e is
r
ecur
sion elimination.
ial function by a program, called
fac2 read qn {
q := hd qn;
also calls itself (fac) recursively.
n := hd tl qn;
we cannot define such a recursive
if n {
because recursive macros are not
A := [q, tl n];
ested. We first need to be able t
Res :=
else {
program (self-interpreter) for WHI
}
}
Res := 1
ursive macro as displayed in Fig. 1
s the first of which is a program, n
gram. But fac2 is not yet the fact write Res
andthuswecannotcallfacassuggocompile
else t{hemacroaway.However,withtheheesentsthe
Res := 1 programfacandusingtheuniversalLE,u,we
} factorial2 has canwriteprogramfac2withoutarec0.3.
argument [q,n] so
} Program fac2 takes two argument amely the write Res
emxetar-areparersgenutmatieonotf tqhe factorial pro orial func- tion we want. Applying Kleene’s recursion theorem, however, we obtain a program
RefcaucrRseiofnlTsuhcehothraetm gives us (existence of) facRefl such that
Fig. 10.2: Recursive fac not definable Fig. 10.3: fac2 using reflection for re- JfacReflKWHILE (d) = Jfac2KWHILE [facRefl,d]
in WHILE cursion
and this program does implement the factorial function. We have used the self-
12 10 interpreter here to make the recursion on the program source explicit.
9
TheRperaodoerfsofafmKilliaerenweit’hs ArelocnuzrosiCohnurtche’soruenmtypiesd clo-cnasltcruulucstiwveillwrehciocghnimseetahensimthialatrithyewith
the construction of the recursion operator Y f = (l x. f (x x)) (l x. f (x x)) which also uses two proof tells us how the program q actually looks like. It turns out that, despite of the
self-applications.
elegance of the proof by self application, the resulting program is not very efficient.
1st Impact of Theorem
• Any acceptable programming language is already “closed under recursion”. [Neil Jones]
• Usage in interpreted languages: needs a new self- interpreter called for each recursive call, leading to stacks of self-interpreters running each other,
• leading to exponential runtime,
• thus built-in “reflection” mechanisms to avoid this problem.
13
•
• •
• •
2nd Impact of Theorem
Reflection in compiled languages more difficult as there is no source code or AST.
So no reflection in C or C++.
But in Java as there is a ByteCode interpreter. The Reflection library allows to introspect classes/ methods.
This allows one to circumvent static type checking to
work with “unknown” classes
Frameworks like Spring heavily use reflection.
“Plug-in” technology needs reflection!
14
c Bernhar nam
synt
Computatio
notoriouresplyro to be
ghoodsie pcult t ust exist wit
CHAPTER 10. SELF-REFERENCE 10.2. RECURSION THEOREM
3.Lmsthata T
W follow- ing:
Exam . Such a progintstate-
men
own file
abstract WHILE. Thouhaself-
write, it is thehelpofJKtsatisfies
L
Example 10.1 CoJnspideKr a (sexlf-r.eypro)du=cing xprogram, also called a quine. Such 15
variable.Asusualwestdatoemnenotst—witsroiwtnesoeuxrcepcloidceiwtitehonuctuosidnginangyibnpruat7cokrkentoswlefdogreolfiiststo[wxn,y].
TheproofofKleeTnhoeu’gshit(iseacnonn-trdiv)ialrtaesckutorwsritoenaqutihnee,8oitriesemasyitosproevelathtaitvsuechlyaseslfh-ortbutvery
The proof of Kleene’s second recursion theorem is relatively short but ver
which is achieved by program p that writes as output hd XY if XY is its input a program is supposed to produce—often print as most languages provide print
file name. In our case, where L is WHILE, the program must return its own abstract
for instance the program that returns hd X if X was its input variable.
we therefore define the function:
5
This program q returns an L-program, and this is actually what we will choose for the
This program q returns an L-program, and this is actually what we will choose for the
•
LL
f(r,d)=Jfp(rK,d)(=Jspe(csKpec(r,(r,r)), dd)) (10.1) (10.1)
language. f = L
6
selfL sLelf self
syntax tree. Quines are notoriously difficult to write and this also holds for WHILE.
reproducing program must exist with the help of the above theorem. Just choose p clever indeed.7 to be a program that satisfies:
clever indeed.
Proof. We start with program p that takes two arguments the first of which is con-
which returns an L program that “performs” this self-application. Then we can pass and can plug that into given program p:
this resulting pLrogram as input toLour p to obtain a function
JpK (JspecK (q,q) , d) LL
11w81h1e8re f is now a function mapping L-data to L-data. S1in0ceS1Le0lfi-sreSfaeclrfce-enrecpfitneargbePnlecr,oingfgraoPmrsograms LetuscalltheprogfrisamL-ctohmatpuhtabslethbiysabpehroagvriaomurpself.Suchaprogramclearl
self
where f is now a funDcetfiinoitinon1m0.1awpepknionwgthaLt f-dmaustabectompLut-abdleabtyaa.nLS-pirnogcraemLp is.Inaschcoret:ptable, from
p = f se(1l0f.2) existsasLisTuringcomplete(anditisactupally=eafsytowritethi(1s0.2p)rogramdow
Def. 10.1 we know that f must be computable by an L-program p . In short: 5This is a relatively mild assumption of a language that we are prepared to call a programming
in terms of macro calls oNf q y
loanNwg
pouwawg
25, 2000).
7 So one cannot simply pass the program’s source as its own input.
16 self application of pself self 8 self application of p
This is subject of Exercises 7 and 8, respectively.
p
lic
L self L
Ls
at
of
r
self
,eews. isemspilmyepdlecyfidn,efitanhenpthrdeogprraqomg)rqa.mweqNawreeolaowroeklinogwokfionergasfsoarinaomsthaenprostelhlyef-raspedpllfi-ecaapfitpiolninc,aetiont, he program
6 selfself L
t h i A s f t t i e mr t e h e o A f m p e r i c a n . p h i l o s o p h e r s a e n d l l o f g i c i a n W i l l a r d V a n O r m a n Q u i n e ( J u n e 2 5 , 1 9 0 8 – D e c e m b e r
(10.2) Thisisarelativelymilpdrogarsasmurmequpitreiodnbyothnetaheolarenmg.uWaegheavethtoasthowethatriethpasrethpearerqeudiretdoprcoapelrltya. programming
p=
we are looking for as another self-apqp=licspaectio( pn, ,tphis) time of p(10.3) . Semantically
this time of p .
f
self
elf self
q = specL ( pself, pself) (10.3)
6
WHILE
p [x, y] = x
We start with program p that takes two arguments the first of which i
sidered to be a program itself. We know there is a specialiser spec for the program- which is achieved by program p that writes as output hd XY if XY is its input
ming language (as it is acceptable). We can therefore apply any program, say r, to Proof of Recursion Theorem
considered to be a program itself. We know there is a specialiser spec fo variable. As usual, we do not write explicit encoding brackets for list [x, y].
the programming languagTehe p(roaofsofiKtleeines’s (asecocnde) precturasiobn ltheo)re.m isWrelaetiveclyashnort btuthveryrefore apply an itself, i.e. to its data representation r, with the help of the specialiser
•
ered to be a program itself. We know there is a specialiser spec for the programming Maintechnique:agJasipnesceKlf(-ra,prp)lication!
clever indeed.
program, say q, to itself with the help of the specialiser
Proof We start with program p that takes two arguments the first of which is consid-
| {Lz }
L
language (as it is acceptable). We can therefore apply any program, say r, to itself,
• i.e. to its data repreJsesntpatieoncr,Kwith(thqe h,elqp o)f the specialiser: self application of r
andthenwhwicehrceatunrnpslauLgptrhoigsraimnttohaotu“prerpfotroms
•
We can apply a program to itself and still get
a program (S-1-1 Theorem i.e. specialiser)
s
this resulting program as input to our p to obtain a function
specL (r, r )
”
h
g
e
s
t
ion
e
lf
a
e
t
i
s
lf-application. Then we can pass
p
program required by the theorem. We have to show that it has the required property.
JspecK (
L
self self
p ,p ) LselfselfLL
q (dL) = spec (pL s,eplf s)elf(d) use Eq.10.3, the definition of q
q (d) = spec (p , p ) (d) use Eq.10.3, the definition of q
= p sel(fp s,edl)f use S-1-1 Theorem 10.1 with p and s = p self aftertheAmericanphilosopher=andp logi(cpian,Wd) illardVanuseOSr-1m-1aThneoQremu1i0n.1ew(iJthupnaend2s5=,p1908–Decem-
is Turing-complete in the sense of Def. 2.1, i.e. it computes all progra uring machine can compute.5
Kleene’s Recursion Theorem semantically 6
hat can the Recursion Theorem be used for? A famous example is the
ple 10.1. Consider a self-reproducing program, also called a quine ram is supposed to produce – often print as most languages provide pr
validates the principle
ts – its own source code without using any input7 or knowledge of its d Reus, Sussex University 2015 Limits of
e. In our case, where L is WHILE, the program must return its own ax tree. Quines are notoriously difficult to write and this also holds for
a program that satisfies
m in
of reflection in
gh it is a non-triv10i.2alKlteeanes’skRetcoursiown Trhietoerema quine8, it is easy to prove th1a17t suc dui cincgupltrotgoramwrmituestaenxdisttwhiitsh athlesohehlpolodf sthfeoarbWoveHthILeoEre.mT. hJuosut c
1.
Lha
i
n
p
the sense of Definition 7.1) and g
r
sa
self-in
o
g
terp
r
rete
a
r (or
univer
m
therefore must have programs-as-data as well as pairing;
easy to prove that such a self-reproducing program m
2. TheS-m-ntheorem(seeSect.10.1)holdsforL;
3. L is Turing-complete, i.e. it computes all programs that a Turing machine can
the above theorem. Just choose p to be a program tha
p WHILE [x,y] = x
m
sal prog
compute.5
What can the Recursion Theorem be used for? A famous example is the following:
ra
JK
w ww
P
eu h
a m
g
e r
y
o i
h
o
o
e
q
w i
hi
h
e
wn
o w
a
0
hi m
h
n nc
a
a
d
g
u mp
ue s
t
w n
er 25, 2000).
a
makes use of a macro call to mult and also calls itself (fac) recursively. ddirierecctltyly,,eevveeniinextensions of WHILEbecausseerreeccuurrssiviveemmaacrcorossaraerenontostuspupoproterdted
nment A :=
JpKL (JspecKL (q, q) , d)
corresponds to A :=
chaallstuhnetpilroselfmclearly
wgerarmunthtahtehsapsetchiiaslibsehdavpirougrrapm. . Such a progra g complete (and it is actually e10asySeltf-orefwerernictiengtPhroigsrapmrsogr
n theorem is just a generalisation of the S-1-1 t
calls of p, spec, and q). Now we simply define the p number m refersLto the number of arguments
lf
JspecK (p ,p ) (d) usedefinitionq self
Proof of Recursion Theorem
( p , d )
= pL(q,d) use Eq.10.3, definition q backwards
, d ) self usesSe-l1f-1 Theorem 10.1 with p and s = p
118 10 Self-referencing Programs pself = f (10.2)
as another self-application, this time of pself. Sem
refers to the number of
e the function:
arguments D represen pself = f (10.2)
efine the program q we are looking for as another self-application,
•
NoNwwoewsimwplyedecfionentshiedperorgramnqowtheearrelsooeklifn-gafporpalsicanaothioernse:l
f-application,
f.
’sReqc=fu=rspsJeiscopne(cpKT(hp,epo,rp)em) (10.3)
this time of pself. L
L self self
q = specL ( pself, pself) •
(10.3)
which retuserlfnasppalicnatiLon-opfrpogram which is our
• it remains to show that for this program q:
by the
theorem. W
L
L
w that it has the required property.
eh
L
s
el
f
s
elf
rq (d)= spec (p ,p ) (dz
wv
) use Eq. 10.3, the definition of q
a
v
et
o
sho
ery easy to show that q does the requi c. It is no self L self self
L
self self
self application of pself self
L
turns an L-program, and this is actually what we will choose for the m p, there is a L-program q such that for all in s actually easy to write this program down in terms
sion Theorem Let L be an acceptable program ately that a program q exists with f = JqK as L
program required by the theorem. We have to show that it has the required property.
This program q returns an L-program, and this is actually what we will choose for the desired program q ;
= p (p ,d) use S-1-1 Theorem10.1 with p and s = p
self
= f(p L,d)
LL
L self self
c (p ,p L)Jq(dK)L
useEq.10.2,definition p e.l1f0J.3p, tKhe d(eqfin,itdio)n of q
self
sue
= p (spec (p , p ),
d) use Eq.10.1, definition of f
( dslfe)Esq=
fL self L L self
use Eq. 10.2, definition p 9
deal with reflexive programs and what is an a
This is yet another neat proof achieved with self-application, two helpings of self-
ge. The reflexive program is q which is define
L selfL self self self
spec (p , p ),d) use Eq.10.1, definition of f
aplication act(upally. ,d) use definition p
se
8s L is Turin the S-m-
s of macro = 1). The
looking for number n
am down heorem (
rogram q program
antically, ts.
ming lang is Turing
put d 2 L- of macro
red job:
efore defin
w we simply d s time of psel
Kleene
’s Recur
ws immedi
is program q re L-progra
te (and it i
gram required
p and spe
L
(d) = spe
L= psel JqK (d) =
se
= f(p doesthisdmissible
= pL(
lf
ng langu= J K
d via the ich has an=exJtprKa (pJasrpaemcKete(pr to ,rpepre)s,edn)t “usseelfd”e.fiSnoitiponmqay regard q
L
a
= p (q,d)
is is yet another ne1a0t.p3rooRfecaucrhsiieovnedElwimitihnasteilofn-application,9 two helpings of self-
L
L use Eq.10.3, definition q backwards 17
self self = JpKL(q,d)
tadata representation.
plication actually.
a acceptable programming language is a programming language (i
There are many applications of this theorem. A classic one is recursion elimination.
on: Con- ehfaoslloawuingitorial.wh
s).
Turing ma
So let us return to the specific language WHILE (so L := WHILE). Figure 10.2 shows proof achieved with the help of self-application.
eadaynatptemroptvofidimepldemeentaingrlthiefrac)torfiaolrfunwctiohnibcyhaprtohgraem,fcoalleldofwacinthagt h 10.3. RECURSION ELIMINATION CHAPTER 10. SELF-REFERENCE
makes use of a macro call to mult and also calls itself (fac) recursively.
EiRme
vaetrtseamlpptrofgwrrai
i
0h.3.ef
mnEati
Fig. 10.2 Recursive fac
RoErC
I.ON
s
el
f
CHAPTER 10. SELF-REFERENCE
bes a WIDE program for mu
gseflofr
not definable in WHILEself
ion (of number
RAELI
AsT
APrTeE
. sSiE
ENiC
ofthis1tofo
oeURmS
ecMlINac
this time of pself. | {z
usIOicN
CiHsn
TcRu10rh
mq rosnieo
REeFlr
ion Elim1i0n.3.aRtEiCoUnRSION ELIMINATION CHAPTER 10. SELF-REFERENCE
Pro
10.3. RECURSION ELIMINATION CHAPTER 10. SELF-REFERENCE
Now we simply define the program q we are looking for as another self-application,
mt
ng factorial as a WIDE program fac
Now we simply define the program q we are looking for as another self-application,
this time of p .
10.3. RECURSION ELIMINATION
we
Now we simply define the prqo=graJmspqecwKe a(rpe loo,kping fo)r as another self-applic(a1ti0o.n3,)
N
oww
esi
mply
this time of pself. L
defi
ne th
epr
ogra
are
as an
this time of p .
pplications of this theorem. A classic one is recursion elimination.
eorem holds
| self applic{atzioinfof np { }
q = JspecK L(p self, p sel)f (10.3)
) (10.3) We compute the required equation just by using the
self q=JspecK (p ,p
this time of p . | self applic{atzion ofApse:l=f }
the specific language WHILE (so| L := W{Hz ILE).}Figure 10.2 shows
L
l
Now we simply define the program q weLaresloelofkinsgseeflolffr as another self-application,
This program q returns a L-program and this is actually what we will choose for the self application ofRpes :=
l
sl
n,
t
f saec
n
{
oeolfkin
i
p
l
i
c
ae dlf
}
a
fr
q=JspecK (p ,p ) (10.3)
es
q=JspecKL(pself,psself) (10.3) self application of pself
This program q returns a L-prog|ram and t{hzis is actua}lly what we will choose for the definitpirognrasmwreequimredabdyeth:e theorem. We have to}show that it has the required property.
plementing the factorial function by a program, called fac that This program q returns a L-program and this is acsteulfally what we will choose for the program required by the theorem.sWelfeaphpalivcaetiotnoeosflhpsowe that it has the required property.
complete, ier. it computez s all programs that a program required by the theorem. We Lhave to show that it has the required property.
This program q returns a L-program and this is actually what we will choose for the
acro call to mult and also calls itself (fa{ c) recursively. pTrhoiLgsrparmogrreaqmruiqrerdetbuyrnLtshaesLteh-lpefroorgesrmealm.fWaznedhtahvies itsoaschtouwalltyhwathiatthwase twhiellrcehqouoirsedfoprothperty.
t
othe
eoLFn-
rse
lf-ap
plic
atio
JqK (d) = JspecK (p ,p ) L (d) use Eq. 10.3, the definition of q
5 L r L self selfz Res := 1
re.ial.wcl
pJrqoKgr(adm)r=equiJrsepdebcyKth(eptheor,epm. W)e hLa(vde)toushseowEqth.a1t0i.t3h,atshethdeerfienqiutiorendopfrqoperty.
with Alonzo ChuLr
L
LL self self z }
self self L self
>tlr n;
qy
JqK (d)=qpJspecyK((pp ,,dp) ) (d) uuseseESq-.11-01.3T,htmhe.d1e0fi.1niwtioitnhopfqands=p
L LL self self
q selfyL self L self
JqK (d)=rJpspecK((pp ,d,p) z) (d) u}sseeSE-1q-.1T0.h3m,.th1e0.d1efiwnitihtiopnaonfdqs=p
L sseellffL self self self
JqK (d)=qf(JpsppecyK,Ld()p ,dp) ) (d) wuursuseiestEeSeqE-.1qR1-1e01.sT03,.h2tmh,e.d1ed0fie.nfi1intwitoiotnhnpofaqnds=p
= f(p ,d) use Eq 10.2, definition p
self
= p
(p ,d) use S-1-1 Thm. 10.1 with p and s = p
sesleflf self self self
c
h
’s uL ntyped -calculus will re
se
e fac q selfy self self self self
self
f a program =Jfp(pKL(Js,pde)cKL(pself,pself),d)usseeEqq.10.12,definiittiionopf f
is a s
L LoEf the recursion oLse
d
efined via this theorem
= f(p ,d) use Eq 10.2, definition p
=JpK (Jsp(epcK (,pd) ,p ),du)suesSe-1E-q1.T1h0m.1.,1d0e.1finwitiithonpoafndf s=p
s
elf
l
fL
se
l
f
p
L self self erator Y.
self =Jfp(pKpKL(qJs,,dpd)e)cK (pfac,prea),d)uunsuseesEeE{qEq1.q01..012.0,1d.,3ed,fiednfieintfiiiontiniotinpoonfqfbackwards
lf
=6JpKL(Jqs,dp)ecKL(pself, pself),d)usseeEqq..1100.3.1,,ddeefifinnitiitoionnqobfafckwards
lled a quine Such a program is supposed to
=JpK (Jqs,pde)cK (p i,pf n),d{) uusseeEEqq..1100.1.3,,ddefiefinnititoionnofqfbackwards
L L self self
c
o
gnise the
= JpKL(q,d) use Eq. 10.3, definition q backwards
9 This is yet anotLher neat proof achieved with self-application99, two helpings of self-
ReadersTfhamisiliisaryewtiathnoAtlhoenrzoneCahtuprrcoho’sf uancthyipeeAvdedλ:-wc=aitlhcu
= JpK (q,d) use Eq. 10.3, definition q backwards
else
nes and Rodgers
stiyoenm
construction of the recursion operator Y f = (λx · f (x x)) (λx · f (x x)) which also uses two
ellryd
applicationactually. Res :=
rogramapmplicautiosntactruaellyt.urn its own abstract syntax tr
printaTpcphli siciam
t ancotauthan
n.ea
9
n
ou
o
s
t
proo
on ,
)
i
f
a
t
s
o
chie
ve
w
dw
This is yet another neat proof achieved with self-application9, two helpings of self- self-appliacpaptiloicnas.tion actually. 9
This is yet another neat pro4of achieved with self-application , two helpings of self-
application actually.
}
10.3 Recursion Elimination 10.3 Recursion Eliminati{on
10.3 Recursion Elimination
n
s
ith se
lf
o
-ap
u
pl
r
ic
c
ati
tw
e
c
o
d
o
hel
e
pi
.
I
ngs o
f
self-
ther neat e have alr
There are olds4
pplications
.3 Recurs
ult descri ere are many a
e s-m-n th
let us return to attempt of im
itshTeunring- kes use of a m
:n= c