A fast algorithm for translating combinator expressions with BC-chains (Q1096387)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A fast algorithm for translating combinator expressions with BC-chains |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A fast algorithm for translating combinator expressions with BC-chains |
scientific article |
Statements
A fast algorithm for translating combinator expressions with BC-chains (English)
0 references
1987
0 references
A fast algorithm is presented for translating lambda expressions to combinator trees with BC-chains. The time complexity of this algorithm is O(n log n) in the worst case, where n is the length of an input expression. Furthermore it requires only O(n log n) working space. This result achieves a substantial improvement to the previously known algorithm having the quadratic complexity. The basic idea of the algorithm may be applied to practical processing systems, whether they use BC-chains or not.
0 references
abstraction algorithm
0 references
functional programming
0 references
fast algorithm
0 references
lambda expressions
0 references
combinator trees with BC-chains
0 references
