Hacker News Reader

Comment by icarus127 | Hacker News Reader

Having state does not mean a function/algorithm is not pure.

http://en.wikipedia.org/wiki/Pure_function

Pure functions model state nicely.

  compile :: Source -> Core
  optimizer :: Core -> Core
  nativeCode :: Core -> Assembly

Those are just signatures, what is going on inside the boxes?

Also, how does one encode iterative computation, like a data-flow analysis, in Haskell? And symbol tables? Is it sufficient that the symbol table is encapsulated within compile even if it involves dictionary read/writes? I'm genuinely curious.

Inside the boxes, you might use a (State SymbolTable) monad to carry around the symbol table:

  type SymbolTable = Map String Symbol

Me and a codeveloper are working on a type system in Haskell, where our current code has iterative computation, until it reaches a fixpoint.

Here's the iterative code:

https://github.com/Peaker/lamdu/blob/master/Lamdu/Data/Expre...

If you need to internally carry state, you just use a State monad to thread around the state purely.

Pure functions handle state without any issues (quite elegantly, actually). They simply can't have mutable state that is globally observable. For instance, you could have a struct, and every time you 'mutate' the struct, you actually clone it and simply set the relevant field to the new value when you're instantiating the new struct.

Functional programming languages have mechanisms that make this process pure, simple, and efficient and you get the benefits of never mutating an existing value (which is important when several different functions may hold a reference to it, among other reasons).

See also: The Haskell state monad or lenses. Theses are pure mechanisms that Haskell provides to update state without mutating any data.

Edit: In the event that you do need shared mutable state, the Haskell STM (Shared Transactional Memory) monad is your answer.

The ST monad [1] provides an efficient hashtable now; doing hashtables as pure functional data structures is well know to be slow.

I would hope one wouldn't need to resort to STM for a compiler, especially since retry is fairly undefined! Still nothing about iterative computation however, I wonder how the ST monad would deal with a Y combinator?

[1] http://hackage.haskell.org/package/hashtables

Reply on news.ycombinator.com