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 |