[clean-list] Bugs in StdOverloadedList

[John van Groningen]

Shivkumar Chandrasekaran wrote:
>I tried to use Zip and Unzip from StdOverloadedList hoping to get the following uniqueness propagation functionalities:
>
>Zip :: !(!.(l a),.(l .b)) -> .(l .(a,.b)) | List l a & List l b & List l (a,b)
>Unzip:: !.(l .(a,.b)) -> .(.(l a),.(l .b)) | List l a & List l b & List l (a,b)

The specified types of these functions in StdOverloadedList can be made
more general. I have changed the types to:

Unzip:: !u:(l v:(.a,.b)) -> .(u:(l .a),u:(l .b))
                                 | List l a & List l b & List l (a,b), [u<=v]
Zip :: !.(!u:(l .a),u:(l .b)) -> u:(l v:(.a,.b))
                                 | List l a & List l b & List l (a,b), [u<=v]
Zip2 :: !u:(l .a) u:(l .b) -> u:(l v:(.a,.b))
                                 | List l a & List l b & List l (a,b), [u<=v]

Unfortunately the uniqueness type system of Clean requires that all
occurences of a type variable have the same uniqueness variable. Therefore
"u:" has to be used before all occurences of "(l" , making the types
less general.

Using the same type of list (l) is not required, but is done on purpose,
because otherwise too many specialized versions would have to be generated,
and to reduce the number of cases in which overloading can not be resolved.

In case such a general version is required, use one of the macros
UnzipM, ZipM or Zip2M.

>However using Zip and Unzip in this form was rejected by the compiler. Ominously I noticed the following lines in StdOverloadedList.icl:
>
>//Unzip:: !.(l (.a,.b)) -> (.(l .a),.(l .b)) | List l a & List l b & List l (a,b)	// compiler bug ?
>//Unzip :: !.(a (.b,.c)) -> (.(d .b),.(e .c)) | List a (b,c) & List e c & List d b	// compiler bug ?
>
>I am not sure if the implementation in StdOverloadedList.icl is a type inference bug or not.

No, the "compiler bug ?" was probably added because of the restriction in
the uniqueness type system mentioned above.

>But I know that the following definitions are being accepted by Clean 2.2 (Mac OS X).
>
>myUnzip :: !.[!.(l,.e)!] -> .([!l!], .[!.e!])
>myUnzip [! !] = ([! !], [! !])
>myUnzip [! (x,y) : xys !]
>	#! (x1s, y1s) = myUnzip xys
>	= ([! x : x1s !], [! y : y1s! ])

To improve perfermance you could try:

myUnzip :: !.[!.(l,.e)!] -> .( ! [!l!], ! .[!.e!])


>myZip :: !.(![!l!], !.[!.e!]) -> .[!.(l,.e)!]
>myZip ([!l:ls!], [!e:es!])
>	#! les = myZip (ls, es)
>	= [!(l,e): les!]
>myZip (_, _) = [!!]
>
>Maybe one of the Clean gurus can comment on this, and if possible, implement a more generic Zip and Unzip? Thanks,

You can use ZipM and UnzipM if you want a more generic Zip or Unzip.

Unfortunately because of a restriction and a bug, the functions
Zip, Unzip and Zip2 should not be used in Clean 2.2 (use the _M versions
instead). The compiler does not use the specialized versions for these
functions, because it does not use specialized version with the
context "List l (a,b)" (or similar) where the types of a or b are not specified.
I have improved to compiler to use the versions.

Because of a bug that was introduced by the implementation of an optimization
(of curried applications with more than one argument) in Clean 2.2, applying
a function on overloaded lists using a lazy or strict boxed list causes the
program to crash, if the compiler could not optimize the use of overloading
by generating or use a specialized version of the function.
Usually this does not happen, because the compiler will generate a specialized
version of the function, or use the specialized version that is exported.

However, because the specialized versions of Unzip, Zip and Zip2 are not
used by the compiler (because of the List (a,b) restriction), using the
functions usually causes the program to crash in Clean 2.2.

You can fix this by updating _system.abc file (for 32 bit systems)

http://clean.cs.ru.nl/download/Clean22/source/_system.abc

or: (for 64 bit systems)

http://clean.cs.ru.nl/download/Clean22/source/64/_system.abc

in Libraries/StdEnv/Clean System Files or lib/stdenv/Clean System Files (linux).

On linux the file
lib/stdenv/Clean System Files/_system.o
should be removed after updating _system.abc. A new one can be generated with
clm -O _system
The CleanIDE seems to automatically regenerate _system.o when _system.abc
is modified.

It is unlikely that you need this patch, if you don't use Zip,Zip2 or Unzip
and don't export overloaded functions using a List l a context without
specialized versions for [],[! ],[ !] and [!!].

Kind regards,

John van Groningen