Tail call optimization

[nicowilliams]

TCO is important. It would allow some iterations that can be expressed via recursion to be used that way without exhausting the stack (which is dynamically allocated, but still, without wasting memory).

The optimization looks simple to do, in execute.c, in the handling of CALL_JQ. If

• the called function has no arguments, and
• the next instruction is a RET

then instead of pushing a new frame just:

• save the current frame's retaddr and retdata
• pop the current frame
• push a new frame
• set the new frame's retaddr and retdata to be the same as the old one's

It looks like this ought to work. However, the closure passed to frame_push() makes this tricky. The following patch provides TCO (passes all tests, and demonstrably applies TCO to a tail-recursive test case), but only for self-recursion, not co-recursion:

diff --git a/execute.c b/execute.c
index 6e0ddc1..241b5da 100644
--- a/execute.c
+++ b/execute.c
@@ -654,10 +654,21 @@ jv jq_next(jq_state *jq) {
     case CALL_JQ: {
       jv input = stack_pop(jq);
       uint16_t nclosures = *pc++;
-      uint16_t* retaddr = pc + 2 + nclosures*2;
-      struct frame* new_frame = frame_push(jq, make_closure(jq, pc),
-                                           pc + 2, nclosures);
-      new_frame->retdata = jq->stk_top;
+      uint16_t* retaddr;
+      struct frame* new_frame;
+      struct closure cl = make_closure(jq, pc);
+      if (nclosures == 0 && *(pc + 2) == RET && frame_current(jq)->bc == cl.bc) {
+        // TCO
+        retaddr = frame_current(jq)->retaddr;
+        stack_ptr retdata = frame_current(jq)->retdata;
+        frame_pop(jq);
+        new_frame = frame_push(jq, cl, pc + 2, 0);
+        new_frame->retdata = retdata;
+      } else {
+        retaddr = pc + 2 + nclosures*2;
+        new_frame = frame_push(jq, cl, pc + 2, nclosures);
+        new_frame->retdata = jq->stk_top;
+      }
       new_frame->retaddr = retaddr;
       pc = new_frame->bc->code;
       stack_push(jq, input);