×

Safe operators: Brackets closed forever. Optimizing optimal \(\lambda\)-calculus implementations. (English) Zbl 0901.03017

Summary: Considerations from category theory described in an earlier paper [A. Asperti, Ann. Soc. Math. Pol., Ser. IV, Fundam. Inf. 22, No. 1-2, 3-22 (1995; Zbl 0818.03007)] have permitted to add new rewriting rules for optimal reductions of the \(\lambda\)-calculus. These rules produce an impressive improvement in the performance of the reduction system, and provide a first step towards the solution of the well-known and crucial problem of accumulation of control operators. In this paper, after an introduction to optimal reductions, we exhibit the aforementioned problem and prove the correctness of the new rules.

MSC:

03B40 Combinatory logic and lambda calculus
68N01 General topics in the theory of software
68Q42 Grammars and rewriting systems
03B70 Logic in computer science
Full Text: DOI