On Tuesday, 26 August 2014 02:55:25 UTC+2, Robert Bradshaw wrote:
>
> On Mon, Aug 25, 2014 at 5:19 PM, Bill Hart <goodwi...@googlemail.com
> <javascript:>> wrote:
> >
> >
> > On Tuesday, 26 August 2014 00:40:34 UTC+2, Robert Bradshaw wrote:
> >>
> >> On Mon, Aug 25, 2014 at 1:24 PM, Bill Hart <goodwi...@googlemail.com>
> >> wrote:
> >>
> >> >> > Correct. But classes are essentially objects in Python because
> >> >> > everything is
> >> >> > an object, pretty much. This really muddies the water. Better to
> >> >> > think
> >> >> > of
> >> >> > classes and objects as being separate concepts.
> >> >>
> >> >> I, for one, find it very convenient (especially compared to using
> >> >> reflection and other hacks that are needed to reason about type at
> >> >> runtime in C++ or Java). Not that some languages aren't even better.
> >> >>
> >> >> > Also better to think of ZZ as a class in Sage and elements of ZZ
> as
> >> >> > objects,
> >> >> > even though actually ZZ happens to be an object too because
> Python.
> >> >>
> >> >> No. ZZ is an object because you might want to do things with it,
> like
> >> >> ask for it's properties (is it infinite?)
> >> >
> >> > Sorry if I have that wrong. But when I type ZZ?? into Sage, it pulls
> up
> >> > the
> >> > definition of a class.
> >>
> >> If a is an instance of class A, typing a?? will give you the definition
> of
> >> A.
> >
> > Ah thanks for pointing that out. I now see that 1 is an object of class
> > Integer, whereas ZZ is an object of class Integer_ring.
> >
> > So where I spoke of ZZ in Sage, please substitute Integer.
>
> Well, some of the places you wrote ZZ at least, as you interchange the
> two concepts quite a bit. That explains at least why you sounded so
> confused.
>
I wasn't really confused. Sage makes the distinction between the
mathematical domain, the type and the values.
I distinguish only types and values.
Sage is not wrong, it's just a bit overcomplicated. And it would be naive
to think it can push the carpet down at all the edges.
> >> I think so; the Euclidean property doesn't place any constraint on the
> >> morphisms.
> >
> >
> > I should have asked whether Fields were. Some references say yes, some
> no.
> >
> > It's also really funny that if you look up Category of Euclidean Domains
> on
> > the intertubes you get two types of pages in general. The first is Wiki
> > articles that use the words category and subcategory in the common
> speech
> > sense, not in the mathematical sense. Then there is the Sage
> documentation,
> > which speaks of the Category of Euclidean Domains.
> >
> > As a concept, it just isn't that useful to category theorists
> (apparently; I
> > wouldn't know, I'm not a category theorist).
> >
> > My point is really that having a typeclass hierarchy that revolves
> around
> > category theory isn't necessarily useful.
> >
> > Euclidean rings (and more specifically Euclidean domains) are a
> difficult
> > concept to model in a type hierarchy, because it is not that easy to
> tell
> > when a ring is a Euclidean ring, and if so, what the Euclidean function
> is
> > on that ring.
> >
> > Also, the Euclidean function may only be used implicitly in any
> algorithms
> > used to compute a gcd. So the Euclidean function is not that useful. And
> > there may be more than one Euclidean structure on a ring, e.g. Z/nZ for
> n
> > composite.
> >
> > The upshot of this is that whether or not a ring has a Euclidean
> function
> > defined on it is probably not something you want to represent in an
> > "interface". Thus, it is not that useful a concept when defining a
> typeclass
> > or interface for types to belong to.
> >
> > You could make your interface depend on whether there is a gcd function.
> But
> > such a function could just return an ideal, for example in a Dedekind
> domain
> > (Sage even does this; inconsistently). So whether there is a gcd
> function is
> > neither here nor there.
> >
> > So I would argue right from the outset that EuclideanDomain is neither a
> > useful concept category theory-wise, nor computationally.
> >
> > Note that there is no EuclideanDomain typeclass currently in Nemo (I
> know I
> > did provide it in my big long list of typeclasses that could be added).
> >
> >>
> >> I am still curious how you would express that
> >> UnivariatePolynomialRing{QQ} <: EuclideanDomans but the same doesn't
> >> hold for UnivariatePolynomialRing{ZZ} in Julia.
> >
> >
> > You wouldn't do this. But suppose you would.
> >
> > You might have:
> >
> > abstract Ring
> > abstract EuclideanDomain <: Ring
> >
> > type Poly{T <: Ring} <: Ring
> > # blah blah
> > end
> >
> > type EuclideanPoly{T <: Field} <: EuclideanDomain
> > # more blah blah
> > end
> >
> > The type construction function PolynomialRing can then be written such
> >
> > PolynomialRing{T <: Ring}(::Type{T}, S::string) # this is the generic
> > function which gets called if T is a ring but not a field
> > # return a Poly
> > end
> >
> > PolynomialRing{T <: Field}(::Type{T}, S::string) # this function
> specialises
> > the previous one, when T happens to be a field
> > # return a EuclideanPoly
> > end
> >
> > There are various ways you could handle functions that take either an
> > EuclideanPoly or a Poly. For example
> >
> > myfun(a :: Union(EuclideanPoly, Poly))
> >
> > or
> >
> > typealias AnyPoly Union(EuclideanPoly, Poly)
> >
> > myfun(a :: AnyPoly)
> >
> > And there are various ways you could handle functions that take elements
> of
> > a EuclideanDomain or a general Ring. E.g.
> >
> > myfun{T <: EuclideanDomain}(a :: T)
> >
> > myfun{T <: Ring}(a :: T)
> >
> > But I don't think there is any compelling reason to go to all of this
> > trouble. A much better and cleaner way is the following.
> >
> > abstract Ring
> >
> > type Poly{T <: Ring} <: Ring
> > # blah blah
> > end
> >
> > abstract GCDDomain <: Ring
> > abstract Field <: GCDDomain # it's questionable whether you really want
> to
> > do this instead of Field <: Ring, but that's another story
> >
> > typealias EuclideanDomain{T <: Field} Union(GCDDomain, Poly{T})
>
> So is this Union type extensible, e.g. if I had a third type that was
> also a EuclideanDomain but neither a GCDDomain nor a Poly{T}, could I
> add it in later? Or mus they all be enumerated upfront?
>
It is immutable. So adding new types to the union at runtime is right out.
Just the same as adding new integers to the Int type is also somewhat
forbidden.
I defined a type called RobertType then tried:
julia> EuclideanDomain.body = Union(Poly,Field,ZZ,RobertType)
ERROR: type TypeConstructor is immutable
Boom. Capital letters. You really shouldn't have done that!
But there is a way, if you really want the ability to change it at runtime.
abstract Ring
type ZZ <: Ring
end
type Poly{T <: Ring} <: Ring
#blah
end
abstract Field <: Ring
type QQ <: Field
end
EuclideanDomain = eval(:(typealias $(gensym()){T <: Field} Union(Field,
Poly{T}, ZZ)))
type Robert <: Ring
end
Robert <: EuclideanDomain
Field <: EuclideanDomain
Ring <: EuclideanDomain
ZZ <: EuclideanDomain
QQ <: EuclideanDomain
Poly{ZZ} <: EuclideanDomain
Poly{QQ} <: EuclideanDomain
EuclideanDomain = eval(:(typealias $(gensym()){T <: Field} Union(Field,
Poly{T}, ZZ, Robert)))
Field <: EuclideanDomain
Ring <: EuclideanDomain
ZZ <: EuclideanDomain
QQ <: EuclideanDomain
Poly{ZZ} <: EuclideanDomain
Poly{QQ} <: EuclideanDomain
Robert <: EuclideanDomain
I know, I know, it's an EVIL hack. But I bet I can find evil hacks in Sage
too.
And if I were really going to do this in practice I'd write a macro to
handle the evil, so it'd be
@registertype EuclideanDomain Robert
I'm sure there are much better solutions to this problem. At present things
don't require this to be solved. In Nemo it just tells you no gcd function
is available for your type and gives you a line number in the source.
That's pretty much what you want it to do anyway.
Admittedly it would be nice if it told you this as soon as you called the
function, rather than the first time it encounted the gcd call in the code.
But if you want that kind of type safety you don't want a dynamic language.
> I do have to admit I was hoping for something a bit more elegant...
>
A way might exist. I don't know it at the moment.
Python has union types too (multiple inheritance with an empty body,
> though yes the mix of interface and implementation makes that messy).
>
> A more concrete example is Z/nZ for n composite or prime. What is the
> type hierarchy for 3 in Z/5Z? In Z/10Z?
In Nemo, 3 doesn't belong to Z/nZ. If R = Z/5Z then R(3) is an element of
Z/5Z.
The type of R(3) is basically Residue{ZZ, 5}.
> Do you have values for Z/nZ,
> or is Z/nZ just a parameterized type (the way ZZ is the time of 3 \in
> Z)?
>
I use a parameterised type for Z/nZ, namely Residue{R, d} where R <: Ring
and d :: R.
>
> > function myfun{T <: EuclideanDomain}(a :: T)
> > # blah
> > end
> >
> > This lot all compiles by the way. And you can check it really works:
> >
> > First define a type which belongs to Field:
> >
> > type Bill <: Field
> > end
> >
> > julia> myfun(Bill())
> >
> > julia> myfun(Poly{Bill}())
> >
> > No complaints.
> >
> > Now define a type which is not a field, but just a ring:
> >
> > type Fred <: Ring
> > end
> >
> > And then:
> >
> > julia> myfun(Poly{Fred}())
> > ERROR: `myfun` has no method matching myfun(::Poly{Fred})
> >
> > julia> myfun(Fred())
> > ERROR: `myfun` has no method matching myfun(::Fred)
> >
> > However, in all of the above, you see that I never actually used
> GCDDomain
> > at all. So it can really be removed if so desired. It's likely you
> defined a
> > gcd function for some clean set of rings in the first place, which can
> all
> > be delineated nicely without having some special typeclass for it.
> >
> > And then, in reality, EuclideanDomain is just a union of various types,
> just
> > as the particular rings you can define a gcd function for is an eclectic
> > mix, with no particular rhyme or reason to it.
> >
> >>
> >> >> (As
> >> >> you mention, trying to use the type hierarchy in Python to model
> >> >> categorical relationships in Sage has generally lead to pain which
> is
> >> >> why we're moving away from that...)
> >> >
> >> > Oh I can't think why.
> >>
> >> I buy that the type system is more powerful in Julia (yay), but I'm
> >> still skeptical that it is the best way to express the relationship
> >> between objects and categories, and at the same time elements and
> >> objects, and attach useful information to those categories and
> >> objects.
> >
> >
> > That was kind of the point of my earlier post. There is no such best
> way.
> > Categories don't match any concept in computer science (well, that is
> not
> > strictly true, but that's a long diversion into n-categories and
> homotopy
> > types). Usually we can't push the carpet down around all the corners of
> the
> > room, but we can get it sufficiently flat locally.
>
> Yet you seem to be trying to tie the two together. Or is your point
> that Nemo gives you a sufficiently strong type system that the locally
> flat place is as big as needed?
>
Sure, I only plan to handle groups, rings, fields in Nemo at this point.
It's a flint interpreter after all.
At the moment I only have Field <: Ring at the typeclass level.
At the level of types I have ResidueRing, PolynomialRing, PowerSeriesRing,
ZZ which all belong to Ring, and FractionField, QQ, FiniteField which all
belong to Field.
If something needs a gcd and there isn't one, it currently just tells you
there's no gcd.
But Nemo has a gcd in more rings than just EuclideanDomains, same as Sage.
For example, it allows you to take gcds in Z/nZ or of polys over ZZ or
polys over Z/nZ and so on.
So checking whether you have a polynomial over a field isn't so useful,
actually.
If I wanted to know if a given ring was a Euclidean domain or not, I could
write a generic:
is_euclidean_domain{T <: Field}(::Type{Poly{T}}) = true
is_euclidean_domain(ZZ) = true
is_euclidean_domain{T <: Field}(::Type{T}) = true
I could also add:
is_euclidean_domain{T <: Ring)(::Type{Poly{T}}) = false
is_euclidean_domain{T <: Ring}(::Type{R}) = false
but that's probably not really useful, since some rings that are not ZZ,
polynomials over fields or fields are still Euclidean domains. And there's
just no easy way to tell which.
Bill.
> - Robert
>
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
