The expression can also be represented as a directed acyclic graph, allowing sub-expressions to be shared:
Combinator graph reduction is a fundamental implementation technique for functional programming languages, in which a program is converted into a combinator representation which is mapped to a directed graph data structure in computer memory, and program execution then consists of rewriting parts of this graph ("reducing" it) so as to move towards useful results.
The concept of a graph reduction that allows evaluated values to be shared was first developed by Chris Wadsworth in his 1971 Ph.D.
In 1976 David Turner incorporated lazy evaluation into SASL using combinators.
[3] SASL was an early functional programming language first developed by Turner in 1972.