- Haskell-Cafe - Haskell.org

Auto generated instance codes through 'deriving'
by Jong Keun Na 07 Feb '03

07 Feb '03

Hello folks, Is there any method with which I can see instance's codes generated automatically by using 'deriving' keyword in GHC? I'm curious in how GHC generates 'Read' class's instance code for user-defined data type. Any help will be great appreciated. /JongKeun

1 0

Re: arrays and lamda terms
by Claus Reinke 06 Feb '03

06 Feb '03

>Right, I mean constant-steps, rather than single steps. Could you give an example to what you are describing? Sure. Just thought you'd like to play with the idea yourself first:-) If you limit beta-reduction to deal only with unary abstractions, there's little chance of deconstructing an expression involving n separate subterms with less than n steps. Otherwise, it is just the old idea of representing data structures by their folds. A selector then returns one of its n parameters, which usual implementations deal with in a single step. You could even compute the selectors for each combination of array-size and position if Haskell's type system didn't get in the way (a job for template Haskell, or some type class hackery). Cheers, Claus -- representing arrays as their folds, -- here for m=5 arr5 a1 a2 a3 a4 a5 s = s a1 a2 a3 a4 a5 show_arr5 a = show $ a (,,,,) list2arr5 [a1,a2,a3,a4,a5] = arr5 a1 a2 a3 a4 a5 -- selectors -- sm_n =~= (ignore^(n-1)) (keep^(m-n)) -- where {- const by any other name -} -- ignore f x = f -- keep x y = x s5_1 a1 a2 a3 a4 a5 = a1 s5_2 a1 a2 a3 a4 a5 = a2 s5_3 a1 a2 a3 a4 a5 = a3 s5_4 a1 a2 a3 a4 a5 = a4 s5_5 a1 a2 a3 a4 a5 = a5 -- updates -- for illustration only; whole-array ops preferable u5_1 a1 a2 a3 a4 a5 f = arr5 (f a1) a2 a3 a4 a5 u5_2 a1 a2 a3 a4 a5 f = arr5 a1 (f a2) a3 a4 a5 u5_3 a1 a2 a3 a4 a5 f = arr5 a1 a2 (f a3) a4 a5 u5_4 a1 a2 a3 a4 a5 f = arr5 a1 a2 a3 (f a4) a5 u5_5 a1 a2 a3 a4 a5 f = arr5 a1 a2 a3 a4 (f a5) -- example uses main = do let a = list2arr5 [1..5::Int] putStrLn $ "a="++show_arr5 a putStrLn $ "a[4]="++show (a s5_4) let b = a u5_4 (const 0) putStrLn $ "b="++show_arr5 b putStrLn $ "b[4]="++show (b s5_4) mapM_ (print . b) [s5_1,s5_2,s5_3,s5_4,s5_5] let c = b u5_1 (+1) u5_3 (+1) u5_5 (*2) putStrLn $ "c="++show_arr5 c

2 2

Re: separate compilation [was Re: Global variables?]
by Jon Cast 06 Feb '03

06 Feb '03

Andrew J Bromage <ajb(a)spamcop.net> wrote: > G'day all. > On Wed, Feb 05, 2003 at 08:05:56PM -0600, Jon Cast wrote: > > I'm not sure I follow this. If you change the type of a value exported > > from a given module, that's a public change, no? And if you don't, why > > should re-compilation be needed? > Consider this: > << > module A where > import B > {- use B.b -} > >> > << > module B (b) where > import C > b = C.c > >> > << > module C (c) where > c :: Int > >> > Changing the type of c requires recompiling module A. > You would expect that changing c's type forces a recompilation of B, > since you changed C's public interface. However, this also changes > B's public interface even though you did not touch the text of module > B. The reason is that B's public interface is partly based on modules > which it _privately_ imports, even if it does not re-export any > symbols from those modules. I think I see what you're saying. I still maintain, however, that, since you've changed the type of B.b (admittedly implicitly), and B.b is exported from B, that you've changed B's interface. There is a reason make is designed to re-build B /and/ (potentially) A when C changes, after all. > One fix is to require all exported symbols to have explicit type > declarations. Since this is good practice anyway, I would be in > favour of making it a language requirement in Haskell 2. > Cheers, > Andrew Bromage Jon Cast

2 1

Re: separate compilation [was Re: Global variables?]
by Jon Cast 06 Feb '03

06 Feb '03

Andrew J Bromage <ajb(a)spamcop.net> wrote: > G'day all. > On Wed, Feb 05, 2003 at 04:16:33PM -0800, Iavor S. Diatchki wrote: > > why do you think separate compilation is difficult to achieve in > > Haskell 98? > Because of type inference over recursive module imports. Determining > the type of a function may, in general, require inferring types from an > arbitrary number of other modules, and may require inference to occur > at the level of granularity of a clique in the import graph, rather than > at the level of a single module. > Requiring an implementation to perform static analysis a clique at a > time is not "separate compilation", because changing something which > is private to one module may in general require an unbounded number of > other modules to be recompiled, even if inter-module optimisation is > turned off. I'm not sure I follow this. If you change the type of a value exported from a given module, that's a public change, no? And if you don't, why should re-compilation be needed? <snip> > Cheers, > Andrew Bromage Jon Cast

2 1

RE: Global variables?
by Simon Peyton-Jones 06 Feb '03

06 Feb '03

| Haskell 98 has never supported separate compilation. That's why we | have hi-boot files (or something similar). | | So, yes, I'd like to know how the language designers intend to support | separate compilation in the next version. H98 has nothing to say about the separate compilation; it's an issue for the implementation. GHC does separate compilation for Haskell, and always has done. It requires the programmer to supply an auxiliary hi-boot file for one module in each mutually recursive group (and, of course, none if there is no recursion between modules). Simon

4 5

RE: Looking for large Haskell programs
by Simon Marlow 05 Feb '03

05 Feb '03

> PS: Approximately how many lines of code is GHC these days? ~78k lines of code, ~63k lines of comments in the compiler itself. The runtime has a further ~50k lines of C. Cheers, Simon

1 0

Re: arrays and lamda terms
by oleg＠pobox.com 05 Feb '03

05 Feb '03

Cagdas Ozgenc wrote: > Is it possible to encode an array using lamda terms only, and recover > the term specified by an index term in O(1) time? I'd like to go on a limb and argue that there is generally no such thing as O(1) array access operation. On the conventional hardware, the fastest access to the i-th element of an array 'ar' is expressed by the following formula, which underlies C "arrays": ar[i] = *(ar + i) The formula involves the addition of two numbers -- which is, generally, a O(log(n)) operation. Granted, if we operate in the restricted domain of mod 2^32 integers, addition can be considered O(1). If we stay in this domain however, the size of all our arrays is limited to M (which is 2^32, often less). If we implement our arrays as linked lists, the cost of accessing one element will not exceed M*2*cost(dereference), which is constant, which is O(1). Thus pedantically speaking, within the restricted integral domain, any terminating array access method is O(1). The choice of "hardware" may greatly affect the apparent complexity. For example, associative memory access is difficult on conventional architectures and fast for holographic memory. > Or is it possible in any rewriting system? If all your arrays are limited in size to 2^32, and if your re-writing system offers projection operators pi_0, pi_1, ... pi_4294967295 (i.e., the right "hardware"), well, then it is possible.

2 1

Stacking up state transformers
by Guest, Simon 05 Feb '03

05 Feb '03

Thanks to Andrew, I'm now backtracking my state correctly. Now what I want to do is have two elements of state, an element that gets backtracked, and an element that doesn't. My monad now looks like this: type NondetState bs ns a = StateT bs (NondetT (StateT ns Maybe)) a where bs is my backtracked state, and ns my non-backtracked state. I can still access my backtracked state using Control.Monad.State.{get,put}, but I can't access my non-backtracked state. How do I burrow through the stack of monad transformers to get and put the 'ns' state? Supplementary question: What documentation should I be reading? cheers, Simon

3 2

arrays and lamda terms
by Cagdas Ozgenc 04 Feb '03

04 Feb '03

Greetings. My question is not directly related to Haskell. Is it possible to encode an array using lamda terms only, and recover the term specified by an index term in O(1) time (in other words in one step reduction, without cheating using several steps behind the scenes)? Or is it possible in any rewriting system? I might not be making any sense, but I am sure there are people out there who can read my mind, and possibly put my question into better terminology. Thanks

2 1

RE: Concurrent-Haskell in GHC
by Simon Marlow 04 Feb '03

04 Feb '03

> | I've started looking into the docs on GHC's > | implementation of Concurrent-Haskell, and I got > | confused about the architecture. Different sources > | seem to indicate that it either: > | - Uses one OS thread, and blocking IO calls will > | therefore block all the Haskell-threads, or > | - Uses one OS thread, occasionaly (50 times a second?) > | calling select() to simulate blocking IO calls without > | blocking other Haskell-threads, or > | - Uses a pool of OS threads so that when a blocking IO > | call is made, another thread takes over execution. > > Basically the last of these. (At least in the most recent > GHC.) Simon > Marlow implemented a web server using Concurrent Haskell, and has a > paper about it too. http://www.haskell.org/~simonmar/bib.html But we should really point out that you get the second method by default; the "pool of OS threads" method is currently experimental and not enabled unless you rebuild GHC's RTS with the right flags. The default single-threaded IO multiplexing works pretty well, although it doesn't scale to multiple processors of course. Cheers, Simon

1 0