ackermann imperative vs functional

ackermann.pas

MODULE ackerman;
 
IMPORT  Out, Integers;
 
VAR     m, n, BigOne, BigZero  : Integers.Integer;
s : ARRAY 256 OF CHAR;
 
PROCEDURE Ackerman (x, y   : Integers.Integer) : Integers.Integer;
 
BEGIN
  IF    Integers.Compare(x,BigZero)=0  THEN  RETURN  Integers.Sum(y, BigOne)
  ELSIF Integers.Compare(y, BigZero)=0  THEN  RETURN  Ackerman (Integers.Difference(x, BigOne) , BigOne)
  ELSE
    RETURN  Ackerman (Integers.Difference(x, BigOne) , Ackerman (x , Integers.Difference(y, BigOne)))
  END
END Ackerman;
 
PROCEDURE Do*;
BEGIN
BigOne := Integers.Long(1);
BigZero := Integers.Long(0);
Integers.ConvertToString(Ackerman (Integers.Long(3), Integers.Long(9)), s);
Out.String (s);
Out.Char (9X);
Out.String("Finished");
END Do;
END ackerman.

ackerman.Do;

functional.fs

module Tramp =
    type TrampValue<'T> =
        | DelayValue of Delay<'T>
        | ReturnValue of Return<'T>
        | BindValue of IBind<'T>
    and ITramp<'T> = 
        abstract member Value : TrampValue<'T>
        abstract member Run : unit -> 'T

    and Delay<'T>(f : unit -> ITramp<'T>) =
        member self.Func = f 
        interface ITramp<'T> with
            member self.Value = DelayValue self
            member self.Run () = (f ()).Run()

    and Return<'T>(x :'T) = 
        member self.Value = x
        interface ITramp<'T> with
            member self.Value = ReturnValue self
            member self.Run () = x

    and IBind<'T> = 
        abstract Bind<'R> : ('T -> ITramp<'R>) -> ITramp<'R>
    and Bind<'T, 'R>(tramp : ITramp<'T>, f : ('T -> ITramp<'R>)) = 
        interface IBind<'R> with
            member self.Bind<'K>(f' : 'R -> ITramp<'K>) : ITramp<'K> =
                new Bind<'T, 'K>(tramp, fun t -> new Bind<'R, 'K>(f t, (fun r -> f' r)) :> _) :> _
        interface ITramp<'R> with
            member self.Value = BindValue self
            member self.Run () = 
                match tramp.Value with
                | BindValue b -> b.Bind(f).Run() 
                | ReturnValue r -> (f r.Value).Run()
                | DelayValue d -> (new Bind<'T, 'R>(d.Func (), f) :> ITramp<'R>).Run() 

    // Builder
    type TrampBuilder() = 
        member self.Return a = new Return<_>(a) :> ITramp<_>
        member self.Bind(tramp, f) = 
            new Bind<'T, 'R>(tramp, f) :> ITramp<'R>
        member self.Delay f = 
            new Delay<_>(f) :> ITramp<_>
   
    let tramp = new TrampBuilder()

    let run (tramp : ITramp<'T>) = tramp.Run()


module Test =
    let zero = bigint(0)
    let one = bigint(1)
    //int 1002 in 0.363400
    //bigint 1000 in 0.578400
    let rec ack (m:bigint) (n:bigint) = 
        if m = zero then (n + one) 
        elif n = zero then ack (m-one) one 
        else ack (m-one) (ack m (n-one))

    let ackT (m:bigint) (n:bigint)  = 
        let rec acI (m:bigint) (n:bigint) cnt =
            if m = zero then cnt(n + one)
            elif n = zero then acI (m-one) one cnt
            else (acI m (n-one) (fun x -> acI (m-one) x cnt))
        acI m n id

    open Tramp
    let ackTramp (m:bigint) (n:bigint) = 
        let rec ack (m:bigint) (n:bigint)  = 
            tramp{
                if m = zero then return (n + one) 
                elif n = zero then let! x = ack (m-one) one 
                                   return x
                else let! y = ack m (n-one)
                     let! x = ack (m-one)  y
                     return x
            }
        ack m n |> run 

    let test (m:int) (n:int) name fn =

        let sw = System.Diagnostics.Stopwatch.StartNew()
        try
            let r = fn <| bigint(m) <| bigint(n) 
            sw.Stop()

            printfn "%s n=%d m=%d res=%A in %f" name n m r sw.Elapsed.TotalMilliseconds
        with |ex -> printfn "ex %A" ex
open Test
[<EntryPoint>]
let main argv = 
    //warmup
    test 3 4 "ack" ack
    test 3 4 "ackT" ackT
    test 3 4 "ackTramp" ackTramp

    test 3 4 "ack" ack
    test 3 4 "ackT" ackT
    test 3 4 "ackTramp" ackTramp

    //test 3 8 "ack" ack //stack overflow
    test 3 9 "ackT" ackT
    test 3 9 "ackTramp" ackTramp
    System.Console.ReadLine() |> ignore
    0 // return an integer exit code

Imperative.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;

namespace Ack
{

    class Program
    {
        static void Main(string[] args)
        {
            Test("Ackermann", 3, 4, Ackermann);
            Test("AckermannStack", 3, 4, AckermannStack);
            Test("AckermannOptimized", 3, 4, AckermannOptimized);

            Test("Ackermann", 3, 4, Ackermann);
            Test("AckermannStack", 3, 4, AckermannStack);
            Test("AckermannOptimized", 3, 4, AckermannOptimized);

            Test("Ackermann", 3, 9, Ackermann);
            Test("AckermannStack", 3, 9, AckermannStack);
            Test("AckermannOptimized", 3, 9, AckermannOptimized);
            Console.ReadLine();
        }

        public static void Test(string name, int m, int n, Func<BigInteger,BigInteger,BigInteger> fn) {
            var sw = System.Diagnostics.Stopwatch.StartNew();
            var r = fn(m, n);
            sw.Stop();
            Console.WriteLine(String.Format("{0} {1} {2} {3} {4}", name, n, m, r, sw.Elapsed.TotalMilliseconds));
        }

        public static BigInteger Ackermann(BigInteger m, BigInteger n)
        {
            if (m == 0)
                return n + 1;
            if (n == 0)
                return Ackermann(m - 1, 1);
            else
                return Ackermann(m - 1, Ackermann(m, n - 1));
        }

        public static BigInteger AckermannStack(BigInteger m, BigInteger n)
        {
            Stack<BigInteger> stack = new Stack<BigInteger>();
            stack.Push(m);
            while (stack.Count != 0)
            {
                m = stack.Pop();
                skipStack:
                if (m == 0)
                    n = n + 1;
                else if (n == 0)
                {
                    --m;
                    n = 1;
                    goto skipStack;
                }
                else
                {
                    stack.Push(m - 1);
                    --n;
                    goto skipStack;
                }
            }
            return n;
        }

        public static BigInteger AckermannOptimized(BigInteger m, BigInteger n)
        {
            var stack = new OverflowlessStack<BigInteger>();
            stack.Push(m);
            while (!stack.IsEmpty)
            {
                m = stack.Pop();
                skipStack:
                if (m == 0)
                    n = n + 1;
                else if (m == 1)
                    n = n + 2;
                else if (m == 2)
                    n = n * 2 + 3;
                else if (n == 0)
                {
                    --m;
                    n = 1;
                    goto skipStack;
                }
                else
                {
                    stack.Push(m - 1);
                    --n;
                    goto skipStack;
                }
            }
            return n;
        }
    }

    public class OverflowlessStack<T>
    {
        internal sealed class SinglyLinkedNode
        {
            //Larger the better, but we want to be low enough
            //to demonstrate the case where we overflow a node
            //and hence create another.
            private const int ArraySize = 2048;
            T[] _array;
            int _size;
            public SinglyLinkedNode Next;
            public SinglyLinkedNode()
            {
                _array = new T[ArraySize];
            }
            public bool IsEmpty { get { return _size == 0; } }
            public SinglyLinkedNode Push(T item)
            {
                if (_size == ArraySize - 1)
                {
                    SinglyLinkedNode n = new SinglyLinkedNode();
                    n.Next = this;
                    n.Push(item);
                    return n;
                }
                _array[_size++] = item;
                return this;
            }
            public T Pop()
            {
                return _array[--_size];
            }
        }
        private SinglyLinkedNode _head = new SinglyLinkedNode();

        public T Pop()
        {
            T ret = _head.Pop();
            if (_head.IsEmpty && _head.Next != null)
                _head = _head.Next;
            return ret;
        }
        public void Push(T item)
        {
            _head = _head.Push(item);
        }
        public bool IsEmpty
        {
            get { return _head.Next == null && _head.IsEmpty; }
        }
    }

}

results.txt

functional(warmed) f# fsi 14.0.23413.0
ack n=4 m=3 res=125 in 1.666900
ackT n=4 m=3 res=125 in 11.235900
ackTramp n=4 m=3 res=125 in 15.884900
ack n=9 m=3 res=stack overflow
ackT n=9 m=3 res=4093 in 7461.394700
ackTramp n=9 m=3 res=4093 in 15940.763000

functional(warmed) f# 4.0 
ack n=4 m=3 res=125 in 1.854900
ackT n=4 m=3 res=1 in 0.212700
ackTramp n=4 m=3 res=125 in 8.160000
ack n=9 m=3 res=stack overflow
ackT n=9 m=3 res=1 in 0.271000
ackTramp n=9 m=3 res=4093 in 8187.301100

imperative(warmed) c# console
Ackermann(BigInt) 4 3 125 1,456
AckermannStack 4 3 125 1,0506
AckermannOptimized 4 3 125 0,0125
Ackermann(int) 9 3 4093 25,909
Ackermann(BigInt) 9 3 4093 1456,909
AckermannStack 9 3 4093 1070,6599
AckermannOptimized 9 3 4093 0,0135

imperative BlackBox component pascal
Ackermann(int) 4 9 125 78,0
Ackermann(BigInt) 4 9 125 2578,0