Transpiled version (22976L) is out of date.
1 | // Backtracking-enabled stacks (BStacks) are very useful for AI |
2 | // computation because they allow inserting a branching point anywhere |
3 | // in a computation, even deep inside nested function calls and loops. |
4 | // |
5 | // BStacks normally operate serially, always exploring the main branch first |
6 | // and then optionally backtracking afterwards. |
7 | // |
8 | // However, the only thing preventing a BStack from backtracking in |
9 | // parallel to the main computation is the use of external mutable |
10 | // objects. With sufficient cloning of these objects at a branch point |
11 | // and/or the use of immutable data structures, there is no obstacle to |
12 | // parallelizing. |
13 | // |
14 | // A further evolution of BStacks are PStacks. In PStacks, at any point |
15 | // in time, every ongoing or potential computation is listed with a |
16 | // probability value p (usually 0 < p <= 1). |
17 | // |
18 | // This "table of possible computations or continuations of computations" |
19 | // constantly sorts itself by decreasing probability, so computations |
20 | // with higher probability can be pursued first. |
21 | // |
22 | // PStack doesn't support undos because those only make sense in |
23 | // serial execution. |
24 | |
25 | sclass PStack<A> extends VStack is IPStack { |
26 | static int idCounter; |
27 | int stackID = ++idCounter; // for debugging |
28 | |
29 | // cloned version made at last branch point |
30 | selfType snapshot; |
31 | |
32 | // remaining options at last branch point |
33 | Iterator<IVF1> options; |
34 | |
35 | *() {} |
36 | *(Computable<A> computation) { push(computation); } |
37 | *(Iterable<Computable> l) { pushAll(l); } |
38 | |
39 | selfType cloneStack() { |
40 | new selfType s; |
41 | s.snapshot = snapshot; |
42 | s.options = options; |
43 | s.stack = shallowCloneElements(stack); |
44 | ret s; |
45 | } |
46 | |
47 | public <B extends VStack.Computable> void options(B function, IVF1<B>... options) { |
48 | options(function, arrayIterator(options)); |
49 | } |
50 | |
51 | public <B extends VStack.Computable> void options(B function, Iterable<IVF1<B>> options) { |
52 | Iterator<IVF1<B>> iterator = nonNullIterator(iterator(options)); |
53 | |
54 | if (!iterator.hasNext()) |
55 | throw new NoOptionsException; |
56 | |
57 | IVF1<B> firstOption = iterator.next(); |
58 | |
59 | // All options except first are stored as alternatives |
60 | // in cloned stacks. |
61 | |
62 | setOptions(iterator); |
63 | |
64 | // Execute the first option |
65 | firstOption.get(function); |
66 | } |
67 | |
68 | <B> void setOptions(Iterator<IVF1<B>> options) { |
69 | snapshot = cloneStack(); |
70 | this.options = (Iterator) options; |
71 | } |
72 | |
73 | // Try to backtrack one step and return a new stack |
74 | // Returns null if no backtracking possible |
75 | public selfType backtrack() ctex { |
76 | // no more options? done |
77 | if (options == null || !options.hasNext()) null; |
78 | |
79 | // get snapshot and option to execute |
80 | selfType nextStack = snapshot; |
81 | var option = options.next(); |
82 | |
83 | // If there are more options in the list, make another clone |
84 | // of the snapshot |
85 | bool moreOptions = options.hasNext(); |
86 | if (moreOptions) { |
87 | nextStack = new selfType; |
88 | nextStack.stack = shallowCloneElements(snapshot.stack); |
89 | nextStack.snapshot = snapshot; |
90 | nextStack.options = options; |
91 | } |
92 | |
93 | nextStack.push(new ExecuteOption(option)); |
94 | ret nextStack; |
95 | } |
96 | |
97 | public A nextResult() { |
98 | stepAll(this); |
99 | return (A) latestResult; |
100 | } |
101 | |
102 | // calculate next result and print stack at every step |
103 | public A nextResultWithPrintStruct(long maxSteps) { |
104 | stepMaxWithPrintIndentedStruct(this, maxSteps); |
105 | return (A) latestResult; |
106 | } |
107 | |
108 | srecord noeq ExecuteOption(IVF1 option) is VStack.Computable { |
109 | public void step(VStack stack, O subComputationResult) { |
110 | O target = stack.caller(); |
111 | stack.return(); |
112 | option.get(target); |
113 | } |
114 | } |
115 | |
116 | sclass NoOptionsException extends RuntimeException {} |
117 | } |
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: | 121 / 185 |
Version history: | 8 change(s) |
Referenced in: | [show references] |