Transpiled version (22976L) is out of date.
// Backtracking-enabled stacks (BStacks) are very useful for AI // computation because they allow inserting a branching point anywhere // in a computation, even deep inside nested function calls and loops. // // BStacks normally operate serially, always exploring the main branch first // and then optionally backtracking afterwards. // // However, the only thing preventing a BStack from backtracking in // parallel to the main computation is the use of external mutable // objects. With sufficient cloning of these objects at a branch point // and/or the use of immutable data structures, there is no obstacle to // parallelizing. // // A further evolution of BStacks are PStacks. In PStacks, at any point // in time, every ongoing or potential computation is listed with a // probability value p (usually 0 < p <= 1). // // This "table of possible computations or continuations of computations" // constantly sorts itself by decreasing probability, so computations // with higher probability can be pursued first. // // PStack doesn't support undos because those only make sense in // serial execution. sclass PStack<A> extends VStack is IPStack { static int idCounter; int stackID = ++idCounter; // for debugging // cloned version made at last branch point selfType snapshot; // remaining options at last branch point Iterator<IVF1> options; *() {} *(Computable<A> computation) { push(computation); } *(Iterable<Computable> l) { pushAll(l); } selfType cloneStack() { new selfType s; s.snapshot = snapshot; s.options = options; s.stack = shallowCloneElements(stack); ret s; } public <B extends VStack.Computable> void options(B function, IVF1<B>... options) { options(function, arrayIterator(options)); } public <B extends VStack.Computable> void options(B function, Iterable<IVF1<B>> options) { Iterator<IVF1<B>> iterator = nonNullIterator(iterator(options)); if (!iterator.hasNext()) throw new NoOptionsException; IVF1<B> firstOption = iterator.next(); // All options except first are stored as alternatives // in cloned stacks. setOptions(iterator); // Execute the first option firstOption.get(function); } <B> void setOptions(Iterator<IVF1<B>> options) { snapshot = cloneStack(); this.options = (Iterator) options; } // Try to backtrack one step and return a new stack // Returns null if no backtracking possible public selfType backtrack() ctex { // no more options? done if (options == null || !options.hasNext()) null; // get snapshot and option to execute selfType nextStack = snapshot; var option = options.next(); // If there are more options in the list, make another clone // of the snapshot bool moreOptions = options.hasNext(); if (moreOptions) { nextStack = new selfType; nextStack.stack = shallowCloneElements(snapshot.stack); nextStack.snapshot = snapshot; nextStack.options = options; } nextStack.push(new ExecuteOption(option)); ret nextStack; } public A nextResult() { stepAll(this); return (A) latestResult; } // calculate next result and print stack at every step public A nextResultWithPrintStruct(long maxSteps) { stepMaxWithPrintIndentedStruct(this, maxSteps); return (A) latestResult; } srecord noeq ExecuteOption(IVF1 option) is VStack.Computable { public void step(VStack stack, O subComputationResult) { O target = stack.caller(); stack.return(); option.get(target); } } sclass NoOptionsException extends RuntimeException {} }
download show line numbers debug dex old transpilations
Travelled to 2 computer(s): mowyntqkapby, mqqgnosmbjvj
No comments. add comment
Snippet ID: | #1035419 |
Snippet name: | PStack [dev.] |
Eternal ID of this version: | #1035419/9 |
Text MD5: | 6bd4416468f08de80d3b6e53c9ff62c4 |
Author: | stefan |
Category: | javax |
Type: | JavaX fragment (include) |
Public (visible to everyone): | Yes |
Archived (hidden from active list): | No |
Created/modified: | 2022-05-08 16:03:26 |
Source code size: | 3793 bytes / 117 lines |
Pitched / IR pitched: | No / No |
Views / Downloads: | 120 / 183 |
Version history: | 8 change(s) |
Referenced in: | [show references] |