[clean-list] Passing an environment around

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

On Wed, Oct 18, 2000 at 11:29:15AM -0500, Hamilton Richards wrote:
> At 5:12 AM -0200 10/18/00, José Romildo Malaquias wrote:
> >Hello.
> >
> >I am implementing a Computer Algebra system (CALG) in Clean, and I have a
> >problem I would like the opinion of Clean programmers.
> >
> [...]
> >
> >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.
> >  --------------------------------------------------------------------
> [...]
> 
> >
> >Would be other good alternatives to solve this problem?
> 
> Perhaps it would help to distinguish between (1) "the algorithm for
> addition" and (2) the transformation of expressions involving addition. If
> I don't misunderstand your problem, the environment is needed for the
> transformation, and not for the addition.
> 
> Consider representing your expressions as elements of a recursive algebraic
> type. For example (please excuse the Haskell syntax),
> 
> 	data Expr = Lit (Maybe Float) | Var String | Add Expr Expr |
> 	            Sub Expr Expr | Mul Expr Expr | Pow Expr Expr

In fact, the type of expressions is a recursive algebraic data type:

:: Fn = Sum        // sum
      | Pro        // product
      | Pow        // power
      | Log        // logarithm
      | Sin        // sin
      | Cos        // cossin
      | ATan       // arc tangent
      | Der        // derivative

:: Exp = Int Int
       | Cte String
       | Var String
       | App Fn [Expression]

being an expression
- an integer:		Int 2
- a named constant:	Cte ":pi"
- a (pure) variable:	Var "x"
- a functional:		App Sum [Int 2, Cte ":pi", Var "x"]

and the objective is to have library for manipulating exact
expressions. So there will not be any floating point numbers
as aproximations for real numbers and
	App Mul [Int 2, App Pow [Int 3, Int (-1)]]
is the canonical form for the rational 2/3

> Then the expression
> 
> 	a^2 + b^2 + 3*a*b - a*b
> 
> would be represented by
> 
> 	Sub (Add (Add (Pow "a" 2) (Pow "b" 2)) (Mul (Mul 3 "a") "b"))
>             (Mul "a" "b")
> 
> and translating ordinary infix expressions to instances of Expr is routine.

Yes, and I already have a parser for them in an application that uses the
library (an interactive calculator).

> 
> Then you'll have functions such as
> 
> 	transform :: Expr Env -> Expr  -- uses the environment
> 
> 	evaluate :: Expr -> Maybe Float  -- uses the algorithm for addition
> 
> and the issue of the arity of infix operators never arises.

The library should provide operations over expressions, as we
have in Mathematics. For example, in Math we can do:

	Let a, b and c real numbers. The solutions of the
	quadratic equation
		a*x^2 + b*x + c = 0
	is given by
		x' = (-b + sqrt(b^2 - 4*a*c))/(2*a)
	and
		x'' = (-b - sqrt(b^2 - 4*a*c))/(2*a)
	Write a function to find the (algebraic) solutions of
	a quadratic equation, given their coeficients.

To easily program this function one needs the operations over expressions:

  quadratic :: Exp Exp Exp -> (Exp, Exp)
  quadratic a b c = ( r + s, r - s )
    where
    r = - b / k
    s = (b^two - four * a * c)^(one/two) / k
    k = two * a

once the binary operators +, -, * and / are overloaded to work
with expressions.

This particular example do not use the environment
explicitly. But some complex algorithms queries the environment
in order to build the result.

So the transformations are made in order to simplify (or expand)
expressions. How that is done depends on the environment. In
an environment configured to expand multiplications over
sums, the product of (a + b) and (c + d) results in
	a*c + a*d + b*c + b*d
but if the environment is configured for not expanding, than it
would not be further developed, resulting in
	(a+b)*(c+d)

> Hope that helps,

Thanks for your comments.

As a member of the Clean team has alread pronounced, there is
no plan to implement the extensions I have commented on. So,
at least by now, there is no hope to have such functions
as binary operators and the environment should be passed
explicitly. This way the quadratic function above has to
be writen as something like:

  quadratic :: Env Exp Exp Exp -> (Exp, Exp)
  quadratic env a b c = ( sum r s, sub r s )
    where
    r = div (neg b) (mul two a)
    s = div (pow (sub (pow b two)
                      (pro (four (pro a c))))
                 (div one two))
            k
    k = mul two a

Bigger expressions would become unreadable.

Romildo
-- 
Prof. José Romildo Malaquias <romildo@iceb.ufop.br>
Departamento de Computação
Universidade Federal de Ouro Preto
Brasil