- Haskell-Cafe - Haskell.org

Designing DSL with explicit sharing [was: I love purity, but it's killing me]
by oleg＠okmij.org 17 Feb '08

17 Feb '08

Matthew Naylor wrote: > it's not immediately clear (to me at least) how efficient your method > will be in "practice". Any method based on common sub-expression > elimination surely must inspect every node in the flattened graph. In > the worst case, an acyclic graph containing n nodes could have 2^n > nodes when flattened to a tree: > > tricky 0 = constant 0 > tricky d = add g g > where > g = tricky (d-1) It should work quite well in practice, as demonstrated below. Once our DSL is extended with a let form (so the user can declare the intention to share results of computations rather than computations themselves), tricky code becomes trivial. The code remains declarative, safe and pure, and, save for the (cosmetic) lack of the monomorphism restriction, Haskell98. The well-commented code is available at http://okmij.org/ftp/Haskell/DSLSharing.hs First a few comments on the tricky code. It is true that (absent programmer's proclamations and code structuring forms) a complete method of common sub-expression elimination must inspect every sub-expression in the program. That inspection must include at least one comparison of a node with some other nodes. As I understand the original problem had less to do with the number of comparison but more to do with the cost of a single comparison. In an impure language, we can use constant-time physical equality. It is usually provided natively as pointer comparison, and can be trivially emulated via mutation. The original poster used pure Haskell and the following representation for the program graph: data Expression = Add Expression Expression | Sub Expression Expression | Variable String | Constant Int deriving Eq Here, the derived equality operation, albeit pure, no longer takes constant time. Comparing nodes near the root of a deep tree really takes a while. As the previous message on DSL with sharing showed, one can do common sub-expression elimination and the conversion of the program tree to a DAG using a constant-time node equality operation, without sacrificing purity. The tricky function is a metaprogram that builds a large DSL program: (tricky 12) yields a single DSL expression with 8191 nodes. Such humongous expressions with thousands of components are unlikely to be written by human programmers (although can be easily generated). Many compilers will choke if we submit a program with one large expression. (Incidentally, the previously posted code converts the tree (tricky 12) to a 12-node DAG in 0.25 secs on 1GHz Pentium). The reason we can compile much larger projects is because we structure them, into compilation units, functions, let-blocks. The structure gives the common sub-expression eliminator and other optimizer phases much needed hints and so significantly limits the search space. For example, hardly any compiler searches for common sub-expressions across compilation units. More importantly for us here, forms like let-expressions let the programmer declare that the results of certain computations be shared. Although the tricky code also contains a let-expression (masqueraded as 'where'), the sharing there occurs at the meta-level and benefits the generator rather than the generated program. We share code generators rather than the generated code. The importance of placing 'let' in the right phase has been extensively discussed in http://www.cs.rice.edu/~taha/publications/conference/pepm06.pdf also in the context of a DSL (for dynamic programming). In our case, we need to give our DSL programmer a way to state their intention on sharing results of DSL computations. The programmer declares certain expressions common, and thus greatly helps the compiler as well as human readers of the code. As Chung-chieh Shan has pointed out, we need to introduce a "let" construct in the _embedded_ language. Since our DSL already has (concrete) variables with string names, we can extend our language thusly: let_ "v1" (add (constant 1) (variable "x)) (add (variable v1") (variable "v1")) We chose a different way: higher-order abstract syntax. We use variables of the metalanguage (that is, Haskell) as let-bound variables. Our language is now defined as > class Exp repr where > constant :: Int -> repr Int > variable :: String -> repr Int > add :: repr Int -> repr Int -> repr Int > sub :: repr Int -> repr Int -> repr Int > let_ :: repr a -> (repr a -> repr b) -> repr b -- like flip ($) Here are simple programs in our language > a = add (constant 10) (variable "i1") > b = sub (variable "i2") (constant 2) > c = add a b > d = add c c > e = add d d -- "e" now as 16 leaf nodes. > e' = let_ d (\x -> add x x) The programs (e) and (e') evaluate to the same integer given the same environment for "i1" and "i2". The two programs differ in how sharing is declared. The program (e) uses the identifier (d) twice; even if GHC shares the corresponding expressions rather than copies them (a Haskell system is not obliged to share anything: sharing is not observable in Haskell98), what GHC shares are metalanguage computations. Although the metalanguage (Haskell) is pure, the object language does not have to be. Indeed, the common-subexpression elimination, when considered as an evaluation of an object expression, is an impure evaluation. The same object expression may give, in different contexts, different results (that is, compile to different assembly code). In the case of (e'), we explicitly stated that "d" is a common sub-expression. It must be executed once, with the results shared. The difference is easy to see if we print e and e': *DSLSharing> test_showe "10 + i1 + i2 - 2 + 10 + i1 + i2 - 2 + 10 + i1 + i2 - 2 + 10 + i1 + i2 - 2" *DSLSharing> test_showe' "let v0 = 10 + i1 + i2 - 2 + 10 + i1 + i2 - 2 in v0 + v0" Higher-order syntax for let_ (see e') seems better than that based on concrete variable names. As test-showe' demonstrates, we can easily convert from higher-order abstract to the concrete syntax. The converse is much more cumbersome. We easily extend the previously written common sub-expression eliminator by adding the clause for let_ > instance Exp A where > ... > let_ e f = A(do > x <- unA e > unA $ f (A (return x))) And that is it. We can write the tricky function with the explicit sharing: > tricky' 0 = constant 0 > tricky' d = let_ (tricky' (d-1)) (\g -> add g g) > > test_tricky' n = runState (unA (tricky' n)) exmap0 *DSLSharing> test_tricky' 12 (AAdd 12, ExpMaps {hashcnt = 13, ctmap = fromList [(0,0)], vrmap = fromList [], admap = fromList [(1,(AConst 0,AConst 0)),(2,(AAdd 1,AAdd 1)), (3,(AAdd 2,AAdd 2)),(4,(AAdd 3,AAdd 3)),(5,(AAdd 4,AAdd 4)), (6,(AAdd 5,AAdd 5)),(7,(AAdd 6,AAdd 6)),(8,(AAdd 7,AAdd 7)), (9,(AAdd 8,AAdd 8)),(10,(AAdd 9,AAdd 9)),(11,(AAdd 10,AAdd 10)), (12,(AAdd 11,AAdd 11))], sumap = fromList []}) (0.01 secs, 0 bytes) Indeed it takes negligible time. In fact, test_tricky' 12 takes (0.01 secs, 561860 bytes) test_tricky' 100 takes (0.03 secs, 1444888 bytes) If the DAG corresponding to (test_tricky' 100) were converted to a tree, it would have had 2^101 -1 nodes (which is more than 10^31).

5 4

Re: [Haskell-cafe] Designing a Parser
by PR Stanley 17 Feb '08

17 Feb '08

Actually, I haven't sent this question to the list before. So you're in no danger of repeating yourself. Thanks for your kind reply anyway Paul At 07:03 17/02/2008, you wrote: >On Feb 17, 2008 6:20 AM, PR Stanley <prstanley(a)ntlworld.com> wrote: > > I can't think of an elegant pattern for the last function. I've > > already tried set comprehension. However, something tells me that the > > answer may lie in a complex recursive pattern. I'm not afraid of > > complex solutions but I naturally see them as an easy way out. It's > > those clear simple patterns that separate men from mice. :-) I'd be > > grateful for any advice on this and indeed my approach as a whole. If > > you think I'm on the wrong path from the start feel free to let me > > know. I'm not asking for the answer. I'd like to work that out by > > myself although some guidance would be most appreciated. > >Yes, I definitely think you're on the wrong path from the start. In >high school when I was learning C++ I wrote an arithmetic expression >parser in something like this fashion. I scanned the input for the >first opening bracket, then I walked forward to the matching closing >bracket and extracted the subexpression and evaluated it. > >The approach turned out to be both complicated and inefficient. I >think the biggest problem was that it didn't scale well with >implementation complexity; eg. to add support for prefix functions >like sin() was almost impossible. Think about how you would go about >doing such things using your approach. > >I think I've seen you ask questions relating to this on the list >before, and at the risk of repeating others, I suggest the ReadS in >the Haskell Prelude. You get the benefit of it being a clean, >top-down solution as well as the benefit of having a lot of primitive >Haskell types already implemented for you (such as Integers). > >I'll describe the approach again, describing the combinators, and then >afterward showing how you might use them to accomplish this problem. >I'll leave the details up to you, since you can learn a lot by >implementing combinator libraries like this. > >First, you build a bunch of functions which are "parsers". A "parser" >is just a function of type String -> [(a,String)] for some type 'a'; >that is, it takes a string and returns a list of "parses", where a >parse is the value parsed paired with the remainder of the string. So >if you have a function: > > parseInt :: String -> [(Int,String)] > >Then you can expect this result: > > parseInt "123 hello world" = [(123, " hello world")] > >Or maybe even: > > parseInt "123 hello world" = [(123, " hello world"), (12, "3 hello >world"), (1, "23 hello world")] > >But that latter behavior is not recommended in this case (i.e. it is >advisable force int parsing to be greedy). > >Then to combine parsers you can use some combination operations: > > sequenceParsers :: (String -> [(a,String)]) -> (a -> String -> >[(b, String)]) -> String -> [(b,String)] > >That one may be easier to see if you use the built-in type synonym >ReadS a = String -> [(a, String)]: > > sequenceParsers :: ReadS a -> (a -> ReadS b) -> ReadsB > >The second argument here is a function, because we have already parsed >the first argument and know its value, so the second argument ought to >be able to use it. We can also write: > > alternateParsers :: ReadS a -> ReadS a -> ReadS a > >Which gives all valid parses that the first one recognizes >concatenated with all valid parsers that the second one recognizes. > >Implementation of these combinators is left to you. Since the types >of these functions are quite general, you can use a type-directed >approach (i.e. if your implementation uses all available data and it >typechecks, it's probably correct). > >Now that you have these, how do you use them to actually parse >something? Let's parse simple logical expressions. First we need a >data structure to parse into: > > data Exp > = Variable String > | AndExp Exp Exp > | OrExp Exp Exp > >Let's do it with a top down coding strategy: write a function to >parse an expression using whatever helper functions we need but >haven't written yet :-) > > parseExp :: ReadS Exp > parseExp = parseAnyOf [ parseVariable, parseAndExp, parseOrExp ] > >Where we haven't written parseAnyOf yet. Write that inductively on the list: > > parseAnyOf :: [ReadS a] -> ReadS a > parseAnyOf [] = \input -> [] > parseAnyOf (p:ps) = alternateParsers p (parseAnyOf ps) > >And jump in to the next thing we haven't written, parseVariable: > > parseVariable :: ReadS Exp > parseVariable = mapParser Variable parseString > >mapParser doesn't actually parse anything, it just parses whatever its >argument does and applies a function to the result: > > mapParser :: (a -> b) -> ReadS a -> ReadS b > mapParser :: (a -> b) -> (String -> [(a,String)]) -> String -> > [(b,String)] > >I rewrote the type signature to help guide your implementation. > >That should get you started, and show you how the approach usually >goes. You seem to already get the idea of writing many small >functions and composing them together. This is the same idea, except >the functions are abstracting the problem more. > >Luke

2 1

GHC + interactive input/output
by Jonathan Cast 17 Feb '08

17 Feb '08

$ cat > foo.c #include <stdio.h> int main() { char s[1024]; printf("gsi> "); gets(s); printf("%s\n", s); return 0; } $ make foo cc gsi.c -o gsi $ ./foo warning: this program uses gets(), which is unsafe. gsi> hello hello $ cat > foo.hs main = do putStr "gsi> " s <- getLine putStrLn s $ ghc foo.hs -o foo $ ./foo hello gsi> hello (This is on MacOS X). It strikes me that GHC is being extraordinarily unhelpful here. Is there anyone on the planet who ever actually wants this behavior? jcc

13 25

ANN: winerror-0.1
by Felix Martini 17 Feb '08

17 Feb '08

This is a small package for error handling when making foreign calls to the Windows API. The functions are similar to those in Foreign.C.Error, e.g. throwWinErrorIf corresponds to throwErrnoIf. Dynamic io errors are thrown with GHC so the catchWinError function can catch specific Windows error codes and handle them. Regards, Felix

1 0

Designing a Parser
by PR Stanley 17 Feb '08

17 Feb '08

Hi friends I'm in the process of designing a series of functions which you might collectively call a parser. The idea is to evaluate an input string for a proof software. So a typical input string would be something like "(P & Q) -> q". There are a number of things to consider here, for example, does the string belong to the domain which is a subset of the 7-bit ASCII table, starting from 32 and ending at 126. Then you need to remove all space characters to make things a bit simpler. Next we find out if the logical sentnece is bracketted. I start this by looking for a bracket in the string. If true then I isolate the brackets into a new set in order to spot any odd ones. Here is what I've done so far: domain :: [Char] domain = [x | x <- ascii7, x >= ' ' && x <= '~'] where ascii7 = ['\0'..'\127'] -- a legal input character is a member of domain. isInDomain :: Char -> Bool isInDomain x = any (==x) domain -- a legal input string is a subset of domain. isSubset :: [Char] -> Bool isSubset input = all isInDomain input -- delete spaces for easier parsing. noSpace :: [Char] -> [Char] noSpace input = [x | x <- input, x /= space] where space = ' ' -- set of brackets brackets = ['(', ')', '[', ']', '{', '}'] -- Are there any brackets in input? hasBrackets :: [Char] -> Bool hasBrackets input = or [True | x <- input, any (==x) brackets] -- filter all brackets into a subset. getBrackets :: [Char] -> [Char] getBrackets input = [x | x <- input, any (==x) brackets] -- What are matching brackets? areMatched :: Char -> Char -> Bool areMatched '(' ')' = True areMatched '[' ']' = True areMatched '{' '}' = True areMatched _ _ = False -- Can all the brackets in input be paired up? allMatched :: [Char] -> Bool I can't think of an elegant pattern for the last function. I've already tried set comprehension. However, something tells me that the answer may lie in a complex recursive pattern. I'm not afraid of complex solutions but I naturally see them as an easy way out. It's those clear simple patterns that separate men from mice. :-) I'd be grateful for any advice on this and indeed my approach as a whole. If you think I'm on the wrong path from the start feel free to let me know. I'm not asking for the answer. I'd like to work that out by myself although some guidance would be most appreciated. Thanks, Paul

2 1

GHC strange behavior
by Ruslan Evdokimov 17 Feb '08

17 Feb '08

Hi, all! I have strange GHC behavior. Consider the code: import Control.Parallel main = print (o `par` (fromInteger e) / (fromInteger o)) where [e,o] = map sum $ map (`filter` numbers) [even, odd] numbers = [1..10000000] When it compiled without threaded it has 19068 ms to run, 396 Mb total memory in use and %GC time 88.2%, the same with -threaded and +RTS -N1, but with +RTS -N2 it takes only 3806 ms to run, 3 Mb total memory in use and %GC time 8.1%. Why it so? It's a bug or I missed something? I test it on dual-core Athlon X2 4200+ 2Gb running 64bit Gentoo system. gcc 4.2.2 and ghc 6.8.2. -- Ruslan

4 8

Haskell project support and analysis on ohloh
by Don Stewart 16 Feb '08

16 Feb '08

Recently ohloh.net added support for analysing haskell code. You can see a range of Haskell projects analysed on ohloh here: http://www.ohloh.net/projects/search?q=haskell Including: http://www.ohloh.net/projects/11789?p=nhc98 http://www.ohloh.net/projects/6869?p=xmonad http://www.ohloh.net/projects/4078?p=HUGS http://www.ohloh.net/projects/6949?p=yi http://www.ohloh.net/projects/10496?p=bytestring http://www.ohloh.net/projects/11766?p=parsec http://www.ohloh.net/projects/11779?p=mtl http://www.ohloh.net/projects/11729?p=binary http://www.ohloh.net/projects/11769?p=X11 http://www.ohloh.net/projects/11790?p=array Which gives rise to some fun 'reports' (and also helps non-Haskell people notice that there are lots of Haskell projects, and developers with experience): xmonad: " Over the past twelve months, 34 developers contributed new code to xmonad. This is one of the largest open-source teams in the world, and is in the top 2% of all project teams on Ohloh. " nhc98: "nhc has a mature, well established code base. The first lines of source code were added to nhc98 in 1999. This is a relatively long time for an open source project to stay active, and can be a very good sign. A long source control history like this one shows that the project has enough merit to hold contributors's interest for a long time. It might indicate a mature and relatively bug-free code base, and can be a sign of an organized, dedicated development team. " Now, they don't support analysing darcs repos, but the do support git, and with darcs-to-git and darcs2git I've been able to (slowly) get a bunch of repos into git form. You can find the git conversions here, if you're interested: http://www.cse.unsw.edu.au/~dons/git/ (git clone http://www.cse.unsw.edu.au/~dons/git/parsec for example). GHC, base and lambdabot are still in the process of conversion. If you want to do your own conversions, I suggest trying darcs2git first, which is very fast. If that doesn't suceed, try darcs-to-git, which is *much* slower (damn ruby), but seems to be more robust. You can then register the resulting git repo for analysis. The global language statistics, and individual Haskell statistics will update in the next few hours, I suspect. http://www.ohloh.net/languages/38 Though at the time of writing they appear out of date. Happy hacking. -- Don

1 0

Help with error
by Jeff φ 16 Feb '08

16 Feb '08

Hello, I get an error message on the code below with GHC. I can't figure out how to get rid of the error. I'd appreciate suggestions on how to fix this. (BTW, the code may look overly combersome because I stripped out anything unnecessary to demonstrate the error.) {-# OPTIONS_GHC -fglasgow-exts -fbreak-on-exception -fallow-undecidable-instances #-} import qualified Prelude import Prelude import Data.Array.IArray class Sequence seq where slength :: (seq e) -> Int snull :: (seq e) -> Bool shead :: (seq e) -> e stail :: (seq e) -> (seq e) instance Sequence [] where slength = length snull = null shead = head stail = tail class From_seq t where from_seq :: (Sequence seq) => (seq e) -> (t e) instance From_seq [] where from_seq seq | snull seq = [] | otherwise = (shead seq) : (from_seq (stail seq)) from_seq' seq | snull seq = (listArray (0,-1) []) | otherwise = listArray (0,fromIntegral (slength seq) -1) (from_seq seq) {- When I uncomment this out, I get the error messages: Error.hs:41:19: Could not deduce (IArray a e) from the context (From_seq (a i), Ix i, Num i, IArray a e1, Sequence seq) arising from a use of `from_seq'' at Error.hs:41:19-31 instance (Ix i, Num i, IArray a e) => From_seq (a i) where from_seq seq = from_seq' seq -} When I load the module above, I can evaluate the folloing in GHCI *Main> from_seq' [0..5] :: Array Int Double array (0,5) [(0,0.0),(1,1.0),(2,2.0),(3,3.0),(4,4.0),(5,5.0)] But, I'd like to do this with the From_seq class. If anyone has suggestions, I'd be grateful. Thanks, Jeff

2 2

*** JOB OFFER *** related to realtime 3D graphics, animation and reactive content
by Peter Verswyvelen 16 Feb '08

16 Feb '08

<http://www.anygma.com/> Anygma is a startup company focusing on generating easy-to-use tools for creating audio-visual 2D/3D content, in the area of entertainment, media, corporate communication and the internet. <http://www.anygma.com/> Anygma has recently raised new capital in order to fund the development of a new platform targeted towards artists and designers for generating procedural and reactive geometry, animations and games. We are looking for talented and passionate computer scientists and software engineers to help us design and implement a prototype of this platform. If you are interested in applying Haskell, OpenGL, and some C/C++, to create such a platform, feel free to apply for the job by sending an email to <mailto://peter%3CAT%3Enazooka%3CDOT%3Ecom> peter AT nazooka DOT com. More information about the job offer can be found <http://www.anygma.com/JobOfferA.html> here. Thank you, Peter Verswyvelen, Software Architect, www.anygma.com <http://www.anygma.com/> PS: This job offer was already placed in the Haskell Café a while ago, but apparently many Haskellers did not notice it, so heres take#2

2 1

Re: [Haskell] Lemmas about type functions
by Ryan Ingram 16 Feb '08

16 Feb '08

[moved to haskell-cafe] Hmm, there's a problem here. Since type functions are open, it's not actually true that (forall ts. Cat ts () = ts), because someone could add, for example type instance Cat [a] () = [(a,a)] which makes the lemma no longer true. What you are doing in cat_nil is not proving that Cat ts () = ts, but rather that the form of ts is a particular form which makes that theorem hold, in particular, for all types ts of the form ts = (t1, (t2, ..., (tN, ()) ... )) Cat ts () = ts So for your lemma to hold, you need a new judgement "Valid ts": class Valid ts where cat_nil :: Equiv (Cat ts ()) ts -- other lemmas here instance Valid () where cat_nil = Equiv instance Valid x => Valid (a, x) where cat_nil = case (cat_nil :: Equiv (Cat x ()) x) of Equiv -> Equiv coerce :: forall f ts. Valid ts => f (Cat ts ()) -> f ts coerce x = case (cat_nil :: Equiv (Cat ts ()) ts) of Equiv -> x Also, I'm not sure if GHC can currently optimize away cat_nil; it's clear by construction that cat_nil is total, but if the compiler can't detect that it needs to run and make sure it returns Equiv and not _|_. Otherwise you get an unsound result: (given the type instance above) instance Valid [a] where cat_nil = cat_nil Oleg has pointed out this problem with GADTs as type witnesses here: http://okmij.org/ftp/Haskell/GADT-problem.hs -- ryan On 2/15/08, Ryan Ingram <ryani.spam(a)gmail.com> wrote: > I am pretty sure that this doesn't exist, but it's quite interesting. > I've submitted a feature request here: > > http://hackage.haskell.org/trac/ghc/ticket/2101 > > On 2/15/08, Louis-Julien Guillemette <guillelj(a)iro.umontreal.ca> wrote: > > Hi all, > > > > I've been using GHC's type families somewhat extensively in my > > type-preserving compiler (BTW, they work great), and quite often I > > come across the need to prove lemmas about those functions. As far as > > I understand there's currently no way to handle such lemmas purely at > > the type level, and I have to encode them as term-level functions. > > > > I wonder if I'm missing something, or otherwise if there are plans to > > provide some way to do this kind of type-level reasoning. > > > > Here's a simple example. > > > > I encode (de Bruijn) type contexts as lists of types of this form: > > > > (t0, (t1, (... , ()...))) > > > > I sometimes concatenate type contexts, and need a lemma stating that > > appending an empty context leaves it unchanged (ts ++ [] == ts). > > > > type family Cat ts0 ts > > type instance Cat () ts' = ts' > > type instance Cat (s, ts) ts' = (s, Cat ts ts') > > > > That is, I need to coerce: > > > > Exp (Cat ts ()) > > > > into: > > > > Exp ts > > > > The way I presently do it is through a term-level function that > > produces a witness that the two types are equivalent, like this: > > > > data Equiv s t where > > Equiv :: (s ~ t) => Equiv s t > > > > cat_nil :: EnvRep ts -> Equiv (Cat ts ()) ts > > cat_nil R0 = Equiv > > cat_nil (Rs _ ts_r) = case cat_nil ts_r of Equiv -> Equiv > > > > coerce :: EnvRep ts -> Exp (Cat ts ()) -> Exp ts > > coerce ts_r e = case cat_nil ts_r of Equiv -> e > > > > > > Louis > > > > _______________________________________________ > > Haskell mailing list > > Haskell(a)haskell.org > > http://www.haskell.org/mailman/listinfo/haskell > > >

1 0