1 \documentclass[times, 10pt,twocolumn, draft]{article}
4 \usepackage{amssymb,amsmath,mathrsfs,stmaryrd,amsthm}
13 \newcommand{\semT}[1]{\ensuremath{\llbracket #1 \rrbracket}}
14 \newcommand{\sem}[1]{\llbracket \ensuremath{#1} \rrbracket}
15 \newcommand{\pair}[2]{<\!#1,#2\!>}
16 \newcommand{\canonical}{\bot}
17 \newcommand{\R}{~\mathscr{R}~}
18 \newcommand{\N}{\,\mathbb{N}\,}
19 \newcommand{\B}{\,\mathbb{B}\,}
20 \newcommand{\NT}{\,\mathbb{N}\,}
21 \newcommand{\NH}{\,\mathbb{N}\,}
22 \renewcommand{\star}{\ast}
23 \renewcommand{\vec}{\overrightarrow}
24 \newcommand{\one}{{\bf 1}}
25 \newcommand{\mult}{\cdot}
26 \newcommand{\ind}{Ind(X)}
27 \newcommand{\indP}{Ind(\vec{P}~|~X)}
28 \newcommand{\Xind}{\ensuremath{X_{ind}}}
29 \newcommand{\XindP}{\ensuremath{X_{ind}}}
30 \renewcommand{\|}{\ensuremath{\quad | \quad}}
31 \newcommand{\triUP}{\ensuremath{\Delta}}
32 \newcommand{\triDOWN}{\ensuremath{\nabla}}
33 \newcommand{\Rx}{\ensuremath{R_X}}
35 \newtheorem{thm}{Theorem}[subsection]
37 \title{Modified Realizability and Inductive Types}
46 In 1959, Kreisel introduced a notion of ``modified'' realizability to
47 provide an alternative technique to G\"odel functional (dialectica)
48 interpretation for establishing the connection between Peano Arihtmetic
49 and System T. While the dialectica interpretation has been widely
50 studied in the literature, Kreisel's technique, although remarkably
51 simpler,has apparently been almost neglected (with the only exception
52 of Troelstra). In this paper we give a modern presentation of the technique,
53 and generalize it to arbitrary inductive types in a first order setting.
54 This is part of a larger program, advocating the study
55 of logical systems with primitive inductive types starting form
56 weak, predicative logical frameworks and adding little by little small
57 bits of logical power.
61 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
62 \Section{Introduction}
63 The characterization of the provable recursive functions of
64 Peano Arithmetic as the terms of system T is a well known
65 result of G\"odel \cite{Godel58,Godel90}. Although several authors acknowledge
66 that the functional interpretation of the Dialectica paper
67 is not among the major achievements of the author (see e.g. \cite{Girard87}),
68 the result has been extensively investigated and there is a wide
70 topic (see e.g. \cite{Troelstra,HS86,Girard87}, just to mention textbooks,
71 and the bibliography therein).
73 A different, more neglected, but for many respects much more
74 direct relation between Peano (or Heyting) Arithmetics and
75 G\"odel System T is provided
76 by the so called {\em modified realizability}. Modified realizability
77 was first introduced by Kreisel in \cite{Kreisel59} - although it will take you
78 a bit of effort to recognize it in the few lines of paragraph 3.52 -
79 and later in \cite{Kreisel62} under the name of generalized realizability.
80 The name of modified realizability seems to be due to Troelstra
82 - who contested Kreisel's name but unfortunately failed in proposing
83 a valid alternative; we shall reluctantly adopt this latter name
84 to avoid further confusion. Modified realizability is a typed variant of
85 realizability, essentially providing interpretations
86 of $HA^{\omega}$ into itself: each theorem is realized by a typed function
87 of system T, that also gives the actual computational content extracted
89 In spite of the simplicity and the elegance of the proof, it is extremely
90 difficult to find a modern discussion of this result; the most recent
91 exposition we are aware of is in the encyclopedic work by
92 Troelstra \cite{Troelstra} (pp.213-229) going back to thirty years ago.
93 Even modern introductory books
94 to Type Theory and Proof Theory devoting much space to system T
95 such as \cite{GLT} and \cite{TS} surprisingly leave out this simple and
96 illuminating result. Both the previous textbooks
97 prefer to focus on higher order arithmetics and its relation with
98 Girard's System $F$ \cite{Girard86}, but the technical complexity and
99 the didactical value of the two proofs is not comparable: when you
100 prove that the Induction Principle is realized by the recursor $R$
101 of system $T$ you catch a sudden gleam of understanding in the
102 students eyes; usually, the same does not happen when you show, say,
103 that the ``forgetful'' interpretation of the higher order predicate defining
104 the natural numbers is the system $F$ encoding
105 $\forall X.(X\to X) \to X \to X$ of $\N$.
106 Moreover, after a first period of enthusiasm, the impredicative
107 encoding of inductive types in Logical Frameworks has shown several
108 problems and limitations (see e.g. \cite{Werner} pp.24-25) mostly
109 solved by assuming inductive types as a primitive logical notion
110 (leading e.g. form the Calculus of Constructions to the Calculus
111 of Inductive Constructions - CIC). Even the extraction algorithm of
112 CIC, strictly based on realizability principles, and in a first time
113 still oriented towards System F \cite{Paulin87,Paulin89} has been
114 recently rewritten \cite{Letouzey04}
115 to take advantage of concrete types and pattern matching of ML-like
116 languages. Unfortunately, systems like the Calculus of Inductive
117 Constructions are so complex, from the logical point of view, to
118 substantially prevent a really neat theoretical exposition (at present,
120 even exists a truly complete consistency proofs covering all aspects
121 of such systems); moreover, not everybody may be interested in all the features
122 offered by these frameworks, from polymorphism to types depending on
123 proofs. Our program is to restart the analysis of logical systems with
124 primitive inductive types in a smooth way, starting form first order
125 logic and adding little by little small bits of logical power.
126 This paper is the first step in this direction.
128 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
129 \Section{G\"odel system T}
130 We shall use a variant of system T with three atomic types $\N$ (natural
131 numbers), $\B$ (booleans) and $\one$ (a terminal object), and two binary
132 type constructors $\times$ (product) and $\to$ (arrow type).
134 The terms of the language comprise the usual simply typed lambda terms
135 with explicit pairs, plus the following additional constants:
138 \item $true: \B$, $false:\B$, $D:A\to A \to \B \to A$
139 \item $O:\N$, $S:\N \to \N$, $R:A \to (A \to \N \to A) \to \N \to A$,
141 Redexes comprise $\beta$-reduction, projections,
142 and type specific reductions as reported in table \ref{tab:tredex}
146 \begin{tabular}{p{0.34\textwidth}r}
147 $\lambda x:U.M ~ N \leadsto M[N/x]$ & $(\beta)$ \\
148 $fst \pair{M}{N} \leadsto M$ & $(\pi_1)$ \\
149 $snd \pair{M}{N} \leadsto N$ & $(\pi_2)$ \\
150 $D~M~N~ true \leadsto M$ & $(D_{true})$ \\
151 $D~M~N~false \leadsto N$ & $(D_{false})$ \\
152 $R~M~F~ 0 \leadsto M$ & $(R_0)$ \\
153 $R~M~F~(S~n) \leadsto F~n~(R~M~F~n)$ & $(R_S)$ \\
154 $M \leadsto * ~~~~ $ for any M of type $\one$ & $(*)$
155 \end{tabular}\vspace{0.1cm}
157 \caption{\label{tab:tredex}Reduction rules for System T}
160 Note that using the well known isomorpshims
161 $\one \to A \cong A$, $A \to \one \cong \one$
162 and $A \times \one \cong A \cong \one\times A$ (see \cite{AL91}, pp.231-239)
163 we may always get rid of $\one$ (apart the trivial case).
164 The terminal object does not play a major role in our treatment, but
165 it allows to extract better algorithms. In particular we use it
166 to realize atomic proposition, and stripping out the terminal object using
167 the above isomorphisms gives a simple way of just keeping the truly
168 informative part of the algorithms.
170 \Section{Heyting's arithmetics}
175 \item $nat\_ind: P(0) \to (\forall x.P(x) \to P(S(x))) \to \forall x.P(x)$
176 \item $ex\_ind: (\forall x.P(x) \to Q) \to \exists x.P(x) \to Q$
177 \item $ex\_intro: \forall x.(P \to \exists x.P)$
178 \item $fst: P \land Q \to P$
179 \item $snd: P \land Q \to Q$
180 \item $conj: P \to Q \to P \land Q$
181 \item $false\_ind: \bot \to Q$
182 \item $discriminate:\forall x.0 = S(x) \to \bot$
183 \item $injS: \forall x,y.S(x) = S(y) \to x=y$
184 \item $plus\_O:\forall x.x+0=x$
185 \item $plus\_S:\forall x,y.x+S(y)=S(x+y)$
186 \item $times\_O:\forall x.x\mult0=0$
187 \item $times\_S:\forall x,y.x\mult S(y)=x+(x\mult y)$
191 {\bf Inference Rules}
193 say that ax:AX refers to the previous Axioms list...
195 %\hrule\vspace{0.1cm}
196 %\begin{tabular}{p{0.34\textwidth}r}
198 $$\Gamma, x:A, \Delta \vdash x:A ~~~ (Proj)$$
199 $$ \Gamma \vdash ax : AX~~~ (Const)$$
200 $$\frac{\Gamma,x:A \vdash M:Q}{\Gamma \vdash \lambda x:A.M: A \to Q} ~~~ (\to_i)$$
201 $$\frac{\Gamma \vdash M: A \to Q \hspace{0.5cm}\Gamma \vdash N: A}
202 {\Gamma \vdash M N: Q} ~~~ (\to_e)$$
203 $$\frac{\Gamma \vdash M:P}{\Gamma \vdash \lambda x:\N.M: \forall x.P}(*) ~~~
205 $$\frac{\Gamma \vdash M :\forall x.P}{\Gamma \vdash M t: P[t/x]}
208 %\end{tabular}\vspace{0.1cm}
210 %\caption{\label{tab:HArules}Inference rules}
214 % (\land_i)\frac{\Gamma \vdash M:A \hspace{1cm}\Gamma \vdash N:B}
215 % {\Gamma \vdash \pair{M}{N} : A \land B}
217 % (\land_{el})\frac{\Gamma \vdash A \land B}{\Gamma \vdash A}
219 % (\land_{er})\frac{\Gamma \vdash A \land B}{\Gamma \vdash B}
224 % (\exists_i)\frac{\Gamma \vdash P[t/x]}{\Gamma \vdash \exists x.P}\hspace{2cm}
225 % (\exists_e)\frac{\Gamma \vdash \exists x.P\hspace{1cm}\Gamma \vdash \forall x.P \to Q}
231 The formulae to types translation function $\sem{\cdot}$, see table
232 \ref{tab:formulae2types}, takes in input formulae in HA and returns
233 types in T. In table \ref{tab:structproof} we the proofs to terms
234 function for structured proofs. Axiom translation is reported in table
235 \ref{tab:axioms}. In table \ref{tab:canonical} we define how the
236 canoniac element is formed.
240 \begin{tabular}{p{0.21\textwidth}p{0.21\textwidth}}
241 $\sem{A} = \one$ if A is atomic &
242 $\sem{A \land B} = \sem{A}\times \sem{B}$ \\
243 $\sem{A \to B} = \sem{A}\to \sem{B}$ &
244 $\sem{\forall x:\N.P} = \N \to \sem{P}$ \\
245 $\sem{\exists x:\N.P} = \N \times \sem{P}$ &
246 \end{tabular}\vspace{0.1cm}
248 \caption{\label{tab:formulae2types}Formulae to types translation}
253 \begin{tabular}{p{0.20\textwidth}p{0.20\textwidth}}
254 $\semT{M N} = \semT{M} \semT{N}$ &
255 $\semT{M t} = \semT{M} \semT{t}$ \\
256 \multicolumn{2}{l}{$\semT{\lambda x:A.M} = \lambda x:\sem{A}.\semT{M}$} \\
257 \multicolumn{2}{l}{$\semT{\lambda x:\N.M} = \lambda x:\N.\semT{M}$}
258 \end{tabular}\vspace{0.1cm}
260 \caption{\label{tab:structproof}Structured proofs}
265 \begin{tabular}{l}%{0.47\textwidth}p{0.47\textwidth}}
266 $\sem{fst} = \pi_1$\\
267 $\sem{snd} = \pi_2$\\
268 $\sem{conj} = \lambda x:\sem{P}.\lambda y:\sem{Q}.\pair{x}{y}$\\
269 $\sem{false\_ind} = \canonical_{\sem{Q}}$\\
270 $\sem{discriminate} = \lambda \_:\N.\lambda \_:\one.\star$\\
271 $\sem{injS}= \lambda \_:\N. \lambda \_:\N.\lambda \_:\one.\star$\\
272 $\sem{plus\_O} = \sem{times\_O} = \lambda \_:\N.\star$\\
273 $\sem{nat\_ind} = R$ \\
274 $\sem{plus\_S} = \sem{times\_S} = \lambda \_:\N. \lambda \_:\N.\star$ \\
275 $\sem{ex\_intro} = \lambda x:\N.\lambda f:\sem{P}.\pair{x}{f}$ \\
276 $\sem{ex\_ind} = \lambda f:(\N \to \sem{P} \to \sem{Q}).$\\
277 $\qquad\lambda p:\N\times \sem{P}.f~(fst~p)~(snd~p)$
278 \end{tabular}\vspace{0.1cm}
280 \caption{\label{tab:axioms}Axioms translation}
285 \begin{tabular}{l}%p{0.23\textwidth}p{0.23\textwidth}}
286 $\canonical_\one = \lambda x:\one.x$ \\
287 $\canonical_N = \lambda x:\one.0$ \\
288 $\canonical_{U\times V} = \lambda x:\one.\pair{\canonical_{U}
289 x}{\canonical_{V} x}$ \\
290 $\canonical_{U\to V} = \lambda x:\one.\lambda \_:U. \canonical_{V} x$
291 \end{tabular}\vspace{0.1cm}
293 \caption{\label{tab:canonical}Canonical element}
297 \Section{Realizability}
298 The realizability relation is a relation $f \R P$ where $f: \sem{P}$, and
299 $P$ is a closed formula.
302 \item $\neg (\star \R \bot)$
303 \item $* \R (t_1=t_2)$ iff $t_1=t_2$ is true ...
304 \item $\pair{f}{g} \R (P\land Q)$ iff $f \R P$ and $g \R Q$
305 \item $f \R (P\to Q)$ iff for any $m$ such that $m \R P$, $(f \,m) \R Q$
306 \item $f \R (\forall x.P)$ iff for any natural number $n$ $(f n) \R P[\underline{n}/x]$
307 \item $\pair{n}{g}\R (\exists x.P)$ iff $g \R P[\underline{n}/x]$
309 %We need to generalize the notion of realizability to sequents.
310 %Given a sequent $B_1, \ldots, B_n \vdash A$ with free variables in
311 %$\vec{x} = x_1,\ldots, x_m$, we say that $f \R B1, \ldots, B_n \vdash A$ iff
312 %forall natural numbers $n_1, \ldots, n_m$,
313 %if forall $i \in {1,\ldots,n}$
314 %$m_i \R B_i[\vec{\underline{n}}/\vec{x}]$ then
315 %$$f <m_1, \ldots, m_n> \R A[\vec{\underline{n}}/\vec{x}]$$.
318 We need to generalize the notion of realizability to sequents.\\
319 Let $\vec{x} = FV_{\N}( B_1, \ldots, B_n, P)$ a vector of variables of type
320 $\N$ that occur free in $B_1, \ldots, B_n, P$. Let $\vec{b:B}$ the vector
321 $b_1:B_1, \ldots, b_n:B_n$.\\
322 We say that $f \R B_1, \ldots, B_n \vdash A:P$ iff
323 $$\lambda \vec{x:\N}. \lambda \vec{b:B}.f \R
324 \forall \vec{x}. B_1 \to \ldots \to B_n \to P$$
325 Note that $\forall \vec{x}. B_1 \to \ldots \to B_n \to P$ is a closed formula,
326 so we can use the previous definition of realizability on it.
329 We proceed to prove that all axioms $ax:Ax$ are realized by $\sem{ax}$.
333 We must prove that the recursion schema $R$ realizes the induction principle.
334 To this aim we must prove that for any $a$ and $f$ such that $a \R P(0)$ and
335 $f \R \forall x.(P(x) \to P(S(x)))$, and any natural number $n$, $(R \,a \,f
336 \,n) \R P(\underline{n})$.\\
337 We proceed by induction on n.\\
338 If $n=O$, $(R \,a \,f \,O) = a$ and by hypothesis $a \R P(0)$.\\
339 Suppose by induction that
340 $(R \,a \,f \,n) \R P(\underline{n})$, and let us prove that the relation
341 still holds for $n+1$. By definition
342 $(R \,a \,f \,(n+1)) = f \,n \,(R \,a \,f \,n)$,
343 and since $f \R \forall x.(P(x) \to P(S(x)))$,
344 $(f n (R a f n)) \R P(S(\underline{n}))=P(\underline{n+1})$.
347 We must prove that $$\underline{ex\_ind} \R (\forall x:(P x)
348 \to Q) \to (\exists x:(P x)) \to Q$$ Following the definition of $\R$ we have
349 to prove that given\\ $f~\R~\forall~x:((P~x)~\to~Q)$ and
350 $p~\R~\exists~x:(P~x)$, then $\underline{ex\_ind}~f~p \R Q$.\\
351 $p$ is a couple $\pair{n_p}{g_p}$ such that $g_p \R P[\underline{n_p}/x]$, while
352 $f$ is a function such that forall $n$ and for all $m \R P[\underline{n}/x]$
353 then $f~n~m \R Q$ (note that $x$ is not free in $Q$ so $[\underline{n}/x]$
355 Expanding the definition of $\underline{ex\_ind}$, $fst$
356 and $snd$ we obtain $f~n_p~g_p$ that we know is in relation $\R$ with $Q$
357 since $g_p \R P[\underline{n_p}/x]$.
361 $$\lambda x:\N.\lambda f:\sem{P}.\pair{x}{f} \R \forall x.(P\to\exists x.P(x)$$
362 that leads to prove that for each n
363 $\underline{ex\_into}~n \R (P\to\exists x.P(x))[\underline{n}/x]$.\\
364 Evaluating the substitution we have
365 $\underline{ex\_into}~n \R (P[\underline{n}/x]\to\exists x.P(x))$.\\
366 Again by definition of $\R$ we have to prove that given a
367 $m \R P[\underline{n}/x]$ then $\underline{ex\_into}~n~m \R \exists x.P(x)$.
368 Expanding the definition of $\underline{ex\_intro}$ we have
369 $\pair{n}{m} \R \exists x.P(x)$ that is true since $m \R P[\underline{n}/x]$.
372 We have to prove that $\pi_1 \R P \land Q \to P$, that is equal to proving
373 that for each $m \R P \land Q$ then $\pi_1~m \R P$ .
374 $m$ must be a couple $\pair{f_m}{g_m}$ such that $f_m \R P$ and $g_m \R Q$.
375 So we conclude that $\pi_1~m$ reduces to $f_m$ that is in relation $\R$
378 \item $snd$. The same for $fst$.
381 We have to prove that
382 $$\lambda x:\sem{P}. \lambda y:\sem{Q}.\pair{x}{y}\R P \to Q \to P \land Q$$
383 Following the definition of $\R$ we have to show that
384 for each $m \R P$ and for each $n \R Q$ then
385 $(\lambda x:\sem{P}. \lambda y:\sem{Q}.\pair{x}{y})~m~n \R P \land Q$.\\
386 This is the same of $\pair{m}{n} \R P \land Q$ that is verified since
387 $m \R P$ and $n \R Q$.
391 We have to prove that $\bot_{\sem{Q}} \R \bot \to Q$.
392 Trivial, since there is no $m \R \bot$.
394 \item $discriminate$.
395 Since there is no $n$ such that $0 = S n$ is true... \\
396 $\underline{discriminate}~n \R 0 = S~\underline{n} \to \bot$ for each n.
399 We have to prove that for each $n_1$ and $n_2$\\
400 $\lambda \_:\N. \lambda \_:\N.\lambda \_:\one.*~n_1~n_2 \R
401 (S(x)=S(y)\to x=y)[n_1/x][n_2/y]$.\\
402 We assume that $m \R S(n_1)=S(n_2)$ and we have to show that
403 $\lambda \_:\N. \lambda \_:\N.\lambda \_:\one.*~n_1~n_2~m$ that reduces to
404 $*$ is in relation $\R$ with $n_1=n_2$. Since in the standard model of
405 natural numbers $S(n_1)=S(n_2)$ implies $n_1=n_2$ we have that
409 Since in the standard model for natural numbers $0$ is the neutral element
410 for addition $\lambda \_:\N.\star \R \forall x.x + 0 = x$.
413 In the standard model of natural numbers the addition of two numbers is the
414 operation of counting the second starting from the first. So
415 $$\lambda \_:\N. \lambda \_:\N. \star \R \forall x,y.x+S(y)=S(x+y)$$.
418 Since in the standard model for natural numbers $0$ is the absorbing element
419 for multiplication $\lambda \_:\N.\star \R \forall x.x \mult 0 = 0$.
422 In the standard model of natural numbers the multiplications of two
423 numbers is the operation of adding the first to himself a number of times
424 equal to the second number. So
425 $$\lambda \_:\N. \lambda \_:\N. \star \R \forall x,y.x+S(y)=S(x+y)$$.
432 Let us prove the following principle of well founded induction:
433 \[(\forall m.(\forall p. p < m \to P~p) \to P~m) \to \forall n.P~n\]
434 In the following proof we shall make use of proof-terms, since we finally
435 wish to extract the computational content; we leave to reader the easy
436 check that the proof object describes the usual and natural proof
439 We assume to have already proved the following lemmas (having trivial
441 \[L : \forall p, q.p < q \to q \le 0 \to \bot\]
442 \[M : \forall p,q,n.p < q \to q \le (S n) \to p \le n \]
443 Let us assume $h : \forall m.(\forall p. p < m \to P~p) \to P~m$.
444 We prove by induction on $n$ that $\forall q. q \le n \to P~q$.
445 For $n=0$, we get a proof of $P ~q$ by
447 B & \equiv & \lambda q.\lambda h_0:q \le 0. h ~q~ \nonumber\\
448 & & \quad (\lambda p.\lambda k:p < q. false\_ind ~(L~p~q~k~h_0)) \nonumber
450 In the inductive case, we must prove that, for any $n$,
451 \[(\forall q. q \le n \to P~q) \to (\forall q. q \le S n \to P~q)\]
452 Assume $h_1: \forall q. q \le n \to P q$ and
453 $h_2: q \le S ~n$. Let us prove $\forall p. p < q \to P~p$.
454 If $h_3: p < q$ then $(M~ p~ q~ n~ h_3~ h_2): p \le n$, hence
455 $h_1 ~p ~ (M~ p~ q~ n~ h_3~ h_2): P~p$.\\
456 In conclusion, the proof of the
459 I & \equiv & \lambda n.\lambda h_1:\forall q. q \le n \to P~ q.\lambda q.\lambda h_2:q \le S n. \nonumber\\
460 & & \quad h ~ q ~ (\lambda p.\lambda h_3:p < q.h_1 ~p~ (M~ p~ q~ n~ h_3~ h_2))
463 (where $h$ is free in I).
466 & \lambda h:\forall m.(\forall p. p < m\to P~p)\to P~m.\lambda m. &\nonumber\\
467 & \quad nat\_ind ~B ~ I ~m~m~ (le\_n ~ m) & \nonumber
470 where $le\_n$ is a proof that $\forall n. n \le n$, and the free $P$ in the definition of $nat_{ind}$ is instantiated with $\forall m.m \le m \to P~m$.\\
471 Form the previous proof,after stripping terminal objects,
472 and a bit of eta-contraction to make
473 the term more readable, we extract the following term (types are omitted):
475 \[R' \equiv \lambda f.\lambda m.
476 R~ (\lambda n.f ~n~ (\lambda q.*))~
477 (\lambda n\lambda g\lambda q.f ~q~g)~m ~m\]
479 The intuition of this operator is the following: supose to
480 have a recursive definition $h q = F[h]$ where $q:\N$ and
481 $F[h]: A$. This defines a functional
482 $f: \lambda q.\lambda g.F[g]: N\to(N\to A) \to A$, such that
483 (morally) $h$ is the fixpoint of $f$. For instance,
484 in the case of the fibonacci function, $f$ is
486 fibo & \equiv & \lambda q. \lambda g. if~ q = 0~then~ 1~ else \nonumber\\
487 & & \quad if~ q = 1~ then~ 1~ else ~ g (q-1)+g (q-2) \nonumber
491 approximation of $h$ from the previous approximation $h$ taken
492 as input. $R'$ precisely computes the mth-approximation starting
493 from a dummy function $(\lambda q.*_A)$. Alternatively,
494 you may look at $g$ as the ``history'' (curse of values) of $h$
495 for all values less or equal to $q$; then $f$ extend $g$ to
498 Let's compute for example
500 R'~fibo~2 & \leadsto &
501 R~ (\lambda n.fibo ~n~ (\lambda q.*))~
502 (\lambda n\lambda g\lambda q.fibo ~q~g)~2 ~2\nonumber\\
504 (\lambda n\lambda g\lambda q.fibo ~q~g)~1~
506 (\lambda n.fibo ~n~ (\lambda q.*))~
507 (\lambda n\lambda g\lambda q.fibo ~q~g)~1)~
512 (\lambda n.fibo ~n~ (\lambda q.*))~
513 (\lambda n\lambda g\lambda q.fibo ~q~g)~1)~
517 ((\lambda n\lambda g\lambda q.fibo ~q~g)~0~
519 (\lambda n.fibo ~n~ (\lambda q.*))~
520 (\lambda n\lambda g\lambda q.fibo ~q~g)~0))~
526 (\lambda n.fibo ~n~ (\lambda q.*))~
527 (\lambda n\lambda g\lambda q.fibo ~q~g)~0)
532 (\lambda n.fibo ~n~ (\lambda q.*)))2
535 fibo~2~(\lambda q.fibo ~q~ (\lambda n.fibo ~n~ (\lambda q.*))) \nonumber\\
537 (\lambda q.fibo ~q~ (\lambda n.fibo ~n~ (\lambda q.*))) 1 +
538 (\lambda q.fibo ~q~ (\lambda n.fibo ~n~ (\lambda q.*))) 0 \nonumber\\
540 fibo ~1~ (\lambda n.fibo ~n~ (\lambda q.*)) +
541 fibo ~0~ (\lambda n.fibo ~n~ (\lambda q.*)) \nonumber\\
545 Note that the second argument of $fibo$ is always a method to calculate all the prvious values of $fibo$. DA CAPIRE (per me) come mai $\lambda n$ non viene usata...
548 n non serve perche' c'e' una relazione logica di n con q,
549 in particolare $q <= Sn$ ... quindi $q < n$ (lemma M)...
550 e quindi posso usare come history $< n$ una history $< q$.
551 il $\lambda h2$ essendo $[[q <= Sn]]$ = 1 viene scartata.
553 se si spiega come array viene decente... forse. lunedi' provo a scrivere
556 \Section{Inductive types}
557 The notation we will use is similar to the one used in
558 \cite{Werner} and \cite{Paulin89} but we prefer
559 giving a label to each constructor and use that label instead of the
560 longer $Constr(n,\ind\{\ldots\})$ to indicate the $n^{th}$ constructor.
561 We adopt the vector notation to make things more readable.
562 $\vec{m}$ has to be intended as $m_1~\ldots~m_n$ where $n$ may
563 be equal to 0 (we use $m_1~\vec{m}$ when we want to give a
564 name to the first $m$ and assert $n>0$). If the vector notation is
565 used inside an arrow type it has a slightly different meaning,
566 $A \to \vec{B} \to C$ is a shortcut for
567 $A \to B_1 \to \ldots \to B_n \to C$.
569 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
570 \SubSection{Extensions to the logic framework}
571 To talk about arbitrary inductive types (and not hard coded natural numbers) we
572 have to extend a bit our framework.
574 First we admit quantification over inductive types $T$, thus $\forall x:T.A$
575 and $\exists x:T.A$ are allowed. Then rules 4 and 5 of the $\sem{\cdot}$
576 definition are replaced by $\sem{\forall x:T.P} = T \to \sem{P}$ and
577 $\sem{\exists x:T.P} = T \times \sem{P}$.
579 For each inductive type we will describe the formation rules and the
580 corresponding induction principle schema.
582 Symmetrically we have to extend System T with arbitrary inductive types and
583 we will see how theyr recursors are defined in the following sections.
585 The definition of $\R$ is modified substituting each occurrence of $\N$ with
586 a generic inductive type $T$.
588 %%%%%%%%%%%%%%%%%%%%%%%%%%%%
589 \SubSection{Type definition}
590 $$\ind\{c_1:C(X); \ldots ; c_n:C(X)\}$$
591 $$C(X) ::= X \| T \to C(X) \| X \to C(X)$$
592 In the second case we mean $T \neq X$.
594 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
595 \SubSection{Induction principle}
596 The induction principle for an inductive type $X$ and a predicate $Q$
597 is a constant with the following type
598 $$\Xind:\vec{\triUP\{C(X), c\}} \to \forall t:X.Q(t)$$
599 $\triUP$ takes a constructor type $C(X)$ and a term $c$ (initially $c$ is a
600 constructor of X, and $c:C(X)$) and is defined by recursion as follows:
602 \triUP\{X, c\} & = & Q(c) \nonumber\\
603 \triUP\{T \to C(X), c\} & = &
604 \forall m:T.\triUP\{C(X),c~m\} \nonumber\\
605 \triUP\{X \to C(X), c\} & = &
606 \forall t:X.Q(t) \to \triUP\{C(X), c~t\} \nonumber
609 %%%%%%%%%%%%%%%%%%%%%
610 \SubSection{Recursor}
611 %\SubSubSection{Type}
612 The type of the recursor $\Rx$ on an inductive type $X$ is
613 $$\Rx : \vec{\square\{C(X)\}} \to X \to \alpha$$
614 $\square$ is defined by recursion on the constructor type $C(X)$.
616 \square\{X\} & = & \alpha \nonumber \\
617 \square\{T \to C(X)\} & = & T \to \square\{C(X)\}\nonumber \\
618 \square\{X \to C(X)\} & = & X \to \alpha \to \square\{C(X)\}\nonumber
620 %\SubSubSection{Reduction rules}
622 $$\Rx~\vec{f}~(c_i~\vec{m}) \leadsto
623 \triDOWN\{C(X)_i, f_i, \vec{m}\}$$
624 $\triDOWN$ takes a constructor type $C(X)$, a term $f$
625 (of type $\square\{C(X)\}$) and is defined by recursion as follows:
627 \triDOWN\{X, f, \} & = & f\nonumber \\
628 \triDOWN\{T \to C(X), f, m_1~\vec{m}\} & = &
629 \triDOWN\{C(X), f~m_1, \vec{m}\}\nonumber \\
630 \triDOWN\{X \to C(X), f, m_1~\vec{m}\} & = &
631 \triDOWN\{C(X), f~m_1~(\Rx~\vec{f}~m_1),
634 We assume $\Rx~\vec{f}~(c_i~\vec{m})$ is well typed, so in the first case we
635 can omit $\vec{m}$ since it is an empty sequence.
637 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
638 \SubSection{Realizability of the induction principle}
639 Once we have inductive types and their induction principle we want to show that
640 the recursor $\Rx$ realizes $\Xind$, that is that $\Rx$ has type
641 $\sem{\Xind}$ and is in relation $\R$ with $\Xind$.
643 \begin{thm}$\Rx : \sem{\Xind}$\end{thm}
645 We have to compare the definition of $\square$ and $\triUP$
646 since they play the same role in constructing respectively the types of
648 $\Xind$. If we assume $\alpha = \sem{Q}$ and we apply the $\sem{\cdot}$
649 function to each right side of the $\triUP$ definition we obtain
650 exactly $\square$. The last two elements of the arrows $\Rx$ and
651 $\Xind$ are again the same up to $\sem{\cdot}$.
654 \begin{thm}$\Rx\R \Xind$\end{thm}
656 To prove that $\Rx\R \Xind$ we must assume that for each $i$ index
657 of a constructor of $X$, $f_i \R \triUP\{C(X)_i, c_i\}$ and we
658 have to prove that for each $t:X$
659 $$\Rx~\vec{f}~t \R Q(t)$$
661 We proceed by induction on the structure of $t$.
663 The base case is when the
664 type of the head constructor of $t$ has no recursive arguments (i.e. the type
665 is generated using only the first two rules $C(X)$), so
666 $(\Rx~\vec{f}~(c_i~\vec{m}))$ reduces in one step to $(f_i~\vec{m})$. $f_i$
667 realizes $\triUP\{C(X)_i, c_i\}$ by assumption and since we are in the base
668 case $\triUP\{C(X)_i, c_i\}$ is of the form $\vec{\forall t:T}.Q(c_i~\vec{t})$.
669 Thus $f_i~\vec{m} \R Q(c_i~\vec{m})$.
671 In the induction step we have as induction hypothesis that for each recursive
672 argument $t_i$ of the head constructor $c_i$, $r_i\equiv
673 \Rx~\vec{f}~t_i \R Q(t_i)$. By the third rule of $\triDOWN$ we obtain the reduct
674 $f_i~\vec{m}~\vec{t~r}$ (here we write first all the non recursive arguments,
675 then all the recursive one. In general they can be mixed and the proof is
676 exactly the same but the notation is really heavier). We know by hypothesis
677 that $f_i \R \triUP\{C(X)_i, c_i\} \equiv \vec{\forall m:T}.\vec{\forall
678 t:X.Q(t)} \to Q(c_i~\vec{m}~\vec{t})$, thus $f_i~\vec{m}~\vec{t~r} \R
679 Q(c_i~\vec{m}~\vec{t})$.
681 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
682 \Section{Strong normalization of extended system T}
683 Strong normalization for system T is a well know result\cite{GLT}
684 that can be easily extended to System T with this kind of inductive
685 types. The first thing we have to do is to extend the definition of
686 neutral term to the terms not of the form $<u,v>$, $\lambda x.u$,
689 In conformity with the demonstration we are extending we call $\nu(t)$
690 the length of the longest reduction path from $t$ and $\ell(t)$ the
691 number of symbols in the normal form of $t$.
693 For an inductive type $\ind\{c_1:C(X); \ldots ; c_n:C(X)\}$
694 we have to prove that for each $i$,
695 given a proper sequence of reducible arguments $\vec{m}$ and $\vec{f}$,
696 $(c_i~\vec{m})$ and $\Rx~\vec{f}~(c_i~\vec{m})$ are reducible.
698 First the simple case of constructors. If the constructor $c_i$ takes
699 no arguments then it is already in normal form. If it takes
700 $m_1,\ldots,m_n$ reducible arguments, then $\nu(c_i~\vec{m}) = max \{m_1,
701 \ldots,m_n\}$ and so $c_i~\vec{m}$ is strongly nomalizable thus
702 reducible for the definition of reducibility for base types.
704 To show that $\Rx~\vec{f}~(c_i~\vec{m})$ is reducible we can use
705 (\textbf{CR 3}) that states that if $t$ is neutral and every $t'$ obtained by
706 executing one redex of $t$ is reducible, then $t$ is reducible.
708 Now we have to show that each term that can be obtained by a
709 reduction step is reducible. We can procede induction on
710 $\Sigma\nu(f_i) + \nu(c_i~\vec{m}) +
711 \ell(c_i~\vec{m})$ since we know by hypothesis that $\vec{f}$ and
712 $(c_i~\vec{m})$ are reducible and consequently strongly normalizing.
714 The base case is when $c_i$ takes no arguments and $\vec{f}$ are
715 normal. In this case the only redex we can compute is
716 $$\Rx~\vec{f}~c_i~\leadsto~f_i$$ that is reducible by hypothesis.
718 The interesting inductive case is when $\vec{m}$ and $\vec{f}$ are
719 normal, so the only reduction step we can execute is
720 $$\Rx~\vec{f}~(c_i~\vec{m})~\leadsto~f_i~\vec{m}~\vec{(\Rx~\vec{f}~n)}$$
721 where $\vec{n}$ are the recursive arguments of $c_i$ (here we wrote
722 the recursive calls as the last parameters of $f_i$ just to lighten
723 notation). Since $\ell(n_j)$ is less than $\ell(c_i~\vec{m})$ for
724 every $j$ we can apply the inductive hypothesis and state that
725 $\Rx~\vec{f}~n_j$ is reducible. Then by definition of reducibility of
726 the arrow types and by the hypothesis that $f_i$ and $\vec{m}$ are
727 reducible, we obtain that $$f_i~\vec{m}~\vec{(\Rx~\vec{f}~n)}$$ is
730 All other cases, when we execute a redex in $\vec{m}$ or $\vec{f}$,
731 are straightforward applications of the induction hypothesis.
734 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
735 \Section{Improving inductive types}
736 It is possible to parametrise inductive types over other inductive types
737 without much difficulties since the type $T$ in $C(X)$ is free. Both the
738 recursor and the induction principle are schemas, parametric over $T$.
740 Possiamo anche definire $X_{\vec{P}}\equiv Ind(P|X)={c_i : C(P|X)}$ e poi
741 fare variare $T$ su $\vec{P}$, ma non ottengo niente di meglio.
743 Credo anche che quantificare su eventuali variabili di tipo non cambi niente
744 visto che non abbiamo funzioni.
746 Se ammettiamo che i tipi dipendano da termini di tipo induttivo
749 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
750 \bibliographystyle{latex8}
751 %\bibliography{latex8}
753 \begin{thebibliography}{}
754 \bibitem{AL91}A.Asperti, G.Longo. Categories, Types and Structures.
755 Foundations of Computing, Cambrdidge University press, 1991.
756 \bibitem{Girard86}G.Y.Girard. The system F of variable types, fifteen
757 years later. Theoretical Computer Science 45, 1986.
758 \bibitem{Girard87}G.Y.Girard. Proof Theory and Logical Complexity.
759 Bibliopolis, Napoli, 1987.
760 \bibitem{GLT}G.Y.Girard, Y.Lafont, P.Tailor. Proofs and Types.
761 Cambridge Tracts in Theoretical Computer Science 7.Cambridge University
763 \bibitem{Godel58}K.G\"odel. \"Uber eine bisher noch nicht ben\"utzte Erweiterung
764 des finiten Standpunktes. Dialectica, 12, pp.34-38, 1958.
765 \bibitem{Godel90}K.G\"odel. Collected Works. Vol.II, Oxford University Press,
767 \bibitem{HS86}J.R.Hindley, J. P. Seldin. Introduction to Combinators and
768 Lambda-calculus, Cambridge University Press, 1986.
769 \bibitem{Howard68}W.A.Howard. Functional interpretation of bar induction
770 by bar recursion. Compositio Mathematica 20, pp.107-124. 1958
771 \bibitem{Howard80}W.A.Howard. The formulae-as-types notion of constructions.
772 in J.P.Seldin and j.R.Hindley editors, to H.B.Curry: Essays on Combinatory
773 Logic, Lambda calculus and Formalism. Acedemic Press, 1980.
774 \bibitem{Kleene45}S.C.Kleene. On the interpretation of intuitionistic
775 number theory. Journal of Symbolic Logic, n.10, pp.109-124, 1945.
776 \bibitem{Kreisel59} G.Kreisel. Interpretation of analysis by means of
777 constructive functionals of finite type. In. A.Heyting ed.
778 {\em Constructivity in mathematics}. North Holland, Amsterdam,1959.
779 \bibitem{Kreisel62} G.Kreisel. On weak completeness of intuitionistic
780 predicatelogic. Journal of Symbolic Logic 27, pp. 139-158. 1962.
781 \bibitem{Letouzey04}P.Letouzey. Programmation fonctionnelle
782 certifi\'ee; l'extraction
783 de programmes dans l'assistant Coq. Ph.D. Thesis, Universit\'e de
784 Paris XI-Orsay, 2004.
785 \bibitem{Loef}P.Martin-L\"of. Intuitionistic Type Theory.
786 Bibliopolis, Napoli, 1984.
787 \bibitem{Paulin87}C.Paulin-Mohring. Extraction de programme dans le Calcul de
788 Constructions. Ph.D. Thesis, Universit\'e de
790 \bibitem{Paulin89}C.Paulin-Mohring. Extracting $F_{\omega}$ programs
791 from proofs in the Calculus of Constructions. In proc. of the Sixteenth Annual
793 Principles of Programming Languages, Austin, January, ACML Press 1989.
794 \bibitem{Sch}K.Sch\"utte. Proof Theory. Grundlehren der mathematischen
795 Wissenschaften 225, Springer Verlag, Berlin, 1977.
796 \bibitem{Troelstra}A.S.Troelstra. Metamathemtical Investigation of
798 Arithmetic and Analysis. Lecture Notes in Mathematics 344, Springer Verlag,
800 \bibitem{TS}A.S.Troelstra, H.Schwichtenberg. Basic Proof Theory.
801 Cambridge Tracts in Theoretical Computer Science 43.Cambridge University
803 \bibitem{Werner}B.Werner. Une Th\'eorie des Constructions Inductives.
804 Ph.D.Thesis, Universit\'e de Paris 7, 1994.
807 \end{thebibliography}