Some observations and questions on Joy equivalence

Nick Forde — 2002-11-30 18:57:29

Is the definition of equivalence in Joy documented anywhere? I haven't

been able to find any references to it in Manfred's papers. Whilst

using the 'in' and 'has' atoms I got some unexpected results which

prompted me to look at their implementation along with '=' and

'equals'. I have found some inconsistencies but need to know their

intended behaviour before I can resolve the problems.



The Joy interpreter implements '=' and 'equals' something like the

following:



(1) `atom: '='  function: eql_()  args: x1, x2

----------------------------------------------

  PROCEDURE eql_

    IF (type(x1) == boolean) OR (type(x1) == char) OR (type(x1) == integer))

      IF (floating point comparison possible)

        RETURN result of floating point comparison

      ELSE

        RETURN result of integer comparison

    IF (type(x1) == float) 

      IF (floating point comparison possible)

        RETURN result of floating point comparison

      ELSE

        RETURN false

    IF (type(x1) == set) 

      RETURN result of bitwise comparison

    IF (type(x1) == list)

      RETURN error

    ELSE

      IF (type(y1) == list)

        RETURN error

      ELSE

        RETURN result of string comparison

  ENDPROC



(2) atom: 'equal'  function: equal_()  args: x1, x2

--------------------------------------------------- 

  PROCEDURE equal_

    IF (type(x1) == boolean) OR (type(x1) == char) OR (type(x1) == integer))

      IF NOT (type(x2) == boolean) OR (type(x2) == char) OR (type(x2) == integer))

        RETURN false

      ELSE

        RETURN result of integer comparison

    IF (type(x1) == set)

      IF (type(x2) != set)

        RETURN false

      ELSE

        RETURN result of integer comparison

    IF (type(x1) == list)

      IF (type(x2) != list)

        RETURN false

      ELSE

        RETURN result of recursing using equal_list_aux procedure

    ELSE

        RETURN result of string comparison

  ENDPROC



Of these atoms I assume that the intention is '=' should be the

coarsest or least discriminating of the two. It doesn't enforce type

equivalence and will not do recursive comparison over lists. The

current implementation does, however, have some problems:



  [] 0 =                --> true

  0 [] =                --> error

  "f" "r" fopen stdin = --> true

  stdin stdout =        --> true



i.e. the list type checking isn't quite strict enough and there isn't

any support for file types.



The 'equal' atom takes a more thorough approach by insisting largely

on type equivalence (except with boolean, chars and integers). It will

also allow list comparisons. It too has some problems:



  "f" "r" fopen stdin equal --> true

  stdin stdout equal        --> true

  1.0 0.1 equal             --> true



i.e. there is no file or float type support.



The 'in' and 'has' atoms use the following implementation:



(3) atom: 'in/has'  function: in_()/has_()  args: a1, x2

--------------------------------------------------------

  PROCEDURE in_

     IF (type(a1) == set)

       RETURN result of bitwise and with x2

     IF (type(a1) == string)

       FOREACH character in a1

         IF (match found) 

           RETURN true

         ELSE

           RETURN false

     IF (type(a1) == list)

       FOREACH element in list

         IF (integer match found)

           RETURN true

         ELSE

           RETURN false

     ELSE

        RETURN error

  ENDPROC



As you can see from the above the equality test here is similar,

although not the same, as that implemented by '='. For example:



  ["a" "b" "c"] "a" has --> false



I suggest that the best solution to this problem is that 'in' and

'has' should be using the same code as '=' or 'equal'. So, what is the

desired behaviour of these atoms?



Also, does it make sense in Joy to add another equality atom similar

to 'eq?' in scheme which does pointer comparisons? I imagine that this

would be of very limited applicability due to the way data is accessed

in Joy through stack manipulation, but I'm not sure. Perhaps a

stricter test which insists on equal types in all cases would be

useful?



Regards,



Nick.

Manfred von Thun — 2002-12-02 06:24:13

On Sat, 30 Nov 2002, Nick Forde wrote:



 > Is the definition of equivalence in Joy documented anywhere? I haven't

> been able to find any references to it in Manfred's papers. Whilst

> using the 'in' and 'has' atoms I got some unexpected results which

> prompted me to look at their implementation along with '=' and

> 'equals'. I have found some inconsistencies but need to know their

> intended behaviour before I can resolve the problems.



 
It is years since I wrote those parts of the implementation,

and presumably my original intentions are not all that relevant

any more. Suffice it to say that for '=' and 'equals' I must

have had Scheme's 'eq', 'eql' and 'equal' in mind.

Also, much the same problems will be present with the comparators

such as  <  <=  >  >=  

What a mess. Sorry.



 > The Joy interpreter implements '=' and 'equals' something like the

> following:



 
[ ... pseudo code for '=' and 'equals' ]



 > Of these atoms I assume that the intention is '=' should be the

> coarsest or least discriminating of the two. It doesn't enforce type

> equivalence and will not do recursive comparison over lists.



 
Something like that, yes. But that may or may not be a good idea.

Unfortunately I do not have my Scheme SICP with me here, which

could provide some ideas. I am very happy to hear your suggestions

about this.



 >                                                               The

> current implementation does, however, have some problems:

> 

>   [] 0 =                --> true

>   0 [] =                --> error

>   "f" "r" fopen stdin = --> true

>   stdin stdout =        --> true

> 

> i.e. the list type checking isn't quite strict enough and there isn't

> any support for file types.



 
AAARRRGH ! You are right, of course.



 > The 'equal' atom takes a more thorough approach by insisting largely

> on type equivalence (except with boolean, chars and integers). It will

> also allow list comparisons. It too has some problems:

> 

>   "f" "r" fopen stdin equal --> true

>   stdin stdout equal        --> true

>   1.0 0.1 equal             --> true

> 

> i.e. there is no file or float type support.



 
More AAARGH !



 > The 'in' and 'has' atoms use the following implementation:



 
[ ... pseudocode for in/has ]



 > As you can see from the above the equality test here is similar,

> although not the same, as that implemented by '='. For example:

> 

>   ["a" "b" "c"] "a" has --> false

> 

> I suggest that the best solution to this problem is that 'in' and

> 'has' should be using the same code as '=' or 'equal'.



 
I quite agree. That would be the most consistent solution. But it

is not entirely clear to me which choice should be made.



There is one other possibility: introduce two combinators 'c-in'

and 'c-has' which take an additional quotation parameter that

computes a relation, such as any of the following:

  obviously:   [=]  [equals]  [<]  [>]  [<=]  [=>]

  but also :   [in]  [has]  [divides]  ... [any-relation!]

These two combinators might be quite useful. But of course things

like  '[=] c-has' or '[equals] c-has' would be less efficient than

'has'. So I think one would want to have 'in' and 'has' with

the relational parameter built in.

 

 >                                                       So, what is the

> desired behaviour of these atoms?



 
I would be guided by Scheme or Lisp, but both are at home.

But more than that I would be happy to go by your suggestions

and what others in the group might say.



 > Also, does it make sense in Joy to add another equality atom similar

> to 'eq?' in scheme which does pointer comparisons? I imagine that this

> would be of very limited applicability due to the way data is accessed

> in Joy through stack manipulation, but I'm not sure.



 
Yes, I do remember thinking about this explicitly. I decided against

it because I thought it does not belong into a pure language.



 >                                                      Perhaps a

> stricter test which insists on equal types in all cases would be

> useful?



 
Yes,  '[] 0 ='  should really give an error. Maybe I had in mind that

the  'null' predicate does not distinguish, so '=' should not either.



Thanks a lot for that. 



  - Manfred



 > Regards,

> 

> Nick.