Quantitative Aspects of Linear and Affine Closed Lambda Terms

DOI10.1145/3173547MaRDI QIDQ4581460zbMATH OpenOpenAlexWikidataFDO

Authors Pierre Lescanne

Publication date 20 August 2018

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.03085

zbMATH Keywords

combinatoricsfunctional programminglambda calculus

Mathematics Subject Classification ID

Combinatory logic and lambda calculus (03B40) Functional programming and lambda calculus (68N18)

Abstract: Affine $lambda$-terms are $lambda$-terms in which each bound variable occurs at most once and linear $lambda$-terms are $lambda$-terms in which each bound variables occurs once. and only once. In this paper we count the number of closed affine $lambda$-terms of size $n$, closed linear $lambda$-terms of size $n$, affine $$-normal forms of size $n$ and linear $$-normal forms of ise $n$, for different ways of measuring the size of $lambda$-terms. From these formulas, we show how we can derive programs for generating all the terms of size $n$ for each class. For this we use a specific data structure, which are contexts taking into account all the holes at levels of abstractions.

Recommendations

• Quantities related to the openness constant of linear operators
• On the lambda function and a quantification of Torhorst theorem
• Quantities related to upper and lower semi-Fredholm type linear relations
• A note on discriminability of lambda terms
• Linear lambda terms as invariants of rooted trivalent maps
• A quantitative Coulhon-Lamberton theorem
• On the quantization of linear maps
• On Certain Densely Invariant Quantities of Linear Operators
• scientific article; zbMATH DE number 1222102

Cited in

(9)

• On uniquely closable and uniquely typable skeletons of lambda terms
• A hiking trip through the orders of magnitude: deriving efficient generators for closed simply-typed lambda terms and normal forms
• Counting a type's (principal) inhabitants
• A note on discriminability of lambda terms
• Deriving efficient sequential and parallel generators for closed simply-typed lambda terms and normal forms
• Counting environments and closures
• scientific article; zbMATH DE number 7455712 (Why is no real title available?)
• Sampling -normal linear -terms
• Linear lambda terms as invariants of rooted trivalent maps

This page was built for publication: Quantitative Aspects of Linear and Affine Closed Lambda Terms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4581460)