Can't Haskell catch up with Clean's uniqueness typing?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
34 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Can't Haskell catch up with Clean's uniqueness typing?

haskell-cafe.mail.zooloo
Hi all,

being occupied with learning both languages, I'm getting curious if Haskell couldn't achieve most of the performance gains
resulting from uniqueness typing in Clean by *automatically* determining the reference count of arguments wherever
possible and subsequently allowing them to be physically replaced immediately by (the corresponding part of) the
function's result. Are there any principal obstacles, or *could* this be done, or *is* this even done already, e. g. in
ghc?


Regards,

zooloo






--
No virus found in this outgoing message.
Checked by AVG Free Edition.
Version: 7.1.362 / Virus Database: 267.13.12/192 - Release Date: 05.12.2005

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Optimistic Evaluation was Re: Can't Haskell catch up with Clean's uniqueness typing?

Shae Matijs Erisson
[hidden email] writes:

> being occupied with learning both languages, I'm getting curious if
> Haskell couldn't achieve most of the performance gains resulting from
> uniqueness typing in Clean by *automatically* determining the reference
> count of arguments wherever possible and subsequently allowing them to
> be physically replaced immediately by (the corresponding part of) the
> function's result. Are there any principal obstacles, or *could* this be
> done, or *is* this even done already, e. g. in ghc?

Maybe you're describing speculative evaluation?

Optimistic Evaluation: An Adaptive Evaluation Strategy for Non-Strict Programs
http://citeseer.ist.psu.edu/ennals03optimistic.html
--
Shae Matijs Erisson - http://www.ScannedInAvian.com/ - Sockmonster once said:
You could switch out the unicycles for badgers, and the game would be the same.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can't Haskell catch up with Clean's uniqueness typing?

Tomasz Zielonka
In reply to this post by haskell-cafe.mail.zooloo
On Tue, Dec 06, 2005 at 03:17:21PM +0100, [hidden email] wrote:
> being occupied with learning both languages, I'm getting curious if
> Haskell couldn't achieve most of the performance gains resulting from
> uniqueness typing in Clean by *automatically* determining the
> reference count of arguments wherever possible and subsequently
> allowing them to be physically replaced immediately by (the
> corresponding part of) the function's result.

We can get similar performance from Haskell using various features of
GHC (unboxed arrays, mutable arrays, ST monad, soon SMP, etc) and one
can argue that they are even nicer.

I liked the concept of UT in Clean, but I haven't ever got comfortable
with using it to write real programs.

> Are there any principal obstacles, or *could* this be done, or *is*
> this even done already, e. g. in ghc?

I think the biggest obstacle is that almost nobody asks for it.
Well, you asked, but how much Haskell code did you write to be
sure that you really need it?

Best regards
Tomasz

--
I am searching for a programmer who is good at least in some of
[Haskell, ML, C++, Linux, FreeBSD, math] for work in Warsaw, Poland
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can't Haskell catch upwith Clean's uniqueness typing?

haskell-cafe.mail.zooloo
In reply to this post by Shae Matijs Erisson

From: "Shae Matijs Erisson - [hidden email]"
Sent: Tuesday, December 06, 2005 6:16 PM


> [hidden email] writes:
>
> > being occupied with learning both languages, I'm getting curious if
> > Haskell couldn't achieve most of the performance gains resulting from
> > uniqueness typing in Clean by *automatically* determining the reference
> > count of arguments wherever possible and subsequently allowing them to
> > be physically replaced immediately by (the corresponding part of) the
> > function's result. Are there any principal obstacles, or *could* this be
> > done, or *is* this even done already, e. g. in ghc?
>
> Maybe you're describing speculative evaluation?
>
> Optimistic Evaluation: An Adaptive Evaluation Strategy for Non-Strict Programs
> http://citeseer.ist.psu.edu/ennals03optimistic.html
> --


Thanks for the pointer - I have heard a little about optimistic evaluation already, but don't know much of the
details (yet). Anyway, from what I know, I think it's a different thing.

In Clean, you can (and often are required to) assign uniqueness attributes to some parts of a function's type signature.
The extended type checker ensures that none of those parts is referred to more than once during a single run of the
program. Based on this guarantee, a function does not have to allocate new memory at all to store a unique result but can
overwrite the unique arguments in place.

Apparently, the uniqueness assignments have to comply with very tight laws - getting a program through the Clean type
checker can be tough, once it reports an uniqueness coercion error. I suppose, no explicit uniqueness attributing is going
to be implemented in Haskell, anyway.

My question is - and this might better suit to Haskell -, can't uniqueness be inferred (and exploited) automatically in
many cases?


Regards,

zooloo




--
No virus found in this outgoing message.
Checked by AVG Free Edition.
Version: 7.1.371 / Virus Database: 267.13.12/192 - Release Date: 05.12.2005

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can't Haskell catch upwith Clean's uniqueness typing?

Bugzilla from robdockins@fastmail.fm
On Tuesday 06 December 2005 04:00 pm, [hidden email] wrote:

> From: "Shae Matijs Erisson - [hidden email]"
> Sent: Tuesday, December 06, 2005 6:16 PM
>
> > [hidden email] writes:
> > > being occupied with learning both languages, I'm getting curious if
> > > Haskell couldn't achieve most of the performance gains resulting from
> > > uniqueness typing in Clean by *automatically* determining the reference
> > > count of arguments wherever possible and subsequently allowing them to
> > > be physically replaced immediately by (the corresponding part of) the
> > > function's result. Are there any principal obstacles, or *could* this
> > > be done, or *is* this even done already, e. g. in ghc?
> >
> > Maybe you're describing speculative evaluation?
> >
> > Optimistic Evaluation: An Adaptive Evaluation Strategy for Non-Strict
> > Programs http://citeseer.ist.psu.edu/ennals03optimistic.html
> > --
>
> Thanks for the pointer - I have heard a little about optimistic evaluation
> already, but don't know much of the details (yet). Anyway, from what I
> know, I think it's a different thing.
>
> In Clean, you can (and often are required to) assign uniqueness attributes
> to some parts of a function's type signature. The extended type checker
> ensures that none of those parts is referred to more than once during a
> single run of the program. Based on this guarantee, a function does not
> have to allocate new memory at all to store a unique result but can
> overwrite the unique arguments in place.
>
> Apparently, the uniqueness assignments have to comply with very tight laws
> - getting a program through the Clean type checker can be tough, once it
> reports an uniqueness coercion error. I suppose, no explicit uniqueness
> attributing is going to be implemented in Haskell, anyway.
>
> My question is - and this might better suit to Haskell -, can't uniqueness
> be inferred (and exploited) automatically in many cases?

Yes, probably.  There is a technique called sharing analysis that attempts to
determine when a datastructure is only referenced once (ie, NOT shared).  If
you can prove a datastructure node is not shared then you can reuse it
destructively.

Here is a paper on the technique.  It's written for lisp cons cells, but one
might be able to generalize the technique to ADT.  I don't know where to find
a free copy.

http://portal.acm.org/citation.cfm?id=99375


There has also been some similar work done along these lines for Mercury (a
logic programming language).

http://www.cs.mu.oz.au/research/mercury/information/papers.html

Search for papers with the word "reuse" in the title.  I'm not very familiar
with this work, so I don't know how applicable this might be.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can't Haskell catch upwith Clean's uniqueness typing?

greenrd
In reply to this post by haskell-cafe.mail.zooloo
On Tuesday 06 December 2005 21:00, [hidden email] wrote:
> In Clean, you can (and often are required to) assign uniqueness attributes
> to some parts of a function's type signature. The extended type checker
> ensures that none of those parts is referred to more than once during a
> single run of the program. Based on this guarantee, a function does not
> have to allocate new memory at all to store a unique result but can
> overwrite the unique arguments in place.

The rough equivalent to this in Haskell would be ST and STRefs, I believe.
They work somewhat differently, however.

> My question is - and this might better suit to Haskell -, can't uniqueness
> be inferred (and exploited) automatically in many cases?

I'm not sure that uniqueness is the right thing to focus on here. I see this
suggestion as a special case of situations where the compiler can know that a
value will never be needed after a certain point, and therefore it can be
free'd instead of being garbage collected (I don't know the technical term
for that). These situations are - surely - not limited to situations where
the value is referred to only once.

--
Robin
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can't Haskell catch up with Clean's uniqueness typing?

Jan-Willem Maessen
In reply to this post by haskell-cafe.mail.zooloo

On Dec 6, 2005, at 9:17 AM, [hidden email] wrote:

> Hi all,
>
> being occupied with learning both languages, I'm getting curious if  
> Haskell couldn't achieve most of the performance gains
> resulting from uniqueness typing in Clean by *automatically*  
> determining the reference count of arguments wherever
> possible and subsequently allowing them to be physically replaced  
> immediately by (the corresponding part of) the
> function's result. Are there any principal obstacles, or *could*  
> this be done, or *is* this even done already, e. g. in
> ghc?

Yes, this could be done.  The principle obstacles are the same as for  
any reference counting scheme: It imposes more run-time overhead than  
GC does, unless the data structures involved are large.  Let me  
repeat that: accurate up-to-the-moment reference counting is  
dramatically slower than GC.  Techniques exist to make ref counting  
fast, but they all require the equivalent of a full stack walk in  
order to get an accurate count.

That said, clever techniques (like 1-bit ref counting) are available  
that will get 80% of what is desired.  1-bit reference counting keeps  
a single bit which says either "this is certainly the only reference"  
or "other references may exist".  The bit can be kept in the pointer  
itself.  There's still run-time overhead, though---the bit must be  
masked on each pointer dereference.

Wearing my "Fortress language designer" hat, we've given serious  
thought to these techniques for very large arrays.  Copying such  
structures is terribly expensive, or even impossible (imagine copying  
a 1PB array).  I'd think hard before I used them for, say, cons cells.

Shae: All this is very, very different from eager / optimistic  
evaluation.

-Jan-Willem Maessen

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re[2]: Can't Haskell catch upwith Clean's uniqueness typing?

Bulat Ziganshin
In reply to this post by Bugzilla from robdockins@fastmail.fm
Hello Robert,

Wednesday, December 07, 2005, 2:19:22 AM, you wrote:

>> In Clean, you can (and often are required to) assign uniqueness attributes
>> to some parts of a function's type signature. The extended type checker
>> ensures that none of those parts is referred to more than once during a
>> single run of the program. Based on this guarantee, a function does not
>> have to allocate new memory at all to store a unique result but can
>> overwrite the unique arguments in place.
>>
>> My question is - and this might better suit to Haskell -, can't uniqueness
>> be inferred (and exploited) automatically in many cases?

RD> Yes, probably.  There is a technique called sharing analysis that attempts to
RD> determine when a datastructure is only referenced once (ie, NOT shared).  If
RD> you can prove a datastructure node is not shared then you can reuse it
RD> destructively.

may be, John Meacham can say something about it? his JHC compiler uses
region analysis to avoid garbage collection - may be these techniques
has something in common?

--
Best regards,
 Bulat                            mailto:[hidden email]



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can't Haskell catch up with Clean's uniqueness typing?

David Roundy
In reply to this post by Jan-Willem Maessen
On Wed, Dec 07, 2005 at 08:21:42AM -0500, Jan-Willem Maessen wrote:
> Yes, this could be done.  The principle obstacles are the same as for any
> reference counting scheme: It imposes more run-time overhead than GC
> does, unless the data structures involved are large.  Let me repeat that:
> accurate up-to-the-moment reference counting is dramatically slower than
> GC.  Techniques exist to make ref counting fast, but they all require the
> equivalent of a full stack walk in order to get an accurate count.

For strict functions, does ghc do optimizations like this automatically?
i.e. can it statically count references and avoid allocation of
intermediates?
--
David Roundy
http://www.darcs.net
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can't Haskell catch up with Clean's uniqueness typing?

Wolfgang Jeltsch
In reply to this post by Jan-Willem Maessen
Am Mittwoch, 7. Dezember 2005 14:21 schrieb Jan-Willem Maessen:
> [...]

> The principle obstacles are the same as for any reference counting scheme:
> It imposes more run-time overhead than GC does, unless the data structures
> involved are large.

Why?  I think the point with uniqueness typing/analysis is that this is done
at *compile-time*.

> [...]

Best wishes,
Wolfgang
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can't Haskell catch up with Clean's uniqueness typing?

haskell-cafe.mail.zooloo
In reply to this post by Jan-Willem Maessen

----- Original Message -----
From: "Jan-Willem Maessen - [hidden email]"
Sent: Wednesday, December 07, 2005 2:21 PM
>
> Wearing my "Fortress language designer" hat, we've given serious
> thought to these techniques for very large arrays.  Copying such
> structures is terribly expensive, or even impossible (imagine copying
> a 1PB array).

That's slightly beyond the size of arrays I am currently dealing with. ;) I can see that in-place updating is of utmost
importance in such cases.

However, I was actually thinking of something the Clean people call "garbage collection at compile time", which, as far as
I can see, involves no runtime overhead at all (Clean Language Report 2.1, section 9.1. -
ftp://ftp.cs.kun.nl/pub/Clean/Clean20/doc/CleanLangRep.2.1.pdf).

I don't quite see why it should be necessary to specify uniqueness attributes explicitely (as it mostly is in Clean), if
the type checker knows the coercion laws better than me, anyway. Hence, my question about automatically deriving
uniqueness properties of tokens, to the greatest extent safely feasible at compile time. (Sorry, if this is all trivial
and already implemented in ghc. As indicated, I am merely learning Haskell, and I haven't spent any mentionable time yet
to understand compiler intestines.)


Regards,

zooloo



--
No virus found in this outgoing message.
Checked by AVG Free Edition.
Version: 7.1.371 / Virus Database: 267.13.12/192 - Release Date: 05.12.2005

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can't Haskell catch up with Clean's uniqueness typing?

haskell-cafe.mail.zooloo
In reply to this post by Tomasz Zielonka


----- Original Message -----
From: "Tomasz Zielonka - [hidden email]"
Sent: Tuesday, December 06, 2005 9:18 PM


>
> We can get similar performance from Haskell using various features of
> GHC (unboxed arrays, mutable arrays, ST monad, soon SMP, etc) and one
> can argue that they are even nicer.
>
> I liked the concept of UT in Clean, but I haven't ever got comfortable
> with using it to write real programs.
>


Clean-like _explicit_ uniqueness typing is not what I'm asking for in Haskell.

>
> I think the biggest obstacle is that almost nobody asks for it.
> Well, you asked, but how much Haskell code did you write to be
> sure that you really need it?
>


Indeed, my own experience is too limited to really compare. However, the latest ghc survey,

http://haskell.org/ghc/survey2005-summary.html

suggests that "Performance of compiled code" is a top issue to others, too. OC, this involves various aspects, with memory
usage being only one of them.


It might be possible to get extremely fast code out of ghc, but as an overall impression, it's not easy, whilst Clean sort
of gives it for granted (well, struggeling with wrongly assigned uniqueness attributes aside).


In the debian shootout,

http://shootout.alioth.debian.org/benchmark.php?test=all&lang=ghc&lang2=clean,

programs generated by ghc generally need multiples of time and space of the Clean version, even though the latter is, in
many cases, a nearly literal translation from Haskell.

I know, all this is not representative. Anyway, it may serve as motivation for my question (or suggestion).


Regards,

zooloo



--
No virus found in this outgoing message.
Checked by AVG Free Edition.
Version: 7.1.371 / Virus Database: 267.13.12/192 - Release Date: 05.12.2005

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can't Haskell catch up with Clean's uniqueness typing?

Greg Buchholz
[hidden email] wrote:
> It might be possible to get extremely fast code out of ghc, but as an overall
> impression, it's not easy, whilst Clean sort of gives it for granted (well,
> struggeling with wrongly assigned uniqueness attributes aside).

<snip>

> programs generated by ghc generally need multiples of time and space of the
> Clean version, even though the latter is, in many cases, a nearly literal
> translation from Haskell.

Maybe you'd be interested in Hacle?

  http://www-users.cs.york.ac.uk/~mfn/hacle/
   
  " The aim was to develop a translator which is capable of reading in any
   given Haskell'98 program and writing out a semantically equivalent Clean
   one. Why? To investigate the suitability of the Clean compiler for
   compiling Haskell programs, i.e.  Can the Clean compiler, in combination
   with this tool, produce faster executables than existing Haskell
   compilers? "


Greg Buchholz
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can't Haskell catch up with Clean's uniqueness typing?

Sebastian Sylvan
On 12/7/05, Greg Buchholz <[hidden email]> wrote:

> [hidden email] wrote:
> > It might be possible to get extremely fast code out of ghc, but as an overall
> > impression, it's not easy, whilst Clean sort of gives it for granted (well,
> > struggeling with wrongly assigned uniqueness attributes aside).
>
> <snip>
>
> > programs generated by ghc generally need multiples of time and space of the
> > Clean version, even though the latter is, in many cases, a nearly literal
> > translation from Haskell.
>
> Maybe you'd be interested in Hacle?
>
>   http://www-users.cs.york.ac.uk/~mfn/hacle/
>
>   " The aim was to develop a translator which is capable of reading in any
>    given Haskell'98 program and writing out a semantically equivalent Clean
>    one. Why? To investigate the suitability of the Clean compiler for
>    compiling Haskell programs, i.e.  Can the Clean compiler, in combination
>    with this tool, produce faster executables than existing Haskell
>    compilers? "

That looks interesting. I wonder what the results mean =)

It could be that Clean and Haskell are roughly equivalent in speed
(modulo som variance), or it could mean that GHC is great at
optimizing Haskell code, but in certain cases uniqueness typing (among
other things?) gives so much benifits that it outweights GHC's
optimization.
It definatly means that there are cases where GHC could improve significantly.

Nevertheless, Haskell speed is definatly a big issue for many. It is a
general purpose language, after all, and that makes speed important.
For "single-purpose" languages like, say, php it's not as important
(because you're not going to write, say, a game engine in php for
reasons other than speed).

Haskell is certainly better now than it used to be, but there's plenty
of room for improvement.


/S

--
Sebastian Sylvan
+46(0)736-818655
UIN: 44640862
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can't Haskell catch up with Clean's uniqueness typing?

haskell-cafe.mail.zooloo
In reply to this post by haskell-cafe.mail.zooloo
On Wed, Dec 07, 2005 at 05:59:55PM +0100, [hidden email] wrote:
> > I liked the concept of UT in Clean, but I haven't ever got comfortable
> > with using it to write real programs.
>
> Clean-like _explicit_ uniqueness typing is not what I'm asking for in Haskell.

So you want implicit, automatically inferred uniqueness typing -
something that would be even more fragile and sensitive then current
Haskell's space problems arising from laziness? ;-)

> It might be possible to get extremely fast code out of ghc, but as an
> overall impression, it's not easy, whilst Clean sort of gives it for
> granted (well, struggeling with wrongly assigned uniqueness attributes
> aside).

Well, C sort of gives it for granted too, because it is very difficult
to write inefficient, simple, specification-like code. I want to be able
to write simple and elegant code, even if it is inefficient!

Best regards
Tomasz

--
I am searching for a programmer who is good at least in some of
[Haskell, ML, C++, Linux, FreeBSD, math] for work in Warsaw, Poland
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can't Haskell catch up with Clean's uniqueness typing?

haskell-cafe.mail.zooloo
In reply to this post by Sebastian Sylvan

----- Original Message -----
From: "Sebastian Sylvan - [hidden email]"
Sent: Wednesday, December 07, 2005 8:36 PM
>
> > Maybe you'd be interested in Hacle?
> >
> >   http://www-users.cs.york.ac.uk/~mfn/hacle/

Yep, I am. :) I've discovered it a while ago.

> >
> >   " The aim was to develop a translator which is capable of reading in any
> >    given Haskell'98 program and writing out a semantically equivalent Clean
> >    one. Why? To investigate the suitability of the Clean compiler for
> >    compiling Haskell programs, i.e.  Can the Clean compiler, in combination
> >    with this tool, produce faster executables than existing Haskell
> >    compilers? "
>
> That looks interesting. I wonder what the results mean =)
>
> It could be that Clean and Haskell are roughly equivalent in speed
> (modulo som variance), or it could mean that GHC is great at
> optimizing Haskell code, but in certain cases uniqueness typing (among
> other things?) gives so much benifits that it outweights GHC's
> optimization.

Just a side note (please, correct me if I'm wrong): Hacle does not even make use of uniqueness typing (apart from *World
and *File), so any benefits are due to other differences, like, inferred strictness.


Regards,

zooloo




--
No virus found in this outgoing message.
Checked by AVG Free Edition.
Version: 7.1.371 / Virus Database: 267.13.12/192 - Release Date: 05.12.2005

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can't Haskell catch upwith Clean's uniqueness typing?

John Meacham
In reply to this post by Bulat Ziganshin
On Wed, Dec 07, 2005 at 04:38:19PM +0300, Bulat Ziganshin wrote:
> may be, John Meacham can say something about it? his JHC compiler uses
> region analysis to avoid garbage collection - may be these techniques
> has something in common?

By the time jhc makes any decisions regarding memory management, the
code has already been transformed into a first order, strict, imperative
language (but with stronger types than normal and in a monad) so I am
not sure how much they would have in common.

But there definitely are higher level optimizations that achieve similar
things, update avoidance being a particular one as it collects pretty
much exactly the info we want, when a node will only be referenced once.
GHC has some very advanced algorithms for this sort of thing and I
believe from first glance they will do a better job than the clean
system.

The update analysis info in jhc is not propegated all the way to the
back end, the grin compiler does do a separate analysis to recapture
this type of info after various transformations. I found it somewhat
tricky to maintain the annotations all the way through various
optimizations so I recalculate it (and perhaps get better results on the
simpler program).

However figuring out a way to propagate  that info would be vital if we
wanted user supplied region annotations, which several papers have said
can be very beneficial. It is not clear at all what they would look like
in a lazy language though since your run-time stack does not follow your
program structure. (I'm open to ideas...)

        John

--
John Meacham - ?repetae.net?john?
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can't Haskell catch up with Clean's uniqueness typing?

haskell-cafe.mail.zooloo
In reply to this post by haskell-cafe.mail.zooloo

----- Original Message -----
From: "Tomasz Zielonka - [hidden email]"
Sent: Wednesday, December 07, 2005 8:53 PM


> >
> > Clean-like _explicit_ uniqueness typing is not what I'm asking for in Haskell.
>
> So you want implicit, automatically inferred uniqueness typing -
> something that would be even more fragile and sensitive then current
> Haskell's space problems arising from laziness? ;-)
>

Maybe it's just my lacking insight, but why should uniqueness inferring be all that fragile? A uniqueness checker can be
rather robust, as is demonstrated by the Clean one, so all we'd have to worry about is how to find a good set of
supposedly unique node candidates to suggest to the checker. (It certainly would not work well the dumb way, like, trying
every single combination out of n^2 possibilities, where n is the total node count.)

Whatever suggestion gets through the uniqueness checker, the resulting code can't be consuming more space, slower, or
otherwise worse than the one without reusing unique nodes, can it? On the other hand, performance gains thereby seem
likely to me.

> > It might be possible to get extremely fast code out of ghc, but as an
> > overall impression, it's not easy, whilst Clean sort of gives it for
> > granted (well, struggeling with wrongly assigned uniqueness attributes
> > aside).
>
> Well, C sort of gives it for granted too, because it is very difficult
> to write inefficient, simple, specification-like code. I want to be able
> to write simple and elegant code, even if it is inefficient!
>

errr..., could you give me some clue how you'd expect automatically uniqueness detection to deteriorate your coding style?
I, for one, don't define elegance in terms of not running too fast. ;)

I don't feel very comfortable either with the impact _explicit_ uniqueness attributing has on the ease of coding. Anyway,
I am not arguing pro Clean but pro compile time sharing analysis here.

To be honest, your reply feels like a counterpart to the likewise questionable monad avoidance in Clean.


Regards,

zooloo



p. s.: Anyone knows what makes your cited mail appear in the list archive as beeing sent from my address? The copy I got
to my mailbox is ok.




--
No virus found in this outgoing message.
Checked by AVG Free Edition.
Version: 7.1.371 / Virus Database: 267.13.12/192 - Release Date: 05.12.2005

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can't Haskell catch up with Clean's uniqueness typing?

Wolfgang Jeltsch
In reply to this post by Wolfgang Jeltsch
Am Donnerstag, 8. Dezember 2005 04:00 schrieb Jan-Willem Maessen:

> On Dec 7, 2005, at 9:58 AM, Wolfgang Jeltsch wrote:
> > Am Mittwoch, 7. Dezember 2005 14:21 schrieb Jan-Willem Maessen:
> >> [...]
> >>
> >> The principle obstacles are the same as for any reference counting
> >> scheme:  It imposes more run-time overhead than GC does, unless the data
> >> structures involved are large.
> >
> > Why?  I think the point with uniqueness typing/analysis is that
> > this is done at *compile-time*.
>
> But the email asked if there were some other way of doing this using
> run-time techniques in the absence of such a type system (or at
> least, that was the way I understood it, and the spirit of my answer).

I thought that the original question was about using some kind of uniqueness
type system at an intermediate stage during compiling.  Haskell would still
have no uniqueness types but the compiler would infer uniqueness types
internally and use the uniqueness information it gets from this.

> -Jan

> [...]

Best wishes,
Wolfgang
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can't Haskell catch up with Clean's uniqueness typing?

haskell-cafe.mail.zooloo
----- Original Message -----
From: "Wolfgang Jeltsch - [hidden email]"
Sent: Thursday, December 08, 2005 6:13 PM
>
> I thought that the original question was about using some kind of uniqueness
> type system at an intermediate stage during compiling.  Haskell would still
> have no uniqueness types but the compiler would infer uniqueness types
> internally and use the uniqueness information it gets from this.
>
 
Right, that's what I was having in mind. See also http://www.haskell.org/pipermail/haskell-cafe/2005-December/012625.html


Regards,

zooloo



--
No virus found in this outgoing message.
Checked by AVG Free Edition.
Version: 7.1.371 / Virus Database: 267.13.12/192 - Release Date: 05.12.2005

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
12