Arc Forumnew | comments | leaders | submitlogin
A tiny lisp interpreter in JS (github.com)
3 points by kraks 3569 days ago | 3 comments


2 points by rocketnia 3569 days ago | link

The parser implementation is pretty concise. :)

I'm concerned about looping. It looks like you're implementing function calls in terms of JavaScript function calls, so there's no tail call elimination, and a recursive loop will soon exhaust the JS stack. A while loop could be a practical alternative.

-----

2 points by kraks 3567 days ago | link

Thanks to your advices. The runtime is based on Node.js, so there is no tail recursion elimination, I'm finding a method to transform recursion code to iteration code automatically, do you have some advice?

-----

2 points by rocketnia 3567 days ago | link

If you want to have full tail recursion elimination, I recommend changing everything to work in continuation-passing style. That will overflow the JS stack even sooner, so I recommend using a trampoline.

  // before
  function plus( a, b ) {
      return a + b;
  }
  
  // after
  function plus( a, b, then ) {
      // We call `then()` only after we've unwound the stack.
      return trampolineBounce( function () {
          return then( a + b );
      } );
  }
  
  // the trampoline system
  function trampolineBounce( func ) {
      return { type: "bounce", func: func };
  }
  function runTrampoline( func ) {
      var step = func( function ( result ) {
          return { type: "result", result: result };
      } );
      while ( step.type === "bounce" )
          step = step.func();
      return step.result;
  }
  
  // example usage
  var onePlusTwoPlusThree = runTrampoline( function ( then ) {
      return plus( 1, 2, function ( onePlusTwo ) {
          return plus( onePlusTwo, 3, function ( result ) {
              return then( result );
          } );
      } );
  } );
This part is a bit redundant:

  function ( result ) {
      return then( result );
  }
It's equivalent to `then` but uses one more JS stack frame. We can just reuse the `then` continuation directly. In general, the places we can do this are tail calls.

  // example usage with a tail call
  var onePlusTwoPlusThree = runTrampoline( function ( then ) {
      return plus( 1, 2, function ( onePlusTwo ) {
          return plus( onePlusTwo, 3, then );
      } );
  } );
---

"I'm finding a method to transform recursion code to iteration code automatically"

I don't think it's possible to get full tail recursion elimination that way unless you statically analyze the whole program, or you transform the code so it uses the CPS-and-trampolining technique above.

Maybe you can get something somewhat less powerful than full tail recursion, but I don't have advice on that. If you do want to work on that, here's an example of a tail-recursive while loop you can test with:

  ; Evaluate an expression repeatedly until it returns something falsy.
  ( (lambda (f body) (f f body))
    (lambda (f body)
      (if (body)
        (f f body)
        #f))
    (lambda () ___))  ; insert expression here

-----