4 ms·

When I did something similar the hard part was implementing continuations efficiently, a feature that a lot of these small lisp interpreters lack.

timmg 4y ago
Any pointer to how that's done (in the context of an "easy" interpreter like this)?
- deanmen 4y ago
  Trampolines
  - convolvatron 4y ago
    as long as your arguments never spill, you can also make an asm insert macro that does a jump instead of a call
    - earleybird 4y ago
      The purpose being 'rename + goto'?
      - convolvatron 4y ago
        the purpose being to be able to use generic C function bodies as continuations without having to trampoline the stack
- emmanueloga_ 4y ago
  The "PLAI" book explains how to do it trough a rewrite/desugaring transformation: [0] The heart of [a CPS] transformation is [...] to turn every one-argument function, f, into one with an extra argument. This extra argument is the continuation, which represents the rest of the computation. The continuation is itself a function of one argument. This argument takes the value that would have been returned by f and passes it to the rest of the computation. f, instead of returning a value, instead passes the value it would have returned to its continuation. CPS is a general transformation, which we can apply to any program. Because it’s a program transformation, we can think of it as a special kind of desugaring: in particular, instead of transforming programs from a larger language to a smaller one (as macros do), or from one language to entirely another (as compilers do), it transforms programs within the same language: from the full language to a more restricted version that obeys the [... CPS pattern]. As a result, we can reuse an evaluator for the full language to also evaluate programs in the CPS subset. There's a more terse description on this site too [1]. And I have to agree with this: [...] there are many methods for transforming into CPS [... but] learning CPS transformation remains difficult. Also I remember stumbling upon this article [2] which kind of gave me an excuse to not pay too much attention to CPS :-) (...but not really :-p, mostly the subject got too hairy for me and I lost interest :-p). If I remember right, the article argues in favor of "delimited continuations" as opposed to implementing full general call/cc. 0: http://cs.brown.edu/courses/cs173/2012/book/Control_Operations.html#%28part._.Continuation-.Passing_.Style%29 http://cs.brown.edu/courses/cs173/2012/book/Control_Operatio... 1: https://matt.might.net/articles/cps-conversion/ https://matt.might.net/articles/cps-conversion/ 2: https://okmij.org/ftp/continuations/against-callcc.html https://okmij.org/ftp/continuations/against-callcc.html
  - bruce343434 4y ago
    This doesn't go into detail of how to make stackfull continuations work (and indeed when it is necessary to make a new stack). If you're working in C, you need to use inline assembly for this. setjmp and longjmp are not stackfull.
- psuedobrain 4y ago
  CEK[1] machines are very clean way of implementing continuations or other features that can be implemented in terms of them in a language with no support for lambdas or closures. they are also reasonably fast too. i implemented a simple unlambda[2] interpreter in haskell using the cek/cesk style and it was ~20% faster and more memory efficient than the fastest c interpreter i could find. [1] https://matt.might.net/articles/cek-machines/ https://matt.might.net/articles/cek-machines/ [2] http://www.madore.org/~david/programs/unlambda/ http://www.madore.org/~david/programs/unlambda/

timmg 4y ago

Any pointer to how that's done (in the context of an "easy" interpreter like this)?

deanmen 4y ago
Trampolines
- convolvatron 4y ago
  as long as your arguments never spill, you can also make an asm insert macro that does a jump instead of a call
  - earleybird 4y ago
    The purpose being 'rename + goto'?
    - convolvatron 4y ago
      the purpose being to be able to use generic C function bodies as continuations without having to trampoline the stack
emmanueloga_ 4y ago
The "PLAI" book explains how to do it trough a rewrite/desugaring transformation: [0] The heart of [a CPS] transformation is [...] to turn every one-argument function, f, into one with an extra argument. This extra argument is the continuation, which represents the rest of the computation. The continuation is itself a function of one argument. This argument takes the value that would have been returned by f and passes it to the rest of the computation. f, instead of returning a value, instead passes the value it would have returned to its continuation. CPS is a general transformation, which we can apply to any program. Because it’s a program transformation, we can think of it as a special kind of desugaring: in particular, instead of transforming programs from a larger language to a smaller one (as macros do), or from one language to entirely another (as compilers do), it transforms programs within the same language: from the full language to a more restricted version that obeys the [... CPS pattern]. As a result, we can reuse an evaluator for the full language to also evaluate programs in the CPS subset. There's a more terse description on this site too [1]. And I have to agree with this: [...] there are many methods for transforming into CPS [... but] learning CPS transformation remains difficult. Also I remember stumbling upon this article [2] which kind of gave me an excuse to not pay too much attention to CPS :-) (...but not really :-p, mostly the subject got too hairy for me and I lost interest :-p). If I remember right, the article argues in favor of "delimited continuations" as opposed to implementing full general call/cc. 0: http://cs.brown.edu/courses/cs173/2012/book/Control_Operations.html#%28part._.Continuation-.Passing_.Style%29 http://cs.brown.edu/courses/cs173/2012/book/Control_Operatio... 1: https://matt.might.net/articles/cps-conversion/ https://matt.might.net/articles/cps-conversion/ 2: https://okmij.org/ftp/continuations/against-callcc.html https://okmij.org/ftp/continuations/against-callcc.html
- bruce343434 4y ago
  This doesn't go into detail of how to make stackfull continuations work (and indeed when it is necessary to make a new stack). If you're working in C, you need to use inline assembly for this. setjmp and longjmp are not stackfull.
psuedobrain 4y ago
CEK[1] machines are very clean way of implementing continuations or other features that can be implemented in terms of them in a language with no support for lambdas or closures. they are also reasonably fast too. i implemented a simple unlambda[2] interpreter in haskell using the cek/cesk style and it was ~20% faster and more memory efficient than the fastest c interpreter i could find. [1] https://matt.might.net/articles/cek-machines/ https://matt.might.net/articles/cek-machines/ [2] http://www.madore.org/~david/programs/unlambda/ http://www.madore.org/~david/programs/unlambda/