Categorical abstract machines for higher-order typed lambda-calculi
Curien's CAM is an environment machine for the untyped lambda -calculus based on cartesian closed categories (CCC's). This categorical model represents both environments and terms by morphisms regardless of their conceptual difference. We show that Ehrhard's D-categories yield a nice...
| Main Author: | |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
1994
|
| Subjects: |
| Summary: | Curien's CAM is an environment machine for the untyped lambda -calculus based on cartesian closed categories (CCC's). This categorical model represents both environments and terms by morphisms regardless of their conceptual difference. We show that Ehrhard's D-categories yield a nice way of separating these two notions. Based on suitable categorical combinators for these D-categories we derive an eager and a lazy abstract machine. These machines specialize to the CAM and to Krivine's machine respectively. D-categories extended with additional structure to model the calculus of constructions yield generalizations of the CAM and Krivine's machine to this higher-order lambda -calculus. We also obtain an algorithm for type checking of these combinators, which uses the above reduction machines. Tests using Church-numerals show that the abstract machines are quite efficient compared to other implementations. |
|---|