2 people like it.

# Staged Ackermann

Partial evaluating the Ackermann function.

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: ``` ``````// http://lambda-the-ultimate.org/node/4039#comment-61431 open Microsoft.FSharp.Quotations // <@ fun x -> (% <@ x @> ) @> ~ lambda (fun x -> x) let lambda (f : Expr<'T> -> Expr<'R>) : Expr<'T -> 'R> = let var = new Var("__temp__", typeof<'T>) Expr.Cast<_>(Expr.Lambda(var, f (Expr.Cast<_>(Expr.Var var)))) // Staged fixed-point combinator let fix : (Expr<'T -> 'R> -> Expr<'T -> 'R>) -> Expr<'T -> 'R> = fun f -> <@ fun x -> let rec loop x = (% lambda (fun f' -> f f') ) loop x in loop x @> let rec ack (m : int) : Expr int> = fix (fun f -> lambda (fun (n : Expr) -> if m = 0 then <@ %n + 1 @> else <@ if %n = 0 then (% ack (m - 1)) 1 else (% ack (m - 1)) ((%f) (%n - 1)) @>)) // Example let ack2 = ack 2 // m=2 ``````
namespace Microsoft
namespace Microsoft.FSharp
namespace Microsoft.FSharp.Quotations
val lambda : f:(Expr<'T> -> Expr<'R>) -> Expr<('T -> 'R)>

Full name: Script.lambda
val f : (Expr<'T> -> Expr<'R>)
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<_>
val var : Var
Multiple items
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:System.Type * ?isMutable:bool -> Var
val typeof<'T> : System.Type

Full name: Microsoft.FSharp.Core.Operators.typeof
static member Expr.Cast : source:Expr -> Expr<'T>
static member Expr.Lambda : parameter:Var * body:Expr -> Expr
static member Expr.Var : variable:Var -> Expr
val fix : f:(Expr<('T -> 'R)> -> Expr<('T -> 'R)>) -> Expr<('T -> 'R)>

Full name: Script.fix
val f : (Expr<('T -> 'R)> -> Expr<('T -> 'R)>)
val x : 'T
val loop : ('T -> 'R)
val f' : Expr<('T -> 'R)>
val ack : m:int -> Expr<(int -> int)>

Full name: Script.ack
val m : 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 f : Expr<(int -> int)>
val n : Expr<int>
val ack2 : Expr<(int -> int)>

Full name: Script.ack2