News aggregator

On type safety for core Scala: "From F to DOT: Type Soundness Proofs with Definitional Interpreters"

Lambda the Ultimate - Sat, 10/24/2015 - 7:45am

From F to DOT: Type Soundness Proofs with Definitional Interpreters by Tiark Rompf and Nada Amin:

Scala's type system unifies aspects of ML-style module systems, object-oriented, and functional programming paradigms. The DOT (Dependent Object Types) family of calculi has been proposed as a new theoretic foundation for Scala and similar expressive languages. Unfortunately, type soundness has only been established for a very restricted subset of DOT (muDOT), and it has been shown that adding important Scala features such as type refinement or extending subtyping to a lattice breaks at least one key metatheoretic property such as narrowing or subtyping transitivity, which are usually required for a type soundness proof.
The first main contribution of this paper is to demonstrate how, perhaps surprisingly, even though these properties are lost in their full generality, a richer DOT calculus that includes both type refinement and a subtyping lattice with intersection types can still be proved sound. The key insight is that narrowing and subtyping transitivity only need to hold for runtime objects, but not for code that is never executed. Alas, the dominant method of proving type soundness, Wright and Felleisen's syntactic approach, is based on term rewriting, which does not make an adequate distinction between runtime and type assignment time.
The second main contribution of this paper is to demonstrate how type soundness proofs for advanced, polymorphic, type systems can be carried out with an operational semantics based on high-level, definitional interpreters, implemented in Coq. We present the first mechanized soundness proof for System F<: based on a definitional interpreter. We discuss the challenges that arise in this setting, in particular due to abstract types, and we illustrate in detail how DOT-like calculi emerge from straightforward generalizations of the operational aspects of F<:.

Not only they solve a problem that has been open for 12 years, but they also deploy interesting techniques to make the proof possible and simple. As they write themselves, that includes the first type-soundness proof for F<: using definitional interpreters — that is, at least according to some, denotational semantics.

Understated Twitter announcement here.

Categories: Offsite Discussion

A couple of quick questions about recursion-schemes

Haskell on Reddit - Sat, 10/24/2015 - 6:35am

I am looking at the recursion-schemes package (not for the first time), and would like to improve my understanding of some things:

  1. Mu and Nu are supposed to be the least and greatest fixed points, respectively, yet they both have both Foldable and Unfoldable instances. Is it the case that if you wanted to consistently distinguish between data and codata, that you would then only have Foldable (Mu f) and Unfoldable (Nu f), but not vice versa?

  2. How come there are three? Does Fix correspond to Mu or to Nu... or, somehow, to both, or neither? (Is there a fourth hanging out somewhere offstage?)

  3. I notice that if you write data ListF a x = Nil | Cons a x and plug that into Fix, you get a potentially-infinite list: "codata", while if you use data ListF' a x = Nil' | Cons' a !x, you get a strictly-finite list: "data". Does the strictness of the recursive position always determine whether the result is data or codata? What if I do something silly like data WeirdTreeF a x = Leaf | Branch x a !x, where it's heterogenous?

  4. What if I plug those into Mu and Nu? Is data-vs.-codataness determined by the fixed point operator, or by the base functor?

  5. Is there a word (instead of "data-vs.-codataness") to encompass data and codata, in the way that "color" is a word to encompass red and green, or "polarity" is for positive and negative?

submitted by glaebhoerl
[link] [13 comments]
Categories: Incoming News

type error formatting

glasgow-user - Sat, 10/24/2015 - 3:48am
Here's a typical simple type error from GHC: Derive/Call/India/Pakhawaj.hs:142:62: Couldn't match type ‘Text’ with ‘(a1, Syllable)’ Expected type: [([(a1, Syllable)], [Sequence Bol])] Actual type: [([Syllable], [Sequence Bol])] Relevant bindings include syllables :: [(a1, Syllable)] (bound at Derive/Call/India/Pakhawaj.hs:141:16) best_match :: [(a1, Syllable)] -> Maybe (Int, ([(a1, Syllable)], [(a1, Sequence Bol)])) (bound at Derive/Call/India/Pakhawaj.hs:141:5) In the second argument of ‘mapMaybe’, namely ‘all_bols’ In the second argument of ‘($)’, namely ‘mapMaybe (match_bols syllables) all_bols’ I've been having more trouble than usual reading GHC's errors, and I finally spent some time to think about it. The problem is that this new "relevant bindings include" section gets in between the expected and actual types (I still don't like that wording but I've gotten used to it), which is the most critica
Categories: Offsite Discussion

ICFP 2016 Call for Workshop and Co-located Event Proposals

General haskell list - Sat, 10/24/2015 - 12:31am
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;CALL FOR WORKSHOP AND CO-LOCATED EVENT PROPOSALS &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ICFP 2016 &nbsp;21st ACM SIGPLAN International Conference on Functional Programming &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;September 18-24, 2016 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Nara, Japan &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;http://icfpconference.org/icfp2016/ The 21st ACM SIGPLAN International Conference on Functional Programming will be held in Nara, Japan on September 18-24, 2016. ICFP provides a forum for researchers and developers to hear about the latest work on the design, implementations, principles, and uses of functional programming. Proposals are invited for workshops (and other co-located events, such as tutorials) to be affiliated with ICFP 2016 and sponsored by SIGPLAN. These events should
Categories: Incoming News

Breaking Changes and Long Term Support Haskell

libraries list - Wed, 10/21/2015 - 10:33am
There seems to be a fair amount of friction between those who want to introduce new features or fix significant historical warts in the base libraries - even if this requires breaking changes - and those who insist on no significant breaking changes in new releases, regardless of the reason or how much warning was given. The rest of the industry has already solved this with long-term/extended support releases. Some version of the platform is blessed with long-term support, and will continue to receive bug fixes and security patches for a number of years, but no other changes. This solution exists for Haskell as well, in the form of Long-Term Support Haskell (https://github.com/fpco/lts-haskell/blob/master/README.md) by FP Complete. Not only GHC but an entire ecosystem of libraries are frozen when a new LTS version is released and only bug/security fixes are allowed going forward. Users requiring long-term stability over new features could use LTS Haskell, while those who accept some fixing up of old code
Categories: Offsite Discussion

3 release policy

libraries list - Tue, 10/20/2015 - 8:55pm
A "3 release policy" has been recently mentioned several times, whereby it should always be possible to write code that compiles with the last three releases of GHC, without generating any -Wall warnings. The no warning requirement seems excessively harsh. Will early warnings of impending breakage really cause so much trouble that accepted proposals have to be dragged out over several years to avoid them? If so, would a flag to suppress the warnings suffice? I should note that GHC has traditionally had no qualms about introducing new warnings, on by default. -- View this message in context: http://haskell.1045720.n5.nabble.com/3-release-policy-tp5820363.html Sent from the Haskell - Libraries mailing list archive at Nabble.com.
Categories: Offsite Discussion

Default definition for fromRational

libraries list - Thu, 10/15/2015 - 11:51pm
A suitable default definition for fromRational could be the following: fromRational n = fromInteger (numerator n) / fromInteger (denominator n) Changing the MINIMUM pragma to just {-# MINIMAL recip | (/) #-} - Joe
Categories: Offsite Discussion

New gtk2hs 0.12.4 release

gtk2hs - Wed, 11/21/2012 - 12:56pm

Thanks to John Lato and Duncan Coutts for the latest bugfix release! The latest packages should be buildable on GHC 7.6, and the cairo package should behave a bit nicer in ghci on Windows. Thanks to all!

~d

Categories: Incoming News