A fast algorithm for translating combinator expressions with BC-chains (Q1096387): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/bf03037465 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2045428044 / rank | |||
Normal rank |
Latest revision as of 10:51, 30 July 2024
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