Module: Klam::CompilationStages::ConvertSelfTailCallsToLoops

Included in:
Klam::Compiler
Defined in:
lib/klam/compilation_stages/convert_self_tail_calls_to_loops.rb

Overview

Convert Self Tail Calls To Loops

The Shen specification requires that self tail calls be optimized. This stage transforms defuns containing self tail calls into a loop/recur form akin to Clojure’s loop/recur. The code emitter knows how to handle these synthetic special forms.

For example, this code with tail calls:

(defun fact-iter (N Accum)
  (if (= N 0)
    Accum
    (fact-iter (- N 1) (* N Accum))))

is converted to:

(defun fact-iter (N Accum)
  ([LOOP]
    (if (= N 0)
      Accum
      ([RECUR] (N Accum) ((- N 1) (* N Accum))))))

The variable names are carried along with their new binding expressions in the [RECUR] form so that they can be rebound before looping.

Note that this rebinding of variables causes a wrinkle with respect to closures created in the body. Those closures should close over the value at the point of closing rather than the ultimate values after rebinding. To solve this, another sythetic primitive, [FIX-VARS], is used to wrap these cases and the emitted Ruby code samples those variables.

This compilation stage must come after SimplifyBooleanOperations and ConvertFreezesToLambdas.

Instance Method Summary collapse

Instance Method Details

#convert_self_tail_calls_to_loops(sexp) ⇒ Object 



37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
# File 'lib/klam/compilation_stages/convert_self_tail_calls_to_loops.rb', line 37

def convert_self_tail_calls_to_loops(sexp)
  # Self tail calls can only be found in functions defined by defun.
  # defun is only allowed at the top level, so there's no need to
  # walk the tree if this form is not a defun.
  if sexp.kind_of?(Array) && sexp[0] == :defun
    _, name, params, body = sexp
    if contains_self_tail_calls?(body, name)
      insert_loop_and_recur_into_defun(fix_vars(sexp, params))
    else
      sexp
    end
  else
    sexp
  end
end