anchor.diff:              let node = Var("node", typeof<obj>)
               
               let run t = typedefof<ITraversal<_>>.MakeGenericType([|t|]).GetMethod("Run")
  +
  +
  +            let runInherit (t : Type) (n : string) =
  +                if n = name then
  +                    Expr.Call(Expr.Var traversal, run t, [Expr.Var node])
  +                else
  +                    let t = getTraversal n t
  +                    let t = Expr.Call(t, t.Type.GetMethod "WithState", [Expr.PropertyGet(Expr.Var traversal, traversal.Type.GetProperty "State")])
  +
  +                    Expr.Call(t, t.Type.GetMethod "Run", [Expr.Var node])
   
               let rec build (sfs : list<SemanticFunction>) =
                   match sfs with
  
positive.code:                                         if Set.contains n strictInh then
                                              let get = traversalGetValue.MakeGenericMethod [| v.Type |]
                                              Expr.Call(Expr.Var traversal, get, [Expr.Value n])
  
                                          else
                                              if n = name then
                                                  let get = run v.Type
                                                  Expr.Call(Expr.Var traversal, get, [Expr.Var node])
                                              else
                                                  let t = getTraversal n v.Type
                                                  let get = run v.Type
                                                  Expr.Call(t, get, [Expr.Var node])
  
                                      v, replacement
                                     )
  
negative.code:                 )
  
              
              // replace all attribute-lookups with traversal-calls and add the traversal argument
              // to all semantic functions
              let definitions = 
                  let convert (t : Type) (e : Expr) = Expr.Coerce(e, t)
  
                  let rec getInfo (strictInh : HashSet<string>) (strictSyn : HashSet<string>) (attType : ref<Type>) (kind : ref<SemanticFunctionKind>) (e : Expr) =
                      match e with
                          | Application(Call(None, mi, [o; Value(:? string as nn, _)]), Value(_)) when mi.Name = "op_Dynamic" ->
                              // syn case
                              kind := Synthesize
                              strictSyn.Add nn |> ignore
                     
  
                          | Call(None, mi, [o; Value(:? string as nn, _)]) when mi.Name = "op_Dynamic" ->
                              strictInh.Add nn |> ignore
  
                          | Call(None, mi, [_; value]) when mi.Name = "op_LessLessEquals" ->
                              attType := value.Type
  
  
                          | ShapeVar(v) ->
                              ()
  
                          | ShapeLambda(v,b) ->
                              getInfo strictInh strictSyn attType kind b
  
                          | ShapeCombination(o, args) ->
                              args |> List.iter (getInfo strictInh strictSyn attType kind)
  
  
                  definitions |> List.choose (fun d ->
                      match d.definition with
                          | Lambda(nodeVar,body) ->
                              let kind = ref Synthesize
                              let strictInh = HashSet()
                              let strictSyn = HashSet()
                              let attType = ref body.Type
                              getInfo strictInh strictSyn attType kind body
                              strictInh.Remove d.name |> ignore
                
                              let (|RootVar|_|) (v : Var) = 
                                  let t = v.Type
                                  if t.IsGenericType && t.GetGenericTypeDefinition() = typedefof<Root<_>> then
                                      let t = t.GetGenericArguments().[0]
                                      Some t
                                  else
                                      None
  
                              let isRoot, nodeVar =
                                  match nodeVar with
                                      | RootVar t ->
                                          true, Var("caller", t)
                                      | _ -> 
                                          false, nodeVar
                        
  
                              let res = 
                                  { d with 
                                      definition = Expr.Lambda(nodeVar, body) 
                                      kind = !kind
                                      strictInh = Set.ofSeq strictInh
                                      strictSyn = Set.ofSeq strictSyn
                                      isRoot = isRoot
                                      nodeType = nodeVar.Type
                                      valueType = !attType
                                  }
                              Some res
  
                          | _ ->
                              None
                      
                  )
  
  
              { cases = 
                  definitions
                      |> List.map (fun sf -> sf.nodeType, sf)
                      |> HashMap.ofList
              }
  
  
  
  module Test =
   
      type TraversalState(parent : Option<TraversalState>, node : obj, cache : Dictionary<string, Option<obj>>) =
          static let root = TraversalState(None, null, Dictionary.empty)
          static member Root = root
  
          member x.Parent = parent
          member x.Node = node
  
          member x.ChildState(n : obj) =
              if isNull node then TraversalState(None, n, Dictionary.empty)
              else TraversalState(Some x, n, Dictionary.empty)
  
  
          member x.TryGet(name : string) =
              match cache.TryGetValue name with
                  | (true, v) -> v
                  | _ -> None
  
          member x.Set(name : string, value : Option<obj>) =
              cache.[name] <- value
  
          member x.GetOrCreate(name : string, f : string -> Option<'a>) =
              match cache.TryGetValue name with
                  | (true, v) ->  v |> Option.map unbox
                  | _ ->
                      let v = f name
                      cache.[name] <- v |> Option.map (fun v -> v :> obj)
                      v
  
  
      type Root<'a> = class end
      type Inh = class end
      let inh = Unchecked.defaultof<Inh> 
  
      let (<<=) (i : Inh) (value : 'a) =
          ()
  
  
      type ITraversal<'a> =
          abstract member RunUnit : obj -> unit
          abstract member Run : obj -> 'a
          abstract member WithState : TraversalState -> ITraversal<'a>
          abstract member State : TraversalState
  
  
      type SynthesizeTraversal<'a>(syn : SynthesizeTraversal<'a> -> obj -> Option<'a>, state : TraversalState, strict : TraversalState -> obj -> unit) =
  
          member x.State : TraversalState = 
              state
  
          member x.WithState (state : TraversalState) =
              SynthesizeTraversal<'a>(syn, state, strict)
  
          member x.Run(o : obj) =
              let childState = state.ChildState o
              strict childState o
              syn (x.WithState childState) o |> Option.get
  
          member x.RunUnit(o : obj) : unit =
              failwith "not supported"
  
          member x.GetValue<'a>(name : string) =
              match state.TryGet(name) with
                  | Some (:? 'a as v) -> v
                  | _ -> failwith ""
  
          interface ITraversal<'a> with
              member x.Run(o) = x.Run(o)
              member x.RunUnit(o) = x.RunUnit(o)
              member x.WithState s = x.WithState s :> ITraversal<_>
              member x.State = x.State
  
      type InheritTraversal<'a>(name : string, inh : InheritTraversal<'a> -> obj -> Option<'a>, root : InheritTraversal<'a> -> obj -> Option<'a>, state : TraversalState) =
  
          member private x.create o name =
              match state.Parent with
                  | Some p -> inh (x.WithState p) p.Node
                  | None -> root x o
  
          member x.State : TraversalState = 
              state
  
          member x.WithState (state : TraversalState) =
              InheritTraversal<'a>(name, inh, root, state)
  
          member x.Run(o : obj) =
              state.GetOrCreate(name, x.create o) |> Option.get
   
          member x.RunUnit(o : obj) =
              state.GetOrCreate(name, x.create o) |> ignore
  
          member x.GetValue<'a>(name : string) =
              match state.TryGet(name) with
                  | Some (:? 'a as v) -> v
                  | _ -> failwith ""
  
          interface ITraversal<'a> with
              member x.Run(o) = x.Run(o)
              member x.RunUnit(o) = x.RunUnit(o)
              member x.WithState s = x.WithState s :> ITraversal<_>
              member x.State = x.State
                  
      type IList =
          abstract member Sum : TraversalState -> int
  
      type Nil() = 
          interface IList with
              member x.Sum(s) = s.TryGet "Index" |> Option.get |> unbox<int>
  
      type Cons(h : int, t : IList) =
          interface IList with
              member x.Sum(s) =
                  let i = s.TryGet "Index" |> Option.get |> unbox<int>
                  let s = s.ChildState(t)
                  s.Set("Index", Some ((i + 1) :> obj))
                  h + t.Sum(s)
  
          member x.Head = h
          member x.Tail = t
  
      let state : TraversalState = TraversalState.Root
  
      [<Semantic; ReflectedDefinition>]
      type Sems() =
  
  
          member x.Sum(n : Nil) : int =
              n?Index - n?Blubber + n?Bla - n?Gabbl + n?Gobbl
  
          member x.Sum(c : Cons) =
              c.Head + c.Tail?Sum()
  
          member x.Index(l : Root<IList>) = 
              inh <<= 0
  
          member x.Index(c : Cons) = 
              let id = c?Index
              inh <<= id + 1
      
  
          member x.Blubber(l : Root<IList>) = 
              inh <<= 0
  
          member x.Blubber(c : Cons) = 
              let id = c?Blubber
              inh <<= id + 1   
  
          member x.Bla(l : Root<IList>) = 
              inh <<= 0
  
          member x.Bla(c : Cons) = 
              let id = c?Bla
              inh <<= id + 1   
  
          member x.Gabbl(l : Root<IList>) = 
              inh <<= 0
  
          member x.Gabbl(c : Cons) = 
              let id = c?Gabbl
              inh <<= id + 1   
  
  
          member x.Gobbl(l : Root<IList>) = 
              inh <<= 0
  
          member x.Gobbl(c : Cons) = 
              let id = c?Gobbl
              inh <<= id + 1   
  
  
  
      type SemanticFunctionKind =
          | Inherit
          | Synthesize
  
      type SemanticFunction =
          {
              name        : string
              kind        : SemanticFunctionKind
              strictInh   : Set<string>
              strictSyn   : Set<string>
              original    : MethodInfo
              isRoot      : bool
              nodeType    : Type
              valueType   : Type
              definition  : Expr
          }
  
      [<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
      module SemanticFunction =
          
          let private all = BindingFlags.NonPublic ||| BindingFlags.Public ||| BindingFlags.Instance ||| BindingFlags.Static ||| BindingFlags.CreateInstance
          let private prettyName (t : Type) =
              Aardvark.Base.ReflectionHelpers.getPrettyName t
  
          let private methodName (m : MethodInfo) =
              let t = prettyName m.DeclaringType
              let args = m.GetParameters() |> Array.map (fun p -> sprintf "%s : %s" p.Name (prettyName p.ParameterType)) |> String.concat ", "
              sprintf "%s.%s(%s)" t m.Name args
  
          let private instances = Dict<Type, obj>()
          let private getInstance (t : Type) =
              instances.GetOrCreate(t, fun t ->
                  let ctor = t.GetConstructor(all, Type.DefaultBinder, CallingConventions.Any, [||], null)
                  if isNull ctor then
                      failwithf "[Ag] cannot create semantic-type '%s' (no empty constructor)" (prettyName t)
  
                  ctor.Invoke [||]
              )
  
  
          let ofSeq (name : string) (getTraversal : string -> Type -> Expr) (methods : seq<MethodInfo>) =
              let methods = Seq.toList methods
  
              // try to get definitions for all methods
              let definitions = 
                  methods |> List.choose (fun mi ->
                      if mi.IsGenericMethodDefinition || mi.GetParameters().Length <> 1 then
                          Log.warn "[Ag] ill-formed semantic function '%s' (skipping)" (methodName mi)
                          None
                      else
                          match Expr.TryGetReflectedDefinition mi with
                              | Some d -> 
                                  Some {
                                      name        = mi.Name
                                      kind        = Synthesize
                                      strictInh   = Set.empty
                                      strictSyn   = Set.empty
                                      original    = mi
                                      isRoot      = false
                                      nodeType    = mi.GetParameters().[0].ParameterType
                                      valueType   = mi.ReturnType
                                      definition  = d
                                  }
                              | _ ->
                                  Log.warn "[Ag] could not get definition for '%s' (skipping)" (methodName mi)
                                  None
                  )
  
              // remove all 'this' references from the methods and replace them with an appropriate 
              // cached instance (created on demand)
              let definitions = 
                  definitions |> List.map (fun sf ->
                      { sf with
                          definition =
                              match sf.definition with
                                  | Lambda(v,b) when v.Type.IsDefined(typeof<SemanticAttribute>) -> 
                                      b.Substitute (fun vi -> if v = vi then Some (Expr.Value(getInstance v.Type, v.Type)) else None)
                                  | e -> 
                                      e
                      }
                  )
  
  
              let definitions =
                  definitions |> List.map (fun sf ->
                      let rec retType (e : Expr) =
                          match e with
                              | Call(None, mi, [_; value]) when mi.Name = "op_LessLessEquals" ->
                                  value.Type
  
  
                              | Value(v,t) -> t
  
  
                              | Var(v) ->
                                  v.Type
  
                              | Lambda(v,b) ->
                                  retType b
  
                              | Sequential(_,r) ->
                                  retType r
  
                              | Let(_,_,b) ->
                                  retType b
  
                              | Coerce(_,t) ->
                                  t
  
                              | IfThenElse(_,i,_) -> retType i
  
                              | WhileLoop(_,_) -> typeof<unit>
  
                              | ForIntegerRangeLoop(_,_,_,_) -> typeof<unit>
  
                              | Call(_,mi,_) -> mi.ReturnType
  
                              | Application(b, arg) ->
                                  retType b
  
                              | e -> 
                                  failwithf "unknown expression %A" e
                  
                      { sf with valueType = retType sf.definition }
  
                  )
              
              
              // replace all attribute-lookups with traversal-calls and add the traversal argument
              // to all semantic functions
  