rust.txt

SUBMITTED
Checked arithmetic
Ban private items in public APIs
Turn capitalization conventions into language rules for 1.0
Change `extern "ABI"` to `extern<ABI>` or `extern ABI`
Use `for` to introduce universal quantification
Trait-based exception handling
Rename `Option`, add `Assert` trait
Represent equivalent enums the same as bool, make bool an enum
Allow #attr and #attr(foo) but still require #[attr = foo]
Lifetime syntax (lose the tick)
foo::<T>() -> foo@<T>()

NEXT UP
"Enum match problem" lint
Make `.` always maximally deref
`extern mod`

Distinguish data types from abstract types
Deconflate types and modules
Purity
DST reform (EQT)

trait Transmute
Garbage collection (trait Trace)
&out
&move

# RFCs
  # CRITICAL
    * Existentially Quantified Types (IN PROGRESS)
      * `struct Foo<T: Trait>` `&Foo` for thin pointer to structs with internal vtables
      * String literals are unboxed rvalues
      * ...
    * Purity for (almost) free (FIGURED OUT)
    * Deconflate types and modules, UFCS, UMCS, ... (FIGURED OUT)
    * Distinguish data types from abstract types (`abstract struct`, `data struct`, `class`, whatever) (IN PROGRESS)
    * Deterministic name resolution (AKA "No guessing")
    * Closure reform (SUBMITTED BY nikomatsakis)
  # BIC
    * Make inline `mod`s obey normal scoping rules
      Distinguish inline (in-file) vs. external (separate file) modules
      Items of (in-same-file) parent modules are in scope for inline mods, `use` uses relative paths. Like C++.
      inline mods: `mod foo { ... }`, out-of-line mods declared: `extern mod foo;` (but bikeshed)
      http://www.reddit.com/r/rust/comments/2he9xi/rusts_modules_are_weird_another_explanation_of/cks4cch
    ? Remove subtyping and variances (only sublifetimes, but not sub*type*s?)
    ? Automatic coercions reform (`as` reform?)
    ? Linear types
      Unwinding? Require explicit `Drop` bounds?
    * Parametricity
      * QUESTION: how to reconcile with trait SizeOf<T> { static N: uint } forall types?
        trait SizeOf<T> { static SIZE_OF: uint; }; 
        unsafe fn size_of<T>() -> uint;
        is this a problem for static declarations?
        or just have a `sizeof` operator which is `unsafe`?
      * QUESTION how to deal with Drop? require it explicitly?
    * Checked arithmetic (SUBMITTED)
    * Ban private items in public signatures (KINDA ACCEPTED BUT NOT REALLY)
    * Tighten shadowing rules (SUBMITTED BY Kimundi)
    * Enforce capitalization conventions (REJECTED)
      Convention over configuration!
    * *T should be non-nullable
      `Option<fn()>` is *already* required in FFI! Should just guarantee repr of `Option`-like generic types with FFI-relevant type arguments.
    * Syntax wibbles:
        Struct { f: v } -> Struct { f = v }
        #[attr]         -> #attr (like hashtags => suggestive of metadata)
        name@pat        -> pat as name
        <'a> |&'a Foo|  -> for<'a> |&'a Foo|
        &'a mut Foo     -> &mut 'a Foo
        extern "C"      -> extern C, extern<C>, or extern(C) (SUBMITTED)
        foo::<T>        -> foo@<T> (remove confusion w/ module scoping)
        fn foo<'a>      -> fn foo<lifetime a> or fn foo<scope a>
        &'a Foo         -> &(a) Foo or &{a} Foo (braces are suggestive of scopes)
  # IMPORTANT
    * "Mutability polymorphism"
    * Trait-based exception handling (SUBMITTED)
    * trait Trait1 + Trait2 (PARTIALLY IMPLEMENTED)
    * trait Transmute<T> (SUBMITTED BY gereeter)
    * GC, trait Trace
    * &move
    * &out (SUBMITTED BY gereeter)
    * "Unboxed trait objects" (SUBMITTED BY aturon, POSTPONED) (might be subsumed by EQT!)
    * Type ascription
    * Associated types (SUBMITTED BY aturon)
    * Macro reform
  # MINOR
    * General function-like generics syntax sugar
        type Proc(A) -> R = Box<Send + FnOnce(A) -> R>;
      QUESTION where to put lifetimes (&mut FnMut...)
      (general guideline: use for things that (could) impl... Fn? Category? Profunctor?)
    * UnsafeUnion<A, B>
    ? Incoherent empty traits
    * Associated statics (SUBMITTED BY aturon)
    ? Anonymous sum types (int|bool|char)
    * enum bool { false, true }, all two-nullary-variant enums repr.-ed the same as a bool (BIC?)
      generally: guarantee all merely-alpha-renamed structs, tuples, enums repr.-ed the same? (no reason not to)
    * Early return from any block (like `break`, but not just loops, and with a value)
    * Explicit refutable `let`: `let`..`else`
    * Scoped refutable `let`: `if let` (SUBMITTED BY kballard, ACCEPTED)
    * Expose tuple fields as .0 .1 ... .N (SUBMITTED BY P1Start, ACCEPTED)
    * Array splicing
    * Fixed-length array slices in patterns (SUBMITTED BY krdln)
    * Destructuring assignment
    * Disjunctive patterns in `let`s (SUBMITTED BY P1start, POSTPONED)
    * Liberalized destructing struct destructuring
    ? Limited type inference for `static` items
    * #compact struct, enum
    ? Generalized unboxed object literals (closures) for any trait, not just `Fn`* 
        QUESTION syntax: impl-like? closure-like? struct-like?
          let num = 42;
          let showable_obj = &Show {
              show: num.to_str()
          };
        self is implicit?! like fn closures
    * for<T1..TN> { ..items.. } (SUBMITTED BY ben0x539, POSTPONED)
    * Naming wibbles:
        macro_rules! -> macro!, define!
        Any          -> Dynamic
        Arc          -> AtomicRc
        Option       -> Maybe  (Optional,   Nullable)
        Some|None    -> Yes|No (Full|Empty, Val|Null)
        unwrap       -> assert (goes well w/ Yes|No)
        Void         -> Never
        int, uint    -> isize, usize
        char         -> Char (no need to confuse w/ C char)
        Iterator     -> Iterate? (or maybe Iterable -> Iterate)
        unsafe       -> dangerous? (same meaning, stronger)
  # FAR FUTURE
    * `static` generics parameters
    * Generic generics parameters (HKT)
    * Partial type application
    * Trait generics parameters (ConstraintKinds)
    * Kind polymorphism
    * First-class polymorphic types (higher-rank types)
    * Explicit existential quantification syntax
    * Existential quantification in structs
    * Polymorphic recursion
    * `static fn`, CTFE
    ? Dependent types a la pigworker
    * Datatype-generic programming (GHC.Generics)
    * Variadic generics
    * TCE
    ? Delayed initialization of struct fields (loop tying)


## QUESTIONS
 * What would break without subtyping for lifetimes?
 * What's the conflict between modules and macros?
 * Why isn't a simple newtype-based design sufficient for HashMap?
 * Is `Arrow` connected to linear logic/types? (To closed (symmetric) monoidal categories?)
   * linear types correspond in some way to indexed monads (session types)
   * categories are indexed monoids (arrows extend categories)
   * a monoid is kind of like a monad without the typaram (Monad m => Monoid (m ()))
   * Monads hide the state and only expose state transformers
   * GHC's IO + ST monad uses linear capability passing behind the scenes, but can't enforce the linearity, hence IO is abstract
   * Arrowized FRP hides the signals and only exposes signal transformers
   * => With linear types, could we safely expose the signals?
 * Is there a relationship between traits and copatterns/codata? https://github.com/idris-lang/Idris-dev/wiki/Copatterns
 * Is there a description/paper about UHC's implementation of existential types?
 * How can safety of (multiply-)intrusive data structures be proved / reasoned about in general?
 * https://github.com/rust-lang/meeting-minutes/blob/master/workweek-2014-08-18/associated-items.md
   => What are path dependent types?
   Same thing as this? http://stackoverflow.com/questions/2693067/what-is-meant-by-scalas-path-dependent-types
   Where do they occur in Rust? (Something to do with trait objects?)
 * Is it possible that we might want bidirectional typechecking/inference instead of HM?
   The biggest "drawback" usually cited for BiDiTC is that it requires type signatures on top-level definitions.
   But we already require that!


## LANG ITEMS PROBLEM
There are many language features which would be backwards-compatible additions, except that they would, or should, have an impact on various lang item traits => scope creep. Is there any good resolution to this problem?
Examples:
 * `Fn`* want associated types.
 * `Fn`* may want arity polymorphism.
 * `Iterator` wants associated types and `&move`.
 * `Deref`* and `Alloc` (for `box`) want HKTs.
 * `Alloc` wants `&out`.
 * `Deref`, `Fn`, `Index` want mutability polymorphism!
Just declare these unstable, and move on? Or what?
Specific features:
 * We're already adding assoc types.
 * If it's not much work on top of static drop analysis, we should just add `&out` (and `&move`?).
 * HKTs are harder.
 * Arity polymorphism: definitely not yet.
 * Mutability polymorphism: seems like a big change.
Likewise for standard library... if we want to add everything that might impact std before 1.0, we're going to end up adding /every/ major feature before 1.0.
If a feature didn't have an impact on libraries, it wouldn't be major.
Only real solution is to version stdlib.


## MUTABILITY POLYMORPHISM
move mutability from reference types onto lifetimes
this is what Disciple does!!
lifetimes can have constraints e.g. "mutable", "unaliased", "shared", w/e
("lifetime" nomenclature stops being so helpful - difficult to envision a lifetime having a mutability; a "region" less so)
instead of current 2 reference types (+ more in the future), would have only one, parameterized over a lifetime, which in turn over mutability
can be either polymorphic over constraints-on-lifetimes or specify constraints; constraints can conflict
current set of constraints would be: shared, mut (which conflict)
this would essentially be reifying existing borrow checker rules/logic into language constructs
can mostly (entirely?) keep existing (quite nice) surface syntax as sugar for more sophisticated underlying mechanisms
example: instead of separate `Deref` traits for shared and mutable refs, could have just a single one
    trait Deref<constraints cs> {
        fn deref<T, 'a: cs>(&'a Self<T>) -> &'a T; // also HKT here, but orthogonal
    }
    impl<constraints cs> Deref<cs> for Box { ... } // equiv of both existing `Deref` and `DerefMut`
    impl Deref<shared> for Rc { ... } // equiv of just existing `Deref`
  could also `impl Deref<mut> for ...` if that's ever desired (just `DerefMut`)
  likewise for `Fn`, `Index`, ...?
could extend lifetime elision to also elaborate mutabilities/constraints
with `&?" to denote a reference of unspecified constraints (plain `&` continues to mean "shared"):
    fn get_member(self: &? Foo) -> &? Bar;
elaborates to:
    fn get_member<constraints cs, 'a: cs>(self: &'a Foo) -> &'a Bar;
putting the constraint in the ref type is just sugar for the same constraint on the lifetime
    `fn foo(&mut int)`        -> `fn foo<'a: mut>(&'a int)`
    `fn foo<'a>(&'a mut int)` -> `fn foo<'a: mut>(&'a int)`
built-in traits on `&` determined by constraints on lifetime
    impl<T, 'a: shared> Copy for &'a T { }
can expand the set of constraints to "add more reference types", with repercussions
  `uniq`: conflicts with `shared`, implied by `mut`
  `read`: can be read from ("is initialized"). implied by `shared`, `mut`, `move`
  `move`: "is initialized, must be deinitialized" implies `mut`, `uniq`, and `read`
  `out`: "is uninitialized, must be initialized" implies `uniq`, conflicts with `read`
  has further ramifications for built-in traits & "default assumptions"
  a ref with `out` lifetime must be used linearly
  can't consume `move` without destroying referree
  instantiating above fully-polymorphic impl Deref for Box with `out` or `move` would **not** be safe
    therefore, the definition as provided must be considered illegal? (or not, because uses `unsafe`?)
  to make it safe&legal, would prob need something like:
    impl<constraints cs: read>  Deref<cs> for Box { ... }
  but still not enough: must somehow rule out `move`!
  (maybe each lifetime should be parameterized over *two* constraints: a "before" and an "after"? 
    might help reduce proliferation of types of constraints. e.g. instead of `out`, have before: init, after: uninit
    in this case the `Box` impl could specify that both before & after must be alive, which hopefully should be sufficient)
could potentially fold unsafe/raw pointers under this umbrella as well
  `safe` and/or `unsafe` would become further constraints
  derefing a ref with `unsafe` (or without `safe`?) lifetime would require an `unsafe { }`
  `mut` would no longer imply `uniq`, and would be separate (to support `*mut`)
  probably further refinements required to support read-only `*const` vs. usually-immutable `&`
in expression language, /could/ make `&` operator be polymorphic over constraints, thus inferred from use site
  but probably don't want to!!
  functions being usable with different reference types is valuable
  `&` operator being usable with any concretely-constrained function is not, just hurts readability
  (would also lead to ambiguity w/ constraint-polymorphic functions, but could just default to "shared")


## REMOVE SUBTYPING?
  https://github.com/rust-lang/rfcs/pull/192#issuecomment-52168355
  or rather, remove the need for variance inference / annotations?
  TENTATIVE PLAN:
    type parameters are always invariant
      use `trait Transmute`, safe-`transmute()` to explicitly coerce compatible types
    lifetime parameters are always contravariant (like `&`)
      is there any use case _whatsoever_ for a closure or fn type where the lifetime of an arg is fixed instead of polymorphic?
      e.g. do you _ever_ want `fn foo<'a>(f: fn(&'a Foo) -> ...)` instead of `fn foo(f: <'a> fn(&'a Foo) -> ...)`?
  motivation:
   * avoid the need for variance annotations on abstract types
   * free up complexity budget for other things (e.g. EQT)


## TRANSMUTE
 (originally Coercible)
 featherweightmusings.blogspot.hu/2014/03/subtyping-and-coercion-in-rust.html
 no subtyping
 only Transmute trait + variances/roles
 Transmute is explicitly declared for abstract `struct`s, just like the other built-in traits
 three different conversioney things:
   Transmutes:
     zero-runtime-cost reinterpretations
   Automatic coercions:
     those which only involve throwing information away
     casting away concrete types into existentials
     casting numeric types to strictly larger numeric types
       u8  -> u16 i16 u32 i32 f32 u64 i64 f64
       i8  ->     i16     i32 f32     i64 f64
       u16 ->         u32 i32 f32 u64 i64 f64
       i16 ->             i32 f32     i64 f64
       u32 ->                     u64 i64 f64
       i32 ->                         i64 f64
       f32 ->                             f64
     how to extend this to user-defined types?
   Casts with `as`:
     somewhat ad-hoc?
     int-float conversions based on numeric value
       like for hypothetical automatic coercions, but in any direction
     how to extend to user-defined types?
  if T is:
    free          => no conditions
    covariant     => T: Coercible<U>
    contravariant => U: Coercible<T>
    invariant     => T: Coercible<U> && U: Coercible<T>
    fixed         => !
    what about `ref` roles? part of this hierarchy or orthogonal?
      free: always ref
      fixed: never ref
      co, contra, invariant: ?
 instead of variances on type parameters, use generic `Transmute` impls!!
   instead of `struct Foo<bivariant T>`:
     impl<U> Transmute<Foo<U>> for Foo<T>
   instead of `struct Foo<covariant T>`:
     impl<U, T: Transmute<U>> Transmute<Foo<U>> for Foo<T>
   instead of `struct Foo<contravariant T>`:
     impl<U, T: Transmute<U>> Transmute<Foo<T>> for Foo<U>
   instead of `struct Foo<invariant T>`:
     impl<T, U> where T: Transmute<U>, U: Transmute<T> Transmute<Foo<U>> for Foo<T>
   instead of `struct Foo<fixed T>`:
     nothing
   instead of `struct HashMap<K, covariant V>`:
     impl<K, V2, V1: Transmute<V2>> Transmute<HashMap<K, V2>> for HashMap<K, V1>
   `impl<T, U: HasPrefix<T>> Transmute<&U> for &T`
   `impl<T, U: Transmute<T>, static N: uint> Transmute<[U, ..N]> for [T, ..N]`
   mass borrowing would require forall-constraints, but can be done with Skolems
 can this be done entirely as a library?? (except for the auto-deriving and the more-magical built-in impls..?)
 impl<T> HasPrefix<()> for T
 impl<T> HasPrefix<T> for Void // or even Transmute?
 HasPrefix -> Extends?


## LINKS

Inferring Safe is wrong (abstract vs. data type distinction)
https://ghc.haskell.org/trac/ghc/ticket/8827
related http://ezyang.tumblr.com/post/96448232652/safe-zero-cost-coercions-for-haskell-richard

FlexibleInstances can be used to violate coherence!!
http://www.reddit.com/r/haskell/comments/2agy14/type_classes_confluence_coherence_global/civ6y1g
TODO port test case to Rust!
related http://blog.ezyang.com/2014/09/open-type-families-are-not-modular/ (ragamuffin instances)

Macro import/export
https://github.com/mozilla/rust/issues/3114

Meeting discussion about macros
https://github.com/rust-lang/meeting-minutes/blob/master/Meeting-other-2014-07-16.md

Adding dependent types to Haskell (pigworker = Conor McBride)
http://stackoverflow.com/a/13241158

Full dependent types in Haskell (w/ singletons)
http://lpaste.net/109388

Niko Matsakis's name resolution plan + prototype
https://github.com/nikomatsakis/rust-name-resolution-algorithm

API stability discussion, w.r.t. deterministic name resolution
https://github.com/rust-lang/meeting-minutes/blob/master/workweek-2014-08-18/api-evolution.md

Syntactic closures
http://www.rntz.net/post/intuitive-hygienic-macros.html

GHC kind inference
https://ghc.haskell.org/trac/ghc/ticket/9200

Freestanding implementation of OutsideIn
https://github.com/batterseapower/outside-in

Hindley-Milner elaboration in applicative style
http://ezyang.tumblr.com/post/96449381857/hindley-milner-elaboration-in-applicative-style

Implementation strategies for polymorphism
http://www.eecs.harvard.edu/~greg/cs256sp2005/lec15.txt

Ericson2314's modules/traits proposal
TOREAD https://github.com/Ericson2314/rfcs/blob/master/active/0000-combine-mod-trait.md
related http://ezyang.tumblr.com/post/96605373187/1ml-core-and-modules-as-one-or-f-ing-first-class
related http://www.reddit.com/r/haskell/comments/2foggq/why_does_david_turner_say_type_classes_were_a_bad/ckbw3g7 (neelk)
related http://www.reddit.com/r/haskell/comments/2foggq/why_does_david_turner_say_type_classes_were_a_bad/ckchsx5 (edwardkmett)

TCE
https://mail.mozilla.org/pipermail/rust-dev/2011-August/000711.html
https://mail.mozilla.org/pipermail/rust-dev/2011-August/000700.html
https://mail.mozilla.org/pipermail/rust-dev/2013-April/003557.html
https://github.com/mozilla/rust/issues/217

TOREAD Variadic generics / arity polymorphism
http://www.ccs.neu.edu/racket/pubs/NU-CCIS-08-01.pdf
http://www.ccs.neu.edu/racket/pubs/NU-CCIS-08-03.pdf
http://www.ccs.neu.edu/racket/pubs/esop09-sthf.pdf
http://www.ccs.neu.edu/racket/pubs/dissertation-tobin-hochstadt.pdf

rwbarton on type lambdas
http://www.reddit.com/r/haskell/comments/urc75/complicating_conduit/c4xyqiz

edwardkmett on the mistakes of Scala
http://www.reddit.com/r/haskell/comments/1pjjy5/odersky_the_trouble_with_types_strange_loop_2013/cd3bgcu
implicit lambdas http://www.reddit.com/r/haskell/comments/2fbe4t/compose_to_avoid_lambdas/ck7vzcs

BitC Lessons For Other Language Developers - Simple vs. Too Simple
http://www.coyotos.org/pipermail/bitc-dev/2012-May/003469.html

Exceptions
https://mail.mozilla.org/pipermail/rust-dev/2013-November/006563.html
http://blogs.msdn.com/b/ericlippert/archive/2008/09/10/vexing-exceptions.aspx
http://twistedoakstudios.com/blog/Post399_improving-checked-exceptions
http://www.reddit.com/r/haskell/comments/2csaml/are_there_any_new_developments_in_the_last_seven/
http://blog.ezyang.com/2011/08/8-ways-to-report-errors-in-haskell-revisited/
http://hackage.haskell.org/package/control-monad-exception
http://www.jot.fm/issues/issue_2011_01/article1.pdf
http://erdani.com/publications/cuj-2003-12.pdf

Linear types, regions, capabilities
http://pauillac.inria.fr/~fpottier/slides/fpottier-2007-05-linear-bestiary.pdf

Existential types
TODO add papers

Higher-rank types
TODO add papers


## INTRUSIVE DATA STRUCTURES
requires non-moveable types!?
what would the ExplicitMove trait look like?
because passing by value (moving) is impossible, pass by &move?
can't actually move out of the &move, but can consume it and copy contents
trait Relocate {
    fn relocate(from: &move Self, to: &out Self);
}
implicit movability is turned off by impl Relocate?
do you ever want Relocate and not Clone?
Relocate is equivalent to a Clone followed by a Drop (but more efficient)
reason normal movable types + pinning by borrowing it is not suitable:
  if it's borrowed it can't be moved to a new location explicitly either
  `relocate()` maintains dynamic invariants through user code
idea in Rust w/ everything movable is that values can have pointers out from them, but not into them
except in cases where it's statically tracked by the borrow checker
but this doesn't allow for constructs where invariants are upheld dynamically at runtime
is this also connected to the fact that you can only safely express (sendable) tree structures?
http://www.reddit.com/r/rust/comments/2ac60j/safely_storing_a_selfreference_in_self/ciu7wtw
is this related to arena allocation?
  yeah.. arenas shouldn't be movable
  but maybe that's handled by having `&` references into them?
  but then they're not `Send`, which is the point?
generic functions?? :(
use case: http://www.reddit.com/r/rust/comments/2gwi11/jonathan_blow_ideas_about_a_new_programming/cknhxyb
  how could we express this safely in Rust?
    struct Mesh<static N: uint, static M: uint> {
        N, M,
        verts: &'self mut [Vector3, ..N],
        indices: &'self mut [uint, ..M],
        verts_data: [Vector3, ..N],
        indices_data: [uint, ..M]
    }


## &out, &move
Expressiveness delta relative to pass-by-value and return-by-value:
  Explicit lifetimes, tying together
  Trait objects
  Slices
  Uniform representation
  Flexible timing of returns / moves


## Deterministic name resolution
"no guessing"
QUESTIONS: is seeing names from outer scopes still deterministic? why?
  conjecture: safe to add items, but not remove them
  what's the precise definition of "deterministic"?
  an extensional definition: such that adding (removing?) items doesn't cause silent behavior changes
  can we give an intensional one, i.e. what it precisely is that we're not allowed to do? (i.e. guessing/branching)
same-scope shadowing problem
  this is being solved
autoderef problem:
  method calls on things that impl Deref *always* deref
  to call fn on ref/ptr/box itself, use UFCS
  would auto cross-borrowing (smart Deref ptr -> &) cause any issues here?
autoref problem:
  TODO is there a problem?
method resolution + impls problem:
  should _not_ search trait impls when resolving methods
  trait methods are like any other generic fn
patterns + enum variants & statics problem:
  enforcing capitalization conventions globally would be best, but...
  a narrowly targetted solution:
  (irrefutable patterns can be left alone I think - don't think it's possible for it to cause a difference?)
  in refutable patterns, compiler *always assumes* uppercase is an enum/static, lowercase is binding!
  (definitely in `match`, need to think about `if let`)
  if you want to have an uppercase binding or lowercase enum/static, need to explicitly say so
  e.g. `Some(as MyBinding)` (esp. if/when `name@pat` becomes `pat as name`),  `enum my_variant`, `static my_static`, or something like that
  (bikeshed...)
  this is butt ugly!! but: so is the current situation!!!
  rarely-encountered ugly syntax is lesser evil than rarely-encountered ugly semantics:
    only the latter causes bugs
  there's still the hardline "case should never be significant" position, but if both sides standing on principle (i.e. not much practical difference), correctness is the more important principle


## DOM
> constraints:
> cheap field access from internal methods;
  > cheap      = constant offset (fixed prefix layout)
  > less cheap = offset in vtable
  > expensive  = virtual method
> cheap dynamic dispatch of methods;
  > "cheap"   = current virtual methods
  > expensive = going through an indirection for each link in the inheritance chain, i.e. a non-flattened tree-like structure
> cheap downcasting;
  > cheap     = TypeId in vtable
  > expensive = going through a virtual method to retrieve a TypeId (or worse)
> thin pointers;
> sharing of fields and methods between definitions;
> safe, i.e., doesn't require a bunch of transmutes or other unsafe code to be usable.
relevant features:
  trait Transmute
  EQT (thin pointers, downcasting (Any/Dynamic w/ associated static TypeId))
  closed traits (cheap "dynamic dispatch" (not even dynamic), downcasting)
TODO translate https://gist.github.com/jdm/9900569


## Misc features
 - lint: warn if a lowercase name in a pattern resolves to a variant/const, or if an uppercase one becomes a new binding
 - `struct std::float { val: f32 }` where the ops are all implemented to go through f64?
   (`half` where ops are via `f32` could be similarly)
 - `let loop` for recursive let?
 - fn literals
 - "trait objects for traits that never refer to Self could just be a pointer to vtable" (Ericson2314)
   but the associated fns, etc. are still associated to the type
   they just don't use a value of it at runtime
   (conflict w/ implicit Drop, Trace?)
   can we reformulate `fn` as a trait object this way?
 - potential new operators:
   ++/<>: semigroup op
   <=>: Ord compare
   ^, ^^, **: exponentiation
   function composition?
   logical implication? (equiv. to !B || A)
 - should be able to dyncast slices (types existentially-quantified-over-length) to fixed-length arrays slices
   where result slice length is *at most*, not *exactly* actual length (except for &out, &move...)
   then index elements statically
   (should this be integrated with pattern matching?)
 - allow `loop { }` to evaluate to a value by providing it to `break`
   `for`..`in`, `while`: have an `else` block
   related to "early return from any block"
 - allow assigning to return value before exiting function?
   fn foo() -> int {
       return = 9;
       println!("howdy");
   }
   as-if it were `fn foo(&out int)`
   but maybe this particular syntax doesn't work
   also strange w.r.t. types... last evaled expr wouldn't match return type
 - short-circuiting ptr-equality comparison for `impl Eq for &`?
   needs some kind of magic because of PartialEq, e.g. `{ let f = NaN; &f == &f } == false` even though ptr-equal
   maybe rewrite rules?
 - attributes to specify type class laws.. or first-class language feature? for fns in general, not just type classes
 - allow inferred type-wildcards (_) in `impl` method signatures?
 - `fn swap<T>(self: &Cell<T>, other: &mut T)`? (no Copy!)
 - `EXPR is PAT: bool` operator
 - currying: foo(1) if foo is a two-arg callable thing returns a one-arg callable thing (unboxed closure)
 - refutable patterns in for loops (obsoleted by `while let`!)
 - destructuring in assignments
 - array splicing [1, 2, ..arr] [..[1, 2, 3], 4, 5, ..[6, 7], 8, 9, ..[10]]
   can only splice fixed-length arrays into fixed-length arrays
 - early return from any block: return 's val? break 's val?
   default for `break` is innermost loop, not block. is that intuitive? for `return` is outermost block.. `'fn`
 - compacted enum & struct:
   would use most compact possible representation the compiler can devise
   i.e. sizeof should not usually be greater than log2(number of logical inhabitants)
   tradeoff: can't have references to interior of compacted enum/struct
   instead, when taking an &ref to field, unpack and copy it out onto stack first (like rvalues)
   for &mut ref, the same, then pack and copy it back afterwards!
   because of rigorous control over lifetimes, this should work
     also need to make sure copy-back happens during task failure?
   would remove need for manual bit twiddling whenever the goal is a compact, efficient representation
   such as flag bits, e.g.:
       #repr(compact)
       struct Flags { flag_a: bool, flag_b: bool, ... flag_h: bool }
       => sizeof(Flags) == 1
   could also take advantage of tag bits in pointers, i31, ... go crazy
   would not supplant manual bit twiddling if a _specific_ representation is required, e.g. for hardware interaction
   (but maybe allow specifying explicitly in #repr args?! would need to be pretty sophisticated...)
   http://nikic.github.io/2012/02/02/Pointer-magic-for-efficient-dynamic-value-representations.html
 - allow type inference of locally declared fns and statics?
 - deriving Functor, Contrafunctor, Bifunctor, Profunctor, .. ?
 - all built-in types just sugar for lang items
   nice for documentation & macros & general niceness
       #lang(const_ptr)  struct ConstPtr<T>
       #lang(mut_ptr)    struct MutPtr<T>
       #lang(shared_ref) struct Ref<'s, T>
       #lang(mut_ref)    struct MutRef<'s, T>
       #lang(array)      struct Array<static N: uint, T>
       #lang(str)        struct str<static N: uint> { data: [u8, ..N] }
       #lang(char)       struct char { data: u32 }
       #lang(bool)       enum bool { false, true }
       ...numeric types...
       what about `fn`? tuples?
 - let .. else ..
   - also important to enable e.g. let &mut [mut ref a, ..] = my_mut_arr else fail!();
 - ! as first class type (is just forall a. a)
 - disjunctive patterns in lets
 - anonymous sum types
 - DefaultSignatures
 - unsafe traits and and unsafe impls? (can break variant that isn't directly unsafe, but other thing relies on it for safety)
 - BIC? modular 'unsafe'? unsafe(memory), unsafe(array), unsafe(overflow), unsafe(rc_cycles), unsafe(concurrency)
   - would require mapping the dependencies
 - unsafe overlapping/incoherent impls, assumed confluent?


## Lazy<T>
- for any given function with a parameter Rust wants a version where it's a value, and one where it's a closure
- Haskell values are lazy, so it gets away with a single definition
- ...whereas these Rust versions would want to use once fns
- a lazy value only gets evaluated once
- blackholing ~ borrow checking? (RefCell)
- the FnOnce bound should only be necessary at construction!!
- in: FnOnce, out: FnMut

pub struct Lazy<F, T> {
    eval: fn(&mut Lazy<F, T>) -> &mut T,
    data: UnsafeUnion<F, T>
}

impl<F: Copy, T: Copy> Copy for Lazy<F, T> { }
impl<F: Send, T: Send> Send for Lazy<F, T> { }
what about Sync?
??? impl<F, T, U: Transmute<T>> Transmute<Lazy<F, U>> for Lazy<F, T> { }

pub fn lazy<T, F: FnOnce() -> T>(closure: F) -> Lazy<F, T> {
    Lazy {
        eval: eval_force::<T, F>,
        data: unsafe { transmute(closure) }
    }
}

pub fn eval<T>(self: &mut Lazy<T>) -> &mut T {
    (self.eval)()
}

?? pub fn eval_share<T, F: Fn() -> T>(self: &Lazy<F, T>) -> &T;

pub fn unwrap<T>(self: Lazy<T>) -> T {
    self.eval();
    unsafe { transmute(self.data) }
}

fn eval_force<T, F: FnOnce() -> T>(self: &mut Lazy<F, T>) {
    *self = Lazy {
        eval: eval_noop::<F, T>,
        data: unsafe { transmute(transmute::<_, F>(self.data)()) }
    };
    eval_noop(self)
}

fn eval_noop<F, T>(self: &mut Lazy<F, T>) -> &mut T {
    unsafe { transmute(&mut self.data) }
}

impl Functor, Applicative, Monad, Comonad

impl Fn{,Mut,Once}?
  return T: unwrap? Copy? Clone?
  return &mut T?
or impl Deref{,Mut,Move}?
  could impl `DerefMut`, but not `Deref`?!


QUESTION Lazy<F, T> or Lazy<T, F>?
 * implicit existential quantification
 * partial type application for Functor etc.
 This seems to suggest Lazy<F, T>...
 Should the Functor instance be forall F or exists F?
 ...certainly seems like exists would be correct!
 In that case, does partial type application still matter?
 Is there a relationship between p.t.a. and i.e.q.?

QUESTION when can we allow `eval()` through shared references?
  I think GHC's blackholing corresponds directly to RefCell, and <<loop>> to a borrow failure
  Can we avoid RefCell if we require Fn (pure) instead of FnOnce?

QUESTION (how) can we allow `eval()` in pure code?
  By requiring `Fn` instead of `FnOnce`
  Bifurcate into `Lazy` and `PureLazy`, or just require `Fn` at the `eval()` site (eval_share)?
  Can we have an existential of `Lazy` produced by `lazy_pure()` where we know it supports `Fn`, without duplicating everything, and without carrying runtime evidence?

QUESTION how can we `eval()` from multiple threads?
  By requiring Fn?
  By using some thread-safe version of RefCell? (look into how blackholing works!)

(last three questions are closely related)


## UnsafeUnion<A, B>
  sizeof(UnsafeUnion<A, B>) = max(sizeof(A), sizeof(B))
  alignof(UnsafeUnion<A, B>) = lcm(alignof(A), alignof(B))
  unsafe_transmute
    A -> UnsafeUnion<A, B>
    B -> UnsafeUnion<A, B>
    UnsafeUnion<A, B> -> A
    UnsafeUnion<A, B> -> B
  if {x, y}: UnsafeUnion<A, B>, *x = y is unsafe!! destructors don't run
     should it be a linear type??
  impl<A: Copy, B: Copy> Copy for UnsafeUnion<A, B>
  -- or just impl Copy for UnsafeUnion<A, B>?? or a disjunction??
  likewise Share, Send, etc.
  UnsafeUnion<_, _> is idempotent, commutative, associative
  so we can just define UnsafeUnion3<A, B, C> = UnsafeUnion<A, UnsafeUnion<B, C>>
    this is where constructor = transmute, instead of plain fn, would be important
  with type macros perhaps UnsafeUnion!(A, B, C, D)


## TYING THE KNOT

fn tie<T>(build: |Gc<T>| -> T) -> Gc<T>
{
    
}

struct Stream<T> { head: T, tail: Gc<Stream<T>> }

fn repeat<T>(val: T) -> Gc<Stream<T>>
{
    tie(|tail| Stream { head: val, tail: tail } /* tail not yet initialized here!! :( */)
}

use Box<Lazy<T>>? (Rc/Gc+RefCell?)

use a type-based HKT approach? 
instead of `Gc`, parameterize it, is one opaque type while constructing/tying, becomes Gc once knot is tied
feel like `&out` should be involved somewhere...

should `tie` be a trait method? recursive structures make sense for `Gc` but not `Box` or many others
could we provide one for `Rc` and automatically use `Weak` in the right places?


## Trait names

// Semigroup
trait Combine<T> {
    fn combine(a: T, b: T) -> T;
}

// Monoid
trait CombineWithUnit<T: Combine> { // ??
    fn unit() -> T;
}

// Semigroupoid
trait Compose<Cat> {
    fn compose<A, B, C>(a: Cat(A) -> B, b: Cat(B) -> C) -> Cat(A) -> C;
}

// Category
trait ComposeWithIdentity<Cat: Compose> { // ??
    fn identity<A>() -> Cat(A) -> A;
}

// Group? Groupoid?

// Functor
trait Map<F> { // Collect? // abstract over fn type?? e.g. `Option` would like `FnOnce`
    fn map<A, B>(a: F<A>, f: &Fn(A) -> B) -> F<B>;
}
// additional reason to avoid `Functor` name: different meaning in C++ & others

// Contrafunctor
trait ReverseMap<F> {
    fn reverse_map<A, B>(a: F<A>, f: &Fn(B) -> A) -> F<B>;
}

// InvFunctor, Bifunctor, Profunctor, Strong, Choice?

// Applicative
trait Apply<F: Map> { // Sequence? Map2? Multimap? ...
    fn wrap<A>(a: A) -> F<A>;
    fn unit() -> F<()>;
    fn map2<A, B, C>(a: F<A>, b: F<B>, f: &Fn(A, B) -> C) -> F<C>;
    fn pair<A, B>(p: (F<A>, F<B>)) -> F<(A, B)>; 
    fn apply<A, B>(f: F<&Fn(A) -> B>, a: F<A>) -> F<B>;
}

// Monad
trait Flatten<F: Apply> {
    fn flatten<T>(a: F<F<T>>) -> F<T>;
    fn and_then
}

// Comonad
trait Unflatten<F: Map> {
    fn unwrap<T>(a: F<T>) -> T;
    fn unflatten<T>(a: F<T>) -> F<F<T>>;
}

// Foldable
trait Fold<C> { // Summarize? Digest? Reduce? Process? Condense? 
    fn fold<A: CombineWithUnit>(a: C<A>) -> A;
    fn foldMap<A>(a: C<A>, map: &Cn(A) -> B, combine: &Cn(B, B) -> B) -> B;
}

// Traversable
trait Traverse<C: Map + Fold> { // ?? 
    fn sequence<T, F: Apply>(a: C<F<T>>) -> F<C<T>>;
    fn traverse
}

// use "transform" for something?


## Mass borrowing with Transmute

//impl<'s, T> Transmute<&'s R<&'s T>> for &'s R<Box<T>> { }
//impl<'s, T, type<covariant type> R> Transmute<&'s mut R<&'s mut T>> for &'s mut R<Box<T>> { }
//impl<'s, 't, T, type<covariant type> R> Transmute<&'s R<&'t T>> for &'s R<&'t mut T> { }

impl<'s, T, type<type> R> 
    where for<A, B: Transmute<A>> R<B>: Transmute<R<A>> 
    Transmute<&'s R<&'s T>> for &'s R<Box<T>> { }

class SkolemA;

class SkolemB { x: SkolemA }

impl Transmute<SkolemA> for SkolemB { }

impl<'s, T, type<type> R>
    where R<SkolemB>: Transmute<R<SkolemA>>
    Transmute<&'s R<&'s T>> for &'s R<Box<T>> { }

impl<'s, T, U: BorrowExtend<'s, T>, type<type> R>
    where R<SkolemB>: Transmute<R<SkolemA>>
    Transmute<&'s R<U>> for &'s R<T> { }


## MISC QUESTIONS
- static stack space analysis + tables-next-to-code?
  put stack space usage at a fixed offset next to fn body
  if you get an fn pointer, can take the offset and find out
  gets more interesting with HOFs
  instead of a uint, store an fn pointer which takes as arguments the fn args to the HOF,
  (or their stack usage, as uints), and calculates the stack usage of the HOF with those args?
    but this stack-usage-calculating-fn would itself use stack?! infinite regress?
    no: if it takes uints as args, then it's not a HOF itself
    and/or maybe static bound can be shown globally for all such space-calculating fns (probs only do basic arithmetic...)
  reminds me of type classes & dictionary passing... static polymorphism vs. dynamic
  also of recursion schemes (f-algebras, catamorphism)
    gets messier if the higher-order arguments aren't plain fns, but data structures of fns
    in that case the stack-calculator would take the same datastructure with all the fn nodes replaced by their stack usage
    this sounds highly nontrivial.
  - no runtime overhead when only calling statically known fns
  - strictly more expressive than "can only call static fns" formulation
  - no restrictions on expressiveness? would probs still have to ban recursion (except tail recursion?)
  - runtime overhead only where code would otherwise be illegal under only-static-calls
  is this any better than just doing a stack check in fn prologues?
- "optimize out" references to zero-sized structs?
  - can't literally make the references themselves zero-sized, but...
  - it's guaranteed that no actual data will ever be read from them
  - ditto for references to uninhabited types?
  - therefore they can just be treated as `undef`
  - moved to the end of function argument lists and not actually passed in
  - moved to the end of structs and not considered for `sizeof`?
  - is there anywhere this evilness is observable?
    - would anyone care if sizeof((A, B)) >= sizeof(A) + sizeof(B) breaks?
    - what about `ptr_eq`?
    - unsafe code transmuting the type there and back would expect the reference to stay valid
      - e.g. with pointers to opaque types in FFI
        - would they ever use `&mut Thing` or `&Thing`, or just `*Thing`?
        - probably would... ?
      - perhaps only do this for _either_ zero-sized or uninhabited references, but not both?
      - &Void and &mut Void are inherently unsound!
      - or more like: only for `data struct`s? (and `data enum`s?)
      - then I think we only have the `ptr_eq` problem
- can stack maps / stack tracing also be used for relocatable stacks? (why not?)
    have a map of all non-heap refs/pointers on the stack
    what about *T?!
    any of these which point to an address inside the stack are incremented with the offset to the new stack
- what should a not-fully-general Drop or Trace impl mean?
    A: not-covered types should have glue as normal, just not the impl
    B: a not-covered type is illegal
    given A, then B can be expressed with a smart constructor
      also allow trait bounds on struct typarams?
      only covers the case where Drop is restricted to a trait, not to a type (requires an (~) constraint)
      think this should be a separate feature
- is there any way to give a safe type signature to `alloca`, with e.g. &out?
  (obviously needs to be some kind of built-in intrinstic, can't be an actual function)
  (only makes sense for dynamic things, if you know the type/size at compile time you can just `let`)
  fn alloca<T>(n: uint) -> &out [T];
  fn alloca<ref T>() -> &out T;
  but lifetime needs to be tied to current stack frame somehow...
  and can _only_ work for the current stack frame/lifetime
  can't alloca into caller stack frames, and callee stack frames don't even exist
  so passing in the lifetime as a parameter cannot be part of the solution
  add a magical lifetime which always refers to the lifetime of the current scope?
  fn alloca<T>(n: uint) -> &'self out [T];
  but the `'self` lifetime of the caller isn't in scope at the type sig of `alloca`...
  maybe trying to write it as a normal fn type signature is a bad idea in the first place,
    & it should be a built-in operator instead... 
    like you can't write the type signatures of the `&` and `&mut` operators in the language itself either
  but then specifying the argument & return without overspecializing becomes the problem
  surely fixed-length arrays and `ref T` aren't the only meaningful possibilities
  what's the most general formulation? is there one? 
    is it actually `ref T`? does the fixed-length array case fit into it?
  so conceptually: `alloca: ref T -> &'self out T`?
  should this even be exposed as a separate "thing"?
  maybe the right thing to do is to just allow using `ref` types in `let`s (which would otherwise be strictly forbidden as not representable),
    and use alloca under the hood?
  ...would this actually allow removing all restrictions on use of `ref` types in fn bodies - and thus the need for `ref` itself???
  does this end up being intensional type analysis at the limit??? wouldn't be surprised...
- `let x = ...; let y = &move x; x = *y;` seems like it should be OK? saying "actually, don't destroy it after all"
    can this be shown safe in general?
  is there an analogue for `&out`?
  `let x; let y = &out x; ???`?
- how to relate `trait Foo<T>` + `impl<T> Foo<T> for My<T>` and `trait Foo for type<type> Self` + `impl Foo for My`?
    trait GBox for type<type> Self where for<T> Box<Self<T>> ???
    class forall a. Box (b a) => GBox b
- how to specify subtyping nicely?
  http://www.reddit.com/r/haskell/comments/1u9pbw/feedback_sought_a_typetheoretic_account_of/ceg4cos
- how to do TCE?
  TCE calls are always explicit
  if moves/drops are tracked statically, and TCE is explicit, those are no problem
    static error in case of conflict
  problem: calling conventions
    C convention: caller cleanup
    we need: callee cleanup
    QUESTION where do we need it?
        "The problem seems to be that you can't do tail calls with the C calling convention.
        For example, let's say a 0-argument function tail calls a 1-argument one: the 1-argument function expects an argument on the stack, so the 0-argument function must push one.
        However, when the 1-argument function returns, the argument will still be on the stack, because with the C calling convention the caller removes arguments from the stack.
        But the caller called a 0-argument function, so he won't remove any argument, and thus the stack is now misaligned due to the argument left over there, which will crash the program soon.
        However, just switching to the Pascal/stdcall convention, where the callee removes arguments from the stack should just work; it might be slightly slower, but on all modern architectures (i.e. those that aren't x86-32) parameters are going to be passed in registers anyway for must functions, so it shouldn't matter.
        The problem of that is that non-varags functions cannot be called with a varargs prototype; this is an issue with K&R C that allows calling undeclared functions, but isn't an issue with Rust.
        So, I'm not quite sure why Rust doesn't just switch calling conventions and support tail calls."
  solution:
    make a callee-cleanup wrapper around every fn?
    always at a fixed offset
       should always be 2 insns: call f; ret N;
    TCE calls take the offset before calling
    but it's the last call that needs to be caller-cleanup, not the first...?
    more precisely:
      f calls g, g tail-calls h, then:
      f (not g) needs to know that g will do TCE?
      h (not g) needs to know that g will do TCE?
  or alternately:
    don't actually do tail calls, just re-use own stack for arguments of callee
    not complete because return pointer is still added to stack
  what should the keyword be? go? in? out? tail? goto? self? use?
    "Tail calls can be made explicitly in Perl, with a variant of the "goto" statement that takes a function name: goto &NAME;"
      http://perldoc.perl.org/functions/goto.html
    interacts how with explicit/implicit return?
    `return` is always tail unless followed by drops?
- how to do variadic generics?
  C++ solution is too "big" and complex
  primary use case: abstracting over # of fn parameters
  but also need to 'splice', e.g. for `trait Fn`
  also would be nice: type c_union<type..>
  how might Applicative look?
  interaction with HKT?
    is a variadic parameter its own kind?
    interaction with type inference?
  is everything either a map or a fold? do we need explicit recursion?
    what contexts are maps, folds, splices allowed in?
  which parts of C++11 variadics does Rust need, which parts are handled in other ways, which parts are out of scope?
    do we only need it for types, or also non-types and HKTs?
  is providing variadic args implicit like C++, or explicit? e.g. c_union<[int, char]>
    have explicit syntax, allow sugar when it's unambiguous?
  but that's essentially tuples... would deconstructing, mapping, and splicing tuples be enough?
  USE CASES:
    trait Fn, FnMut, etc.
    typedefs for same
    c_union
    trait Applicative?
    variadic tuple structs
    StructF, EnumF, ComposeF?
- how to do higher-rank types?
  QML, HML, HMF, MLF, FPH, bidirectional, "Practical type inference..."
  HML < HMF < MLF
  others: ??
  "It's very easy to extend the system with annotations for polymorphic applications. However, this makes it more complicated to explain which program transformations preserve typability. Basically, you get to pick any two of: (a) impredicativity, (b) preservation of typability under eta, and (c) the usual type language of System F. We chose (b) and (c) in this paper, MLF picks (a) and (b), and HMF/FPH pick (a) and (c)."
- GeneralizedGeneralizedNewtypeDeriving? not just for newtypes, but any two Coercible types?
    impl the trait for tuples + anonymous sums -> newtype-derive it for representationally compatible types
  (doesn't work where the names of types, fields, and variants are relevant)
- are enums just existentially quantified somethings? (yes)


## "Interesting projects"

### Once Rust has `Trace` GC, implement a Haskell compiler/runtime piggybacking off of it?
Desugar Haskell to Rust?
  every type just becomes Gc<Lazy<T>>?? what about threads?
  what about currying?
Merely Haskell-like syntax for Rust, keeping Rust semantics?

### Mechanically translate C to Rust with *const T, *mut T, `unsafe`
problematic bits:
  goto
  switch with fallthrough?
next step: determine where * can safely be replaced with &... what other obvious things?

### Mechanically translate Rust to C
is there any point to this, given Rust has a C FFI?
wider portability

### C++ ABI compabitibility for Rust?
(only two major C++ ABIs: Itanium + MSVC)
modules <=> namespaces
built-in Rust types <=> C++ equivalents?
static polymorphism <=> templates
dynamic polymorphism <=> vtables, or structs-of-function-pointers
ADTs <=> tag-enum-plus-union, tagged_union<...>?

### a Rust-inspired typechecker plugin / semantic analysis for C++? i.e. a semantic "Safe C++" subset
make use of Rustic typesystem and "convention over configuration"-based inference for provably safe C++ code
any Safe C++ program is also a legal C++ program; reverse is not true
  ideally also: compiles to the same code, i.e. safe no matter what it is compiled with
  i.e. doesn't depend on automatically inserted runtime checks or similar, wholly compile-time
i.e. Safe C++ is a strict (semantic) subset of C++
any program accepted as Safe C++ is provably free of type/memory safety violations and UB, except where explicitly annotated otherwise
(other forms of correctness, e.g. nullability, "trait coherence", principal types, separate typechecking of generics, ... are most likely out of scope)
(expressiveness, elegance, convenience, performance ... are also not improved)
  complementary w/ Yt lib for these other aspects?
  cooperation with Yt: Yt has runtime checks, but can safely be disabled given Safe C++ static checks?
  define SAFE_CPLUSPLUS?
three "layers":
 1. attempt to infer as much currently existing actually-safe C++ code as possible as safe (might be feasible for only a limited amount of code)
 2. where 1. fails, make it possible to straightforwardly reformulate code such that it /can/ be inferred as safe
 3. where 2. is impossible, make use of explicit safe/unsafe boundaries (ala Rust `unsafe`)
ratio of safe-to-unsafe code will in all likelihood not be as good as Rust, but still a massive improvement over existing C++ where essentially 0% of code is safe
particular techniques:
 - types are propositions, etc. (assume provided values are valid; forbid constructing invalid values)
 - unsafe code is tasked w/ upholding usual C++ invariants (!UB), *and* Safe C++ invariants!
 - lifetime inference/elision for pointers and references
   - just like in Rust, incl. special handling of `this`
   - what corresponds to Rust's unsafe pointers? (actual C++ pointers, and only references are safe? a special unsafe pointer type?)
     - as opposed to Rust, an "unsafe block" just means "lift all static checks", rather than "permit invoking unsafe operations"?
     - i.e. normal pointers are both safe pointers outside "unsafe blocks", and unsafe pointers inside them
     - unlike Rust we don't optimize based on the invariants we are enforcing, so this should be OK
     - this doesn't really work? have a ptr field in a struct, which should be unsafe; should forbid accessing it from safe code
     - use either `unsafe` in name or attribute to track this, & require all variables it is copied to to also have the annotation?
     - how can we say that a function returns an unsafe pointer? :/
 - reinterpret `const` to mean deeply immutable
   - what's `Cell`? can we have "impl<T: Copy> Copy for &mut T"?
   - `const` in C++ is attached to the type, but maybe this is not a problem? (same cases exist as in Rust, + more, but don't care about those)
 - CFG for function bodies to track initialization states etc.
 - pointers are assumed to be nullable, references non-nullable
   - have a special analysis based on CFG for nullity of pointers: allow deref ptr inside if (ptr) { } block
   - to require/assume an argument non-null, use references
   - for non-null ptrs/refs in containers, make a `Ref` type
 - assume+require bools and enums only contain listed values
 - affine types: after invoking move constructor, further use of variable (before reinitialization) is an error
   - (how can we make sure copy/move constructors are safe? do we need any special handling here beyond usual safe/unsafe split?)
   - static drops or dynamic drops? (existing C++ destructors /should/ already impl dynamic drops...) (maybe an annotation?)
   - a type is affine if: it has a non-trivial destructor? move constructor?
   - mutable pointers/references are affine (likely to be painful? lots of stuff needs to become `const`... but most references already are)
 - do all analysis /after/ template expansion and overloading have been resolved!! (just like existing C++ checks!)
   - this should let us sidestep /all/ of the craziness around overloading and templates!
   - from our perspective, templates and overloading do not exist
   - work w/ the language, not against it
 - annotations via comments, attributes, and/or naming conventions
   - e.g. an `unsafe fn` is any function whose name begins with "unsafe"?
   - also for lifetimes? etc.
   - must have the approach that default inference is always most conservative, annotations required for greater liberalness?
   - are annotations sufficient, or do we need actual types?
 - HOFs: polymorphic over safety?
   - i.e. if you have an fn pointer as argument (you are a HOF), you may call it
   - but safe fns which call the HOF may only pass safe functions as arguments
   - virtual functions: require annotating the virtual fn decl with its safety! (default: safe), & overrides must obey the contract
   - likewise fn pointer members of structs
     - do safe/unsafe fn pointers need to be different types?? :(
     - to avoid the information being lost...
     - use either `unsafe` in name or an attribute to track this, & require all variables it is copied to to also have the annotation?
       - is this a sufficient condition??
       - are e.g. names/attributes of fn args something we can know about?
 - if necessary:
    - distribute own (header-only) library w/ custom "lang item" types which are known to the Safe C++ typechecker w/ magical properties
      - magical properties, or just the same annotations as elsewhere?
      - Ref<T>, MutRef<T>, Out<T>, ...
    - have own, compatible stdlib implementation w/ runtime checks; programs safe as long as it uses this `std`?
    - have wired-in knowledge of properties of things in stdlib? (is this possible in general, across different stdlib implementations?)
technical difficulties:
 - signed integer overflow UB
   - is it possible to make a wrapping-overflow integer type by casting to uint -> perform op -> cast back? (should be?)
 - division, shifts UB
   - same as above?
 - what other UB?
 - evaluation order?
   - can use CFG to forbid undefined orders?
 - strict aliasing? (i.e. type-based aliasing)
   - safe code restrictions should rule it out anyways, & in unsafe code it's not our concern?
 - exception safety?
   - just make *catching* exceptions unsafe, like Rust task failure? but what about interaction w/ unsafe code? (not our concern?)
 - subtyping?
 - lifetimes of temporaries?
 - how can we know whether user-defined types are nullable? should we?
 - how can we handle structs which /should/ have lifetime parameters?
 - how can we tell when a lifetime was intended to be 'static?
practical difficulties:
 - interoperation with existing code & libraries
 - which parts are safe & which unsafe?
 - chicken & egg problem: libraries unwilling to add Safe C++ support unless it is popular; Safe C++ popularity depends on library support
see also: 
 - http://homes.cs.washington.edu/~asampson/blog/quala.html
 - https://developer.chrome.com/native-client/reference/pnacl-undefined-behavior
 - 2*3 regehr.org & clang UB series
 - FAQ, FQA...

 
## Misc 

`Result` should have its type arguments flipped if it wants to be a Functor.

`Box` is going to become a library type, right?

Option -> Maybe, Optional, Nullable

Some/None -> Yes/No, Full/Empty, Val/Null

enum Maybe<T> {
    Yes(T),
    No
}

enum Maybe<T> {
    Full(T),
    Empty
}

enum Optional<T> {
    Full(T),
    Empty
}

enum Nullable<T> {
    Val(T),
    Null
}

enum BorrowOrBox<'a, T> {
    Borrow(&'a T),
    Box(Box<T>)
}

types you can use a statically fixed number of times (linear types = once, Rc = unbounded):

    enum Z;
    enum S<T>;

    struct Foo<N> { ... }

    fn do_thing_with<N>(foo: Foo<S<N>>) -> Foo<N>;

    fn do_last_thing_with(foo: Foo<Z>);

vReplicate :: (PI n :: Nat) -> x -> Vec n x
vReplicate Z     x = VNil
vReplicate (S n) x = VCons x (vReplicate n x)

vReplicate :: forall (n :: Nat). x -> Vec n x
vReplicate = case (reflect @ n) of
    Z x => VNil

reflect :: forall (n :: Nat). Nat

lens lib -> opticks, CT lib -> abstract-nonsense

groupoid      <-> equivalence relation
idempotence   <-> reflexivity
commutativity <-> symmetry
associativity <-> transitivity
what's the precise relationship here

https://github.com/idris-lang/Idris-dev/wiki/Copatterns
    codata Stream : Type -> Type where
        head : Stream a -> a
        tail : Stream a -> Stream a
        constructor (::) head tail

    map : (a -> b) -> Stream a -> Stream b
    head (map f s) = f (head s)
    tail (map f s) = map f (tail s)

    nats : Stream Nat
    head nats = Z
    tail nats = map S nats

trait Stream<T> {
    fn head(&Self<T>) -> T;
    fn tail(&Self<T>) -> &Stream<T>; // or -> Stream<T>?
}

fn map<A, B>(input: Box<Stream<A>>, f: Box<Fn(A) -> B>) -> Box<Stream<B>> {
    box Stream {
        head: f(s.head()),
        tail: s.tail().map(f)
    }
}

enum Nat { Z, S(Nat) } // Box?

fn nats() -> Box<Stream<Nat>> {
    box Stream {
        head: Z,
        tail: nats().map(S)
    }
}

also need Lazy to make this actually work... maybe Gc<Lazy<T>> or something everywhere to make it simpler

while let i@1..10 = i + 1 {
}


## No privates in public

Not OK:
    mod m {
        pub struct S;
    }
    pub fn f() -> m::S;

OK:
    mod m {
        pub struct S;
    }
    pub use m::S;
    pub fn f() -> S;

Not OK:
    struct S; 
    pub mod m { 
        pub fn f() -> super::S; 
    }

OK:
    pub struct S; 
    pub mod m { 
        pub fn f() -> super::S;
    }

Not OK:
    struct S; 
    mod m { 
        pub fn f() -> super::S; 
    } 
    pub use f = m::f;

OK:
    pub struct S; 
    mod m { 
        pub fn f() -> super::S; 
    } 
    pub use f = m::f;


## Things other languages get wrong which Rust does, or should, get right
 * Expression language
 * Nulls (Option)
 * Resource handling (RAII)
 * Generics, objects, closures (type classes, trait objects)
 * Modules
 * Privacy (no-privates-in-public, `abstract struct`)
 * Overflow
 * Exceptions
 * Inheritance
 * GC
 * Return type inference / voldemort types
 * Macros

Things we do better than Haskell:
 * Distinction between namespacing (modules) and compilation units (crates)
 * Recursive modules
 * Submodules
 * Declarative macros without stage restriction
 * Macro invocation syntax that doesn't suck
 * Attributes, incl. for conditional compilation
 * No orphan instances
 * Impl resolution considers constraints, not just head
 * No type inference at API level
 * Affine types, destructors, resource handling (obvious)
 * Exhaustive matching + irrefutable patterns
 * Zero-sized types!
 * Local mutable variables w/o ST gunk
 * Struct fields don't clash
 * Niceties:
    - Disjunctive patterns
    - `if let`
    - tuple fields (.0, .1, ...)
    - `return`, `break`, and `continue` of type `forall a. a`
 ? Overflow
 ? Privacy, abstract types
 ? Exceptions


## Things I wrote
TODO: sort them

`static fn`
http://www.reddit.com/r/rust/comments/2e76zs/rust_as_a_host_for_multilevel_languages_using/cjxdrd5

Linear types
http://www.reddit.com/r/rust/comments/2b02mb/rust_will_be_the_language_of_the_future/cj1sbcq
http://www.reddit.com/r/rust/comments/2b02mb/rust_will_be_the_language_of_the_future/cj8n5zf

Abstract over `&` and `&mut` via a built-in higher-kinded `Reference` trait
http://www.reddit.com/r/rust/comments/2a721y/a_safe_way_to_reuse_the_same_code_for_immutable/cj8pebl

Zero-sized tokens as evidence
http://www.reddit.com/r/rust/comments/1wvxcn/lazily_initialized_statics/cf61im5

Scoped attributes for checked arithmetic
https://github.com/rust-lang/rfcs/pull/146

Change `extern "ABI"` syntax
https://github.com/rust-lang/rfcs/pull/156

`abstract struct`, `abstract enum`
https://github.com/rust-lang/rfcs/pull/10

No privates in public
https://github.com/rust-lang/rfcs/pull/136

Enforce capitalization rules
https://github.com/rust-lang/rfcs/pull/154

`for` = forall
https://github.com/rust-lang/rfcs/pull/157

`Transmute` née `Coercible`
https://github.com/rust-lang/rust/issues/9912#issuecomment-36073562
https://github.com/rust-lang/rfcs/pull/91
https://github.com/rust-lang/rfcs/pull/91#discussion_r13057612
https://github.com/rust-lang/rfcs/pull/91#issuecomment-46834744
https://github.com/rust-lang/rfcs/pull/91#issuecomment-50234451

`MaybeOwned`, `CopyOnWrite` (-> `MaybeUnique`, `MakeUnique`)
https://github.com/rust-lang/rust/pull/11230#issuecomment-32708787

GC, `Trace`
https://github.com/rust-lang/rust/pull/11399#issuecomment-33124755
https://github.com/rust-lang/rust/pull/11399#issuecomment-33310724
https://github.com/rust-lang/rust/pull/11399#issuecomment-34439765
https://github.com/rust-lang/rust/pull/11399#issuecomment-33756578
https://github.com/rust-lang/rust/pull/11399#issuecomment-33930506

Unboxed trait objects
https://github.com/rust-lang/rust/issues/11455
https://github.com/rust-lang/rfcs/pull/105
https://github.com/rust-lang/rfcs/pull/105#issuecomment-45096279
https://github.com/rust-lang/rfcs/pull/105#issuecomment-47545719

Deterministic name resolution
https://github.com/rust-lang/rust/issues/11878

`&out`
https://github.com/rust-lang/rust/issues/10672#issuecomment-32342797
https://github.com/rust-lang/rfcs/pull/98
https://github.com/rust-lang/rfcs/pull/98#issuecomment-44788950
https://github.com/rust-lang/rfcs/pull/98#issuecomment-46036846
http://www.reddit.com/r/rust/comments/2b02mb/rust_will_be_the_language_of_the_future/cj94b1c

`UnsafeUnion`
https://github.com/rust-lang/rfcs/pull/197#issuecomment-52054190

Anonymous sum types
https://github.com/rust-lang/rust/issues/8277

Generalized destructing struct destructuring
https://github.com/rust-lang/rust/issues/11855

#compact `struct`, `enum`
https://github.com/rust-lang/rust/issues/12642

`impl<T: Copy> Copy for &mut T`
http://discuss.rust-lang.org/t/impl-t-copy-copy-for-mut-t/414

`swap` for `Cell`
http://discuss.rust-lang.org/t/a-swap-method-for-cell/392

Multiple mutable borrows from `Vec`
http://www.reddit.com/r/rust/comments/2fj07c/ml_family_workshop_2014_the_rust_language_and/ckbk368

On whether to have a type called `int`
http://discuss.rust-lang.org/t/if-int-has-the-wrong-size/454/18?u=glaebhoerl

How `box` should work
https://github.com/rust-lang/rfcs/issues/413

Rust vs. C+Haskell
http://www.reddit.com/r/rust/comments/2ll2of/c_and_haskell/clvsanj

The benefits of checked arithmetic
http://www.reddit.com/r/rust/comments/2nnpzg/rfc_scoped_attributes_for_checked_arithmetic_146/cmf8ajb

Closures, existentials, type classes, OOP
http://www.reddit.com/r/haskell/comments/2nqubp/record_equivalent_to_subclassed_member_variables/cmg3szc?context=3

C++'s `&&` is Rust's `&mut`
http://www.reddit.com/r/rust/comments/2oes6s/cs_rvalue_references_correspond_to_rusts_mut/

Undecidable type checking
http://www.reddit.com/r/rust/comments/2o6yp8/brainfck_in_rusts_type_system_aka_type_system_is/cmkuvbu

Kind syntax
http://www.reddit.com/r/programming/comments/2ny8c1/rust_generics_and_collections/cmiqhyx