I wanted to gauge the interest of people on the list in adding purity
annotations to ocaml. Purity is one of those things that could really help
with reducing memory allocations through deforestation and decreasing the
running time of programs written in the functional paradigm, and it could
be very useful for parallelism as well. The basic scheme I have in mind is
this:

- Functions that do not access mutable structures would be marked pure.
- Functions that access only local mutable structures would be marked as st
(a la state monad)
- Functions that access global mutable data would be unmarked (as they are
now).
- Pure functions can call st functions/code so long as all of the state
referred to by the st code is contained within said pure functions.
- Functions that call higher order functions, but do not modify mutable
state would be marked hpure (half-pure). These functions would be pure so
long as the functions they call remain pure. This allows List.map,
List.fold etc to work for both pure and impure code.
- The same thing exists for st code: hst represents functions that take
higher order functions but only performs local state mutation.
- In order to take advantage of this mechanism, there's no need to annotate
functions. The type inference algorithm will figure out the strictest type
that can be applied to a function and will save the annotation to an
external, saved annotation file. This means that non-annotated code can
take advantage of purity without doing any extra work, and the programmer
never has to think about purity.
- Having the purity annotations as an option is useful to force certain
parts of the code, such as monads, to be pure.
- An edge case: local state can be made to refer to global state by some
external function call. Therefore, local state is considered 'polluted'
(and global) if it is passed to an impure function.
- Exceptions: not sure how to handle them yet. The easiest solution is to
forbid them in st/pure code. Another easy alternative is to only allow
catching them in impure code, as haskell does.

Thoughts?

-Yotam