Compiling Set Comprehensions to Bytecode: an exercise in managing abstractions

mgcadmin 07-23-2026

When I transitioned owlscript from being a tree walking interpreter to compiling to bytecode, one of the features that took much longer than others was the re-implementation of set/list comprehensions. Some of the challenges posed by their implementation were partially adressed during the introduction of for-each loops - managing iterators, efficiently generating lists, etc. Other issues, like managing the actual function application took a bit more thought. I've finally managed to get both the syntax and implementation to a place i like, and so in todays post I'm going to cover the many moving parts required to compile list comprehensions to bytecode for the glaux VM.

List Comprehension Syntax in Owlscript 

Owlscript actually has two flavors of list comprehension: plain, and filtered. Plain list comprehensions accept a single lambda function as an argument, using the keyword 'as', like so:

Owlscript(0)> println [ 1 .. 10 as &(let i) -> 2*i+1 ];
[3 5 7 9 11 13 15 17 19 21 ]

Filtered list comprehensions have the same syntax, but are further augmented with a second lambda function following the keyword 'if', like this:

Owlscript(1)> println [ 1 .. 10 as &(let i) -> 2*i+1 if &(let j) -> j % 2 != 0 ];
[3 7 11 15 19 ]

Additionally, as all functions are first class functions (def is just syntactic sugaring around a lambda expression), any function - named or lambda can be used:

Owlscript(0)> def fact(let k) { if (k < 2) { return 1; } return fact(k-1)*k; }
Owlscript(1)> let even := &(let i) -> i % 2 == 0;
Owlscript(2)> println [ 1 .. 10 as fact if even ];
[2 24 720 40320 3628800 ]
Owlscript(3)> def fib(let q) { if (q < 2) { return 1; } return fib(q-1)+fib(q-2); }
Owlscript(4)> def odd(let q) { return q % 2 != 0; }
Owlscript(5)> println [ 5 .. 20 as fib if odd ] 
[8 21 55 144 377 987 2584 6765 ]

I've been using the ranged list generator expressions for examples, but any list can be used as the input list for a comprehension:

Owlscript(6)> let xs := [ 13, 42, 86, 11, 24, 9];
Owlscript(7)> println [ xs as &(let i) -> i+i ];
[26 84 172 22 48 18 ]
Owlscript(8)> println [ xs as &(let i) -> i+i if odd ];
[26 22 18 ]

 Now that we've seen what they are and have a test of how they're used, lets talk about how they work.

Peeking Under the Hood

At their heart, unfiltered 'as' comprehensions are very similar to the higher order function 'map' familiar to lisp hackers and present in many modern impreative languages like Javascript. It takes an input list and a lamnda reference and returns a new list consisting of the result of applying the provided lambda to each member of the input list.

Following this same analgoy, List comprehensions using the 'if' keyword are akin to lisps' 'filter' where values are only appended to the result list if the input value passes the supplied predicate test.

    bool is_filtered = n->right && n->right->next;
    int IDX = symTable.lookup("scitr").addr; //Index into list    
    int SEQ = symTable.lookup("scclti").addr; // list to iterate over
    int RET = symTable.lookup("sctrl").addr; //result list

Lets take a moment to take stock of the various moving parts involved. We have an input list, a result list, an output lambda, and an optional predicate lambda. 

    //Create & store result list
    emit(Instruction(mklist));
    emit(Instruction(ldaddr, RET));
    emit(Instruction(stlocal));
    //generate code for the input list expression
    genExpression(n->left, false);

We will also need to maintain an iterator into the input list to obtain its elements as input to the lambdas. We store the list to iterate in the address at SEQ. Next, we assign 0 to IDX - the first position in the list.

    emit(Instruction(ldaddr, SEQ));
    emit(Instruction(stlocal));
    emit(Instruction(ldconst, StackItem(0.0)));
    emit(Instruction(ldaddr, IDX));
    emit(Instruction(stlocal));

Because we want to iterate over the entire list, we compare the value of IDX to the length of the list at SEQ, if its less, we fall through to process the element at that index. If it is greater than or equal to the length of the list, then were done processing the list and can bail out.

    // loop test expr: index < list.length (IDX < length(SEQ))
    int P1 = skipEmit(0); //jump target
    emit(Instruction(ldlocal, IDX)); //current index into list
    emit(Instruction(ldlocal, SEQ)); //current list to iterate
    emit(Instruction(list_len));      // obtain its length
    emit(Instruction(binop, VM_LT));  //more to go?
    //Because we dont yet know the address for the fail branch, 
    //we reserve a space to back patch it into (L1)
    int L1 = skipEmit(0); 
    skipEmit(1);

At the start of loop body, to begin each iteratiom we set up the stack by first pushing the result list onto the stack. Next, push the value at the current index of the list being iterated on to the stack to be used as input to the lambda to be called, 

    emit(Instruction(ldlocal, RET)); //result list
    emit(Instruction(ldlocal, SEQ)); //current list were iterating
    emit(Instruction(ldlocal, IDX));  // index of current position
    emit(Instruction(ldidx));         // get data at that index

What happens next depends on whether it is a filtered comprehension or plain comprehension.

Diverging Paths

We'll start with unfiltered comprehensions first, since they're quite a bit simpler. At the current point of execution, our stack looks like this:

------------------------------     <- top of stack
argument to lambda expr. 
------------------------------
Result List
------------------------------
 .... etc ....

The lambda expression is fetched and pushed onto the stack and immediately called, taking the value on the stack as its argument and replacing it with the return value of applying the lambda to the argument. The value is then appeneded to the result list before preparing for the next iteration.

if (!is_filtered) {
        genExpression(n->right, false);
        emit(Instruction(call, -1, 1));
        emit(Instruction(list_append)); //result list
        emit(Instruction(popstack));
} else {

For filtered comprehensions, the predicate lambda is called first, and the value on the top of the stack is popped off and used as it's argument, The result of the predicate expression is then pushed onto the stack in its place. Depending on the return value we either fall through to apply the second lambda, or jump to a point to set up for the next iteration without appending the result, having filtered out that result. If the value passes the predicate and is not filtered out, we must first re-load the input argument from the input list, since that value was consumed by the predicate.

} else {
        genCode(n->right->next, false); //get predicate expression
        emit(Instruction(call, -1, 1)); //execute it
        int IL1 = skipEmit(0); //will backpatch branch on false once we know jump point.
        skipEmit(1);
        emit(Instruction(ldlocal, SEQ)); //current list were iterating
        emit(Instruction(ldlocal, IDX));  // index of current position
        emit(Instruction(ldidx));         // get data at that index
        genExpression(n->right, false);  //get 'as' lambda
        emit(Instruction(call, -1, 1)); // execute it
        emit(Instruction(list_append)); // save result
        int L2 = skipEmit(0);//jump to here if result of predicate is false.
        emit(Instruction(popstack));
        skipTo(IL1);
        emit(Instruction(brf, L2)); //backpatch branch on false to L2 to the space reserved at L1.
        restore();
}

Regardless of the type of comprehension, once a list item has been processed and the result dealt with, our job turns to updating the iterartor value and preparing the environment for the next pass. 

    emit(Instruction(ldlocal, IDX)); //get value of current index
    emit(Instruction(incr));        //increment it by 1
    emit(Instruction(ldaddr, IDX));  //save new index value
    emit(Instruction(stlocal));
    emit(Instruction(jump, P1));  //jump back up to test expression

All thats left to do now is backpatch the address of the jump target for the test expressions' failure branch (remember that?).

    int L2 = skipEmit(0);
    skipTo(L1);               
    emit(Instruction(brf, L2)); 
   restore();
    emit(Instruction(ldlocal, RET));
}

---