Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-26T05:50:16.274Z Has data issue: false hasContentIssue false
  • English
  • Français

Tight typings and split bounds, fully developed

Part of: ICFP2018

Published online by Cambridge University Press:  19 May 2020

BENIAMINO ACCATTOLI Open the ORCID record for BENIAMINO ACCATTOLI [Opens in a new window] ,
STÉPHANE GRAHAM-LENGRAND  and
DELIA KESNER
BENIAMINO ACCATTOLI
Affiliation:
Inria & LIX, École Polytechnique, UMR 7161, Palaiseau, France (e-mail: [email protected])
STÉPHANE GRAHAM-LENGRAND
Affiliation:
SRI International, USA (e-mail: [email protected])
DELIA KESNER
Affiliation:
IRIF, CNRS, Université de Paris & Institut Universitaire de France, France (e-mail: [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Multi types – aka non-idempotent intersection types – have been used. to obtain quantitative bounds on higher-order programs, as pioneered by de Carvalho. Notably, they bound at the same time the number of evaluation steps and the size of the result. Recent results show that the number of steps can be taken as a reasonable time complexity measure. At the same time, however, these results suggest that multi types provide quite lax complexity bounds, because the size of the result can be exponentially bigger than the number of steps. Starting from this observation, we refine and generalise a technique introduced by Bernadet and Graham-Lengrand to provide exact bounds. Our typing judgements carry counters, one measuring evaluation lengths and the other measuring result sizes. In order to emphasise the modularity of the approach, we provide exact bounds for four evaluation strategies, both in the λ-calculus (head, leftmost-outermost, and maximal evaluation) and in the linear substitution calculus (linear head evaluation). Our work aims at both capturing the results in the literature and extending them with new outcomes. Concerning the literature, it unifies de Carvalho and Bernadet & Graham-Lengrand via a uniform technique and a complexity-based perspective. The two main novelties are exact split bounds for the leftmost strategy – the only known strategy that evaluates terms to full normal forms and provides a reasonable complexity measure – and the observation that the computing device hidden behind multi types is the notion of substitution at a distance, as implemented by the linear substitution calculus.

Type
Research Article
Information
Journal of Functional Programming , Volume 30 , 2020 , e14
Copyright
© The Author(s), 2020. Published by Cambridge University Press

References

Accattoli, B. (2012) An abstract factorization theorem for explicit substitutions. In RTA’12. LIPIcs, Tiwari, A. (ed.), vol. 15, Nagoya, Japan. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 6–21.Google Scholar
Accattoli, B. (2018a) (In)Efficiency and reasonable cost models. Electr. Notes Theor. Comput. Sci. 338, 23–43. https://doi.org/10.1016/j.entcs.2018.10.003CrossRefGoogle Scholar
Accattoli, B. (2018b) Proof nets and the linear substitution calculus. In Theoretical Aspects of Computing - ICTAC 2018 - 15th International Colloquium, October 16–19, 2018, Proceedings, Stellenbosch, South Africa. Springer, pp. 37–61. https://doi.org/10.1007/978-3-030-02508-3_3CrossRefGoogle Scholar
Accattoli, B., Bonelli, E., Kesner, D. & Lombardi, C. (2014) A nonstandard standardization theorem. In POPL 2014, Jagannathan, S. & Sewell, P. (eds), San Diego, California, USA. ACM, pp. 659–670.CrossRefGoogle Scholar
Accattoli, B. & Dal Lago, U. (2012) On the invariance of the unitary cost model for head reduction. In RTA’12. LIPIcs, Tiwari, A. (ed.), vol. 15, Nagoya, Japan. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 22–37.Google Scholar
Accattoli, B. & Dal Lago, U. (2016) (Leftmost-Outermost) Beta-reduction is invariant, indeed. Log. Methods Comput. Sci. 12(1), 1–46.CrossRefGoogle Scholar
Accattoli, B., Graham-Lengrand, S. & Kesner, D. (2018). Tight typings and split bounds. PACMPL 2(ICFP), 94:1–94:30. https://doi.org/10.1145/3236789Google Scholar
Accattoli, B. & Guerrieri, G. (2018) Types of fireballs. In Programming Languages and Systems - 16th Asian Symposium, APLAS 2018, December 2–6, 2018, Proceedings, Wellington, New Zealand. Springer, pp. 45–66. https://doi.org/10.1007/978-3-030-02768-1_3CrossRefGoogle Scholar
Accattoli, B., Guerrieri, G. & Leberle, M. (2019). Types by need. In Programming Languages and Systems - 28th European Symposium on Programming, ESOP 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, April 6–11, 2019, Proceedings, Prague, Czech Republic. Springer, pp. 410–439. https://doi.org/10.1007/978-3-030-17184-1_15CrossRefGoogle Scholar
Accattoli, B. & Kesner, D. (2010) The structural λ-calculus. In CSL’10, Brno, Czech Republic. Springer, pp. 381–395.CrossRefGoogle Scholar
Alves, S., Kesner, D. & Ventura, D. (2019). A Quantitative Understanding of Pattern Matching. CoRR abs/1912.01914.arXiv:1912.01914. http://arxiv.org/abs/1912.01914Google Scholar
Avanzini, M. & Dal Lago, U. (2017). Automating sized-type inference for complexity analysis. PACMPL 1, ICFP, 43:1–43:29.Google Scholar
Benedetti, E. D. & Ronchi Della Rocca, S. (2016). A type assignment for λ-calculus complete both for FPTIME and strong normalization. Inf. Comput. 248, 195–214.CrossRefGoogle Scholar
Bernadet, A. & Graham-Lengrand, S. (2013a). A Big-Step Operational Semantics via Non-idempotent Intersection Types. Technical report. http://www.lix.polytechnique.fr/lengrand/Work/Reports/BigStep.pdfGoogle Scholar
Bernadet, A. & Graham-Lengrand, S. (2013b) Non-idempotent intersection types and strong normalisation. Log. Methods Comput. Sci. 9(4), 1–46.CrossRefGoogle Scholar
Bernadet, A. & Lengrand, S. (2011). Complexity of strongly normalising lambda-terms via non-idempotent intersection types. In FoSSaCS’11. Lecture Notes in Computer Science, Hofmann, M. (ed.), vol. 6604, Saarbrücken, Germany. Springer, pp. 88–107.Google Scholar
Blelloch, G. E. and Greiner, J. (1995) Parallelism in sequential functional languages. In FPCA’95, Williams, J. (ed.), La Jolla, California, USA. ACM, pp. 226–237.CrossRefGoogle Scholar
Bucciarelli, A. & Ehrhard, T. (2001). On phase semantics and denotational semantics: The exponentials. Ann. Pure Appl. Logic 109(3), 205–241.CrossRefGoogle Scholar
Bucciarelli, A., Ehrhard, T. & Manzonetto, G. (2012). A relational semantics for parallelism and non-determinism in a functional setting. Ann. Pure Appl. Log. 163(7), 918–934.CrossRefGoogle Scholar
Bucciarelli, A., Kesner, D. and Ronchi Della Rocca, S. (2014) The inhabitation problem for non-idempotent intersection types. In IFIP-TCS’14. Lecture Notes in Computer Science, Díaz, J., Lanese, I. & Sangiorgi, D. (eds), vol. 8705, Rome, Italy. Springer, pp. 341–354.CrossRefGoogle Scholar
Bucciarelli, A., Kesner, D. & Ventura, D. (2017) Non-idempotent intersection types for the Lambda-Calculus. Log. J. IGPL 25(4), 431–464.CrossRefGoogle Scholar
Carraro, A. & Guerrieri, G. (2014) A semantical and operational account of call-by-value solvability. In FoSSaCS 2014. Lecture Notes in Computer Science, Muscholl, A. (ed.), vol. 8412, Grenoble, France. Springer, pp. 103–118.Google Scholar
Coppo, M. and Dezani-Ciancaglini, M. (1978). A new type assignment for lambda-terms. Arch. Math. Log. 19, 139–156.CrossRefGoogle Scholar
Coppo, M. and Dezani-Ciancaglini, M. (1980). An extension of the basic functionality theory for the λ-calculus. Notre Dame J. Formal Log. 4, 685–693.CrossRefGoogle Scholar
Dal Lago, U. & Gaboardi, M. (2011). Linear dependent types and relative completeness. Log. Methods Comput. Sci. 8(4). https://doi.org/10.2168/LMCS-8(4:11)2012Google Scholar
Dal Lago, U. & Petit, B. (2013) The geometry of types. In The 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL’13, Rome, Italy - January 23–25, 2013, pp. 167–178. https://doi.org/10.1145/2429069.2429090CrossRefGoogle Scholar
Dal Lago, U. & Petit, B. (2014). Linear dependent types in a call-by-value scenario. Sci. Comput. Program. 84, 77–100. https://doi.org/10.1016/j.scico.2013.07.010CrossRefGoogle Scholar
Danos, V. & Regnier, L. (2004) Head Linear Reduction. Technical report.Google Scholar
de Carvalho, D. (2007) Sémantiques de la logique linéaire et temps de calcul. Thèse de Doctorat. Université Aix-Marseille II.Google Scholar
de Carvalho, D. (2009). Execution Time of lambda-Terms via Denotational Semantics and Intersection Types. CoRR abs/0905.4251, pp. 1–36.Google Scholar
de Carvalho, D. (2016) The relational model is injective for multiplicative exponential linear logic. In CSL 2016. LIPIcs, Talbot, J.-M. & Regnier, L. (eds), vol. 62, Marseille, France. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 41:1–41:19.Google Scholar
de Carvalho, D. (2018) Execution time of λ-terms via denotational semantics and intersection types. Math. Struct. Comput. Sci. 28(7), 1169–1203. https://doi.org/10.1017/S0960129516000396CrossRefGoogle Scholar
de Carvalho, D., Pagani, M. & Tortora de Falco, L. (2011) A semantic measure of the execution time in linear logic. Theor. Comput. Sci. 412(20), 1884–1902.CrossRefGoogle Scholar
de Carvalho, D. & Tortora de Falco, L. (2016) A semantic account of strong normalization in linear logic. Inf. Comput. 248, 104–129.CrossRefGoogle Scholar
Díaz-Caro, A., Manzonetto, G. & Pagani, M. (2013) Call-by-value non-determinism in a linear logic type discipline. In LFCS 2013. Lecture Notes in Computer Science, Artëmov, S. N. & Nerode, A. (eds.), vol. 7734, San Diego, California, USA. Springer, pp. 164–178.CrossRefGoogle Scholar
Dudenhefner, A. & Rehof, J. (2017) Intersection type calculi of bounded dimension. In POPL’17, Castagna, G. & Gordon, A. D. (eds.), Paris, France. ACM, pp. 653–665.Google Scholar
Ehrhard, T. (2012) Collapsing non-idempotent intersection types. In CSL’12. LIPIcs, Cégielski, P. & Durand, A. (eds.), vol. 16, Fontainebleau, France. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 259–273.Google Scholar
Ehrhard, T. & Guerrieri, G. (2016) The Bang Calculus: An untyped lambda-calculus generalizing call-by-name and call-by-value. In PPDP 2016, Edinburgh, UK. ACM, pp. 174–187.CrossRefGoogle Scholar
Gardner, P. (1994) Discovering needed reductions using type theory. In TACS’94. Lecture Notes in Computer Science, Hagiya, M. and Mitchell, J. C. (eds), vol. 789, Sendai, Japan. Springer, pp. 555–574.Google Scholar
Girard, J.-Y. (1988) Normal functors, power series and the λ-calculus. Ann. Pure Appl. Log. 37, 129–177.CrossRefGoogle Scholar
Girard, J.-Y., Taylor, P. & Lafont, Y. (1989) Proofs and Types. New York, NY, USA: Cambridge University Press.Google Scholar
Grabmayer, C. (2018) Modeling terms by graphs with structure constraints (two illustrations). In Proceedings Tenth International Workshop on Computing with Terms and Graphs, TERMGRAPH@FSCD 2018, Oxford, UK, 7th July 2018, pp. 1–13. https://doi.org/10.4204/EPTCS.288.1CrossRefGoogle Scholar
Guerrieri, G., Pellissier, L. and Tortora de Falco, L. (2016) Computing connected proof(-structure)s from their Taylor expansion. In FSCD 2016. LIPIcs, Kesner, D. & Pientka, B. (eds), vol. 52, Porto, Portugal. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 20:1–20:18.Google Scholar
Hoffmann, J., Aehlig, K. & Hofmann, M. (2012) Resource aware ML. In CAV 2012. Lecture Notes in Computer Science, Madhusudan, P. & Seshia, S. A. (eds), vol. 7358, Berkeley, CA, USA. Springer, pp. 781–786.Google Scholar
Hoffmann, J. & Hofmann, M. (2010) Amortized resource analysis with polynomial potential - a static inference of polynomial bounds for functional programs. In ESOP’10. Lecture Notes in Computer Science, Gordon, A. D. (ed.), vol. 6012, Paphos, Cyprus. Springer, pp. 287–306.Google Scholar
Hofmann, M. & Jost, S. (2003) Static prediction of heap space usage for first-order functional programs. In POPL 2003, Aiken, A. & Morrisett, G. (eds), New Orleans, Louisisana, USA. ACM, pp. 185–197.CrossRefGoogle Scholar
Hughes, J., Pareto, L. & Sabry, A. (1996) Proving the correctness of reactive systems using sized types. In POPL’96, Boehm, H.-J. & Steele Jr., G. L. (eds), St. Petersburg Beach, Florida, USA. ACM, pp. 410–423.CrossRefGoogle Scholar
Jost, S., Vasconcelos, P. B., Florido, M. and Hammond, K. (2017) Type-based cost analysis for lazy functional languages. J. Autom. Reason. 59(1), 87–120.CrossRefGoogle Scholar
Kesner, D. & Conchúir, S. (2008) Milner’s Lambda Calculus with Partial Substitutions. Technical report. Paris 7 University. http://www.pps.univ-paris-diderot.fr/~kesner/papers/shortpartial.pdfGoogle Scholar
Kesner, D. & Ventura, D. (2014) Quantitative types for the linear substitution calculus. In IFIP-TCS’14. Lecture Notes in Computer Science, Díaz, J., Lanese, I. & Sangiorgi, D. (eds), vol. 8705, Rome, Italy. Springer, pp. 296–310.CrossRefGoogle Scholar
Kesner, D. & Ventura, D. (2015) A resource aware computational interpretation for Herbelin’s syntax. In ICTAC 2015. Lecture Notes in Computer Science, Leucker, M., Rueda, C. & Valencia, F. D. (eds), vol. 9399, Cali, Colombia. Springer, 388–403.Google Scholar
Kesner, D. & Vial, P. (2017) Types as resources for classical natural deduction. In FSCD 2017. LIPIcs, Miller, D. (ed.), vol. 84, Oxford, UK. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 24:1–24:17.Google Scholar
Kesner, D. & Vial, P. (2019) Non-idempotent types for classical calculi in natural deduction style. Log. Methods Comput. Sci. 16(1). https://lmcs.episciences.org/6028Google Scholar
Kesner, D., Viso, A. & Ríos, A. (2018) Call-by-need, neededness and all that. In FoSSaCS’18. Lecture Notes in Computer Science, Baier, C. & Dal Lago, U. (eds.), vol. 10803, Thessaloniki, Greece. Springer, pp. 241–257.Google Scholar
Kfoury, A. J. (2000) A linearization of the Lambda-calculus and consequences. J. Logic Comput. 10(3), 411–436.CrossRefGoogle Scholar
Klop, J. W. (1980) Combinatory Reduction Systems. PhD thesis. Utrecht University.Google Scholar
Krivine, J.-L. (1993) Lambda-Calculus, Types and Models. Ellis Horwood.Google Scholar
Mascari, G. & Pedicini, M. (1994) Head linear reduction and pure proof net extraction. Theor. Comput. Sci. 135(1), 111–137.CrossRefGoogle Scholar
Mazza, D., Pellissier, L. & Vial, P. (2018) Polyadic approximations, fibrations and intersection types. PACMPL 2(POPL), 6:1–6:28.Google Scholar
Milner, R. (2007) Local bigraphs and confluence: Two conjectures. Electr. Notes Theor. Comput. Sci. 175(3), 65–73.CrossRefGoogle Scholar
Neergaard, P. M. & Mairson, H. G. (2004) Types, potency, and idempotency: Why nonlinearity and amnesia make a type system work. In ICFP 2004, Okasaki, C. & Fisher, K. (eds), Snowbird, Utah, USA. ACM, pp. 138–149.CrossRefGoogle Scholar
Ong, C.-H. L. (2017) Quantitative semantics of the lambda calculus: Some generalisations of the relational model. In LICS 2017, Ouaknine, J. (ed.), Reykjavik, Island. IEEE Computer Society, pp. 1–12.CrossRefGoogle Scholar
Paolini, L., Piccolo, M. & Rocca, S. R. D. (2017) Essential and relational models. Math. Struct. Comput. Sci. 27(5), 626–650.CrossRefGoogle Scholar
Portillo, Á. J. R., Hammond, K., Loidl, H.-W. & Vasconcelos, P. B. (2002) Cost analysis using automatic size and time inference. In IFL 2002. Lecture Notes in Computer Science, Pena, R. & Arts, T. (eds), vol. 2670, Madrid, Spain. Springer, pp. 232–248.Google Scholar
Pottinger, G. (1980) A type assignment for the strongly normalizable λ-terms. In To H.B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism, Seldin, J. P. & Hindley, J. R. (eds). Academic Press, pp. 561–578.Google Scholar
Simões, H. R., Hammond, K., Florido, M. & Vasconcelos, P. B. (2007) Using intersection types for cost-analysis of higher-order polymorphic functional programs. In TYPES 2006, Revised Selected Papers. Lecture Notes in Computer Science, Altenkirch, T. & McBride, C. (eds), vol. 4502, Nottingham, UK. Springer, pp. 221–236.Google Scholar
Urzyczyn, P. (1999) The emptiness problem for intersection types. J. Symb. Logic 64(3), 1195–1215.CrossRefGoogle Scholar
Urzyczyn, P. (2009) Inhabitation of low-rank intersection types. In TLCA 2009. Lecture Notes in Computer Science, Curien, P.-L. (ed.), vol. 5608. Springer, pp. 356–370.CrossRefGoogle Scholar
van Raamsdonk, F., Severi, P., Sørensen, M. H. & Xi, H. (1999) Perpetual reductions in lambda-calculus. Inf. Comput. 149(2), 173–225.CrossRefGoogle Scholar
Vasconcelos, P. B. & Hammond, K. (2004) Inferring cost equations for recursive, polymorphic and higher-order functional programs. In IFL 2003, Revised Papers. Lecture Notes in Computer Science, vol. 3145, Edinburgh, UK. Springer, pp. 86–101.CrossRefGoogle Scholar
Submit a response

Discussions

No Discussions have been published for this article.