Limiting resources on a per-function basis?

[Alastair Reid]

> I would really like to be able to set resource limits on a per-function
> basis.  I am envisioning something like:
>
> limit :: l -> (a -> b) -> (a -> Maybe b)
> limit lim fn = ...
>
> which would convert a function so that it returns Nothing if a limit
> (on stack, heap, time, etc.) is exceeded during evaluation of that
> function.  Is there any hope of being able to do this within the
> existing GHC libraries?

This is tricky in a lazy language for two reasons:

1) Suppose the function returns '(42,37)', what do you want
   the limit to be applied to?

   a) Computing the whole result.
   b) Computing '(42,?)' (i.e., not evaluating the 2nd field)
   c) Computing '(?,37)' (i.e., not evaluating the 1st field)
   d) Computing '(?,?)' (i.e., not evaluating either field)

2) Suppose the value being evaluated depends on a shared
   result, should you include that cost in the result?

   For example, if you have:

     primes :: [Int]
     primes = ... 

     getPrime :: Int -> Int
     getPrime n = primes !! n

   should all calls to 'limit 10 getPrime 100' return the same
   result even though the first call is vastly more expensive
   than the subsequent calls.

There are also some semantic issues like retaining referential
 transparency but the details depend a bit on the answers to the
 above questions.

Some of the semantic issues can be addressed using non-deterministic 
exceptions.  (For the most part, this involves putting 'limit' in the IO 
monad.)

> If not, is it even possible to determine after-the-fact how much
> stack or heap space a function evaluation required?

GHC's profiling tools can give information of this sort.
I don't think there's a way to access this information at
runtime but it should be possible to implement and might
even be straightforward?

--
Alastair Reid     www.haskell-consulting.com