-
-
Save arseniiv/286e859efd37eca1e055225b64ef49b7 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import ceylon.collection { | |
| ArrayList, | |
| Stack | |
| } | |
| shared abstract class ComplexTrampoline<Type>() | |
| of ComplexReturn<Type> | ComplexCall<Type> { | |
| shared formal Type result; | |
| } | |
| shared class ComplexReturn<Type>(shared actual Type result) | |
| extends ComplexTrampoline<Type>() { | |
| } | |
| shared class ComplexCall<Type>(ComplexTrampoline<Type>(Stack<[ComplexTrampoline<Type>, Type(Type, Type)]>) bounce) | |
| extends ComplexTrampoline<Type>() { | |
| shared actual Type result { | |
| variable ComplexCall<Type> previous = this; | |
| value stack = ArrayList<[ComplexTrampoline<Type>, Type(Type, Type)]>(); | |
| variable Boolean skip = false; | |
| while (true) { | |
| value current = previous.bounce(stack); | |
| switch (current) | |
| case (is ComplexReturn<out Anything>) { | |
| variable Type result = current.result; | |
| while (exists element = stack.pop()) { | |
| value [operand, operator] = element; | |
| switch (operand) | |
| case (is ComplexReturn<out Anything>) { | |
| result = operator(result, operand.result); | |
| } | |
| case (is ComplexCall<out Anything>) { | |
| stack.push([ComplexReturn(result), operator]); | |
| previous = operand of ComplexCall<Type>; | |
| skip = true; | |
| break; | |
| } | |
| } | |
| if (skip) { | |
| skip = false; | |
| continue; | |
| } | |
| return result; | |
| } | |
| case (is ComplexCall<out Anything>) { | |
| previous = current of ComplexCall<Type>; | |
| } | |
| } | |
| } | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Whole fibonacci(Whole n) { | |
| value wholePlus = callableFactory.fromContainedCallable(Whole.plus); | |
| ComplexTrampoline<Whole> fibonacciHelper(Whole n) { | |
| if (n == zero || n == one) { | |
| return ComplexReturn(n); | |
| } else { | |
| return ComplexCall<Whole>((Stack<[ComplexTrampoline<Whole>, Whole(Whole, Whole)]> stack) { | |
| stack.push([fibonacciHelper(n - two), wholePlus]); | |
| return fibonacciHelper(n - one); | |
| }); | |
| } | |
| } | |
| return fibonacciHelper(n).result; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment