April 2009 - Haskell-Cafe

Recommending "Design concepts in programming languages"
by Eugene Kirpichov 14 May '09

14 May '09

Hi. To all those people who are in any sense interested in PL theory I'd like to recommend the book "Design concepts in programming languages", because I am extremely impressed with it and because I, surprisingly, have not heard much about it. So, the book is about various concepts encountered in various kinds of programming languages: denotational and operational (BOS/SOS) semantics, issues of state and control, type systems, modules, modeling effects and compilation. Every concept is introduced by defining the semantics of a language that has this concept and exploring the design dimensions and issues of this concept and language. Concepts are gradually accumulated, and by the time you reach the chapter on modules you've got a CBV language with records, mutable state, polymorphic algebraic data types, a System F type system with type inference and a hint of dependent types, abstract data types and first-class dynamically loadable modules. The tools used for description are of course the good old denotational and operational semantics and typing judgements and derivation trees; but each element of those is clearly and succintly described in text; it happens to me all the time that I am reading a type reconstruction algorithm and wondering, "why does this rule have that restriction?" and it immediately turns out that in the next paragraph, the authors focus attention on why this rule has that restriction; just like if they were reading my thoughts. That's why this book feels very comfortable to me: I am absolutely sure that I won't encounter a point where I am lost and buried under the notation; but there is also not a single boring moment. I've been interested in functional programming and PL theory for 2-3 years already, and here's a brief list of the *new* things that I have learned, at least: - What do SOS and BOS mean, and why one should care, and what properties a SOS might posess (confluence and normalization, for instance) - How many features of languages can be defined in terms of simply desugaring, and how in some cases they can't - How one might use monadic style in the semantics metalanguage to greatly simplify the semantic rules for monadic concepts like state, control and error handling (the authors mention the word "monad" only once, but they use return- and bind-like operators in their semantics) - How powerful records are, and of what use are operators like "conceal" - What use is subtyping outside of OOP - How does one define CPS-style semantics and how such a style allows to add state, control and errors with minimal changes - How small yet powerful an OOP language core can be - How algebraic datatypes can be very useful in a language without static typing - How pattern matching can be desugared into CPS-style deconstructors - How many caveats are there in defining typing rules, and how a small change in them can lead to very big changes in language expressiveness - How HM type inference actually works - Why purity is important for certain polymorphism issues - What let-polymorphism means - What effect systems are - How effect reconstruction works and how it is different from type reconstruction in nature - How effect inference can prove the external purity of certain internally impure programs That's where I finished my reading for now. The remaining looks even more intriguing; for example, I don't (yet) know how functional languages are compiled and how register allocation is done. I'm afraid to sound like a salesman, but this is absolutely the best-written technical book I have ever seen in my life, and probably the most influential one for me, excluding probably SICP. Here you can check out its table of contents: http://cs.wellesley.edu/~fturbak/pubs/6821/current/contents-nov22.pdf I was impressed with the TOC even before buying the book, but turned out that I was greatly under-estimating it. Well, that's it :) -- Eugene Kirpichov Web IR developer, market.yandex.ru

8 12

ANN: priority-sync-0.1.0.1: Cooperative task prioritization.
by Christopher Lane Hinson 13 May '09

13 May '09

http://hackage.haskell.org/cgi-bin/hackage-scripts/package/priority-sync $ cabal install priority-sync git clone http://www.downstairspeople.org/git/priority-sync.git Feedback will be greatly appreciated. This package is a spin-off from my work on roguestar, where I need to do significant background processing while retaining enough resources to perform smooth animation. The following is the front-page documentation for the package. In a simple use case, we want to run some expensive tasks in prioritized order, so that only one task is running on each CPU (or hardware thread) at any time. For this simple case, four operations are needed: simpleTaskPool, schedule, claim, and startQueue. let expensiveTask = threadDelay 1000000 pool <- simpleTaskPool forkIO $ claim Acquire (schedule pool 1) $ putStrLn "Task 1 started . . ." >> expensiveTask >> putStrLn "Task 1 completed." forkIO $ claim Acquire (schedule pool 3) $ putStrLn "Task 3 started . . ." >> expensiveTask >> putStrLn "Task 3 completed." forkIO $ claim Acquire (schedule pool 2) $ putStrLn "Task 2 started . . ." >> expensiveTask >> putStrLn "Task 2 completed." threadDelay 100000 -- contrive to wait for all tasks to become enqueued putStrLn "Starting pool: " startQueue pool threadDelay 4000000 -- contrive to wait for all tasks to become dequeued A TaskPool combines Rooms and Queues in an efficient easy-to-use-interface. Rooms provide fully reentrant synchronization to any number of threads based on arbitrary resource constraints. For example, the Room from a simpleTaskPool is constrained by GHC.numCapabilities. Queues provide task prioritization. A Queue systematically examines (to a configurable depth) all waiting threads with their priorities and resource constraints and wakes the most eagerly prioritized thread whose constraints can be satisfied. TaskPools are not thread pools. The concept is similar to IO Completion Ports. There are no worker threads. If a number of threads are waiting, the thread that is most likely to be processed next is woken and temporarily serves as a working thread. Rooms, Queues, and TaskPools are backed by carefully written STM (software transactional memory) transactions. A salient feature is that, because any thread can participate, a TaskPool supports both bound threads and threads created with forkOnIO. Friendly, --Lane

2 2

ANN: atom-0.0.2
by Tom Hawkins 05 May '09

05 May '09

Atom is a DSL in Haskell for designed hard realtime embedded programs. At Eaton, we are using it to control hydraulic hybrid refuse trucks and shuttle buses. After my talk at CUFP (http://cufp.galois.com/2008/schedule.html) a few people inquired about atom -- I finally had a chance to upload it to Hackage. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/atom-0.0.2 Some new enhancements: - A simple rule scheduler for load balancing. - Signal probing for debug and data logging. - Functional coverage to monitor which rules have executed. - Started integration with the Yices SMT solver for bounded model checking. Experiences with our Eaton project: - 5K lines of Haskell/atom replaced 120K lines of matlab, simulink, and visual basic. - 2 months to port simulink design to atom. - 3K lines of atom generates 22K lines of embedded C. - Design composed of 450 atomic state transition rules. - Rules with execution periods from 1ms to 10s all scheduled at compile time to a 1 ms main loop. - 3 minute compilation time from atom source to ECU. - Atom design clears electronic/sw testing on first pass. - Currently in vehicle testing with no major issues. Tom

3 3

Dynamically altering sort order
by Denis Bueno 02 May '09

02 May '09

Hi all, Suppose I have the following interface to a sorting function: sort :: (Ord a) => [a] -> IO [a] -- sort large, on-disk array of records but I don't have a sortBy where you can simply pass a compare function. Wrapped around this is a command-line program which should allow the user to specify different orderings on Records. For example, if the Record has three fields, the user should be able to say "sort only on the first two". Is there an Ord instance that can be dynamically changed in this way? My first idea is something like this: data CompareRecord = CR{ rCompare :: Record -> Record -> Ordering, unCR :: Record } instance Ord CompareRecord where compare (CR cmp x) (CR _ y) = cmp x y where the rCompare field would be a function that is based on the flags passed to the command-line problem. But this has an ugly asymmetry. Does anyone have any other ideas? Thanks. Denis

4 6

Runge-Kutta and architectural style
by Richard O'Keefe 02 May '09

02 May '09

I was interested to see a Runge-Kutta package posted to this list recently, particularly as I have a fairly simple-minded non-adaptive RK "generator": an AWK script that takes a table and some optional stuff and spits out C. The Haskell package is, of course, a lot prettier than my AWK program, as well as offering some adaptive methods, which is important. We can imagine a spectrum of RK packages: (1) Higher order function taking some runtime parameters. That's what we got. (2) The same specialised for a known table at compile time. Doable using the code that we were given plus SPECIALIZE pragmas. I don't how well that works across modules. (3) A generator that writes Haskell source. (4) Template Haskell. (5) A generator that generates native code to be called through FFI. The question is, how do you decide what's the appropriate approach?

3 2

swish - semantic web in Haskell
by Vasili I. Galchin 02 May '09

02 May '09

Hello, http://www.ninebynine.org/Software/swish-0.2.1.html .... I am trying to get permission from the author of Swish to move it into Hackage. I will write "cabalize" it get up to current Haskell standards. Before I go to this effort is anybody attempting to do this? Kind regards, Vasili

3 3

Thread priority?
by Christopher Lane Hinson 01 May '09

01 May '09

Is there any interest or movement in developing thread priority or any other realtime support in Haskell? Right now, if I have tasks that need to be responsive in real time, even if the realtime needs are very soft, it seems that the only option is to try to ensure that at least one hardware thread is kept clear of any other activity. To be very useful to me, thread priority would not need to come with very strict guarantees, but there would need to be a way to make sure that `par` sparks and DPH inherit the priority of the sparking thread. In part I ask because I'm working on a small library to support a degree of cooperative task prioritization. Friendly, --Lane

6 7

How to install HOpenGL to Windows?
by Alexandr N. Zamaraev 30 Apr '09

30 Apr '09

I get darcs source HOpenGL Try runghc Setup.hs configure I see: Configuring OpenGL-2.3... Warning: The 'build-type' is 'Configure' but there is no 'configure' script. Setup.hs: configure script not found. runghc Setup.hs build wrote: Preprocessing library OpenGL-2.3... Building OpenGL-2.3... Graphics\Rendering\OpenGL\GL\BasicTypes.hs:24:0: HsOpenGLConfig.h: No such file or directory How to build HOpenGL? Os Windows Vista Home Ru + sp ghc 6.10.1

7 13

Google SoC: Space profiling reloaded
by Patai Gergely 30 Apr '09

30 Apr '09

Hello all, I'm one of the lucky individuals accepted for this year's Summer of Code. Here's the abstract of my proposal: http://socghop.appspot.com/student_project/show/google/gsoc2009/haskell/t12… There's less than a month left before I'm supposed to jump into coding, and I'd love to hear about any little idea you think would make this project even better! I created a project page with a rough draft of what I intend to concentrate on, but the issue tracker is obviously begging for content, so feel encouraged to populate it. :) http://code.google.com/p/hp2any/ I also intend to expand the description later. Gergely -- http://www.fastmail.fm - The professional email service

2 1

Arrow preprocessor and *** combinator
by Peter Verswyvelen 30 Apr '09

30 Apr '09

After doing some pragmatic tests, it seems that neither the arrow preprocessor nor GHC's builtin one generate / optimize to the (***) combinator. For example, p = proc (x,y) -> do x' <- f <- x y' <- g <- y return (x',y') is equivalent to p = f *** g But I have the impression this kind of rewrites is not being done? Is it possible to provide rewrite rules for arrows? Since *** is a method of the arrow type class, it might have a more optimal implementation. I haven't looked at the arrow preprocessor or GHC's code yet, but comments are welcome, I might see things wrongly. Cheers, Peter

3 4