Custom comparison

Discussions related to Visual Prolog
Martin Meyer
VIP Member
Posts: 290
Joined: 14 Nov 2002 0:01

Unread post by Martin Meyer » 28 Jun 2016 8:42

Thanx for the info!

To ease the thing with the custom comparators you could invent a compare attribute, which, similar to the in_test and in_iterate attributes, defines the predicate that is used as the custom comparator for a domain/interface.

Regards
Martin

User avatar
Thomas Linder Puls
VIP Member
Posts: 1625
Joined: 28 Feb 2000 0:01

Unread post by Thomas Linder Puls » 28 Jun 2016 21:49

I have considered such an attribute: at first sight seems to be a good idea, but when considering it in details there seem to be problems as well.

I think it is a bit too much to go over the details here, but one problem is the relation to the fundamental equality that matching/unification is based on. Another problem is that most domains actually need several different comparators for different purposes.
Regards Thomas Linder Puls
PDC

Martin Meyer
VIP Member
Posts: 290
Joined: 14 Nov 2002 0:01

Unread post by Martin Meyer » 29 Jun 2016 1:45

Suppose a new build-in predicate ::customCompare is introduced, which has the signature of the comparator domain. The semantics of the predicate would be:

Iff the compare attribute is not set, ::customCompare defaults to ::compare. Otherwise, when the compare attribute points to some custom comparator predicate, say myCompare, ::customCompare evaluates to myCompare.

Matching/unification, i.e. the semantics of the "=" operator, would not be altered. The compare attribute would define a "primary" comparison for a domain, but there is still the freedom to use comparators other then ::customCompare as well.

When doing it like that, there would arise no problem. Or?

Regards
Martin

Martin Meyer
VIP Member
Posts: 290
Joined: 14 Nov 2002 0:01

Unread post by Martin Meyer » 29 Jun 2016 8:57

To make the syntax more intuitive the attribute could be named customCompare. So that it has the same name as the predicate.

Regards
Martin

User avatar
Thomas Linder Puls
VIP Member
Posts: 1625
Joined: 28 Feb 2000 0:01

Unread post by Thomas Linder Puls » 29 Jun 2016 9:09

(I have split this discussion from the original mail: Remove predicate, since the topic is now rather different.)

I see the built-in equality that goes hand in hand with matching/unification as the primary equality. Any other equality must be secondary.

<> is defined as the negation of =, the other relational operators <, <= , etc could/can be defined in many ways but they must respect = (if A = B then A cannot be smaller than B on the other hand it must be smaller or equal to B). So primary comparator can be primary must fulfill this requirement (for all A and B):

Code: Select all

A = B <=> compare(A, B) = equal
This is on top of these relations that must apply to any comparator

Code: Select all

compare(A, B) = equal  <=> compare(B, A) = equal compare(A, B) = greater <=> compare(B, A) = less
All those words are merely explaining that any custom comparison must in some sense become a secondary comparison.

But it could of course still be the case that the secondary custom comparison is used by default in some situations, for example as map-key comparator. But what about list sorting, removal of duplicates, etc should they all start using the custom comparator?

In simple cases I think this would be relatively easy to deal with, give that we still have access to both comparators.

The really problematic thing is when domains are used to define other domains:

Code: Select all

domains     neutralString = string [comparator(string::compareCaseNeutral)].   domains     ddd = ddd(neutralString NS).     myDomain = md(neutralString S, ddd D).
The custom comparator for myDomain will use the custom comparator for neutralString for the first argument. It will also use the custom comparator for ddd which in turn uses the custom comparator for neutralString.

The problem is that we now have access to two comparators on myDomain the custom comparator that uses custom compare in all levels, and then the built-in comparator that uses built-in comparison in all levels.

So it is all or nothing but I believe you will actually very often need some "in between" like: Built-in compare on outer level, but still custom compare on inner levels (which is in many cases defined in a completely different context).

You can of course still handle such situations by writing yet another comparator, but then it seems that the benefit was not that big after all.
Regards Thomas Linder Puls
PDC

Martin Meyer
VIP Member
Posts: 290
Joined: 14 Nov 2002 0:01

Unread post by Martin Meyer » 30 Jun 2016 0:08

OK, let's call a custom comparator a secondary comparator and the build-in ::compare the primary comparator.

I had but a different semantics in mind for the custom comparator attribute. In 'my' semantics the domain myDomain from your example would be handled as follows:

To evaluate the term ::customCompare(X, Y), where X and Y are of myDomain, the compiler looks at first, whether the declaration of myDomain has a custom comparator attribute. Because myDomain does not have the attribute, ::customCompare(X, Y) is evaluated to ::compare(X, Y). And ::compare(X, Y) in turn will just be evaluated in the familiar way (my semantics does not change ::compare). Therefore X and Y are compared on all (sub-) levels without using string::compareCaseNeutral.

An "in between" custom comparator for myDomain, which uses different kinds of comparison for different sub-components, could be declared by:

Code: Select all

domains     neutralString = string [comparator(string::compareCaseNeutral)].   domains     ddd = ddd(neutralString NS).     myDomain = md(neutralString S, ddd D)      [comparator(       {          (md(S_a, ddd(NS_a)), md(S_b, ddd(NS_b))) =            if Result1 = equal then              customCompare(NS_a, NS_b)            else              Result1            end if :-                Result1 = compare(S_a, S_b).       })      ].
Thus the "all or nothing"-problem does not arise with my semantics. However, to name the attribute's identifier customComparator instead of comparator, would seem more intuitive to me.

Regards
Martin

User avatar
Thomas Linder Puls
VIP Member
Posts: 1625
Joined: 28 Feb 2000 0:01

Unread post by Thomas Linder Puls » 30 Jun 2016 8:24

I do not think that semantics gives a significant reason to introduce it.

The reason that I find it interesting is exactly due to the cascading effect, this attributes alters the semantics of the domain. I.e. it changes the semantics of the domains everywhere it is used, also when it is used nested in other domains.

Example. In the syntax tree for the parser we have the following domain (interface yTree):

Code: Select all

domains     yName = name(cursor Cursor, symbol Name, string OriginalName).
The Name is a lowercase copy of the OriginalName. The Name should be used as key in maps. We have several choices when creating maps, we can extract the Name and use that as key both when insetting and looking up, or we can create a map with a custom comparator.

The custom comparator would help on this. However we also have many places where we would combine a name and for example an arity (number of arguments) as a key:

Code: Select all

facts     table : mapM{tuple{yName Name, unsigned Arity}, something Something} := ...
I don't really think that the tuple itself should be treated in a custom way. I just think that the yName inside it should be treated in the same custom way that I have already specified once.

So I think it is quite natural and much more convenient that such a custom behavior should cascade into all usages of the domain.
Regards Thomas Linder Puls
PDC

Martin Meyer
VIP Member
Posts: 290
Joined: 14 Nov 2002 0:01

Unread post by Martin Meyer » 1 Jul 2016 2:09

I understand: tuple{T1, T2} is a universal domain and we don't want to destroy its generality by attaching a custom comparator to it. We expect, that tuple{yName Name, unsigned Arity} inherits a custom comparator from domain yName. That means, we want the cascading effect of ::customCompare to reach all compared sub-levels.

But unfortunately unleashing the cascading effect leads into problems. The result of ::compare would then depend on, from where the call to ::compare was issued. When it comes from a ::customCompare, which is cascading down, then the ::compare could use custom comparison for sub-components. Otherwise, when the call to ::compare is not part of the excution of a call to ::customCompare, then ::compare won't use custom comparison for sub-components. Thus, memorizing/recalling results of the ::compare function becomes a problem, because ::compare now uses the information, from where it was called, as a hidden third input parameter. In the mathematical sense, ::compare/2-> is not a function anymore.

In conclusion, I agree, that my before proposed semantics is insufficient, but when we try to improve it by letting the cascading effect reach all sub-levels, we are running into troubles.

Thanx Thomas, for explaining the issue!
Martin

Post Reply