LIPS: Scheme based Lisp interpreter in JavaScript | Hacker News Reader

LIPS: Scheme based Lisp interpreter in JavaScript

lips.js.org

87 pointsaragonite35 comments

Looks great, however note that it doesn't do tail calls, which are required on conforming implementations.

Sorry, I don't quite understand what you mean by 'doesn't do tail calls', I tried the stupid fib and it ran fine (well, okay, slowly but fine). Does it translate to JS and depend on the implementation to provide tail call optimisation/elimination?

Curious, did you run it in Safari on Mac?

Ew, no, I ran it on Firefox on LineageOS.

Apparently this is a tree-walking interpreter, so JavaScript's handling of tail calls is not directly relevant.

I suspect it does tail calls on Safari as Safari is the ONLY browser to completely implement ES6+ and implement proper tail calls (I'd note that it's not the only ES6+ compliant implementation, but most of the rest are aimed at microcontrollers or embedding).

Huh, that in turn means that - server-side or for scripts - this should run better on Bun than on Node (or Deno), because Bun is based on JavaScriptCore and actually handles taill call optimization well[1]

[1] https://www.onsclom.net/posts/javascript-tco

Seems like TCO is is hard to do in browser JS, that's surprising. It's kind of a deal killer for basing a functional language on. JVM too for that matter.

I'm sorry you are so attached to implementation details but that hardly detracts from the general usability of a language. Clojure is hosted both on the JVM and JavaScript and is, all things considered, both usable and popular enough of a Lisp and it definitely doesn't have TCO. You can bail out to using "loop" if you're that perf sensitive.

It's not an implementation detail if you can't do recursion in constant stack space. The underlying VM should allow all CS primitives, and the guest can add constraints as it wants.

How is that not an implementation detail? You can't really inspect the stack at runtime in a useful way. It's literally just performance and yeah you might run out of memory somewhere but that's true of every language detail, some languages are more efficient than others. I'm getting downvoted but I think my comment stands. Clojure is a perfectly useful example of a language without TCO. It's not necessary, it's a detail. And as a long time developer, there hasn't been a single time where I cared if my stack took constant space or not. It has never mattered.

In full TCO, any tail call is a jump in constant stack space.

What Clojure provides is a "loop" construct, which kind of looks like a limited form of self recursion.

Not hard at all. Chrome had it implemented, removed it, then added it back, but only for WASM.

They disliked that it didn't leave stack frames in some cases.

Apple refused to break the JS backward-compatibility guarantee and implemented as-per the spec and Chrome refused to turn on their implementation for users unless it added a special keyword to identify it as a tail call.

Chrome dev's emotional investment and resulting stubbornness has split the JS community and made their implementation incompatible with the spec. They are 100% in the wrong here.

In the meantime on the backend we’re looking at stack traces cut apart with trampolines and living with it…

> Chrome dev's emotional investment and resulting stubbornness ...

You really undermine your position when you start fabricating bullshit like that.

The chromium team had good reasons to not implement it (including clusterfuzz security issues).

Apparently it was actually the Microsoft and Mozilla teams that blocked the feature: https://stackoverflow.com/questions/54719548/tail-call-optim...

FF objected because they didn't want to do the work, but they're now doing that work making proper tail calls work in WASM, so their objection is irrelevant now. MS objected that Windows APIs made PTC slow, but they now use Chrome, so they don't have an excuse today either.

There's nothing inherently insecure about proper tail calls and that is pure FUD.

That just leaves Google. They chose to die on the hill of syntactic tail calls and are still refusing to implement the spec. The only reason left is their pride and emotional investment in STC.

Even back then, Safari was implementing and had more marketshare than Edge and FF combined (now 2.5x their combined market share with FF only having around 3% share today).

I'm tired of bad excuses and want them to actually implement the now 8 year old spec properly.

Implementation language doesn't have necessarily to do with language being implemented, unless one does the easy way to translate one into the other.

I might be confused, but do you mean "it doesn't do tail call optimization"? "Doing tail calls" is a bit of a strange phrase, if I understand the concept of what a tail call is—I'm under the impression that a tail call is just a call, that happens to be the final action in its scope. If a language can do "calls" at all then it can "do tail calls."

Yes, you're correct about the more general meaning. But in the Scheme world "doing tail calls" means something like being "properly tail recursive" (see https://www.gnu.org/software/guile/manual/html_node/Tail-Cal... for more details). It's not appropriate to call it an optimization because it's a foundational property of the language.

Got it. Thanks for giving more of the language-specific context on that.

It's best to call it "Tail Call Elimination". It's not a nice-to-have optimization in Scheme as using tail calls is the only way to iterate (do is a convenience built on tail calls), it's a necessity for any non-toy Scheme implementation.

Tail call elimination isn't a very good term.

- The only optimization that completely eliminates calls is inlining, so it is misleading. An optimized tail call still has some trappings of a call, like a control transfer somewhere else, with arguments.

- In Scheme lingo, the procedure calls so optimized are called tail calls; they are produced, and thus not eliminated. When the goto is taken, the procedure is said to be making a tail call, or tail calling. In assembly language, if you hand coded such a goto, you might put in a comment saying "this is a tail call", so it's not just Scheme lingo.

You know this, but being explicit helps the casual reader:

The "elimination" in "tail call elimination" refers to the "elimination" of the call frame.

In languages like C each call pushes a frame to the call stack. When the called procedure is done, execution returns to the site of the call. In a tail call there is no work to done, so the frame is now removed and execution continues where the previous frame points. But ... if we simply never omit the call frame, then executation then exectuation automatically returns to the parent frame.

The spec talks about allowing an "unbounded number of active tail calls". In an implementation with frames, it means tail calls can't just keep pushing frames.

Seen in isolation "tail call elimination" doesn't seem like a big deal, but combined with "real macros" (structural, scope-respecting macros) it is possible to implement control structures as a user without worrying about stack overflow.

In Scheme slang, a tail call is a procedure call that has been turned into a kind of goto, and so doesn't require a new stack frame or return linkage.

The term "tail call optimization" still makes sense, but refers to the production of tail calls out procedure calls that occur in the tail position, not to the reduction/elimination of tail calls.

Yes, this was an issue of me knowing general terminology (where this idea, or similar ones, show up in Haskell and Clojure, for example) but not the more specific parlance of Scheme. I'm happy to learn!

Author here. That's why it's not listed on the official scheme.org website as one of the implementations. I was told that to me called Scheme, you need TCO and continutations.

I made one attempt to implement them some time ago but failed. The code was not working. I based my implementation on someone else code. And later turned out that the call/cc that I based my code pm was not even full continuations and failed my test case.

Most Toy Scheme implementations don't have TCO and call/cc so I can't use them as a reference. But I have an implementation that is really promising that implemented them, the code is very minimal and I can base my code on that.

    lips> (let ((a (begin (define b 4) 5)))
            (+ a b))
    9
    lips> b
    4

I mentioned this regarding a previous version and the author said it was deliberate. I feel it breaks lexical context and is icky in general. Scheme has definition context, and loosening it is probably a good thing - but not further than "to all bodies".

How does it compare to https://try.gambitscheme.org ?

Gambit has tail call optimisation:

  > (define (fib x)
      (let loop ((a 0)
                 (b 1)
                 (c 0))
        (if (= c x)
            a
            (loop b
                  (+ a b)
                  (+ c 1)))))
  > (fib 10)
  55
  > (fib 100)
  354224848179261915075
  > (fib 1000)
  43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

LIPS has documentation builtin into every function. You can see the docstring when you hover over the name of the symbol in the REPL. It also has auto-indent. Also if you press enter you can get back and modify previous lines of code. History doesn't repeat lines only full S-Expressions so it's easy to rerun a big chunk of code.

Even though Try Gambit is a REPL it's not very user-friendly.

The try.gambitscheme.org web app has most of these features and more:

- REPL history with up/down arrows (explained on the landing page's README)

- You can use the "help" procedure to browse the full documentation

- TAB key for autocompletion

- In addition to the REPL there is a code editor to edit programs stored in the browser

- The system supports multiple threads, one REPL per thread

- There is a builtin tutorial to learn the basics of Scheme with examples executable in the REPL with a single click on a "run" button

- The REPL supports single stepping the execution of code

- Easy interface to JS with the SIX syntax extension, e.g. (let ((msg "hello")) \console.log(`msg, 1+2/3))

- The error messages are clear and precise giving the file and line number and highlighting in yellow the piece of code (in the REPL or file) that raised the exception. Just try this in both systems to see the difference:

    > (define (f x) (/ 1 (* x x)))
    > (f 5)
    > (f "hello") ;; the * procedure will raise an exception and highlight "(* x x)"

- in Gambit History works on lines not S-Expressions like in LIPS

- With LIPS you don't need any new syntax to integrate with JavaScript you just use JavaScript directly (let ((msg "hello") (console.log msg)) SIX syntax doesn't look like Scheme.

- Help popup documentation, with LIPS you have documentation directly in the REPL (when you hover over the symbol) and you can access docstring as strings and assign them to values.

- You can create new syntax similar to scheme vectors and make representation the same as code

- You can manipulate almost everything in the language like environments that you can modify

- LIPS show stack trace not one line which gives an error that makes it easier to find where the error happens.

- The Bookmarks allow to run the REPL on every page even PDF files with R7RS spec.

- You can actually run the code that uses quotes (’ The apostrophe symbol) from the spec if you use syntax extension to add new syntax.

I like the idea, but got this when I tried to run it on my Mac:

> lips node:internal/modules/esm/resolve:853 throw new ERR_MODULE_NOT_FOUND(packageName, fileURLToPath(base), null);

Unfortunately, I don't have access to a Mac. I can only run Safari at BrowserStack. So I can't test it and fix it.

But this is Open Source and anyone who has a Mac can test it and fix this issue. I can't.

I like ClojureScript.

Reply on news.ycombinator.com