Re: an idea about possreps

On 4 feb, 03:46, David BL <davi..._at_iinet.net.au> wrote:
> On Feb 3, 11:59 pm, Jan Hidders <hidd..._at_gmail.com> wrote:
>
>
>
> > On 3 feb, 05:31, Marshall <marshall.spi..._at_gmail.com> wrote:
>
> > > I just had this idea about possreps.
>
> > > In another context, someone discussing methods, or functions
> > > that are bound very closely to a specific type, commented
> > > that he thought that such functions should be extremely
> > > limited, rather than the grab-bag that OOP usually produces.
> > > I thought this a rather interesting comment, and after thinking
> > > about it for a long time decided it was a good comment,
> > > but that I didn't really know how to measure how well a
> > > design achieved that goal.
>
> > That's actually not that hard. You can formalize this by introducing a
> > notion of completeness that says that a set of operations for a
> > certain type / domain is complete if it holds that when we add the
> > domain / type and its operations to a computationally complete
> > programming or query language it stays computationally complete (*).
>
> > A set of operations is then called essential for a domain if any
> > proper subset of them is not complete in the above sense. Note that
> > this set is not necessarily unique.
>
> > (*) Computationally complete is a stronger notion than Turing
> > complete. In many cases the two coincide, but here their difference
> > matters. Roughly it means that for all types available in the language
> > you can express all computable functions over these types.
>
> I think in practice one would typically only define the set of all
> computable functions over a given type indirectly by defining a set of
> essential operators.  IOW, essential operators seem to have an
> axiomatic character to me.

Not necessarily. For a concrete data type which is defined based on some internal type / representation you can define it based on this internal type and independent of any operators. For an abstract data type you can take the initial model for that purpose. In both cases it is possible that you find that your set of operators is redundant.

• Jan Hidders