Deriving Efficient Sequential and Parallel Generators for Closed Simply-Typed Lambda Terms and Normal Forms

DOI10.3233/FI-2020-1994zbMath1497.68088OpenAlexW3111730893MaRDI QIDQ4988930

Paul Tarau

Publication date: 20 May 2021

Published in: Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3233/fi-2020-1994

zbMATH Keywords

normal formstype inferencelogic programming transformationsparallel combinatorial generation algorithmsProlog multi-threadingsequential combinatorial generation algorithmssimply-typed lambda terms

Mathematics Subject Classification ID

Logic programming (68N17) Combinatory logic and lambda calculus (03B40)

Uses Software

• Automath
• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The lambda calculus. Its syntax and semantics. Rev. ed.
• Intuitionistic propositional logic is polynomial-space complete
• \(\lambda\) to SKI, semantically -- declarative pearl
• 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
• Types for proofs and programs. International conference, TYPES 2007, Cividale des Friuli, Italy, May 2--5, 2007. Revised selected papers
• A Natural Counting of Lambda Terms
• The YAP Prolog system
• SWI-Prolog
• Ranking/Unranking of Lambda Terms with Compressed de Bruijn Indices
• Efficient generation of test data structures using constraint logic programming and program transformation
• Random generation of closed simply typed λ-terms: A synergy between logic programming and Boltzmann samplers
• Asymptotically almost all \lambda-terms are strongly normalizing
• Introduction to generalized type systems
• The full-reducing Krivine abstract machine KN simulates pure normal-order reduction in lockstep: A proof via corresponding calculus
• Lambda terms of bounded unary height
• Counting and generating terms in the binary lambda calculus
• Counting and generating lambda terms

This page was built for publication: Deriving Efficient Sequential and Parallel Generators for Closed Simply-Typed Lambda Terms and Normal Forms