- Haskell-Cafe - Haskell.org

Imagining a G-machine
by Albert Y. C. Lai 17 May '07

17 May '07

A native G-machine --- physical, or chemical, or biological, but not a repressed simulation over the imperative cpu-memory architecture --- is the dream of every lazy-functional programmer of great devotion. If only it became the dominant computing architecture! People would say, Haskell is high-level assembly because it is the closest to the bare metal (or bare protein) and still supports all sorts of abstractions. People would ask, why is my C program five times slower than Haskell, and people would answer, that's because C is compiled to a stack of seven monad transformers (one of which is ContT to support longjmp), and because you should use more linked lists and fewer arrays. We truely rule the world when C programmers have to consult us for performance tips. A necessary condition for dominance is existence. Here is my crazy imagination of a native G-machine. It is worded as biotech but may as well be molecular computing or nanotech. The heap is a soup of nutrients. A node is a molecular structure made from the nutrients. A thunk is a lot of nodes linked up. Nodes and thunks are suspended in the soup. Allocation means constructing nodes and links from nutrients, and deallocation means unlinking nodes and eventually dismantling them back into nutrients. As a side effect, memory upgrade is cheap and convenient: Just go buy a can of Campbell soup (my favourite is the alphabet soup) and pour into your heap. There are 24-hour convenient stores at every street corner --- pervasive computing has never been so pervasive before. A thunk is nodes linked together and suspended in the soup. A theorem in graph theory asserts that all finite graphs can be embedded without crossing edges in 3D space, and we take advantage of this to space out the nodes in a complicated thunk. Still, it is not easy, being NP-hard and all. There is a relaxation heuristic for this: It simply requires nodes to be a bit repulsive to each other and links to be elastic, and they will sort things out themselves. (When they don't, a bit of shaking up helps tremendously.) Evaluation is performed by a small organism crawling over a thunk and performing its thunk-rewriting duty as per the G-machine. It applies enzymes to construct and deconstruct nodes and links from nutrients. It performs primitive arithmetic on its own. It maintains its own stack, inside or outside its body (to be investigated). It is possible to unleash several such evaluators for parallel computing. It is possible to enable reproduction to boost parallelism. To add garbage collection, roots send out a periodic (or sustained) signal to all connected nodes. Nodes receiving the signal do not self-destruct. Nodes not receiving the signal invokes their built-in self-destruct mechanism to dissolve themselves back into nutrients. There may be better schemes. Interacting with the outside world is open, but Andrew Gordon's thesis contains translations from monadic I/O to other I/O schemes, e.g., continuations, streams, etc. Perhaps one of them can be adapted. Debugging can be done by making evaluators send radio signals concerning operations they perform; then a second computer can log these and you can review them. You can also use radio signals to instruct the evaluators to perform unusual operations on demand. The existence of a native G-machine is a necessary but not sufficient condition for world dominance. We still need to make it fast, compact, and cheap. There may also be better but totally different ways to realize a native G-machine.

8 8

Re: Type class help please
by oleg＠pobox.com 17 May '07

17 May '07

Adrian Hey wrote: > -- Instances of GT are instances of Eq -- > instance (GT map key, Eq a) => Eq (map a) where > map1 == map2 = assocsAscending map1 == assocsAscending map2 > ... > Overlapping instances for Eq [(key, a)] > arising from use of `==' at Test.hs:10:16-59 > Matching instances: > instance (Eq a) => Eq [a] -- Defined in GHC.Base > instance (GT map key, Eq a) => Eq (map a) -- Defined at Test.hs:9:0 > > How can my new instance overlap with the old (ghc) instance unless > [] is also an instance of GT for some key type (which it isn't). > Could someone explain? You are right in your explanation of the GHC behavior. Your instance |Eq (map a)| indeed overlaps the `standard` instance |Eq [a]|. The overlap may be easier to see if we write [a] as ([] a), which is what it is, an application of the type constructor [] to the type variable a. So, the type [a] (aka [] a) is a particular instance of the type (map a), with `map' being []. This is the overlapping that GHC is complaining about. Regarding the need for -fallow-undecidable-instance: GHC is not a general purpose termination checker. Furthermore, it seems reasonable for GHC to employ simple termination heuristics, which can be decided quickly, syntactically and locally (that is, considering only the instance in question, rather than collection of all instances in the program). Thus GHC employs a set of heuristics that look if the instance constraints are `smaller' than the instance head. That will assure termination. That criterion is of course not complete, so there are (many) terminating, decidable typeclass program that fail simple GHC termination tests and thus require -fallow-undecidable-instance extension. One method of avoiding overlapping instances is to define a newtype wrapper: newtype MyMap map a = MyMap{unMyMap::map a} class Ord key => GT map key | map -> key where assocsAscending :: map a -> [(key,a)] -- Just 1 of many methods instance GT (MyMap Data.IntMap) Int where ... The drawback is writing MyMap and unMyMap in many places. That spoils the appearance, but rarely fatal. Another solution is replacing the general instance instance (GT map key, Eq a) => Eq (map a) where map1 == map2 = assocsAscending map1 == assocsAscending map2 with its instantiations, for all `maps' in question: instance Eq a => Eq (Data.IntMap a) where ... instance Eq a => Eq (Data.Map key a) where ... instance Eq a => Eq (Data.IntSet a) where ...

2 4

Bad "let..do" syntax
by Chad Scherrer 17 May '07

17 May '07

I've gotten into a habit of preceding most "do"s in my code with a "$", and indenting the next line. I kind of like this, since it makes the indentation more uniform. But it seems to have bitten me now. I'd like to write something like this s = sum $ do x <- [1,2,3] let b = sum $ do y <- [0..x + 1] return y return (x + b) But GHC complains of "Empty 'do' construct". It likes the alternative s' = sum $ do x <- [1,2,3] let b = sum $ do y <- [0..x + 1] return y return (x + b) just fine, but that looks horrible to me (ok, "horrible" is a bit strong, but I don't like it as much). So I'm wondering, (1) Is this intended to give an error, or is it just a momentary hiccup, and (2) if others have run into this, is there a more aesthetic alternative that works? Thanks, Chad

2 2

negate and -
by Maurício 17 May '07

17 May '07

Hi, Haskell language reference says the special - operator translates to negate. However, this: (+ negate 5) 5 works but this: (+ -5) 5 is not valid. Why? Thanks, Maurício

2 1

haskell quiry
by ashutosh dimri 17 May '07

17 May '07

Thanks a lot Mr. jules now the code is working perfectly for higher values , the problem was with ord .

1 0

haskell quiry
by ashutosh dimri 17 May '07

17 May '07

I have written a code to convert hexadecimal numbers into base 10 number but its working only for 32 bits and I need it to work upto 160 bits , code is given below. please help. --its a program to convert hexadecimal numbers into base 10 numbers import Char -- the function "func" takes a list of strings in hexadecimal and convert -- it to a list of corresponding numbers in decimal format -- func "eefba12" = [14,14,15,11,10,1,2] func [] = [] func (x:xs) |(ord x > 57) = ((ord x)-87):func xs |otherwise = ((ord x)-48):func xs -- (mul.func) function takes a hexadecimal number and convert it to base 10 but its working only for 32 bits -- whereas haskell supports calculations much higher than 32 bits..... -- mul.func $ "ee" = 238 -- mul.func $ "e23e" = 57918 mul xs = mul1 xs ((length xs)-1) mul1 (x:xs) 0 = x mul1 (x:xs) n = (x*16^n)+ mul1 xs (n-1)

2 1

ANNOUNCE: Dimensional 0.4 -- Statically checked physical dimensions
by Björn Buckwalter 16 May '07

16 May '07

Dear all, I am pleased to announce version 0.4 of Dimensional (working name). Dimensional is a library providing data types for performing arithmetic with physical quantities and units. Information about the physical dimensions of the quantities/units is embedded in their types and the validity of operations is verified by the type checker at compile time. The boxing and unboxing of numerical values as quantities is done by multiplication and division with units. The library is designed to, as far as is practical, enforce/encourage best practices [1] of unit usage. Since the previous formal announcement [2] (version 0.1) Dimensional has gone through several structural and stylistic improvements but usage remains fundamentally unchanged. Noteworthy changes are a vastly solidified 'NumType' module, a complete(?) set of elementary functions and a 'Prelude'-replacement for users' convenience. There is also an experimental 'Extensible' module supporting user-defined dimensions. Additional structural changes and additions (primarily of units) are planned and the library will continue to have an unstable API until the 1.0 release. However, apart from module reshuffling no changes are anticipated that would break user code. Additional information and code is available from the project web site [3]. Thank you, Bjorn Buckwalter [1] http://physics.nist.gov/Pubs/SP811/ [2] http://www.haskell.org/pipermail/haskell/2006-December/018993.html [3] http://code.google.com/p/dimensional/

1 0

CUFP website
by Cyril Schmidt 16 May '07

16 May '07

I noticed recently that the website of CUFP conference (Commercial Uses of Function Programming), which used to be at http://www.galois.com/cufp, is not accessible anymore. Does anybody know where it moved? Cyril

3 2

quiry
by ashutosh dimri 16 May '07

16 May '07

how to convert a hexadecimal into base 10 integer using haskell . I have written a code but its not working for large values , please help

4 3

Books on Haskell
by PR Stanley 16 May '07

16 May '07

Hi, Is Graham Hutton's book on Haskell Programming a good text for FP beginners? Paul

2 1