The Typed Polymorphic Label-Selective Lambda-Calculus

Jacques Garrigue and Hassan Aït-Kaci. In Proc. of the 21st ACM Symposium on Principles of Programming Languages. Portland, 1994.

Abstract. Formal calculi on record structures have recently been a focus of active research. However, scarcely anyone has studied formally the dual notion - i.e. argument-passing to functions by keywords, and its harmonization with currying. We have.

Recently, we introduced the label-selective lambda-calculus, a conservative extension of lambda-calculus that uses a labeling of abstractions and applications to perform unordered currying. In other words, it enables some form of commutation between arguments. This improves program legibility, thanks to the presence of labels, and efficiency, thanks to argument commuting.

In this paper, we propose a simply typed version of the calculus, then extend it to one with ML-like polymorphic types. For the latter calculus, we establish the existence of principal types and we give an algorithm to compute them. Thanks to the fact that label-selective lambda-calculus is a conservative extension of lambda-calculus by adding numeric labels to stand for argument positions, its polymorphic typing provides us with a keyword argument-passing extension of ML abviating the need of records. In this context, conventional ML syntax can be seen as a restriction of the more general keyword-oriented syntax limited to using only implicit positions instead of keywords.

You can get the postcript version of this paper (61396 bytes), or the PDF version popl94-typed-sel-a4.pdf (212718 bytes). It appeared as well as DEC PRL report 35, (87227 bytes).

JG 2024.03.15