Compiling a DSL on the shoulders of GHC
Hello all, I'm trying to reuse as much of the sweat and tear put into GHC as possible to derive a compiler for a language highly similar to Haskell in many aspects. The difference is that instead of constructing an expression of type IO (), the programmer has to provide a stream processor on the top level - whether this is an arrow structure or just a pure function mapping input to output is not decided yet. In other words, I want to allow the programmer to use full Haskell as a metaprogramming language to create an expression of a much more limited language. My idea was to move the relevant types into a module, and make my combinators simple data constructors behind the scene, so the Haskell phase would effectively build an AST. The tricky bit is that I don't necessarily want to make everything an explicit data constructor. For instance, I'd like to allow Haskell functions in the tree. Using the GHC API, I can get the Core representation of the metaprogram. What I'd like at this point is to evaluate the top level expression and still have a representation open to analysis (traversal, pretty printing, interpretation etc.), including lambdas; if this evaluation takes more time than some well-defined limit, I could treat it as a compile-time error. Basically, I want the constant that is the main program to be folded completely if possible during compile time, and signal an error in case it isn't or doesn't seem to be. The resulting structure would be transformed further by a separate application instead of the existing GHC backends. Unfortunately the GHC API is not very approachable for the uninitiated, so it's not clear to me whether this is even possible. Or is it simply such a bad idea that it's not even worth considering in the face of more conventional approaches? Gergely -- http://www.fastmail.fm - Same, same, but different...
On Sun, 17 Oct 2010, Patai Gergely wrote:
I'm trying to reuse as much of the sweat and tear put into GHC as possible to derive a compiler for a language highly similar to Haskell in many aspects. The difference is that instead of constructing an expression of type IO (), the programmer has to provide a stream processor on the top level - whether this is an arrow structure or just a pure function mapping input to output is not decided yet. In other words, I want to allow the programmer to use full Haskell as a metaprogramming language to create an expression of a much more limited language.
And it is not enough to provide just a driver function, that is called in 'main', say run :: IOArrow a b -> a -> IO b ?
And it is not enough to provide just a driver function, that is called in 'main', say run :: IOArrow a b -> a -> IO b ? No, because I need to compile the stream processing program itself by a different tool. I just want to trick GHC into doing much of the weightlifting. No IO monad is involved, by the way, the stream processor is supposed to be a pure transformation.
Gergely -- http://www.fastmail.fm - Or how I learned to stop worrying and love email again
On Sun, Oct 17, 2010 at 12:12 PM, Patai Gergely
And it is not enough to provide just a driver function, that is called in 'main', say run :: IOArrow a b -> a -> IO b ? No, because I need to compile the stream processing program itself by a different tool.
Not sure how this fits into what I thought you were saying. Are you trying to use Haskell to build an AST, use GHC to optimize it, and then spit it out and compile it with, say, a OCaml program that you have already written? Or is your different tool supposed to spit out Haskell and GHC compiles it into a program? Or what? What is this different tool and how does it fit in to your pipeline? Luke
Not sure how this fits into what I thought you were saying. Are you trying to use Haskell to build an AST, use GHC to optimize it, and then spit it out and compile it with, say, a OCaml program that you have already written? Yes, that would be the basic idea:
What is this different tool and how does it fit in to your pipeline? This tool(set) is a specialised compiler for some low-level target
1. Compile the Haskell metaprogram. 2. Evaluate main, possibly with a timeout, in a way that keeps all its structure including lambdas accessible (e.g. Core). 3. Compile the resulting program with other tools. platform (FPGA, DSP, GPU - again, no clear decision yet), and it is the second half of the pipeline after the GHC phases. Gergely -- http://www.fastmail.fm - The professional email service
Fiddling with GHC internals sounds like overkill for this project.
Are you really sure you need a timeout to run the Haskell metaprogram? There
are many implementations of EDSLs which take the approach that you want to
take by using Haskell to create a syntax tree and the offshore it to some
backend compiler. None of them uses a timeout.
But in case you really insist on a timeout I would recommend using a wrapper
function on the toplevel of your metaprogram which implements the timeout.
That way you don't have to risk your sanity by having to dig around in GHC.
Josef
On Sun, Oct 17, 2010 at 9:53 PM, Patai Gergely
Not sure how this fits into what I thought you were saying. Are you trying to use Haskell to build an AST, use GHC to optimize it, and then spit it out and compile it with, say, a OCaml program that you have already written? Yes, that would be the basic idea:
1. Compile the Haskell metaprogram. 2. Evaluate main, possibly with a timeout, in a way that keeps all its structure including lambdas accessible (e.g. Core). 3. Compile the resulting program with other tools.
What is this different tool and how does it fit in to your pipeline? This tool(set) is a specialised compiler for some low-level target platform (FPGA, DSP, GPU - again, no clear decision yet), and it is the second half of the pipeline after the GHC phases.
Gergely
-- http://www.fastmail.fm - The professional email service
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
There are many implementations of EDSLs which take the approach that you want to take by using Haskell to create a syntax tree and the offshore it to some backend compiler. None of them uses a timeout. The difference is that they implement all the transformations after the parsing phase, and there are no Haskell functions or arbitrary data types in the syntax tree (unless we bring generics into the picture).
But in case you really insist on a timeout I would recommend using a wrapper function on the toplevel of your metaprogram which implements the timeout. That way you don't have to risk your sanity by having to dig around in GHC. Of course, as soon as I give everything an explicit representation, this part of the story is straightforward.
Gergely -- http://www.fastmail.fm - Accessible with your email software or over the web
I have nearly the same plan: I want to compile a restrictive form of Haskell to constant time and space C code for hard realtime embedded targets. Except I need a top level monad with different semantics than IO. Which language is that? ImProve?
Wouldn't a fake driver (fakeRun :: Something -> IO ()) at least simplify the problem? It would prevent you from having to modify GHC to handle a different top level type. And during your evaluation of Core, you would simply ignore fakeRun. I'm not really bothered about the type of main, since I can always just pick a different unused name for my entry point. In fact, that would allow me to compile programs both as normal executables for functional testing (using your fake driver solution) and still pass the Core to the rest of the pipeline.
Gergely -- http://www.fastmail.fm - Email service worth paying for. Try it for free
On Tue, Oct 19, 2010 at 7:54 AM, Patai Gergely
I have nearly the same plan: I want to compile a restrictive form of Haskell to constant time and space C code for hard realtime embedded targets. Except I need a top level monad with different semantics than IO. Which language is that? ImProve?
No. It would be something STMish, similar to Atom. -Tom
So in the result of (a >>= f), the first element is taken from the first element of applying f to the first element of a; the second element is the second element in the result of applying f to the second element of a; and so on. Off the top of my head I am not sure what this corresponds to in terms of agents or where it would be useful, but I'm sure it must correspond to something interesting. In short, join corresponds to continuously sampling a stream of streams. In other words, it turns a higher-order stream into a dynamic data-flow network. That's exactly what the Elerea library [1] is good for: it allows you to do this in constant time instead of the quadratic cost of the pure implementation, but it forces you to traverse streams sequentially -- fortunately, that's exactly what you want to do most of the time. There is also a paper behind the library, which might help a bit in getting a clearer picture [2] (the paper also has an updated version in the process of being published).
Gergely [1] http://hackage.haskell.org/package/elerea [2] http://sgate.emt.bme.hu/documents/patai/publications/PataiWFLP2010.pdf -- http://www.fastmail.fm - One of many happy users: http://www.fastmail.fm/docs/quotes.html
Patai, I read your paper on Elerea. It wasn't easy :), but I think I got the
picture.
So I would have 2 questions :
I made a simple function which turns an infinite list into a signal :
fromList :: [a] -> SignalGen (Signal a)
fromList xs =
stateful xs tail >>= memo . fmap head
1) It does what I want, but is it the good way to do it?
2) Since the returned signal may be used in several places and since I
obtain it through the generic fmap (and not through an Elerea primitive), I
guessed I had to "memo" it instead of simply using "return". Did I guess
right?
3) Concerning the functionnality added by the Param implementation, I have
the impression that the same can be achieved through the use of an external
signal in Simple (*). Am I right? If so, why did you make the Param
alternative?
(*) (ext, sink) <- external 'a'
driver <- start $ someSigGen ext
sink 'b'
driver
sink 'c'
driver
sink 'd'
driver
etc...
2010/12/16 Patai Gergely
So in the result of (a >>= f), the first element is taken from the first element of applying f to the first element of a; the second element is the second element in the result of applying f to the second element of a; and so on. Off the top of my head I am not sure what this corresponds to in terms of agents or where it would be useful, but I'm sure it must correspond to something interesting. In short, join corresponds to continuously sampling a stream of streams. In other words, it turns a higher-order stream into a dynamic data-flow network. That's exactly what the Elerea library [1] is good for: it allows you to do this in constant time instead of the quadratic cost of the pure implementation, but it forces you to traverse streams sequentially -- fortunately, that's exactly what you want to do most of the time. There is also a paper behind the library, which might help a bit in getting a clearer picture [2] (the paper also has an updated version in the process of being published).
Gergely
[1] http://hackage.haskell.org/package/elerea [2] http://sgate.emt.bme.hu/documents/patai/publications/PataiWFLP2010.pdf
-- http://www.fastmail.fm - One of many happy users: http://www.fastmail.fm/docs/quotes.html
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
fromList :: [a] -> SignalGen (Signal a) fromList xs = stateful xs tail >>= memo . fmap head
1) It does what I want, but is it the good way to do it? Yes, I'd do it the same way, assuming that the input is always an infinite list (so this version should probably be called unsafeFromList...). But you can always make a list infinite, just add a Maybe layer or pad with a default value.
2) Since the returned signal may be used in several places and since I obtain it through the generic fmap (and not through an Elerea primitive), I guessed I had to "memo" it instead of simply using "return". Did I guess right? That's exactly what memo is needed for, yes. However, whether it is worth the overhead in such a simple case (after all, head is essentially just a single dereferencing step) should be determined by profiling.
3) Concerning the functionnality added by the Param implementation, I have the impression that the same can be achieved through the use of an external signal in Simple (*). Am I right? Yes, the two are equally expressive. The difference is the way you access the signals. In the case of Param, you get a globally accessible signal that you don't need to pass around explicitly, just retrieve with 'input' wherever you want. This might be useful when there's some ubiquitous piece of information that you need practically everywhere, e.g. real time for a simulation.
Gergely -- http://www.fastmail.fm - Does exactly what it says on the tin
Thanks for your answers. In fact I tried to use Simple with a clock signal
and it's painful to pass it wherever you need it. Param is much more
practical.
I like Elerea, I tried Reactive and Yampa, and I found them (especially
Yampa) heavy and not very practical.
The fact that Elerea is minimalistic makes it easier to learn/use and more
flexible.
2010/12/23 Patai Gergely
fromList :: [a] -> SignalGen (Signal a) fromList xs = stateful xs tail >>= memo . fmap head
1) It does what I want, but is it the good way to do it? Yes, I'd do it the same way, assuming that the input is always an infinite list (so this version should probably be called unsafeFromList...). But you can always make a list infinite, just add a Maybe layer or pad with a default value.
2) Since the returned signal may be used in several places and since I obtain it through the generic fmap (and not through an Elerea primitive), I guessed I had to "memo" it instead of simply using "return". Did I guess right? That's exactly what memo is needed for, yes. However, whether it is worth the overhead in such a simple case (after all, head is essentially just a single dereferencing step) should be determined by profiling.
3) Concerning the functionnality added by the Param implementation, I have the impression that the same can be achieved through the use of an external signal in Simple (*). Am I right? Yes, the two are equally expressive. The difference is the way you access the signals. In the case of Param, you get a globally accessible signal that you don't need to pass around explicitly, just retrieve with 'input' wherever you want. This might be useful when there's some ubiquitous piece of information that you need practically everywhere, e.g. real time for a simulation.
Gergely
-- http://www.fastmail.fm - Does exactly what it says on the tin
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Hello,
I keep on experimenting with Elerea. I'm on my way to achieve a simple Pong
game, but the display is awfully jerky, however the sampling occurs on
average every 0,0015 sec, which gives 670 FPS.
All the elerea-examples run perfectly fine on my computer, however I use
FRP.Elerea.Param, which none of the examples use. But there isn't no known
problem with Param?
(Even if it's much more likely it comes from my code...)
2010/12/23 Yves Parès
Thanks for your answers. In fact I tried to use Simple with a clock signal and it's painful to pass it wherever you need it. Param is much more practical. I like Elerea, I tried Reactive and Yampa, and I found them (especially Yampa) heavy and not very practical. The fact that Elerea is minimalistic makes it easier to learn/use and more flexible.
2010/12/23 Patai Gergely
fromList :: [a] -> SignalGen (Signal a)
fromList xs = stateful xs tail >>= memo . fmap head
1) It does what I want, but is it the good way to do it? Yes, I'd do it the same way, assuming that the input is always an infinite list (so this version should probably be called unsafeFromList...). But you can always make a list infinite, just add a Maybe layer or pad with a default value.
2) Since the returned signal may be used in several places and since I obtain it through the generic fmap (and not through an Elerea primitive), I guessed I had to "memo" it instead of simply using "return". Did I guess right? That's exactly what memo is needed for, yes. However, whether it is worth the overhead in such a simple case (after all, head is essentially just a single dereferencing step) should be determined by profiling.
3) Concerning the functionnality added by the Param implementation, I have the impression that the same can be achieved through the use of an external signal in Simple (*). Am I right? Yes, the two are equally expressive. The difference is the way you access the signals. In the case of Param, you get a globally accessible signal that you don't need to pass around explicitly, just retrieve with 'input' wherever you want. This might be useful when there's some ubiquitous piece of information that you need practically everywhere, e.g. real time for a simulation.
Gergely
-- http://www.fastmail.fm - Does exactly what it says on the tin
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
I keep on experimenting with Elerea. I'm on my way to achieve a simple Pong game, but the display is awfully jerky, however the sampling occurs on average every 0,0015 sec, which gives 670 FPS. I had a similar experience under Windows. Never really got to find out why it happened. You might try adding a short threadDelay call in your main loop and see what happens; I think it helped back then.
All the elerea-examples run perfectly fine on my computer, however I use FRP.Elerea.Param, which none of the examples use. But there isn't no known problem with Param? Haven't heard of any. Note that Param is essentially the same as combining the Simple variant with a reader monad layer, so it shouldn't affect the basic operation of the library.
Gergely -- http://www.fastmail.fm - Same, same, but different...
I had a similar experience under Windows. Never really got to find out why it happened. You might try adding a short threadDelay call in your main loop and see what happens; I think it helped back then.
Wow... it's even worse. Even with a threadDelay of 1ms the FPS drop down to a chaotic 20~30. I forgot to say: I run Ubuntu 10.10 (32bits), and I use HGL for the graphics, not GLFW. This may be important since HGL seems to react badly to threadDelay (The application simply blocks if there are no key pressed or mouse moved), so maybe the original problem comes from it. This is my main loop : mainLoop :: H.Window -> (Input -> IO (H.Graphic, Bool)) -> Time -> IO () mainLoop win driver elapsed = do clk <- mkClock threadDelay 1000 -- in microseconds events <- whileJust (H.maybeGetWindowEvent win) return (graphic, continue) <- driver $ Input elapsed events H.setGraphic win graphic when continue $ do el <- clk print $ round $ 1/el mainLoop win driver el Where data Input = Input Data.Time.Clock.NominalDiffTime [H.Event] mkClock generates an IO action that, when evaluated, gives the time elapsed since mkClock.
Note that Param is essentially the same as combining the Simple variant with a reader monad layer, so it shouldn't affect the basic operation of the library.
Okay. It wasn't very likely the problem came from it.
2010/12/26 Patai Gergely
I keep on experimenting with Elerea. I'm on my way to achieve a simple Pong game, but the display is awfully jerky, however the sampling occurs on average every 0,0015 sec, which gives 670 FPS. I had a similar experience under Windows. Never really got to find out why it happened. You might try adding a short threadDelay call in your main loop and see what happens; I think it helped back then.
All the elerea-examples run perfectly fine on my computer, however I use FRP.Elerea.Param, which none of the examples use. But there isn't no known problem with Param? Haven't heard of any. Note that Param is essentially the same as combining the Simple variant with a reader monad layer, so it shouldn't affect the basic operation of the library.
Gergely
-- http://www.fastmail.fm - Same, same, but different...
I forgot to say: I run Ubuntu 10.10 (32bits), and I use HGL for the graphics, not GLFW. This may be important since HGL seems to react badly to threadDelay Oh, HGL! The Yampa Arcade example (SpaceInvaders) suffered from the same problem, and it was solved by adding the -threaded switch. Without it, the program wouldn't advance in the absence of user events, just like in your case.
Gergely -- http://www.fastmail.fm - One of many happy users: http://www.fastmail.fm/docs/quotes.html
Yes, that would be the basic idea:
1. Compile the Haskell metaprogram. 2. Evaluate main, possibly with a timeout, in a way that keeps all its structure including lambdas accessible (e.g. Core). 3. Compile the resulting program with other tools.
What is this different tool and how does it fit in to your pipeline? This tool(set) is a specialised compiler for some low-level target platform (FPGA, DSP, GPU - again, no clear decision yet), and it is the second half of the pipeline after the GHC phases.
I have nearly the same plan: I want to compile a restrictive form of Haskell to constant time and space C code for hard realtime embedded targets. Except I need a top level monad with different semantics than IO. Wouldn't a fake driver (fakeRun :: Something -> IO ()) at least simplify the problem? It would prevent you from having to modify GHC to handle a different top level type. And during your evaluation of Core, you would simply ignore fakeRun. -Tom
participants (6)
-
Henning Thielemann -
Josef Svenningsson -
Luke Palmer -
Patai Gergely -
Tom Hawkins -
Yves Parès