[Haskell-cafe] Building ? using kleene closure {not haskell specific}
Hello gentle Haskell folks, I happened to read Beautiful code's chapter 1 today and found Brian Kerninghan's regex implementation. In it he only shows the * meta character. I can easily understand how + can be built but am having trouble with building ? (zero or one). I'd really appreciate it if some one could help me understand it. Regards, Kashyap ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] library on common sub-expression elimination?
I guess you mean the function that converts an abstract syntax tree to
a directed acyclic graph (DAG).
Just for completeness I should mention that if the object language has
effects including non-termination, one has to be careful eliminating
seemingly common expressions. For example, in
\a i -
if i = 0 then
a ! i
else if i 0 then
a ! i + a ! (i-1)
else
we see the expression (a ! i) repeated in both branches of
the conditional. Eliminating the `duplicate' by pulling it out
\a i -
let t = a ! i in
if i = 0 then
t
else if i 0 then
t + a ! (i-1)
else
would be wrong, wouldn't it?
This issue has been extensively investigated in the Fortran compiler
community; Elliott, Finne and de Moor's ``Compiling Embedded Languages''
(JFP 2003) talks about it at length.
The standard technique to detect occurrences of common subexpressions
is so-called hash-consing. There are (OCaml) libraries for it:
author= {Jean-Christophe Filli{\^a}tre and Sylvain Conchon},
title = {Type-Safe Modular Hash-Consing},
pages = {12--19},
crossref = ml2006,
doi = 10.1145/1159876.1159880,
The upcoming distilled tutorial at DSL 2011
http://dsl2011.bordeaux.inria.fr/index.php?option=com_contentview=articleid=2Itemid=2
will present a Haskell library for hash-consing. The library can work
with the standard Haskell Hash-tables or without them (using Data.Map,
for example). The library does _not_ rely on Stable names and other
internal GHC operations with unstable semantics. The library will find
all common sub-expressions.
Incidentally, despite the Lisp-sounding name, hash-consing was
invented before Lisp. It was described, for the English audience, in
the first volume of Comm. ACM, in 1958:
@Article{ Ershov-hash-consing,
author= {A. P. Ershov},
title = {On programming of arithmetic operations},
journal = Communications of the {ACM},
year = 1958,
volume= 1,
number= 8,
pages = {3--6},
doi =10.1145/368892.368907,
url = http://portal.acm.org/citation.cfm?id=368907;
}
The translation is quite accurate, as far as I could see, but misses
the flowcharts and the diagram of the original paper. This short paper
fully describes what we now call hash tables, hash functions, useful
properties of hash functions, and hash-consing. The article analyzes
the time complexity of the algorithm. Since the algorithm has two
exits, writing programs in the continuation-passing style must have been
familiar back then.
The library to be presented at DSL 2011 unwittingly follows Ershov's
algorithm closely. The library is (hopefully) better described (see
the preface to the English translation of Ershov's paper). Nowadays,
starting a paper with the phrase ``All unexplained terms are those
from [1]'' (where [1] is the single reference) would not be taken
kindly by reviewers.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Building ? using kleene closure {not haskell specific}
Hi, Perhaps I did not understand the question properly, but it looks very straight forward : oneOrNone x = fmap Just x | pure Nothing it will have a type of oneOrNone :: (Alternative f) = f a - f (Maybe a) In fact, there is a function called optional in Control.Applicative[1] which does exactly that. Is this what you are looking for? thanks, Hemanth K [1] http://haskell.org/ghc/docs/6.12.2/html/libraries/base-4.2.0.1/Control-Applicative.html On Fri, Aug 12, 2011 at 1:31 PM, C K Kashyap ckkash...@gmail.com wrote: Hello gentle Haskell folks, I happened to read Beautiful code's chapter 1 today and found Brian Kerninghan's regex implementation. In it he only shows the * meta character. I can easily understand how + can be built but am having trouble with building ? (zero or one). I'd really appreciate it if some one could help me understand it. Regards, Kashyap ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Building ? using kleene closure {not haskell specific}
I can easily understand how + can be built but am having trouble with building ? (zero or one). If there is a regular expression e for the empty word, one can define ? as a? = e | a If there is a regular expression o that never matches one can define e as e = o* If there are character classes one can define o as o = [] Apart from that, I have no idea.. Sebastian ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Building ? using kleene closure {not haskell specific}
On Fri, Aug 12, 2011 at 4:34 PM, Sebastian Fischer fisc...@nii.ac.jpwrote: I can easily understand how + can be built but am having trouble with building ? (zero or one). If there is a regular expression e for the empty word, one can define ? as a? = e | a If there is a regular expression o that never matches one can define e as e = o* If there are character classes one can define o as o = [] Apart from that, I have no idea.. Sebastian Thanks Sebastian ... this is what I was asking for. I'll try and digest it. Regards, Kashyap ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] fyi GHC 7.2.1 release on the benchmarks game
1) Some of the GHC programs contributed to the benchmarks game have problems with recent GHC releases - meteor-contest #5 - Ambiguous occurrence `permutations' http://shootout.alioth.debian.org/u64q/program.php?test=meteorlang=ghcid=5#log - regex-dna #2 - Precedence parsing error http://shootout.alioth.debian.org/u64q/program.php?test=regexdnalang=ghcid=2#log - reverse-complement #2 - parse error on input `-' http://shootout.alioth.debian.org/u64q/program.php?test=revcomplang=ghcid=2#log - reverse-complement #3 - Could not find module `Monad' http://shootout.alioth.debian.org/u64q/program.php?test=revcomplang=ghcid=3#log 2) I noticed `-fvia-C` has now gone away and there were half-a-dozen programs that had been written to use `-fvia-C` so how might that effect performance of those programs? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] fyi GHC 7.2.1 release on the benchmarks game
Hello Isaac,
On Fri, Aug 12, 2011 at 10:18 AM, Isaac Gouy igo...@yahoo.com wrote:
1) Some of the GHC programs contributed to the benchmarks game have problems
with recent GHC releases
- meteor-contest #5 - Ambiguous occurrence `permutations'
http://shootout.alioth.debian.org/u64q/program.php?test=meteorlang=ghcid=5#log
This can be fixed by changing the line:
import Data.List
to:
import Data.List hiding (permutations)
Also, the program needs to be compiled with -XBangPatterns
- regex-dna #2 - Precedence parsing error
http://shootout.alioth.debian.org/u64q/program.php?test=regexdnalang=ghcid=2#log
This can be fixed by changing this line (line 74):
mapM_ putStrLn $ results `using` parList rdeepseq
to:
mapM_ putStrLn (results `using` parList rdeepseq)
There are also some deprecation warnings related to `rwhnf` among
others being renamed, but those are harmless (may want to fix them
anyway though.)
- reverse-complement #2 - parse error on input `-'
http://shootout.alioth.debian.org/u64q/program.php?test=revcomplang=ghcid=2#log
You can fix this by adding this pragma:
{-# LANGUAGE MagicHash, UnboxedTuples #-}
or compiling with -XMagicHash and -XUnboxedTuples
Also, this program imports 'GHC.IOBase' which is a warning, that
import should be changed to 'GHC.IO' instead.
- reverse-complement #3 - Could not find module `Monad'
http://shootout.alioth.debian.org/u64q/program.php?test=revcomplang=ghcid=3#log
You can fix this one by adding this pragma to the top of revcomp.hs
{-# LANGUAGE BangPatterns #-}
Alternatively you can compile with -XBangPatterns. Also, change the line
import Monad
to:
import Control.Monad
2) I noticed `-fvia-C` has now gone away and there were half-a-dozen programs
that had been written to use `-fvia-C` so how might that effect performance
of those programs?
I can't forsee the potential performance ramifications, but frankly
-fvia-C has been deprecated/not-advised-for-use for quite a while now,
and I wonder how many of these programs just have not been
updated/tested with the native code generator since they were written.
In any case it's not an option anymore, so your only choice is to nuke
it from orbit (orbit being the Makefiles.)
--
Regards,
Austin
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] library on common sub-expression elimination?
Just to make it explicit, is it
\a i -
let t = a ! i in
if i = 0 then
t
else if i 0 then
t + a ! (i-1)
else
bad idea, because of last else-case? Can it be mended with
one another pass for if-expressions?
The upcoming distilled tutorial at DSL 2011 - thank you for the link.
I'm going to experiment with data-reify, while the library you've mentioned
is
OCaml only.
2011/8/12 o...@okmij.org
I guess you mean the function that converts an abstract syntax tree to
a directed acyclic graph (DAG).
Just for completeness I should mention that if the object language has
effects including non-termination, one has to be careful eliminating
seemingly common expressions. For example, in
\a i -
if i = 0 then
a ! i
else if i 0 then
a ! i + a ! (i-1)
else
we see the expression (a ! i) repeated in both branches of
the conditional. Eliminating the `duplicate' by pulling it out
\a i -
let t = a ! i in
if i = 0 then
t
else if i 0 then
t + a ! (i-1)
else
would be wrong, wouldn't it?
This issue has been extensively investigated in the Fortran compiler
community; Elliott, Finne and de Moor's ``Compiling Embedded Languages''
(JFP 2003) talks about it at length.
The standard technique to detect occurrences of common subexpressions
is so-called hash-consing. There are (OCaml) libraries for it:
author= {Jean-Christophe Filli{\^a}tre and Sylvain Conchon},
title = {Type-Safe Modular Hash-Consing},
pages = {12--19},
crossref = ml2006,
doi = 10.1145/1159876.1159880,
The upcoming distilled tutorial at DSL 2011
http://dsl2011.bordeaux.inria.fr/index.php?option=com_contentview=articleid=2Itemid=2
will present a Haskell library for hash-consing. The library can work
with the standard Haskell Hash-tables or without them (using Data.Map,
for example). The library does _not_ rely on Stable names and other
internal GHC operations with unstable semantics. The library will find
all common sub-expressions.
Incidentally, despite the Lisp-sounding name, hash-consing was
invented before Lisp. It was described, for the English audience, in
the first volume of Comm. ACM, in 1958:
@Article{ Ershov-hash-consing,
author= {A. P. Ershov},
title = {On programming of arithmetic operations},
journal = Communications of the {ACM},
year = 1958,
volume= 1,
number= 8,
pages = {3--6},
doi =10.1145/368892.368907,
url = http://portal.acm.org/citation.cfm?id=368907;
}
The translation is quite accurate, as far as I could see, but misses
the flowcharts and the diagram of the original paper. This short paper
fully describes what we now call hash tables, hash functions, useful
properties of hash functions, and hash-consing. The article analyzes
the time complexity of the algorithm. Since the algorithm has two
exits, writing programs in the continuation-passing style must have been
familiar back then.
The library to be presented at DSL 2011 unwittingly follows Ershov's
algorithm closely. The library is (hopefully) better described (see
the preface to the English translation of Ershov's paper). Nowadays,
starting a paper with the phrase ``All unexplained terms are those
from [1]'' (where [1] is the single reference) would not be taken
kindly by reviewers.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Potential problem with AC-Vector-Fancy package
I think I have found a problem with the union function: If you look here: http://hpaste.org/49889 You will see that line 4 gives a different result to lines 6, 8, 10; this shouldn't be the case because union is commutative. AC-Vector-Fancy is merely a fancy facard over AC-Vector. So the bug is actually with AC-Vector. Looking at my source code, the true bug is in Data.BoundingBox.Range [which provides the engine that all the other bounding box types use). The actual bug turns out to by face-slappingly stupid: it's a typo in one of the variable names. I'll go get that fixed... and then maybe write some QuickCheck properties. I just updated AC-Vector 2.3.2, which fixes the bug. Sorry about that... Let me know if you find any other stupid mistakes. (Or even clever ones, but I rather doubt that!) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] library on common sub-expression elimination?
Note that data-reify will only find *some* common/equal sub-expressions, namely the pointer-equal ones. In all of my code-generating (deep) DSLs, it's been very important for efficiency to also pull out equal-but-pointer-unequal expressions. - Conal On Thu, Aug 11, 2011 at 4:41 AM, Vo Minh Thu not...@gmail.com wrote: I guess you refer to data-reify: http://hackage.haskell.org/package/data-reify 2011/8/11 Stephen Tetley stephen.tet...@gmail.com: Strafunski and its successors (Uniplate, SYB, KURE) are really for working on trees. If you want to work on graphs you would probably be better of with something else. I think I overlooked that you want common sub-expression _elimination_, rather than expression simplification. There are libraries for observable sharing (Andy Gill's recent one is the state-of-the-art, its on Hackage but I've forgotten its name) - that are pertinent where you have built the expressions as an embedded DSL in Haskell and you want sharing in code you generate from the Haskell DSL. On 11 August 2011 08:57, Anton Kholomiov anton.kholom...@gmail.com wrote: Thank you for the reference to Strafunski libraries, I read HaskellWiki, but I don't have a permission to visit their site. All links are forbidden. Can it be a function: fun :: Eq a = Tree a - [(Int, (a, [Int]))] where tuple codes nodes, and Int's code edges. 2011/8/11 Stephen Tetley stephen.tet...@gmail.com Wouldn't this be dependent upon your AST and thus not readily package-able as a library? Expression simplification has been a prime example for Strafunski style traversal libraries. You might be able to find examples that you can adapt to your own AST written with Uniplate or similar library. On 11 August 2011 05:00, Anton Kholomiov anton.kholom...@gmail.com wrote: Is there a library on common sub-expression elimination? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Distributions link on Hackage
Hi, Am Donnerstag, den 11.08.2011, 15:46 +0200 schrieb Peter Simons: the home page of a package on Hackage links to various distributions to show which versions are available, i.e. Fedora, Debian, FreeBSD, etc. In NixOS, we have fairly up-to-date package set, and I would like to see that distribution included on Hackage. Now I wonder how to get that done? Can anyone advice on the procedure to add support for a distribution to Hackage? have a look at http://hackage.haskell.org/trac/hackage/ticket/570 for the history of the feature, http://people.debian.org/~nomeata/cabalDebianMap.txt for the format for the file you have to provide, and open a ticket at aboves trac for it to be included. Greetings, Joachim -- Joachim nomeata Breitner Debian Developer nome...@debian.org | ICQ# 74513189 | GPG-Keyid: 4743206C JID: nome...@joachim-breitner.de | http://people.debian.org/~nomeata signature.asc Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] library on common sub-expression elimination?
Do you mean that x and y in x = a + 1 y = a + 1 are different from data-reify point of view? 2011/8/12 Conal Elliott co...@conal.net Note that data-reify will only find *some* common/equal sub-expressions, namely the pointer-equal ones. In all of my code-generating (deep) DSLs, it's been very important for efficiency to also pull out equal-but-pointer-unequal expressions. - Conal On Thu, Aug 11, 2011 at 4:41 AM, Vo Minh Thu not...@gmail.com wrote: I guess you refer to data-reify: http://hackage.haskell.org/package/data-reify 2011/8/11 Stephen Tetley stephen.tet...@gmail.com: Strafunski and its successors (Uniplate, SYB, KURE) are really for working on trees. If you want to work on graphs you would probably be better of with something else. I think I overlooked that you want common sub-expression _elimination_, rather than expression simplification. There are libraries for observable sharing (Andy Gill's recent one is the state-of-the-art, its on Hackage but I've forgotten its name) - that are pertinent where you have built the expressions as an embedded DSL in Haskell and you want sharing in code you generate from the Haskell DSL. On 11 August 2011 08:57, Anton Kholomiov anton.kholom...@gmail.com wrote: Thank you for the reference to Strafunski libraries, I read HaskellWiki, but I don't have a permission to visit their site. All links are forbidden. Can it be a function: fun :: Eq a = Tree a - [(Int, (a, [Int]))] where tuple codes nodes, and Int's code edges. 2011/8/11 Stephen Tetley stephen.tet...@gmail.com Wouldn't this be dependent upon your AST and thus not readily package-able as a library? Expression simplification has been a prime example for Strafunski style traversal libraries. You might be able to find examples that you can adapt to your own AST written with Uniplate or similar library. On 11 August 2011 05:00, Anton Kholomiov anton.kholom...@gmail.com wrote: Is there a library on common sub-expression elimination? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] fyi GHC 7.2.1 release on the benchmarks game
On Fri, 2011-08-12 at 11:44 -0500, austin seipp wrote: 2) I noticed `-fvia-C` has now gone away [...] I can't forsee the potential performance ramifications, but frankly -fvia-C has been deprecated/not-advised-for-use for quite a while now, and I wonder how many of these programs just have not been updated/tested with the native code generator since they were written. In any case it's not an option anymore, so your only choice is to nuke it from orbit (orbit being the Makefiles.) Well, the better option would be to try with the NCG, and also with LLVM (the -fllvm flag). While the NCG is certainly competitive for idiomatic Haskell code, it's likely to be a bit behind when it comes to heavy C-in-Haskell code like what often gets submitted to the shootout. LLVM seems likely to do better in some cases. -- Chris ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] fyi GHC 7.2.1 release on the benchmarks game
On 12.08.2011 18:44, austin seipp wrote: Hello Isaac, On Fri, Aug 12, 2011 at 10:18 AM, Isaac Gouyigo...@yahoo.com wrote: 1) Some of the GHC programs contributed to the benchmarks game have problems with recent GHC releases - meteor-contest #5 - Ambiguous occurrence `permutations' http://shootout.alioth.debian.org/u64q/program.php?test=meteorlang=ghcid=5#log This can be fixed by changing the line: import Data.List to: import Data.List hiding (permutations) ... and enabling the warning -fwarn-missing-import-lists in order to be warned about such imports ... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] fyi GHC 7.2.1 release on the benchmarks game
--- On Fri, 8/12/11, austin seipp a...@hacks.yi.org wrote: Thanks, I do like easy fixes :-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] library on common sub-expression elimination?
yes. On Fri, Aug 12, 2011 at 11:02 AM, Anton Kholomiov anton.kholom...@gmail.com wrote: Do you mean that x and y in x = a + 1 y = a + 1 are different from data-reify point of view? 2011/8/12 Conal Elliott co...@conal.net Note that data-reify will only find *some* common/equal sub-expressions, namely the pointer-equal ones. In all of my code-generating (deep) DSLs, it's been very important for efficiency to also pull out equal-but-pointer-unequal expressions. - Conal On Thu, Aug 11, 2011 at 4:41 AM, Vo Minh Thu not...@gmail.com wrote: I guess you refer to data-reify: http://hackage.haskell.org/package/data-reify 2011/8/11 Stephen Tetley stephen.tet...@gmail.com: Strafunski and its successors (Uniplate, SYB, KURE) are really for working on trees. If you want to work on graphs you would probably be better of with something else. I think I overlooked that you want common sub-expression _elimination_, rather than expression simplification. There are libraries for observable sharing (Andy Gill's recent one is the state-of-the-art, its on Hackage but I've forgotten its name) - that are pertinent where you have built the expressions as an embedded DSL in Haskell and you want sharing in code you generate from the Haskell DSL. On 11 August 2011 08:57, Anton Kholomiov anton.kholom...@gmail.com wrote: Thank you for the reference to Strafunski libraries, I read HaskellWiki, but I don't have a permission to visit their site. All links are forbidden. Can it be a function: fun :: Eq a = Tree a - [(Int, (a, [Int]))] where tuple codes nodes, and Int's code edges. 2011/8/11 Stephen Tetley stephen.tet...@gmail.com Wouldn't this be dependent upon your AST and thus not readily package-able as a library? Expression simplification has been a prime example for Strafunski style traversal libraries. You might be able to find examples that you can adapt to your own AST written with Uniplate or similar library. On 11 August 2011 05:00, Anton Kholomiov anton.kholom...@gmail.com wrote: Is there a library on common sub-expression elimination? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] type-class inference
Hi, Why does the Haskell :type command only sometimes print the type-class? Should I expect type-class inference as well as type inference? Maybe the type-class is inferred where possible, but not always printed? Thanks, Pat -- Code k x = x + 3 data T = T class A a where g::a - a g a = a instance A T where instance A Integer where -- The results from the above code. -- First in the case of a function. Inferred the Num class *Main :t k k :: forall a. (Num a) = a - a *Main :t k 3 k 3 :: forall t. (Num t) = t -- Did not print type class *Main :t k (3::Integer) k (3::Integer) :: Integer -- Second in the case of a method of a type class. -- Inferred Num *Main :t g 3 g 3 :: forall t. (A t, Num t) = t -- Did not print class A. *Main :t g T g T :: T -- Did not print any class. *Main :t g (3::Integer) g (3::Integer) :: Integer This message has been scanned for content and viruses by the DIT Information Services E-Mail Scanning Service, and is believed to be clean. http://www.dit.ie ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] type-class inference
On Fri, 2011-08-12 at 23:52 +0100, Patrick Browne wrote: -- Second in the case of a method of a type class. -- Inferred Num *Main :t g 3 g 3 :: forall t. (A t, Num t) = t -- Did not print class A. *Main :t g T g T :: T -- Did not print any class. This is because you already know that T is T. The compiler has checked that T is, in fact, an instance of A, but it need not tell you so because it has information that's strictly more specific than that. *Main :t g (3::Integer) g (3::Integer) :: Integer Same thing. Integer is an instance of A, so telling you it's an Integer is even better (more specific). -- Chris Smith ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] type-class inference
On Fri, Aug 12, 2011 at 18:52, Patrick Browne patrick.bro...@dit.ie wrote: Why does the Haskell :type command only sometimes print the type-class? Haskell infers the most specific type applicable. If the most specific it can get is a typeclass, that's what it produces; if it can infer an explicit type, it will. Should I expect type-class inference as well as type inference? Maybe the type-class is inferred where possible, but not always printed? Typeclasses are not independent of types, and are not inferred separately from types. If you want to know what typeclasses a type is a member of, use :info. Haskell supports polymorphism: a bound expression does not need to have a single specific type, it can apply to multiple types and adapt itself to the type at its use site. Typeclasses are part of how this is accomplished. So if a bound expression is polymorphic, you will see its type expressed in terms of type variables, possibly with typeclass contexts. -- brandon s allbery allber...@gmail.com wandering unix systems administrator (available) (412) 475-9364 vm/sms ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] type-class inference
On Fri, Aug 12, 2011 at 19:08, Brandon Allbery allber...@gmail.com wrote: On Fri, Aug 12, 2011 at 18:52, Patrick Browne patrick.bro...@dit.iewrote: Why does the Haskell :type command only sometimes print the type-class? Haskell infers the most specific type applicable. If the most specific it can get is a typeclass, that's what it produces; if it can infer an explicit type, it will. By the way, a possible source of confusion here is the combination of the monomorphism restriction and defaulting, especially GHCi's extended defaulting. The monomorphism restriction says that if you don't provide a way to *easily* infer a type for a binding (in practice this means there are no parameters), Haskell insists that the binding is not polymorphic unless you explicitly provide a type signature. Defaulting is how it accomplishes this: there is a list of default types that can be applied when a concrete type is required and none is available, and the first one that typechecks is used. The Haskell standard specifies Double and Integer as default types; GHCI's extended defaulting (or GHC in general with -XExtendedDefaultRules) adds () aka unit. So, for example, something that you might expect to be (Num a = a) may end up being Integer due to the monomorphism restriction requiring a concrete type and defaulting supplying one. (There's a widely expressed sentiment that the monomorphism restriction should go away because the confusion it engenders is worse than the problems it solves; on the other hand, GHC recently added a new application of it (monomorphic pattern bindings). In any case, if you want to play around with types in GHCi, you may want to :set -XNoMonomorphismRestriction -XNoMonoPatBinds so you can see how types actually behave in the wild.) -- brandon s allbery allber...@gmail.com wandering unix systems administrator (available) (412) 475-9364 vm/sms ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] library on common sub-expression elimination?
On 8/12/11 12:52 PM, Anton Kholomiov wrote: Just to make it explicit, is it \a i - let t = a ! i in if i= 0 then t else if i 0 then t + a ! (i-1) else bad idea, because of last else-case? Can it be mended with one another pass for if-expressions? Lifting the computation out of the guards preserves the semantics of the original program only if: (a) you can guarantee that it has no observable effects (i) this clearly precludes nontermination (ii) this also precludes it taking any non-zero measurable length of time to compute (or memory, or any other observable resource) or (b) you can guarantee that the computation is executed in every possible execution path from the point to which the computation is lifted (including all exceptional paths); moreover, you can guarantee that all observable effects generated prior to the original sites of the computation are identical along all paths. The reason for including (a)(ii) is that, if the computation takes a non-zero measurable length of time, then we can detect a difference between the original and the modified program whenever the computation does not adhere to condition (b). This is notable for performance reasons, but, more importantly, it's critical for the semantics of security. The relative time taken by different branches of a computation is an observable effect which could allow the informational content of secret variables[1] to leak out and be discovered. It is only valid to ignore (a)(ii) when the semantics you're preserving explicitly exclude concerns with program execution time, memory, security, etc., by assuming/pretending that these things aren't observable. [1] In this case, information about the value of i, and possibly additional things in the trailing else case. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] library on common sub-expression elimination?
On 8/12/2011 10:30 AM, Conal Elliott wrote: Note that data-reify will only find *some* common/equal sub-expressions, namely the pointer-equal ones. In all of my code-generating (deep) DSLs, it's been very important for efficiency to also pull out equal-but-pointer-unequal expressions. - Conal data-reify-cse (http://hackage.haskell.org/package/data-reify-cse) by Sebastiaan Visser performs cse for graphs generated by Andy's data-reify. -Levent. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] library on common sub-expression elimination?
in let t= a!i a!i might be out of bounds ?
On Fri, Aug 12, 2011 at 9:52 AM, Anton Kholomiov
anton.kholom...@gmail.comwrote:
Just to make it explicit, is it
\a i -
let t = a ! i in
if i = 0 then
t
else if i 0 then
t + a ! (i-1)
else
bad idea, because of last else-case? Can it be mended with
one another pass for if-expressions?
The upcoming distilled tutorial at DSL 2011 - thank you for the link.
I'm going to experiment with data-reify, while the library you've mentioned
is
OCaml only.
2011/8/12 o...@okmij.org
I guess you mean the function that converts an abstract syntax tree to
a directed acyclic graph (DAG).
Just for completeness I should mention that if the object language has
effects including non-termination, one has to be careful eliminating
seemingly common expressions. For example, in
\a i -
if i = 0 then
a ! i
else if i 0 then
a ! i + a ! (i-1)
else
we see the expression (a ! i) repeated in both branches of
the conditional. Eliminating the `duplicate' by pulling it out
\a i -
let t = a ! i in
if i = 0 then
t
else if i 0 then
t + a ! (i-1)
else
would be wrong, wouldn't it?
This issue has been extensively investigated in the Fortran compiler
community; Elliott, Finne and de Moor's ``Compiling Embedded Languages''
(JFP 2003) talks about it at length.
The standard technique to detect occurrences of common subexpressions
is so-called hash-consing. There are (OCaml) libraries for it:
author= {Jean-Christophe Filli{\^a}tre and Sylvain Conchon},
title = {Type-Safe Modular Hash-Consing},
pages = {12--19},
crossref = ml2006,
doi = 10.1145/1159876.1159880,
The upcoming distilled tutorial at DSL 2011
http://dsl2011.bordeaux.inria.fr/index.php?option=com_contentview=articleid=2Itemid=2
will present a Haskell library for hash-consing. The library can work
with the standard Haskell Hash-tables or without them (using Data.Map,
for example). The library does _not_ rely on Stable names and other
internal GHC operations with unstable semantics. The library will find
all common sub-expressions.
Incidentally, despite the Lisp-sounding name, hash-consing was
invented before Lisp. It was described, for the English audience, in
the first volume of Comm. ACM, in 1958:
@Article{ Ershov-hash-consing,
author= {A. P. Ershov},
title = {On programming of arithmetic operations},
journal = Communications of the {ACM},
year = 1958,
volume= 1,
number= 8,
pages = {3--6},
doi =10.1145/368892.368907,
url = http://portal.acm.org/citation.cfm?id=368907;
}
The translation is quite accurate, as far as I could see, but misses
the flowcharts and the diagram of the original paper. This short paper
fully describes what we now call hash tables, hash functions, useful
properties of hash functions, and hash-consing. The article analyzes
the time complexity of the algorithm. Since the algorithm has two
exits, writing programs in the continuation-passing style must have been
familiar back then.
The library to be presented at DSL 2011 unwittingly follows Ershov's
algorithm closely. The library is (hopefully) better described (see
the preface to the English translation of Ershov's paper). Nowadays,
starting a paper with the phrase ``All unexplained terms are those
from [1]'' (where [1] is the single reference) would not be taken
kindly by reviewers.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
