Hacker News new | ask | show | jobs
by radarsat1 2804 days ago
Is it possible? I mean, to add linear types via a library? I feel like it would have been done already if it were.
3 comments

I am always impressed by what the ocaml/Haskell people can do compared to my language of choice (scheme).

Iirc Oleg Kiselyov implemented proper delimited continuations in ocaml as a library, without touching the runtime or compiler. Something similar has been done in Haskell.

I doubt fully dependent types can be implemented in Haskell without extra help by ghc. There has been lots of work in the area, and last time I checked you could simulate DT to some degree, but it never was as powerful as the dependant types in idris. Iirc t were some edge cases where the typing became undecidable.

>Iirc Oleg Kiselyov implemented proper delimited continuations in ocaml as a library, without touching the runtime or compiler.

To clarify this, the library you're talking about implements most of the functionality in C, reusing the runtime's exception mechanism. So it doesn't require any upstream change to compiler or runtime, but it also can't be implemented in pure OCaml.

Hmmm. I remembered incorrectly then. The bytecode version is possible in pure ocaml, but for native it apparently needs C.

For Haskell it is however possible. There is a neat paper by among others Kent Dybvig.

It's possible if you have dependent types and are not afraid to (ab)use the type system. See section 2.4 of my thesis (link in bio) for a taste. You have to squint a bit but a system like that can ensure linearity.
Linear types amounts to modification of environment - "use" of linear value removes it from environment, so you can't eat cake and still have it. If you look at the use of unique types in Clean, you will see that their use closely reminds monadic code (e.g. "#" syntax). Otherwise you will need to invent variable names like handle1, handle2, handle3... to refer of "modified" handles generated after each use.

You can easily simulate that using parametrized monad: http://blog.sigfpe.com/2009/02/beyond-monads.html

E.g., hClose will have type like (Has listIn h, listOut ~ Del h listIn) => h -> ParamMonad listIn listOut () and hGetLine will result in type much like this one: (Has list h) => h -> ParamMonad list list String

It is not perfect: you still may have reference to handle after it's use and you may be tempted to introduce it somehow back and get run-time error; you also would struggle juggling two handles for copying files, for example (for this you may have to use ST parametrization trick).

But anyway, you really not need linear types all that often (they are cumbersome - I tried to develop language with linear types, type checking rules and types get unwiledy very soon) and when you do, you can have a library. Just like STM, parsers, web content generation/consumption, etc. Linear types do not warrant language change.