[clean-list] Passing an environment around

[=?iso-8859-1?Q?Jos=E9_Romildo_Malaquias?=]

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