Preventing values from escaping a context

Preventing values from escaping a context

[Rich Neswold]

[-- Attachment #1: Type: text/plain, Size: 1947 bytes --]

Hello,

I'm writing my first serious Ocaml library and have a question, which I'll
state later on.

Most of the functions in my library take a parameter that describes the
current environment. I call this data type, "context". The context is passed
to a function which will then use other functions in the library to get its
job done. The signature of the function that starts all this is:

val usingContext : (context -> 'a) -> 'a


('usingContext' takes other parameters which are used to create the context
parameter. I dropped them in this example to simplify the problem.)

So 'usingContext' creates a context and passes it to the given function.
'usingContext' will free up the resources of the context whether the
function parameter returns normally, or throws an exception. After cleaning
up the resources, it returns the value returned by the function parameter
(or re-raises the exception.)

My question is this: Is there a way to make the compiler reject a function
parameter from returning the context parameter? For instance, the identity
function should be disallowed since the context is invalid outside the scope
of 'usingContext'. It's true that a returned context would be unusable,
since its resources are gone, but it would be nice to prevent contexts from
escaping the 'usingContext' function entirely.

I'm aware that the ST monad, in Haskell, uses some forall abilities to
prevent stuff from leaving the ST monad. Hopefully there's a way to achieve
this using Ocaml.

(I realize that making this context a monad is a legitimate solution.
However, until I see the Ocaml community including monads in the standard
library, I think I'll stick with idiomatic Ocaml. I'd also like to solve
this functionally, so I'm discounting the use of objects. Sorry for these
constraints!)

Thanks for any help you can provide!

-- 
Rich

Google Reader: https://www.google.com/reader/shared/rich.neswold
Jabber ID: rich@neswold.homeunix.net

[-- Attachment #2: Type: text/html, Size: 2538 bytes --]

Re: [Caml-list] Preventing values from escaping a context

[Jacques Garrigue]

From: Rich Neswold <rich.neswold@gmail.com>

> Most of the functions in my library take a parameter that describes the
> current environment. I call this data type, "context". The context is passed
> to a function which will then use other functions in the library to get its
> job done. The signature of the function that starts all this is:
> 
> val usingContext : (context -> 'a) -> 'a
[...]
> My question is this: Is there a way to make the compiler reject a function
> parameter from returning the context parameter? For instance, the identity
> function should be disallowed since the context is invalid outside the scope
> of 'usingContext'. It's true that a returned context would be unusable,
> since its resources are gone, but it would be nice to prevent contexts from
> escaping the 'usingContext' function entirely.

The short answer is no.
Types are not sufficient to prevent values from escaping.
In ocaml, you have both functions and references.
So you can always plug a function of type [unit -> unit] into a
reference, and the function is allowed to access the full context
available when it was created.

let r = ref (fun () -> ())

let f ctx =
  r := (fun () -> chgCtx ctx)

(* later on *)

List.hd !r ()


The language is just too expressive...
You should rather look into adding a dynamic flag to your context,
causing a runtime error if you use it later.

Jacques Garrigue

Re: [Caml-list] Preventing values from escaping a context

[Miles Sabin]

On Tue, Feb 9, 2010 at 3:38 AM, Jacques Garrigue
<garrigue@math.nagoya-u.ac.jp> wrote:
> From: Rich Neswold <rich.neswold@gmail.com>
>> My question is this: Is there a way to make the compiler reject a function
>> parameter from returning the context parameter? For instance, the identity
>> function should be disallowed since the context is invalid outside the scope
>> of 'usingContext'. It's true that a returned context would be unusable,
>> since its resources are gone, but it would be nice to prevent contexts from
>> escaping the 'usingContext' function entirely.
>
> The short answer is no.
> Types are not sufficient to prevent values from escaping.

I appreciate that mention of Scala is borderline off-topic on this
list, however that's a very broad negative statement, so broad
counterexamples seem appropriate ... ;-)

Philippe Haller of EPFL is working on a uniqueness types extension of
Scala which provides exactly this, packaged as a compiler plugin for
scalac (my hope is that it will be rolled into the main scala
distribution during the 2.8.x series, so this isn't solely academic
exercise).

An example here,

  http://tinyurl.com/ya6f7jv

and the corresponding compiler-time error,

  http://tinyurl.com/yzgnus5

Full details can be found in his technical report here,

  http://lamp.epfl.ch/~phaller/capabilities.html

Scala isn't the only language which supports linear/uniqueness types,
however it's the only which does and has some prospect of becoming
mainstream.

Cheers,


Miles

-- 
Miles Sabin
tel: +44 (0)7813 944 528
skype:  milessabin
http://www.chuusai.com/
http://twitter.com/milessabin

Re: [Caml-list] Preventing values from escaping a context

[Jacques Garrigue]

From: Miles Sabin <miles@milessabin.com>
>> The short answer is no.
>> Types are not sufficient to prevent values from escaping.
> 
> I appreciate that mention of Scala is borderline off-topic on this
> list, however that's a very broad negative statement, so broad
> counterexamples seem appropriate ... ;-)
> 
> Philippe Haller of EPFL is working on a uniqueness types extension of
> Scala which provides exactly this, packaged as a compiler plugin for
> scalac (my hope is that it will be rolled into the main scala
> distribution during the 2.8.x series, so this isn't solely academic
> exercise).

Indeed my statement was too general. Uniqueness type can do the
trick... because they are explicitly designed for that.

I answered this way because, in Haskell, since there are no hidden
references, types are enough to disallow escaping. Unfortunately this
does not work in ocaml. So ocaml also could profit from uniqueness
types.

Cheers,

Jacques Garrigue

Re: [Caml-list] Preventing values from escaping a context

[Rich Neswold]

[-- Attachment #1: Type: text/plain, Size: 387 bytes --]

On Tue, Feb 9, 2010 at 2:24 AM, Miles Sabin <miles@milessabin.com> wrote:

> Scala isn't the only language which supports linear/uniqueness types,
> however it's the only which does and has some prospect of becoming
> mainstream.
>

Interesting. Thanks for the information!

-- 
Rich

Google Reader: https://www.google.com/reader/shared/rich.neswold
Jabber ID: rich@neswold.homeunix.net

[-- Attachment #2: Type: text/html, Size: 797 bytes --]

Re: [Caml-list] Preventing values from escaping a context

[Tiphaine Turpin]

Jacques Garrigue a écrit :
> From: Rich Neswold <rich.neswold@gmail.com>
>
>   
>> Most of the functions in my library take a parameter that describes the
>> current environment. I call this data type, "context". The context is passed
>> to a function which will then use other functions in the library to get its
>> job done. The signature of the function that starts all this is:
>>
>> val usingContext : (context -> 'a) -> 'a
>>     
> [...]
>   
>> My question is this: Is there a way to make the compiler reject a function
>> parameter from returning the context parameter? For instance, the identity
>> function should be disallowed since the context is invalid outside the scope
>> of 'usingContext'. It's true that a returned context would be unusable,
>> since its resources are gone, but it would be nice to prevent contexts from
>> escaping the 'usingContext' function entirely.
>>     
>
> The short answer is no.
> Types are not sufficient to prevent values from escaping.
> In ocaml, you have both functions and references.
>   
There is at least a partial solution using polymorhic records or other
ways of quantifying type variables inside a type expression : If you
artificially parameterise the type context with an unused parameter (and
hide the type definition), you can then require the argument function to
be polymorphic with respect to this parameter, which should prevent it
from returning or storing its argument.

However, it still allows Jacques Garrigue's example, if  there exists a
function chgCtx which takes any context (ignoring the parameter) and
does something with it. Maybe there is a way to type chgCtx so as to
prevent that ?

Tiphaine

> So you can always plug a function of type [unit -> unit] into a
> reference, and the function is allowed to access the full context
> available when it was created.
>
> let r = ref (fun () -> ())
>
> let f ctx =
>   r := (fun () -> chgCtx ctx)
>
> (* later on *)
>
> List.hd !r ()
>
>
> The language is just too expressive...
> You should rather look into adding a dynamic flag to your context,
> causing a runtime error if you use it later.
>
> Jacques Garrigue
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
>   

Re: [Caml-list] Preventing values from escaping a context

[Rich Neswold]

[-- Attachment #1: Type: text/plain, Size: 1730 bytes --]

On Tue, Feb 9, 2010 at 2:31 AM, Tiphaine Turpin <Tiphaine.Turpin@irisa.fr>wrote:

> Jacques Garrigue a écrit :
> > From: Rich Neswold <rich.neswold@gmail.com>
> >> My question is this: Is there a way to make the compiler reject a
> function
> >> parameter from returning the context parameter?
> > The short answer is no.
> > Types are not sufficient to prevent values from escaping.
> > In ocaml, you have both functions and references.
> >
> There is at least a partial solution using polymorhic records or other
> ways of quantifying type variables inside a type expression : If you
> artificially parameterise the type context with an unused parameter (and
> hide the type definition), you can then require the argument function to
> be polymorphic with respect to this parameter, which should prevent it
> from returning or storing its argument.
>

I'm not understanding you fully, sorry. I tried this:

module type Test =
  sig
  type 'a context = Context of int * int
  val usingContext : ('a context -> 'b) -> 'b
  end;;

module InsTest : Test =
  struct
  type phantom = unit
  type 'a context = Context of int * int
  let usingContext f = f (Context (1, 2) : phantom context)
  end;;


But I'm getting a "Signature mismatch" error in the usingContext signature.
Even trying to force the function:

let usingContext (f : 'a context -> 'b) = f (Context (1, 2) : phantom
context)


causes the error (the compiler is too smart  :) I've tried some minor
variations, but without success. Am I even close to what you were
describing?

Thank you for your time,

-- 
Rich

Google Reader: https://www.google.com/reader/shared/rich.neswold
Jabber ID: rich@neswold.homeunix.net

[-- Attachment #2: Type: text/html, Size: 4024 bytes --]

Re: [Caml-list] Preventing values from escaping a context

[Tiphaine Turpin]

Rich Neswold a écrit :
> On Tue, Feb 9, 2010 at 2:31 AM, Tiphaine Turpin
> <Tiphaine.Turpin@irisa.fr <mailto:Tiphaine.Turpin@irisa.fr>> wrote:
>
>     Jacques Garrigue a écrit :
>     > From: Rich Neswold <rich.neswold@gmail.com
>     <mailto:rich.neswold@gmail.com>>
>     >> My question is this: Is there a way to make the compiler reject
>     a function
>     >> parameter from returning the context parameter?
>     > The short answer is no.
>     > Types are not sufficient to prevent values from escaping.
>     > In ocaml, you have both functions and references.
>     >
>     There is at least a partial solution using polymorhic records or other
>     ways of quantifying type variables inside a type expression : If you
>     artificially parameterise the type context with an unused
>     parameter (and
>     hide the type definition), you can then require the argument
>     function to
>     be polymorphic with respect to this parameter, which should prevent it
>     from returning or storing its argument.
>
>
> I'm not understanding you fully, sorry. I tried this:
>
Sorry, I shouldn't have suggested such an exotic feature (polymorphic
records) without any explanation. Here is an adaptation of your example.
Of course, this kind of trick is not very intuitive, and using it in an
API may not always be a good idea.

Tiphaine

module type Test =
sig
  type 'a context = Context of int * int
  type 'b contextUser = {f : 'a . 'a context -> 'b}
  val usingContext : 'b contextUser -> 'b
end

module InsTest : Test =
struct
  type 'a context = Context of int * int
  type 'b contextUser = {f : 'a . 'a context -> 'b}
  let usingContext f = f.f (Context (1, 2))
end

open InsTest

(* Allowed *)
let _ = usingContext {f = function Context (x, _) -> x}

(* Rejected *)
let _ = usingContext {f = function x -> x}

(* Allowed *)
let _ = usingContext {f = function Context (x, y) -> Context (x, y)}
(* If you also wanted to prevent this one, you could make the type
   "context" either asbtract, with accessors (if you want context
   information to be accessed only in restricted, "consistent" way) or
   private (intuitively, "read-only") *)

Re: [Caml-list] Preventing values from escaping a context

[Rich Neswold]

[-- Attachment #1: Type: text/plain, Size: 474 bytes --]

On Tue, Feb 9, 2010 at 12:45 PM, Tiphaine Turpin
<Tiphaine.Turpin@irisa.fr>wrote:

> Here is an adaptation of your example.
>

Thank you! I'll experiment with your example to see if I can use it (like
you said, it may be too complicated to add to the API.) Regardless, it was
an interesting lesson and taught me a little more about the language.

Thanks again,

-- 
Rich

Google Reader: https://www.google.com/reader/shared/rich.neswold
Jabber ID: rich@neswold.homeunix.net

[-- Attachment #2: Type: text/html, Size: 887 bytes --]

Re: [Caml-list] Preventing values from escaping a context

[Goswin von Brederlow]

Rich Neswold <rich.neswold@gmail.com> writes:

> On Tue, Feb 9, 2010 at 12:45 PM, Tiphaine Turpin <Tiphaine.Turpin@irisa.fr>
> wrote:
>
>     Here is an adaptation of your example.
>
>
> Thank you! I'll experiment with your example to see if I can use it (like you
> said, it may be too complicated to add to the API.) Regardless, it was an
> interesting lesson and taught me a little more about the language.
>
> Thanks again,

Why not make the context a custom block with finalizer? The finalizer
then frees the resources. If the context escapes then it remains alive
and the finalizer will not be called any time soon. Only when it is no
longer reachable. That would also allow someone to create a context and
use it for a number of operations before forgeting it.

The drawback is that the finalizer will only be called when the GC runs
at some later time. If you need the resources to be freed right there
then it won't help.

MfG
        Goswin

Re: [Caml-list] Preventing values from escaping a context

[Rich Neswold]

[-- Attachment #1: Type: text/plain, Size: 719 bytes --]

On Wed, Feb 10, 2010 at 2:55 AM, Goswin von Brederlow <goswin-v-b@web.de>wrote:

> Why not make the context a custom block with finalizer? The finalizer
> then frees the resources. If the context escapes then it remains alive
> and the finalizer will not be called any time soon. Only when it is no
> longer reachable. That would also allow someone to create a context and use
> it for a number of operations before forgeting it.
>

Good point. I'll need to consider this as a possible API direction. I have
many years of C/C++ programming under my belt, so I tend to want to
micromanage the resources. :)

-- 
Rich

Google Reader: https://www.google.com/reader/shared/rich.neswold
Jabber ID: rich@neswold.homeunix.net

[-- Attachment #2: Type: text/html, Size: 1112 bytes --]

Re: [Caml-list] Preventing values from escaping a context

[Goswin von Brederlow]

Rich Neswold <rich.neswold@gmail.com> writes:

> On Wed, Feb 10, 2010 at 2:55 AM, Goswin von Brederlow <goswin-v-b@web.de>
> wrote:
>
>     Why not make the context a custom block with finalizer? The finalizer
>     then frees the resources. If the context escapes then it remains alive
>     and the finalizer will not be called any time soon. Only when it is no
>     longer reachable. That would also allow someone to create a context
>     and use it for a number of operations before forgeting it.
>
>
> Good point. I'll need to consider this as a possible API direction. I have many
> years of C/C++ programming under my belt, so I tend to want to micromanage the
> resources. :)

As an example I have done this while rewriting Unix.file_descr for
myself.

My FD is a custom block containing the int. MyUnix.close will set the
int to -1 to signal the FD is no longer valid. MyUnix.read / write /
... throw an exception when the FD is -1. And the finalizer outputs a
warning and closes the FD unless it is -1.

That way I can close FDs when I want them closed and I can not leak an
unclosed FD (although you can still keep it alive forever). I also get a
warning when I forget to close an FD either soon after it dies or at the
end of the program if it was kept alive forever.

MfG
        Goswin

Re: [Caml-list] Preventing values from escaping a context

[Rich Neswold]

[-- Attachment #1: Type: text/plain, Size: 725 bytes --]

On Mon, Feb 8, 2010 at 9:38 PM, Jacques Garrigue <
garrigue@math.nagoya-u.ac.jp> wrote:

> From: Rich Neswold <rich.neswold@gmail.com>
>
> > My question is this: Is there a way to make the compiler reject a
> function
> > parameter from returning the context parameter?
>
> The language is just too expressive...
> You should rather look into adding a dynamic flag to your context,
> causing a runtime error if you use it later.
>

This is the way it works now, so I'll continue to use it. I'm still new to
the functional language scene and wasn't sure if I was missing something
obvious.

Thanks for your time!

-- 
Rich

Google Reader: https://www.google.com/reader/shared/rich.neswold
Jabber ID: rich@neswold.homeunix.net

[-- Attachment #2: Type: text/html, Size: 1330 bytes --]

Re: [Caml-list] Preventing values from escaping a context

[Yaron Minsky]

[-- Attachment #1: Type: text/plain, Size: 849 bytes --]

On Mon, Feb 8, 2010 at 10:07 PM, Rich Neswold <rich.neswold@gmail.com>wrote:

> (I realize that making this context a monad is a legitimate solution.
> However, until I see the Ocaml community including monads in the standard
> library, I think I'll stick with idiomatic Ocaml. I'd also like to solve
> this functionally, so I'm discounting the use of objects. Sorry for these
> constraints!)
>

I don't know that monads solve your problem here, but monads are a perfectly
reasonable idiom in OCaml.  You won't find them in the standard library
because the standard library is very conservative.  But you will find them
in Jane Street's Core library, and we use them reasonably often.  I think
there's no reason to avoid monads in OCaml (although obviously there's not
much to be gained by using them for vanilla effects, as is done in Haskell.)

y

[-- Attachment #2: Type: text/html, Size: 1159 bytes --]

Re: [Caml-list] Preventing values from escaping a context

[Rich Neswold]

[-- Attachment #1: Type: text/plain, Size: 1347 bytes --]

On Mon, Feb 8, 2010 at 9:59 PM, Yaron Minsky <yminsky@gmail.com> wrote:

> On Mon, Feb 8, 2010 at 10:07 PM, Rich Neswold <rich.neswold@gmail.com>wrote:
>
>> (I realize that making this context a monad is a legitimate solution.
>> However, until I see the Ocaml community including monads in the standard
>> library, I think I'll stick with idiomatic Ocaml. I'd also like to solve
>> this functionally, so I'm discounting the use of objects. Sorry for these
>> constraints!)
>>
>
> I don't know that monads solve your problem here, but monads are a
> perfectly reasonable idiom in OCaml.  You won't find them in the standard
> library because the standard library is very conservative.  But you will
> find them in Jane Street's Core library, and we use them reasonably often.
> I think there's no reason to avoid monads in OCaml (although obviously
> there's not much to be gained by using them for vanilla effects, as is done
> in Haskell.)
>

I've used monads in Haskell to "hide" a parameter, so I may be able to do
the same for this case. Since I think I'm also going to use the Lwt library,
which is monadic, I wouldn't be setting the precedent.

Thanks, I'll also look into adding Jane Street's Core library to my
installation.

-- 
Rich

Google Reader: https://www.google.com/reader/shared/rich.neswold
Jabber ID: rich@neswold.homeunix.net

[-- Attachment #2: Type: text/html, Size: 2124 bytes --]

Re: [Caml-list] Preventing values from escaping a context

[Alexey Rodriguez]

On Tue, Feb 9, 2010 at 4:59 AM, Yaron Minsky <yminsky@gmail.com> wrote:
>
> I don't know that monads solve your problem here, but monads are a perfectly
> reasonable idiom in OCaml.  You won't find them in the standard library
> because the standard library is very conservative.  But you will find them
> in Jane Street's Core library, and we use them reasonably often.  I think
> there's no reason to avoid monads in OCaml (although obviously there's not
> much to be gained by using them for vanilla effects, as is done in Haskell.)

This is interesting. We have been considering using monads where I
work but we worry about possible performance problems. Have you
experienced reduced performance? Also, do you have a guideline on when
to use them? We are thinking of using monads in a DSL, but only to
build values (think of some kind of compilation) that can later be
efficiently inspected.

On whether monads can solve the problem in this thread, yes they can.
But for this you need support from the type system (rank-2 universal
quantification). This is what Haskell does with the ST monad. The
compiler detects the value leak and aborts compilation with a type
error. If you are interested in a reference I can dig it up later.

Cheers,

Alexey

Re: [Caml-list] Preventing values from escaping a context

[rossberg]

"Alexey Rodriguez" <mrchebas@gmail.com> wrote:
>
> On whether monads can solve the problem in this thread, yes they can.

Not in OCaml. In the presence of unrestricted side effects, the ST monad
trick is no longer sufficient because a resource can leak through a
reference or an exception without that showing up in the type.

> But for this you need support from the type system (rank-2 universal
> quantification).

FWIW, OCaml can express that, but it doesn't help the problem.

/Andreas

Re: [Caml-list] Preventing values from escaping a context

[Alexey Rodriguez]

On Thu, Feb 11, 2010 at 12:05 PM,  <rossberg@mpi-sws.org> wrote:

>> But for this you need support from the type system (rank-2 universal
>> quantification).
>
> FWIW, OCaml can express that, but it doesn't help the problem.

Andreas, I'd be interested in seeing such encodings. Any pointers?

Thanks!

Cheers,

Alexey

Re: [Caml-list] Preventing values from escaping a context

[rossberg]

"Alexey Rodriguez" <mrchebas@gmail.com> wrote:
>
>>> But for this you need support from the type system (rank-2 universal
>>> quantification).
>>
>> FWIW, OCaml can express that, but it doesn't help the problem.
>
> Andreas, I'd be interested in seeing such encodings. Any pointers?

There are currently two ways to express that in OCaml, either through
polymorphic record fields or through polymorphic object methods. For the
former, consider:

  type f_arg = {it : 'a. 'a -> 'a}
  let f {it = g} = (g 5, g true)

  f {it = fun x -> x}

One caveat is that the value restriction can byte you, especially if you
try to encode s.th like monads, but that's a somewhat separate issue.

/Andreas