Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!seismo!columbia!rutgers!ames!amdcad!amd!intelca!mipos3!omepd!intelisc!littlei!ogcvax!pase
From: pase@ogcvax.UUCP (Douglas M. Pase)
Newsgroups: comp.lang.misc
Subject: Re: Polymorphic Type Systems: some unsolved problems
Message-ID: <1365@ogcvax.UUCP>
Date: Thu, 30-Jul-87 06:51:32 EDT
Article-I.D.: ogcvax.1365
Posted: Thu Jul 30 06:51:32 1987
Date-Received: Sat, 8-Aug-87 02:00:14 EDT
References: <watcgl.1506>
Reply-To: pase@ogcvax.UUCP (Douglas M. Pase)
Organization: Oregon Graduate Center, Beaverton, OR
Lines: 99

In article <watcgl.1506> kdmoen@watcgl.UUCP (Doug Moen) writes:
> [...] it seems to me that there are many interesting and well defined
>polymorphic functions which cannot be easily expressed in currently
>existing polymorphic type systems.

I use a strongly typed variant of ML *we* call SML, which appears
to be otherwise unrelated to *Standard* ML.

>
>1) Write a single function 'twice' such that
>      twice(f, x) = f(f(x))
>   for any function f and value x for which this makes sense.

	let twice = \f. \x. f (f x) ;

	twice : (*a -> *a) -> *a -> *a

>
>2) Define a function similar to the 'printf' function in the C
>   library, except that it is fully type checked.

This is harder, since it depends on the I/O system defined by the language
(SML has none).  In general it is very difficult (if at all possible) to
define a function which is able to accept a list of args, whose length and
types are both arbitrary.  The big problem I see is when do you stop looking
for more args?  If the length is fixed, count the args you've got.  If the
type is fixed, use a marker of a different type to signal the end.

>
>3) Define a function 'apply' such that
>      apply(f, arglist)
>   calls the function 'f' with 'arglist' as an argument list,
>   for any function f, and any argument list that can legal be
>   passed to it.

I find it hard to fathom exactly what is wanted here.  My own guess results
in the trivial function

	let apply = \ f . f ;

	apply : *a 

This works, because apply is an implicit operator in the language.

>
>4) Define a function called 'curry' which maps functions onto functions.
>   Curry maps functions with 0 or 1 arguments onto themselves,
>   and maps functions with 2 or more arguments onto Curried versions
>   of these functions.  For example, it maps a function of type
>   "(T1, T2) -> R" onto a function of type "T1 -> T2 -> R". Similarly, it maps
>   "(T1, T2, T3) -> R" onto "T1 -> T2 -> T3 -> R", etc.
>

This one actually borders on the difficult.  SML does not support arbitrarily
long "pairs" the way it supports lists.  Lists must have all elements of the
same type, but are unbounded in length.  Pairs may contain many different types
of expressions, but are fixed in length.  Thus a "curry2" or a "curry3" may
easily be written, but a "curryN" is not within its bounds.  LML, which is also
a variant of ML supports a disjoint union (it momentarily escapes me if this
is the proper term) of types (e.g. int+real+...) and is therefore able to
create a "curryN" function.  However, because tuples only come in one size
also (i.e. pairs), there is some ambiguity if a type Tn is itself a pair.

>5) Define a function called 'uncurry' which is more or less the inverse
>   of curry.
>

Similar to #4, SML could define an "uncurry2", etc., but I do not see how
either SML or LML could support an "uncurryN".  Neither am I sure it is
impossible.

>6) Suppose that 'array N of T' is the type of a one dimensional array...

Neither SML nor LML support arrays so I cannot provide assistance.

>7) Define a single function that can accept an argument whose type
>   is either T1 or T2.

SML is not capable of this.  In LML (if I remember my syntax):

	let f x = case (x)
		int :  3 ;
		real : 4 ;
		;;

	f : (int+real) -> int

(The beauty of the disjoint union!)


I have received numerous requests for information/articles/references/authors
for LML (Lazy ML) and ML, but alas, I have none.  My information came from
classes offered here, so I can't offer much in the way of assistance.  (I 
suppose you could write and ask for the class notes for CSE 511, 512 and 515,
but I don't guarantee results.)  So if any of you advanced students of
functional programming or closet type-theorists do have such knowledge,
please share it with the rest of us.
--
Doug Pase   --   ...ucbvax!tektronix!ogcvax!pase  or  pase@Oregon-Grad.csnet