Not logged in.  Login/Logout/Register | List snippets | | Create snippet | Upload image | Upload data

64
LINES

< > BotCompany Repo | #1030375 - Turn Ackermann function into a virtual stack [memory-compact version plus tail calls]

JavaX source code (Dynamic Module) [tags: use-pretranspiled] - run with: Stefan's OS

Uses 911K of libraries. Click here for Pure Java version (2453L/13K).

cprint {
  sclass VStack implements Steppable {
    new L<Computable> stack;
    O latestResult;
    
    void push(Computable computation) {
      stack.add(computation);
    }
    
    public bool step() {
      if (empty(stack)) false;
      O latestResult = this.latestResult;
      this.latestResult = null;
      last(stack).step(this, latestResult);
      true;
    }
    
    // called from computation to return a value
    void _return(O value default null) {
      latestResult = value;
      removeLast(stack);
    }
    
    // called from computation to tail-call another routine
    void tailCall(Computable computation) {
      removeLast(stack);
      stack.add(computation);
    }
  }
  
  // A is what the function returns
  asclass Computable<A> {
    abstract void step(VStack stack, O subComputationResult);
  }
  
  sclass f_ackermann extends Computable<BigInt> {
    BigInt a, b;
    int currentStep; // 0 in the beginning, goes up to 1

    *(BigInt *a, BigInt *b) {}
    
    void step(VStack stack, O subComputationResult) {
      if (currentStep == 0) {
        if (a.equals(BigInt.ZERO))
          stack._return(plus(b, BigInt.ONE));
        else if (b.equals(BigInt.ZERO))
          stack.tailCall(new f_ackermann(a.subtract(BigInt.ONE), BigInt.ONE);
        else {
          stack.push(new f_ackermann(a, minus(b, BigInt.ONE)));
          currentStep = 1;
        }
      } else if (currentStep == 1)
        stack.tailCall(new f_ackermann(minus(a, BigInt.ONE), subComputationResult/BigInt));
      else fail();
    }
  }
  
  start-thread {
    new VStack stack;
    stack.push(new f_ackermann(bigInt(2), bigInt(2)));
    stepAllWithStats(stack);
    print("Result: " + stack.latestResult);
  }
}

Author comment

Began life as a copy of #1030374

download  show line numbers  debug dex   

Travelled to 3 computer(s): bhatertpkbcr, mqqgnosmbjvj, pyentgdyhuwx

No comments. add comment

Snippet ID: #1030375
Snippet name: Turn Ackermann function into a virtual stack [memory-compact version plus tail calls]
Eternal ID of this version: #1030375/7
Text MD5: 4af1f55538e845610d786af005ed6259
Transpilation MD5: 28d79d42d49e8e99bed6bed589579e50
Author: stefan
Category: javax / maths
Type: JavaX source code (Dynamic Module)
Public (visible to everyone): Yes
Archived (hidden from active list): No
Created/modified: 2020-12-10 14:09:01
Source code size: 1791 bytes / 64 lines
Pitched / IR pitched: No / No
Views / Downloads: 25 / 87
Version history: 6 change(s)
Referenced in: [show references]

Formerly at http://tinybrain.de/1030375 & http://1030375.tinybrain.de