bytecode compilation of map()

4 files changed, 101 insertions, 5 deletions

diff --git a/chunk.d b/chunk.d
index 63d5bae..18bf12d 100644
--- a/chunk.d
+++ b/chunk.d
@@ -126,6 +126,9 @@ class List : Seq {
     }
 
     override Seq rest() {
+        if (this.inner.length == 0) {
+            return new List(0);
+        }
         List ret = new List(to!int(this.inner.length) - 1);
         for (int i = 1; i < this.inner.length; i++) {
             ret.addItemAtIndex(this.inner[i], i - 1);
@@ -157,7 +160,11 @@ class List : Seq {
     }
 
     override string toString() {
-        return format("list ('%s' + %d)", printableValue(this.inner[0]), this.inner.length - 1);
+        if (this.inner.length == 0) {
+            return "nil";
+        } else {
+            return format("list ('%s' + %d)", printableValue(this.inner[0]), this.inner.length - 1);
+        }
     }
 }
 
@@ -185,6 +192,7 @@ enum OpCode {
     OP_JUMP,
     OP_JUMP_IF_FALSE,
     OP_JUMP_IF_TRUE,
+    OP_JUMP_TO,
 
     OP_IS_NIL,
     OP_DUPLICATE,
diff --git a/compiler.d b/compiler.d
index 4a3df27..d55b7f5 100644
--- a/compiler.d
+++ b/compiler.d
@@ -437,6 +437,16 @@ class Compiler {
         this.func.chunk.code[offset + 1] = jmp & 0xff;
     }
 
+    void jumpBackTo(OpCode type, int dest) {
+
+        this.func.chunk.writeOp(to!ubyte(type), this.current.line);
+
+        int lower = (dest >> 8) & 0xff;
+        int higher = dest & 0xff;
+        this.func.chunk.writeOp(to!ubyte(lower), this.current.line);
+        this.func.chunk.writeOp(to!ubyte(higher), this.current.line);
+    }
+
     void compileIf(Form form) {
         If if_ = cast(If)form;
 
@@ -611,6 +621,74 @@ class Compiler {
         this.func.chunk.writeOp(OpCode.OP_MEMBER, args[0].line);
     }
 
+    void compileMap(Form[] args) {
+        // TODO how do we identify/propagate errors?
+        if (args.length != 2) {
+            this.error(format("'map': expected [2] arguments, received %d", args.length), -1);
+            this.advance();
+            return;
+        }
+        ValueType vt = this.resolve(args[0], ValueType.ANY);  // resolves the function
+        vt = this.resolve(args[1], ValueType.ANY);            // resolves the list
+
+        // we want to keep track of the length of the generated list (starts at zero)
+        // TODO this could probably be cleaner, as we should know the length of the resulting list already
+        this.func.chunk.writeOp(OpCode.OP_ZERO, args[0].line);     // | [ fn ] [ list ] [ 0 ]
+        this.func.chunk.writeOp(OpCode.OP_ROTATE_N, args[0].line);
+        this.func.chunk.writeOp(to!ubyte(3), args[0].line);     // | [ 0 ] [ fn ] [ list ]
+
+        // we're going to jump back to this point, so let's keep track of our location
+        int jumpBack = to!int(this.func.chunk.code.length);
+
+        // with our list on top of the stack, let's check for nil to see if we're done
+        this.func.chunk.writeOp(OpCode.OP_DUPLICATE, args[0].line);  // | [ 0 ] [ fn ] [ list ] [ list ]
+        this.func.chunk.writeOp(OpCode.OP_IS_NIL, args[0].line);     // | [ 0 ] [ fn ] [ list ] [ bool ]
+
+        // we'll jump from here to the end if we have nil
+        int nilJump = this.jump(OpCode.OP_JUMP_IF_TRUE);  // TODO if we're using "falsey", we could cut an instruction here
+
+        // get rid of the boolean on top
+        this.func.chunk.writeOp(OpCode.OP_POP, args[0].line);     // | [ 0 ] [ fn ] [ list ]
+
+        // duplicate the function and list, and rotate it below the length (we'll need it later)
+        this.func.chunk.writeOp(OpCode.OP_DUPLICATE_2, args[0].line);    // | [ 0 ] [ fn ] [ list ] [ fn ] [ list ]
+        this.func.chunk.writeOp(OpCode.OP_ROTATE_N, args[0].line);
+        this.func.chunk.writeOp(to!ubyte(5), args[0].line);           // | [ list ] [ 0 ] [ fn ] [ list ] [ fn ]
+        this.func.chunk.writeOp(OpCode.OP_ROTATE_N, args[0].line);
+        this.func.chunk.writeOp(to!ubyte(5), args[0].line);           // | [ fn ] [ list ] [ 0 ] [ fn ] [ list ]
+
+        // get the first item from the top list, then run the function on it (we know there's always 1 argument)
+        this.func.chunk.writeOp(OpCode.OP_FIRST, args[0].line);       // | [ fn ] [ list ] [ 0 ] [ fn ] [ item ]
+        this.func.chunk.writeOp(OpCode.OP_CALL, args[0].line);
+        this.func.chunk.writeOp(to!ubyte(1), args[0].line);           // | [ fn ] [ list ] [ 0 ] [ fn(item) ]
+
+        // preserve the value we just generated
+        this.func.chunk.writeOp(OpCode.OP_ROTATE_N, args[0].line);
+        this.func.chunk.writeOp(to!ubyte(4), args[0].line);           // | [ fn(item) ] [ fn ] [ list ] [ 0 ]
+
+        // increment the counter, and save it *after* the value
+        this.func.chunk.writeOp(OpCode.OP_INCREMENT, args[0].line);   // | [ fn(item) ] [ fn ] [ list ] [ 1 ]
+        this.func.chunk.writeOp(OpCode.OP_ROTATE_N, args[0].line);
+        this.func.chunk.writeOp(to!ubyte(3), args[0].line);           // | [ fn(item) ] [ 1 ] [ fn ] [ list ]
+
+        // get the rest of the list
+        this.func.chunk.writeOp(OpCode.OP_REST, args[0].line);        // | [ fn(item) ] [ 1 ] [ fn ] [ rest(list) ]
+
+        // jump back to the top of the loop
+        this.jumpBackTo(OpCode.OP_JUMP_TO, jumpBack);
+
+        // jump here when we have a nil
+        this.patchJump(nilJump);              // | [ fn(first) ] ... [ fn(last) ] [ length ] [ fn ] [ nil ] [ true ]
+
+        // pop the unneeded state at the top
+        this.func.chunk.writeOp(OpCode.OP_POP, args[0].line);
+        this.func.chunk.writeOp(OpCode.OP_POP, args[0].line);
+        this.func.chunk.writeOp(OpCode.OP_POP, args[0].line);  // | [ fn(first) ] ... [ fn(last) ] [ length ]
+
+        // create a list from the stack, with the length as the top item
+        this.func.chunk.writeOp(OpCode.OP_LIST_N, args[0].line);
+    }
+
     void compileFirst(Form[] args) {
         // TODO how do we identify/propagate errors?
         if (args.length != 1) {
@@ -776,6 +854,11 @@ class Compiler {
             case "eq?":
                 return this.compileEq(cons.tail);
 
+            // HOF
+            case "map":
+                this.compileMap(cons.tail);
+                break;
+
             // STRINGS
             case "concat":
                 return this.compileConcat(cons.tail);
diff --git a/dbg.d b/dbg.d
index 7e92eb5..b9aad21 100644
--- a/dbg.d
+++ b/dbg.d
@@ -205,6 +205,8 @@ int disassemble(Chunk chunk, int offset) {
             return simpleInstruction("OP_NIL", offset);
         case OpCode.OP_JUMP:
             return jumpInstruction("OP_JUMP", 1, chunk, offset);
+        case OpCode.OP_JUMP_TO:
+            return jumpInstruction("OP_JUMP_TO", -1, chunk, offset);
         case OpCode.OP_JUMP_IF_FALSE:
             return jumpInstruction("OP_JUMP_IF_FALSE", 1, chunk, offset);
         case OpCode.OP_JUMP_IF_TRUE:
diff --git a/vm.d b/vm.d
index 75f6328..ba7fc50 100644
--- a/vm.d
+++ b/vm.d
@@ -311,7 +311,7 @@ class VM {
 
                     // pop the next n-1 values
                     Value[] inner;
-                    for (int i = 0; i < n - 1; i++) {
+                    for (int i = 0; i < (n - 1); i++) {
                         inner ~= this.popA();
                     }
 
@@ -319,7 +319,7 @@ class VM {
                     this.pushA(top);
 
                     // push the other values (preserve order)
-                    for (int i = n - 1; i >= 0; i--) {
+                    for (int i = (n - 2); i >= 0; i--) {
                         this.pushA(inner[i]);
                     }
                     break;
@@ -568,13 +568,16 @@ class VM {
                     this.popA();  // throw this one away
                     this.pushA(val);
                     break;
-
+                case OpCode.OP_JUMP_TO:
+                    uint addr = this.readShort();
+                    //this.current.ip -= offset;
+                    this.current.ip = to!ubyte(addr);
+                    break;
                 case OpCode.OP_JUMP:
                     uint offset = this.readShort();
                     //ip += offset;
                     this.current.ip += offset;
                     break;
-
                 case OpCode.OP_JUMP_IF_FALSE:
                     uint offset = this.readShort();
                     if (!isBoolean(this.peekA(0))) {