14 A Domain for Expressions of Species

 14.1 The Representation of SpeciesExpressions

In this file we implement a domain whose elements represent species as expressions.

429* 13+   384  444
-------------------------------------------------------------------
----
---- Combinat
---- Copyright (C) Ralf Hemmecke <ralf@hemmecke.de>
---- Copyright (C) Martin Rubey <martin.rubey@univie.ac.at>
---- svn co svn://svn.risc.uni-linz.ac.at/hemmecke/combinat/
----
-------------------------------------------------------------------
#include "combinat"
dom: SpeciesExpression 430

Type Constructor

SpeciesExpression

Description

A domain for expressions describing combinatorial species.

Elements of SpeciesExpression are used to give a formal description of a combinatorial species. A special symbol, Self, is used to denote the species the expression describes. For example, an expression for binary trees is

Plus(EmptySetSpecies,Times(SingletonSpecies, Time(Self,Self))).

Most importantly, we will use the equality operation in SpeciesExpression to test whether two combinatorial species are equal.

ToDo 66
mrx 12 19-Oct-2006: I have no idea how to implement a good equality test. Currently, of course, the test only returns true for identical expressions. First of all we should implement it for holonomic expressions, I guess.
mrx 13 26-Dec-2006: Recently I learned that equality is decidable – in fact there is a normal form – if we restrict to Plus, Times and Compose, see Karl Aberer. Furthermore, equality is decidable for algebraic differential equations, see Joris van der Hoeven.
mrx 14 05-Nov-2006: Eventually this domain should export ArithmeticType, or something similar.
430dom: SpeciesExpression 430  (429)
SpeciesExpression: ExpressionType with {
        exports: SpeciesExpression 432
} == add {
        implementation: SpeciesExpression 441
}

Defines:
SpeciesExpression, used in chunks 81, 83, 84, 88, 94, 104b, 114, 125b, 129b, 133c, 144a, 164, 169a, 177, 184, and 192a.

Uses ExpressionType 620a.

Exports of SpeciesExpression

new: () -> % Create a new expression

new: Integer -> %

set!: (%, %) -> () Destructively modify a expression

+: (%, %) -> % Add two expressions

*: (%, %) -> % Multiply two expressions

^: (%, %) -> % Exponentiation for expressions

compose: (%, %) -> % Compose expressions

leaf: Symbol -> % Create a leaf

leaf: String -> %

leaf: Integer -> %

apply: (Symbol, List %) -> % Create an operator

coerce: ExpressionTree -> % Coercion from ExpressionTree

Export of SpeciesExpression

new: () -> %

Description

Create a new expression

new creates a new expression object, that defaults to the special symbol Self(1). When an integer argument is given, for example 2, the default is modified to Self(2).

Remarks

Note that new has to be a function. Otherwise all expressions initialized with new would be identical, even after modifying them using set!.

432exports: SpeciesExpression 432  (430)  433
new: () -> %;
new: Integer -> %;

Uses Integer 66.

Export of SpeciesExpression

set!: (%, %) -> ()

Description

Destructively modify a expression

set! is useful for the definition of expressions within recursively defined species. See the constructors Plus and Times,

Remarks

Note that the user has to be careful not to modify constants like X exported by SpeciesExpression with set!. Although Aldor will not complain, the results will likely be surprising. This problem also occurs in the series framework. A workaround would be to make such constants functions, as we did with new.

433exports: SpeciesExpression 432+   (430)  432  434
set!: (%, %) -> ();

Export of SpeciesExpression

+: (%, %) -> %

Description

Add two expressions

+ returns the sum of two expressions. It corresponds to the constructor Plus.

434exports: SpeciesExpression 432+   (430)  433  435
+: (%, %) -> %;

Export of SpeciesExpression

*: (%, %) -> %

Description

Multiply two expressions

* returns the product of two expressions. It corresponds to the constructor Times.

435exports: SpeciesExpression 432+   (430)  434  436
*: (%, %) -> %;

Export of SpeciesExpression

^: (%, %) -> %

Description

Exponentiation for expressions

^ provides exponentiation of two expressions.

ToDo 67 Currently, there is no constructor corresponding to ^, although it is used to represent the CharacteristicSpecies.
436exports: SpeciesExpression 432+   (430)  435  437
^: (%, %) -> %;

Export of SpeciesExpression

compose: (%, %) -> %

Description

Compose expressions

compose returns the composition of two expressions. It corresponds to the constructor Compose.

437exports: SpeciesExpression 432+   (430)  436  438
compose: (%, %) -> %;

Export of SpeciesExpression

leaf: Symbol -> %

Description

Create a leaf

Usage

import from String, Symbol, List SpeciesExpression;
expression: SpeciesExpression == leaf(- "SingletonSpecies");, 

leaf creates a leaf. A leaf can correspond to a species that does not take any arguments, in which case it should be a String, or it may be an argument to some species constructor.

438exports: SpeciesExpression 432+   (430)  437  439
leaf: Symbol -> %;
leaf: String -> %;
leaf: Integer -> %;

Uses Integer 66 and String 65.

Export of SpeciesExpression

apply: (Symbol, List %) -> %

Usage

import from String, Symbol, List SpeciesExpression;
expression: SpeciesExpression == apply(- "RestrictedSpecies", 
                                       [expression$F(L), leaf n]);

Description

Create an operator

apply creates an operator, corresponding to a species that takes some arguments.

439exports: SpeciesExpression 432+   (430)  438  440a
apply: (Symbol, List %) -> %;

Export of SpeciesExpression

coerce: ExpressionTree -> %

Description

Coercion from ExpressionTree

coerce provides coercion from ExpressionTree.

440aexports: SpeciesExpression 432+   (430)  439
coerce: ExpressionTree -> %;

Uses ExpressionTree 624a.
ToDo 68
mrx 15 It is not clear to me whether rational?, algebraic?, etc. should be exported by CombinatorialSpecies or SpeciesExpression.
440bNOTYET: exports: SpeciesExpression 440b
        rational?: % -> Boolean;
        algebraic?: % -> Boolean;
        holonomic?: % -> Boolean;