[clean-list] Re: Passing an environment around
=?iso-8859-1?Q?Jos=E9_Romildo_Malaquias?=
romildo@urano.iceb.ufop.br
Sat, 21 Oct 2000 06:48:40 -0200
The following discussion is been conducted in the Clean mailing list.
As the issue is pertinent also to Haskell, I have cross-posted this
letter to the Haskell mailing list too.
Romildo.
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 don't see how alternative #3 would work.
>
> Of the three approaches, I think #1 is probably the best way to go.
> Functional programming encourages us to program with higher-order functions,
> and doing so naturally leads to this loss-of-sharing problem. Memoization
> is thus a useful tool. Adding it to Clean would probably help others as
> well as you.
>
>
> I recommend that you find out how real computer algebra systems address this
> issue. I've used these systems some and have the impression that there is a
> default set of simplification rules, plus some strategies for non-standard
> "simplifications" like factoring. You could apply the default set in a
> bottom-up way, with no need for memoization. This is precisely the approach
> used for algebraic simplification in Pan (an Haskell-based image synthesis
> library). See the recent paper "Compiling Embedded Languages" on my pubs
> page. You can also get the Pan source release to check out the real
> details.
>
> Good luck, and please let me know how it turns out.
>
> - Conal
>
> -----Original Message-----
> From: Simon Peyton-Jones
> Sent: Thursday, October 19, 2000 1:51 AM
> To: José Romildo Malaquias; clean-list@cs.kun.nl
> Cc: Conal Elliott (E-mail); Meurig Sage (E-mail)
> Subject: RE: [clean-list] Passing an environment around
>
> It's interesting that *exactly* this issue came up when Conal
> Eliott was implementing Fran in Haskell. His 'behaviours'
> are very like your expressions.
> type Behaviour a = Time -> a
> and he found exactly the loss of sharing that you did.
>
> For some reason, though, I'd never thought of applying the
> implicit-parameter
> approach to Fran. (Perhaps because Implicit parameters came along after
> Fran.)
> But I think it's rather a good idea.
>
> I think Conal may have a paper describing the implementation choices
> he explored; I'm copying him.
>
> Simon
>
> | -----Original Message-----
> | From: José Romildo Malaquias [mailto:romildo@urano.iceb.ufop.br]
> | Sent: 18 October 2000 08:12
> | To: clean-list@cs.kun.nl
> | Subject: [clean-list] Passing an environment around
> |
> |
> | Hello.
> |
> | I am implementing a Computer Algebra system (CALG) in Clean,
> | and I have a
> | problem I would like the opinion of Clean programmers.
> |
> | The CALG system should be able to simplify (or better, to transform)
> | algebraic expressions (from Mathematics) involving integers,
> | named constants
> | (like "pi" and "e"), variables, arithmetic operations (addition,
> | multiplication, exponentiation), and other forms of expressions
> | (trigonometric, logarithmic, derivatives, integrals,
> | equations, etc.). The
> | tansformaations should follow the rules from Algebra and
> | other areas of
> | Mathematica. But we know that in general an algebraic
> | expression can be
> | transformed in different ways, depending on the goal of the
> | transformation. Thus, the algebraic expression
> |
> | a^2 + b^2 + 3*a*b - a*b
> |
> | could result in
> |
> | a^2 + 2*a*b + b^2
> |
> | or in
> |
> | (a + b)^2
> |
> | To control the transformations made with an algebraic
> | expression there is a
> | set of flags collected in a record. I will call this record
> | the environment
> | in which the expression should be simplified. The algorithms I am
> | implementing may change this environment temporarily for some local
> | transformations. So the enviroment should be passed around in
> | the function
> | calls I am writing. This way the functions that implements the
> | transformations will have an extra argument representing the
> | environment in
> | which the transformation is to be performed.
> |
> | Let's take an example: the algorithm for addition will have
> | two arguments to
> | be added and a third argument corresponding to the enviroment:
> |
> | add :: Expr Expr Env -> Expr
> |
> | and its result will depend of the flags in the environment.
> | But it is highly
> | desirable to define functions like add as BINARY INFIX
> | OPERATORS. Having 3
> | arguments, add cannot be made a binary operator!
> |
> | --------------------------------------------------------------------
> | So I am looking for alternative ways to pass the environment around.
> | --------------------------------------------------------------------
> |
> | 1. Handle the arguments as functions themselves, which, given
> | an enviroment,
> | returns the simplified algebraic expression in that environment:
> |
> | add :: (Env -> Expr) (Env -> Expr) -> (Env -> Expr)
> |
> | Now add can be made a binary infix operator. This solution has the
> | disadvantage that we loose sharing when doing local
> | simplifications. For
> | example:
> |
> | f :: (Env -> Expr) (Env -> Expr) -> (Env -> Expr)
> | f fx fy = (add (add fx fy) fy)
> |
> | fe1, fe2 :: Env -> Exp
> | fe1 e = ...
> | fe2 e = ...
> |
> | initialEnv :: Env
> | initialEnv = ...
> |
> | Start = f fe1 fe2 initialEnv
> |
> | In this program fragment, fe2 may be applied twice to the same
> | environment value, computing its body twice. The resulting
> | program would
> | be too inneficient. If Clean had a mean of implementing MEMOIZATION
> | FUNCTIONS, the computation of a memoized function
> | application to the same
> | argument would evalute the body of the function only the
> | first time the
> | function is applied. Subsequent applications of that
> | function to the same
> | argument would remember the result of the previous
> | application and would
> | reutilize it. Then this way of handling environment
> | passing would be a
> | good solution.
> |
> | For more on memo functions see
> | <http://www.cse.ogi.edu/~byron/memo/dispose.ps>.
> |
> | 2. Extend Clean to support IMPLICIT PARAMETER PASSING (that
> | is, a form of
> | dynamic scoping), as has been done in some Haskell
> | implementations (Hugs,
> | GHC). Than the environment could be passed implicitly and
> | add could be
> | considered to have only 2 arguments
> |
> | add :: (Env ?env) => Exp Exp -> Exp
> |
> | Here ?env represents an implicit parameter. It is not
> | passed explicitly
> | like the two argument parameters. It can be used normally
> | in the function
> | definition, like any normal parameter. To pass an argument
> | implicitly,
> | there is 2 additional forms of expression: dlet and with:
> |
> | dlet ?env = ... in add e1 e2
> |
> | add e1 e2 with ?env = ...
> |
> | I think this could be the best solution to my problem, if Clean had
> | such extension implemented.
> |
> | For more information, see
> | <http://www.cse.ogi.edu/~jlewis/implicit.pdf.gz>
> |
> | 3. Join the algebraic expression and the environment in a single value
> |
> | add :: (Env,Exp) (Env,Exp) -> (Env,Exp)
> |
> | The enviroment is then carried around with each expression.
> | But now add has two enviroments to consult. Which one should be
> | used?
> |
> | Would be other good alternatives to solve this problem?
> |
> | Would future versions of Clean support
> |
> | - memoization functions, or
> | - implciit parameter passing?
> |
> | I am open to discussion on this topics.
> |
> | Regards,
> |
> | Romildo
> | --
> | Prof. José Romildo Malaquias <romildo@iceb.ufop.br>
> | Departamento de Computação
> | Universidade Federal de Ouro Preto
> | Brasil
> |
> | _______________________________________________
> | clean-list mailing list
> | clean-list@cs.kun.nl
> | http://www.cs.kun.nl/mailman/listinfo/clean-list
> |
>
> _______________________________________________
> clean-list mailing list
> clean-list@cs.kun.nl
> http://www.cs.kun.nl/mailman/listinfo/clean-list
--
Prof. José Romildo Malaquias <romildo@iceb.ufop.br>
Departamento de Computação
Universidade Federal de Ouro Preto
Brasil