Is the Optimal Implementation Inefficient? Elementarily Not

DOI10.4230/LIPICS.FSCD.2017.17MaRDI QIDQ5111313zbMATH OpenOpenAlexFDO

Authors Marco Solieri, Stefano Guerrini

Publication date 26 May 2020

Full work available at URL https://hal.inria.fr/hal-01644123

zbMATH Keywords

optimalitycomplexitylinear logic\(\lambda\)-calculussharing graphs

Mathematics Subject Classification ID

Cut-elimination and normal-form theorems (03F05) Combinatory logic and lambda calculus (03B40) Proof-theoretic aspects of linear logic and other substructural logics (03F52) Functional programming and lambda calculus (68N18)

Recommendations

• A general theory of sharing graphs
• Optimality and inefficiency: what isn't a cost model of the lambda calculus?
• Sharing implementations of graph rewriting systems
• scientific article; zbMATH DE number 1523048
• On the dynamics of sharing graphs

Cites work

• scientific article; zbMATH DE number 4123722 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 1418450 (Why is no real title available?)
• (Leftmost-outermost) beta reduction is invariant, indeed
• (Optimal) duplication is not elementary recursive
• Coherence for sharing proof-nets
• Context semantics, linear logic, and computational complexity
• Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine
• Intuitionistic light affine logic
• Light linear logic
• Light logics and optimal reduction: completeness and complexity
• On Constructor Rewrite Systems and the Lambda-Calculus
• Parallel beta reduction is not elementary recursive
• The bologna optimal higher-order machine
• The optimal implementation of functional programming languages
• The typed lambda-calculus is not elementary recursive

Cited in

(7)

• On the dynamics of sharing graphs
• (Optimal) duplication is not elementary recursive
• Bottom-up \(\beta\)-reduction: uplinks and \(\lambda\)-DAGs
• Optimality and inefficiency: what isn't a cost model of the lambda calculus?
• scientific article; zbMATH DE number 1523048 (Why is no real title available?)
• (In)efficiency and reasonable cost models
• Sharing implementations of graph rewriting systems

This page was built for publication: Is the Optimal Implementation Inefficient? Elementarily Not

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