Substitute.hs

module Substitute where
import Recursive

The intention with class Subst is that subst s e applies the subsitution s to all variables occuring in e.

It is assumed that name capture will not happen, i.e., s does not affect variables that are bound in (parts of) e, and if x is free in e, s x does not contain variables that become bound when substituted into e.

class Subst i e | e->i where
  subst :: (i->e) -> e->e

The intention with class MapExp is that mapExp f e applies the function f to every expression occuring in a larger structure (e.g., a list of declarations). Instances of Subst will typically make use of instances of MapExp.

class MapExp e s | s->e where
  mapExp :: (e->e) -> s->s

instance MapExp e s => MapExp e [s] where mapExp = map . mapExp

esubst = mapExp . subst

esubst1 var e x = esubst s
  where
    s y = if y==x then e else var y

mapExpRec = mapRec . mapExp

{-
class Subst i e s1 s2 | e->i,s1->i, where
  subst :: (i->e)->s1->s2
-}