Edit detail for SandBox Monoid revision 2 of 4

Axiom output parse error!

Axiom output parse error!

Let's try this ... Axiom output parse error!

Interesting! Is it somewhere written that "has" can have a category as its first argument?

OK, we are going to implement... Axiom output parse error!

Oops, that's not so easy. Have I made some error? (You originally wrote begin{axiom} but this is spad code.

Unfortunately, this won't work. For example in the above definition of Monoid, we are effectively creating to different things with the same name, but different types. We have an m of type Symbol, and another one of type (%,%)->%. As soon as we add a default implementation, this mistake surfaces:

Axiom output parse error!

Axiom output parse error!

Axiom output parse error!

What we really would like to have would be something along the lines of: Axiom output parse error!

Axiom output parse error!

Axiom output parse error!

Then:

  Word: MyMonoid1(String,(a:String,b:String):String+->concat(a,b)) with
      coerce: String -> %
    == add

      Rep := String
      coerce(a: String): % == a
      c(a:%, b:%):% == concat(a::Rep, b::Rep)

However, there are two problems here:

• it is not possible to refer to the category to be defined in the parameter, as in MyMonoid(m: (%,%)-> %)
• it is not possible to refer to an operation which is not yet defined as in Word: MyMonoid(c) with

Martin

Martin wrote:

Unfortunately, this won't work. For example in the above definition of Monoid, we are effectively creating to different things with the same name, but different types. We have an m of type Symbol, and another one of type (%,%)->%.

I agree that there is a scope issue here. Perhaps it comes from the idea of allowing default implementation as part of the category definition. But I think the proper semantics are quite easy to define. The exports need to have priority over the parameters. The m of type Symbol is not exported by MyMonoid but the m of type (%,%)-> % is exported. The m in the implementation m(a,a) should refer to m that is being exported.

So I think this is a compiler error.

Based on an idea posted to this page by Martin Rubey, I have constructed what I think is a good facsimile of a generic monoid. I think think that this construction is only possible in Aldor.

The idea is basically to specify a monoid as a tuple in the usual manner, consisting of a set S, an associative binary operator m and unit u. In this example MyMonoid? exports two operations and a constant: * for the binary operation in the monoid (whatever it happens to be), ^ for repeated * repeated n times, and 1 denoting the ring identity.

This is rather different that the notion that we started with in this thread - in fact more or less the opposite: from any more complex domain we can extract the monoid part. Of course this is fundamentally very simple, just as it should be. :)

Axiom output parse error!

This is how the MyMonoid domain looks to the Axiom interpreter. Axiom output parse error!

Here is Martin Rubey's String monoid example: Axiom output parse error!

And of course we can construct a large number of other examples. Axiom output parse error!

Axiom output parse error!

Axiom output parse error!

Now try to define a group.

Axiom output parse error!

This is how the MyGroup domain looks to the Axiom interpreter. Axiom output parse error!

For example: Axiom output parse error!

I am not impressed. However, this kind of finessed the whole issue of notation and neglected the dual inheritance situation, and I expect one will get into trouble when one wants to go on to MyRing. Any domain in MyRing should work without unnecessary package calls in the Interpreter. All this mechanism did was passing a function m to constructors, here to be used as the monoid categorically defined multiplication. This technique has been used before, in Axiom, in GDMP. The notation in an Interpreter session is still *, the operator declared in MyMonoid. So even though we have MyMonoid(INT,+,0) and we can compute using i1*i2 to really get the sum of i1 and i2, this is not using + notation. Notice also that MyGroup should have been implemented as a category constructor. In )sh MyGroup, the group operation is *, the unit is 1 and the inverse is - (which is incompatible with * and wrong, since a group should not be commutative in general). But these last two comments are minor quibbles and easily corrected.

I indicated before that I believe one needs to make some deeper changes to implement inheritance that would support notational changes in a way such that multiple inheritance of MyMonoid to the same domain constructor can distinguish the operators. Any proposed solution under the currently available systems, if possible at all, should include MyRing (as a category, not domain) and MyInteger as a domain in MyRing.

I am more interested in the associative category and the ForAll in Aldor. How exactly does that differ from Axiom? ForAll seems to be only a case by case verification, given actual elements of the domain.

William

William, it seems to me that you are easily not impressed ;) But thanks for your comments.

I agree that the second half of this page implements a different structure than the first half - I said as much above. It is in a formal sense the exact opposite thing. But opposites can be useful. I am working out the details here because I am hoping that in the end we can see the issue of inheritance more precisely as the dual to this construction.

The point here is that MyGroup(INT,+,-,0) declares that this combination of domain, operations and constant constitutes a group. It does not attempt to construct this group in INT but rather it extracts this part of INT as a subdomain having the structure of a group:

    MyGroup(INT,+,-,0) >-----> INT
    with *, ~, 1               with +, -, 0, *, /, 1,  ...

In categorical terms both MyMonoid and MyGroup are monomorhic functors, i.e. subdomain constructors.

(Note that I changed the notation for inverse in MyGroup to ~ so that perhaps it is less confusing.)

MyGroup is not implemented as a category constructor because as I said, the intent here is not to construct MyInteger by inheritance. In this case the implementation of Integer is given and we are simply identifying parts of it.

Inheritance does require something similiar:

    MyInteger: Join(Group(%,+,-,0), Monoid(%, *, 1), ...
                    with *, ~, 1    with *, 1

In this case the categories Group, Monoid, etc. are given and we wish to provide new names for their operations in MyInteger as suggested by Ralf. Unfortunately as Martin demonstrated on the first part of this page, the SPAD compiler does not compile it correctly. Maybe we can still find a way to do this with Aldor. I haven't given up yet, I am just working on a different aspect of the problem.

The associative category as I implemented it above in Aldor can also be written this way in SPAD. But as far as I know Aldor does not implement Axiom's axioms (assertions) so in Aldor these must be coded as categories with a possibly empty with { } clause.

ForAll is not an Aldor primitive construct, it is just a simple export that is intended to express the axioms in a manner that could be used in some kind of theorem proving subsystem (which does not exist yet :). You are right however that this could very easily be used to implement an automatic verification system. Such as system could least provide useful counter examples when the axioms fail.

I am still thinking about how best to encode these sort of axioms, so the ForAll construct above is likely to change a little.

Stay tuned to this channel ...

---

Define an Abelian (commutative) group: Axiom output parse error!

MyAbelianMonoid? is a MyMonoid?. MyAbelianGroup? is a MyGroup? and a MyMonoid?. Axiom output parse error!

Define a ring: Axiom output parse error!

It looks like this. Axiom output parse error!

Integer is a MyRing?. Axiom output parse error!

---

Martin Rubey discovered a way to use the Aldor extend construct to add Monoid(Integer,*,1) as a category to an existing domain, thus in principle also allowing this to be distinguished from Monoid(Integer,+,0) in a if ... has ... statement. But there may be problems. See: [SandBox Monoid Extend]?.

SandBoxAbelianDuck?