A fast algorithm for translating combinator expressions with BC-chains (Q1096387)

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.