Modeling Algebra Expressions

SPAD allows symbolic expressions to be created, this uses the Expression domain which in turn uses the Kernel domain. Expression has specific support for symbolic expressions in terms of domains/categories (such as: GcdDomain, Integer, IntegralDomain, Ring, AbelianMonoid and SemiGroup). That is the code has specific tests and chunks of code for these. Symbolic functions are explicitly listed in Expression (such as: pi, exp, log, sin, cos...).

This is very powerful for algebras, like 'ring' and 'field' that are well supported. What I would like to do is allow symbolic expressions to be created and manipulated (for example equation solvers where this is possible) for any domain I am working on. Just to make this clear, SPAD already allows a value of any type to be given an alphanumeric label, we can set this to a value given by an expression but this must always evaluate to a literal value. We can't, in general, put an unknown on the right hand side of an assignment. I would like better general support for equations and equation solvers for any domain. Also I would like to be able to express (and preferably to enforce) the axioms for a given domain.

For example, I would like to have symbolic names for elements of a Clifford algebra and to be able to create expressions involving these. I would like to be able to do this without hacking the Expression domain (which is already very messy). It would be much better for people working on the code if this were done in, or near, the Clifford algebra domain. I would not want to duplicate the general expression handling code, only separate out the parts that change for different algebras.

This may not be simple so, on this page, I would like to try to discover the top level principles.

Variables verses Combinators

I can think of two ways to approach the above issues:

In the first we would need to have 'equations'. SPAD supports equations (in 'Equation' domain) but, again, it does not seem general in that it is based on predefined operations like: +,-,*,/,1 and = so it has to have specific code for various categories of algebras. The Equation domain also has support for specific operations on the whole equation such as differentiation.

The Equation domain has a representation containing lhs and rhs both of which can be any type.

Combinators could use a language like 'Joy' which is based on the concept of a stack.

Catamorphism and Anamorphism

If we start with an algebra that has a binary operation (S,S)->S and, instead of supplying interal values we supply a symbolic value to represent a variable or unknown, we might build up a free algebra. free algebra

 

catamorphism anamorphism

Catamorphism

Reduces the data structure to a required value.

Tree is a initial object in the category of F-algebras

Anamorphism

Upwards morphism - Builds an invocation tree as an explicit data structure.

zip and iterate are examples of anamorphisms

A notation for ana(f) found in the literature is [(f)]. The brackets used are known as lens brackets.

Hylomorphism

Composition of an anamorphism and a catamorphism. Invocation tree is isomorphic to a function which processes lists.

Example Monoid

free monoid = list

 

monoid expression

 

Fold Left fold left
Fold Right fold right

 

 

So the fold operation takes a list and a monoid and returns a value

fold

Googles MapReduce software framework.

Example Field

free field = tree?

free field

Monoid and Monad

  Monoid Monad
Definition A set: S
An operation: •: S×S->S
An element of S: e:1->S
an endofunctor: T
natural transformations:
multiplication µ: T×T-> T
unit η: 1->T
Satisfies Laws (a•b)•c=a•(b•c)
e•a=a=a•e
for all a,b,c
µ(µ(T×T)×T)=µ(T×µ(T×T))
µ(η(T)) = T = T(η)

Algebraic Category

Every Algebraic Category has co-limits

The category Alg T is a free completion of Top under sifted colimits

 


metadata block
see also:
Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

flag flag flag flag flag flag Axiom Volume 1: Tutorial. Documentation is freely availible from: http://www.axiom-developer.org/axiom-website/documentation.html

 

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2017 Martin John Baker - All rights reserved - privacy policy.