April 2002 - Haskell - Haskell.org

RE: handling errors in Happy
by Simon Marlow 03 Apr '02

03 Apr '02

> Is it possible to get the result of function happyError, in > the main module > of my program (which imports the module generated by Happy)? Sure. You need to use Happy's %monad feature, the documentation describes how to turn parse errors into something you can handle in the program: http://www.haskell.org/happy/doc/html/sec-monads.html#SEC-EXCEPTION Cheers, Simon

1 0

Haskell/Erlang Research Position
by Phil Trinder 03 Apr '02

03 Apr '02

Research Associate in Haskell/Erlang for Distributed Telecommunications �17,278-�26,229 p.a. Applications are invited for a three year Research Associate position at Heriot-Watt University to work with Dr Phil Trinder on an EPSRC funded project entitled "High-Level Techniques for Distributed Telecommunications Software". The project is a collaboration with Motorola UK Research Labs and aims to evaluate high-level distributed programming techniques for constructing realistic telecommunications software. Applications are welcomed from candidates with a doctorate or a very good first degree in Computing or cognate discipline; a successful candidate without a PhD will have the opportunity of registering for one. Applicants should have good written and verbal communication skills and be able to demonstrate a strong programming ability: experience with distribution and the Haskell or Erlang programming languages is desirable. Likewise a research background, and familiarity with the telecommunications sector are desirable. For application details please contact the Personnel Office, Heriot-Watt University, Edinburgh, EH14 4AS, tel/fax: 0131 451 3475 (24 hours) quoting Ref 66/02/J. The closing date is Friday 19th April 2002. Informal enquires can be directed to Phil Trinder tel: +44 131 451 3435, or e-mail: trinder(a)cee.hw.ac.uk. More details of the project and further particulars for the position can be found at: http://www.cee.hw.ac.uk/~dsg/telecoms/

1 0

Re: ">>" and "do" notation
by John Hughes 03 Apr '02

03 Apr '02

>If (as a human reader of a programme) I see > >do a <- thing1 > <expression> > >and I notice (perhaps after some modifications) that a is >not present in <expression>, then I /really/ don't want a >change to > >do thing1 > <expression> > >to change the meaning of the programme. I think the point that's being missed in this discussion is that a monad is an *abstract* type, and sometimes the natural "equality" on the abstract type is not the same as equality on representations. Of course, we want the left and right hand sides of the monad laws to have the same "meaning", and we want >> to "mean" >>= \_ ->, but this meaning is really up to the abstract equality, not the concrete one. If we can give >> a more efficient implementation, which constructs a better representation than >>= does, that's fine, as long as the two representations "mean" the same thing. To be specific, the application that kicked off this discussion was program generation. In this example, it's not important that >> and >>= generate the same *program text*, the important thing is that they generate equivalent programs. If >> can more easily generate a more efficient program, that's fine. There's another example in QuickCheck, where we use a monad Gen for random value generation -- Gen a is a generator for random values of type a. Gen does not satisfy the monad laws: for example, g and g >>= return will usually generate different values. But viewed as *probability distributions* (which is how we think of them), they are the same. "Morally", Gen is a monad. This is all perfectly respectable, and has to do with the fact that Haskell is a programming language, not mathematics -- so we represent equivalence classes by values chosen from them. For the *language* to rule out constructing different representations for "equivalent" constructions, such as >> and >>=, would be unreasonable. John Hughes

3 2

Re: sort inefficiency
by Serge D. Mechveliani 03 Apr '02

03 Apr '02

Glenn G. Chappell <ggchappell(a)yahoo.com> writes > I am wondering about a design decision in the List module. > > To wit: "sort", in both the H98 library report and the Hugs file > List.hs, is implemented using a quadratic sort (insertion sort). > > Using the name "sort" certainly suggests that this is a good function > to use for sorting. I would think it is pretty obvious that "sort" > should be implemented using an efficient algorithm. I am thinking > primarily of merge sort, which has O(n log n) worst case behavior, > is stable, and has an elegant and efficient functional implementation. > > Certainly insertion sort is good to have around, if one is sorting > data that is nearly sorted already, but I would say insertion sort > is clearly not the best choice (or even a good choice) for a general- > purpose sorting algorithm. > > Or am I missing something? The Standard library specifies only the map related to the name `sort'. This map can be described, for example, via sort-by-insertion program. And the algorithm choice is a matter of each particular implementation. Implementation has right to change the algorithm. For example, I tried once to argue with GHC for incorporating the mergeSort algorithm for `sort'. But they have some version of quickSort which is said faster on average and O(n^2) in the worst case. Disliking this n^2 hazard, I overload `sort' with my_sort. ----------------- Serge Mechveliani mechvel(a)botik.ru

1 0

handling errors in Happy
by Andre W B Furtado 03 Apr '02

03 Apr '02

Is it possible to get the result of function happyError, in the main module of my program (which imports the module generated by Happy)? Thanks a lot, -- Andre

1 0

JVM-Bridge Current Status
by Ashley Yakeley 03 Apr '02

03 Apr '02

1. Changes So Far The following changes have been checked into CVS since the 0.1 release: Native/ * MacOS X support * Beginnings of mingw32 support * New Sun 1.4 JVM * Now installs in /usr/lib/jvm-bridge/ * ExecuteFunction bindings now done at run-time Haskell/ * MacOS X support * 'Haskell' now a separate Autotools project installing in /usr/lib/jvm-bridge/ * New array region access functions * Correct array types in autogenerated class interfaces * Subtype parameters in autogenerated class interfaces * VMLayer 'env' parameter now implicit * Various changes in the BasicLayer * new native StartExecuteFunction function called by getExecuteFunctionClass, defineCallbackClass I recommend using GHC 5.02.2 or later. Possibly it might work with 5.02. 2. Current Work MacOS X callback support is buggy, and I'm currently working on it. It might a problem with ghc-5.03-13032002-MacOSX (foreign export dynamic), or it might be a bug in JVM-Bridge. Thomas Pasch <extern.thomas.pasch(a)volkswagen.de> has done some work on getting JVM-Bridge to compile under mingw32. I have integrated some of his patches. I do not have a Windows machine myself. I would like to do a 0.2 release, say when both examples work on all three platforms. 3. I have created a new mailing list: <http://lists.sourceforge.net/lists/listinfo/jvm-bridge-devel> If you are using JVM-Bridge I encourage you to subscribe. -- Ashley Yakeley, Seattle WA

1 0

Inefficient sort implementation
by Glenn G. Chappell 02 Apr '02

02 Apr '02

I am wondering about a design decision in the List module. To wit: "sort", in both the H98 library report and the Hugs file List.hs, is implemented using a quadratic sort (insertion sort). Using the name "sort" certainly suggests that this is a good function to use for sorting. I would think it is pretty obvious that "sort" should be implemented using an efficient algorithm. I am thinking primarily of merge sort, which has O(n log n) worst case behavior, is stable, and has an elegant and efficient functional implementation. Certainly insertion sort is good to have around, if one is sorting data that is nearly sorted already, but I would say insertion sort is clearly not the best choice (or even a good choice) for a general- purpose sorting algorithm. Or am I missing something? ===== Glenn G. Chappell <>< ggchappell(a)yahoo.com Dept. of Mathematical Sciences * Ofc: (907) 474-5736 University of Alaska Fairbanks * Fax: (907) 474-5394 __________________________________________________ Do You Yahoo!? Yahoo! Tax Center - online filing with TurboTax http://http://taxes.yahoo.com/

1 0

Re: Lambda over types.
by oleg＠pobox.com 02 Apr '02

02 Apr '02

anatoli <anatoli at yahoo> wrote: > Attached are two interpreters: one for untyped lambda calculus, I'm afraid the attached interpreter can't be an implementation of the lambda calculus. For one thing, it lacks the hygiene of substitutions: Lambda> :t lambdaEval (A (L X (L Y (A X Y))) T) lambdaEval (A (L X (L Y (A X Y))) T) :: L Y (A T Y) That's OK. However, Lambda> :t lambdaEval (A (L X (L Y (A X Y))) Y) lambdaEval (A (L X (L Y (A X Y))) Y) :: L Y (A Y Y) That is wrong! The correct answer is: L Yfresh (A Y Yfresh) The interpreter in question doesn't appear to be able to manufacture fresh identifiers (i.e., fresh types). Without an ability to expand the set of available identifiers, the capture-free substitution is impossible. Furthermore, some terms fail to evaluate: Lambda> :t lambdaEval (A (L X (A X X)) T) lambdaEval (A (L X (A X X)) T) :: Eval (A (L X (A X X)) T) a => a Lambda> :t lambdaEval (A (A (L X X) T) Y) lambdaEval (A (A (L X X) T) Y) :: Eval (A (A (L X X) T) Y) a => a which is not the result one would've expected. Finally, the interpreter doesn't actually find the normal form. The rule > instance Eval (L v e) (L v e) prevents any reductions under lambda. True, call-by-name or call-by-value interpreters stop short of reducing the body of a lambda form. Normal or applicative order interpreters however -- in order to find the beta-eta-normal form -- should seek and attempt any reduction. The hygienic substitution (with alpha-conversion if necessary) and the repeated identification of the leftmost outermost redex are actually quite challenging. We can guarantee the hygienic substitution if we implement the de Bruijin notation for lambda terms. Another, related technique is coloring of existing identifiers. A macro-expander of R5RS Scheme macros implements the coloring to ensure the hygiene of macro expansions. The macro-expander can be cajoled into painting identifiers on our demand, which has been used in a macro-expand-time lambda calculator. In Haskell, we have to paint manually. A variable in a typechecker-time lambda-calculator has to be represented by a type like Vr (Succ (Succ (Succ Zero))) X. The latter component is the "name" and the former is the color. The Eval and Subst relations should be extended with color_in and color_out type parameters (perhaps with a dependency: term color_in -> color_out). The only non-trivial use of colors is in doing a substitution (L var body)[exp/var']. The bound variable has to be repainted before the substitution in the body. The beta-substitutor itself can do the repainting.

2 2

Haskell Reference at Zvon (alpha release)
by Miloslav Nic 02 Apr '02

02 Apr '02

Hello, I have put on-line alpha version of Haskell reference: http://zvon.org/other/haskell/Outputglobal/index.html I would appreciate your comments and suggestions. -- ****************************************** <firstName> Miloslav </firstName> <surname> Nic </surname> <mail> nicmila(a)systinet.com </mail> <support> http://www.zvon.org </support>

1 0

Re: using less stack
by C.Reinke 02 Apr '02

02 Apr '02

> > > cpsfold f a [] ú > > > cpsfold f a (x:xs) ÿ x a (\y -> cpsfold f y xs) > > > > and f takes a continuation, Bob's my uncle, and I have a program that > > runs quickly in constant space! > > Good. I'm curious to know from other readers whether > continuations like this are the only way of solving it, > though. Actually, and quite apart from it being cumbersome to use, I've got my doubts about whether this cpsfold really does the job (is that just me missing some point?-). Also, I'm curious to know why the usual strict variant of foldl doesn't help in this case? foldl' f a [] = a foldl' f a (x:xs) = (foldl' f $! f a x) xs or, with the recently suggested idiom for strictness, tracing and other annotations:-) annotation = undefined strict a = seq a False foldl' f a l | strict a = annotation foldl' f a [] = a foldl' f a (x:xs) = foldl' f (f a x) xs Claus

8 10