Glasgow Haskell "hacker's release" available (v 0.18)
I have dropped a snapshot of our current Glasgow Haskell sources on
ftp.dcs.glasgow.ac.uk, in pub/haskell/glasgow/working/, in
ghc-0.18-src.tar.gz (3MB, gzipped, probably unpacks to about 10MB).
This version, 0.18, is strictly a "hacker's release". The attached
ghc/README file provides a few details.
I will try to drop a ghc-0.18-bin-sun4.tar.gz in the same location in
the near future. We haven't done any porting work to speak of since
the 0.16/0.17 files, but I will drop intermediate C (.hc) files, etc.,
if people ask.
HACKERS: We *hope* to do our next public release in early December.
If you have code to be merged, could we please have it by the week of
Nov 22-26? I would prefer complete copies of changed or new files, so
I can do the diffs myself against some known base release.
Thanks for many fine reports and comments, folks. As usual, our
addresses are glasgow-haskell-{bugs,request}@dcs.glasgow.ac.uk.
Will Partain
assistant typist of the AQUA project
=== ghc-0.18/ghc/README ===
This is version 0.18 of the Glasgow Haskell compiler.
0.18 is an "internal" release intended *ONLY* for those actually
hacking on the compiler source -- that is, those who *REALLY* know
what they are doing. Anyone else is crazy to use it; anyone who uses
it without keeping a "real" GHC release (0.16 or 0.17) around is
obviously demented.
The chances of a "clean" build are near zero, no matter what Haskell
compiler you build with. Be prepared to utter magic incantations.
(For example, `make reader/ReadPragmas.o
EXTRA_HC_OPTS="-fno-strictness -fno-specialise -fno-case-of-case"'.)
An incomplete "what's new" list:
* Unfoldings across module boundaries. Still v limited.
* Specialisation of overloaded functions. Instances -- not yet.
* Strictness analyser that handles "nested" strictness and does
"absence analysis" as well. Makes Prelude.hi fun to read. Hints:
_N_ = nothing, _A_ = arity, _U_ = update analysis info, _S_ =
strictness (U = unpack, A = absent, L = lazy, S = strict, E = strict
& enumeration type, P = primitive).
* Prelude info no longer horribly built into the compiler (as much).
Manipulating the prelude is not nearly so delicate as it once was.
* Some names have changed: MkChar => C#, MkInt => I#, MkFloat => F#,
MkDouble => D#, MkInteger => J#. (They won't change again...)
* Includes Patrick Sansom's array-based substitution code (much faster
typechecking). (You probably won't see the speedup, though, because
we've spent all the savings on fancier intermodule stuff.)
* We've added a Core "lint" pass, which can be used to check
types/out-of-scope-errors/etc after every Core-to-Core pass. It's
great! -dcore-lint.
* Initial "Native" class support; use "-syslib hbc".
* Lots of compiler code hacked on, for better or worse.
* Lots of gratuitous "trace" messages when running the compiler :-)
Documentation is unchanged since 0.1[67]. There is not one word about
any new features.
We *hope* for a new public release before Christmas (1993).
Will Partain
Keeper of the Bits, AQUA Project
Dated: 93/11/04
E-mail contacts:
[EMAIL PROTECTED] (bug reports)
[EMAIL PROTECTED] (general queries)
Anonymous FTP site: ftp.dcs.glasgow.ac.uk:pub/haskell/glasgow. Mostly
mirrored by ftp.cs.chalmers.se and nebula.cs.yale.edu (same
directory). Also: src.doc.ic.ac.uk, in
computing/programming/languages/haskell/glasgow/.
Re: Liftedness again
>By "incompatible" I mean that you need parallel specualative evaluation >to implement it. So a truly polymorphic seq is out. That takes us back >to an overloaded version, except that seq couldn't have an instance for >(unlifted) tuples! At the risk of repeating myself: this is exactly right. A polymorphic function should need to know nothing about the type in which it is polymorphic. Many implementations behave quite differently when evaluating an integer, say, to evaluating a list. So operationally, seq does not reflect the usual intuition about polymorphism. Even worse (from the point of view of semantics), a "polymorphic" seq cripples parametricity (theorems for free). Already, because fix is polymorphic, the relations in the parametricity theorem are forced to be strict which throws away some interesting theorems. If seq were polymorphic, then the relations would have to be bottom-reflecting also (only bottom related to bottom) which throws away a vast number of theorems. (Even so it's not as bad as having equality polymorphic which forces the relations to be one-to-one making parametricity almost entirely useless). Using overloading solves the problem neatly. class Str a where seq : a -> a instance Str [a] where seq [] = [] seq (x:xs) = x:xs for example. Str can be added to the collection of things which are derivable, and everybody can sleep well at night. John.
Liftings
More on liftings: In our FPCA 91 paper, Simon and I came to the conclusion that the "proper" way to give semantics to data declarations was, as follows. If data T = A U V | B W then the model for T (written here T*) is T* = ((U* x V*) + W*)_\bot where the x is pure domain product, the + is disjoint union (i.e. not smash sum, not separated sum, but a union which results in a domain without a least element), and _\bot is lifting. The form of bottomless types is now obvious: bottomless S = A U V | B W is modelled by S* = (U* x V*) + W* What this means is that constructors really are playing three roles in standard Haskell: they are formed as a composition of lifting and injection into a sum, and introduce a (true) product. I believe we ought to be very cautious about introducing special cases for single constructors, for example, which do not generalise neatly. John.
Obfuscated Haskell Code Contest
Obfuscated Haskell Code Contest === THE TIME HAS COME! Haskell has now come of age and it is time to prove that we can do as good as C programmers can. Thus, the time has come for an obfuscated Haskell code contest. The contest is modelled after the corresponding C contest. But with Haskell we should be able to reach levels of obfuscation that C programmers can only dream of in their wildest nightmares. Just consider the exception filled lexical rules (e.g. comments), strange syntax (try mixing layout with no-layout), and a semantics that is still debated. The goal: a program of at most 1024 characters that is as incomprehensible as possible. Deadline: 1 Jan 1994. Send to: [EMAIL PROTECTED] Full rules (stolen from the C contest) below. Have fun -- Lennart Augustsson 1st International Obfuscated Haskell Code Contest Rules Obfuscate: tr.v. -cated, -cating, -cates. 1. a. To render obscure. b. To darken. 2. To confuse: his emotions obfuscated his judgment. [LLat. obfuscare, to darken : ob(intensive) + Lat. fuscare, to darken < fuscus, dark.] -obfuscation n. obfuscatory adj. GOALS OF THE CONTEST: * To write the most Obscure/Obfuscated Haskell program under the rules below. * To show what should NOT be done in Haskell programs. RULES: To help us handle the entries, we ask that you follow the rules below. 1) Your source MUST be 1024 bytes or less, and it must be a complete program, not just a subroutine. 2) To help us process your entries, we ask that you submit entries in the following format. Please be sure to include ALL --- lines, otherwise our extraction program may skip your entry! ---header items--- name: Your name, of course! org:School/Company/Organization email address: Email address from a well known site, or in a registered domain postal address: Postal address include your country as well environment:Indicate the compiler under which your program was tested entry: 5 remarks:Remarks may be continued with leading whitespace until the line ---how to compile-- is encountered. (see #3 below) ---how to compile--- Give the command(s) needed to compile your program using a Haskellcompiler. If you program should not be compiled under a K&R style C, leave this section blank. ---program--- Place obfuscated source of 1024 characters or less in this section. Add a leading X to each line to avoid problems with mailers. Some mailers don't like files with very long lines. If your entry contains lines longer 80 chars we ask you to send a uuencoded version of the file instead. ---end--- 3) Regarding the header items: * Any text outside of the above format will be kept confidential. * All header lines are required, but you may use 'anonymous' for any header line other than 'remarks' or 'entry'. * In the 'remarks' please include: - what this program does - why you think the program is obfuscated - any other remarks (humorous or otherwise) 4) Your entry should be written in standard Haskell 1.2. It should not use any preprocessor (e.g. cpp or an unliterator) nor any of the extended I/O requests from the appendix. 5) The program must be of original work. All programs must be in the public domain. All copyrighted programs will be rejected. 6) Entries must be received between before 1-Jan-94 0:00 UTC Email your entries to: [EMAIL PROTECTED] We will attempt to Email a confirmation of receipt of contest entries. 7) Each person may submit up to 8 entries. Multiple entries must be sent in separate Email letters. ANNOUNCEMENT OF WINNERS: * First announcement will likely be in mid January 1994. * Winning entries will be posted in comp.lang.functional. * Winners receive international fame and flames! :-) JUDGING: Awards will be given to the best entry in a number of categories. The actual category list will vary depending on the types of entries we receive. As a guide, consider using the following: * The strangest source layout * The most useful obfuscated program * The most creatively obfuscated program * Best obfuscated entry smaller than 256 bytes * Best abuse of overloading * Worst abuse of the rules (no abuse of entry format please!) * Extra points will be awarded to (correct) programs that break any of the existing Haskell systems.
Liftedness again
Warren makes an excellent point, though he doesn't highlight it: unlifted tuples are INCOMPATIBLE with seq By "incompatible" I mean that you need parallel specualative evaluation to implement it. So a truly polymorphic seq is out. That takes us back to an overloaded version, except that seq couldn't have an instance for (unlifted) tuples! The reason for this is that we can't implement unlifted tuples directly at all. Instead, we simulate them by making pattern matching lazy, so that _|_ behaves identically to (_|_,_|_), even though the two may have different runtime representations. The seq function exposes the trick! That's why Miranda fails in Warren's example. Is this what we want? Simon
Lifted Stuff
Some people have referred to semantic issues and Abramsky and Ong's work when contributing to the lifted/unlifted debate. I think it would be fair to summarise them as follows. Pro lifting === The simplest possible lambda calculus has lifting in its canonical model as soon as "laziness" is introduced. Otherwise, non-strict constructors could not be modelled in the calculus. When actual non-strict constructors are provided, therefore, essentially nothing new has been added. The same models work beautifully. Thus in my POPL 93 paper about lazy semantics, I used lifted function spaces to obtain a direct correspondence between operational and denotational semantics that held *everywhere*. Contrast this with Purushothaman and Seaman's ESOP 92 paper where they used unlifted function spaces, and there the correspondence was only true at base types. Summary: operational and denotational models "fit" with one another if function spaces are lifted (and products too by implication). Con Lifting === If our goal is to improve equational reasoning then, as many people have pointed out, more (interesting) equations hold when function and product spaces are not lifted. Furthermore, the natural semantics of unboxed types is that of domains without bottoms (FPCA 91), so if Haskell is ever likely to move (in the future) in the direction of accepting unboxed types into its definition, then it would make sense not to introduce possibly unnecessary liftings elsewhere. John.
Re: Liftedness again
Simon writes | Warren makes an excellent point, though he doesn't highlight it: | | unlifted tuples are INCOMPATIBLE with seq | | By "incompatible" I mean that you need parallel specualative evaluation | to implement it. So a truly polymorphic seq is out. That takes us back | to an overloaded version, except that seq couldn't have an instance for | (unlifted) tuples! I mentioned the other day that in fact it could. The question is whether this would be desirable. Consider the following: class Strict a where seq :: a -> b -> b strict :: (a -> b) -> a -> b seq x y = y strict f x = seq x (f x) instance Strict (a,b) instance Strict [a] where seq []y = y seq (_:_) y = y The question is what we want seq to mean. One possibility is seq x y = _|_ if x = _|_ y otherwise Another is more operational: seq x y = y if x has a whnf _|_ otherwise Since seq definitely has an operational flavor to it anyway, maybe this isn't so bad. The above declarations conform to this second approach. It's like saying that a pair is necessarily in whnf, as it has a (the only possible) constructor wrapped around it. Is this a good idea? On the one hand a programmer might be surprised that writing seq (x,y) z doesn't accomplish much of anything. (As far as that goes, he might also be surprised that seq (map f xs) y only resolves the first argument to nil or cons before proceeding with y.) On the other hand, if we have g = strict f where f is polymorphic in its argument type, an operational intent is that applications of g need not build a suspension for their arguments, which is the case for an (unlifted) pair, since it's already suspended. Thus, in a sense, seq and strict can have something resembling polymorphic implementations after all. | The reason for this is that we can't implement unlifted tuples directly at | all. Instead, we simulate them by making pattern matching lazy, so that | _|_ behaves identically to (_|_,_|_), even though the two may have different | runtime representations. The seq function exposes the trick! That's why | Miranda fails in Warren's example. As I said before, I think the issue is one of abstraction. Our implementations tend to have lifted tuples (and functions) but that shouldn't limit what the abstract values are. Naively adding a new operation to an ADT may reveal that the abstraction function was not an isomorphism. --Joe
Legal problems
Here are two more legal problems, ie problems concerning (broken) laws. The first is a problem with lifted functions spaces (even though I voted for them before), similar to Simon's recent "Effect 1". Consider: f [] = \y -> e1 g [] y = e1 f (x:xs) = \y -> e2 g (x:xs) y = e2 Is f _|_ = _|_ ? I guess so (the functions on the right needn't be so blatant) Is g _|_ = _|_ ? I guess so, because g = f Is seq (g _|_) 42 = _|_ ? It has to be, but this suggests that when a partial application is evaluated, other than because it is being applied to something, the `relevant amount' of pattern matching needs to be done to determine termination. This would be difficult to generalise, given current pattern matching practice. I think what's wrong here is the statement g = f, which relies on a relative of the eta rule, namely extensionality: "if for all x: g x = f x then g = f" which is only true for non-_|_ functions. Thus g /= f, g _|_ = \y -> g _|_ y and functions generally have have a `detectable' natural arity. (I have personally never liked partial application; it can lead to very bad error reporting for beginners for one thing. I still like higher order functions, of course.) The second problem concerns a law which I would like to see enforced: symmetry of arguments. That is, if I swap the arguments of a function (f x y goes to f y x) in its definition and in every call, there should be no overall effect on the program. I believe this is compatible with partial application if you are careful (although partial application does tend to promote asymmetrical thinking; another reason why I don't like it). However, is this compatible with current pattern matching practice? I am not sure (certainly with uniform patterns there are definitions which are not uniform when you exchange arguments, as Simon points out in his 1987 implementation book). Incidentally, we are experimenting with a compilation method which eliminates partial applications early on (and otherwise follows the STG route). It is easy to explain and implement, it supports a lifted function space, and it allows the standard C calling conventions to be used. At first sight, it appears costly; a call-and-return to evaluate every (dynamic) function value before appying it, but then you don't have to do a check for the right number of arguments on entry to every function. Ian[EMAIL PROTECTED], Tel: 0272 303334
re. Liftedness again
> Simon says:
> Warren makes an excellent point, though he doesn't highlight it:
>
> unlifted tuples are INCOMPATIBLE with seq
>
> The reason for this is that we can't implement unlifted tuples directly at
> all. Instead, we simulate them by making pattern matching lazy, so that
> _|_ behaves identically to (_|_,_|_), even though the two may have different
> runtime representations. The seq function exposes the trick!
In a private conversation with Arvind some days ago I pointed out
that, contrary to his earlier message, there is a situation where Id,
too, distinguishes lifted from unlifted tuples. It turns out to
correspond exactly to the situation that Warren and Simon cite. In Id
we have a sequencing construct (called a ``barrier'') which behaves in
the same way:
{ x = (e1,e2);
( y = x
--- % this sequences the statements in parens
z = y )
In
z }
This will return a tuple even if e1 and e2 diverge, whereas:
{ ( y = (e1,e2)
--- % this sequences the statements in parens
z = y )
In
z }
this will return a tuple only if e1 and e2 terminate.
Nikhil
Laws of unlifted tuples
Simon notes that lifted functions prevent certain optimisations, and then Joe wonders if lifting tuples prevents optimisations. Arvind has already answered this question. Unlifted tuples satisfy the type isomorphism (a,(b,c)) = (a,b,c) which is heavily used for optimising Id, but is invalid if tuples are lifted as in Haskell. Furthermore, only unlifted tuples satisfy the type isomorphism a -> b -> c = (a,b) -> c Just for sentimental reasons, I would like this last to hold in a language named for Haskell Curry. -- P
