Re: Maps, was Re: GHC source code improvement ideas
Christian Maeder wrote: Simon Marlow wrote: Regarding Data.Map, I'd be interested in trying out AVL trees instead, to see if they have better performance, but then we'd have to import the code of course. Surely, we want the best maps possible for ghc and as public library (and minimize maintenance). The problem is to agree on a suitable interface. I would suggest to take (or only slightly change) Daan's interface (the current Data.Map) and improve the underlying implementation possibly using (i.e. Adrian Hey's) AVL trees. The trouble is as far as implementations is concerned the best maps possible is a continually moving target I suspect, not to mention being highly dependent on key type. I certainly wouldn't say AVL tree based Maps are best possible, though they do seem give better performance (particularly for union, intersection etc..). The clone also address some defects in the current Data.Map (like lack of strictness control) and has some other useful stuff. But if this is going to be used at all, I would say this is only a stop gap solution, which leads me to your second point about interfaces. The generalised trie lib I was working on was a serious attempt to see what a real useable non-toy map API should look like. It's the GT class here.. http://code.haskell.org/collections/collections-ghc6.8/Data-Trie-General/Data/Trie/General/Types.hs (Sorry for the long URL). It's already somewhat huge and still incomplete IMO, but even in it's current form it gives a uniform API for Ints, arbitrary Ord instances and Lists. It's a shame it's all completely untested :-( What really needs to happen on this is.. 1 - Finish and stabilise the GT class definition. There's still more that's needed but I think the promised type families magic is needed first. 2 - Write a comprehensive test/benchmarking suite for GT instances. 3 - Provide some way to automatically generate the instances for arbitrary user defined types. Which is all rather a lot of work that nobody seems very interested in :-( Regards -- Adrian Hey ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Rank-2 polymorphism and pattern matching
On Jan 4, 2008 5:15 AM, Simon Peyton-Jones [EMAIL PROTECTED] wrote:
| The following won't compile for me
|
| isnull :: (forall a . [a]) - Bool
| isnull ([] :: forall b . [b]) = True
|
| Couldn't match expected type `forall b. [b]'
| against inferred type `[a]'
| In the pattern: []
This is a pretty strange thing to do, to match a polymorphic argument against
a data constructor. I guess you'd expect this to work too, perhaps?
f :: forall a. (forall b. Either a b) - a
f (Left x) = x
I grant that arguably these should work, but I think it'd be quite tricky to
make it do so, because it'd involve re-generalising in the pattern.
Furthermore, I can't see any use for it. Just remove the type signature from
the pattern.
One could argue that it's a bad sign that the pattern typechecker should have
difficulty with this. But until it turns out to be important I'm not going
to lose sleep over it!
This is literate Haskell. It's in the LaTeX style, since my mail
reader won't change the quoting mark from ''. It is not a valid LaTeX
file.
My reason for wanting pattern matching on values of polymorphic types
is a kind of first-level refinement types. I'm going to demonstrate
using the risers function, as presented in Dana N. Xu's ESC/Haskell
(http://research.microsoft.com/Users/simonpj/papers/verify/escH-hw.ps
or http://www.cl.cam.ac.uk/~nx200/research/escH-hw.ps ), which
references Neil Mitchell's Catch
(http://www-users.cs.york.ac.uk/~ndm/catch/ ). I'll also be
referencing an example from Tim Freeman's thesis on refinement types
for ML (http://www.cs.ucla.edu/~palsberg/tba/papers/freeman-thesis94.pdf
)
\begin{code}
{-# OPTIONS -fglasgow-exts #-}
-- The LANGUAGE pragma is usually a pain for exploratory programming.
\end{code}
This is the risers function, as presented by Xu. It returns the sorted
sublists of a list. None of the lists in the return value are empty,
and if the argument is non-empty, the return value is also non-empty.
\begin{code}
risersXu :: (Ord t) = [t] - [[t]]
risersXu [] = []
risersXu [x] = [[x]]
risersXu (x:y:etc) =
let ss = risersXu (y : etc)
in case x = y of
True - (x : (head ss)) : (tail ss)
False - ([x]) : ss
\end{code}
Xu uses head and tail. These are safe here by a proof created by ESC/Haskell.
Here is the risers function according to Mitchell:
\begin{code}
risersMitchell :: Ord a = [a] - [[a]]
risersMitchell [] = []
risersMitchell [x] = [[x]]
risersMitchell (x:y:etc) = if x = y
then (x:s):ss
else [x]:(s:ss)
where (s:ss) = risersMitchell (y:etc)
\end{code}
The unsafe part here is the pattern in the where clause. Mitchell
presents a tool to prove this safe.
These unsafe operations depend on the second property of the function:
non-null inputs generate non-null outputs. We could write a type for
this functions using a trusted library with phantom types for branding
(http://okmij.org/ftp/Computation/lightweight-dependent-typing.html ).
This technique (called lightweight static capabilities) can do this
and much else, as well, but clients lose all ability to pattern match
(even in case). We could also write a type signature guaranteeing this
by using GADTs. Without either one of these, incomplete pattern
matching or calling unsafe head and tail on the result of the
recursive call seems inevitable.
Here's another way to write the function which does away with the need
for second property on the recursive call, substituting instead the
need for the first property, that no lists in the return value are
empty:
\begin{code}
risersAlt :: (Ord t) = [t] - [[t]]
risersAlt [] = []
risersAlt (x:xs) =
case risersAlt xs of
[] - [[x]]
w@((y:ys):z) -
if x = y
then (x:y:ys):z
else ([x]):w
([]:_) - error risersAlt
\end{code}
The error is never reached.
Though ensuring the second property with our usual types seems tricky,
ensuring the first is not too tough:
\begin{code}
type And1 a = (a,[a])
risersAlt' :: Ord a = [a] - [And1 a]
risersAlt' [] = []
risersAlt' (x:xs) =
case risersAlt' xs of
[] - [(x,[])]
w@(yys:z) -
if x = fst yys
then (x,fst yys : snd yys):z
else (x,[]):w
\end{code}
It is now much easier to see that risers is safe: There is one pattern
match and one case, and each is simple. No unsafe functions like head
or tail are called.
It does have two disadvantages. First, the second property is still
true, but the function type does not enforce it. This means that any
other callers of risers may have to use incomplete pattern matching or
unsafe functions, since they may not be so easy to transform. It is my
intuition that it is not frequently the case that these functions are
tricky to transform, but perhaps Neil Mitchell disagrees. We could fix
this by writing another risers function with type And1 a - And1 (And1
a), but this brings us to the
Re: binary-dists for ghc-6.8.2
Hi Chris, On Sat, Jan 05, 2008 at 03:38:58PM -0500, Chris Saunders wrote: Will there be a binary release for Windows x86_64? Unfortunately not in the near future; see this ticket for more details: http://hackage.haskell.org/trac/ghc/ticket/1884 Thanks Ian ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: GHC 6.8.1 port on FreeBSD-amd64?
On Fri, Jan 04, 2008 at 09:54:45PM +0100, Matthias Kilian wrote: [Note: already shortly discussed with Wilhelm] On Fri, Nov 23, 2007 at 12:30:06PM +, Wilhelm B. Kloke wrote: ../../compiler/stage1/ghc-inplace -package-name unix-2.2.0.0 -hide-all-packages -i -idist/build/autogen -idist/build -i. -Idist/build -Iinclude -#include HsUnix.h -#include execvpe.h -odir dist/build -hidir dist/build -stubdir dist/build -package base-3.0.0.0 -package directory-1.0.0.0 -O -XCPP -XForeignFunctionInterface -idist/build -H32m -O0 -fasm -Rghc-timing -keep-hc-files -O -c dist/build/System/Posix/Process.hs -o dist/build/System/Posix/Process.o -ohi dist/build/System/Posix/Process.hi Prologue junk?: .type s32x_ret, @function s32x_ret: pushl %ebp movl%esp, %ebp I see nearly the same problem with ghc-6.8.2 on OpenBSD, using the gcc-3.3.5 included in its base system. Presumably this also happens if you do a normal build with -fvia-C, i.e. it's not specific to building from an HC file bundle? [1] BTW: what's the point of using -fasm with -keep-hc-files? IMHO, it should be -fviaC -keep-hc-files. Someone let me know if I should correct this in the wiki. GHC will act as if -fvia-C is given if -keep-hc-files is given. It would be nice to update the wiki to say -fvia-C rather than -fasm to avoid confusion, though. ps: yes, I'm slowly trying to bring HC bootstrap back to work. It's a must-have for the OpenBSD port. Note that there is a plan to drop the registerised via-C way of compiling GHC at some point, so this isn't going to work in the long term (unless you want to bootstrap via an unregisterised compiler). Would it not be possible to have a ghc-bin package in OpenBSD, which contains a precompiled binary that can be used to compile a ghc source package? I think Gentoo does something like that. pps: I guess, cvs-ghc would be the more correct list for sending patches and discussing the bootstrapping stuff, right? Yup. Thanks Ian ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: GHC 6.8.1 port on FreeBSD-amd64?
On Sun, Jan 06, 2008 at 05:20:18PM +, Ian Lynagh wrote: Prologue junk?: .type s32x_ret, @function s32x_ret: pushl %ebp movl%esp, %ebp I see nearly the same problem with ghc-6.8.2 on OpenBSD, using the gcc-3.3.5 included in its base system. Presumably this also happens if you do a normal build with -fvia-C, i.e. it's not specific to building from an HC file bundle? That's right, it's just -fvia-C that triggers the bug. [1] BTW: what's the point of using -fasm with -keep-hc-files? IMHO, it should be -fviaC -keep-hc-files. Someone let me know if I should correct this in the wiki. GHC will act as if -fvia-C is given if -keep-hc-files is given. It would be nice to update the wiki to say -fvia-C rather than -fasm to avoid confusion, though. Done. ps: yes, I'm slowly trying to bring HC bootstrap back to work. It's a must-have for the OpenBSD port. Note that there is a plan to drop the registerised via-C way of compiling GHC at some point, so this isn't going to work in the long term (unless you want to bootstrap via an unregisterised compiler). I think I'll be happy with unregisterised bootstrap, too, even if the actual build of the port will take longer. Would it not be possible to have a ghc-bin package in OpenBSD, which contains a precompiled binary that can be used to compile a ghc source package? I think Gentoo does something like that. AFAIK, FreeBSD does it in a similar way. However, this isn't the way we do ports for OpenBSD, so I'll work towards the unregisterised bootstrap. Ciao, Kili ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: GHC Core question
On 1/5/08, Neil Mitchell [EMAIL PROTECTED] wrote:
Hi
I've compiled the Debug.Trace module to Core, but can't understand the
resulting output. The original code is:
trace string expr = unsafePerformIO $ do
putTraceMsg string
return expr
The core is:
Debug.Trace.trace =
\ (@ a) -
__letrec {
trace :: GHC.Base.String - a - a
[]
trace =
\ (string :: GHC.Base.String) (expr :: a) -
GHC.Base.$
@ (GHC.IOBase.IO a)
@ a
(GHC.IOBase.unsafePerformIO @ a)
( @ () @ a (Debug.Trace.putTraceMsg string) (return @ a expr));
$dMonad :: GHC.Base.Monad GHC.IOBase.IO
[]
$dMonad = $dMonad;
return :: forall a. a - GHC.IOBase.IO a
[]
return = GHC.Base.return @ GHC.IOBase.IO $dMonad;
$dMonad :: GHC.Base.Monad GHC.IOBase.IO
[]
$dMonad = GHC.IOBase.$f16;
:: forall a b.
GHC.IOBase.IO a - GHC.IOBase.IO b - GHC.IOBase.IO b
[]
= GHC.Base. @ GHC.IOBase.IO $dMonad;
} in trace;
And my Haskell reformatting of that is:
Debug.Trace.trace = let
trace string expr = unsafePerformIO $ putTraceMsg string return expr
$dMonad = $dMonad;
return = GHC.Base.return $dMonad;
$dMonad = GHC.IOBase.$f16;
= GHC.Base. $dMonad;
in trace
However, that let expression has two bindings for $dMonad, one of
which looks like a black-hole. Are the semantics of __letrec different
from let in some way?
How are you printing out the Core? It looks like the unique ids are
missing (you can see them if you pass the -ppr-debug flag, which can
be set using the API) -- if the unique ids were being printed, you
would see that the bindings for $dMonad (likely) have different
uniques.
Cheers,
Tim
--
Tim Chevalier * http://cs.pdx.edu/~tjc * Often in error, never in doubt
...Losing your mind, like losing your car keys, is a real hassle. --
Andrew Solomon
___
Glasgow-haskell-users mailing list
Glasgow-haskell-users@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Module system, was Re: GHC source code improvement ideas
Johannes Waldmann wrote: Brian Hulley wrote: In the long term, Haskell needs a better module system IMHO [...] I agree with the symptoms that were described, but I draw a different conclusion. We don't need to change the language - we need better tools (IDEs) that operate not at the textual level, but use the annotated syntax tree, including knowledge on fully qualified names and types. Hi Johannes, I agree that better tools would be a good thing, and could improve the programming experience considerably, but I still think that an improved module system design would be an orthogonal benefit. Best regards, Brian. ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: GHC 6.8.1 port on FreeBSD-amd64?
Matthias Kilian [EMAIL PROTECTED] schrieb: On Sun, Jan 06, 2008 at 05:20:18PM +, Ian Lynagh wrote: Prologue junk?: .type s32x_ret, @function s32x_ret: pushl %ebp movl%esp, %ebp I see nearly the same problem with ghc-6.8.2 on OpenBSD, using the gcc-3.3.5 included in its base system. Presumably this also happens if you do a normal build with -fvia-C, i.e. it's not specific to building from an HC file bundle? That's right, it's just -fvia-C that triggers the bug. This is not quite the case. I compiled even with -fvia-C without errors on FreeBSD-amd64. This bug is specific for the bootstrap with crosscompiling i386 - amd64 vi .hc-bundle. -- Dipl.-Math. Wilhelm Bernhard Kloke Institut fuer Arbeitsphysiologie an der Universitaet Dortmund Ardeystrasse 67, D-44139 Dortmund, Tel. 0231-1084-257 PGP: http://vestein.arb-phys.uni-dortmund.de/~wb/mypublic.key ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
