Passing an environment around

José 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