Jagiellonian University Repository

Combinatorics of explicit substitutions

Combinatorics of explicit substitutions

Show full item record

dc.contributor.author Bendkowski, Maciej [SAP14013025] pl
dc.contributor.author Lescanne, Pierre pl
dc.date.accessioned 2018-09-14T09:33:52Z
dc.date.available 2018-09-14T09:33:52Z
dc.date.issued 2018 pl
dc.identifier.isbn 978-1-4503-6441-6 pl
dc.identifier.uri https://ruj.uj.edu.pl/xmlui/handle/item/56971
dc.language eng pl
dc.rights Dodaję tylko opis bibliograficzny *
dc.rights.uri *
dc.title Combinatorics of explicit substitutions pl
dc.type BookSection pl
dc.pubinfo New York : ACM pl
dc.abstract.en \lambda υ is an extension of the \lambda -calculus which internalises the calculus of substitutions. In the current paper, we investigate the combinatorial properties of \lambda υ focusing on the quantitative aspects of substitution resolution. We exhibit an unexpected correspondence between the counting sequence for \lambda υ-terms and famous Catalan numbers. As a by-product, we establish effective sampling schemes for random \lambda υ-terms. We show that typical \lambda υ-terms represent, in a strong sense, non-strict computations in the classic \lambda -calculus. Moreover, typically almost all substitutions are in fact suspended, i.e. unevaluated, under closures. Consequently, we argue that \lambda υ is an intrinsically non-strict calculus of explicit substitutions. Finally, we investigate the distribution of various redexes governing the substitution resolution in \lambda υ and investigate the quantitative contribution of various substitution primitives. pl
dc.description.publication 0,81 pl
dc.description.conftype international pl
dc.identifier.doi 10.1145/3236950.3236951 pl
dc.title.container Proceedings of the 20th International Symposium on Principles and Practice of Declarative Programming pl
dc.language.container eng pl
dc.affiliation Wydział Matematyki i Informatyki : Zespół Katedr i Zakładów Informatyki Matematycznej pl
dc.subtype ConferenceProceedings pl
dc.conference PPDP '18 Proceedings of the 20th International Symposium on Principles and Practice of Declarative Programming; 2018-09-03; 2018-09-05; Frankfurt; Niemcy; ; indeksowana w Scopus ; pl
dc.identifier.articleid 7 pl
dc.rights.original bez licencji pl
dc.identifier.project ROD UJ / O pl
dc.sourceinfo liczba autorów 60; liczba stron 230; liczba arkuszy wydawniczych 18,8; pl

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)