On Fri, Oct 27, 2000 at 09:07:24AM -0700, Jeffrey R. Lewis wrote:
José Romildo Malaquias wrote:
On Thu, Oct 19, 2000 at 09:08:16AM -0700, Conal Elliott wrote:
Indeed Fran behaviors are like your alternative #1 (function passing), and hence sharing loss is a concern. Simon PJ is right that I have a paper discussing this issue and some others. See "Functional Implementations of Continuous Modeled Animation" on my pubs page (http://research.microsoft.com/~conal/papers).
About alternative #2 (implicit arguments), would it help? Does it eliminate the non-memoized redundant function applications, or just hide them? For Fran, Erik Meijer suggested implicit functions to me a couple of years ago. I hadn't thought of it, and it did indeed seem to be attractive at first as a way to eliminate the need for overloading in Fran. However, the (Time -> a) representation of Fran behaviors is not really viable, so I wouldn't merely want to hide that representation behind implicit arguments.
It seems that implicit parameters does not eliminate redundant function applications, as Conal Elliott has commented. Reading the paper
Implicit Parameters: Dynamic Scoping with Static Types Jefrrey Lewis, Mark Shields, Erik Meijer, John Launchbury http://www.cse.ogi.edu/~jlewis/
(especially section 5.1) I got this impression. I would like to hear from others as well, as I had some difficulties with the paper.
I am sorry you had difficulties!
The difficulties I had is basicaly due to my lack of solid knowledge on type theory and semantic formalisms. Not that the paper was badly written.
Yes, as implemented using the dictionary translation, implicit parameterization can lead to loss of sharing, exactly in the same way that overloading (and HOF in general) can lead to loss of sharing.
However, I can imagine that a compiler might chose to implement implicit parameters more like dynamic variables in lisp. Each implicit param essentially becomes a global variable, implemented as a stack of values - the top of the stack is the value currently in scope. This would avoid the sharing problem nicely.
--Jeff
I suppose your implementation of implicit parameterization in GHC and Hugs uses the dictionary translation, right? Would an alternative implementation based on a stack of values be viable and even done? Does it have serious drawbacks when compared with the dictionary translation technique? Thanks. Romildo -- Prof. José Romildo Malaquias <romildo@iceb.ufop.br> Departamento de Computação Universidade Federal de Ouro Preto Brasil
On 27-Oct-2000, José Romildo Malaquias <romildo@urano.iceb.ufop.br> wrote:
On Fri, Oct 27, 2000 at 09:07:24AM -0700, Jeffrey R. Lewis wrote:
Yes, as implemented using the dictionary translation, implicit parameterization can lead to loss of sharing, exactly in the same way that overloading (and HOF in general) can lead to loss of sharing.
However, I can imagine that a compiler might chose to implement implicit parameters more like dynamic variables in lisp. Each implicit param essentially becomes a global variable, implemented as a stack of values - the top of the stack is the value currently in scope. This would avoid the sharing problem nicely.
I suppose your implementation of implicit parameterization in GHC and Hugs uses the dictionary translation, right?
I believe so.
Would an alternative implementation based on a stack of values be viable
Yes.
and even done?
Unlikely ;-)
Does it have serious drawbacks when compared with the dictionary translation technique?
In the form described by Jeff Lewis above, yes, it does: it's not thread-safe. An alternative is to store the values of the implicit parameters in thread-local storage rather than global storage. But this is more complicated. It may also be less efficient on some targets (depending on how efficiently thread-local storage is implemented). -- Fergus Henderson <fjh@cs.mu.oz.au> | "I have always known that the pursuit | of excellence is a lethal habit" WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.
Fergus Henderson wrote:
On 27-Oct-2000, José Romildo Malaquias <romildo@urano.iceb.ufop.br> wrote:
On Fri, Oct 27, 2000 at 09:07:24AM -0700, Jeffrey R. Lewis wrote:
Yes, as implemented using the dictionary translation, implicit parameterization can lead to loss of sharing, exactly in the same way that overloading (and HOF in general) can lead to loss of sharing.
However, I can imagine that a compiler might chose to implement implicit parameters more like dynamic variables in lisp. Each implicit param essentially becomes a global variable, implemented as a stack of values - the top of the stack is the value currently in scope. This would avoid the sharing problem nicely.
I suppose your implementation of implicit parameterization in GHC and Hugs uses the dictionary translation, right?
I believe so.
Sorry - that wasn't clear from my reply - yes, implicit parameters in GHC are compiled using the dictionary translation.
Would an alternative implementation based on a stack of values be viable
Yes.
and even done?
Unlikely ;-)
That's a shame ;-)
An alternative is to store the values of the implicit parameters in thread-local storage rather than global storage. But this is more complicated. It may also be less efficient on some targets (depending on how efficiently thread-local storage is implemented).
I don't know the costs associated w/ thread local storage - how is it likely to compare w/ the dictionary passing implementation? --Jeff
participants (3)
-
Fergus Henderson -
Jeffrey R. Lewis -
José Romildo Malaquias