Fold-Unfold Transformations on State Monadic Interpreters

摘要: In this paper we advocate the use of fold-unfold transformations for mastering complexity abstract machines intended real implementations. The idea is to express machine as an interpreter in a purely functional language. initial should be ‘obviously correct’ (but might inefficient — don’t care at point). Fold-unfold are then used remove inefficiencies interpreter/abstract machine. We illustrate by deriving (the equivalent of) e-scheme G-machine from composition C and EVAL instruction. This first done on call-by-name (tree reduction) interpreter. To model sharing graph manipulation that goes reduction implementation, state monads. do same transformation monadic It much less straightforward transform interpreter, have lean heavily laws monad. return can said better implementation.