add filter

1 files changed, 91 insertions, 0 deletions

diff --git a/compiler.d b/compiler.d
index bbe7550..f721e86 100644
--- a/compiler.d
+++ b/compiler.d
@@ -358,6 +358,93 @@ class Compiler {
     }
 
     // HOF
+    void compileFilter(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);
+            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)
+        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, duplicate it,
+        // then rotate it back to keep it
+        this.func.chunk.writeOp(OpCode.OP_FIRST, args[0].line);       // | [ fn ] [ list ] [ 0 ] [ fn ] [ item ]
+        this.func.chunk.writeOp(OpCode.OP_DUPLICATE, args[0].line);       // | [ fn ] [ list ] [ 0 ] [ fn ] [ item ] [ item ]
+        this.func.chunk.writeOp(OpCode.OP_ROTATE_N, args[0].line);
+        this.func.chunk.writeOp(to!ubyte(3), args[0].line);           // | [ fn ] [ list ] [ 0 ] [ item ] [ fn ] [ list ]
+
+        // call the function
+        this.func.chunk.writeOp(OpCode.OP_CALL, args[0].line);
+        this.func.chunk.writeOp(to!ubyte(1), args[0].line);           // | [ fn ] [ list ] [ 0 ] [ item ] [ fn(item) ]
+
+        // jump if false (but where?)
+        int filterSkip = this.jump(OpCode.OP_JUMP_IF_FALSE);
+
+        // save the value and increment
+        this.func.chunk.writeOp(OpCode.OP_POP, args[0].line);         // | [ fn ] [ list ] [ 0 ] [ item ]
+        this.func.chunk.writeOp(OpCode.OP_ROTATE_N, args[0].line);
+        this.func.chunk.writeOp(to!ubyte(4), args[0].line);           // | [ item ] [ fn ] [ list ] [ 0 ]
+        this.func.chunk.writeOp(OpCode.OP_INCREMENT, args[0].line);   // | [ item ] [ fn ] [ list ] [ 1 ]
+
+        int hopOver = this.jump(OpCode.OP_JUMP);
+
+        // bad filters end up here
+        this.patchJump(filterSkip);
+
+        this.func.chunk.writeOp(OpCode.OP_POP, args[0].line);         // | [ fn ] [ list ] [ 0 ] [ item ]
+        this.func.chunk.writeOp(OpCode.OP_POP, args[0].line);         // | [ fn ] [ list ] [ 0 ]
+
+        this.patchJump(hopOver);
+
+        // keep the incremented list
+        this.func.chunk.writeOp(OpCode.OP_ROTATE_N, args[0].line);
+        this.func.chunk.writeOp(to!ubyte(3), args[0].line);           // | [ item ] [ 1 ] [ fn ] [ list ]
+
+        // get the rest of the list
+        this.func.chunk.writeOp(OpCode.OP_REST, args[0].line);        // | [ 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 compileMap(Form[] args) {
         // TODO how do we identify/propagate errors?
         if (args.length != 2) {
@@ -944,6 +1031,9 @@ class Compiler {
                 return this.compileEq(cons.tail);
 
             // HOF
+            case "filter":
+                this.compileFilter(cons.tail);
+                break;
             case "map":
                 this.compileMap(cons.tail);
                 break;
@@ -1109,6 +1199,7 @@ class Compiler {
         this.globals["eq?"] = 2;
 
         // HOF
+        this.globals["filter"] = 2;
         this.globals["map"] = 2;
         this.globals["reduce"] = 3;