Atze Dijkstra, Arie Middelkoop and S. Doaitse Swierstra, 2008
Abstract: Implementations of language processing systems often use unification and substitution to compute desired properties of input language fragments; for example when inferring a type for an expression. Purely functional implementations of unification and substitution usually directly correspond to the formal specification of language properties. Unfortunately the concise and understandable formulation comes with gross inefficiencies. A seond appoach is to focus on efficiency of implementation. However, efficient implementations of unification and substitution forgo pure functionality and rely on side effects. We present a third, ‘best of both worlds’, solution, which is both purely functional and efficient by simulating side effects functionally.We compare the three approaches side by side on implementation and performance.