search

LIPS-scheme / lips

Scheme based powerful lisp interpreter in JavaScript
https://lips.js.org
Other
397 stars 32 forks source link

Continuations and TCO #127

Open jcubic opened 3 years ago

jcubic commented 3 years ago

Implement first class continuations (call/cc) and Tail Call Optimization.

jcubic commented 2 years ago

Great post on StackOverflow about TCO and Continuations, it's multiple answers by the same person:

How to adapt trampolines to Continuation Passing Style?

mark-friedman commented 2 months ago

What is the plan with regard to continuations and tail call optimization? In the short term TCO is more important to me, since it is a fairly basic Scheme feature, especially in educational contexts. In the long term it would also be really nice to have call/cc, since there are a bunch of nice Scheme libraries and SRFIs which use it. It looks like there was some work done on a "continuations" branch back in August of 2021 which was not completed. Was that because you came across the StackOverflow post that you mention above and decided that that was a better approach?

jcubic commented 2 months ago

No, the code in 2021 was based on one implementation, I was not able to make it work. But later I found out that the implementation I based my code on was not actually proper continuations. Even BiwaScheme don't have 100% working continuation.

So now I need to write those from scratch, I started working on it actually in continuations-2 branch. And this time I will base the code on different scheme implementation that do work. The code will be based on js-scheme that have most core features of Scheme and the code is small and simple.

I also want to have call/cc and TCO. I planned to do this in a near, unknown future, but now you just give me extra motivation to actually continue working on it. It would be really nice if all examples in Scheme tutorial on the website work in LIPS.

lassik commented 2 months ago

Worth reading what IronScheme did on the .NET framework.

In particular:

There is a call/cc in IronScheme, but it is not a complete implementation. You can only do escape continuations, basically call/ec from Racket. [...] The only way to implement call/cc completely in .NET is to use CPS in the compiler. I did such an expirement before, and while it does work, it was horribly slow (10 times or more), and all the .NET interop pretty much goes out of the window.

jcubic commented 2 months ago

LIPS already has performance issues. Maybe adding call/cc will not make it slower. Also, in my opinion (because of performance) the best use case for it is in education.

mark-friedman commented 2 months ago

LIPS already has performance issues. Maybe adding call/cc will not make it slower. Also, in my opinion (because of performance) the best use case for it is in education.

Indeed, education is my use case.

mark-friedman commented 2 months ago

BTW, I've posted a few messages to your LIPS gitter. Is that the best place to have LIPS related discussions or would you rather do it via some other place, (like, perhaps, GitHub Discussions)?

jcubic commented 2 months ago

I'm not at home right now, and I didn't have Gitter tab open.

mark-friedman commented 2 months ago

I'm not at home right now, and I didn't have Gitter tab open.

I understand. So, in the future would you prefer Gitter or something else? Whatever is most convenient for you is fine by me.

mark-friedman commented 2 months ago

I also want to have call/cc and TCO. I planned to do this in a near, unknown future, but now you just give me extra motivation to actually continue working on it.

Great! Thanks.

jcubic commented 2 months ago

Whatever works best for you. When I'm at home I will probably reply faster on Gitter and even if I replay late after a few exchanges of messages we will sync and exchange instantly because we will be both live.

jcubic commented 2 months ago

Answer to my question that suggest spaghetti stack.

mark-friedman commented 2 months ago

Your last comment led me down a bit of a rabbit hole which led me to a few papers that I think might be useful for you.

jcubic commented 2 months ago

Thanks.

mark-friedman commented 1 month ago

Compiling for Multi-language Task Migration: You wouldn't know it by the title, but this is another, potentially useful, paper with info about implementing TCO and continuations for Schemes that interact with other non-Scheme languages.

mark-friedman commented 2 weeks ago

Just curious if this (especially TCO) is something that is being actively worked on (i.e. might be appearing in the relatively near future)?

jcubic commented 2 weeks ago

No, it's not actively worked on right now. I would like to have this implemented, but I don't have much time right now.

mark-friedman commented 2 weeks ago

Thanks for the update, @jcubic. I will plan accordingly.