16.2 Translating Grammars to Combinatorial Species
453⟨pkg: InterpretingTools 453⟩≡ (449)
InterpretingTools: with {
⟨exports: InterpretingTools 454⟩
} == add {
⟨implementation: InterpretingTools 455⟩
}
Defines:
InterpretingTools, used in chunks 461 and 730–32.
Exports of InterpretingTools
-
-
evaluate: (ExpressionTree, List LabelSpecies) -> LabelSpecies Evaluate an
ExpressionTree
-
-
interpret: List ExpressionTree -> List LabelSpecies Translates a grammar into a list
of combinatorial species.
Export of InterpretingTools
evaluate: (ExpressionTree, List LabelSpecies) -> LabelSpecies
Usage
s: String
== "Plus(SingletonSpecies, SingletonSpecies, Self(0))";
S: LabelSpecies
== evaluate(parse s, [coerce SingletonSpecies]);
Description
Evaluate an ExpressionTree
evaluate evaluates the given ExpressionTree, replacing Self(i) with the ith
element of the given list. Instead of Self(1) the shorthand Self is also
allowed.
Remarks
Note that the correspondence between leaves and species like SingletonSpecies
and operators and operations on species like Plus is hardcoded in the function. If
necessary, this could be done differently, namely passing evaluate additionally a
table that describes the correspondence.
455⟨implementation: InterpretingTools 455⟩≡ (453) 458b ⊳
local getName(op: ExpressionTreeOperator): Symbol == name$op;
evaluate(t: ExpressionTree, selfList: List LabelSpecies): LabelSpecies == {
import from ExpressionTreeLeaf, ExpressionTree;
import from List ExpressionTree, Symbol, String, Integer, MachineInteger;
if leaf? t then return {
str := string leaf t;
(str = "Self") => first selfList;
(str = "EmptySetSpecies") => coerce EmptySetSpecies;
(str = "SingletonSpecies") => coerce SingletonSpecies;
(str = "SetSpecies") => coerce SetSpecies;
(str = "Partition") => coerce Partition;
never;
}
op: String := name getName(operator t);
n: MachineInteger := #arguments t;
(op = "Self") => {
if n = 1 and leaf? first arguments t
then selfList.(str2int string leaf first arguments t);
else error "Self takes a single argument which is a positive Integer"
}
(op = "CharacteristicSpecies") => {
if n = 1 and leaf? first arguments t
then coerce CharacteristicSpecies(
str2int(string leaf first arguments t)::Integer);
else error "CharacteristicSpecies takes a single argument which is a positive Integer."
}
args: List LabelSpecies := [evaluate(arg, selfList)
for arg in arguments t];
(op = "NonEmpty") => {
if n = 1
then coerce NonEmpty(coerce args.1)
else error "NonEmpty takes a single argument which is a CombinatorialSpecies"
}
(op = "Plus") => {
if n = 2
then coerce Plus(coerce(args.1), coerce(args.2))
else error "Plus takes only two arguments"
}
(op = "Times") => {
if n = 2
then coerce Times(coerce(args.1), coerce(args.2))
else error "Times takes only two arguments"
}
(op = "Compose") => {
if n = 2
then coerce Compose(coerce(args.1), coerce(args.2))
else error "Compose takes only two arguments"
}
never;
}
Uses CharacteristicSpecies 85, CombinatorialSpecies 71, Compose 182a,
EmptySetSpecies 83, ExpressionTree 624a, ExpressionTreeLeaf 623,
ExpressionTreeOperator 620b, Integer 66, LabelSpecies 452, MachineInteger 67,
name 198, NonEmpty 131a, Partition 146, Plus 166a, SetSpecies 117,
SingletonSpecies 84, String 65, and Times 175a.
Export of InterpretingTools
interpret: List ExpressionTree -> List LabelSpecies
Usage
T23: List LabelSpecies == interpret
[parse "Plus(SingletonSpecies, Times(Self(2), Self(2)))",
parse "Plus(SingletonSpecies, Times(Self,Times(Self,Self)))"];
Description
Translates a grammar into a list of combinatorial species.
interpret translates a list of ExpressionTree’s into a list of combinatorial species.
The list of ExpressionTree’s [s_1, s_2, \dots, s_n] is interpreted as a system of
equations as follows:
| Self(1) | = s1 | |
|
| Self(2) | = s2 | |
|
 | |
|
| Self(n) | = sn. | | |
In the following we explain why interpret works in Aldor versions 1.0.2 and
1.0.3. Before doing so we have to stress however that very likely this depends on the
current implementation. The code is probably not conforming to the specification in
the Aldor user guide.
In principle the reason is that the compiler evaluates (coerce evaluate(p.i, res))(L)
lazily – although it wouldn’t have to. Consider, for example, what happens when we
call
-
-
C == interpret([parse "Plus(SingletonSpecies, Times(Self, Self))"]);
g := generatingSeries$C;
First res is initialized with a list of combinatorial species. For simplicity we use
EmptySetSpecies, but any other would do.
Then E(1) is called. However, note that (coerce evaluate(p.i, res))(L)
is an expression in type context, as explained in the Aldor user guide,
Section 7.3. Thus, Aldor is – a priori – free to choose when it evaluates
it. In fact, it seems that Aldor evaluates it only much later, namely at
the point when for the first time on operation from the formed domain is
called.
Thus, in the next step, res.1 is assigned the result of coerce E(1). Note that
(coerce evaluate(p.i, res))(L) is still not being evaluated. At this point
the operation interpret is left and Aldor commences the evaluation of
g := generatingSeries$C.
Of course, now it is truly necessary to evaluate (coerce evaluate(p.i, res))(L),
and this is exactly what happens. Meanwhile the list res contains as first member
the result of coerce E(1). Thus, res.1 is indeed defined recursively, as we were
hoping.
Previously we said that Aldor would be free to choose when to evaluate
(coerce evaluate(p.i, res))(L). However, there is another paragraph in the
Aldor user guide, Section 7.9, that might apply:
The bodies of with and add expressions are evaluated in such a
way that they will be evaluated after the expressions they depend on.
If mutually recursive type-forming expressions are found within the
body of either with or add expressions, the expressions are computed
as a xed point, rather than evaluated in strict sequence. This xed
point computation uses a technique from functional programming to
create self-referential data structures.
|
Note that another problem with the code in interpret is, that Aldor requires
name constancy in type context. However, we modify the contents of res. On the
other hand, consider the following sequence of expressions. Here C is some category
and f and g are functions taking two domains of type C and returning another one:
-
-
A: C; B: C;
A == f(A, B) add;
B == g(A, B) add;
One can argue that the situation in the code in interpret is very similar, indeed,
why should
-
-
l: List C == [someC, someC];
l.1 == f(l) add;
l.2 == g(l) add;
produce a different result?
ToDo ⊲ 74 ⊳ rhx ⊲ 54 ⊳ 22-May-2006: The domain constructor
E in the
above code chunk is there in order to get the type right. (Actually writing
-
-
for i in 1..#p repeat res.i := {evaluate(parse(p.i), res) add};
should suffice, but the compiler cannot correctly infer the type for the expression
inside the braces. And it is important that
E has a parameter, otherwise as a
constant domain it would only be evaluated once.
Type Constructor
Interpret
Usage
T := Interpret([parse "Plus(SingletonSpecies, Times(Self, Self))"], ACInteger);
s := structures([1,2,3,4,5])$T;
partialNext! s
Description
A domain function that returns a CombinatorialSpecies.
This domain is mainly useful within the Axiom environment. It returns the
CombinatorialSpecies corresponding to the expression Self within the given
grammar p.
Remarks
Note that the add within the body is necessary. Otherwise Axiom would, in the
above usage example, complain about a missing function partialNext!.
some blabla here?