Hacker News Reader

Comment by catern | Hacker News Reader

Note that you don't have to defunctionalize to be serializable or perform other manipulations. Tagless final style extensible-interpreter techniques allows direct-style programs to be serialized and manipulated.

View on HN

That sounds interesting too. Any chance you have a link or two handy for reference? I've seen Oleg Kiselyov's bibliography on the tagless-final style (http://okmij.org/ftp/tagless-final/index.html), but there's quite a lot there.

Referencing his "Typed Tagless Final Interpreters: Lecture Notes", it seems like a tagless-final interpreter is just a regular function whose result depends on the domain you intend to evaluate it in. It seems like the easiest thing to do is define a domain in which the tagless-final primitive operations map to an initial type, then serialize that. (So tagless-final seems at least as expressive as the initial representation, and by the "initial" concept, I would expect it to be no more expressive.)

There are also some blog posts over at Serokell about tagless final in Haskell: https://serokell.io/blog/tagless-final.

How so? Tagless final style usually requires a monad instance; how can you describe the result of a call to fmap in a serializable way without executing it?

Applicative Functors/Selective Applicative Functors should be more suitable to serialization than monads, because they do not contain lambdas and expose the underlying structure, allowing you to inspect,modify it, etc.:

https://www.cs.ox.ac.uk/jeremy.gibbons/publications/delivery... http://simonmar.github.io/bib/papers/haxl-icfp14.pdf https://www.staff.ncl.ac.uk/andrey.mokhov/selective-functors...

Applicatives still contain lambdas in the same sense that monads do, no?

I think you can think of applicative like specifying the abstract syntax tree for the operation you want to perform and then giving it to an evaluator, as opposed to a monad where you code the implementation more directly, but deliver it opaquely as a lambda to the system.

Presumably you execute it with an instance that does serialization instead of interpretation.

This is correct. (Something else to add on here: Initial and final encodings are bijective – theoertically, anything one can do, the other can too.)

But you can't serialize a function - that's the whole point of the post.

But if you're writing an interpreter, you can serialize the result of 'evaluating' the structure of your 'function' made out of components that are being interpreted by your code, thus turning your 'function' (when evaluated with one set of code) into a data structure (when evaluated by something that serializes each of the components making up your function)

At that point you've already evaluated it and can't recover the original program - you're serializing the result of interpretation, not the computation to be interpreted. Since that computation might contain arbitrary functions, the only way to serialize that would be if you had a way of serializing arbitrary functions.

Reply on news.ycombinator.com