Haskell monk use odor code?

Question

God, I hate the term “code smell,” but I can't think of anything more accurate.

I develop a high-level language and compiler for Whitespace in my free time to learn about building a compiler, and functional programming (the compiler is written in Haskell).

During the compiler code generation phase, I have to maintain the state -ish data when I cross the syntax tree. For example, when compiling flow control statements, I need to create unique names for shortcuts that can be redirected to (labels created using the counter that was passed, updated and returned, and the old counter value should never be used again). Another example is that when I come across string literals in the syntax tree, they need to be constantly converted to heap variables (in Whitespace, strings are best stored on the heap). I am currently completing the entire state monad code generation module to handle this.

I was told that writing a compiler is a problem well suited to a functional paradigm, but I find that I design it just like I would design it in C (you can really write C in any language - even Haskell w / state monads).

I want to learn how to think in Haskell (rather, in a functional paradigm) - not in C with Haskell syntax. Should I really try to eliminate / minimize the use of the state monad or is this a legitimate functional “design pattern”?

Answer 1

I would say that state is not at all a code smell if it remains small and well controlled.

This means that using monads such as State, ST, or custom, or just having a data structure containing state data that you pass in several places is not so bad. (In fact, monads are just help in doing just that!) However, having a state that is ubiquitous (yes, that means you, MO monad!) Has a bad smell.

A vivid example of this was my team, which worked on our entry for the ICFP Programming Contest 2009 (the code is available at git: //git.cynic.net/Haskell/MKVP- contest2009). We received several different modular parts:

• VM: the virtual machine that ran the simulation program
• Controllers: several different sets of routines that read the simulator output and generate new control inputs.
• Solution: create a solution file based on controller output
• Visualizers: several different sets of routines that read both input and output ports and generate some kind of visualization or log of what happened as the simulation progressed.

Each of them has its own state, and they all interact in different ways through the input and output values ​​of the virtual machine. We had several different controllers and visualizers, each of which had its own different state.

The key point here was that the interiors of any particular state were limited to their own separate modules, and each module did not know anything about the existence of a state for the other modules. Any particular set of code and data with state usually consisted of only a few tens of lines with a small number of data elements in state.

All this was glued into one small function of about a dozen lines that did not have access to the interiors of any of the states and which simply called the right things in the correct order, when they went in cycles in the simulation and passed a very limited amount of external information for each module ( of course, together with the previous state of the module).

When state is used in such a limited way, and the type system prevents you from inadvertently modifying it, it is fairly easy to handle. This is one of Haskell's beauties that allows you to do this.

One answer says, "Do not use monads." From my point of view, this is exactly the opposite. Monads are a management structure that, among other things, can help you minimize the amount of code that relates to state. If you look at monadic parsers as an example, the state of the analysis (i.e., the text being analyzed, how far it got to it, any accumulated warnings, etc.) should go through every combinator used in the parser, but there will be only a few combinators who actually manipulate the state directly; everything else uses one of these several functions. This allows you to clearly see in one place all the small amount of code that can change state, and more easily understand how it can be changed, which again makes work easier.

Answer 2

I wrote several compilers in Haskell, and the state monad is a reasonable solution to many compiler problems. But you want to keep it abstract - don't make it obvious that you are using a monad.

Here is an example from the Glasgow Haskell compiler (which I did not write, I just work with multiple edges), where we plot the flow of control. Here are the main ways to create charts:

empyGraph :: Graph mkLabel :: Label -> Graph mkAssignment :: Assignment -> Graph -- modify a register or memory mkTransfer :: ControlTransfer -> Graph -- any control transfer (<*>) :: Graph -> Graph -> Graph 

But, as you have discovered, supporting the supply of unique labels is tedious at best, so we also provide these features:

 withFreshLabel :: (Label -> Graph) -> Graph mkIfThenElse :: (Label -> Label -> Graph) -- branch condition -> Graph -- code in the 'then' branch -> Graph -- code in the 'else' branch -> Graph -- resulting if-then-else construct 

The whole thing Graph is an abstract type, and the translator just funly constructs the graphs in a purely functional way, without realizing that something monadic is happening. Then, when the graph is finally built to turn it into an algebraic data type, we can generate the code from, we give it a supply of unique shortcuts, launch the state monad and pull out the data structure.

The state monad is hidden under it; although this is not client-specific, the Graph definition looks something like this:

 type Graph = RealGraph -> [Label] -> (RealGraph, [Label]) 

or more precisely

 type Graph = RealGraph -> State [Label] RealGraph -- a Graph is a monadic function from a successor RealGraph to a new RealGraph 

With a state monad hidden behind a layer of abstraction, it is not stinky at all!

Answer 3

Have you looked at Grammar Attributes (AG)? (More on wikipedia and the Monad Reader article )?

With AG, you can add attributes to the syntax tree. These attributes are separated in synthesized and inherited attributes.

Synthesized attributes are things that you generate (or synthesize) from your syntax tree, it can be generated code or all comments or something else that interests you.

Inherited attributes are entered into your syntax tree, it can be an environment or a list of labels used during code generation.

At the University of Utrecht, we use the Attribute Grammar System ( UUAGC ) to write compilers. This is a preprocessor that generates haskell code ( .hs files) from the provided .ag files.

---

Although, if you are still learning Haskell, then maybe this is not the time to start learning another layer of abstraction over this.

In this case, you can manually write the type of code that generates the grammar for you, for example:

 data AbstractSyntax = Literal Int | Block AbstractSyntax | Comment String AbstractSyntax compile :: AbstractSyntax -> [Label] -> (Code, Comments) compile (Literal x) _ = (generateCode x, []) compile (Block ast) (l:ls) = let (code', comments) = compile ast ls in (labelCode l code', comments) compile (Comment s ast) ls = let (code, comments') = compile ast ls in (code, s : comments') generateCode :: Int -> Code labelCode :: Label -> Code -> Code 

Answer 4

You might need an applicative functor instead of a monad:

http://www.haskell.org/haskellwiki/Applicative_functor

I think the original article explains this better than the wiki:

http://www.soi.city.ac.uk/~ross/papers/Applicative.html

Answer 5

I don't think that using State Monad is the smell of code when it was used to model state.

If you need to pass state through your functions, you can do it explicitly by taking state as an argument and returning it to each function. State Monad offers a good abstraction: it conveys the state to you and provides many useful functions for combining functions that require state. In this case, using State Monad (or Applicatives) is not a code smell.

However, if you use the State Monad to imitate the imperative style of programming while a functional solution would be enough, you simply complicate the situation.

Answer 6

In general, you should try to avoid a condition where this is possible, but it is not always practical. Applicative makes eye-catching code more enjoyable and functional, especially tree traversal code can benefit from this style. For the name generation problem, there is now a pretty good package: value-supply .

Answer 7

Well, do not use monads. The power of functional programming is the purity of functions and their reuse. There, in this article, one of my professors once wrote, and he is one of the guys who helped build Haskell.

The paper is called “ Why does functional programming matter?”, I suggest you read it. It is well read.

Answer 8

be careful with the terminology here. The state itself is bad; functional languages ​​have a state. What is code smell when you discover that you want to assign values ​​to variables and change them.

Of course, the Haskell state monad exists for precisely this reason - as with I / O, it allows you to do unsafe and unreliable things in a limited context.

So yes, that is probably the smell of code.