a riga 8 in A.17sia stato riportato identico nel tipo di H1 modulo ridenomina- zione della P in R, mentre il caso induttivo a riga 9 diA.17sia stato semplificato mediante la rimozione dell’ipotesi induttiva U s. Così facendo è stata spezzata la catena di dipendenze fra tipi che avrebbe reso necessaria l’introduzione delle proposizioni P, Q, ed S. In questo modo la dimostrazione del lemma push_len risulta più semplice e leggibile:
lemma push_len: ∀e, s. e_len (push e s) = S (e_len e). @Environment_simple_ind2
[ //
|#e #s #H #s1 normalize >H // ] qed.
Codice A.19: Enuciato e dimostrazione del lemma push_len
A.4 Tecniche di riduzione in compendio
In molte parti del lavoro si è parlato della necessità di effettuare riduzioni mirate dei termini per evitare fenomeni di esplosione della taglia. Come abbiamo visto, infatti, tali fenomeni comporterebbero un rallentamento del dimostratore inte- rattivo dovuto all’aumento dei tempi di applicazione dei tactic che, in alcuni casi, sarebbero tali da rendere impraticabile la dimostrazione in tempi accet- tabili. Per evitare questi fenomeni è necessario saper usare opportunamente i tactic di riduzione messi a disposizione da Matita.
Ogni tactic di riduzione, se non specificato altrimenti, viene applicato al goal corrente, mentre se seguito dalla pattern riducono solo in quei sottotermini del goal corrente (o delle ipotesi), che fanno match col pattern. Per i nostri fini non analizzeremo la sintassi e la semantica dei pattern, tuttavia una trattazione più accurata di tale argomento, rimandiamo il lettore alla consultazione di [6].
normalize
Il tactic normalize effettua la normalizzazione del termine su cui è chiamato; per far ciò tutte le definizioni (i.e. di lemmi e funzioni) vengono riscritti con il loro corpo che viene successivamente ridotto alla forma normale. Le condizioni di accettazione delle definizioni (per esempio come quelle previste per le funzioni ricorsive di cui abbiamo discusso in A.2) garantiscono che la riduzione ad un certo punto termini. Come abbiamo anticipato in A.2, l’uso di questo tactic è particolarmente aggressivo sul termine e può causare l’esplosione della sua taglia specialmente qualora nel corpo del sotto-termine ridotto siano presenti prove, poiché di solito le dimensioni di questi λ-termini sono spesso elevate. Quindi, in questi contesti, che nel lavoro di formalizzazione che abbiamo descritto erano la maggior parte dei casi, risulta più indicato l’uso dei tactic whd e change with.
Esempio A.4.1. Supponiamo di avere il goal (3+5)+1 = 9. L’applicazione del
tactic normalize ridurrebbe il goal a 9=9, mentre per esempio l’applicazione del tactic normalize in match (3+5); ridurrebbe il goal in 8+1 = 9.
whd
Il tactic whd semplifica un termine riducendolo alla sua weak-head normal form, ossia in modo che il suo costruttore più esterno (la sua testa) non sia ulteriormente semplificabile.
Esempio A.4.2. Supponiamo di avere il goal (3+5)+1 = 9. L’applicazione del
tactic whd in match (3+5) semplifica la somma in S (2 + 5) e, dal momento che il costruttore più esterno è S, l’espressione ha raggiunto la sua weak-head normal form ed il goal viene riscritto come S (2+5)+1 = 9. Similmente l’ap- plicazione del tactic normalize in match ((3+5)+1); ridurrebbe il goal in S (2+5)+1 = 9, ma dal momento che la testa del sottotermine su cui è chiamato (in questo caso +) è ancora semplificabile, esso effettua un altro passo di ridu- zione del sottotermine in S (2+5+1). A questo punto il termine ha raggiunto la sua weak-head normal form, per cui il goal viene riscritto in S (2+5+1) = 9.
change with
Il tactic change with, invece, è fortemente più espressivo dei precedenti: esso sostituisce il sottotermine t su cui è chiamato con qualsiasi altro termine t' che sia convertibile alla forma normale di t. Dal momento che ogni termine è convertibile alla propria forma normale o alla propria weak-head normal form, il tactic change with è espressivo almeno quanto i tactic normalize e whd. Inoltre può essere usato “a rovescio” per rifattorizzare alcune parti di un termine che sono state semplificate troppo per esempio da una normalize.
Esempio A.4.3. Supponiamo di avere il goal (3+5)+1 = 9. L’applicazione
del tactic change with (7+1) in match (3+5); cerca nel goal tutti i sotto termini che si normalizzano come (3+5), in questo caso (3+5) e 8, sottotermine di 93, e li riscrive come 7+1, per cui il goal diventa (7+1)+1 = S (7+1).
3Ricordiamo che i naturali sono espressi con il tipo induttivo N := O : N | S : N → N,
Bibliografia
[1] Beniamino Accattoli. “The Complexity of Abstract Machines”. In: Electro-
nic Proceedings in Theoretical Computer Science 235 (gen. 2017), pp. 1–
15. issn: 2075-2180. doi:10.4204/eptcs.235.1. url: http://dx.doi. org/10.4204/EPTCS.235.1.
[2] Beniamino Accattoli e Bruno Barras. “Environments and the Complexity of Abstract Machines”. In: Proceedings of the 19th International Sympo-
sium on Principles and Practice of Declarative Programming. PPDP ’17.
Namur, Belgium: Association for Computing Machinery, 2017, pp. 4–16. isbn: 9781450352918. doi: 10 . 1145 / 3131851 . 3131855. url: https : //doi.org/10.1145/3131851.3131855.
[3] Beniamino Accattoli e Giulio Guerrieri. “Implementing Open Call-by- Value”. In: 7th International Conference on Fundamentals of Software En-
gineering (FSEN). A cura di Mehdi Dastani e Marjan Sirjani. Vol. LNCS-
10522. Fundamentals of Software Engineering. Teheran, Iran: Springer International Publishing, apr. 2017, pp. 1–19. doi:10.1007/978-3-319- 68972-2\_1. url:https://hal.archives-ouvertes.fr/hal-01675365. [4] Beniamino Accattoli e Giulio Guerrieri. “Open Call-by-Value (Extended Version)”. In: CoRR abs/1609.00322 (2016). arXiv: 1609 . 00322. url:
http://arxiv.org/abs/1609.00322.
[5] Beniamino Accattoli et al. “Crumbling Abstract Machines”. In: CoRR abs/1907.06057 (2019). arXiv: 1907.06057. url: http://arxiv.org/ abs/1907.06057.
[6] Andrea Asperti, Wilmer Ricciotti e Claudio Sacerdoti Coen. “Matita Tu- torial”. In: Journal of Formalized Reasoning 7.2 (dic. 2014), pp. 91–199. doi: 10.6092/issn.1972-5787/4651. url: https://jfr.unibo.it/ article/view/4651.
[7] Hendrik Pieter Barendregt. The lambda calculus - its syntax and se-
mantics. Vol. 103. Studies in logic and the foundations of mathematics.
North-Holland, 1985. isbn: 978-0-444-86748-3.
[8] Hendrik Pieter Barendregt, Wil Dekkers e Richard Statman. Lambda Cal-
culus with Types. Perspectives in logic. Cambridge University Press, 2013.
isbn: 978-0-521-76614-2. url:http://www.cambridge.org/de/academic/ subjects/mathematics/logic-categories-and-sets/lambda-calculus- types.
[9] Henk (Hendrik) Barendregt e E. Barendsen. “Introduction to lambda calculus”. In: Nieuw archief voor wisenkunde 4 (gen. 1984), pp. 337–372. [10] J. Barkley Rosser. “Haskell B. Curry and Robert Feys. Combinatory logic.
Volume I. With two sections by William Craig. Studies in logic and the foundations of mathematics. North-Holland Publishing Company, Amster- dam1958, xvi 417 pp.” In: Journal of Symbolic Logic 32.2 (1967), pp. 267– 268. doi:10.1017/S0022481200114203.
[11] Yves Bertot e Pierre Castran. Interactive Theorem Proving and Pro-
gram Development: Coq’Art The Calculus of Inductive Snoctructions. 1st.
Springer Publishing Company, Incorporated, 2010. isbn: 3642058809. [12] Luca Cardelli. “Type Systems”. In: ACM Comput. Surv. 28.1 (mar. 1996),
pp. 263–264. issn: 0360-0300. doi:10.1145/234313.234418. url:https: //doi.org/10.1145/234313.234418.
[13] Oliver Danvy e Andrzex Filinski. “Representing Control: a Study of the CPS Transformation”. In: Mathematical Structures in Computer Science 2.4 (1992), pp. 361–391. doi: 10.1017/S0960129500001535.
[14] Davide Davoli e Claudio Sacerdoti Coen. davidedavoli/Crumbling-Abstract-
Machines v0.1.1. Ver. v0.1.1. Dic. 2020. doi:10.5281/zenodo.4300328. url:https://doi.org/10.5281/zenodo.4300328.
[15] Cormac Flanagan et al. “The Essence of Compiling with Continuations”. In: SIGPLAN Not. 39.4 (apr. 2004), pp. 502–514. issn: 0362-1340. doi:
10.1145/989393.989443. url: https://doi.org/10.1145/989393. 989443.
[16] Jan Martin Jansen. “Programming in the -Calculus: From Church to Scott and Back”. In: (gen. 2013). doi:10.1007/978-3-642-40355-2_12. [17] Andrew Kennedy. “Compiling with Continuations, Continued”. In: SIG-
PLAN Not. 42.9 (ott. 2007), pp. 177–190. issn: 0362-1340. doi:10.1145/ 1291220.1291179. url:https://doi.org/10.1145/1291220.1291179. [18] G.D. Plotkin. “Call-by-name, call-by-value and the -calculus”. In: Theo-
retical Computer Science 1.2 (1975), pp. 125–159. issn: 0304-3975. doi:
https : / / doi . org / 10 . 1016 / 0304 - 3975(75 ) 90017 - 1. url: http : //www.sciencedirect.com/science/article/pii/0304397575900171.