Compile-Time Pointer Reversal
This paper introduces an alternative representation for λ-terms which has the notable property that the search for the leftmost outermost redex is restricted to two steps. This is important in the implementation of a lazy functional programming language, as this search consumes time and space. The r...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Text |
| Language: | English |
| Published: |
1996
|
| Subjects: | |
| Online Access: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.5505 http://greyarea.is.tsukuba.ac.jp/journal/jflp/articles/1996/A96-03/JFLP-A96-03.ps.gz |
| Summary: | This paper introduces an alternative representation for λ-terms which has the notable property that the search for the leftmost outermost redex is restricted to two steps. This is important in the implementation of a lazy functional programming language, as this search consumes time and space. The representation introduced is similar to that resulting from the implementation technique of reversing pointers in the left spine of a term while traversing it, except that here the pointers in the left spine are reversed before reduction. This paper completely develops this new representation, including rigourous proofs of the correctness as a representation for -terms and a number of properties, such as the restriction on the search for the next redex. It is shown that the representation can be used with graphs, hence it can be used as the basis for an implementation of a lazy functional language. An implementation is introduced and its performance is compared with a conventional implementati. |
|---|