undefined | Better HN

0 pointsvnorilo3y ago0 comments

Yes, and also not a data structure that is suitable for the task. If you want to keep every version of the buffer as a value (which has nice properties like versioning) you would need a data structure that shares most of its structure with the previous versions. Like a persistent radix-n tree. Slower than mutable buffer for sure, but not pathological.

0 comments

zodiac3y ago

Got it. I'm familiar with persistent data structures but I was more curious as to the "Haskell approach" of doing the same problem (which, I assume, doesn't use persistent data structures per se).

Follow-up question: if you wanted to implement the interpreter (as in the author's article) in idiomatic Haskell, would using the State monad be one solution? (I assume that's what you meant by "compose functions that manipulate that state"). Then, if you translated that Haskell directly into Racket (something like: use the exact same functions, just delete the type annotations), what would be the run-time of the solution?

(Not a trick question, I really don't know the answers. I've "understood" how the State, Reader, Writer work in the sense of reading the code, checking the types, and confirming that they do what they claim, but didn't think about how a compiler would compile them before)

dllthomas3y ago

Translating naively, in Haskell I might use https://hackage.haskell.org/package/containers-0.6.5.1/docs/..., which does use sharing to reduce copying.

tromp3y ago

A simple Brankfuck interpreter in Haskell using state monads may be found at https://tromp.github.io/cl/Binary_lambda_calculus.html#Brain...

1 more reply

vnoriloOP3y ago

Not sure there's any benefit in using the state monad for an interpreter.

My first thought is to model a cycle of the interpreter as a function of old state into new state.

I guess the state monad could be used to thread the state dataflow through the interpreter, but it would not make the copy-big-buffer any more efficient. Code using the state monad is still pure and uses immutable data.

Now if you have to use a mutable buffer (only one fits in memory?) then you could use techniques like the IO monad to deal with it.

Disclaimer: Am more Clojure than Haskell person.

ChadNauseam3y ago

Writing efficient interpreters in a functional style is not easy. I write interpreters in OCaml for a living and we had to switch to a mutation-heavy style for performance and memory usage reasons. It can be done though.

When you think about it, any dependently typed language has to have an interpreter inside it, because you can put function applications inside a type and the typechecker will probably need to evaluate the application at some point. The go-to technique is to use Normalization by Evaluation [0], where you convert the AST version of a function in the interpreted language to an actual function in the host language, and piggyback off the host language's (presumably very fast) function application.

[0]: https://en.wikipedia.org/wiki/Normalisation_by_evaluation

4 more replies

j / k navigate · click thread line to collapse