A Domain for Expressions of Species

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.

430⟨dom: 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!.

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.

Export of SpeciesExpression

+: (%, %) -> %

Description

Add two expressions

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

Export of SpeciesExpression

*: (%, %) -> %

Description

Multiply two expressions

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

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 .

Export of SpeciesExpression

compose: (%, %) -> %

Description

Compose expressions

compose returns the composition of two expressions. It corresponds to the constructor 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.

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.

Export of SpeciesExpression

coerce: ExpressionTree -> %

Description

Coercion from ExpressionTree

coerce provides coercion from ExpressionTree.

14 A Domain for Expressions of Species