April 2007 - Haskell-Cafe

Is Template Haskell a suitable macro language?
by Joel Reymont 24 Apr '07

24 Apr '07

I'm finding myself dealing with several large abstract syntax trees that are very similar in nature. The constructor names would be the same or one type may be a small extension of another. This is something that I wouldn't worry about with Lisp, for example, as I would create a bunch of macros for creating syntax trees and reuse them all over. I cannot do this in Haskell, though, as my "macros" are functions and so I must repeat them for every AST since they return different types. I'm wondering if Template Haskell is a suitable replacement for Lisp macros. What is the consensus? Thanks, Joel -- http://wagerlabs.com/

5 5

Re: haskell question
by oleg＠pobox.com 23 Apr '07

23 Apr '07

Greg Meredith wrote: > The file compiles with ghc as is. If you uncomment the last > section, however, you see that to close the loop on the constraints for the > agent syntax we hit a typing error. i <b><i>think</i></b> this is a hard > constraint in Haskell that prevents this level of generality in the > specification, but maybe you can see a way around it. I believe the Haskell typechecker is right > instance (Eq n, Eq p) => > CoreAgentSyntax (MinimalAgentSyntax n p) where > bind [] proc = Thunk (\() -> proc) > > data MinimalAgentSyntax n p = > Thunk (() -> p) > | Abstraction ([n] -> p) > | Concretion [n] p The bind method has the signature bind :: (CoreProcessSyntax p, CoreAgentSyntax x) => [n] -> (p a x) -> x That is: for any agent x and for _any_ process p (regardless of x), we should be able to perform the bind operation. The signature for bind proclaims total independence between 'p' and 'x'. However, when we define the instance > CoreAgentSyntax (MinimalAgentSyntax n p) where > bind [] proc = Thunk (\() -> proc) we see that process proc and the agent aren't totally independent: the result of bind has the type 'MinimalAgentSyntax n process' and thus is dependent on the 'process == p a x'. We have broken our previously made independence proclamation, and so the typechecker rightfully complaints. The following is one solution. It works sans the line marked TODO. I'm not sure that line is correct: -- -- TODO : lgm : need to substitute m for n in proc -- bind (name:names) proc = Abstraction (\m -> bind names proc) According to the type of Abstraction, 'bind names proc' should have the type 'p', that is, the same type as proc. It should be a process. OTH, bind returns an agent. Something is amiss here. {-# OPTIONS -fglasgow-exts #-} module Core where -- What's in a name? class Nominal n where nominate :: i -> n i newtype Name i = Nominate i deriving Eq instance Nominal Name where nominate i = Nominate i -- Where are we? class Locality a where locate :: (Eq s, Nominal n) => s -> (n i) -> a s (n i) name :: (Eq s, Nominal n) => a s (n i) -> (n i) data Location s n = Locate s n deriving Eq instance Locality Location where locate s n = Locate s n name (Locate s n) = n -- Constraints class CoreProcessSyntax p a x | p -> a x where zero :: p sequence :: a -> x -> p compose :: [p] -> p class CoreAgentSyntax x p n | x -> p n where bind :: [n] -> p -> x offer :: [n] -> p -> x -- Freedom (as in freely generated) data MinimalProcessSyntax l x = Null | Sequence l x | Composition [MinimalProcessSyntax l x] data MinimalAgentSyntax n p = Thunk (() -> p) | Abstraction ([n] -> p) | Concretion [n] p -- Constraining freedom instance CoreProcessSyntax (MinimalProcessSyntax l x) l x where zero = Null sequence l a = Sequence l a compose [] = zero compose ps = Composition ps instance CoreAgentSyntax (MinimalAgentSyntax n p) p n where bind [] proc = Thunk (\() -> proc) -- -- TODO : lgm : need to substitute m for n in proc -- bind (name:names) proc = Abstraction (\m -> bind names proc) -- here's the possible implementation. I don't know if it's right. -- But at least it types bind (name:names) proc = Abstraction (\m -> comp $ bind names proc) where comp (Thunk f) = f () -- comp (Concretion n p) = ... offer names proc = Concretion names proc

2 3

QuickCheck testing of AST transformers
by Joel Reymont 23 Apr '07

23 Apr '07

My previous post did not receive any replies so I thought I might try generalizing the problem a bit... Suppose I'm parsing a language into a syntax tree and then transforming that tree into another AST representing a "core language". The core language is a more general AST that should help with compiling to other languages. My problem is how to best structure my AST transformations to be able to test them with QuickCheck. I suspect that I'm not going about it in the most optimal way so I thought I should ask for suggestions. The transformation into the core AST applies operations to simplify, or desugar, the AST of the original language. Here's sample code in the source language which, incidentally, was recently highlighted at Lambda the Ultimate [1]. Array: MyArray[10](10 + 2); Value1 = MyArray[5][10]; This declares an array of 10 elements and initializes each element to 12. Value1 (a built-in variable) is then initialized to the value of element #5 as of 10 bars ago. A bar is, basically, a stock quote. The code is invoked on every bar and so "5 bars ago" can be treated as 5 invocations ago. The syntax tree of the above code is a 1-1 mapping. We declare an array of integers of 10 elements. Initialize it to the sum of two integers and then assign to Value1. [ ArrayDecs [ VarDecl (VarIdent "MyArray") TyInt [Int 10] (Op Plus (Int 10) (Int 2)) ] , Assign (VarIdent "Value1") [] (Var (VarIdent "MyArray") [Int 5] (BarsBack (Int 10))) ] The "desugared" version does away with the array declaration statement and declares MyArray to be a variable of array type. Arrays in the "core language" do not remember values from one invocation to another but there's a data series type, so we declare a series variable to hold the value of element #5. We must manually store the value of the array element in the data series and can then refer to the value of the series 10 data points ago. vars = [ ("MyArray", VarDecl (TyArray TyInt) [Int 10] (Just (Plus (Int 10) (Int 2)))) , ("series0", VarDecl (TySeries TyInt) [] Nothing) ] code = [ AddToSeries (VarIdent "series0") (Var (VarIdent "MyArray") [Int 5]) , Assign (Var (VarIdent "Value1") []) (Series (VarIdent "series0") (Int 10)) ] The next step would be to take the above "core syntax tree" and transform it yet again into a C# (or other target language) AST. It's assumed that all target languages have a data series type. The OCaml version of my code translated directly into the C# AST but I figured an intermediate syntax tree will help me translate into other languages such as Haskell, Erlang or OCaml. The part I can't figure out is how to come up with a set of invariants for my transformations. Should I, for example, state that every access to an array value in a previous invocation should introduce an extra variable to hold the series plus the appropriate assignment code? Should I write the translator as a series of small transformers in the ST monad that can be threaded and tested separately? Thanks in advance, Joel [1] http://lambda-the-ultimate.org/node/2201 -- http://wagerlabs.com/

3 2

Re: [Haskell-cafe] QuickCheck testing of AST transformers
by Thomas Schilling 23 Apr '07

23 Apr '07

Additionally, as a safety net, you might want to type-check the code that's being produced by your Arbitrary instances and state some invariants on your code. Also, you'll likely want to limit your number of evaluation steps if your language allows non-terminating programs. In any case, QuickCheck may not get you far enough to gain enough confidence, so proving properties by hand (after you made sure that QuickCheck doesn't find any counter-examples, of course) can give you interesting insights, since, this way, you have to take a look at all the possible cases yourself. /Thomas On 24 apr 2007, at 00.05, Lennart Augustsson wrote: > Without looking into your language and transformation in more > detail it's hard to come up with concrete suggestions. But here > are some anyway: > > Write an interpreter for each of your languages (original AST, > transformed AST) etc, and then use a quickcheck property stating > that well formed programs have the same denotation before and after > transformation, i.e., the two interpreters give the "same" value > (you might need some relaxed notion of same). > > You transformations are trying to get rid of some language > construct, I presume. So you can have some properties stating that > they will be gone in the transformed program.. > > -- Lennart > > > On Apr 23, 2007, at 22:46 , Joel Reymont wrote: > >> My previous post did not receive any replies so I thought I might >> try generalizing the problem a bit... >> >> Suppose I'm parsing a language into a syntax tree and then >> transforming that tree into another AST representing a "core >> language". The core language is a more general AST that should >> help with compiling to other languages. >> >> My problem is how to best structure my AST transformations to be >> able to test them with QuickCheck. I suspect that I'm not going >> about it in the most optimal way so I thought I should ask for >> suggestions. >> >> The transformation into the core AST applies operations to >> simplify, or desugar, the AST of the original language. Here's >> sample code in the source language which, incidentally, was >> recently highlighted at Lambda the Ultimate [1]. >> >> Array: MyArray[10](10 + 2); >> Value1 = MyArray[5][10]; >> >> This declares an array of 10 elements and initializes each element >> to 12. Value1 (a built-in variable) is then initialized to the >> value of element #5 as of 10 bars ago. A bar is, basically, a >> stock quote. The code is invoked on every bar and so "5 bars ago" >> can be treated as 5 invocations ago. >> >> The syntax tree of the above code is a 1-1 mapping. We declare an >> array of integers of 10 elements. Initialize it to the sum of two >> integers and then assign to Value1. >> >> [ ArrayDecs [ VarDecl (VarIdent "MyArray") TyInt [Int 10] >> (Op Plus (Int 10) (Int 2)) ] >> , Assign (VarIdent "Value1") [] (Var (VarIdent "MyArray") [Int 5] >> (BarsBack (Int 10))) ] >> >> The "desugared" version does away with the array declaration >> statement and declares MyArray to be a variable of array type. >> Arrays in the "core language" do not remember values from one >> invocation to another but there's a data series type, so we >> declare a series variable to hold the value of element #5. >> >> We must manually store the value of the array element in the data >> series and can then refer to the value of the series 10 data >> points ago. >> >> vars = [ ("MyArray", VarDecl (TyArray TyInt) [Int 10] >> (Just (Plus (Int 10) (Int 2)))) >> , ("series0", VarDecl (TySeries TyInt) [] Nothing) >> ] >> >> code = [ AddToSeries (VarIdent "series0") (Var (VarIdent >> "MyArray") [Int 5]) >> , Assign (Var (VarIdent "Value1") []) >> (Series (VarIdent "series0") (Int 10)) >> ] >> >> The next step would be to take the above "core syntax tree" and >> transform it yet again into a C# (or other target language) AST. >> It's assumed that all target languages have a data series type. >> >> The OCaml version of my code translated directly into the C# AST >> but I figured an intermediate syntax tree will help me translate >> into other languages such as Haskell, Erlang or OCaml. >> >> The part I can't figure out is how to come up with a set of >> invariants for my transformations. >> >> Should I, for example, state that every access to an array value >> in a previous invocation should introduce an extra variable to >> hold the series plus the appropriate assignment code? >> >> Should I write the translator as a series of small transformers in >> the ST monad that can be threaded and tested separately? >> >> Thanks in advance, Joel >> >> [1] http://lambda-the-ultimate.org/node/2201 >> >> -- >> http://wagerlabs.com/ >> >> >> >> >> >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

ANN: template 0.1 - Simple string substitution
by Johan Tibell 23 Apr '07

23 Apr '07

As an exercise I wrote a simple string substitution library that supports "$"-based substitution ala Perl or Python. Example usage: > import qualified Data.ByteString.Lazy.Char8 as B > import Text.Template > > context = Map.fromList . map packPair > where packPair (x, y) = (B.pack x, B.pack y) > > helloTemplate = B.pack "Hello, $name! Want some ${fruit}s?" > helloContext = context [("name", "Johan"), ("fruit", "banana")] > > main = B.putStrLn $ substitute helloTemplate helloContext Hopefully this is useful for someone who needs something more readable than Text.Printf's "%s"-based substitution or string concatenation for longer strings but less than a full blown templating system like the ones found in most web frameworks. Release: http://www.johantibell.com/template/template-0.1.tar.gz Source: darcs get http://darcs.johantibell.com/template Once we get ByteString literals most of the noise in the above example will disappear. In the mean time it's probably a good idea to write utility function like "context" above when you prefer a convenient String interface to a somewhat faster ByteString interface. It would be great if someone could do a code review and add it to Hackage if it looks OK. I'll really appreciate the feedback. Also, I'm not 100% sure how to make the haddock links work with Hackage so they link to the library docs. Is this something done at upload time? Here are some open issues: * I currently use my own ByteString parser. Data.Binary almost does what I need. Basically I need takeWhile and two chars of look-ahead. * I would like to only depend on base, currently I use State so I depend on mtl. Cheers, Johan

1 0

Announce: DisTract: Distributed Bug Tracker implemented in Haskell
by Matthew Sackman 23 Apr '07

23 Apr '07

DisTract is a Distributed Bug Tracker. We're all now familiar with working with distributed software control systems, such as Monotone, Git, Darcs, Mercurial and others, but bug trackers still seem to be fully stuck in the centralised model: Bugzilla and Trac both have single centralised servers. This is clearly wrong, as if you're able to work on the Train, off the network and still perform local commits of code then surely you should also be able to locally close bugs too. DisTract allows you to manage bugs in a distributed manner through your web-browser. Currently only Firefox is supported. The reason for this is that there is no local server used, and so the web-browser must directly (via Javascript) call programs on your local system. I only know how to do this in Firefox. The distribution is achieved by making use of a distributed software control system, Monotone. Thus Monotone is used to move files across the network, perform merging operations and track the development of every bug. Finally, the glue in the middle that generates the HTML summaries and modifies the bugs is written in Haskell. The first version, 0.1 has just been released. There are missing features currently, and I've only tested it on Linux. However, it should work on OS X and Windows if you can make it compile! It's only been tested with Monotone version 0.33. http://www.distract.wellquite.org/ Many thanks, Matthew

2 1

New York Functional Programmers Network Inaugural Meeting - Thurs day May 3rd 2007 from 6pm
by Mansell, Howard 23 Apr '07

23 Apr '07

We are starting up a New York area-based network for functional programmers. The idea is to have a regular meeting through which functional programmers can meet to discuss experiences, get and give information, find jobs etc. The first official meeting will be held on Thursday May 3rd at the offices of Credit Suisse in Manhattan, from 6pm to ~8pm. The meeting is intended to be an informal gathering and refreshments will be provided to make the experience even more pleasant. Please let me know if you would like to attend so that I can make sure we have a large enough room and adequate libation. Howard Mansell (Credit Suisse) Jeff Polakow (Deutsche Bank) ============================================================================== Please access the attached hyperlink for an important electronic communications disclaimer: http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html ==============================================================================

1 0

Performance and STUArrays
by Dominic Steinitz 23 Apr '07

23 Apr '07

I've been playing around some more trying improve the performance of the SHA1 implmentation in the crypto library. I've isolated one of the functions and implemented it using a) unfold and b) STUArray The STUArray implementation is about twice as fast but I was expecting an order of magnitude improvement given I thought I would have been allocating 16 x 80 new 32 bit words with unfold but nothing with the STUArray. Should I have been disappointed? dom@heisenberg:~/sha12> time ./arrTest 17 STUArray > /dev/null real 0m11.102s user 0m9.129s sys 0m0.112s dom@heisenberg:~/sha12> time ./arrTest 17 Unfold > /dev/null real 0m18.381s user 0m16.361s sys 0m0.212s Dominic. import Data.Bits import Data.List import Data.Word import Control.Monad.ST import Data.Array.ST import System import System.IO data Word160 = Word160 !Word32 !Word32 !Word32 !Word32 !Word32 deriving (Eq, Show) ss :: Word160 ss = Word160 0x67452301 0xefcdab89 0x98badcfe 0x10325476 0xc3d2e1f0 test :: [Word32] test = [0x61626380, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000018] tests :: Int -> [[Word32]] tests n = map (\n -> n:[0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x18]) [1..2^n] rotL :: Bits b => Int -> b -> b rotL = flip rotateL v1 :: a -> [Word32] -> [Word32] v1 ss xs = take 80 (n xs) where h [w0, w1, w2, w3, w4, w5, w6, w7, w8, w9, w10, w11, w12, w13, w14, w15] = Just (w0,[w1, w2, w3, w4, w5, w6, w7, w8, w9, w10, w11, w12, w13, w14, w15, (rotL 1 (w0 `xor` w2 `xor` w8 `xor` w13))]) n = unfoldr h v2 ss xs = vs where us = do w <- newArray (0,79) 0 :: ST s (STUArray s Int Word32) let initLoop 15 = writeArray w 15 (xs!!15) initLoop n = do writeArray w n (xs!!n) initLoop (n+1) mainLoop 79 = nextW 79 mainLoop n = do nextW n mainLoop (n+1) nextW n = do wm16 <- readArray w (n-16) wm14 <- readArray w (n-14) wm8 <- readArray w (n-8) wm3 <- readArray w (n-3) writeArray w n (rotL 1 (wm3 `xor` wm8 `xor` wm14 `xor` wm16)) initLoop 0 mainLoop 16 getElems w vs = runST us test1 n = map (v1 ss) (tests n) test2 n = map (v2 ss) (tests n) data TestType = Unfold | STUArray deriving (Eq, Read, Show) main = do progName <- getProgName args <- getArgs if length args /= 2 then putStrLn ("Usage: " ++ progName ++ " <testSize> <testType>") else do let n = read (args!!0) t = read (args!!1) if t == Unfold then putStrLn (show (test1 n)) else putStrLn (show (test2 n))

3 2

Creating QuickCheck properties
by Joel Reymont 23 Apr '07

23 Apr '07

Folks, I have code like this that I want to test with QuickCheck but I'm having trouble imagining how I would wrap it up in a property. Do I make sure that id, subs, back are always morphed properly or do I leave that to separate properties for their respective types? Do I then ensure that array types are always unwrapped (see getType below), that a "series" variable is always declared, code added and a series reference returned? Last but not least, is monadic testing part of Test.QuickCheck.*? Thanks, Joel type Core a = State CoreUnit a data CoreUnit = Core { coreSym :: Integer -- starting # for gensym , coreVars :: M.Map String VarDecl , coreCode :: M.Map Integer [Statement] } deriving (Show, Eq) morphHistArrayAccess :: VarIdent -> Subscript -> BackRef -> C.Core C.Expr morphHistArrayAccess id subs back = do id' <- morph id subs' <- morph subs back' <- morph back (C.TyArray ty) <- getType id' s <- genSym "series" addVar s (C.TySeries ty) [] Nothing addCodeFront 1 [ C.AddToSeries (C.VarIdent s) (C.Var id' subs') ] return $ C.Series (C.VarIdent s) back' -- http://wagerlabs.com/

1 0

Gotta love Haskell
by Justin Bailey 23 Apr '07

23 Apr '07

My wife has been put in charge of scheduling lectors and ministers at our church, so of course she needs a Haskell program to do the schedules for her! While I've been working on it, I wrote something that I thought was a pretty cool trick. Each Mass requires a variety of different type and number of participants, so when defining the "Mass" data structure I put a function in which selects participants for that type of Mass from a given list: data MassTime = MassTime { ... selectParticipants :: (Participants -> Maybe Participants), -- Picks participants for this mass ... } Each mass has particular requirements. Notice the 'selectParticipants' function does not take a mass definition as an argument. Here's the trick I thought was neat. When creating the MassTime value, I capture it in a closure and bind it to the selector function, as below: makeMass :: Day -> MassTime makeMass day = mass where -- Use trick here to capture mass defined and pass to our selection function. mass = MassTime ... (weekendMassSelector mass) ... 'weekendMassSelector' is defined elsewhere, and basically knows how to count up the right number of participants based on the mass definition given. It's signature is: weekendMassSelector :: MassTime -> Participants -> Maybe Participants So weekendMassSelector gets the MassTime value it needs, before it is even constructed. Partial evaluation then gives a function with the (Participants -> Maybe Participants) signature required by the data constructor. I love Haskell - this just seems too cool. Since I really doubt this is something new - is this a technique that's commonly used? Does it have a name? It looks a lot like passing a "this" argument to a function - have I re-invented OOP encapsulation? :) Justin

2 1