May 2011 - Haskell-Cafe

Hackage build failure
by Jonas Almström Duregård 10 May '11

10 May '11

Hi, Is there something wrong with the Hackage build system? It fails to build BNFC-meta: http://hackage.haskell.org/package/BNFC-meta It complains about a missing dep even though it (the dependency) has been built successfully. Also the dependencies are exactly the same as in the previous version (which configures fine but fails to build because of some bug in HsColor). Regards Jonas

2 1

Re: [Haskell-cafe] [Haskell] ANN: syntactic-0.1
by Emil Axelsson 10 May '11

10 May '11

2011-05-10 15:31, Heinrich Apfelmus skrev: >>> I'm also unhappy about some of the boilerplate. For instance, have a >>> look at the function goE in compileAccumB (line 210), it's just a >>> generic applicative traversal through the data type. >> >> Most likely, this boilerplate could be simplified using syntactic. > > Hm, does the boilerplate get removed or only simplified? I was hoping > that one could use a completely generic traversal; but is that actually > the case? I was using careful wording :) I think the traversal can be completely generic. But syntactic brings its own (constant) overhead, so I felt the word "remove" might be too strong. > On closer inspection, I'm discovering another issue, namely the need for > the Typeable class. This is quite unfortunate, because it would mean > that I won't be able to make an API built on type classes like Functor > or Applicative. Some discussion on that can be found at the end of > > http://apfelmus.nfshost.com/blog/2011/04/24-frp-push-driven-sharing.html Hm... The only reason (afair) for having Typeable constraints in the tree was that my code motion transform (not yet released) needs to move around nodes in a way that the type checker is not happy with. But as long as my algorithm is correct, the type casts will actually always succeed. So it might be possible to use unsafeCoerce directly and get rid of Typeable. There might also be ways to make Typeable optional... I will look into this. > So, it looks like I can't make use of syntactic at the moment. Then > again, my library is probably one of the strongest tests of expressivity > for endeavors like syntactic , so that's fine. Another example of > similar difficulty would be D. Swierstra's recent parser/grammar > combinators that can handle left-recursive grammars. Once syntactic > can deal with those, you're the king! :) Thanks for the tip! It would be interesting to try out these libraries for real, if only for the sake of getting to know the practical limits of syntactic. But my focus is currently on the Feldspar implementation, so I probably won't have time for things like this in a (long) while. / Emil

1 0

An update on ICFP'11 in Tokyo (September 18-24, 2011)
by Wouter Swierstra 10 May '11

10 May '11

Given the fairly recent severe earthquake and tsunami in Japan, you may wonder how this affects the preparations for ICFP'11 in Tokyo. Luckily, Tokyo was significantly less affected by these saddening events than the regions further north. In fact, the situation in Tokyo is almost back to normal, after only two months, with another four months until ICFP. Moreover, all major embassies have in the meantime lifted their travel advisories for the Tokyo metropolitan region (while they still maintain active advisories for some other regions.) Our local organisational team has completed major parts of the preparations and recently summarised the most important facts on a local information page for ICFP'11: http://www.biglab.org/icfp11local/index.html The main conference site is at http://www.icfpconference.org/icfp2011/ We are looking forward to seeing you in Tokyo in September! Manuel Chakravarty Zhenjiang Hu (General Chairs of ICFP'11)

1 0

Template Haskell reified type.
by Serguey Zefirov 10 May '11

10 May '11

Language.Haskell.TH.Type contains, among others, two constructors: TupleT Int and ListT. I can safely construct types using them, but reification returns ConT "GHC.Tuple.(,)" and ConT "GHC.Types.[]" respectively. This is not fair asymmetry, I think. Also, it took purity from one of my functions while I debugged that problem. I had to make it into Q monad. ;)

2 2

Locking, unsafePerformIO and bolt-on thread safety.
by Jason Dusek 10 May '11

10 May '11

A friend is making bindings to a C library that offers some fast math operations. The normal way to use the library is like this: int a = ...; int b = ...; int c = ...; int d = ...; int x = ...; int m, n; create_lookup_table(x); m = perform_math(a, b, x); n = perform_math(c, d, x); We see that the lookup table for x must be created before we can perform math in the field/ring/what-have-you defined by x. Once we have created the table, though, we're done. My friend would like to create a pure interface to this library. One thought was to write an interface to perform_math that checked if the table was created, created it if not, and did all this while locking an MVar so that no other instance could be called at the same time, trashing the table. Doing this behind unsafePerformIO would seem to be the ticket. We end up with an implementation like this: module FastMath where import Control.Concurrent import Foreign import Foreign.C foreign import ccall create_lookup_table :: CInt -> IO () foreign import ccall perform_math :: CInt -> CInt -> CInt -> IO CInt masterLock = unsafePeformIO (newMVar [CInt]) safe_perform_math a b x = do list <- takeMVar masterLock toPut <- if not (x `elem` list) then do create_lookup_table x return (x:list) else return list result <- perform_math a b x putMVar masterLock toPut return result performMath a b x = unsafePerformIO (safe_perform_math a b x) This does not compile but I think it gets the point across. Is this approach safe? The unsafePerformIO in conjunction with locking has me worried. -- Jason Dusek () ascii ribbon campaign - against html e-mail /\ www.asciiribbon.org - against proprietary attachments

2 1

Re: [Haskell-cafe] Asynchronous Arrows need Type Specialization - Help!
by Paul L 10 May '11

10 May '11

I now understand where you are coming from, but I don't quite get your motivation to develop new classes for arrows. Tupling is Haskell is of course very lazy, it does not evaluate any of its element. As for the spatial and logical concepts, don't you think they are over-specifying what is really necessary for your system model? So I guess what I'm having trouble with is your arr f example. If f is sufficiently lazy, it does not evaluate the elements in its input tuple at all. Most pure functions we use to wire up arrows are like this: arr fst, arr snd, arr swap, arr (\x -> (x, x)), etc. I also don't quite follow your example of passing a time stamp together with value. Do you intend to keep the time stamp always updated? If you are getting unwanted results, it is perhaps due to wrong computation, rather than the composition to a pure functions. Maybe you want to give a specific example of "f". Regards, Paul Liu On Fri, Apr 1, 2011 at 1:55 PM, David Barbour <dmbarbour(a)gmail.com> wrote: > On Fri, Apr 1, 2011 at 11:47 AM, Paul L <ninegua(a)gmail.com> wrote: >> On Sun, Mar 20, 2011 at 10:18 PM, David Barbour <dmbarbour(a)gmail.com> wrote: >> >>> The (***) and (&&&) operations, as specified in Control.Arrow, are >>> inherently synchronization points. >>> >>> Ideally one could do something like: >>> >>> (a1 *** a2) >>> first a3 >>> >>> and the output from a1 would be piped directly as input to a3, without >>> touching a2. However, arrows also allow: >>> >>> (a1 *** a2) >>> arr f >>> >>> And, in this case, the current state of a1 and a2 must be combined >>> into a stream of pairs so that f may be mapped over the stream. >>> Obtaining both streams at a single place (a single vat) and time is a >>> synchronizing operation. The synchronization operations are severely >>> undermining the intended scalability and performance of this agent >>> abstraction. >> >> If what you mean by "synchronization" is that for every output of a1 >> there must be an output of a2, then YES. >> >> But if you mean that both the outputs of a1 and a2 have to be >> available (fully evaluated) due to the tupling, then NO, at least not >> in Haskell where things are evaluated lazily. > > What I mean by synchronization is that the outputs from a1 and a2 must > occur at the same logical or physical space and time. > > Assume 'a1' and 'a2' represent external, asynchronous resources. > * 'a1' loads a file, with latency 40 milliseconds. (input is filename) > * 'a2' is a database query, with a latency of 100 milliseconds. (input is query) > > (a1 *** a2) both loads a file and performs a query, then tuples the > results as (r1,r2). > > (a1 *** a2 >>> first a3) further processes the file state r1, > generating (r3,r2). > > Logically, a pair is a spatial-temporal concept: if you have a pair, > you have access to a fst and a snd value at the same place and the > same time. This synchronization is obvious if you pass values into an > 'arr' arrow. The 'physical' synchronization issue is that the naive > way to implement (a1 *** a2) is to wait for both resources to be > available (time) in the same thread (space), then generate a tuple > that couples the responses. > > For my programming model, however, I must avoid both forms of > synchronization. The 'logical' synchronization is minimized. You might > model this, roughly, by pairing the responses with their latencies: > ((40,r1),(100,r2)). This would essentially be a 'futures' passing > style. The idea is that '(a1 *** a2) >>> first a3' might generate > something like ((80,r3),(100,r2)). Explicit synchronization might > bring this to ((100,r3),(100,r2)). > > Futures passing might work well enough for the problem as I've > explained it to you. My programming model is operating under several > additional constraints to support reactivity, concurrency, > parallelism, scalability, distribution, and open systems. Under the > more stringent requirements, I've been unable to make futures fit the > problem. However, in the time since my last Haskell-cafe post, I have > found a way to leverage GADTs to at least keep elements of a product > distinct under-the-hood and minimize physical synchronization. > > data A a d r where > Aprim :: a d r -> A a d r > Aid :: A a r r > Acomp :: A a d' r -> A a d d' -> A a d r > Aarr :: (d -> r) -> A a d r > Aprod :: A a d r -> A a d' r' -> A (a,a') (d,d') > Adup :: A a (a,a) > Afst :: A a (b,c) b > Asnd :: A a (b,c) c > ... > >> >> BTW, according to arrow laws, (a1 *** a2) >>> first a3 is equivalent >> to (a1 >>> a3) *** a2, does the latter look more appealing to you? If >> yes, I don't see where is the problem, unless you intentionally want >> to make them different, and then it is no longer arrow. > > While both expressions should have equivalent observable properties, > neither Haskell nor Arrow laws assure they will possess the same > operational characteristics. In a naive implementation, the latter > will generally be the more efficient option. > > For efficiency reasons, I have also abandoned Ross's Control.Arrow. > The main problem with it is Ross's use of pragmas: > > {-# RULES > "first/arr" forall f . first (arr f) = arr (first f) > "second/arr" forall f . second (arr f) = arr (second f) > "product/arr" forall f g . arr f *** arr g = arr (f *** g) > "fanout/arr" forall f g . arr f &&& arr g = arr (f &&& g) > #-} > > These rules go the wrong direction, making the program more opaque to > the runArrow operation, and actually change both the physical and > logical synchronization characteristics for the worse. I.e. if I pass > ((80,r3),(100,r2)) to 'arr f', the output becomes available at logical > time 100 rather than time 80. > > Peter Gammie suggested use of Adam Megacz's Generalized Arrows, which > would avoid this problem by use of an opaque product type that can > only be converted to a pair by an explicit operation (i.e. 'synch :: a > (b**c) (b,c)' for opaque product type (**)). I'm still debating > whether to take this approach. > -- Regards, Paul Liu

2 1

Type-class conditional behavior
by Nicholas Tung 09 May '11

09 May '11

Dear all, I'd like to write a function "maybeShow :: a -> Maybe String", which runs "show" if its argument is of class Show. The context and motivation for this are as follows. I have a GADT type which encapsulates abstract-value computation (or constants or error codes), a snippet of which is below. data AV t where AVLeft :: AV a -> AV (Either a b) This is used to implement an arrow transformer, and due to Arrows mapping all Haskell functions, I cannot put some kind of qualification on the constructor, like "AVLeft :: Show a => ...". Of course any replies are welcome, but I do need something implemented and stable. If there are GHC-compatible hacks, even an "unsafeShow :: a -> String", that'd be great. I'd also prefer not to branch on all types which could possibly be maybeShow's argument. (Concretely, if I have "newtype AVFunctor a b c = AVF (a (AV b) (AV c))", then the Arrow class declaration forces all types, c.f. variable b, to be potential variables of type AV), class (Category a) => Arrow a where arr :: (b -> c) -> a b c Thanks very much, Nicholas — https://ntung.com — CS major @ UC Berkeley p.s. I posted this question on StackOverflow if you care to get brownie points there, http://goo.gl/PrmYW p.s. 2 -- if there is a general "dump var" function in ghci, which does more than ":info", I'd love to know :)

6 6

Using Haskell to describe computer hardware.
by Serguey Zefirov 09 May '11

09 May '11

http://thesz.mskhug.ru/svn/hhdl/ - main repository and http://thesz.mskhug.ru/svn/hhdl/examples/Simple.hs - three simple examples and http://thesz.mskhug.ru/svn/hhdl/MIPS-example/ - an attempt to describe MIPS-alike CPU using Haskell. Not yet done, it passes only simplest of tests (it fetches commands), but if you take a look at it you'll get an idea of what is going on. The goal is to create something along the lines of Bluespec, but as a DSeL in Haskell. Right now I concentrate on single-clock circuits, as they comprise most of hardware logic. I hacked together transformation of not-so-complex Haskell function definition into Haskell functions that operate on infinite streams. Of course, I tried my best to support calling other functions, conditional operators, pattern matching, etc, because that's what makes Haskell great and Bluespec has them too. Below is little explanation of three simple examples. First comes very simple function: $(transform [d| f1 :: (ToWires a, Num a) => (a,a) -> a f1 (a,b) = a + b |]) After $(transform ...) you will have two functions: f1 and f1_S, the second one operates on streams. ToWires class in the context ensure that input and output values can be converted into arrays of bits when we'll get that part ready. The type of f1_S is: *Simple> :t f1_S f1_S :: (ToWires a[a9GC], Num a[a9GC]) => (S a[a9GC], S a[a9GC]) -> (S a[a9GC], S [String]) or put simply: *Simple> :t f1_S f1_S :: (ToWires a, Num a) => (S a, S a) -> (S a, S [String]) It accepts two streams and return two streams - value and logs. We could add messages into logs: $(transform [d| f2 :: (ToWires a, Num a) => (a,a) -> a f2 (a,b) = s where s = a + b _display_a = a _display_b = b _display_s = s |]) f2 is just like f1, but when ran, it will produce logs about execution along the values. f2 used by runningSum, which compute a sum of values seen before current cycle: $(transform [d| runningSum :: (ToWires a, Num a) => a -> a runningSum x = currentSum where nextSum = f2 (x,currentSum) currentSum = register 0 nextSum _display_currentSum = currentSum _display_x = x _display_nextSum = nextSum |]) runningSum uses latches. It latches nextSum to pass the value to the next cycle using "register" function. "register" accepts default value and a value to latch (stream of values to delay) . When the time will come for synthesizing circuits, our register's will become actual latches with reset and clk wires. This is how we test our runningSum_S with simple data: runningSumLogs :: IO () runningSumLogs = do mapM putStrLn $ map unlines $ take 5 $ toList_S $ snd $ runningSum_S (fromList_S [1::Int ..]) return () The output will be like the following: currentSum: 0 x: 1 nextSum: 1 nextSum_0 = Simple.f2 (x_1, currentSum_2): a: 1 b: 0 s: 1 currentSum: 1 x: 2 nextSum: 3 nextSum_0 = Simple.f2 (x_1, currentSum_2): a: 2 b: 1 s: 3 currentSum: 3 x: 3 nextSum: 6 nextSum_0 = Simple.f2 (x_1, currentSum_2): a: 3 b: 3 s: 6 Logs are nested and after label "nextSum_0 = Simple.f2 (x_1, currentSum_2):" we see logs from f2_S function. The code is in QUITE EXPERIMENTAL stage, but feel free to play and comment.

1 0

A long day with HXT
by nadine.and.henry＠pobox.com 09 May '11

09 May '11

Dear Group, I have just spent many hours staring at code and losing some hair. My hope is to save you the same experience someday. Here was my goal: Take some XML, like <photo url="somewhere" align="left" alt=""/> and replace the align attribute with a class attribute, but only if the value of the align attribute was not null. This led to to followed (hugely condensed) attempts: ------------------------------------------------------------------------ > {-# LANGUAGE Arrows #-} > import Text.XML.HXT.Core > > -- <photo url="somewhere" align="left" alt=""/> > testString = "<photo url=\"somewhere\" align=\"left\" alt=\"\"/>" > toClass :: b -> QName > toClass = const (mkName "class") > > > try f = runLA (xread >>> processTopDown f) testString > > test1 = try $ > hasAttrValue "align" (not.null) >>> > processAttrl (changeAttrName toClass `when` hasName "align" ) > test2 = try $ processAttrl > (changeAttrName toClass `when` hasAttrValue "align" (not.null)) > test3 = try $ processAttrl > (changeAttrName toClass `when` hasName "align") > `when` hasAttrValue "align" (not.null) > > run = do > print test1 > print test2 > print test3 > result of run: [NTree (XTag "photo" [NTree (XAttr "url") [NTree (XText "somewhere") []],NTree (XAttr "class") [NTree (XText "left") []],NTree (XAttr "alt") []]) []] [NTree (XTag "photo" [NTree (XAttr "url") [NTree (XText "somewhere") []],NTree (XAttr "align") [NTree (XText "left") []],NTree (XAttr "alt") []]) []] [NTree (XTag "photo" [NTree (XAttr "url") [NTree (XText "somewhere") []],NTree (XAttr "class") [NTree (XText "left") []],NTree (XAttr "alt") []]) []] test1 and test3 performed as desired, needless to say I started out with something similar to test2 and was almost crying because the align attribute didn't change. Why? In test1, I run through the tree and select the elements which have a non-null align attribute. (hasAttrValue "align" (not.null)) Then for each of these elements I process their attributes. (processAttrl) where I change the attribute name to "class" (changeAttrName toClass) WHEN the attribute name is "align" (`when` hasName "align") Result: Joy In test2, I run through the tree and process every attribute list (processAttrl) I change the name of the attribute to "class" (changeAttrName toClass) WHEN the align attribute is not null (`when` hasAttrValue "align" (not.null))) Result: Nothing changes, - No Joy In test3, I run through the tree process every attribute list (processAttrl) WHEN the align attribute is not null (`when` hasAttrValue "align" (not.null)) and in that case I change the attribute name to "class" (changeAttrName toClass) WHEN the attribute is named "align" (`when` hasName "align") Result: Joy After staring at test2 for more time that I would like to acknowledge, I (think) I realized the following. In test2 I thought the (hasAttrValue "align" (not.null)) was referring to the tree that was coming into the test, but actually it is referring to the list of attributes that is generated by processAttrl. This list of attributes does not itself have any attributes, thus the (hasAttrValue "align" (not.null)) code never succeeds, and thus the (changeAttrName toClass) is never executed. Lessons learned: I'm not really sure, but it is these kind of subtleties that make me sometimes long for my old friend Perl. Best wishes, Henry Laxen -- Nadine & Henry Laxen Belle, Venus, Aphrodite 10580 N. McCarran Blvd. Adonis, Miss Parker & Jarod Suite 115-396 Via Alta # 6 Reno, Nevada Chapala, Jalisco, Mexico 89503-1896 CP 45900 The rest is silence. (Hamlet)

2 1

Re: [Haskell-cafe] [Haskell] ANN: syntactic-0.1
by Emil Axelsson 09 May '11

09 May '11

2011-05-07 09:52, Heinrich Apfelmus skrev: > Emil Axelsson wrote: >> I'm happy to announce the first release of syntactic: >> >> http://hackage.haskell.org/package/syntactic >> >> providing generic abstract syntax and utilities for embedded >> languages. >> >> To get an idea of what it's about, check out the tiny(!) >> implementation of (simplified) Feldspar in the Examples directory: >> >> http://projects.haskell.org/syntactic/Examples/MuFeldspar >> >> The library is intended to provide a growing set of utilities for >> embedded languages. In particular, I hope to be able to provide safe >> interfaces to various unsafe techniques for speeding things up. >> >> Comments, patches and clients are welcome! > > Looks very interesting! > > I'm currently working on a functional reactive programming DSL. Source code: > > http://tinyurl.com/reactive-banana-0-2-pushio > > The EventD type represents the abstract syntax tree (line 150), which > is then compiled in three phases (line 313) > > compile e ~= map compilePath =<< compileUnion =<< compileAccumB e > > If you look at the EventD type, you can see it contains a lot of > "internal constructors" (line 158) that are created in destroyed in > certain compilation phases. Ideally, I would make a new EventD type > for each compilation phase that doesn't have any superfluous > constructors. For instance, compileUnion removes the Union constructor. Hello Heinrich! Thanks for your interest! In principle, this is exactly the kind of thing you can do with syntactic -- if you can make your data type fit into the framework, that is. A compilation phase would then look something like this: phase :: AST (C1 :+: TheRest) -> AST (C2 :+: C3 :+: TheRest) This phase destroys the constructor C1 and introduces C2 and C3. Now, the question is whether your data type can be made to fit into the framework. The only problem I can see (but there may be more!) is that you'd have to treat EventD and BehaviorD as parts of the same data structure. I've pasted an example of how to do that here: http://hpaste.org/46525/ Here, the difference between Event and Behavior is denoted by the type constructors E and B respectively: type Event a = ASTF (Never :+: B2E :+: Pure :+: E2B) (E a) type Behavior a = ASTF (Never :+: B2E :+: Pure :+: E2B) (B a) You decide if this seems like an acceptable solution... > I'm also unhappy about some of the boilerplate. For instance, have a > look at the function goE in compileAccumB (line 210), it's just a > generic applicative traversal through the data type. Most likely, this boilerplate could be simplified using syntactic. > Would your library make me happier? Note that I have an additional > complication: I need to observe sharing and I need to support recursive AST. I plan to add observable sharing soon. Once that's is in place, it should -- I think/hope -- be easy to support cycles. This is not something we need in Feldspar, so it might take a while before I get around to supporting cycles, though. I'd be happy to give more assistance should you choose to try out syntactic for your library! Best regards / Emil

1 0