[clean-list] Passing an environment around
Conal Elliott
conal@MICROSOFT.com
Thu, 19 Oct 2000 09:08:16 -0700
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.
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
|