Old and Unused Transpiler Techniques

Here we document techniques tried but ultimately replaced.

Failed proper tail calls implementations

Failed attempt 1: Wishful thinking

Assume that a function enableProperTailCalls exists. There is a working prototype here.

Then, all functions that students have declared,

function sumTo(n, sum) {
  return n === 0 ? sum : sumTo(n - 1, sum + n);
}

const factorial = (n, total) => {
  return n === 0 ? total : factorial(n - 1, n * total);
}

const squared = map(list(1, 2, 3), x => x * x);

will be transpiled into

const sumTo = enableProperTailCalls((n, sum) => {
  return n === 0 ? sum : sumTo(n - 1, sum + n);
});

const factorial = enableProperTailCalls((n, total) => {
  return n === 0 ? total : factorial(n - 1, n * total);
});

const squared = map(list(1, 2, 3), enableProperTailCalls(x => x * x));

How enableProperTailCalls works

const enableProperTailCalls2 = (() => {
  const tailValue = Symbol("value to return to check if call is in tail position");
  return fn => {
    let isFunctionBeingEvaluated = false;
    let returnValue = undefined;
    const argumentsStack = [];
    let originalArguments = undefined;
    const reset = () => {
      isFunctionBeingEvaluated = false;
      originalArguments = undefined;
      isPossbilyFunctionWithTailCalls = true;
    };
    return function (...args) {
      if (!isPossbilyFunctionWithTailCalls) {
        return fn.apply(this, args);
      }
      argumentsStack.push(args);
      if (!isFunctionBeingEvaluated) {
        isFunctionBeingEvaluated = true;
        originalArguments = args;
        while (argumentsStack.length > 0) {
          let hasError = false;
          try {
            returnValue = fn.apply(this, argumentsStack.shift());
          } catch (e) {
            hasError = true;
          }
          const isTailCall = returnValue === tailValue;
          const hasRemainingArguments = argumentsStack.length > 0;
          if (hasError || (!isTailCall && hasRemainingArguments)) {
            isPossbilyFunctionWithTailCalls = false;
            returnValue = fn.apply(this, originalArguments);
            reset();
            return returnValue;
          }
        }
        reset();
        return returnValue;
      }
      return tailValue;
    };
  };
})();

It takes in a function, and returns a dummy function that when first called, starts a while loop. All subsequent calls do not start a while loop and instead pushes its processed values onto an argument stack, much like how tail calls are supposed to work. This works fine for most functions that involve iterative processes. It detects tail calls by having the function return a specific value, so if a function call is indeed in a tail position it would definitely return that specific value. Otherwise, we say that that function cannot be tail call optimised and rerun the original function without modifications.

But.

Major problem 1

It doesn't differentiate between a "new" call to the same function and a "recursive" call. Take

function f(x, y, z) {
  if (x <= 0) {
    return y;
  } else {
    return f(x-1, y+ /* the coming f should start another "first" f call*/ f(0, z, 0), z);
  }
}
f(5000, 5000, 2); // "first" f call

Once the while loop is entered, it can't differentiate between the above two calls and don't both start their own while loop to evaluate the function, when they should.

Major problem 2

Variables don't work.

let sum = 0;
function f() {
  sum += 1;
}
f();
sum;

we try to see if f can be tail call optimised.
sum gets incremented.
f cannot be tail call optimised.
f is rerun since the tail call optimisation failed.
sum gets incrememented again.

...

Aftermath

In retrospect this was a horrible idea, and now it looks so painfully obvious this wouldn't work. I leaned towards it because it seemed so simple and dreamy. Ah well.

Failed attempt 2: Trampolines are fun only if everyone jumps

We use a trampoline. All return statements are transformed into objects (so they do not perform recursive calls that can blow the stack).

function factorial (n, acc) { //simple factorial
  if (n <= 1) {
    return acc;
  } else {
    return factorial(n - 1, acc * n);
  }
}

becomes

function factorial (n, acc) { //simple factorial
  if (n <= 1) {
    return { value: acc, isTail: false};
  } else {
    return { f:factorial, args: [n - 1, acc * n], isTail: true };
  }
}

Special checks are done to make sure conditional and logical expressions can behave too:

const toZero = n => {
  return n === 0 ? 0 : toZero(n - 1);
}

becomes

const toZero = n => {
  return n === 0 ? {isTail: false, value: 0} : {isTail:true, f:toZero, args:[n - 1]};
};

And then we transform all function calls from f(arg1, arg2, ...) into call(f, [arg1, arg2, ...]).

Where call is

function call(f, args) {
  let result;
  while (true) {
    result = f(...args);
    if (result.isTail) {
      f = result.f;
      args = result.args;
    } else {
      return result.value;
    }
  }
}

Problem

Builtins exist. Predefined functions. They do not and cannot play nice and follow this way of returning their results. They also have no idea on how to call these functions, should these transformed functions be passed to them. While a possible soution would be to rewrite all these builtins to use the same object-returing style, it would become unfeasible should external libraries be needed.

Variable storage (deprecated)

One major problem of using eval is that eval('const a = 1;'); does not let us access the variable a again as it is not declared in the same scope. This would not allow the REPL to work, so there needs to be another way. The first idea that came to mind worked out well for the most part.

Store declared global variables in a global constant named STUDENT_GLOBALS.

Code will be appended to the end of the student's code to store the currently declared global variables into STUDENT_GLOBALS.

e.g.

//Student's main code
const PI = 3;
let sum = 0;
sum = sum + 1;

//Transpiled code
//reset STUDENT_GLOBALS
// student's main code
const PI = 3;
let sum = 0;
sum = sum + 1;
//end of student's main code
//save declared studentglobals
STUDENT_GLOBALS["PI"] = {kind: "const", value: PI};
STUDENT_GLOBALS["sum"] = {kind: "let", value: sum};

Before exectution of REPL code in the same context (so previously declared global variables have to be accessible), all keys of STUDENT_GLOBALS will be looped through and <kind> <key> = STUDENT_GLOBALS["<key>"]; will be prepended. For all variables (those declared with let), STUDENT_GLOBALS["<key>"] = <key>; will be appended to student's code to update the variable's value at the end of the code's execution.

Assuming the previous "main" code has been executed already, PI and sum will have already been saved.

So for the following code in the REPL:

// student's repl code
sum = sum + PI;

// transpiled code
const PI = STUDENT_GLOBALS["PI"].value; // we need to put back these variables 
let sum = STUDENT_GLOBALS["sum"].value; // this too
// student's repl code
sum = sum + PI;
// end of student's code
STUDENT_GLOBALS["sum"] = {kind: 'let', value: sum}; // store back variable sum
// PI does not need to be copied back since it's constant.

Minor Problem

const one = 1;
if (true) {
  1;
} else {
  one;
}

should result in 1 being returned as it's the value of the last statement evaluated. However, because of the the statements to store back the variables,

const one = 1;
if (true) {
  1;
} else {
  one;
}
STUDENT_GLOBALS['one'] = {kind: 'const', value: one};

the last line value is now incorrect. Luckily eval is here yet again. All that needs to be done is to save the value of the last statement and then return it at the end, so we do that by transforming the last statement into a string and then evaling it:

const one = 1;
const lastLineResult = eval(`if (true) {
  1;
} else {
  one;
}
`);
STUDENT_GLOBALS['one'] = {kind: 'const', value: one};
lastLineResult;

and boom, problem solved...

not.

Minorer problem

If the last line is a variable declaration statement, it would get transformed into:

const lastLineResult = eval('const two = 2;'); // last line transformed into eval
STUDENT_GLOBALS['two'] = {kind: 'const', value: two};
lastLineResult;

But then two is not defined in the outer scope, it's defined only within the eval scope, so its value wouldn't get saved. Luckily again, the return value of a declaration is undefined, so if the last line of code is a declaration statement it does not get changed into eval, and we append undefined; at the end of the code:

const two = 2; // last line not transformed into eval
STUDENT_GLOBALS['two'] = {kind: 'const', value: two};
undefined;

Phew.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly