4 people like it.

Complete lambda calculus interpreter with example of Y-combinator recursion

Calculate triangle numbers in the most inefficient way possible!

  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: 
273: 
274: 
275: 
276: 
277: 
278: 
279: 
280: 
281: 
282: 
283: 
284: 
285: 
286: 
287: 
288: 
289: 
290: 
291: 
/// Based on https://opendsa-server.cs.vt.edu/ODSA/Books/PL/html/index.html#lambda-calculus
namespace LambdaCalculus

open System

/// A variable in a lambda expression.
type Variable = string (*name*)

/// Lambda expression.
[<StructuredFormatDisplay("{String}")>]
type Expr =

    /// E.g. "x"
    | Variable of Variable

    /// E.g. "(x y)"
    | Application of (Expr (*function*) * Expr (*argument*))

    /// E.g. "λx.y"
    | Lambda of (Variable (*parameter*) * Expr (*body*))

    /// Converts expression to string.
    member this.String =
        match this with
            | Variable name -> name
            | Application (func, arg) -> sprintf "(%A %A)" func arg
            | Lambda (param, body) -> sprintf %s.%A" param body

    /// Converts expression to string.
    override this.ToString() = this.String

/// Lambda expression functions.
[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module Expr =

    /// Interop with F# quotations.
    module private FSharp =

        open Microsoft.FSharp.Quotations.Patterns

        /// Constructs a lambda expression from an F# quotation.
        let rec ofQuot =
            function
                | Var var -> Variable var.Name    // bound
                | ValueWithName (_, _, name) ->   // free
                    Variable name
                | Application (func, arg) ->
                    Application (ofQuot func, ofQuot arg)
                | Lambda (param, body) ->
                    Lambda (param.Name, ofQuot body)
                | expr -> failwithf "Not supported: %A" expr

    let ofQuot = FSharp.ofQuot

    module private Parse =

        open FParsec

        let private parseExpr, private parseExprRef =
            createParserForwardedToRef<Expr, unit>()

        let private parseName =
            many1Chars (satisfy (fun c ->
                Char.IsLetterOrDigit(c) && (c <> 'λ')))

        let private parseVariable =
            parseName
                |>> Variable

        let private parseApplication =
            pipe5
                (skipChar '(')
                parseExpr
                (many1 <| skipChar ' ')
                parseExpr
                (skipChar ')')
                (fun _ func _ arg _ ->
                    Application (func, arg))

        let private parseLambda =
            pipe4
                (skipAnyOf ['λ'; '^'; '\\'])
                parseName
                (skipChar '.')
                parseExpr
                (fun _ param _ body ->
                    Lambda (param, body))

        do parseExprRef :=
            choice [
                parseVariable
                parseApplication
                parseLambda
            ]

        let parse str =
            let parser = !parseExprRef .>> eof   // force consumption of entire string
            match run parser str with
                | Success (expr, _, _) -> expr
                | Failure (msg, _, _) -> failwith msg

    let parse = Parse.parse

    let toString (expr : Expr) =
        expr.ToString()

    /// Indicates whether the given variable occurs within a lambda expression (either
    /// bound or free).
    let rec occurs name =
        function
            | Variable name' ->
                name' = name
            | Application (func, arg) ->
                occurs name func || occurs name arg
            | Lambda (param, body) ->
                (param = name) || occurs name body

    /// Indicates whether the given variable occurs free within a lambda expression.
    /// (Note that it might occur both free and bound.)
    let rec occursFree name =
        function
            | Variable name' ->
                name' = name
            | Application (func, arg) ->
                occursFree name func || occursFree name arg
            | Lambda (param, body) ->
                (param <> name) && occursFree name body

    /// α-conversion.
    let alphaConvert newName lambda =

        let rec convert oldName newName expr =
            let convert = convert oldName newName
            match expr with
                | Variable name ->
                    assert(name <> newName)
                    if name = oldName then Variable newName   // rename variable
                    else expr
                | Application (func, arg) ->
                    Application ((convert func), (convert arg))
                | Lambda (param, body) ->                     // inner lambda
                    assert(param <> newName)
                    Lambda (param, convert body)

        if occurs newName lambda then
            failwithf "New name '%s' already appears in %A" newName lambda
        match lambda with
            | Lambda (param, body) ->
                Lambda (newName, convert param newName body)
            | _ -> failwithf "α-conversion not supported for %A" lambda

    module Option =
        let defaultWith defThunk option = match option with None -> defThunk () | Some v -> v

    /// Replaces all occurrences of param with arg in body.
    let rec substitute arg param body =

        /// Answers the set of all variables in the given expression.
        let allVariables expr =
            let rec loop expr : seq<string> =
                seq {
                    match expr with
                        | Variable name -> yield name
                        | Application (func, arg) ->
                            yield! loop func
                            yield! loop arg
                        | Lambda (param, body) ->
                            yield param
                            yield! loop body
                }
            loop expr |> Set.ofSeq

        let subst = substitute arg param
        match body with
            | Variable name ->
                if name = param then arg            // replace this variable with the new expression
                else body                           // no-op
            | Application (func, arg) ->
                Application (subst func, subst arg)
            | Lambda (param', body') ->
                if param' = param then body         // no-op (don't actually substitute anything)
                elif occursFree param' arg then     // avoid variable capture
                    let allVars = allVariables body
                    ['a' .. 'z']
                        |> Seq.map (fun c -> c.ToString())
                        |> Seq.tryFind (fun newName ->
                            not <| allVars.Contains(newName))
                        |> Option.map (fun newName ->
                            alphaConvert newName body
                                |> subst)
                        |> Option.defaultWith (fun () ->
                            failwithf "Exhausted variable names for α-conversion")
                else Lambda (param', subst body')   // substitute new expression in lambda body

    /// Reduces a β-reduction expression ("β-redex"). This is
    /// function evaluation, which "calls" the given lambda
    /// with the given argument.
    let betaReduce =
        function
            | Application (Lambda (param, body), arg) ->
                substitute arg param body
            | expr -> failwithf "%A is not a β-redex" expr

    /// Evaluates the given expression lazily (normal order).
    /// See reduceLeftmostOutermostBetaRedex and reduceToNormalForm in
    /// https://opendsa-server.cs.vt.edu/ODSA/AV/PL/interpreters/lambdacalc/version1.4.used.in.book/scripts/interpreter.js
    let eval expr =

        let rec containsBetaRedex =
            function
                | Variable _ -> false
                | Application (Lambda (_, _), _) -> true
                | Application (func, arg) ->
                    containsBetaRedex func || containsBetaRedex arg
                | Lambda (_, body) ->
                    containsBetaRedex body

        let rec reduceLazy expr =
            match expr with
                | Variable _ -> expr
                | Application (Lambda (_, _), _) ->
                    betaReduce expr
                | Application (func, arg) ->
                    if containsBetaRedex func then
                        Application (reduceLazy func, arg)
                    elif containsBetaRedex arg then
                        Application (func, reduceLazy arg)
                    else expr
                | Lambda (param, body) ->
                    Lambda (param, reduceLazy body)

        let rec loop expr =
            if containsBetaRedex expr then
                reduceLazy expr |> loop
            else expr

        loop expr

[<AutoOpen>]
module Lang =

    let True = <@@ fun x y -> x @@> |> Expr.ofQuot
    let False = <@@ fun x y -> y @@> |> Expr.ofQuot
    let If = <@@ fun b x y -> b x y @@> |> Expr.ofQuot
    let And = sprintf "λp.λq.((p q) %A)" False |> Expr.parse
    let Or = sprintf "λp.λq.((p %A) q)" True |> Expr.parse

    let Zero =  <@@ fun f x -> x @@> |> Expr.ofQuot   // same as False
    let One =   <@@ fun f x -> f x @@> |> Expr.ofQuot
    let Two =   <@@ fun f x -> f (f x) @@> |> Expr.ofQuot
    let Three = <@@ fun f x -> f (f (f x)) @@> |> Expr.ofQuot
    let Four =  <@@ fun f x -> f (f (f (f x))) @@> |> Expr.ofQuot
    let Five =  <@@ fun f x -> f (f (f (f (f x)))) @@> |> Expr.ofQuot
    let Six =   <@@ fun f x -> f (f (f (f (f (f x))))) @@> |> Expr.ofQuot
    let Seven = <@@ fun f x -> f (f (f (f (f (f (f x)))))) @@> |> Expr.ofQuot
    let Eight = <@@ fun f x -> f (f (f (f (f (f (f (f x))))))) @@> |> Expr.ofQuot
    let Nine =  <@@ fun f x -> f (f (f (f (f (f (f (f (f x)))))))) @@> |> Expr.ofQuot
    let Ten =   <@@ fun f x -> f (f (f (f (f (f (f (f (f (f x))))))))) @@> |> Expr.ofQuot

    let Succ = <@@ fun n f x -> f ((n f) x) @@> |> Expr.ofQuot
    let Plus = <@@ fun m n f x -> (n f) ((m f) x) @@> |> Expr.ofQuot
    let Mult = <@@ fun m n f -> m (n f) @@> |> Expr.ofQuot

    /// Y-combinator for recursion
    let Y = "λh.(λx.(h (x x)) λx.(h (x x)))" |> Expr.parse

module Program =

    [<EntryPoint>]
    let main argv =

        // display λ chars correctly
        Console.OutputEncoding <- Text.Encoding.Unicode

        let IsZero =
            sprintf "λn.((n λx.%A) %A)" False True
                |> Expr.parse
        let Pred =
            "λn.λf.λx.(((n λg.λh.(h (g f))) λu.x) λu.u)"
                |> Expr.parse
        let TriangleNonRecursive =
            sprintf "λg.λn.(((%A (%A n)) %A) ((%A n) (g (%A n))))" If IsZero Zero Plus Pred
                |> Expr.parse
        let TriangleRecursive =
            sprintf "(%A %A)" Y TriangleNonRecursive
                |> Expr.parse
        let expr =
            sprintf "(%A %A)" TriangleRecursive Four |> Expr.parse |> Expr.eval
        printfn "%A" expr

        0
namespace System
type Variable = string

Full name: LambdaCalculus.Variable


 A variable in a lambda expression.
Multiple items
val string : value:'T -> string

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

--------------------
type string = String

Full name: Microsoft.FSharp.Core.string
Multiple items
type StructuredFormatDisplayAttribute =
  inherit Attribute
  new : value:string -> StructuredFormatDisplayAttribute
  member Value : string

Full name: Microsoft.FSharp.Core.StructuredFormatDisplayAttribute

--------------------
new : value:string -> StructuredFormatDisplayAttribute
type Expr =
  | Variable of Variable
  | Application of (Expr * Expr)
  | Lambda of (Variable * Expr)
  override ToString : unit -> string
  member String : Variable

Full name: LambdaCalculus.Expr


 Lambda expression.
Multiple items
union case Expr.Variable: Variable -> Expr


 E.g. "x"


--------------------
type Variable = string

Full name: LambdaCalculus.Variable


 A variable in a lambda expression.
union case Expr.Application: (Expr * Expr) -> Expr


 E.g. "(x y)"
union case Expr.Lambda: (Variable * Expr) -> Expr


 E.g. "λx.y"
val this : Expr
Multiple items
member Expr.String : Variable

Full name: LambdaCalculus.Expr.String


 Converts expression to string.


--------------------
type String =
  new : value:char -> string + 7 overloads
  member Chars : int -> char
  member Clone : unit -> obj
  member CompareTo : value:obj -> int + 1 overload
  member Contains : value:string -> bool
  member CopyTo : sourceIndex:int * destination:char[] * destinationIndex:int * count:int -> unit
  member EndsWith : value:string -> bool + 2 overloads
  member Equals : obj:obj -> bool + 2 overloads
  member GetEnumerator : unit -> CharEnumerator
  member GetHashCode : unit -> int
  ...

Full name: System.String

--------------------
String(value: nativeptr<char>) : unit
String(value: nativeptr<sbyte>) : unit
String(value: char []) : unit
String(c: char, count: int) : unit
String(value: nativeptr<char>, startIndex: int, length: int) : unit
String(value: nativeptr<sbyte>, startIndex: int, length: int) : unit
String(value: char [], startIndex: int, length: int) : unit
String(value: nativeptr<sbyte>, startIndex: int, length: int, enc: Text.Encoding) : unit
val name : Variable
val func : Expr
val arg : Expr
val sprintf : format:Printf.StringFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.sprintf
val param : Variable
val body : Expr
override Expr.ToString : unit -> string

Full name: LambdaCalculus.Expr.ToString


 Converts expression to string.
property Expr.String: Variable


 Converts expression to string.
Multiple items
type CompilationRepresentationAttribute =
  inherit Attribute
  new : flags:CompilationRepresentationFlags -> CompilationRepresentationAttribute
  member Flags : CompilationRepresentationFlags

Full name: Microsoft.FSharp.Core.CompilationRepresentationAttribute

--------------------
new : flags:CompilationRepresentationFlags -> CompilationRepresentationAttribute
type CompilationRepresentationFlags =
  | None = 0
  | Static = 1
  | Instance = 2
  | ModuleSuffix = 4
  | UseNullAsTrueValue = 8
  | Event = 16

Full name: Microsoft.FSharp.Core.CompilationRepresentationFlags
CompilationRepresentationFlags.ModuleSuffix: CompilationRepresentationFlags = 4
namespace Microsoft.FSharp
namespace Microsoft
namespace Microsoft.FSharp.Quotations
module Patterns

from Microsoft.FSharp.Quotations
val private ofQuot : _arg1:Quotations.Expr -> Expr

Full name: LambdaCalculus.ExprModule.FSharp.ofQuot


 Constructs a lambda expression from an F# quotation.
active recognizer Var: Quotations.Expr -> Quotations.Var option

Full name: Microsoft.FSharp.Quotations.Patterns.( |Var|_| )
val var : Quotations.Var
property Quotations.Var.Name: string
active recognizer ValueWithName: Quotations.Expr -> (obj * Type * string) option

Full name: Microsoft.FSharp.Quotations.Patterns.( |ValueWithName|_| )
val name : string
Multiple items
union case Expr.Application: (Expr * Expr) -> Expr


 E.g. "(x y)"


--------------------
active recognizer Application: Quotations.Expr -> (Quotations.Expr * Quotations.Expr) option

Full name: Microsoft.FSharp.Quotations.Patterns.( |Application|_| )
val func : Quotations.Expr
val arg : Quotations.Expr
Multiple items
union case Expr.Lambda: (Variable * Expr) -> Expr


 E.g. "λx.y"


--------------------
active recognizer Lambda: Quotations.Expr -> (Quotations.Var * Quotations.Expr) option

Full name: Microsoft.FSharp.Quotations.Patterns.( |Lambda|_| )
val param : Quotations.Var
val body : Quotations.Expr
val expr : Quotations.Expr
val failwithf : format:Printf.StringFormat<'T,'Result> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.failwithf
val ofQuot : (Quotations.Expr -> Expr)

Full name: LambdaCalculus.ExprModule.ofQuot
Multiple items
module FSharp

from LambdaCalculus.ExprModule


 Interop with F# quotations.


--------------------
namespace Microsoft.FSharp
namespace FParsec
val private parseExpr : Parser<Expr,unit>

Full name: LambdaCalculus.ExprModule.Parse.parseExpr
val private parseExprRef : Parser<Expr,unit> ref

Full name: LambdaCalculus.ExprModule.Parse.parseExprRef
val createParserForwardedToRef : unit -> Parser<'a,'u> * Parser<'a,'u> ref

Full name: FParsec.Primitives.createParserForwardedToRef
type unit = Unit

Full name: Microsoft.FSharp.Core.unit
val private parseName : Parser<string,unit>

Full name: LambdaCalculus.ExprModule.Parse.parseName
val many1Chars : Parser<char,'u> -> Parser<string,'u>

Full name: FParsec.CharParsers.many1Chars
val satisfy : (char -> bool) -> Parser<char,'u>

Full name: FParsec.CharParsers.satisfy
val c : char
type Char =
  struct
    member CompareTo : value:obj -> int + 1 overload
    member Equals : obj:obj -> bool + 1 overload
    member GetHashCode : unit -> int
    member GetTypeCode : unit -> TypeCode
    member ToString : unit -> string + 1 overload
    static val MaxValue : char
    static val MinValue : char
    static member ConvertFromUtf32 : utf32:int -> string
    static member ConvertToUtf32 : highSurrogate:char * lowSurrogate:char -> int + 1 overload
    static member GetNumericValue : c:char -> float + 1 overload
    ...
  end

Full name: System.Char
Char.IsLetterOrDigit(c: char) : bool
Char.IsLetterOrDigit(s: string, index: int) : bool
val private parseVariable : Parser<Expr,unit>

Full name: LambdaCalculus.ExprModule.Parse.parseVariable
val private parseApplication : Parser<Expr,unit>

Full name: LambdaCalculus.ExprModule.Parse.parseApplication
val pipe5 : Parser<'a,'u> -> Parser<'b,'u> -> Parser<'c,'u> -> Parser<'d,'u> -> Parser<'e,'u> -> ('a -> 'b -> 'c -> 'd -> 'e -> 'f) -> Parser<'f,'u>

Full name: FParsec.Primitives.pipe5
val skipChar : char -> Parser<unit,'u>

Full name: FParsec.CharParsers.skipChar
val many1 : Parser<'a,'u> -> Parser<'a list,'u>

Full name: FParsec.Primitives.many1
val private parseLambda : Parser<Expr,unit>

Full name: LambdaCalculus.ExprModule.Parse.parseLambda
val pipe4 : Parser<'a,'u> -> Parser<'b,'u> -> Parser<'c,'u> -> Parser<'d,'u> -> ('a -> 'b -> 'c -> 'd -> 'e) -> Parser<'e,'u>

Full name: FParsec.Primitives.pipe4
val skipAnyOf : seq<char> -> Parser<unit,'u>

Full name: FParsec.CharParsers.skipAnyOf
val param : string
val choice : seq<Parser<'a,'u>> -> Parser<'a,'u>

Full name: FParsec.Primitives.choice
val private parse : str:string -> Expr

Full name: LambdaCalculus.ExprModule.Parse.parse
val str : string
val parser : Parser<Expr,unit>
val eof : Parser<unit,'u>

Full name: FParsec.CharParsers.eof
val run : Parser<'Result,unit> -> string -> ParserResult<'Result,unit>

Full name: FParsec.CharParsers.run
union case ParserResult.Success: 'Result * 'UserState * Position -> ParserResult<'Result,'UserState>
val expr : Expr
union case ParserResult.Failure: string * ParserError * 'UserState -> ParserResult<'Result,'UserState>
val msg : string
val failwith : message:string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith
val parse : (string -> Expr)

Full name: LambdaCalculus.ExprModule.parse
module Parse

from LambdaCalculus.ExprModule
val toString : expr:Expr -> string

Full name: LambdaCalculus.ExprModule.toString
override Expr.ToString : unit -> string


 Converts expression to string.
val occurs : name:Variable -> _arg1:Expr -> bool

Full name: LambdaCalculus.ExprModule.occurs


 Indicates whether the given variable occurs within a lambda expression (either
 bound or free).
val name' : Variable
val occursFree : name:Variable -> _arg1:Expr -> bool

Full name: LambdaCalculus.ExprModule.occursFree


 Indicates whether the given variable occurs free within a lambda expression.
 (Note that it might occur both free and bound.)
val alphaConvert : newName:Variable -> lambda:Expr -> Expr

Full name: LambdaCalculus.ExprModule.alphaConvert


 α-conversion.
val newName : Variable
val lambda : Expr
val convert : (Variable -> Variable -> Expr -> Expr)
val oldName : Variable
val convert : (Expr -> Expr)
module Option

from Microsoft.FSharp.Core
val defaultWith : defThunk:(unit -> 'a) -> option:'a option -> 'a

Full name: LambdaCalculus.ExprModule.Option.defaultWith
val defThunk : (unit -> 'a)
Multiple items
val option : 'a option

--------------------
type 'T option = Option<'T>

Full name: Microsoft.FSharp.Core.option<_>
union case Option.None: Option<'T>
union case Option.Some: Value: 'T -> Option<'T>
val v : 'a
val substitute : arg:Expr -> param:Variable -> body:Expr -> Expr

Full name: LambdaCalculus.ExprModule.substitute


 Replaces all occurrences of param with arg in body.
val allVariables : (Expr -> Set<string>)


 Answers the set of all variables in the given expression.
val loop : (Expr -> seq<string>)
Multiple items
val seq : sequence:seq<'T> -> seq<'T>

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

--------------------
type seq<'T> = Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>
Multiple items
module Set

from Microsoft.FSharp.Collections

--------------------
type Set<'T (requires comparison)> =
  interface IComparable
  interface IEnumerable
  interface IEnumerable<'T>
  interface ICollection<'T>
  new : elements:seq<'T> -> Set<'T>
  member Add : value:'T -> Set<'T>
  member Contains : value:'T -> bool
  override Equals : obj -> bool
  member IsProperSubsetOf : otherSet:Set<'T> -> bool
  member IsProperSupersetOf : otherSet:Set<'T> -> bool
  ...

Full name: Microsoft.FSharp.Collections.Set<_>

--------------------
new : elements:seq<'T> -> Set<'T>
val ofSeq : elements:seq<'T> -> Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.ofSeq
val subst : (Expr -> Expr)
val param' : Variable
val body' : Expr
val allVars : Set<string>
module Seq

from Microsoft.FSharp.Collections
val map : mapping:('T -> 'U) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.map
Char.ToString() : string
Char.ToString(provider: IFormatProvider) : string
val tryFind : predicate:('T -> bool) -> source:seq<'T> -> 'T option

Full name: Microsoft.FSharp.Collections.Seq.tryFind
val newName : string
val not : value:bool -> bool

Full name: Microsoft.FSharp.Core.Operators.not
member Set.Contains : value:'T -> bool
Multiple items
module Option

from LambdaCalculus.ExprModule

--------------------
module Option

from Microsoft.FSharp.Core
val map : mapping:('T -> 'U) -> option:'T option -> 'U option

Full name: Microsoft.FSharp.Core.Option.map
val betaReduce : _arg1:Expr -> Expr

Full name: LambdaCalculus.ExprModule.betaReduce


 Reduces a β-reduction expression ("β-redex"). This is
 function evaluation, which "calls" the given lambda
 with the given argument.
val eval : expr:Expr -> Expr

Full name: LambdaCalculus.ExprModule.eval


 Evaluates the given expression lazily (normal order).
 See reduceLeftmostOutermostBetaRedex and reduceToNormalForm in
 https://opendsa-server.cs.vt.edu/ODSA/AV/PL/interpreters/lambdacalc/version1.4.used.in.book/scripts/interpreter.js
val containsBetaRedex : (Expr -> bool)
val reduceLazy : (Expr -> Expr)
val loop : (Expr -> Expr)
Multiple items
type AutoOpenAttribute =
  inherit Attribute
  new : unit -> AutoOpenAttribute
  new : path:string -> AutoOpenAttribute
  member Path : string

Full name: Microsoft.FSharp.Core.AutoOpenAttribute

--------------------
new : unit -> AutoOpenAttribute
new : path:string -> AutoOpenAttribute
val True : Expr

Full name: LambdaCalculus.Lang.True
val x : obj
val y : obj
Multiple items
module Expr

from LambdaCalculus


 Lambda expression functions.


--------------------
type Expr =
  | Variable of Variable
  | Application of (Expr * Expr)
  | Lambda of (Variable * Expr)
  override ToString : unit -> string
  member String : Variable

Full name: LambdaCalculus.Expr


 Lambda expression.
val False : Expr

Full name: LambdaCalculus.Lang.False
val If : Expr

Full name: LambdaCalculus.Lang.If
val b : (obj -> obj -> obj)
val And : Expr

Full name: LambdaCalculus.Lang.And
val Or : Expr

Full name: LambdaCalculus.Lang.Or
val Zero : Expr

Full name: LambdaCalculus.Lang.Zero
val f : obj
val One : Expr

Full name: LambdaCalculus.Lang.One
val f : (obj -> obj)
val Two : Expr

Full name: LambdaCalculus.Lang.Two
val Three : Expr

Full name: LambdaCalculus.Lang.Three
val Four : Expr

Full name: LambdaCalculus.Lang.Four
val Five : Expr

Full name: LambdaCalculus.Lang.Five
val Six : Expr

Full name: LambdaCalculus.Lang.Six
val Seven : Expr

Full name: LambdaCalculus.Lang.Seven
val Eight : Expr

Full name: LambdaCalculus.Lang.Eight
val Nine : Expr

Full name: LambdaCalculus.Lang.Nine
val Ten : Expr

Full name: LambdaCalculus.Lang.Ten
val Succ : Expr

Full name: LambdaCalculus.Lang.Succ
val n : ((obj -> obj) -> obj -> obj)
val Plus : Expr

Full name: LambdaCalculus.Lang.Plus
val m : (obj -> obj -> obj)
val n : (obj -> obj -> obj)
val Mult : Expr

Full name: LambdaCalculus.Lang.Mult
val m : (obj -> obj)
val n : (obj -> obj)
val Y : Expr

Full name: LambdaCalculus.Lang.Y


 Y-combinator for recursion
module Program

from LambdaCalculus
Multiple items
type EntryPointAttribute =
  inherit Attribute
  new : unit -> EntryPointAttribute

Full name: Microsoft.FSharp.Core.EntryPointAttribute

--------------------
new : unit -> EntryPointAttribute
val main : argv:string [] -> int

Full name: LambdaCalculus.Program.main
val argv : string []
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
property Console.OutputEncoding: Text.Encoding
namespace System.Text
type Encoding =
  member BodyName : string
  member Clone : unit -> obj
  member CodePage : int
  member DecoderFallback : DecoderFallback with get, set
  member EncoderFallback : EncoderFallback with get, set
  member EncodingName : string
  member Equals : value:obj -> bool
  member GetByteCount : chars:char[] -> int + 3 overloads
  member GetBytes : chars:char[] -> byte[] + 5 overloads
  member GetCharCount : bytes:byte[] -> int + 2 overloads
  ...

Full name: System.Text.Encoding
property Text.Encoding.Unicode: Text.Encoding
val IsZero : Expr
val Pred : Expr
val TriangleNonRecursive : Expr
val TriangleRecursive : Expr
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
Raw view Test code New version

More information

Link:http://fssnip.net/7W7
Posted:5 years ago
Author:Brian Berns
Tags: currying , lambda calculus , logic , parsing , quotation , y-combinator