krzkaczor / babel-plugin-tailcall-optimization

Tail call optimization for JavaScript!
MIT License
192 stars 9 forks source link

Discussion of adding TCO when closure is detected #21

Open dakotamurphyucf opened 5 years ago

dakotamurphyucf commented 5 years ago

When closure is detected what about pre-processing using a combination of copying params/var decelerations to a state object (when those refs are used via closure) in the function and update all refs to point to this state.

And converting all declared functions in the closure to automatically invoked curried functions that apply the state ref via closure.

I believe this would fix any issues related to function scoping rules including referencing of primitive datatypes since the automatically invoked curried functions would be applied with object refs and would keep that reference even if the parent scope re-assigned a new object ref to the state object variable

Basically a statement like this

function someMethod(min, b) {
  const val = b.find(s => s.min < min)
   ...
  return someCondition ? someMethod(val.min, someStatementOf(val)) : val.min
}

would convert to something like this

function someMethod(min, b) {
  var _b, _min
  ...
  while(true){
   // at start of each iteration assign _state to a new object with updated values
   // this allows for automatically invoked curried functions that were applied in a previous iteration to 
   // keep ref to that object while the next iteration scope can work cleanly on the new object with 
   // updated values 
   const _state = {
     min,
   }
   const  val = b.find((state => s => s.min < state['min'])(_state))
   if(someCondition){
        _min = val.min
      _b = someStatementOf(val)
      b = _b
      min = _min
      continue;
    }
    else {
      return val.min
    }
  }
}
krzkaczor commented 5 years ago

@dakotamurphyucf Seems reasonable but I would need to think more about this issue. The reason that it's not implemented is not that it's impossible but rather it's just complicated πŸ˜†

It would be great if you could find the original discussion regarding buggy TCOs in babel@5 and see what kind of issues people had there. (there's a link in readme but I think it's dead now)

dakotamurphyucf commented 5 years ago

@krzkaczor yea I have looked everywhere for it and can't seem to find it. I am going to mess around and try and implement the logic I mentioned. Unfortunately I am not that familiar with babel plugin development so I imagine what I proposed is easier said then done πŸ˜†

I imagine the issues they were having was primarily related to variable references. I know safari figured out a way to implement TCO to spec so it definitely must be doable. I would love to be a part of solving this, this plug-in is great! Such a time-saver in place of having to deconstruct functions for production code lol

dakotamurphyucf commented 5 years ago

@krzkaczor I think I found relevant threads. https://github.com/babel/babel/issues/256. Looks like a lot of the issues stem from debugging concerns related to stack trace. Also it seems they are waiting on this proposal https://github.com/tc39/proposal-ptc-syntax.

krzkaczor commented 5 years ago

@dakotamurphyucf oh wow, ptc syntax is really interesting πŸ‘

I would be really great if you could implement your idea as discussed. I would just prefer if it would be OPT-IN (as option in config or something?), since not breaking existing code is an absolute priority. If it works well for some time we can make it default :)

dakotamurphyucf commented 5 years ago

@krzkaczor yea I agree with it being OPT-IN. I'll start working on it and create a pull-request.

xtuc commented 5 years ago

Good idea! I'm not a TCO expert btw.

What prevents you from doing:

-   const  val = b.find((state => s => s.min < state['min'])(_state))
+   const  val = b.find(s => s.min < _state["min"])

We should be able to detect a closure in a closure and throw, I guess shadowing and scoping will become complicated. Just to avoid breaking the state for outer functions.

I know safari figured out a way to implement TCO to spec so it definitely must be doable

I wouldn't rely on this assumption. The heursistic is quite complex and they spent a lots of hours in it.

dakotamurphyucf commented 5 years ago

@xtuc yea I completely overlooked that _state was being declared in the while loop and so you are right the automatically invoked curried function is not needed

I know safari figured out a way to implement TCO to spec so it definitely must be doable

Thinking more about it, I agree it is probably not a safe assumption.

We should be able to detect a closure in a closure and throw, I guess shadowing and scoping will become complicated. Just to avoid breaking the state for outer functions.

Could you elaborate a little more? Sorry if I am completely missing something I am pretty new to this subject πŸ˜†

I should have a pull-request ready by the end of the week to with a P.O.C.

xtuc commented 5 years ago

We should be able to detect a closure in a closure and throw, I guess shadowing and scoping will become complicated. Just to avoid breaking the state for outer functions.

I was wondering about:

function someMethod(min, b) {
  function a() {
   var min;
   min = 5;
   function b() {
      var min;
      min = 9;
   }

  // maybe b();
 }

   a();
   ///...
  return someCondition ? someMethod(val.min, someStatementOf(val)) : val.min
}

The two min declarations should end up overwritting themself in the state.