Expression and Kernel

[Grigory Sarnitsky]

Hello! Citing Axioms's doc:

Conceptually, an object of type Expression can be thought of a quotient of multivariate polynomials, where the "variables" are kernels. The arguments of the kernels are again expressions and so the structure recurses. See Expression for examples of using kernels to take apart expression objects.

You can find this in HyperDoc in the description of "Kernel" or in the bookvol0 (9.44 Kernel).

As far as I understand this definition, Expression is defined through Kernel, and Kernel through Expression. How is this loop resolved?

[Serge D. Mechveliani]

Probably, similar as the definition of a binary tree.
"A binary tree is either a Leaf
or a Node who's left is a binary tree and right is a binary tree."
So, a binary tree is defined trough itself (+ through a leaf).
For example, each point in this graph defines a tree:

Node
/ \
Node (Leaf 3)
/ \
(Leaf 1) (Leaf 2)

------
Sergei

[Ralf Hemmecke]

awk '/^)abbrev domain EXPR Expression/,/^@/ {print}' expr.spad.pamphlet
|grep '^[ \t]*Rep'
Rep := Fraction MP
Rep := MP
Rep := FreeAbelianGroup K
Rep := K

Expression(R) does not just have ONE representation, but the
representation depends on the parameter R.

As you can see from the nesting of this line
https://github.com/hemmecke/fricas-svn/blob/master/src/algebra/expr.spad.pamphlet#L112
,,, in case R is Integer, FriCAS will use Fraction(MP) where
MP ==> SparseMultivariatePolynomial(R, K)
K ==> Kernel %

Looks like the documentation is not lying. It's "Kernel over Expression"
(% here stands for Expression(R)).

Then look into
https://github.com/hemmecke/fricas-svn/blob/master/src/algebra/kl.spad.pamphlet#L226
to find out what Kernel(S) can do with the parameter S.
It's only
argument: % -> List S
kernel : (OP, List S, N) -> %
that are important.

So unless you construct an infinite kernel that refers from one of its
arguments back to itself (which is impossible without tricks, since the
arguments must be existing before you can give them to the "kernel"
function), there must be a base case (basically a symbol or nullary
operator) that does not involve any expression.

So yes, the Expression/Kernel data structures are recursive. But there
is no problem with the actual representation.

For a developer one can consider an Expression as a multivariate
polynomial where the variables might have a quite complicated structure.
But if you go down this complicated structure, you remove one complexity
level after the other.

Ralf

[Grigory Sarnitsky]

Thank you guys. For some weired reason I thought one cannot define two distinct types, one being defined type in terms of the other, the other being defined through the first one. I should have tried before asking. At least in Haskell I can do it:

{-# LANGUAGE  TypeSynonymInstances, FlexibleInstances #-}

import Math.Core.Field
import Math.CommutativeAlgebra.Polynomial
import Math.Algebras.Structures

type Expression = GlexPoly Q Kernel

data Kernel = Symbol String
            | Exp Expression
            deriving (Eq, Ord)

instance Show Kernel where
  show (Symbol str) = str
  show (Exp x) = "exp(" ++ show x ++ ")"

instance Floating Expression where
  exp = glexvar.Exp

compiled! I was really surprised, but it works:

*Main> let [x, y] = map glexvar [Symbol "x", Symbol "y"]
*Main> 13*x*y + exp(y^3 + x^2 - exp(x) + 4*exp(x))
13xy+exp(y^3+x^2+3exp(x))

[Serge D. Mechveliani]

Such types also can be defined in {\tt Spad}, but the code will be
considerably more complex (I complained on this).
As an example, see in the Axiom source the definition for the domain of
BinaryTree (or, maybe, Tree).
I wonder whether it is simpler in Aldor.

------
Sergei

[Bill Page]

On Wed, May 2, 2012 at 3:24 PM, Serge D. Mechveliani <mec...@botik.ru> wrote:
>
> Such types also can be defined in {\tt Spad}, but the code will
> be considerably more complex (I complained on this).
> As an example, see in the Axiom source the definition for the
> domain of BinaryTree (or, maybe, Tree).
> I wonder whether it is simpler in Aldor.
>

In the context of this group I find your comment rather annoying and I
wonder how you define "complex" in such a way that it allows an
objective comparison.

Regards,
Bill Page.

[Serge D. Mechveliani]

I discussed in this e-mail list of how to define in Spad
ConstructedDomain -- a domain supplied with a certain explicit
construction.
I managed to build such only with a strong assistance of the FriCAS
people. And the definition has occurred very complex.

If you need a concrete example, let us try first something simple.
For example, a _binary search tree_.
Of course, it is for defining as a _user type_, not of the library.
In Haskell, the user can define it, for example, as

------------------------------------------------------------------------
data STree key value =
Empty | Node key value (STree key value) (STree key value)
deriving (Show)

-- key, value are type parameters (parameters of a domain in Spad).
-- It is either Empty or a node containing key, value, left subtree,
-- right subtree.
-- `deriving (Show)' means the default definition for printing of this
-- data to String.

search :: Ord key => key -> STree key value -> Maybe value

-- `::' is `:' of Spad, `=' is `==', `:=' of Spad.
-- `Ord key =>' corresponds to the condition of
-- key : OrderedSet in the domain declaration in Spad.
-- The used `compare' operation is of the class Show.
-- `search' is a polymorphic function. And in Spad, it needs, probably,
-- to be exported by the domain STree.

search k tab = case tab
of
Empty -> Nothing
Node k' v leftBranch rightBranch ->
case compare k k'
of
EQ -> Just v
LT -> search k leftBranch
_ -> search k rightBranch

main = putStr (concat [show tree, "\n\nv = ", show v, "\n"])

-- Example of usage. Buld some tree for key = Int, value = Char,
-- search the value for 2 in it,
-- print the tree and the found value.
where
tree = Node 1 'a' Empty
(Node 2 'b' (Node 3 'c' Empty Empty) Empty)
v = search 2 tree
------------------------------------------------------------------------

Compiling, running under GHC:

> ghc --make -O Main
> ./Main

Node 1 'a' Empty (Node 2 'b' (Node 3 'c' Empty Empty) Empty)

v = Just 'b'


What is the Spad program for this?
This is not a flame war. Because
1) I respect Axiom, and even try to use it in the interface project,
2) you asked for an example,
3) if the Spad code occurs considerably more complex, this would not
mean too much, for example, a) Haskell has not dynamic types, one can
not program parsing a domain in Haskell as I did in Spad,
b) Spad has considerably more of overloading,
4) if the Spad code is sufficiently simple, then I could return to my
ConstructedDomain in Spad and see how can it be improved.

Regards,

------
Sergei
mec...@botik.ru

[Ralf Hemmecke]

Of course, this STree type is wrong in the sense that it allows the
creation of trees that are not appropriate for binary search. (Node 3
below lives in the wrong branch.) Nevertheless, it's an easy exercise.

Ralf

(1) -> T := STree(Integer, String)

(1) STree(Integer,String)

Type: Type
(2) -> t: T := node(1,"a", empty(), node(2, "b", node(3, "c", empty(),
empty()), empty()))

(2) (k=1, v="a", l=(), r=(k=2, v="b", l=(k=3, v="c", l=(), r=()),
r=()))
Type: STree(Integer,String)
(3) -> search(1, t)

(3) "a"
Type: Union(String,...)
(4) -> search(2, t)

(4) "b"
Type: Union(String,...)
(5) -> search(3, t)

(5) "failed"
Type: Union("failed",...)

[Serge D. Mechveliani]

On Thu, May 03, 2012 at 12:32:50PM +0200, Ralf Hemmecke wrote:
> Of course, this STree type is wrong in the sense that it allows the
> creation of trees that are not appropriate for binary search. (Node 3
> below lives in the wrong branch.) Nevertheless, it's an easy exercise.
>
> Ralf
>
> (1) -> T := STree(Integer, String)
>
> (1) STree(Integer,String)
>
> Type: Type
> (2) -> t: T := node(1,"a", empty(), node(2, "b", node(3, "c", empty(),
> empty()), empty()))
>
> (2) (k=1, v="a", l=(), r=(k=2, v="b", l=(k=3, v="c", l=(), r=()),
> r=()))
> Type: STree(Integer,String)
> (3) -> search(1, t)
>
> (3) "a"

> []


So, the Haskell code is

------------------------------------------------------------------------
data STree key value =
Empty | Node key value (STree key value) (STree key value)
deriving (Show)

search :: Ord key => key -> STree key value -> Maybe value

search k tab = case tab of
Empty -> Nothing
Node k' v leftBranch rightBranch ->
case compare k k'
of
EQ -> Just v
LT -> search k leftBranch
_ -> search k rightBranch

------------------------------------------------------------------------

and the Spad code is

------------------------------------------------------------------------
)abbrev domain STREE STree
OF ==> OutputForm

STree(Key: OrderedSet, Value: CoercibleTo OF): CoercibleTo OF with

search: (Key, %) -> Union("failed", Value)
empty: () -> %
node: (Key, Value, %, %) -> %
== add
Node == Record(key: Key, value: Value, left: %, right: %)
Rep == Union("empty", Node)
rep(x:%):Rep == x pretend Rep
per(x:Rep):% == x pretend %

empty(): % == per "empty"
node(k: Key, v: Value, l: %, r: %): % == per [k, v, l, r]

search(k: Key, t: %): Union("failed", Value) ==

rep(t) case "empty" => "failed"
n: Node := (rep t)::Node
n.key = k => n.value
n.key > k => search(k, n.left)
search(k, n.right)
-----------------------------------------------------------------------

I remove the implementation for `coerce' because a similar implementation
for `show' must be added to the Haskell program -- if we skip
`deriving (Show)'.

Thank you for a useful sample of programming.
I am sorry: it is not "considerably more complex",
it is _a bit more complex_.

As to my subjective opinion, it is considerably more complex, because it
is difficult for me to guess of adding
`node: ...', `Node == Record ...', `rep' and `per'.

But with CostructedDomain, it was more difficult
(I could show the code).
The necessity of type recursion is joint there with a particular
_tagged union_ to express the domain construction.

Regards,

------
Sergei
mec...@botik.ru

[Ralf Hemmecke]

> As to my subjective opinion, it is considerably more complex, because it
> is difficult for me to guess of adding
> `node: ...', `Node == Record ...', `rep' and `per'.

I like the rep/per very much, because it clearly distinguishes between %
and Rep.

That you *need*

empty: () -> %
node: (Key, Value, %, %) -> %

is clear. In Haskell you would get the constructors for free, in SPAD
you don't, i.e. no guessing.

You could also do without the extra Node type and simply put the RHS of

Node == Record(...)

directly into the definition of Rep.

This line

n: Node := (rep t)::Node

is also not necessary, but it makes the code more readable.

> But with CostructedDomain, it was more difficult

Maybe you rethink over that domain and re-program it in a similar way to
the sample code that I've shown.

> The necessity of type recursion is joint there with a particular
> _tagged union_ to express the domain construction.

In reality I would have made

Rep == Record(key: Key, value: Value, left: %, right: %)

and interpreted the NIL pointer as the empty tree, i.e.

empty(): % == (NIL$Lisp) pretend %

but I wanted to make the program as similar to Haskell as possible.

Ralf