0 people like it.

Normalization by Evaluation

Optimizing F# quotations by applying Normalization-by-Evaluation

Implementation

  1: 
  2: 
  3: 
  4: 
  5: 
  6: 
  7: 
  8: 
  9: 
 10: 
 11: 
 12: 
 13: 
 14: 
 15: 
 16: 
 17: 
 18: 
 19: 
 20: 
 21: 
 22: 
 23: 
 24: 
 25: 
 26: 
 27: 
 28: 
 29: 
 30: 
 31: 
 32: 
 33: 
 34: 
 35: 
 36: 
 37: 
 38: 
 39: 
 40: 
 41: 
 42: 
 43: 
 44: 
 45: 
 46: 
 47: 
 48: 
 49: 
 50: 
 51: 
 52: 
 53: 
 54: 
 55: 
 56: 
 57: 
 58: 
 59: 
 60: 
 61: 
 62: 
 63: 
 64: 
 65: 
 66: 
 67: 
 68: 
 69: 
 70: 
 71: 
 72: 
 73: 
 74: 
 75: 
 76: 
 77: 
 78: 
 79: 
 80: 
 81: 
 82: 
 83: 
 84: 
 85: 
 86: 
 87: 
 88: 
 89: 
 90: 
 91: 
 92: 
 93: 
 94: 
 95: 
 96: 
 97: 
 98: 
 99: 
100: 
101: 
102: 
103: 
104: 
105: 
106: 
107: 
108: 
109: 
110: 
111: 
112: 
113: 
114: 
115: 
116: 
117: 
118: 
119: 
120: 
121: 
122: 
123: 
124: 
125: 
126: 
127: 
128: 
129: 
130: 
131: 
132: 
133: 
134: 
135: 
136: 
137: 
138: 
139: 
140: 
141: 
142: 
143: 
144: 
145: 
146: 
147: 
148: 
149: 
150: 
151: 
152: 
153: 
154: 
155: 
156: 
157: 
158: 
159: 
160: 
161: 
162: 
163: 
164: 
165: 
166: 
167: 
168: 
169: 
170: 
171: 
172: 
173: 
174: 
175: 
176: 
177: 
178: 
179: 
180: 
181: 
182: 
183: 
184: 
185: 
186: 
187: 
188: 
189: 
190: 
191: 
192: 
193: 
194: 
195: 
196: 
197: 
198: 
199: 
200: 
201: 
202: 
203: 
204: 
205: 
206: 
207: 
208: 
209: 
210: 
211: 
212: 
213: 
214: 
215: 
216: 
217: 
218: 
219: 
220: 
221: 
222: 
223: 
224: 
225: 
226: 
227: 
228: 
229: 
230: 
231: 
232: 
233: 
234: 
235: 
236: 
237: 
238: 
239: 
240: 
241: 
242: 
243: 
244: 
245: 
246: 
247: 
248: 
249: 
250: 
251: 
252: 
253: 
254: 
255: 
256: 
257: 
258: 
259: 
260: 
261: 
262: 
263: 
264: 
265: 
266: 
267: 
268: 
269: 
270: 
271: 
272: 
open System
open System.Reflection
open FSharp.Reflection
open FSharp.Quotations
open FSharp.Quotations.Patterns
open FSharp.Quotations.DerivedPatterns
open FSharp.Quotations.ExprShape

// Semantic interpretation of quotation trees
type Sem =
    | VAR of Var * value:Sem option
    | LIT of obj * Type
    | LAM of Var * Sem * (Sem -> Sem)
    | LET of Var * Sem * Sem
    | TUPLE of Type * Sem list
    | RECORD of Type * Sem list
    | UNION of UnionCaseInfo * Sem list
    | UPCAST of Sem * Type
    // Standard arithmetic operator expression
    | OP of MethodInfo * Sem list
    // Embeds arbitrary syntactic trees
    | SYN of expr:Expr * isPureNode:bool * shape:obj * args:Sem list

/// determines if expression is guaranteed to evaluate without side-effects
let rec isPure (s : Sem) =
    match s with
    | VAR (v,_) -> not v.IsMutable
    | LIT _ | LAM _ -> true
    | LET(_,b,k) -> isPure b && isPure k
    | UPCAST (s,_) -> isPure s
    | TUPLE (_,fs) | RECORD (_,fs) | UNION(_,fs) | OP(_,fs) -> fs |> List.forall isPure
    | SYN(isPureNode = isPureNode; args = args) -> isPureNode && args |> List.forall isPure

let rec getType reflect (s : Sem) =
    match s with
    | VAR (v, None) -> v.Type
    | VAR (_, Some s) -> getType reflect s
    | LIT (null, t) -> t
    | LIT (o, _) -> o.GetType()
    | LAM (v, s, _) -> FSharpType.MakeFunctionType(v.Type, getType false s)
    | LET (_,_,k) -> getType reflect k
    | UPCAST (s,t) -> if reflect then getType reflect s else t
    | TUPLE (t,_) -> t
    | RECORD (t,_) -> t
    | UNION(uci,_) -> uci.DeclaringType
    | OP(mi,_) -> mi.ReturnType
    | SYN(expr = e) -> e.Type

/// determines if the two types are in a subtype relationship
let rec isSubtypeOf (iface : Type) (ty : Type) =
    let proj (t : Type) = t.Assembly, t.Namespace, t.Name, t.MetadataToken
    if iface.IsAssignableFrom ty then true
    elif ty.GetInterfaces() |> Array.exists(fun if0 -> proj if0 = proj iface) then true
    else
        match ty.BaseType with
        | null -> false
        | bt -> isSubtypeOf iface bt

let rec containsReference (v : Var) (s : Sem) =
    match s with
    | VAR (w, _) -> v = w
    | LIT _ -> false
    | LAM (_, b, _) -> containsReference v b
    | LET (_, b, k) -> containsReference v b || containsReference v k
    | UPCAST (s, _) -> containsReference v s
    | TUPLE (_, args)
    | RECORD (_, args)
    | UNION (_, args)
    | OP (_, args)
    | SYN (_, _, _, args) -> args |> List.exists (containsReference v)

type Environment = Map<Var, Sem>

/// Maps syntactic trees to semantic expressions; apply optimizations as required
let rec meaning (env : Environment) (expr : Expr) : Sem =
    let mkLit (x : 'T) = LIT(x, typeof<'T>)

    let (|Deref|) s =
        match s with
        | VAR(_, Some s) -> s
        | _ -> s

    let mkLet v sbind skont =
        // if binding is pure and variable not referenced in kont, eliminate the let
        if isPure sbind && skont |> containsReference v |> not then skont
        else LET(v, sbind, skont)

    // fallback mapping: use trivial expression node embedding
    let fallback (env : Environment) (expr : Expr) =
        match expr with
        | ShapeCombination(shape, args) ->
            let sargs = args |> List.map (meaning env)
            let isPureNode =
                match expr with
                | IfThenElse _
                | TupleGet _
                | TypeTest _
                | UnionCaseTest _
                | LetRecursive _
                | QuoteRaw _
                | QuoteTyped _ -> true
                | PropertyGet(Some e, _, []) when 
                    FSharpType.IsRecord(e.Type, true) || 
                    FSharpType.IsUnion(e.Type, true) ||
                    FSharpType.IsTuple(e.Type) -> true
                | _ -> false

            SYN(expr, isPureNode, shape, sargs)

        | ShapeVar _ | ShapeLambda _ -> failwith "internal error"
        
    match expr with
    | Value(o, t) -> LIT(o, t)
    | Var v -> 
        match env.TryFind v with
        | Some (LIT _ | VAR _ as s) -> s
        | sopt -> VAR(v, sopt)

    | Lambda(v, body) -> 
        let slam s = meaning (env.Add(v, s)) body
        LAM(v, slam (VAR(v, None)), slam)

    | Application(f, g) ->
        match meaning env f with
        | Deref (LAM (v, _, lam)) ->
            match meaning env g with
            // (λ x. M) N ~> M[N/x]
            | LIT _ | VAR _ | LAM _ as s -> lam s
            // (λ x. M) N ~> let x = N in M
            | sbind -> mkLet v sbind (lam (VAR(v, Some sbind)))

        | _ -> fallback env expr

    | Let(v, bind, kont) when not v.IsMutable ->
        let sbind = meaning env bind
        match meaning (env.Add(v, sbind)) kont with
        // let x = N in x ~> N
        | VAR(x, _) when x = v -> sbind 
        // let x = expr in M ~> M
        | skont -> mkLet v sbind skont

    | IfThenElse(cond, ifExpr, elseExpr) ->
        match meaning env cond with
        | Deref (LIT(:? bool as ccond, _)) ->
            // branch elimination
            let branch = if ccond then ifExpr else elseExpr
            meaning env branch
        | _ -> fallback env expr

    | Sequential(left, right) ->
        match meaning env left with
        | ls when isPure ls -> meaning env right
        | _ -> fallback env expr

    // Tuple introduction & elimination [https://github.com/dotnet/fsharp/issues/7914]
    | NewTuple ts when not expr.Type.IsValueType -> TUPLE(expr.Type, ts |> List.map (meaning env))
    | TupleGet(tuple, i) ->
        match meaning env tuple with
        | Deref (TUPLE (_, ts)) -> ts.[i]
        | _ -> fallback env expr

    // Record introduction & elimination
    | NewRecord(t, fs) -> RECORD(t, fs |> List.map (meaning env))
    | PropertyGet(Some e, prop, []) ->
        match meaning env e with
        | Deref (RECORD(t,fs)) -> 
            match FSharpType.GetRecordFields(t, true) |> Array.tryFindIndex(fun p -> prop = p) with
            | Some i -> fs.[i]
            | None -> fallback env expr
        | Deref (UNION(uci, fs)) ->
            match uci.GetFields() |> Array.tryFindIndex(fun p -> prop = p) with
            | Some i -> fs.[i]
            | None -> fallback env expr
        | _ -> fallback env expr

    // Union introduction & elimination
    | NewUnionCase(uci, fs) -> UNION(uci, fs |> List.map (meaning env))
    | UnionCaseTest(e, uci) ->
        match meaning env e with
        | Deref (UNION(uci', _)) -> mkLit(uci = uci')
        | _ -> fallback env expr

    | TypeTest(e, t) ->
        let s = meaning env e
        let st = getType true s
        let staticTypeTestResult =
            if isSubtypeOf t st then Some true
            elif isSubtypeOf st t then None
            else Some false

        match staticTypeTestResult with
        | Some r -> meaning env (Expr.Sequential(e, Expr.Value r))
        | None -> fallback env expr

    | Coerce(e, t) ->
        let (s | UPCAST(s,_)) = meaning env e
        let st = getType true s
        if t = st then
            // UPCAST elimination: remove if expression type matches the reflected type
            let rec tryDeref s =
                match s with
                | LIT _ -> Some s
                | UPCAST(s, _) -> tryDeref s
                | VAR(_, Some v) ->
                    match tryDeref v with
                    | Some _ as r -> r
                    | None -> Some s

                // do not deref if expr is method
                // or other side-effectful operation
                | _ -> None

            match tryDeref s with
            | Some s when getType false s = t -> s
            | _ -> UPCAST(s, t)

        elif isSubtypeOf t st then UPCAST(s, t)
        else fallback env expr

    | SpecificCall <@ (=) @> (None, _, ([value; Value(null,_)] | [Value(null,_) ; value]))
    | SpecificCall <@ isNull @> (None, _, ([value])) ->
        match meaning env value with
        | Deref (LIT (x,_)) -> mkLit(obj.ReferenceEquals(x, null))
        | _ -> fallback env expr

    | SpecificCall <@ (<>) @> (None, _, ([value; Value(null,_)] | [Value(null,_) ; value])) ->
        match meaning env value with
        | Deref (LIT (x,_)) -> mkLit(not <| obj.ReferenceEquals(x, null))
        | _ -> fallback env expr

    | SpecificCall <@ (|>) @> (None, _, [value; func])
    | SpecificCall <@ (<|) @> (None, _, [func; value]) -> meaning env (Expr.Application(func, value))

    | SpecificCall <@ fst @> (None, _, [t]) -> meaning env (Expr.TupleGet(t, 0))
    | SpecificCall <@ snd @> (None, _, [t]) -> meaning env (Expr.TupleGet(t, 1))
    | SpecificCall <@ ignore @> (None, _, [value]) -> meaning env (Expr.Sequential(value, Expr.Value(())))

    | SpecificCall <@ box @> (None, _, [value])
    | SpecificCall <@ LanguagePrimitives.IntrinsicFunctions.UnboxGeneric @> (None, _, [value])
    | SpecificCall <@ LanguagePrimitives.IntrinsicFunctions.UnboxFast @> (None, _, [value])
    | SpecificCall <@ unbox @> (None, _, [value]) -> meaning env (Expr.Coerce(value, expr.Type))

    | Call(None, mi, args) when mi.DeclaringType.FullName = "Microsoft.FSharp.Core.Operators" && mi.Name.StartsWith "op_" ->
        let sargs = args |> List.map (meaning env)
        let literals = sargs |> Seq.choose (function (Deref (LIT(o,_))) -> Some o | _ -> None) |> Seq.toArray
        if literals.Length = sargs.Length then
            // evaluate constant expressions
            try LIT(mi.Invoke(null, literals), expr.Type)
            with :? TargetInvocationException as e when (e.InnerException :? NotSupportedException) ->
                // "Dynamic invocation of operator is not supported"
                OP(mi, sargs)
        else
            OP(mi, sargs)

    | _ -> fallback env expr

/// Maps semantic expressions back to a syntactic representation
let rec reify (s : Sem) : Expr =
    match s with
    | VAR (v, _) -> Expr.Var v
    | LIT (o, t) -> Expr.Value(o, t)
    | LAM (v, b, _) -> Expr.Lambda(v, reify b)
    | LET (v, b, k) -> Expr.Let(v, reify b, reify k)
    | UPCAST (s, t) -> Expr.Coerce(reify s, t)
    | TUPLE (_, fs) -> Expr.NewTuple(fs |> List.map reify)
    | RECORD (t, fs) -> Expr.NewRecord(t, fs |> List.map reify)
    | UNION (uci, fs) -> Expr.NewUnionCase(uci, fs |> List.map reify)
    | OP(mI, args) -> Expr.Call(mI, args |> List.map reify)
    | SYN(_, _, shape, sparams) -> RebuildShapeCombination(shape, sparams |> List.map reify)

/// Apply normalization-by-evaluation to quotation tree
let nbe (e : Expr<'a>) : Expr<'a> = e |> meaning Map.empty |> reify |> Expr.Cast

Examples

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
let nbe_decompile expr = expr |> nbe |> Swensen.Unquote.Operators.decompile

nbe_decompile 
    <@
        let f x =
            match x with
            | Some i -> i > 0
            | None -> false

        f (Some 42), f None
    @>
// (true, false)

nbe_decompile 
    <@ 
        fun () -> 
            let mutable y = 0
            let f x = x + 2
            y <- f 2
            y + 1
    @>
// fun () -> let mutable y = 0 in y <- 4; y + 1

nbe_decompile 
    <@
        fun z ->
            let f x =
                if x > 0 then Console.WriteLine "Positive"
                elif x = 0 then Console.WriteLine "Zero"
                else Console.WriteLine "Negative"

            f -1; f 0; f z
    @>
// fun z -> 
//      Console.WriteLine("Negative")
//      Console.WriteLine("Zero")
//      if z > 0 then Console.WriteLine("Positive") 
//      else (if z = 0 then Console.WriteLine("Zero")
//      else Console.WriteLine("Negative"))

Stream pipelines

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
// Nessos streams: http://trelford.com/blog/post/SeqVsStream.aspx
type Stream<'T> = ('T -> unit) -> unit

nbe_decompile
    <@
        let ofArray (xs : int []) =
            fun k -> for x in xs do k x

        let map : (int -> int) -> Stream<int> -> Stream<int> =
            fun f ts k -> ts (fun t -> k (f t))

        let filter : (int -> bool) -> Stream<int> -> Stream<int> =
            fun f ts k -> ts (fun t -> if (f t) then k t)

        let iter : (int -> unit) -> Stream<int> -> unit =
            fun f ts -> ts f

        fun xs ->
            ofArray xs
            |> filter (fun i -> i > 0)
            |> filter (fun i -> i % 2 = 0)
            |> map (fun i -> i * i)
            |> map (fun i -> i + i)
            |> iter (fun i -> printfn "%d" i)
    @>

//fun (xs : int []) ->
//    for x in xs do
//        if x > 0 then
//            if x % 2 = 0 then
//                let t = x * x
//                let i = t + t
//                printfn "%d" i
namespace System
namespace System.Reflection
namespace Microsoft.FSharp
namespace Microsoft.FSharp.Reflection
namespace Microsoft.FSharp.Quotations
module Patterns

from Microsoft.FSharp.Quotations
module DerivedPatterns

from Microsoft.FSharp.Quotations
module ExprShape

from Microsoft.FSharp.Quotations
type Sem =
  | VAR of Var * value: Sem option
  | LIT of obj * Type
  | LAM of Var * Sem * (Sem -> Sem)
  | LET of Var * Sem * Sem
  | TUPLE of Type * Sem list
  | RECORD of Type * Sem list
  | UNION of UnionCaseInfo * Sem list
  | UPCAST of Sem * Type
  | OP of MethodInfo * Sem list
  | SYN of expr: Expr * isPureNode: bool * shape: obj * args: Sem list

Full name: Script.Sem
union case Sem.VAR: Var * value: Sem option -> Sem
Multiple items
active recognizer Var: Expr -> Var option

Full name: Microsoft.FSharp.Quotations.Patterns.( |Var|_| )

--------------------
type Var =
  interface IComparable
  new : name:string * typ:Type * ?isMutable:bool -> Var
  member IsMutable : bool
  member Name : string
  member Type : Type
  static member Global : name:string * typ:Type -> Var

Full name: Microsoft.FSharp.Quotations.Var

--------------------
new : name:string * typ:Type * ?isMutable:bool -> Var
type 'T option = Option<'T>

Full name: Microsoft.FSharp.Core.option<_>
union case Sem.LIT: obj * Type -> Sem
type obj = Object

Full name: Microsoft.FSharp.Core.obj
type Type =
  inherit MemberInfo
  member Assembly : Assembly
  member AssemblyQualifiedName : string
  member Attributes : TypeAttributes
  member BaseType : Type
  member ContainsGenericParameters : bool
  member DeclaringMethod : MethodBase
  member DeclaringType : Type
  member Equals : o:obj -> bool + 1 overload
  member FindInterfaces : filter:TypeFilter * filterCriteria:obj -> Type[]
  member FindMembers : memberType:MemberTypes * bindingAttr:BindingFlags * filter:MemberFilter * filterCriteria:obj -> MemberInfo[]
  ...

Full name: System.Type
union case Sem.LAM: Var * Sem * (Sem -> Sem) -> Sem
union case Sem.LET: Var * Sem * Sem -> Sem
union case Sem.TUPLE: Type * Sem list -> Sem
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
union case Sem.RECORD: Type * Sem list -> Sem
union case Sem.UNION: UnionCaseInfo * Sem list -> Sem
type UnionCaseInfo
member GetCustomAttributes : unit -> obj []
member GetCustomAttributes : attributeType:Type -> obj []
member GetCustomAttributesData : unit -> IList<CustomAttributeData>
member GetFields : unit -> PropertyInfo []
member DeclaringType : Type
member Name : string
member Tag : int

Full name: Microsoft.FSharp.Reflection.UnionCaseInfo
union case Sem.UPCAST: Sem * Type -> Sem
union case Sem.OP: MethodInfo * Sem list -> Sem
type MethodInfo =
  inherit MethodBase
  member Equals : obj:obj -> bool
  member GetBaseDefinition : unit -> MethodInfo
  member GetGenericArguments : unit -> Type[]
  member GetGenericMethodDefinition : unit -> MethodInfo
  member GetHashCode : unit -> int
  member MakeGenericMethod : [<ParamArray>] typeArguments:Type[] -> MethodInfo
  member MemberType : MemberTypes
  member ReturnParameter : ParameterInfo
  member ReturnType : Type
  member ReturnTypeCustomAttributes : ICustomAttributeProvider

Full name: System.Reflection.MethodInfo
union case Sem.SYN: expr: Expr * isPureNode: bool * shape: obj * args: Sem list -> Sem
Multiple items
type Expr =
  override Equals : obj:obj -> bool
  member GetFreeVars : unit -> seq<Var>
  member Substitute : substitution:(Var -> Expr option) -> Expr
  member ToString : full:bool -> string
  member CustomAttributes : Expr list
  member Type : Type
  static member AddressOf : target:Expr -> Expr
  static member AddressSet : target:Expr * value:Expr -> Expr
  static member Application : functionExpr:Expr * argument:Expr -> Expr
  static member Applications : functionExpr:Expr * arguments:Expr list list -> Expr
  ...

Full name: Microsoft.FSharp.Quotations.Expr

--------------------
type Expr<'T> =
  inherit Expr
  member Raw : Expr

Full name: Microsoft.FSharp.Quotations.Expr<_>
type bool = Boolean

Full name: Microsoft.FSharp.Core.bool
val isPure : s:Sem -> bool

Full name: Script.isPure


 determines if expression is guaranteed to evaluate without side-effects
val s : Sem
val v : Var
val not : value:bool -> bool

Full name: Microsoft.FSharp.Core.Operators.not
property Var.IsMutable: bool
val b : Sem
val k : Sem
val fs : Sem list
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member GetSlice : startIndex:int option * endIndex:int option -> 'T list
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val forall : predicate:('T -> bool) -> list:'T list -> bool

Full name: Microsoft.FSharp.Collections.List.forall
val isPureNode : bool
val args : Sem list
val getType : reflect:bool -> s:Sem -> Type

Full name: Script.getType
val reflect : bool
union case Option.None: Option<'T>
property Var.Type: Type
union case Option.Some: Value: 'T -> Option<'T>
val t : Type
val o : obj
Object.GetType() : Type
type FSharpType =
  static member GetExceptionFields : exceptionType:Type * ?bindingFlags:BindingFlags -> PropertyInfo []
  static member GetFunctionElements : functionType:Type -> Type * Type
  static member GetRecordFields : recordType:Type * ?bindingFlags:BindingFlags -> PropertyInfo []
  static member GetTupleElements : tupleType:Type -> Type []
  static member GetUnionCases : unionType:Type * ?bindingFlags:BindingFlags -> UnionCaseInfo []
  static member IsExceptionRepresentation : exceptionType:Type * ?bindingFlags:BindingFlags -> bool
  static member IsFunction : typ:Type -> bool
  static member IsModule : typ:Type -> bool
  static member IsRecord : typ:Type * ?bindingFlags:BindingFlags -> bool
  static member IsTuple : typ:Type -> bool
  ...

Full name: Microsoft.FSharp.Reflection.FSharpType
static member FSharpType.MakeFunctionType : domain:Type * range:Type -> Type
val uci : UnionCaseInfo
property UnionCaseInfo.DeclaringType: Type
val mi : MethodInfo
property MethodInfo.ReturnType: Type
val e : Expr
property Expr.Type: Type
val isSubtypeOf : iface:Type -> ty:Type -> bool

Full name: Script.isSubtypeOf


 determines if the two types are in a subtype relationship
val iface : Type
val ty : Type
val proj : (Type -> Assembly * string * string * int)
property Type.Assembly: Assembly
property Type.Namespace: string
property MemberInfo.Name: string
property MemberInfo.MetadataToken: int
Type.IsAssignableFrom(c: Type) : bool
Type.GetInterfaces() : Type []
type Array =
  member Clone : unit -> obj
  member CopyTo : array:Array * index:int -> unit + 1 overload
  member GetEnumerator : unit -> IEnumerator
  member GetLength : dimension:int -> int
  member GetLongLength : dimension:int -> int64
  member GetLowerBound : dimension:int -> int
  member GetUpperBound : dimension:int -> int
  member GetValue : [<ParamArray>] indices:int[] -> obj + 7 overloads
  member Initialize : unit -> unit
  member IsFixedSize : bool
  ...

Full name: System.Array
val exists : predicate:('T -> bool) -> array:'T [] -> bool

Full name: Microsoft.FSharp.Collections.Array.exists
val if0 : Type
property Type.BaseType: Type
val bt : Type
val containsReference : v:Var -> s:Sem -> bool

Full name: Script.containsReference
val w : Var
val exists : predicate:('T -> bool) -> list:'T list -> bool

Full name: Microsoft.FSharp.Collections.List.exists
type Environment = Map<Var,Sem>

Full name: Script.Environment
Multiple items
module Map

from Microsoft.FSharp.Collections

--------------------
type Map<'Key,'Value (requires comparison)> =
  interface IEnumerable
  interface IComparable
  interface IEnumerable<KeyValuePair<'Key,'Value>>
  interface ICollection<KeyValuePair<'Key,'Value>>
  interface IDictionary<'Key,'Value>
  new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
  member Add : key:'Key * value:'Value -> Map<'Key,'Value>
  member ContainsKey : key:'Key -> bool
  override Equals : obj -> bool
  member Remove : key:'Key -> Map<'Key,'Value>
  ...

Full name: Microsoft.FSharp.Collections.Map<_,_>

--------------------
new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
val meaning : env:Environment -> expr:Expr -> Sem

Full name: Script.meaning


 Maps syntactic trees to semantic expressions; apply optimizations as required
val env : Environment
val expr : Expr
val mkLit : ('T -> Sem)
val x : 'T
val typeof<'T> : Type

Full name: Microsoft.FSharp.Core.Operators.typeof
val mkLet : (Var -> Sem -> Sem -> Sem)
val sbind : Sem
val skont : Sem
val fallback : (Environment -> Expr -> Sem)
active recognizer ShapeCombination: Expr -> Choice<Var,(Var * Expr),(obj * Expr list)>

Full name: Microsoft.FSharp.Quotations.ExprShape.( |ShapeVar|ShapeLambda|ShapeCombination| )
val shape : obj
val args : Expr list
val sargs : Sem list
val map : mapping:('T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map
active recognizer IfThenElse: Expr -> (Expr * Expr * Expr) option

Full name: Microsoft.FSharp.Quotations.Patterns.( |IfThenElse|_| )
active recognizer TupleGet: Expr -> (Expr * int) option

Full name: Microsoft.FSharp.Quotations.Patterns.( |TupleGet|_| )
active recognizer TypeTest: Expr -> (Expr * Type) option

Full name: Microsoft.FSharp.Quotations.Patterns.( |TypeTest|_| )
active recognizer UnionCaseTest: Expr -> (Expr * UnionCaseInfo) option

Full name: Microsoft.FSharp.Quotations.Patterns.( |UnionCaseTest|_| )
active recognizer LetRecursive: Expr -> ((Var * Expr) list * Expr) option

Full name: Microsoft.FSharp.Quotations.Patterns.( |LetRecursive|_| )
active recognizer QuoteRaw: Expr -> Expr option

Full name: Microsoft.FSharp.Quotations.Patterns.( |QuoteRaw|_| )
active recognizer QuoteTyped: Expr -> Expr option

Full name: Microsoft.FSharp.Quotations.Patterns.( |QuoteTyped|_| )
active recognizer PropertyGet: Expr -> (Expr option * PropertyInfo * Expr list) option

Full name: Microsoft.FSharp.Quotations.Patterns.( |PropertyGet|_| )
static member FSharpType.IsRecord : typ:Type * ?allowAccessToPrivateRepresentation:bool -> bool
static member FSharpType.IsRecord : typ:Type * ?bindingFlags:BindingFlags -> bool
static member FSharpType.IsUnion : typ:Type * ?allowAccessToPrivateRepresentation:bool -> bool
static member FSharpType.IsUnion : typ:Type * ?bindingFlags:BindingFlags -> bool
static member FSharpType.IsTuple : typ:Type -> bool
active recognizer ShapeVar: Expr -> Choice<Var,(Var * Expr),(obj * Expr list)>

Full name: Microsoft.FSharp.Quotations.ExprShape.( |ShapeVar|ShapeLambda|ShapeCombination| )
active recognizer ShapeLambda: Expr -> Choice<Var,(Var * Expr),(obj * Expr list)>

Full name: Microsoft.FSharp.Quotations.ExprShape.( |ShapeVar|ShapeLambda|ShapeCombination| )
val failwith : message:string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith
active recognizer Value: Expr -> (obj * Type) option

Full name: Microsoft.FSharp.Quotations.Patterns.( |Value|_| )
member Map.TryFind : key:'Key -> 'Value option
val sopt : Sem option
active recognizer Lambda: Expr -> (Var * Expr) option

Full name: Microsoft.FSharp.Quotations.Patterns.( |Lambda|_| )
val body : Expr
val slam : (Sem -> Sem)
member Map.Add : key:'Key * value:'Value -> Map<'Key,'Value>
active recognizer Application: Expr -> (Expr * Expr) option

Full name: Microsoft.FSharp.Quotations.Patterns.( |Application|_| )
val f : Expr
val g : Expr
active recognizer Deref: Sem -> Sem
val lam : (Sem -> Sem)
active recognizer Let: Expr -> (Var * Expr * Expr) option

Full name: Microsoft.FSharp.Quotations.Patterns.( |Let|_| )
val bind : Expr
val kont : Expr
val x : Var
val cond : Expr
val ifExpr : Expr
val elseExpr : Expr
val ccond : bool
val branch : Expr
active recognizer Sequential: Expr -> (Expr * Expr) option

Full name: Microsoft.FSharp.Quotations.Patterns.( |Sequential|_| )
val left : Expr
val right : Expr
val ls : Sem
active recognizer NewTuple: Expr -> Expr list option

Full name: Microsoft.FSharp.Quotations.Patterns.( |NewTuple|_| )
val ts : Expr list
property Type.IsValueType: bool
val tuple : Expr
val i : int
val ts : Sem list
active recognizer NewRecord: Expr -> (Type * Expr list) option

Full name: Microsoft.FSharp.Quotations.Patterns.( |NewRecord|_| )
val fs : Expr list
val prop : PropertyInfo
static member FSharpType.GetRecordFields : recordType:Type * ?allowAccessToPrivateRepresentation:bool -> PropertyInfo []
static member FSharpType.GetRecordFields : recordType:Type * ?bindingFlags:BindingFlags -> PropertyInfo []
val tryFindIndex : predicate:('T -> bool) -> array:'T [] -> int option

Full name: Microsoft.FSharp.Collections.Array.tryFindIndex
val p : PropertyInfo
member UnionCaseInfo.GetFields : unit -> PropertyInfo []
active recognizer NewUnionCase: Expr -> (UnionCaseInfo * Expr list) option

Full name: Microsoft.FSharp.Quotations.Patterns.( |NewUnionCase|_| )
val uci' : UnionCaseInfo
val st : Type
val staticTypeTestResult : bool option
val r : bool
static member Expr.Sequential : first:Expr * second:Expr -> Expr
static member Expr.Value : value:'T -> Expr
static member Expr.Value : value:obj * expressionType:Type -> Expr
active recognizer Coerce: Expr -> (Expr * Type) option

Full name: Microsoft.FSharp.Quotations.Patterns.( |Coerce|_| )
val tryDeref : (Sem -> Sem option)
val v : Sem
val r : Sem option
active recognizer SpecificCall: Expr -> Expr -> (Expr option * Type list * Expr list) option

Full name: Microsoft.FSharp.Quotations.DerivedPatterns.( |SpecificCall|_| )
val value : Expr
val isNull : value:'T -> bool (requires 'T : null)

Full name: Microsoft.FSharp.Core.Operators.isNull
val x : obj
Object.ReferenceEquals(objA: obj, objB: obj) : bool
val func : Expr
static member Expr.Application : functionExpr:Expr * argument:Expr -> Expr
val fst : tuple:('T1 * 'T2) -> 'T1

Full name: Microsoft.FSharp.Core.Operators.fst
val t : Expr
static member Expr.TupleGet : tuple:Expr * index:int -> Expr
val snd : tuple:('T1 * 'T2) -> 'T2

Full name: Microsoft.FSharp.Core.Operators.snd
val ignore : value:'T -> unit

Full name: Microsoft.FSharp.Core.Operators.ignore
val box : value:'T -> obj

Full name: Microsoft.FSharp.Core.Operators.box
module LanguagePrimitives

from Microsoft.FSharp.Core
module IntrinsicFunctions

from Microsoft.FSharp.Core.LanguagePrimitives
val unbox : value:obj -> 'T

Full name: Microsoft.FSharp.Core.Operators.unbox
static member Expr.Coerce : source:Expr * target:Type -> Expr
active recognizer Call: Expr -> (Expr option * MethodInfo * Expr list) option

Full name: Microsoft.FSharp.Quotations.Patterns.( |Call|_| )
property MemberInfo.DeclaringType: Type
property Type.FullName: string
String.StartsWith(value: string) : bool
String.StartsWith(value: string, comparisonType: StringComparison) : bool
String.StartsWith(value: string, ignoreCase: bool, culture: Globalization.CultureInfo) : bool
val literals : obj []
module Seq

from Microsoft.FSharp.Collections
val choose : chooser:('T -> 'U option) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.choose
val toArray : source:seq<'T> -> 'T []

Full name: Microsoft.FSharp.Collections.Seq.toArray
property Array.Length: int
property List.Length: int
MethodBase.Invoke(obj: obj, parameters: obj []) : obj
MethodBase.Invoke(obj: obj, invokeAttr: BindingFlags, binder: Binder, parameters: obj [], culture: Globalization.CultureInfo) : obj
Multiple items
type TargetInvocationException =
  inherit ApplicationException
  new : inner:Exception -> TargetInvocationException + 1 overload

Full name: System.Reflection.TargetInvocationException

--------------------
TargetInvocationException(inner: exn) : unit
TargetInvocationException(message: string, inner: exn) : unit
val e : TargetInvocationException
property Exception.InnerException: exn
Multiple items
type NotSupportedException =
  inherit SystemException
  new : unit -> NotSupportedException + 2 overloads

Full name: System.NotSupportedException

--------------------
NotSupportedException() : unit
NotSupportedException(message: string) : unit
NotSupportedException(message: string, innerException: exn) : unit
val reify : s:Sem -> Expr

Full name: Script.reify


 Maps semantic expressions back to a syntactic representation
static member Expr.Var : variable:Var -> Expr
static member Expr.Lambda : parameter:Var * body:Expr -> Expr
static member Expr.Let : letVariable:Var * letExpr:Expr * body:Expr -> Expr
static member Expr.NewTuple : elements:Expr list -> Expr
static member Expr.NewRecord : recordType:Type * elements:Expr list -> Expr
static member Expr.NewUnionCase : unionCase:UnionCaseInfo * arguments:Expr list -> Expr
val mI : MethodInfo
static member Expr.Call : methodInfo:MethodInfo * arguments:Expr list -> Expr
static member Expr.Call : obj:Expr * methodInfo:MethodInfo * arguments:Expr list -> Expr
val sparams : Sem list
val RebuildShapeCombination : shape:obj * arguments:Expr list -> Expr

Full name: Microsoft.FSharp.Quotations.ExprShape.RebuildShapeCombination
val nbe : e:Expr<'a> -> Expr<'a>

Full name: Script.nbe


 Apply normalization-by-evaluation to quotation tree
val e : Expr<'a>
val empty<'Key,'T (requires comparison)> : Map<'Key,'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Map.empty
static member Expr.Cast : source:Expr -> Expr<'T>
val nbe_decompile : expr:Expr<'a> -> string

Full name: Script.nbe_decompile
val expr : Expr<'a>
namespace Swensen
namespace Swensen.Unquote
module Operators

from Swensen.Unquote
val decompile : expr:Expr -> string

Full name: Swensen.Unquote.Operators.decompile
val f : (int option -> bool)
val x : int option
val mutable y : int
val f : (int -> int)
val x : int
val z : int
val f : (int -> unit)
type Console =
  static member BackgroundColor : ConsoleColor with get, set
  static member Beep : unit -> unit + 1 overload
  static member BufferHeight : int with get, set
  static member BufferWidth : int with get, set
  static member CapsLock : bool
  static member Clear : unit -> unit
  static member CursorLeft : int with get, set
  static member CursorSize : int with get, set
  static member CursorTop : int with get, set
  static member CursorVisible : bool with get, set
  ...

Full name: System.Console
Console.WriteLine() : unit
   (+0 other overloads)
Console.WriteLine(value: string) : unit
   (+0 other overloads)
Console.WriteLine(value: obj) : unit
   (+0 other overloads)
Console.WriteLine(value: uint64) : unit
   (+0 other overloads)
Console.WriteLine(value: int64) : unit
   (+0 other overloads)
Console.WriteLine(value: uint32) : unit
   (+0 other overloads)
Console.WriteLine(value: int) : unit
   (+0 other overloads)
Console.WriteLine(value: float32) : unit
   (+0 other overloads)
Console.WriteLine(value: float) : unit
   (+0 other overloads)
Console.WriteLine(value: decimal) : unit
   (+0 other overloads)
type Stream<'T> = ('T -> unit) -> unit

Full name: Script.Stream<_>
type unit = Unit

Full name: Microsoft.FSharp.Core.unit
val ofArray : (int [] -> (int -> unit) -> unit)
val xs : int []
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
val k : (int -> unit)
val map : ((int -> int) -> Stream<int> -> Stream<int>)
val ts : Stream<int>
val t : int
val filter : ((int -> bool) -> Stream<int> -> Stream<int>)
val f : (int -> bool)
val iter : ((int -> unit) -> Stream<int> -> unit)
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn

More information

Link:http://fssnip.net/7Xn
Posted:2 days ago
Author:Eirik Tsarpalis
Tags: metaprogramming , quotations