modeling out of memory

is identity the only polymorphic function without typeclasses?

Re: modeling out of memory

On Sun, 2 Mar 2003 10:16:12 +0200
"Cagdas Ozgenc" <co19 <at> cornell.edu> wrote:

> Could you give an intutive description of data construction

In some form of typed lambda-calculus, you have the sum and product
types. An example is PCF; see for example:

http://citeseer.nj.nec.com/howard90operational.html

Vincenzo

Re: is identity the only polymorphic function without typeclasses?

G'day all.

On Sun, Mar 02, 2003 at 10:18:13AM +0200, Cagdas Ozgenc wrote:

> Is identity function the only meaningful function one can write
> without constraining the type variable using a typeclass? If not,
> could you please give a counter-example?

This might help:

 <at> incollection{ wadler89theorems,
    author = "Philip Wadler",
    title = "Theorems for Free!",
    booktitle = "Proceedings 4th Int.\ Conf.\ on Funct.\ Prog.\ Languages and Computer Arch., {FPCA}'89,
London, {UK}, 11--13 Sept 1989",
    publisher = "ACM Press",
    address = "New York",
    pages = "347--359",
    year = "1989"
}

Cheers,
Andrew Bromage

Re: modeling out of memory

On Sun, 2 Mar 2003 10:16:12 +0200
"Cagdas Ozgenc" <co19 <at> cornell.edu> wrote:

> Greetings,
> 
> 1) How does one model "out of memory" condition in Haskell, perhaps using a Maybe type?

Unfortuntely not since it would not be referentially transparent. It's
part of a more general issue of exceptions in pure code.

You can't have

calculateSomething :: X -> Maybe Y

Such that it returns Nothing if it ran out of memory.

You can do it in the IO monad, which is the standard technique:

doCalculateSomething :: X -> IO (Maybe Y)
doCalculateSomething x =
	catchJust asyncExceptions
		(evaluate $ Just $ calculateSomething x)
		handleOOM
	where
		handleOOM StackOverflow = return Nothing	--return nothing if out of memory
		handleOOM HeapOverflow = return Nothing
		handleOOM otherException = ioError otherException

Probably the thing to do is just catch the exceptions rather than have
your functions return Maybe types. That way you don't have to deal with
Maybes all over the place.

See the paper on asynchronous exceptions which mentions treating out of
memory conditions as an asynchronous exception:
http://research.microsoft.com/Users/simonpj/Papers/asynch-exns.htm

BTW HeapOverflow doesn't actually work yet according to the ghc
documentation.

Duncan

Re: is identity the only polymorphic function without typeclasses?

Cagdas Ozgenc <co19 <at> cornell.edu> wrote:

> Greetings,

> Is identity function the only meaningful function one can write
> without constraining the type variable using a typeclass?  If not,
> could you please give a counter-example?

Certainly you can write lots of ``meaningful function''s without type
classes: not, (&&), (||), as well as many more complicated functions at
more complicated types.

You can also write useful polymorphic functions without type classes, as
long as you specify at least one type.  For example, you can write
polymorphic functions over/yielding lists, such as repeat, cycle, map
and its many relatives, foldr and its many relatives, take and its
relatives, takeWhile and its relatives, etc.  Similar functions often
exist for other types.

I'm somewhat curious, though: why do you ask this question?  How do you
expand your question that makes the answer seem to be ``no''?

> Thanks

Jon Cast

Re: is identity the only polymorphic function without typeclasses?

> Cagdas Ozgenc <co19 <at> cornell.edu> wrote:
>
> > Greetings,
>
> > Is identity function the only meaningful function one can write
> > without constraining the type variable using a typeclass?  If not,
> > could you please give a counter-example?
>
> Certainly you can write lots of ``meaningful function''s without type
> classes: not, (&&), (||), as well as many more complicated functions at
> more complicated types.
>
> You can also write useful polymorphic functions without type classes, as
> long as you specify at least one type.  For example, you can write
> polymorphic functions over/yielding lists, such as repeat, cycle, map
> and its many relatives, foldr and its many relatives, take and its
> relatives, takeWhile and its relatives, etc.  Similar functions often
> exist for other types.
>
> I'm somewhat curious, though: why do you ask this question?  How do you
> expand your question that makes the answer seem to be ``no''?

I did not mean to include functions that take type constructors as
parameters (so lists are out of my discussion scope). I am only considering
functions that uses type variables that are not restricted by typeclasses.
In this setting could you give a few useful function signatures, and their
explanation? How does "not" work polymorphically for example?

Re: modeling out of memory

> > Greetings,
> >
> > 1) How does one model "out of memory" condition in Haskell, perhaps
using a Maybe type?
>
> Unfortuntely not since it would not be referentially transparent. It's
> part of a more general issue of exceptions in pure code.
>
> You can't have
>
> calculateSomething :: X -> Maybe Y
>
> Such that it returns Nothing if it ran out of memory.
>
<snip>
> Probably the thing to do is just catch the exceptions rather than have
> your functions return Maybe types. That way you don't have to deal with
> Maybes all over the place.

Does this make the use of Monads doubtful? I mean it doesn't seem easy to
have a completely pure language, and the time one starts introducing few
impurities one also starts thinking why not include many others?

Just a thought...

Re: is identity the only polymorphic function without typeclasses?

> I did not mean to include functions that take type constructors as
> parameters (so lists are out of my discussion scope). I am only considering
> functions that uses type variables that are not restricted by typeclasses.

There is const:

   const ::  a -> b -> a 
   const x _ = x

And of course a family of const like functions:

   const' :: a -> b -> c -> a
   const' x _ _ = x

and so on...

Of course const is related to id.

There is also undefined:

   undefined :: a
   undefined = undefined

You can extend this with arguments:

   f :: a -> b
   f x = undefined

or even:

   f x = f x

and so on ...

Is this what you are looking for?

> In this setting could you give a few useful function signatures, and their
> explanation? How does "not" work polymorphically for example?

not isn't polymorphic in Haskell 98.

Cheers,
Bernie.

Re: modeling out of memory

> Does this make the use of Monads doubtful? I mean it doesn't seem easy to
> have a completely pure language, and the time one starts introducing few
> impurities one also starts thinking why not include many others?

I suggest that you read this paper:

   A semantics for imprecise exceptions, Peyton-Jones et al.

You can find a copy on the documentation page for GHC:

   http://haskell.cs.yale.edu/ghc/

See also:

  Tackling the Awkward Squad: monadic input/output, concurrency, exceptions,
  and foreign-language calls in Haskell, Peyton-Jones.

You can find it here:

   http://citeseer.nj.nec.com/peytonjones00tackling.html

Cheers,
Bernie.