Add globals on A-stack

1 files changed, 25 insertions, 11 deletions

diff --git a/examples/fastfib.sil b/examples/fastfib.sil
index 0c28ccd..a4e3a9a 100644
--- a/examples/fastfib.sil
+++ b/examples/fastfib.sil
@@ -1,3 +1,5 @@
+[Int] fibs := [1,1];
+
 Int length([Int] xs) {
 	if (xs.nil) {
 		return 0;
@@ -14,20 +16,32 @@ Int get([Int] xs, Int i) {
 	}
 }
 
-// This is not really memoized, as this could be emulated by keeping the last
-// two entries in memory. However, real memoization would only make sense with
-// an array and sil does not have arrays (yet).
-Int fib(Int n) {
-	[Int] fibs;
-	fibs := [1,1];
-	n := n - 2;
+[Int] append([Int] xs, [Int] ys) {
+	if (xs.nil) {
+		return ys;
+	} else {
+		return xs.hd : append(xs.tl, ys);
+	}
+}
 
-	while (!(n == 0)) {
-		fibs := get(fibs,0) + get(fibs,1) : fibs;
-		n := n - 1;
+Bool gt(Int x, Int y) {
+	if (x == 0) {
+		return False;
+	} else if (y == 0) {
+		return True;
+	} else {
+		return gt(x-1, y-1);
 	}
+}
 
-	return fibs.hd;
+Int fib(Int n) {
+	if (gt(length(fibs), n - 1)) {
+		return get(fibs, n - 1);
+	} else {
+		Int fn := fib(n-1) + fib(n-2);
+		fibs := append(fibs, [fn]);
+		return fn;
+	}
 }
 
 Int main() {