Created
September 17, 2017 08:56
-
-
Save phlopsi/b8359f1a679975c58c6dab264e1cdfbe 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<Type>) { | |
| variable Type result = current.result; | |
| while (exists element = stack.pop()) { | |
| value [operand, operator] = element; | |
| switch (operand) | |
| case (is ComplexReturn<Type>) { | |
| result = operator(result, operand.result); | |
| } | |
| case (is ComplexCall<Type>) { | |
| stack.push([ComplexReturn(result), operator]); | |
| previous = operand; | |
| skip = true; | |
| break; | |
| } | |
| } | |
| if (skip) { | |
| skip = false; | |
| continue; | |
| } | |
| return result; | |
| } | |
| case (is ComplexCall<Type>) { | |
| previous = current; | |
| } | |
| } | |
| } | |
| } |
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