Need help with GHC API and GHC internals
I'm attempting to write a call-graph generator for Haskell using the GHC API. I.e., for each top level value definition, I want a list of the top-level names used in the definition. Using GHC API, once I have a 'CheckedModule', I have a dilemma: a) If I use this field parsedSource :: ParsedSource I've got a giant AST that I need to traverse for names, there being no help in the compiler to do so, AFAIK. b) If I use this field coreBinds :: Maybe [CoreBind] although I've got a simpler type to deal with, and some useful functions (e.g. exprFreeNames), I believe I'm now swimming in waters a bit deep for me or maybe this is just a flawed approach: - the core bindings created do not correspond exactly to the bindings in the source and 'exprFreeNames' is acting in surprising ways. - etc, etc. Does anyone have any advice for me here? Is there some way I can get approach (b) to work without becoming a wizard in GHC internals? Is there anything I'm missing? Thanks, Mark ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: [Haskell] Views in Haskell
On Jan 26, 2007, at 6:22 PM, Claus Reinke wrote:
2) There are other reasons why I want to use Haskell-98 and
would like to be able to use other compilers. Thus, I'd want a
pattern-binder preprocessor (extending GHC is not as important to
me).
I see. though I'd hope that as long as we keep our extensions
simple and
general enough, the other implementations will pick them up anyway.
Here's my motivating example. Here's a fragment for an STG
interpreter in Haskell-98:
{{{
rule_CASE_ELIM (Case p alts, s, h, o) =
do
ConApp c as - ptsTo p h
let matchAlt (Alt c' vs e) | c == c' = Just (vs,e)
matchAlt _ = Nothing
(vs,e) - matchFirst matchAlt alts
return (e `sub` (vs,as), s, h, o)
}}}
yes, abstract machines have inspired many a pattern match extension!-)
are we in Maybe, or in anything more complex?
Yep, just Maybe.
view patterns don't seem to apply, but pattern guards do, and
lambda-match helps with the local function pattern (ignoring the
Match type tag for the moment; given the revival of interest in
pattern functions, eg., in view patterns, I ought to try and see
whether I can get rid of the type tag in my library for the special
case of Maybe):
{{{
rule_CASE_ELIM =
(| (Case p alts, s, h, o)| ConApp c as - ptsTo p h
, (vs,e) - matchFirst (| (Alt c' vs e) | c == c' -(vs,e) )
alts
- (e `sub` (vs,as), s, h, o) )
}}}
which isn't quite as abstract as the pattern binder/combinator
version,
but at least I can see the scoping,
Thanks for showing how it looks with lambda-match, I see that lambda-
matches use
more than patterns, they use guards too.
which I am at a loss with in the pattern
binder version:
I'd like it to have a textual form just a little more abstract, I
can do that with pattern binders and some appropriate combinators:
{{{
rule_CASE_ELIM =
{ (Case p alts, s, h, o) }
ptsTo p h === { ConApp c as }
alts === matchFirst { Alt #c vs e }
.-
(e `sub` (vs,as), s, h, o)
}}}
I'll leave it as an exercise to figure out how the last is
parenthesized ;-).
ok, I give up. there seem to be some new combinators,
yes, but nothing fancy:
() :: (a - Maybe b) - (b - Maybe c) - a - Maybe c
() = (.:) -- as in the paper
(===) :: a - (a - Maybe b) - Maybe b
(===) a p = p a
and the pattern binder variables are no longer distinguishable (via
$).
In this example I'm dropping the $: it's less clear what's going on
but it looks cleaner,
more like Haskell patterns.
but unless you've changed the translation as well, the only way the
scopes are going to come out right is if the layout is a lie, right?
The layout /is/ a lie :-( but the scope rule is pretty simple: in
this expression
{p} `op` e
everything bound in p scopes over all e.
So, all the variables in the {p}'s above scope to the end of the RHS
expression.
and how does the translation apply to pattern binders not in an
infix application, in particular, how do vs/e get to
the rhs of .-?
Claus
All the pattern binders here /are/ in an infix application, here's
the parenthesized version:
{{{
rule_CASE_ELIM =
{ (Case p alts, s, h, o) }
(ptsTo p h == { ConApp c as }
(alts === (matchFirst ({ Alt #c vs e }
.-
(e `sub` (vs,as), s, h, o)
}}}
(Oops, I see I'm using # where in the paper I used =.)
I also fixed a type error (nothing like ghci to fix some design
problems), I'm now using
an additional (rather simple) combinator:
(==) :: Maybe a - (a - Maybe b) - Maybe b
(==) = (=)
- Mark
___
Haskell-prime mailing list
Haskell-prime@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-prime
Re: [Haskell] Views in Haskell
On Jan 25, 2007, at 3:49 AM, Claus Reinke wrote: but as far as Haskell is concerned, I am perhaps less radical in my approach than Mark is: Haskellers have invested an awful lot of work in those conventional patterns, in readibility, in optimisations, and in linking them with other extensions (eg., type system extensions). I actually would agree. The purist in me would want to use a language with a simple exhaustive case construct and pattern-binders and no more; but the pragmatist in me does, usually, go with the flow of the language and use some of the more complex pattern-matching constructs. However, I did edit the web page to include an improved description of First Class Patterns, for a point of reference and comparison. - Mark ___ Haskell-prime mailing list Haskell-prime@haskell.org http://www.haskell.org/mailman/listinfo/haskell-prime
[Haskell] Views in Haskell
Sorry to enter the discussion a little late ... First, I'm not clear what Simon meant by first class abstractions in this comment Several proposals suggest first class abstractions rather that first-class patterns. Here are the ones I know of ... Second, I completely agree with Claus in his comment here that my First Class Patterns paper is definitely related to, and not orthogonal to view patterns: The big idea of my paper was to stop the growing complexity of the pattern-language of Haskell. The idea was to use the abstraction capabilities of the language along with some simple syntactic sugar to give us 'pattern omnipotence'. However, my approach could be seen as orthogonal in that I did not propose to change Haskell patterns. Instead, I suggested some additional syntax that could serve as a replacement for complicated uses of patterns. Strangely, for other reasons, I'm planning, within a week or so, to start implementing the pattern-binder syntax I discussed in the paper (either in GHC or as a pre-processor). - Mark Claus Reinke wrote: 3 what you call first class abstractions are not entirely orthogonal to view patterns. taking Tullsen's and my own proposal as examples: - the way patterns and alternatives are handled needs to fit together. that doesn't seem to be a problem since your and our proposals agree on using what I call a monadic data parsing framework (using a MonadPlus such as Maybe to handle pattern match failure and alternatives) - all three proposals have discussed how to handle patterns as well. For Tullsen, that is central to his proposal, for me, it was only one of the more advanced examples because I wanted to focus on match alternatives first. Tullsen first builds his pattern combinators, then outlines a point-free style that avoids the need for pattern variables althogether but does not seem to scale well, then suggests syntactic sugar for translating patterns with variables into applications of his combinators. So that last part is closely related to, if different from, your proposal. In my example, I build up patterns from de-constructors (which use tests and selectors), so that a cons pattern takes a head pattern and a tail pattern as parameters and applies them to the head and tail if it is applied to a non-empty list. To handle variables, I use an old trick from the early functional logic languages, namely that logic variables can be passed unbound, then bound to values later, just what we need for pattern variables. Since Haskell doesn't have logic variables, I have to simulate them, which is the only awkward bit of the example: http://www.haskell.org/pipermail/haskell-prime/2006-November/ 001915.html as long as Haskell doesn't support logic variables, some syntactic sugar for variables in nested patterns, such as Tullsen's or your's, is probably inevitable. ___ Haskell-prime mailing list Haskell-prime@haskell.org http://www.haskell.org/mailman/listinfo/haskell-prime
Re: [Haskell] Views in Haskell
On Jan 22, 2007, at 6:57 AM, Simon Peyton-Jones wrote: I'm thinking of implementing it in GHC, so I'd be interested in feedback of the form - how desirable is it to have a feature of this general form? While it looks like a useful extension with a lot of bang for the buck, I think I'd prefer to live without it; two reasons: 1) I'm a minimalist 2) I find that using my pattern combinators (http://citeseer.ist.psu.edu/tullsen00first.html) and do-notation I get by very well without using any of the advanced features of patterns. OK, I guess I'm a little biased. - can this particular proposal be improved? I definitely agree with Claus's comment: 5 possible extension 1 smells of superfluous complexity. There is almost no gain compared to using tuples, but there's a lot to pay in added types and rules.m ___ Haskell-prime mailing list Haskell-prime@haskell.org http://www.haskell.org/mailman/listinfo/haskell-prime
Re: [Haskell-cafe] What is MonadPlus good for?
Here's an example: In my paper First Class Patterns http://citeseer.ist.psu.edu/tullsen00first.html, by defining the pattern combinators using MonadPlus, you get standard pattern matching with the Maybe instance of MonadPlus and you get backtracking pattern matching with the [] (list) instance of MonadPlus. - Mark On Feb 12, 2005, at 10:08 AM, Benjamin Pierce wrote: I have seen lots of examples that show how it's useful to make some type constructor into an instance of Monad. Where can I find examples showing why it's good to take the trouble to show that something is also a MonadPlus? (I know there are many examples of things that *are* MonadPluses; what I want to know is why this is interesting. :-) Thanks, - Benjamin ___ 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
Can't use home-grown packages with ghci on Mac OS X
Platform: Mac OS X (10.3.3)
(works fine on Linux)
Ghc Version: 6.2.1
(same error with both
the binary built by Wolfgang Thaller
and version built from source using darwinports)
gcc version: 3.3
Problem:
ghci doesn't work with user generated packages.
Details:
While trying to track down why I'm getting this error message for
a user-built package (which seems a little suspicious):
ghci -package galois
___ ___ _
/ _ \ /\ /\/ __(_)
/ /_\// /_/ / / | | GHC Interactive, version 6.2.1, for
Haskell 98.
/ /_\\/ __ / /___| | http://www.haskell.org/ghc/
\/\/ /_/\/|_| Type :? for help.
Loading package base ... linking ... done.
Loading package haskell98 ... linking ... done.
Loading package lang ... linking ... done.
Loading package concurrent ... linking ... done.
Loading package QuickCheck ... linking ... done.
Loading package readline ... linking ... done.
Loading package unix ... linking ... done.
Loading package posix ... linking ... done.
Loading package util ... linking ... done.
Loading package network ... linking ... done.
Loading package net ... linking ... done.
Loading package galois ...
GHCi runtime linker: fatal error: I found a duplicate definition
for symbol
__module_registered
whilst processing object file
/Users/tullsen/r/gd/src/build/lib/galois.o
This could be caused by:
* Loading two different object files which export the same symbol
* Specifying the same object file twice on the GHCi command line
* An incorrect `package.conf' entry, causing some object to be
loaded twice.
GHCi cannot safely continue in this situation. Exiting now. Sorry.
I created a trivial package and now I get the following (bus error):
$ ghci -package mytest
___ ___ _
/ _ \ /\ /\/ __(_)
/ /_\// /_/ / / | | GHC Interactive, version 6.2.1, for
Haskell 98.
/ /_\\/ __ / /___| | http://www.haskell.org/ghc/
\/\/ /_/\/|_| Type :? for help.
Loading package base ... linking ... done.
Loading package mytest ... Bus error
In both of these cases, I can compile, link, and run without problems.
My files are as follows (also attached as tar file):
--- Makefile ---
libmytest.a: Test.hs
ghc -package-name mytest -c Test.hs
rm libmytest.a
ar qvs libmytest.a Test.o
install: libmytest.a mytest.pkg
rm mytest.o # -g not updating this
ghc-pkg -u -g mytest.pkg
ghc-pkg -s mytest
testghci:
ghci -package mytest Main.hs
testghc:
ghc -o main -package mytest Main.hs
--- Test.hs ---
module Test where
succ2 :: Int - Int
succ2 x = x + 2
--- Main.hs ---
module Main where
import Test
main = print $ succ2 0
--- mytest.pkg ---
Package { name = mytest,
import_dirs = [${PWD}],
source_dirs = [],
library_dirs = [${PWD}],
hs_libraries = [mytest],
extra_libraries = [],
include_dirs = [],
c_includes = [],
package_deps = [base],
extra_ghc_opts = [],
extra_cc_opts = [],
extra_ld_opts = []}
--
Thanks,
- Mark
files.tar
Description: Unix tar archive
___
Glasgow-haskell-bugs mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
when is defaulting supposed to occur?
Note the following program x = 1 y = x :: Int This is accepted by ghc but it is rejected hugs (May 2003 cvs): ERROR IntegerTest.hs:4 - Type error in type annotation *** Term : x *** Type : Integer *** Does not match : Int My guess is that hugs is doing defaulting after a declaration group is type-checked, but that ghci leaves 'x' with type 'Num a', then processes further declaration groups, and then does defaulting. I don't see that the report specifies this (did I miss it?). - Mark ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: learning to love laziness
Haskell has lazy/lifted products and not true products. This feature is considered by many to be an unfortunate aspect of Haskell. A 2-tuple is just syntactic sugar for data Tuple2 a b = Tuple2 a b Maybe from seeing this, it's clearer why laws such as x = (fst x,snd x) do not hold. Neither does the following law hold (uncurry . curry) f = f which is unfortunate (for a language named after Haskell *Curry*). To see why it doesn't hold, compare t1 and t2 in this program: f (_,_) = 1 t1 = f undefined t2 = (uncurry . curry) f undefined - Mark On Wednesday, September 24, 2003, at 02:07 PM, Norman Ramsey wrote: Consider the following Haskell function: asPair x = (fst x, snd x) This function has type forall a b. (a, b) - (a, b) and is almost equivalent to the identity function, except it can be used to make programs terminate that might otherwise fall into a black hole. My students are extremely mystified by such functions---and I can hardly blame them! Is there a good place to read about programming with lazy evaluation that will cover such functions and when to use them? Norman ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
should -fglasgow-exts support Haskell98?
I don't know if ghc -fglasgow-exts should always accept valid Haskell 98 programs. If that is the intention, then here is a bug: The following program is legal Haskell98 (works fine w/ ghc) but gives a parse error with -fglasgow-exts: let _ # _ = 1 in (#) Thanks. BTW, I've just noticed that the :t command in ghci now gives me some very useful information for values without type signatures (when they are in a binding group in which other values have signatures): the names of quantified type variables are nabbed from the other signatures. This is really nice! - Mark ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
bug/feature/? of ghci with concurrency
Maybe this is by design, but in case it isn't: I was a little suprprised when I came across this behavior of ghci: ghci ... GHC Interactive, version 5.04.1, for Haskell 98. ... Prelude :m Concurrent Prelude Concurrent let loop c = putChar c loop c in forkIO (loop 'a') (loop 'z') zazazazazazazazazazazazazazazazazazazazazazazazazazazazazazazazazazazazazaza zazazazazazazazazazazazazazazazazazazazazazazazazazazazazazazazazazazazazaza zazazazazazazazazazazazazazazazazazazazazazazazazazazazazazazazazazazazazaza Interrupted. aPrelude Concurrent sum [1..100] a5050 aPrelude Concurrent 1+2 3 Obviously, loop 'a' has never been terminated and starts running anytime execution is in progress. I might expect that either interrupting the execution would kill *all* processes or that after interrupting loop 'z' that I would still see the loop 'a' executing. This is on 386 Linux. - Mark ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
infinite loop in ghc5.04
When I attempt to compile the following code with ghc 5.04 newtype Server i o = Server (i - (o, Server i o)) machine :: s - ((i,s) - (s,o)) - Server i o machine init next = Server (f init) where f s i = (o, Server (f s')) where (s',o) = next (i,s) I get the following $ ghc -c T.hs stack overflow: use +RTS -Ksize to increase it $ ghc -c T.hs +RTS -K10m stack overflow: use +RTS -Ksize to increase it $ ghc -c T.hs +RTS -K20m stack overflow: use +RTS -Ksize to increase it ... But if I transform the program to the equivalent newtype Server i o = Server (i - (o, Server i o)) machine :: s - ((i,s) - (s,o)) - Server i o machine init next = Server (f next init) f next s i = (o, Server (f next s')) where (s',o) = next (i,s) ghc compiles without a problem. Changing 'newtype' to 'data' also makes the problem go away. This is on a Linux (RH 7.3) machine with an i686 processor. Thanks. - Mark ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: GHC bug,or Hugs feature?
I believe the incompatibilities are explained thus:
In section 4.5.1 of the Haskell Report it only states that
A dependency analysis transformation is first performed to increase
polymorphism
But hugs appears to be using a more refined version of the dependency
analysis as explained in section 11.6.3 of Mark Jones' paper Typing
Haskell in Haskell. Read that section.
- Mark
Arthur Baars wrote:
In Mark Jones' paper Typing Haskell in Haskell, I found the following
example(in the section on binding-groups):
f :: Eq a = a - Bool
f x = x==x || g True
g y = y=y || f True
According to the paper the inferred type of g should be:
g::Ord a = a - Bool
Hugs infers this type but GHC infers the following *ambiguous* type:
*Main :i g
-- g is a variable, defined at Test.hs:25
g :: forall a. (Eq a) = Bool - Bool
When adding an explicit type signature for g, Hugs happily accepts the code,
but GHC gives the following error:
f :: Eq a = a - Bool
f x = x==x || g True
g :: Ord a = a - Bool
g y = y=y || f True
Test.hs:24:
Couldn't match `{Ord a}' against `{Eq a1}'
When matching the contexts of the signatures for
g :: forall a. (Ord a) = a - Bool
f :: forall a. (Eq a) = a - Bool
The signature contexts in a mutually recursive group should all be
identical
When generalising the type(s) for g, f
Failed, modules loaded: none.
I think the problems are caused by differences in the binding group analysis
in Hugs and GHC.
Malcolm, could you check what NHC says about the examples above?
Cheers,
Arthur
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Re: Mutable arrays in Haskell 98
José Romildo Malaquias wrote: ... My attempt was mapIOArray :: Ix ix = (a - b) - IOArray ix a - IO (IOArray ix b) mapIOArray f v = do w - newIOArray bounds mapping w (range bounds) where bounds = boundsIOArray v mapping w (i:is) = do x - readIOArray v i writeIOArray w i (f x) mapping w is mapping w [] = return w But I do not know what to use to replace the . Is there a polymorphic value in Haskell that can be of any type? Yes, use undefined from the Prelude: undefined:: a undefined | False = undefined - Mark ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Haskell report (August release)
Simon, Here's a minor quibble with the organization of the Report and Library, not with the content. Sorry if this has been brought up before. In section 4.3.3, Derived Instances, of the Report there is The only classes in the Prelude for which derived instances are allowed are Eq, Ord, Enum, Bounded, Show, and Read, all mentioned in Figure 5, ... Classes defined by the standard libraries may also be derivable. In the introduction to the Library Report there is Classes defined in libraries may be derivable. This report includes the derivation of such classes when appropriate. Now, unless I missed something, the only class in the Library Report which is derivable is Ix. I would argue for bringing the Ix class into the Report for these reasons * One does not have to search through the Library Report to determine what is derivable. * I think one would expect that the Libraries contain stuff that could be implemented in Haskell by the user. Until Haskell has the ability to allow for user-defined derivable classes, Ix cannot be defined by the user. - Mark ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Why is there a space leak here?
Tom,
I noticed this post after I had just posted my own response.
You have to realize that Alastair Reid is one of the truly
great Haskell programmers on planet earth. I'm serious.
So, when he says incredibly subtle space leak I wouldn't
expect the solution to be simple. As far as I can tell, your
argument would also apply to foo2, which doesn't have a space leak.
I'd be happy to be proven wrong, but I think this space leak
really /is/ subtle and in order to see the problem seems to
require some /tedious/ hand-reductions, taking into account both
the sharing and the strictness properties. See my recent posting
for a very brute-force analysis.
- Mark
Tom Moertel wrote:
Alastair David Reid wrote:
Executive summary: David's program has an incredibly subtle space leak
in it (or I'm being incredibly dumb). I encourage the honchos (and
would be honchos) to have a look. Users of other compilers might give
it a shot too.
David Bakin wrote:
Why is there a space leak in foo1 but not in foo2?
The reason that foo1 leaks space is because the middle of v grows
faster than its head. So taking elements from v causes its in-memory
footprint to grow. To see why this is the case, evaluate foo1 by hand:
-- This has a space leak, e.g., when reducing (length (foo1 100))
foo1 m
= take m v
where
v = 1 : flatten (map triple v)
triple x = [x,x,x]
Focusing on just v for now, and letting f = flatten for notation
purposes, we have
(1) v = 1 : f (map triple v)
(2) = { unwrap v }
1 : f (map triple (1 : f (map triple v)))
(3) = { eval map }
1 : f (triple 1 : map triple (f (map triple v)))
(4) = { eval triple }
1 : f ([1,1,1] : map triple (f (map triple v)))
(5) = { eval f (= flatten = foldr (++) []) }
1 : 1 : 1 : 1 : f (map triple (f (map triple v
In order to expose elements 2-4 of v, we had to evaluate v to the extent
that the overall expression held in memory *grew*. Notice how in (1) we
had a single (f (map triple ...)) expression in the tail of v but in (5)
there are two such expressions, nested.
Continuing further, if we want to expose the 5th-7th elements of v, we
have to expand the expression yet even more. Noticing that the (f (map
triple v)) subexpression in (5) is identical to the tail of (1), we can
apply the same expansion that we derived in (1)-(5) to yield
(6) = { repeat (1)-(5) for f (map triple v) in (5) }
1 : 1 : 1 : 1 :
f (map triple (1 : 1 : 1 :
f (map triple (
f (map triple v)))
(7) = { eval map }
1 : 1 : 1 : 1 :
f (triple 1 : map triple (
f (map triple (
f (map triple v
(8) = { eval triple }
1 : 1 : 1 : 1 :
f ([1,1,1] : map triple (
f (map triple (
f (map triple v
(9) = { eval f }
1 : 1 : 1 : 1 : 1 : 1 : 1 :
f (map triple (
f (map triple (
f (map triple v)
Notice how in (9) we have three nested (f (map triple (...)))
expressions in the tail of v whereas in (5) we had only two and in (1)
we had but one?
Now you can see why foo1 has a space leak: In order to take the Nth
element of v, v's definition must be expanded to the point where there
are 1+(N+1)/3 (f (map triple (...))) subexpressions in the tail of v
*that will never be reached*. In other words, v's middle grows faster
than its head, ensuring that take will never consume the tail. Taking
elements from the head only makes the middle grow larger. The more your
take, the larger it grows.
So the problem isn't Hugs but rather the definition of v, which grows
faster than it can be consumed.
Cheers,
Tom
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Re: Why is there a space leak here?
Tom Moertel wrote: Mark Tullsen wrote: You have to realize that Alastair Reid is one of the truly great Haskell programmers on planet earth. I'm serious. So, when he says incredibly subtle space leak I wouldn't expect the solution to be simple. Whoops. Now don't I feel foolish. As far as I can tell, your argument would also apply to foo2, which doesn't have a space leak. Hmmm... Let's see. foo2 m = take m v where v = 1 : flatten (map single v) single x = [x] v = 1 : flatten (map single v) = 1 : flatten (map single (1 : flatten (map single v))) = 1 : flatten (single 1 : map single (flatten (map single v))) = 1 : flatten ([1] : map single (flatten (map single v))) = 1 : 1 : flatten (map single (flatten (map single v))) = Aaaarrh! You're right. Now don't I feel double foolish. :P Okay, then, what is the *right* way to reason about these things? Cheers, Tom Tom, I don't know if this approach is the *right* way but it's one way. This approach is very brute force, and I'm sure there are experts out there who can think and reason at a much higher level than this. But the brute force approach is this: Start evaluating your program symbolically You can do this at the source level using a CBN (call-by-need) calculus. If the program (the program in CBN includes the heap) starts growing in size faster than expected then you have a space leak. Simple, but a bit tedious. It would be great if we had a tool that could output such a trace. - Mark ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Haskell 98 Report
Simon Peyton-Jones wrote: Folks I've finished what I hope is the final version of the Haskell 98 Language and Library Reports http://research.microsoft.com/~simonpj/haskell98-revised However, experience shows that bug fixes are often themselves buggy, so I urge you, once again, to take a look at your favourite passages and check they are correct. As ever, there's a complete list of changes at the above URL, with the ones I've made since the April release identified for your pleasure. Comments (hopefully vanishingly few) by 15 June please. Simon, Sorry to get this comment in so late, but it is a small change. In the List module, the type signature for deleteBy is not as general as it could be, given the definition. It could be generalized to the following (no change to the definition): deleteBy :: (a - b - Bool) - a - [b] - [b] I've found it usefully used at this more general type. Thanks. - Mark ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Haskell 98 Report
Zhanyong Wan wrote: Hello Simon, Looking at the definition for deleteBy: deleteBy:: (x - a - Bool) - x - [a] - [a] deleteBy eq x []= [] deleteBy eq x (y:ys)= if x `eq` y then ys else y : deleteBy eq x ys I can't help wondering why it isn't deleteBy' :: (a - Bool) - [a] - [a] deleteBy' f [] = [] deleteBy' f (y:ys) = if f y then ys else y : deleteBy' f ys The point is that in the definition of deleteBy, all references to eq and x are in the form (eq x), and hence the two parameters can be combined. Is there a reason that the current design was favored when Prelude was designed? Thanks. - Zhanyong Zhanyong, I didn't mean to open up a can of worms! Although, when viewed in isolation, it would make sense to change deleteBy as you suggest; but when we look at the conventions of the List module, I think that it would be undesirable, even if we didn't care about breaking programs, because it would break the xBy convention described below. Originally we had this: delete :: Eq a = a - [a] - [a] deleteBy:: (a - a - Bool) - a - [a] - [a] And all the functions x with a xBy form have types which are related in a particular way, for some functor f: x :: Eq a = f a xBy:: (a - a - Bool) - f a Now, if we generalize the type of deleteBy as I previously suggested, we have these two types: delete :: Eq a = a - [a] - [a] deleteBy:: (a - b - Bool) - a - [b] - [b] And it is still the case that functions x and xBy have types which are related as follows (generalizing the rule): x :: Eq a = f a a xBy:: (a - b - Bool) - f a b (Where we would instantiate 'b' to 'a' for xBy functions which have a less general type.) - Mark ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Recursive types?
Tom Pledger wrote: I don't know whether this is a shining example of an advantage, and am keen to see other comments. For what it's worth, I've pulled some snippets from some code I wrote. I wanted three recursive types which were nearly identical (Exp,ExpQv,ExpPr). Rather than write three different type declarations data Exp = ... data ExpQv = ... data ExpPr = ... I was able to abstract out the commonality into one non-recursive type data FctrExp a = ... Note how concise some of my Sample Functions can be. These would have been very long and ugly to write were I to use the first approach. At the expense of now using a two-level type, I've gained some expressiveness. - Mark Fix Type - data Fix f = In (f (Fix f)) class FixEq f where fixEq :: Eq a = (f a - f a - Bool) class FixShow f where fixShowsPrec :: Show a = (Int - f a - ShowS) instance FixEq f = Eq (Fix f) where (==) (In x) (In y) = fixEq x y instance FixShow f = Show (Fix f) where showsPrec p (In x) = showString In ( . fixShowsPrec p x . showChar ')' Types for Documentation -- type Var = String type Env x = [(Var,x)] type Pat = Exp type Type = Exp Form FormPr Related Types - typeQv= (Exp,Exp) dataPr= Pstep (ExpPr,Justifier,ExpPr) | Pletu (Var, Type, ExpPr) deriving(Show,Eq) data Justifier= Stub1 deriving (Show,Eq) Exp,ExpPr,ExpQv Types data Ftype = Stub2 deriving (Show,Eq) data Ltype = Stub3 deriving (Show,Eq) data Const = Stub4 deriving (Show,Eq) data FctrExp a = Econ Const | Evar Var | Eapp (Ftype, a, a) | Elet (Ltype, Pat, Type, a, a) -- let x:t=e1 in e2 | Elam (Ftype, Pat, Type, a) -- \x:t=e | Eqnt (Ftype, Pat, Type, a) -- |~|x:t=e | Etup [a] -- e1,e2,... | Emu a | Ecase a -- case e | Ein (a,a)-- In i e deriving (Show,Eq) data FctrExpQv a = ExpQvExp (FctrExp a) | ExpQvQv Qv deriving (Show,Eq) data FctrExpPr a = ExpPrExp (FctrExp a) | ExpPrPr Pr deriving (Show,Eq) type Exp = Fix FctrExp type ExpQv= Fix FctrExpQv type ExpPr= Fix FctrExpPr Define Appropriate Functors -- instance Functor FctrExp where fmap = fmapFctrExp fmapFctrExp :: (a-b) - (FctrExp a - FctrExp b) fmapFctrExp f e = case e of Econ x- Econ x Evar x- Evar x Eapp (x,e1,e2)- Eapp (x,f e1, f e2) Elet (x,v,t,y,z) - Elet (x,v,t,f y,f z) Elam (x,v,t,e)- Elam (x,v,t,f e) Eqnt (x,v,t,e)- Eqnt (x,v,t,f e) Etup es - Etup (map f es) Emu e - Emu (f e) Ecase e - Ecase (f e) Ein (i,e) - Ein (f i,f e) Make Exp,ExpQv,ExpPr instances of Show and Eq instance FixEq FctrExp where fixEq= (==) instance FixShow FctrExp where fixShowsPrec = showsPrec instance FixEq FctrExpQv where fixEq= (==) instance FixShow FctrExpQv where fixShowsPrec = showsPrec instance FixEq FctrExpPr where fixEq= (==) instance FixShow FctrExpPr where fixShowsPrec = showsPrec Sample Functions - expToExpPr :: Exp - ExpPr expToExpPr (In x) = In (ExpPrExp (fmap expToExpPr x)) firstExpPr, finalExpPr :: ExpPr - Exp firstExpPr (In x) = case x of ExpPrExp e - In $ fmap firstExpPr e ExpPrPr (Pstep (p,_,_)) - firstExpPr p ExpPrPr (Pletu _) - error firstExpPr finalExpPr (In x) = case x of ExpPrExp e - In $ fmap finalExpPr e ExpPrPr (Pstep (_,_,p)) - finalExpPr p ExpPrPr (Pletu _) - error finalExpPr ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Specifications of 'any', 'all', 'findIndices'
Johannes Waldmann wrote: ... I'd rather write clear code, than worry about efficiency too early. Who said this, "premature optimization is the root of all evil". I've always attributed this to Donald Knuth: Premature optimization is the root of all evil in programming. Though I can't confirm it. I do find this similar statement in his "Structured Programming with go to Statements" (Computing Surveys 6 4, Dec 1974): ... premature emphasis on efficiency is a big mistake which may well be the source of most programming complexity and grief. Note also one of Alan Perlis's epigrams: Optimization hinders evolution. (See http://www.cs.yale.edu/homes/perlis-alan/quotes.html) - Mark Tullsen ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Important error in Download GHC 4.08.1 page
On the page http://www.haskell.org/ghc/download.html The link titled "RedHat 7 binary" should be changed from this URL: ftp://ftp.cse.unsw.edu.au/pub/users/chak/jibunmaki/i386/ghc-4.08.1-1.i386.rpm to this URL: ftp://ftp.cse.unsw.edu.au/pub/users/chak/jibunmaki/i386/ghc-4.08.1-2.i386.rpm ^ oops Thanks, Mark ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: The type of zip
Matt Harden wrote:
It has always seemed to me that having multiple zip functions with
different names (zip, zip3, zip4, etc..) was unfortunate, and a single
zip that handled all possible tuples would be better. Now, with
Multi-Parameter Type Classes and Functional Dependencies, we have an
opportunity to make zip more sensible.
Note: I am not proposing this as a "typo" for the current report, but
for a future version of standard Haskell. Obviously, this would only be
valid if MPTC's and FD's become part of the future standard.
I would propose:
o zip be renamed to zip2 and zipWith to zipWith2
o zip be changed to map tuples-of-lists to lists-of-tuples (the
"opposite" of unzip)
Yes, I've always thought this should be the more sensible type. I know
most Haskellers prefer to always curry, but I tuple in places where it
seems to make sense, like here.
o A Zippable class be created, defining zip and unzip for all tuple
types (or at least the first few)
For _all_ tuple types? That's a lot of instance declarations ;-)!
o (optional) a ZipFunctor class (subclass of Functor) defining a
function which applies a collection of functions to a collection of
values giving a collection of results. The list type ([]) would of
course be a member of this class.
I like this idea. Back before the days of "Functional Dependencies"
I took a stab at trying to do something like this, unsuccessfully.
The advantages I see:
o zip . unzip === id
o types of zip unzip are consistent with each other
o zip could be extended via the class mechanism to work with
non-list collections, and non-tuple elements
Disadvantages:
o Existing code using zip would break
o Implementation might be less efficient than current zip unzip
Sample implementation:
...
shameless plug
I have a paper ("The Zip Calculus", MPC 2000) which is a bit more
ambitious, and is correspondingly more complex. My solution allows
one to write the generic zip without use of the class system and
the theoretic need for an infinite number of instance declarations.
It allows you to write transpose
transpose :: ((a,b),(c,d),(e,f)) - ((a,c,e),(b,d,f))
generically for any m*n "matrix".
I hope to write up a proposal for how to add this capability to Haskell
in the not too distant future.
You can get the paper here if you're interested:
http://cs-www.cs.yale.edu/~tullsen/zip-mpc.ps
\shameless plug
- Mark Tullsen
Re: The type of zip
Matt Harden wrote:
Mark Tullsen wrote:
Matt Harden wrote:
o A Zippable class be created, defining zip and unzip for all tuple
types (or at least the first few)
For _all_ tuple types? That's a lot of instance declarations ;-)!
No doubt. But seriously, I was thinking of a "built-in" Zippable
instance just like we have for Ord, Enum, Show, etc.
That's what I thought you meant. But since I have a pet peeve about
how Haskell implementations work ...
I think the
language definition specifies these instances for all tuple types that
have sensible instances of these classes.
Yes, AFAIK the Report doesn't say anything about implementations being
allowed to not support "deriving" for 6-tuples or 8-tuples or whatever.
Actual Haskell
implementations don't provide these instances for all tuples, AFAIK.
Yes, ugh. I just tested hugs and ghc: they stop at 5-tuples.
Someone can correct me if I'm wrong, but the problem appears to
arise because tuples are not "really" first class in Haskell.
They are just syntactic sugar for fully applied uses of the
following constructors:
(,)
(,,)
(,,,)
...
Which seems to be the reason why tuples are lifted in Haskell.
(Or they are lifted for other reasons, and thus this implementation
then makes sense.)
shameless plug
I have a paper ("The Zip Calculus", MPC 2000) which is a bit more
ambitious, and is correspondingly more complex. My solution allows
one to write the generic zip without use of the class system and
the theoretic need for an infinite number of instance declarations.
It allows you to write transpose
transpose :: ((a,b),(c,d),(e,f)) - ((a,c,e),(b,d,f))
generically for any m*n "matrix".
I hope to write up a proposal for how to add this capability to Haskell
in the not too distant future.
You can get the paper here if you're interested:
http://cs-www.cs.yale.edu/~tullsen/zip-mpc.ps
I have lots of questions, but I'll wait until I've read your paper.
The paper is a little heavy going with all this Pure Type System
stuff. In case it's helpful, I put a copy of the slides from my
MPC talk on the web:
http://cs-www.cs.yale.edu/~tullsen/zip-mpc-talk.ps
- Mark
Re: partition and lifted products
Ross Paterson wrote: On Wed, Jan 19, 2000 at 03:18:34PM -0700, Joe Fasel wrote: *Sigh* And the language named in honor of Haskell Curry for which Currying is not a valid transformation strikes again! Worse, not only are the built-in product and function types lifted, but one can't define the unlifted ones. Before Haskell 1.3, even though the built-in product was lifted, one could define pairs as an abstract type exporting functions to make pairs and extract their components, which would then behave as true products. But then seq was introduced (and in Haskell 98 extended to type variables) so everything is lifted. Can we have extensional products and functions (or at least the means to define them) please? Just to add my vote: Yes, please give us these! I'm working on a program transformation system for a subset of Haskell. But it's not really a subset of Haskell, it has true products and functions. This is because to do without them means either that I have to jettison lots of laws and equivalences or that I have to transform using "partial correctness" ---equivalence modulo termination---rather than "total correctness": yuck). Most people I've talked to consider lifted products a mistake. (This may not mean that most consider it a mistake, maybe only that those who have disagreed have not bothered to tell me so.) Numerous others are unaware that products are lifted in Haskell! A while back, I asked John Peterson about the history of lifted products in Haskell. He told me that the decision was based on pragmatics (not semantics or efficiency): that it was simpler for implementations to represent an n-tuple as an n-ary constructor than to add an extra construct to the language (am I quoting you correctly, John?). - Mark Tullsen
Laws for MonadPlus
The Haskell 1.4 Report states that instances of MonadZero and MonadPlus should satisfy these laws: m zero = zero zero = m = zero m ++ zero = m zero ++ m = m Now that MonadPlus has been moved out of the Prelude (and has changed the names of all its operators), I see that no mention of these laws is in section 10.2 of the Haskell 98 Library Report. I assume this is inadvertent and that instances of MonadPlus should still satisfy these laws. But I have a question: Would it be reasonable to expect any instance of MonadPlus to satisfy the following law (using `mplus', not ++ now)? m = (\x-f x `mplus` g x) = (m = f) `mplus` (m = g) It is true for the Maybe and list instances. Can anyone give me a reasonable instance of MonadPlus which wouldn't satisfy this but does satisfy the above four laws? Or, is there some deep reason why this "should" be true? Thanks. - Mark
Can't install H/Direct on Linux with ghc 4.00
I can't get the current H/Direct (0.12) to install on my Linux system with ghc 4.00 (though I used ghc 3.02 to compile ihc). Thanks for any help. - Mark Tullsen Here's what's happening: -- Information about my system: hdirect-0.12 $ uname -a Linux HAGGIS.CS.YALE.EDU 2.0.35 #1 Thu Jul 23 14:01:04 EDT 1998 i686 unknown -- i.e., Red Hat Linux release 5.1 -- What I've Done So Far: cd /usr/local/fptools-3.02; make install (1) -- make ghc-3.02 the compiler -- if I compile with ghc-4.00, ihc core dumps right away -- in step (4). cd /usr/local/hdirect-0.12(2) make boot make cd /usr/local/fptools-4.00; make install (3) -- switch back to ghc-4.00 cd /usr/local/hdirect-0.12(4) make -k lib -- What Happens: -- (granted, some of the following may be bogus thanks to the use of "make -k") hdirect-0.12 $ make -k lib make -C lib boot make -C lib all make[1]: Entering directory `/usr/local/hdirect-0.12/lib' /usr/local/bin/ghc -M -optdep-f -optdep.depend -optdep-o -optdepo-fglasgow-exts -fno-prune-tydecls -recomp Pointer.lhs HDirect.lhs PointerPrim.hs make[1]: Leaving directory `/usr/local/hdirect-0.12/lib' make[1]: Entering directory `/usr/local/hdirect-0.12/lib' /usr/local/bin/ghc -fglasgow-exts -fno-prune-tydecls -recomp -c Pointer.lhs -o Pointer.o -osuf o Pointer.lhs:265: Value not in scope: `foreignObjToAddr' Pointer.lhs:275: Value not in scope: `foreignObjToAddr' Pointer.lhs:308: Value not in scope: `foreignObjToAddr' Compilation had errors make[1]: *** [Pointer.o] Error 1 /usr/local/bin/ghc -fglasgow-exts -fno-prune-tydecls -recomp -c AutoPrim.hs -o AutoPrim.o -osuf o AutoPrim.hs:8: Could not find valid interface file `Com' AutoPrim.hs:8: Module `Com' does not export `checkHR' AutoPrim.hs:8: Module `Com' does not export `marshalliptr' AutoPrim.hs:8: Module `Com' does not export `IUnknown' AutoPrim.hs:8: Module `Com' does not export `mkIID' AutoPrim.hs:8: Module `Com' does not export `IID' AutoPrim.hs:9: Could not find valid interface file `HDirect' AutoPrim.hs:9: Module `HDirect' does not export `Ptr' AutoPrim.hs:9: Module `HDirect' does not export `sizeofAddr' AutoPrim.hs:9: Module `HDirect' does not export `allocOutPtr' AutoPrim.hs:9: Module `HDirect' does not export `marshallBool' AutoPrim.hs:9: Module `HDirect' does not export `marshallptr' AutoPrim.hs:9: Module `HDirect' does not export `readptr' AutoPrim.hs:9: Module `HDirect' does not export `unmarshallref' AutoPrim.hs:9: Module `HDirect' does not export `trivialFree' AutoPrim.hs:9: Module `HDirect' does not export `doThenFree' AutoPrim.hs:9: Module `HDirect' does not export `sizeofInt32' AutoPrim.hs:9: Module `HDirect' does not export `readInt32' AutoPrim.hs:9: Module `HDirect' does not export `unmarshallString' AutoPrim.hs:9: Module `HDirect' does not export `freeString' AutoPrim.hs:9: Module `HDirect' does not export `sizeofInt16' AutoPrim.hs:9: Module `HDirect' does not export `readInt16' AutoPrim.hs:9: Module `HDirect' does not export `sizeofFloat' AutoPrim.hs:9: Module `HDirect' does not export `readFloat' AutoPrim.hs:9: Module `HDirect' does not export `sizeofDouble' AutoPrim.hs:9: Module `HDirect' does not export `readDouble' AutoPrim.hs:9: Module `HDirect' does not export `readBool' AutoPrim.hs:9: Module `HDirect' does not export `sizeofChar' AutoPrim.hs:9: Module `HDirect' does not export `readChar' AutoPrim.hs:9: Module `HDirect' does not export `unmarshallBool' Compilation had errors make[1]: *** [AutoPrim.o] Error 1 /usr/local/bin/ghc -fglasgow-exts -fno-prune-tydecls -recomp -c ComPrim.hs -o ComPrim.o -osuf o ComPrim.hs:6: Could not find valid interface file `HDirect' ComPrim.hs:10: Could not find valid interface file `Pointer' Compilation had errors make[1]: *** [ComPrim.o] Error 1 /usr/local/bin/ghc -monly-3-regs -fglasgow-exts -fno-prune-tydecls -recomp -c WideString.hs -o WideString.o -osuf o WideString.hs:7: Could not find valid interface file `Pointer' WideString.hs:8: Could not find valid interface file `HDirect' WideString.hs:11: Module `Foreign' does not export `foreignObjToAddr' Compilation had errors make[1]: *** [WideString.o] Error 1 cc -DCOM -c PointerSrc.c -o PointerSrcCom.o In file included from PointerSrc.c:40: comPrim.h:13: parse error before `IID' comPrim.h:13: warning: data definition has no type or storage class comPrim.h:28: parse error before `OLECHAR' comPrim.h:28: warning: data definition has no type or storage class comPrim.h:29: parse error before `*' comPrim.h:29: warning: data definition has no type or storage class comPrim.h:30: parse error before `*' comPrim.h:30: warning: data definition has no type or storage class comPrim.h:32: parse error before `*' comPrim.h:32: warning: data definition has no type or sto
Re: Haskell program manipulator
Mariano Suarez Alvarez wrote: Has anyone written a Haskell program manipulator? What I have in mind is some kind of interactive environment allowing one to, say, fold/unfold definitions, typecheck (sub)expressions, etc...e??Xa?^aZOUo^aUu[ZaaG??E?u?u Not yet, but that is exactly what I am working on in my dissertation research. After working a little on transferring partial evaluation techniques to a lazy language like Haskell, it seemed to me that a program transformation system would be the natural tool which could subsume a partial evaluation tool. Hopefully in a year I'll have something cool which would support much of Haskell. My goal is to create a _useful_ tool and I will post to this group when I believe I've got something in a useful form. I'd certainly welcome any suggestions as to what people would find useful. - Mark Tullsen = Mark Tullsen [EMAIL PROTECTED] Dept. of Computer Science Tel: (203) 432-1267 Yale University 51 Prospect St. P. O. Box 208285 New Haven, CT 06520-8285
