Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.javascript > #35252 > unrolled thread

Fast Explicit Tail Calls using today's JavaScript

Back to article view | Back to comp.lang.javascript

Contents

  Fast Explicit Tail Calls using today's JavaScript glathoud <glathoud@yahoo.fr> - 2018-06-20 11:11 -0700
    Re: Fast Explicit Tail Calls using today's JavaScript "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2018-06-22 13:49 -0700
      Re: Fast Explicit Tail Calls using today's JavaScript glathoud <glathoud@yahoo.fr> - 2018-07-06 05:26 -0700
    Re: Fast Explicit Tail Calls using today's JavaScript Julio Di Egidio <julio@diegidio.name> - 2018-07-06 09:37 -0700
      Re: Fast Explicit Tail Calls using today's JavaScript glathoud <glathoud@yahoo.fr> - 2018-07-06 22:14 -0700
        Re: Fast Explicit Tail Calls using today's JavaScript Julio Di Egidio <julio@diegidio.name> - 2018-07-07 07:08 -0700
          Re: Fast Explicit Tail Calls using today's JavaScript Julio Di Egidio <julio@diegidio.name> - 2018-07-07 08:16 -0700
            Re: Fast Explicit Tail Calls using today's JavaScript glathoud <glathoud@yahoo.fr> - 2018-07-07 12:14 -0700
              Re: Fast Explicit Tail Calls using today's JavaScript Julio Di Egidio <julio@diegidio.name> - 2018-07-08 05:00 -0700
              Re: Fast Explicit Tail Calls using today's JavaScript Julio Di Egidio <julio@diegidio.name> - 2018-07-08 06:05 -0700
                Re: Fast Explicit Tail Calls using today's JavaScript glathoud <glathoud@yahoo.fr> - 2018-07-12 01:53 -0700
          Re: Fast Explicit Tail Calls using today's JavaScript Julio Di Egidio <julio@diegidio.name> - 2018-07-08 05:46 -0700

#35252 — Fast Explicit Tail Calls using today's JavaScript

Hello,

Following the idea of explicitly marking the tail calls that have to be optimized, JavaScript extensions were proposed that add new keywords to the language [2013][2016].

It turns out that we can do this explicit approach using today's JavaScript, without extending the language. [fext.js] demonstrates this.


Self-recursion example:

var gcd = mfun(
       (a, b) => a > b  ?  mret( self, a-b, b )
           :     a < b  ?  mret( self, b-a, a )
           :     a
);
console.log( gcd( 2*3*5*17, 3*5*19 ) );  // 15 (3*5)


Mutual recursion example:

var isOdd = mfun( function isOdd( n ) {
    return n > 0  ?  mret( isEven, n-1 )
        :  n < 0  ?  mret( self, -n )
        :  false
    ;
})
,  isEven = mfun( isOdd, function isEven( n ) {
    return n > 0  ?  mret( isOdd, n-1 )
        :  n < 0  ?  mret( self, -n )
        :  true
    ;
})
console.log( isOdd( 8951531 ) ); // true ; no call stack issue


More about this on [fext.js]. Have fun with it.

On the side: if someone can provide a faster trampoline approach to compare with, I'd be happy to integrate it.

Best regards,
Guillaume

[2013] http://glat.info/js.metaret/
[2016] https://github.com/tc39/proposal-ptc-syntax
[fext.js] http://glat.info/fext

[toc] | [next] | [standalone]

#35289

On Wednesday, June 20, 2018 at 1:11:54 PM UTC-5, glathoud wrote:
> Hello,
> 
> Following the idea of explicitly marking the tail calls that have to be optimized, JavaScript extensions were proposed that add new keywords to the language [2013][2016].
> 
> It turns out that we can do this explicit approach using today's JavaScript, without extending the language. [fext.js] demonstrates this.
> 
> 
> Self-recursion example:
> 
> var gcd = mfun(
>        (a, b) => a > b  ?  mret( self, a-b, b )
>            :     a < b  ?  mret( self, b-a, a )
>            :     a
> );
> console.log( gcd( 2*3*5*17, 3*5*19 ) );  // 15 (3*5)
> 
> 
> Mutual recursion example:
> 
> var isOdd = mfun( function isOdd( n ) {
>     return n > 0  ?  mret( isEven, n-1 )
>         :  n < 0  ?  mret( self, -n )
>         :  false
>     ;
> })
> ,  isEven = mfun( isOdd, function isEven( n ) {
>     return n > 0  ?  mret( isOdd, n-1 )
>         :  n < 0  ?  mret( self, -n )
>         :  true
>     ;
> })
> console.log( isOdd( 8951531 ) ); // true ; no call stack issue
> 
> 
> More about this on [fext.js]. Have fun with it.
> 
> On the side: if someone can provide a faster trampoline approach to compare with, I'd be happy to integrate it.
> 
> Best regards,
> Guillaume
> 
> [2013] http://glat.info/js.metaret/
> [2016] https://github.com/tc39/proposal-ptc-syntax
> [fext.js] http://glat.info/fext

I'm glad to see how far this has progressed since I first saw it here many years ago.

One thing I discovered when I played with this idea some time ago is that it corresponds to an Anamorphism[1] (the unfold function).

For example, when you write out the types (in TypeScript in this case), you see the following:

<script type="TypeScript">
    type Bounce<A> = Done<A> | Call<A>
    type Done<A> = { result: A }
    type Call<A> = { thunk(): Bounce<A> }
</script>

Which is tantalizingly close to the Haskell definition of unfold:

<script type="Haskell">
    data Maybe a = Just a | Nothing
    data F value x = Maybe (value, x)

    ana :: (state -> Maybe (value, state)) -> state -> [value]
    ana f stateOld = case f stateOld of
        Nothing                -> []
        Just (value, stateNew) -> value : ana f stateNew
</script>

We suffer from eager evaluation in JavaScript though, so a direct implementation of unfold could still blow the stack. But we do have iterators now.

This lead me on a search for anyone doing work on Anamorphisms in JavaScript and I came across this:

<http://raganwald.com/2016/11/30/anamorphisms-in-javascript.html>

Asen Bozhilov has been working actively on a related library [2]. I'd be curious what could be synthesized here:

Trampolines generalized to Anamorphisms then translated to iterators?


[1] <https://en.wikipedia.org/wiki/Anamorphism>
[2] <https://github.com/abozhilov/ES-Iter>

[toc] | [prev] | [next] | [standalone]

#35358

On Friday, June 22, 2018 at 10:49:24 PM UTC+2, Michael Haufe (TNO) wrote:
> [...]
> 
> Trampolines generalized to Anamorphisms then translated to iterators?

In terms of performance, I am not sure what rivals a plain old loop. 

Overall, it seems crucial to limit the number of jumps. This was confirmed by the additional performance improvement I obtained by automatically expanding several levels of recursion.

But maybe we are talking about two different topics.

Best regards,
Guillaume Lathoud

[toc] | [prev] | [next] | [standalone]

#35359

On Wednesday, 20 June 2018 20:11:54 UTC+2, glathoud  wrote:

> It turns out that we can do this explicit approach using today's JavaScript

Aka the good old JavaScript, the most misunderstood etc. etc.

Thanks for sharing: IMHO very nice, and clever use of meta-programming in JS.

Indeed, I think lexical evaluation is the opposite of a sin, JS is a functional
language to begin with...

(I'll try and ponder your question about trampolines.)

Cheers,

Julio

[toc] | [prev] | [next] | [standalone]

#35364

On Friday, July 6, 2018 at 6:37:31 PM UTC+2, Julio Di Egidio wrote:
> On Wednesday, 20 June 2018 20:11:54 UTC+2, glathoud  wrote:
> 
> > It turns out that we can do this explicit approach using today's JavaScript
> 
> Aka the good old JavaScript, the most misunderstood etc. etc.
> 
> Thanks for sharing: IMHO very nice, and clever use of meta-programming in JS.
> 
> Indeed, I think lexical evaluation is the opposite of a sin, JS is a functional
> language to begin with...

You're welcome. Yes, tools like `new Function(...)` offer tremendous possibilities. Since the beginning!

One thing I am missing in JavaScript is a (possibly standardized) access to the underlying parser. If I remember correctly, Python offers it. That would make code manipulation much cleaner and easier, without having to use ugly RegExps or maintain parser code.

Another possible direction would be D's mixins (template mixins and string mixins). In practice, that would a bit like `new Function(...)` but keeping access to the local context, which would be... like... the One Evil Thing.

> 
> (I'll try and ponder your question about trampolines.)

Feel free. If you find something faster, I'd be happy to update code & results.

Best regards,
Guillaume

[toc] | [prev] | [next] | [standalone]

#35366

On Saturday, 7 July 2018 07:14:35 UTC+2, glathoud  wrote:

> One thing I am missing in JavaScript is a (possibly standardized) access to the underlying parser. If I remember correctly, Python offers it. That would make code manipulation much cleaner and easier, without having to use ugly RegExps or maintain parser code.

Well, eval() is the parser and gives back "objects" already.  Access to the
private code structure (if that's what you mean) I see more as a violation of
"encapsulation": of course, this implying that IMO a coding discipline of a
sort is always needed.  More below.

> Another possible direction would be D's mixins (template mixins and string mixins). In practice, that would a bit like `new Function(...)` but keeping access to the local context, which would be... like... the One Evil Thing.

Indeed, strongly advised against.  And I see no need, just think pure/
self-contained functions, i.e. context is in the function arguments,
and off you go: to put it simply.

There is also, I'll quickly mention, a matter of keeping concerns separated,
the language minimal, the advantages and discipline of idiomatic/conventional
coding: not to mention, the fact that if anyone finds hoisting difficult,
they rather shouldn't call themselves programmers...  FWIW, I am in fact
against pretty much every language modification that has been and is being
standardised.  JS, the most... and I won't even get into why I think that
has been happening, not just with JS but with everything software.  :)

Anyway, my 2c.

Julio

[toc] | [prev] | [next] | [standalone]

#35368

On Saturday, 7 July 2018 16:09:01 UTC+2, Julio Di Egidio  wrote:
> On Saturday, 7 July 2018 07:14:35 UTC+2, glathoud  wrote:
<snip>
> > but keeping access to the local context, which would be...
> > like... the One Evil Thing.
> 
> Indeed, strongly advised against.  And I see no need, just think pure/
> self-contained functions, i.e. context is in the function arguments,
> and off you go: to put it simply.

Otherwise, there exists a global context: but shared state is the main road
again to pure spaghetti.  --  Indeed, in JS functions *are* closures, but
closures does not mean wildly (and what I said reads what you pass around
and may evaluate better be a self-contained closure).

Julio

[toc] | [prev] | [next] | [standalone]

#35370

On Saturday, July 7, 2018 at 5:16:26 PM UTC+2, Julio Di Egidio wrote:
> ...
> Otherwise, there exists a global context: but shared state is the main road
> again to pure spaghetti.  --  Indeed, in JS functions *are* closures, but
> closures does not mean wildly (and what I said reads what you pass around
> and may evaluate better be a self-contained closure).
> 
> Julio

Thanks for both answers. I agree about most, if not all, of it. 

On the side: yes, I find hoisting just plain great, especially to unwrap half-baked thinking from the top to the bottom, i.e. something one cannot wrap his head around, at least not in its entirety - actually very much what one of the first SICP lectures advise. (That's BTW pretty much the way I wrote the first working version of fext.js)

When reading code, I find hoisting interesting as well, since it shows the top-level API at the top of the code, and goes further down into mostly less and less interesting details.

---

The biggest practical issue I see at the moment is the repetition of the arguments in a "real-life" use case like http://glat.info/fext/#lib_sorted_search_js

You can see 5 times:  `sortedArray, x, less, equal, isFirstFound, isLastFound
            , first_found, last_found, i, j, imax, jmin`

I refuse to put them into an object for performance reasons. If someone has a better idea, please share it.

With eval it would be possible to go down to 1 time, but, apart from the `eval` issues, the implementation would be slightly complicated. A pain without parser.

So here is a compromise: https://github.com/glathoud/fext/issues/11#issuecomment-403236323

This pratical issue would disappear with the use of a local closure (okay IMHO), as in http://glat.info/js.metaret/#sec-sorted-search - *if* e.g. Syntactic Tail Calls would be implemented.

Regards,
Guillaume

[toc] | [prev] | [next] | [standalone]

#35382

On Saturday, 7 July 2018 21:15:04 UTC+2, glathoud  wrote:

> On the side: yes, I find hoisting just plain great, especially to unwrap
> half-baked thinking from the top to the bottom

Are you being sarcastic?  I.e. either I am missing your point here or you
must be missing mine.

I have not so much advocated for hoisting (which anyway I do use, it's
idiomatic and it does simplify the writing of JS code to some extent),
but I am certainly against changes to the language just because 80%+ of
the programmers around just aren't programmers and 80%+ of the vendors
just aren't honest...

Julio

[toc] | [prev] | [next] | [standalone]

#35386

On Saturday, 7 July 2018 21:15:04 UTC+2, glathoud  wrote:
> On Saturday, July 7, 2018 at 5:16:26 PM UTC+2, Julio Di Egidio wrote:
> > ...
> > Otherwise, there exists a global context: but shared state is the main road
> > again to pure spaghetti.  --  Indeed, in JS functions *are* closures, but
> > closures does not mean wildly (and what I said reads what you pass around
> > and may evaluate better be a self-contained closure).
<snip>
> 
> The biggest practical issue I see at the moment is the repetition of the
> arguments in a "real-life" use case like
> http://glat.info/fext/#lib_sorted_search_js
> 
> You can see 5 times:  `sortedArray, x, less, equal, isFirstFound, isLastFound
>             , first_found, last_found, i, j, imax, jmin`
> 
> I refuse to put them into an object for performance reasons. If someone
> has a better idea, please share it.

I should look into the code in detail to see if anything "more clever" could
be done in *that* case, i.e. the actual coding is immediately quite specific.

In general, I do not understand what performance issue you see with passing
just an object: passing lots of arguments is way worse than passing just one
reference in terms of stack operations, i.e. the cost of context switches (the
"call" and then the "return"), then you should see if the dereferencing of
properties is itself such a cost (again, in your specific case) as to still
justify passing so many arguments around...

> This pratical issue would disappear with the use of a local closure (okay IMHO), as in http://glat.info/js.metaret/#sec-sorted-search - *if* e.g. Syntactic Tail Calls would be implemented.

Yes, that's also along the lines of what I mean by "more clever": shared
local state, which (IMO) is still quite OK in JS, given also there is no
concurrency: indeed, as long as the code remains straightforward to read...

Julio

[toc] | [prev] | [next] | [standalone]

#35419

Am Sonntag, 8. Juli 2018 14:00:30 UTC+2 schrieb Julio Di Egidio:
> On Saturday, 7 July 2018 21:15:04 UTC+2, glathoud  wrote:
> 
> > On the side: yes, I find hoisting just plain great, especially to unwrap
> > half-baked thinking from the top to the bottom
> 
> Are you being sarcastic?  I.e. either I am missing your point here or you
> must be missing mine.
> 
> I have not so much advocated for hoisting (which anyway I do use, it's
> idiomatic and it does simplify the writing of JS code to some extent),
> but I am certainly against changes to the language just because 80%+ of
> the programmers around just aren't programmers and 80%+ of the vendors
> just aren't honest...

Fine. No, I wasn't being sacarstic. Maybe "half-baked" wasn't the
best choice of words. I meant: the external API is clear (NOT
half-baked), the crucial internal design decisions are also clear,
but the less crucial in-between stuff hasn't been fully thought out
yet.

Am Sonntag, 8. Juli 2018 14:46:32 UTC+2 schrieb Julio Di Egidio:
> On Saturday, 7 July 2018 16:09:01 UTC+2, Julio Di Egidio  wrote:
> 
> > FWIW, I am in fact against pretty much every language modification that has
> > been and is being standardised.
> 
> *Almost* every: I do love and use strict mode...

Yes. 
I find things like `var {a,b,c} = someObject;` great as well.

Am Sonntag, 8. Juli 2018 15:05:07 UTC+2 schrieb Julio Di Egidio:
> On Saturday, 7 July 2018 21:15:04 UTC+2, glathoud  wrote:
> > On Saturday, July 7, 2018 at 5:16:26 PM UTC+2, Julio Di Egidio wrote:
> > > ...
> > > Otherwise, there exists a global context: but shared state is the main road
> > > again to pure spaghetti.  --  Indeed, in JS functions *are* closures, but
> > > closures does not mean wildly (and what I said reads what you pass around
> > > and may evaluate better be a self-contained closure).
> <snip>
> > 
> > The biggest practical issue I see at the moment is the repetition of the
> > arguments in a "real-life" use case like
> > http://glat.info/fext/#lib_sorted_search_js
> > 
> > You can see 5 times:  `sortedArray, x, less, equal, isFirstFound, isLastFound
> >             , first_found, last_found, i, j, imax, jmin`
> > 
> > I refuse to put them into an object for performance reasons. If someone
> > has a better idea, please share it.
> 
> I should look into the code in detail to see if anything "more clever" could
> be done in *that* case, i.e. the actual coding is immediately quite specific.
> 
> In general, I do not understand what performance issue you see with passing
> just an object: passing lots of arguments is way worse than passing just one
> reference in terms of stack operations, i.e. the cost of context switches (the
> "call" and then the "return"), then you should see if the dereferencing of
> properties is itself such a cost (again, in your specific case) as to still
> justify passing so many arguments around...

In general, yes, I fully agree. However, when profiling shows a
particular function call to be costly, that maybe a case for either
hand-writing optimized code or using some tool like fext.js

In the case of fext.js, by default the bodies of the various
functions are all inlined (and recursively expanded == optimization)
into one big loop (*) inside a single function, so that many useless
instances of parameter copying can be, and are, thrown away.

(*) safety constraint: `var` is not allowed, only `let` and
`const` - otherwise an error is thrown.

To be sure I ran a performance test, more about this here:
https://github.com/glathoud/fext#performance-cost-of-passing-parameters-through-an-object

> > This pratical issue would disappear with the use of a local closure (okay IMHO), as in http://glat.info/js.metaret/#sec-sorted-search - *if* e.g. Syntactic Tail Calls would be implemented.
> 
> Yes, that's also along the lines of what I mean by "more clever": shared
> local state, which (IMO) is still quite OK in JS, given also there is no
> concurrency: indeed, as long as the code remains straightforward to read...

Yes. Agreed.

I tried and failed at argument macros, because it was impossible to
get them working in debug mode.

At the moment the only way I found to implement this was to use
`eval`, see the second code excerpt in:

https://github.com/glathoud/fext#an-example-sortedsearch

Thanks for the feedback and best regards,
Guillaume

[toc] | [prev] | [next] | [standalone]

#35385

On Saturday, 7 July 2018 16:09:01 UTC+2, Julio Di Egidio  wrote:

> FWIW, I am in fact against pretty much every language modification that has
> been and is being standardised.

*Almost* every: I do love and use strict mode...

Julio

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.javascript

csiph-web