module Klam::CompilationStages::ConvertSelfTailCallsToLoops

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.

Public Instance Methods

convert_self_tail_calls_to_loops(sexp) click to toggle source
# 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

Private Instance Methods

contains_self_tail_calls?(body, name) click to toggle source
# File lib/klam/compilation_stages/convert_self_tail_calls_to_loops.rb, line 55
def contains_self_tail_calls?(body, name)
  if body.instance_of?(Array)
    case body[0]
    when name
      true
    when :if
      _, _, true_expr, false_expr = body
      contains_self_tail_calls?(true_expr, name) ||
        contains_self_tail_calls?(false_expr, name)
    when :let
      contains_self_tail_calls?(body[3], name)
    when :do
      contains_self_tail_calls?(body[2], name)
    else
      false
    end
  else
    false
  end
end
fix_vars(sexp, params) click to toggle source
# File lib/klam/compilation_stages/convert_self_tail_calls_to_loops.rb, line 118
def fix_vars(sexp, params)
  if sexp.kind_of?(Array)
    if sexp[0] == :lambda
      referenced_vars = vars_referenced_in(sexp, params)
      if referenced_vars.empty?
        sexp
      else
        [:"[FIX-VARS]", referenced_vars, sexp]
      end
    else
      # Local variables must also be fixed
      if sexp[0] == :let
        params = params + [sexp[1]]
      end
      sexp.map { |x| fix_vars(x, params) }
    end
  else
    sexp
  end
end
insert_loop_and_recur_into_defun(form) click to toggle source
# File lib/klam/compilation_stages/convert_self_tail_calls_to_loops.rb, line 76
def insert_loop_and_recur_into_defun(form)
  rator, name, params, body = form
  loop_var = fresh_variable
  body_with_loop = [:"[LOOP]", loop_var,
                    insert_recur_into_expr(body, name, params,
                                           loop_var)]
  [rator, name, params, body_with_loop]
end
insert_recur_into_expr(sexp, name, params, loop_var) click to toggle source
# File lib/klam/compilation_stages/convert_self_tail_calls_to_loops.rb, line 85
def insert_recur_into_expr(sexp, name, params, loop_var)
  if sexp.instance_of?(Array)
    case sexp[0]
    when name
      if sexp.length - 1 == params.length
        [:"[RECUR]", params, sexp[1..-1], loop_var]
      else
        sexp
      end
    when :if
      rator, test_expr, true_expr, false_expr = sexp
      [rator,
       test_expr,
       insert_recur_into_expr(true_expr, name, params, loop_var),
       insert_recur_into_expr(false_expr, name, params, loop_var)]
    when :let
      rator, var, val_expr, body_expr = sexp
      [rator,
       var,
       val_expr,
       insert_recur_into_expr(body_expr, name, params, loop_var)]
    when :do
      rator, first_expr, second_expr = sexp
      [rator, first_expr, insert_recur_into_expr(second_expr, name,
                                                 params, loop_var)]
    else
      sexp
    end
  else
    sexp
  end
end
vars_referenced_in(sexp, vars) click to toggle source
# File lib/klam/compilation_stages/convert_self_tail_calls_to_loops.rb, line 139
def vars_referenced_in(sexp, vars)
  if sexp.kind_of?(Array)
    sexp.map { |x| vars_referenced_in(x, vars) }.flatten.uniq
  elsif vars.include?(sexp)
    [sexp]
  else
    []
  end
end