- Haskell - Haskell.org

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

Computer Scientist Gets to the "Bottom" of Financial Scandal
by Andrei Serjantov 01 Apr '02

01 Apr '02

Here's an article in the Cambridge Evening News that might interest this group ... April 1, 2002. Computer Scientist Gets to the "Bottom" of Financial Scandal A Cambridge computer professor, Simon Peyton Jones, has made an interesting discovery regarding the Enron collapse. Enron, an American energy company, started life as a regional natural gas pipeline provider, the result of a merger between Houston Natural Gas and InterNorth in 1985. Its chairman, Kenneth Lay, eventually transformed Enron into the world's largest energy trading company and America's seventh-biggest corporation. Enron filed for bankruptcy on December 2 last year in the biggest collapse in American history. Enron's collapse was due to a nearly impenetrable web of financial contracts that disguised the true financial state of the company and allowed Enron to report record profits while actually losing money. A complex set of partnerships were set up in 1999 to move debt off its balance sheet and hide losses. The most complex of these financial contracts are derivative instruments in which the value of a contract depends on other financial contracts. Accountants find that even when they are scrupulously honest about the valuation of such contracts there can still be sharp disagreements in regard to the worth of trading reserves, debts, and other components. Enter Professor Peyton Jones. As part of his research at Microsoft in Cambridge, he developed a computer language for describing and valuing financial contracts. With a colleagues Jean-Marc Eber and Julian Seward, they developed a language capable of accurately describing and valuing even the most complex financial instruments. "While accountants find financial derivatives to be mysterious and difficult, for us they are just ordinary recursive equations," says Jones. "We have been dealing with these for many years and have developed a wide range of techniques for handling them." This language is turning heads in the financial community. According to Emanuel Derman, managing director of firm-wide risk at Goldman Sachs, "In all areas of computer science, there has been a natural evolution towards building high-level languages with a syntax and semantics specifically geared to the domain of the application. Much of the power of the Unix programming environment, as well as its popularity among scientists and engineers, came from the pleasure of working in this framework. It makes sense to do the same thing in the financial arena, and some of the tools we built at Goldman have actually been small steps in this direction." When Professor Jones heard about the Enron collapse, he decided to use his new language to investigate. After weeks of poring over financial statements and contracts, he was able to create a set of mathematical equations using his financial contract language. Once everything was ready, his team was ready to evaluate Enron's financial worth. "It was very dramatic," he relates, "we were all gathered around my computer and I hit the enter key. Instead of generating a value, the program returned `bottom'." Bottom is a special value that computer scientists use to denote a meaningless program. Here, it indicated that Enron had used financial contracts whose values did not actually have any formal meaning." He went on to explain how this works: "It's really very simple. If I write a contract that says it's value is derived from a stock price and the worth of the stock depends solely on the contract, we have bottom. So in the end, Enron had created a complicated series of contracts that ultimately had no value at all." News of this discovery spread quickly. While some accountants feel that computers cannot replace human judgment in the interpretation of financial contracts, others see this as just the first step in a trend towards a more precise language of accounting and financial contracts. Nearly everyone in the accounting field agrees, however, that this work by Peyton Jones will have a significant impact on the legal case against Enron. According to Peyton Jones, his success in the financial world comes from years of research in Haskell, an esoteric computer language. "Without the tools developed by the Haskell community I would never have been able to do what I've done. It's a jolly wonderful way to program computers" he stated. The Arthur Anderson accounting firm is rumored to have made overtures to Peyton Jones. A spokesman for Andersen's Cambridge office said it was too early to speculate as to whether Peyton Jones might leave Microsoft Research but he added "It would be a tremendous boost the credibility of our company and the whole accounting profession to bring someone of this caliber into our company." But Professor Peyton Jones plans to remain where he is. "I'm flattered that my research has finally been of use to someone but I'm quite happy working on Haskell. Besides, I don't want to have to wear a suit to work every day."

1 0

Reply: Z_n in Haskell
by Serge D. Mechveliani 01 Apr '02

01 Apr '02

Hello, Hal Daume III <hdaume(a)ISI.EDU> writes about Z_n in Haskell: > Suppose I want to define integers modulo n, I could do this something > like: > data Zn = Zn Integer Integer -- modulus, number > > instance Num Zn where > (Zn m1 n1) + (Zn m2 n2) > | m1 == m2 = Zn m1 (n1 + n2 `mod` m1) > | otherwise= error "differing moduli" > ...etc... > > However, I'd really like it if, say, addition on Zn-s of different > "n" values were caught by the typechecker and disallowed. One solution to > this problem would be to do something like: > > class Modulus m where modulus :: T m -> Integer > data Zn m = Zn (T m) Integer > > instance Modulus m => Num (Zn m) where > (Zn m1 n1) + (Zn m2 n2) = > (Zn m1 ((n1 + n2) `mod` (modulus m1))) > > [..] oleg(a)pobox.com responds with | The Z_n problem doesn't seem to be different from the problem of | arrays or bitvectors of a statically-checkable size. | | [..] | | Both implementations work in any Haskell-98 system. Multi-parameter | classes, existential types or other extensions are not needed. Also someone advised to follow up the haskell-cafe list archive containing the proposal, probably, by Dylan Thurston (Spring 2001), to exploit existential types to express the constructs like Z/(n) - residue domain of integers modulo n. This whole subject interests me. After maybe a month, I am going to investigate it and answer what precisely is wrong about the approaches mentioned. My previous impressions are as follows * It is hard to believe that the thing can be done in Haskell without existential types (properly implemented). * Dependent types (Aldor, Cayenne) are the adequate instrument for the above task. * The proposal from haskell-cafe (year ago) does not look practicable. I tried certain simple example of using it to work with Z/(m), and it failed. But I hope, we will return to the subject after a month. ----------------- Serge Mechveliani mechvel(a)botik.ru

1 0

Re: ">>" and "do" notation
by Wolfgang Jeltsch 01 Apr '02

01 Apr '02

On Thursday, March 28, 2002, 16:37 CET James B. White III wrote: > [...] > I think the default definition of ">>" is just that, a default, and not a > law. I suppose, a >> b = a >>= \_ -> b is intended to be a law. This would mean that every redefined (>>) would have to obey this law. > [...] > If it is a law, why are users given the power to change it! For performance reasons, I would suppose. > Also, I think that the Report *specifies* the translation of "do" to ">>", > not merely suggests it. The report specifies certain identities and suggests to use these identities for translations into the kernel. If it is also a law that a >> b and a >>= \_ -> b are identical even with respect to laziness then, I think, a conforming Haskell implementation could use the latter instead of the former to realize do expressions. But I would prefer implementations using (>>). > [...] > ">>" should no longer be a class function with a default value that can be > changed; it should be syntactic sugar built into Haskell, like "do" > notation. It shouldn't be syntactic suger but at most an operator which does not belong to the monad class. One could define (>>) just as an ordinary function instead of a class member. > [...] By the way, why uses the report the complicated looking \_ -> b instead of just const b. Wolfgang

4 3

PLAN-X: Programming Language Technologies for XML
by Shriram Krishnamurthi 31 Mar '02

31 Mar '02

PLAN-X: PROGRAMMING LANGUAGE TECHNOLOGIES FOR XML Oct 3, 2002 Pittsburgh, PA (Co-located with PLI) CALL FOR PAPERS Submission deadline: May 1, 2002 XML has emerged as the de facto standard for data interchange on the web. The use of XML as a common format for representation, interchange, and transformation of data poses new challenges to programming languages, applications, and database systems. During the last few years, the database research community has devoted a lot of attention to XML's data representation challenges, as evidenced by the number of XML-related publications in premier database conferences and journals. In contrast, the attention devoted to XML by the programming language research community has been minimal. This is unfortunate, since the robustness of current and future programming standards and tools for XML will depend on the strength of their foundations in core programming technologies e.g., XML parsing (parsing theory and incremental parsing), XML schemas (type systems), XPATH expressions and XSLT programs (pattern-matching languages and their optimization), XSLT debuggers (dynamic program analysis and slicing). Since XML is a new domain, core programming technologies developed in past research cannot be used unchanged; instead, novel research is required to address the unique challenges posed by XML and its use in web applications and standalone applications. This workshop aims to bring together researchers from the programming languages and XML communities, a) to foster novel research to address unique challenges being posed by XML on current and future programming technologies; b) to exchange information on early research experiences with XML-related programming systems, tools, and languages; and c) to expose the PLI community to XML technologies and the potential impact of these technologies on future software. SUBMISSION PROCEDURE We solicit submissions on original research not previously published or currently submitted for publication elsewhere, in the form of extended abstracts. These extended abstracts should not exceed 5000 words (approximately 10 pages). Detailed submission instructions will be posted at http://www.research.avayalabs.com/user/wadler/planx by early April. PROCEEDINGS There will be no formal proceedings. An informal proceedings will be distributed at the workshop. IMPORTANT DATES Paper submission deadline May 1 Notification of acceptance June 21 Final papers due for informal proceedings Sep 4 WEB PAGE: http://www.research.avayalabs.com/user/wadler/planx/ GENERAL CHAIR: Vivek Sarkar, IBM PROGRAM COMMITTEE: Allen Brown (Microsoft) Peter Buneman (Edinburgh) Sophie Cluet (Xyleme / INRIA) Mary Fernandez (AT&T Labs) Shriram Krishnamurthi (Brown) Makoto Murata (IBM Japan) Benjamin Pierce (University of Pennsylvania), co-chair Michael Schwartzbach (Aarhus) Dan Suciu (University of Washington) Philip Wadler (Avaya Labs), co-chair INVITED SPEAKER: James Clark

1 0

Ѱ��
by tony 31 Mar '02

31 Mar '02

�װ��ѣ� ��ã� ��磨��ţ��޹�˾��ʺ��л��տ��ʼ��ϵ�ϣ��ܳ�Ϊ��ڹ� ��Ҫ��顣��һ�Ҳ��¼��ᾧ��о��ƹ�ͷ�չ�¼��ڻ��Ϣ��񡢵� ��ҵӦ�÷��ĸ��¼��ҵ��:http://www.raeline.net email:webmaster@raeline.net лл�� ˾��2000��ȫ��ʻ��Ƴ��²�Ʒ��ȫ��⽫�� ֵ��ѡ�� 1.30M�ռ䣫50M��ҵ��䣫1��ȫ�棬��198Ԫ/�ꡣ ��2.50M�ռ䣫100M��ҵ��䣫1��ȫ�棬��248Ԫ/�ꡣ ��3.100M�ռ䣫100M��ҵ��䣫1��ȫ�棬��318Ԫ/�ꡣ ��4.100M�ռ�+100M��䣫1��+��ַ��ģ��վ+��վ��ҵ��Ϣ ��1000Ԫ �� Ǿ��Ϊ��ṩ��õķ��񡣣��ų��ʧ��Ը��˿Ҳ��Ϊ ��һ��Ĳ��ġ��ǳ�ŵ��ⰴʵ��˿ ��ף��ģ�˳�� webmaster of raeline.net webmaster(a)raeline.net ��磨��ţ��޹�˾�� --------------------------------------------------------------- �е�Ⱥ��ʼ�,��ר��(http://www.21cmm.com) ��CMM��У(http://www.21cmm.com)��Ŀ��ר��

1 0

Unbind ">>"! (was Do-notation)
by James B. White III (Trey) 30 Mar '02

30 Mar '02

Here's my short manifesto on ">>" and "do" notation. It is based on the precedent set with "negate", a precedent that I also support. ">>" should be a member of the "Monad" class, just as "negate" is a member of the "Num" class! Users should have the power to override the default definition of ">>", just as they have the power to override the default definition of "negate"! Haskell compilers should honor user definitions for ">>" and not hard-wire ">>= \_ ->", just as they should honor user definitions for "negate" and do not hardwire "0 - x"! I have fixed the December 2001 release of Hugs to follow these principles for ">>". (I haven't tested the fix exhaustively. It works on my programs. Corrections appreciated!) Here are the "diffs", before the fix followed by after: connect.h: 74c74 < extern Name nameReturn, nameBind; /* for translating monad comps */ --- > extern Name nameReturn, nameBind, nameSequence; /* for translating monad comps */ type.c: 85c85 < Name nameReturn, nameBind; /* for translating monad comps */ --- > Name nameReturn, nameBind, nameSequence; /* for translating monad comps */ 3267a3268 > nameSequence = linkName(">>"); compiler.c: 397c397 < * do { e; qs } => LETREC _h _ = [ e | qs ] in bind m exp _h --- > * do { e; qs } => sequence m e qs 433,442c433,436 < case DOQUAL : { Cell hVar = inventVar(); < Cell ld = cons(pair(singleton(WILDCARD), < transDo(m,e,qs1)), < NIL); < return ap(LETREC, < pair(singleton(pair(hVar,ld)), < ap(ap(ap(nameBind, < m), < translate(snd(q))), < hVar))); --- > case DOQUAL : { > return ap(ap(ap(nameSequence, m), > translate(snd(q))), > transDo(m,e,qs1)); --- James B. White III (Trey) Center for Computational Sciences Oak Ridge National Laboratory whitejbiii(a)ornl.gov

1 0

Re: Z_n in Haskell
by oleg＠pobox.com 29 Mar '02

29 Mar '02

The Z_n problem doesn't seem to be different from the problem of arrays or bitvectors of a statically-checkable size. If you prefer a decimal specification of the modulus, you may find the following articles relevant. Implementation of fixed-precision decimal types: Main> BV D1 0 Bitvector of width 1 and value 0 Main> BV (D1,D2) 123 Bitvector of width 12 and value 123 Main> BV (D5,D7,D9) 31415 Bitvector of width 579 and value 31415 It appears that modulus in the Z_n problem plays the same role as the bitvector width in the bitvector problem. An attempt to perform an operation on bitvectors of different sizes results in a compiler error: Main> (BV (D1,D0) 10) `b_and` (BV (D1,D1) 7) ERROR - Type error in application *** Expression : b_and (BV (D1,D0) 10) (BV (D1,D1) 7) *** Term : BV (D1,D0) 10 *** Type : BitVector (D1,D0) *** Does not match : BitVector (D1,D1) http://groups.google.com/groups?selm=7eb8ac3e.0202201753.473a5cb2%40posting… Arbitrary precision decimal types, e.g.: Main> BV (D1 $ D2 $ D3 $ D4 $ D5 $ D6 $ D7 $ D8 $ D9 $ D0 $ D9 $ D8 $ D7 $ D6 $ D5 $ D4 $ D3 $ D2 $ D1 $ Dim) 1234567879 Bitvector of width 1234567890987654321 and value 1234567879 which are slightly more general and less convenient, are described in: http://groups.google.com/groups?selm=7eb8ac3e.0202230221.62d98db8%40posting… Both implementations work in any Haskell-98 system. Multi-parameter classes, existential types or other extensions are not needed.

1 0