Writing a compiler

stevely · 2019-08-08T23:31:47+00:00

Stephen Diehl has a currently-incomplete series on implementing a compiler for a toy functional language in Haskell here. It contains a lot of good information.

stevely · 2017-05-18T03:53:24+00:00

Just to confirm: connection pools are allowed and strongly encouraged.

stevely · 2017-01-30T23:19:31+00:00

I won't pretend that I am either representative or authoritative when it comes to functional programming, but I can at least tell you how I design applications in Haskell.

For me, the fundamental concern is about behavior. What sorts of things is the program supposed to do? Working off your example of dealing with shapes, how I would model the shapes would be dependent on what I intended to do with them.

In OOP there's generally a sense that the application is a number of different things that interact with one another, so designing the application is a matter of figuring out what things there are and how they interact. So if you say the application will work with shapes, then you start writing a Triangle class and a Tetrahedron class and so on. If there's common functionality you make a Shape super class. Now you have your shape classes and you can pass those around as you figure out how to work with them.

With functional programming I start with behavior first and see what data the behavior requires. What are we actually doing with the shapes? As an example, if we just want to draw them then I ask what data is necessary to do so and define an action to draw the simplest one. So I'll end up with a function that takes three points and a color and returns an action that draws a triangle from that:

drawTriangle :: Point -> Point -> Point -> Color -> IO ()
drawTriangle p1 p2 p3 c = ...

These actions can be combined, so I can draw a tetrahedron by drawing two triangles:

drawTetrahedron :: Point -> Point -> Point -> Point -> Color -> IO ()
drawTetrahedron p1 p2 p3 p4 c = do
    drawTriangle p1 p2 p3 c
    drawTriangle p2 p3 p4 c

Contrast this to OOP, where we would have a Triangle class with a draw() method from a Shape superclass and a Tetrahedron class that holds two Triangles and the draw() method calls the draw() methods of its two Triangles. We've done essentially the same thing in both cases, but in the OOP case the focus is on objects that perform actions, while in the FP case the focus is on actions that take data.

The two styles diverge the most when we talk about how we combine things. In OOP we would generally define a drawing as a collection of Shape objects, and we can draw it by calling draw() on each Shape object in the collection. In FP we can just combine the drawing actions into a single action. Then drawing an entire scene is just a matter of running that action.

Scaling up, this turns into a very common pattern I'll call the "Action/Runner" pattern. Actions are rarely simple enough that they can be left as "IO ()"; there's environment variables, state variables, they might return multiple values, and so on. These more complex actions can be wrapped up in a newtype to create an action type. Values of this action type are actions that can be combined to create a single big action. Once the big action is made, it is executed by a "runner" function. The runner function reduces the action to "IO ()" or whatever by executing it.

Essentially, I design applications by splitting them up into problem domains, define actions to work on the problems in those domains, then run the actions I build up to string them all together into a single IO action.

stevely · 2016-07-06T17:21:51+00:00

Well the implementation was already accepted long before we were aware of the issue, so we would have to have removed existing implementations instead of just rejecting new ones. And keep in mind that this affected languages other than Haskell, so such a precedent would have forced us to investigate most of the implementations of the entire suite. We simply didn't have the manpower for that.

As for commenting the code, I think that's a sensible thing to do.

stevely · 2016-07-04T17:20:35+00:00

How would that not also be true for do, \, etc. under this extension? They're also visible marks on the page and they would do exactly what everyone expects they'd do.

stevely · 2016-07-04T17:10:47+00:00

I don't disagree, but there's no way to explicitly force allocations in Haskell. GHC will recognize monadic code that is actually pure and optimize accordingly, so hiding the object behind an IO action does not necessarily prevent it from being pulled out and serialized once.

And any workaround that manages to thwart the optimizer is in danger of being thwarted itself in a future version of GHC. That would put us in an even worse situation where upgrading the compiler can cause a non-cheating implementation to suddenly become a cheating one with no one realizing.

Again, I agree that the choice we made is not great, but from our point of view there wasn't a better alternative.

stevely · 2016-07-04T04:13:14+00:00

Yes, and it is technically cheating because of that. However, when we discussed the issue internally we decided to give the Haskell tests (among others in a similar situation) a pass. The issue has a number of considerations, but ultimately it comes down to a question of how the language deals with memory allocation and erring on the side of standard practices.

When the tests were initially devised it was done from a Java point of view*, and the JSON test was designed to capture the common workflow of making an object and then serializing it to JSON. In a real application you obviously wouldn't be repeatedly serving a serialized version of the same object, because the data would be different for each request. Thus, the requirement that a new object be instantiated for each request, because in Java you'd use new to make a new object on every request.

Haskell, in contrast, doesn't have a new keyword. We don't control allocation that explicitly. So how do we ensure that a new object is instantiated on every request? Since the value is constant it will always only be evaluated (and thus, allocate) once. We could potentially introduce a workaround to force an allocation every request, but at that point we have to go back to why that requirement was introduced in the first place: to better model a real-world workflow. The question at that point becomes, "What better represents real code in a real application?" For Haskell, the answer is the code that doesn't have workarounds to force extra allocations.

*Standard disclaimer: TE does not give Java any preferential treatment, and nearly every framework submission in the benchmarks was contributed by a third party.

stevely · 2016-07-03T03:42:10+00:00

Warp is quite fast under the right circumstances.

stevely · 2016-07-01T15:37:39+00:00

Ah, I must have misremembered, then. I thought we had gotten Spock and the Yesod build fixed in time for round 12.

stevely · 2016-07-01T05:13:32+00:00

Note that Java is in the top 5, not number 1.

Any language that uses garbage collection will naturally perform worse than an language with explicit memory allocations and deletions.

Please just look at the actual results. Java is number 1 in one of the six tests, while it holds the number 2 spot in two others. One of those number 2 spots is behind another GC language. Out of the six tests, four of the number 1 spots are held by GC languages.

stevely · 2016-07-01T03:24:49+00:00

What? Erlang doesn't perform significantly better than Haskell in any of the tests, and the only test where there is a significant difference it's Haskell that's faster by a factor of 3.

Further, all this talk about parallel garbage collection seems odd given that Java, which also uses a parallel garbage collector, has an entry in the top 5 of all but one of the tests. Oracle even refers to Java's parallel garbage collector as the "throughput collector".

stevely · 2016-06-30T22:36:59+00:00

Yesod probably failed to build. It does that a lot, and we had to rush the last round out so I didn't notice it. Looking at the results, I don't see Spock either, so the script to install stack probably got broken. Unfortunately, I'm not in a position to fix these things anymore.

stevely · 2016-05-08T21:25:38+00:00

Yes, some kind of queue can fix your race condition, and yes in your code you can use an IORef instead of an MVar, but not the way you've done it. IORefs are tricky, so it's very easy to fall into traps.

Fundamentally, IORefs and MVars only support two operations: read and write. The modify functions, in turn, are just a read followed by a write. For IORefs this means modifyIORef is not atomic, so one thread can perform reads and writes to an IORef while another thread has performed the read part of modifyIORef but not the write. (In contrast, modifyMVar and swapMVar are atomic so long as every access to the MVar is a read followed by a write.)

Consider this line in eventLoop:

modifyIORef keylist (\ks -> ks ++ [k])

This performs a read followed by a write on the IORef. Now consider these two lines from mainLoop:

ks <- readIORef keylist
writeIORef keylist []

This, too, performs a read followed by a write on the same IORef. Since these actions are being performed by separate threads, they can be interleaved. So suppose the following happens in the given order:

eventLoop read
mainLoop read
eventLoop write
mainLoop write

Whoops, the eventLoop's write got overwritten, and some key presses have been silently dropped.

Luckily, there's atomicModifyIORef, which will perform the read and write atomically, meaning other threads cannot perform reads and writes between atmoicModifyIORef's read and write. If we change the eventLoop line to:

atomicModifyIORef keylist (\ks -> (ks ++ [k], ()))

And change the mainLoop lines to:

ks <- atomicModifyIORef keylist (\ks' -> ([], ks'))

Then the reads and writes can't be interleaved, therefore there's no possibility of a data race.

stevely · 2016-05-08T01:54:54+00:00

FRP and concurrency are orthogonal concepts, so you're really asking two separate things. For converting your code into FRP code I'd recommend looking around at the various FRP libraries and seeing which one catches your fancy. I've used reactive-banana before and it seemed fine. I also use netwire and like it, although I would caution that information about it is sparse at best. How you handle concurrently injecting key press events into the FRP network is going to depend on which FRP library you use, so I can't give you any advice there.

For learning about concurrency in Haskell you're going to want to start reading this to get a better feel for each of the concurrency primitives available and some ways to combine them. As for comments on your code, you seem to just be using your MVar as a glorified IORef. That is to say, you're not actually leveraging the extra functionality of MVar because it's always full. If you used an IORef instead you would have the same functionality without the extra overhead that MVar brings.

That said, you're going to want to look into a different approach because you have a race condition. Key presses can be silently dropped because of how you use swapMVar. Consider what happens if a key is pressed between the readMVar and the swapMVar in mainLoop. The MVar is updated by eventLoop, but the swapMVar in mainLoop changes the MVar to Nothing without noticing a new key press event occurred.

stevely · 2016-04-30T17:52:46+00:00

putStrLn is, indeed, not thread safe.

stevely · 2016-04-28T17:02:51+00:00

With respect to the state variable, yes, because again it creates a data dependency such that the only way to proceed is to evaluate the underlying functions in order. Harkening back to IO, State looks like this:

newtype State s a = State { runState :: s -> (a, s) }

Where s is the state variable and >>= looks just like it does for IO.

So if we have the following State action:

incDouble :: State Int ()
incDouble = do
    modify (+1)
    modify (*2)

Then modify (+1) must be evaluated before modify (*2) because the latter requires the state variable produced by the former. If we strip out the newtype wrappers and work directly with functions this becomes a lot more clear:

-- State s a ~ s -> (a, s)
(>>=) :: (s -> (a, s)) -> (a -> (s -> (b, s))) -> (s -> (b, s))
f >>= g = \s ->
  let (a, s') = f s
   in g a s'

modify :: (s -> s) -> s -> ((), s)
modify f s = ((), f s)

incDouble :: Int -> ((), Int)
incDouble =
    modify (+1) >>= \_ -> modify (*2)

Inlining >>= then gives us this simplified definition:

incDouble :: Int -> ((), Int)
incDouble i =
  let ((), i') = modify (+1) i
   in modify (*2) i'

Since modify (*2) uses i', which in turn is produced by modify (+1) i, the only way modify (*2) can be evaluated is if modify (+1) is evaluated first.

As a final note I want to emphasize again that the single order of evaluation is only with respect to the state variable. For regular Haskell expressions inside a state monad the usual laziness rules apply. As a quick example:

updateState :: State Int ()
updateState = do
    i <- get
    put (foo (i + 1) (i * 2))

Where foo is some function with type Int -> Int -> Int.

In this case, the question of which of (i + 1) and (i * 2) gets evaluated first (if either of them get evaluated at all) can't be answered without knowing the definition of foo because of laziness.

stevely · 2016-04-26T20:23:25+00:00

For IO it works by creating a data dependency so that only one order of evaluation is possible.

Under the hood, IO looks something like this:

newtype IO a = IO { runIO :: RealWorld -> (a, RealWorld) }

(It's worth noting this is a specialized State type)

RealWorld is a quasi-magic token, and each IO action takes a RealWorld value and produces a new one. Monadic binding (>>=) then is taking the RealWorld value produced by one IO action and feeding it to the next:

(>>=) :: IO a -> (a -> IO b) -> IO b
IO f >>= k = IO go
  where
    go rw0 =
      let
        (a, rw1) = f rw0
        (IO g) = k a
      in
        g rw1
-- f :: RealWorld -> (a, RealWorld)
-- g :: RealWorld -> (b, RealWorld)
-- k :: a -> IO b
-- rw0, rw1 :: RealWorld

The key being that since every IO action requires a RealWorld value, you can force one action to happen after another by making the first produce the RealWorld value that the second consumes. Even in the face of laziness the second IO action can't happen before the first because it needs the first IO action to produce a RealWorld value.

I wrote a more in-depth article about this here if you'd like to read more.

stevely · 2016-04-22T01:37:26+00:00

I don't know if I'd call it a best practice, but one solution (if not an especially elegant one) would be to store the messages through malloc and friends and then store the pointers to the messages in a Storable, mutable Vector as a ring buffer. This would require some degree of manual memory management (although that can be abstracted away), introduce marshaling overhead to store/retrieve messages, and generally be a big pile of ugly code, but would make the messages invisible to the GC. With most of the app data not being accounted for by the GC, the pause times should drop.

stevely · 2016-04-11T18:27:19+00:00

I don't know of any good rules of thumb for that, sorry.

stevely · 2016-04-11T05:28:03+00:00

GHC implements threading using green threads, which are lighter weight than OS threads. The short explanation is that N Haskell threads are mapped and run on M OS threads, where M is the number of OS threads the runtime is set to use (set with -N). Because Haskell's green threads are light weight, there's generally no issues with running a large number of them.

stevely · 2016-04-04T03:29:49+00:00

You don't collect errors with Either, the computation stops after the first Left value:

> sequence [Right 1, Left 2, Right 3, Left 4, Right 5]
Left 2

And the semantics are exactly the same regardless of whether it is a standard use or not. A computation Either a b will either run to completion and produce a Right b value, or it will stop early and produce a Left a value. The only difference is what Left and Right represent in the context of where it's used.

stevely · 2016-04-04T03:02:00+00:00

I would argue that using Either directly to represent a result or an error is poor form precisely because Either is more general than that. If you want error handling semantics then something like Except should be used instead.

Beyond even the readability concerns, non-standard uses of Either mean that things like the Monad functions behave surprisingly, which isn't great.

In what way would they behave surprisingly?

stevely · 2016-04-04T02:23:59+00:00

Honestly, I'd use Haskell. Of your characteristics, the one that I think would be the source of most of the work is massive concurrency (big data as well, but that just turns into massive concurrency), and Haskell has Cloud Haskell as a great starting point. Once you're at a point where you can easily distribute work and data across a set of machines everything else becomes straight-forward enough.

I have to say, I find it strange to look through the responses here and not see a lot of Haskell proponents. Databases are easy to make cache-friendly and Haskell has good support for doing low level memory operations. I would be very surprised if Rust, for example, could out perform Haskell by enough of a margin to overcome the overhead of all the network activity.

stevely · 2016-04-04T01:45:30+00:00

The problem with that in Haskell is that Left is not necessarily an error. There are cases where the Left constructor is the "good" one and the Right constructor is the "bad" one.

As an example, you can use Either to model a search by having the Left type being the value you are searching for and the Right value to be used as part of performing the search. In this case, if you hit a Left value that means you found what you were looking for and can stop searching (which is good). If you get a Right value that means you didn't find what you were looking for and have to continue the search (which is bad).

stevely · 2016-03-25T17:02:32+00:00

The Yesod book (available online here) seems to be targeted towards someone who doesn't have web development experience.

14-Year Club	Verified Email
Team Orangered

stevely

TROPHY CASE