The {pnk}f(eli)x Blog

The informal ramblings of an ex-pat PL enthusiast

An Insight Regarding DST Grammar for Rust

Executive summary: type = unsizedsized, so we should use type as our generalization marker, not unsized.

Background: Dynamically Sized Types (DST)

The Rust team has been discussing incorporating "dynamically-sized types" into the static semantics for Rust. Essentially the idea is to allow code to describe and name static types whose size is only known at Runtime. E.g. the integer vector [int, ..5] is known at compile time to have five elements, and is considered (statically) sized, while the vector [int] has unknown size at compile time, and so that type is called unsized.

There is a series of blog posts about dynamically sized types on niko's blog. So I will not dive into the details too much here

The main points are that the compiler wants to know whether a type is meant to always have a static size, or if it can potentially be unsized. In a language without type polymorphism, this might be easy to determine directly from the parsed type expression (such as in the vector examples I gave at the outset). But once you add polymorphism, things get a litle harder for the compiler.

Anyway, the plan drafted in Niko's "DST, Take 5" is to add an unsized keyword, and then use it as a marker to make certain spots more general than they are by default. The reasoning here is that in the common case, you want a type parameter to represent a sized type. (Since there are certain operations you cannot do with a value of an unsized type, such copying the value into some other location, the compiler needs to know its size statically so that it can allocate an appopriate amount of space for it.)

So under that scheme, to write type parameter of most general type, e.g. for a struct definition that ends with an unsized field, you need to write:

1
2
3
4
5
6
7
8
9
10
struct Named<unsized T> {
    name: ~str,
    payload: T
}

// Accepts solely sized Named<T>.
fn foo<T>(&Named<T>) { ... }

// Accepts both sized and unsized Named<T>
fn bar<unsized T>(&Named<T>) { ... }

That is, you need to use what I will call a "generalization" marker at the spot where you bind a type variable, to indicate that the domain of that type variable is more general than the common-case default of a sized type.

For defining a trait that can be implemented on any possible type, including unsized ones, you would need to use the unsized keyword somewhere there as well. "DST, Take 5" proposed trait Foo<unsized Self> : NormalBounds { ... } (or trait Foo : unsized + NormalBounds { ... }, but this is broken for various reasons). I had been suggesting unsized trait Foo : NormalBounds { ... }, which Niko rightly objected to (since it is not the trait that is unsized, but rather potentially its Self type). Over the Rust work week last week I suggested trait Foo for unsized : NormalBounds { … }, which I think is the first suggestion that Niko and myself could both stomach. (The reasoning behind the latter suggestion is that we write impl Trait for SelfType, so it makes sense to put the generalization marker into the same position, i.e. filling the placeholder in: Trait for _.)

The Insight: type is a better generalization marker

One of the concerns that Niko has pointed out to me is that it is easy to (mis)read unsized T as saying "T must be unsized". But that is not what it is saying; it is saying "T can be unsized"; you can still pass in a sized type for T.

I was reflecting on that this morning, and I realized something: The whole point of DST is to partition the type universe into (Sized ⊎ Unsized). So if you want this construct to be more self-documenting, the generalization marker should be using some name to describe that union (Sized ⊎ Unsized), rather than the name unsized.

But we already have a very appropriate name for that union: type!

So that started me thinking: Why don't we use type as our generalization marker? So the definition of bar in the example above would be written

1
fn bar<type T>(&Named<T>) { ... }
In fact, this can have a very simple explanation: If we keep the Sized trait bound, then you can just say that
1
fn foo<T>(args, ...){ ... }
desugars to
1
fn foo<type T:Sized>(args, ...) { ... }
and in general, any type variable formal binding <T:Bounds> desugars to <type T:Sized+Bounds>

I admit, when I first wrote this, I said "hmm, this looks a bit like C++, is that a problem?" But I'm coming to like it. The biggest problem I can foresee is that a developer might be confused about when they are suppposed to write foo<type T> versus foo<T>. But chances are that someone who does not understand the distinction will not suffer if they just guess the answer; if they over-generalize, either:

  • the code will compile successfully anyway, in which case there is no harm, except perhaps w.r.t. forward-compatibility of their library when they may have wished they had imposed the Sized bound, or

  • the compiler will flag a problem in their code, in which case hopefully our error messages will suggest to add a :Sized bound or to just not use type in the binding for T.

If they under-generalize, then they (or their library's clients) will discover the problem when they apply foo.

For the trait case, it is a little less obvious what to do. I think we could likewise write: trait Foo for type : NormalBounds for the maximally general case. trait Foo : NormalBounds would then desugar to trait Foo for type : Sized + NormalBounds

So the point is that you would only use the type keyword when you wanted to explicitly say "I am generalizing over all types, not just sized ones", and thus are opting into the additional constraints that that scenario presents.

This approach wouldn't be so palatable under earlier envisioned designs for DST where e.g. you were restricted to write explicitly unsized struct S { ... } for structs that could end up being unsized. But at this point I think we have collectively decided that such a restriction is unnecessary and undesired, so there is no worry that someone might end up having to write type struct S { ... }, which definitely looks nonsensical.

There is another potential advantage to this approach that I have not explored much yet: we could also add an Unsized trait bound, and allow people to write <type X:Unsized> for when they want to restrict X to unsized types alone. I am not sure whether this is actual value in this, but it does not seem absurd to put in a special case in the coherence checker to allow one to write impl<X:Sized> SomeTrait for X { ... } and impl<X:Unsized> SomeTrait for X { ... } in order to get full coverage of SomeTrait for all types.

Finally, another obvious (though obviously post Rust 1.0) direction that this approach suggests is that if we decide to add parameterization over constants, we can likewise use the const keyword in the spot where I have written the generalization marker type, e.g.

1
fn foo<const N:int>(nums: &[f64, ..N]) { ... }
(In this case const would not be a generalization marker but instead a kind marker, since it is changing the domain of the parameter from being that of a type to being some value within a type.)

Examples ported from DST, Take 5

Here are the ported definitions of Rc and RcData. (Update: had to turn off syntax highlighting to work-around a rendering bug on *.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct Rc<type T> {
    ptr: *RcData<T>,
    // (a dummy field, just for illustrative purposes)
    dummy: uint,
}

struct RcData<type T> {
    ref_count: uint,

    #[max_alignment]
    data: T
}

impl<type T> Drop for Rc<T> {
    fn drop<'a>(&'a mut self) {
        unsafe {
            intrinsics::drop(&mut (*self.ptr).data);
            libc::free(self.ptr);
        }
    }
}

Here is the ImmDeref example:

1
2
3
4
5
6
7
8
9
10
11
trait ImmDeref<type T> {
    fn deref<'a>(&'a self) -> &'a T;
}

impl<type T> ImmDeref<T> for Rc<T> {
    fn deref<'a>(&'a self) -> &'a T {
        unsafe {
            &(*self.ptr).data
        }
    }
}

(I think I need a wider variety of examples, but this is good enough for now.)

Updating Octopress post-Mavericks Upgrade.

I decided this morning to write a blog post related to Rust. I have not posted to this blog in months, and in the meantime I had upgraded this computer at home to Mac OS X Mavericks (10.9.2).

So of course my existing set of commands for Octopress workflow did not work.

At first there were dependencies like chunky_png-1.2.7 that had to be satisfied (re-installed, I assume; I am pretty sure I blew away my previous Homebrew setup during the upgrade; I do not know how much that overlaps with Ruby's package management system).

The few step was just blind following of the suggestions made by my tools: rake suggests to run bundle install, and I comply. And the results seem promising:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
% rake generate
Could not find chunky_png-1.2.7 in any of the sources
Run `bundle install` to install missing gems.
% bundle install
Fetching gem metadata from http://rubygems.org/.......
Fetching gem metadata from http://rubygems.org/..
Using rake (0.9.6)
Using RedCloth (4.2.9)
Installing chunky_png (1.2.7)
Using fast-stemmer (1.0.2)
Using classifier (1.3.3)
Using fssm (0.2.10)
Installing sass (3.2.5)
Using compass (0.12.2)
Using directory_watcher (1.4.1)
Installing haml (3.1.8)
Installing kramdown (0.13.8)
Installing liquid (2.3.0)
Using syntax (1.0.0)
Using maruku (0.6.1)
Using posix-spawn (0.3.6)
Using yajl-ruby (1.1.0)
Installing pygments.rb (0.3.7)
Installing jekyll (0.12.0)
Installing rack (1.4.5)
Installing rack-protection (1.3.2)
Using rb-fsevent (0.9.3)
Using rdiscount (1.6.8)
Using redcarpet (2.2.2)
Using rubypants (0.2.0)
Installing tilt (1.3.3)
Installing sinatra (1.3.4)
Installing stringex (1.4.0)
Using bundler (1.3.5)
Your bundle is complete!
Use `bundle show [gemname]` to see where a bundled gem is installed.

But I balked on the second step:

1
2
3
4
5
6
7
% rake generate
rake aborted!
You have already activated rake 10.1.0, but your Gemfile requires rake 0.9.6. Using bundle exec may solve this.
/Users/pnkfelix/Dev/Sites/pnkfx-blog/Rakefile:2:in `<top (required)>'
(See full trace by running task with --trace)
% bundle exec
bundler: exec needs a command to run

I did not understand what bundle exec meant here, so I did not do the "obvious thing", which apparently is to re-run generate but within bundle, like so: % bundle exec rake generate

Instead I fumbled around trying to figure out what my situation was with respect to rake: do I need to downgrade to a previous version? Or do I need to upgraade its subcomponents, and/or my whole site configuration?

The first things I learned from a couple web interactions:

From stackoverflow I learned:

  • You can find out what version(s) of a gem you have install, with the relatively obvious gem list command:

    1
    2
    3
    4
    5
    
    % gem list rake
    
    *** LOCAL GEMS ***
    
    rake (10.1.0, 0.9.6)
    

  • You can also remove particular versions of a gem, with the gem uninstall command:

    1
    2
    3
    4
    5
    6
    7
    8
    
    % gem uninstall rake
    
    Select gem to uninstall:
     1. rake-0.9.6
     2. rake-10.1.0
     3. All versions
    > 1
    Successfully uninstalled rake-0.9.6
    

But these facts and this process did not actually help, because I still needed rake-0.9.6 for my site configuration, for some reason I have not yet determined (mostly due to lack of trying).

I then did some more guessing and followed some false paths, like reinstalling the bundler gem, uninstalling and reinstalling rake (which effectively led to me replacing rake-10.1.0 with rake-10.1.1).

At some point I ran this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
% bundle update rake
Fetching gem metadata from http://rubygems.org/........
Fetching gem metadata from http://rubygems.org/..
Resolving dependencies...
Installing rake (0.9.6)
Using RedCloth (4.2.9)
Using chunky_png (1.2.7)
Using fast-stemmer (1.0.2)
Using classifier (1.3.3)
Using fssm (0.2.10)
Using sass (3.2.5)
Using compass (0.12.2)
Using directory_watcher (1.4.1)
Using haml (3.1.8)
Using kramdown (0.13.8)
Using liquid (2.3.0)
Using syntax (1.0.0)
Using maruku (0.6.1)
Using posix-spawn (0.3.6)
Using yajl-ruby (1.1.0)
Using pygments.rb (0.3.7)
Using jekyll (0.12.0)
Using rack (1.4.5)
Using rack-protection (1.3.2)
Using rb-fsevent (0.9.3)
Using rdiscount (1.6.8)
Using redcarpet (2.2.2)
Using rubypants (0.2.0)
Using tilt (1.3.3)
Using sinatra (1.3.4)
Using stringex (1.4.0)
Using bundler (1.3.5)
Your bundle is updated!
but I still got the error:
1
2
3
4
5
% rake generate
rake aborted!
You have already activated rake 10.1.1, but your Gemfile requires rake 0.9.6. Using bundle exec may solve this.
/Users/pnkfelix/Dev/Sites/pnkfx-blog/Rakefile:2:in `<top (required)>'
(See full trace by running task with --trace)
and this is when I finally saw that I had to do:
1
% bundle exec rake generate

Except that this did not solve everything:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
% bundle exec rake generate
## Generating Site with Jekyll
unchanged sass/screen.scss
Configuration from /Users/pnkfelix/Dev/Sites/pnkfx-blog/_config.yml
Building site: source -> public
YAML Exception reading 2013-04-12-better-command-completion-in-bash-aka-resolving-zsh-envy.markdown: invalid byte sequence in US-ASCII
/Users/pnkfelix/Dev/Sites/pnkfx-blog/plugins/backtick_code_block.rb:13:in `gsub': invalid byte sequence in US-ASCII (ArgumentError)
  from /Users/pnkfelix/Dev/Sites/pnkfx-blog/plugins/backtick_code_block.rb:13:in `render_code_block&#39;
  from /Users/pnkfelix/Dev/Sites/pnkfx-blog/plugins/octopress_filters.rb:12:in `pre_filter'
  from /Users/pnkfelix/Dev/Sites/pnkfx-blog/plugins/octopress_filters.rb:28:in `pre_render'
  from /Users/pnkfelix/Dev/Sites/pnkfx-blog/plugins/post_filters.rb:112:in `block in pre_render'
  from /Users/pnkfelix/Dev/Sites/pnkfx-blog/plugins/post_filters.rb:111:in `each'
  from /Users/pnkfelix/Dev/Sites/pnkfx-blog/plugins/post_filters.rb:111:in `pre_render'
  from /Users/pnkfelix/Dev/Sites/pnkfx-blog/plugins/post_filters.rb:166:in `do_layout'
  from /Users/pnkfelix/.rbenv/versions/1.9.3-p194/lib/ruby/gems/1.9.1/gems/jekyll-0.12.0/lib/jekyll/post.rb:195:in `render'
  from /Users/pnkfelix/.rbenv/versions/1.9.3-p194/lib/ruby/gems/1.9.1/gems/jekyll-0.12.0/lib/jekyll/site.rb:200:in `block in render'
  from /Users/pnkfelix/.rbenv/versions/1.9.3-p194/lib/ruby/gems/1.9.1/gems/jekyll-0.12.0/lib/jekyll/site.rb:199:in `each'
  from /Users/pnkfelix/.rbenv/versions/1.9.3-p194/lib/ruby/gems/1.9.1/gems/jekyll-0.12.0/lib/jekyll/site.rb:199:in `render'
  from /Users/pnkfelix/.rbenv/versions/1.9.3-p194/lib/ruby/gems/1.9.1/gems/jekyll-0.12.0/lib/jekyll/site.rb:41:in `process'
  from /Users/pnkfelix/.rbenv/versions/1.9.3-p194/lib/ruby/gems/1.9.1/gems/jekyll-0.12.0/bin/jekyll:264:in `<top (required)>'
  from /Users/pnkfelix/.rbenv/versions/1.9.3-p194/bin/jekyll:23:in `load'
  from /Users/pnkfelix/.rbenv/versions/1.9.3-p194/bin/jekyll:23:in `<main>'

Another web search brought me to a post by a fellow Mavericks user who seems to have a similar attitude to my own about ruby development. And from that I found the full command I needed

1
2
3
4
5
6
% LANG=en_US.utf-8 bundle exec rake generate
## Generating Site with Jekyll
unchanged sass/screen.scss
Configuration from /Users/pnkfelix/Dev/Sites/pnkfx-blog/_config.yml
Building site: source -> public
Successfully generated site: source -> public

And here we are!

Detective Work on Rust Closures

I have recently been trying to keep myself abreast of a flurry of discussion about reforming the design of Rust closures. Niko has a series of blog posts (1, 2, 3, 4, 5, 6, 7, 8); the content of some of those posts were further discussed at Rust team meetings (11, 12, 13, 14, 15, 16), and there have been some more formalized proposals with their own set of discussions: (9, 10).

There are also associated github issues (17, 18, 19), though without sufficient context the discussion in the github issues may not always be intelligible.

Some of the links above are more about "Dynamically Sized Types" (DST), a related topic, as we shall see.

This post is my attempt to condense all of this information down into something where I can see all the pieces at once, and discard the red herrings along the way.

Background: Closures (recurring and otherwise)

In Rust circa version 0.6, closures have three categories according to the type system (&fn, @fn, and ~fn), but as Niko describes, they can be divided into two kinds: by-reference closures and copying closures. By-reference closures are also referred to as stack-allocated closures or sometimes "stack closure." (There is also a orthogonal division of once closures, versus closures that can be invoked more than once; some of these things are, to my knowledge, only part of planned future implementation. Niko discusses them in the blog posts but I'm mostly sidestep them here.)

As Niko states in the first paragraph of 1, a stack closure is allocated on the stack, and can refer to and manipulate the local variables of the enclosing stack frame (by reference).

In Rust (as of version 0.6), one creates a stack-allocated closure by writing an expression |x ...| { ... } within an expression context dictating that it wants a closure of &fn type. Analogously, a closure allocated on the exchange-heap is expressed by putting the expression into a context of ~fn type, et cetera. Since a stack-allocated closure is currently expressed solely by use of &fn type, Niko often uses the term &fn closure synonymously with stack-allocated closure.

(However, Niko also points out (first section of "Procedures, Continued") that one can borrow a @fn or ~fn to a &fn, so the type does not tell you whether you actually have a by-reference or a copying-closure.)

Here is the example of an unsound function that Niko described in his Case of the Recurring Closure post from 2013-04-30, making use of higher-order functions to express a fixed-point combinator:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct R<'self> {
    // This struct is needed to create the
    // otherwise infinite type of a fn that
    // accepts itself as argument:
    c: &'self fn(&R)
}

fn innocent_looking_victim() {
    let mut vec = ~[1, 2, 3];
    conspirator(|f| {
        if vec.len() < 100 {
            vec.push(4);
            for vec.each |i| {
                f.c(&f)
            }
        }
    })
}

fn conspirator(f: &fn(&R)) {
    let r = R {c: f};
    f(&r)
}

As Niko explains, the vector vec is mutated while being traversed by an iterator; this is illegal. The closure |f| { ... } captures a reference to vec, and Rust's borrow checker is not treating the argument f as a potential source of aliases to vec, even though it does alias vec because f ends up being bound to the closure |f| { ... }.

An important detail here is that the closure in question is a stack-allocated closure.

Niko has described his solution to this problem in 1; it would entail adding some new rules about how &fn closures are invoked and passed as parameters. One of the main changes imposed by his solution was that &fn closures would become non-aliasable; this would ensure that one could not express the Y-combinator. The restriction to ensure &fn closures are unaliasable interacts with other proposals, as we shall see. (Note that Rust does have a way of expressing a non-aliasable pointer to T for any T: &mut T.)

Background: DST

The heart of the Dynamically Sized Types proposal is the discrepancy described in Niko's DST, Revisited post from 2013-04-30 (published contemporaneously with Case of the Recurring Closure). Niko has been wrestling with the idea for a while, as one can see on his posts from 2012-04-23 and 2012-04-27.

In Rust, vectors (and strings, which we will treat as a special case of vectors) come in the following forms:

  • dynamic-length: heap-allocated, carries its length N as part of its record structure. Consists of some amount of meta-data, including the length word, followed by the inline-allocated array of N elements. Expressed as ~[T] and @[T] in Rust.
  • slice: represents a substring of a vector; consists of two words: a pointer to the payload, and a length bound. Expressed as &[T] in Rust.
  • fixed-length: represents exactly N elements, where N is statically tracked at compile-time. Consists of just the array of elements, T[N], and nothing more. Expressed as [T, ..N] in Rust.

Niko points out that a slice's two-word representation is quite different from the representations of the other variants. His proposal is to unify the first two representations, by laying out ~[T] and @[T] as pairs of words (a pointer to the boxed elements array, and a length). (Niko claimed that this makes a ~[T] and @[T] valid slices, "apart from the box header"; it seems to me like the box header is quite relevant here, unless the idea is that when you coerce a @[T] to a slice, you increment the pointer value accordingly…)

Then, Niko classifies the types of Rust into two categories: Sized and Unsized; i.e., size is statically known, versus size is tracked at runtime (maybe the letters S and R would have been more appropriate than S and U…). The "unsized types" cannot themselves be assigned as types of local variables, and you cannot have vectors of elements of unsized type; this all stems from the fact that "unsized types" do not have a static size. (The "unsized types" are arguably not actually types; we might be well-served by referring to them as "pretypes" or something). But pointers to unsized types are valid types. Such pointers are the pairs of words discussed above, aka "fat pointers": (payload, meta), where payload is the pointer to the data, and meta is the descriptor that includes some way to determine the size of the payload (to support runtime bounds checks).

The fact that "unsized types" need to be treated specially leads to a complication, discussed further in the post; how to differentiate between type-parameterized code that works on both kinds of types, versus typed-parameterized code that solely operates on sized types. The method proposed in the post is to express the distinction via a trait bound: the Sized bound would restrict the type parameter to one of statically-known size; you would not be able to express types like [X, ..3] (a fixed-length vector of 3 X'es), unless you include the bound X:Sized. (There is more on this restriction and ways to ease it further down.)

One of the benefits of DST that Niko proposes early on is that Traits and closures are other instances of unsized types, so that Rust's type hierarchy could be presented uniformly like so:

1
2
3
4
5
6
7
8
9
10
11
12
T = S            // sized types
  | U            // unsized types
S = &'r T        // region ptr
  | @T           // managed ptr
  | ~T           // unique ptr
  | [S, ..N]     // fixed-length array
  | uint         // scalars
  | ...
U = [S]          // vectors
  | str          // string
  | Trait        // existential ("exists S:Trait.S")
  | fn(S*) -> S
(Note that the actual types assigned to expressions would be instances of S according to this grammar.)

The Problem: DST and Closures

So, from the "Case of the Recurring Closure", we saw that &fn closures were to become non-copyable. But under the DST proposal, generic code should be able to treat &T the same for all T, including when T is some fn(S*) -> S. These two criteria are not compatible; Niko has lots more explanation in his corresponding post: "Recurring Closures and Dynamically Sized Types", from 2013-05-13.

Niko's immediate proposals to resolve this were either:

  • we write &mut fn instead of &fn. &mut T for all T (including fn (S ...) -> S) is forced to be unaliasable by the borrow-checker, and so the hole goes away, or,
  • we change notation, and move the sigils for closures after the fn, side-stepping the special treatment of &fn versus &T by getting rid of &fn and replacing it with fn&.

Is fn~ too ugly?

Niko at first favored the latter, then he wrote a second post, "Mutable Fn Alternatives" on 2013-05-13, which reconsidered whether fn~ is too ugly, and included new survey of the options:

  • Maybe &mut fn is not that bad, or
  • Maybe make all closures borrowed (i.e. stack-allocated), removing the need for any sigil, or
  • Make fn denote stack-allocated closures, and replace fn~ with a new keyword, like proc. (This is a variation on the previous bullet.)

For the second and third bullets, the main point is: If you need to capture state in a manner that cannot be expressed via the available options (stack-allocated closure, or a proc, if present), then you have to use an trait instead (i.e. an object or a record). (I personally am not thrilled about losing the option of using closures to express combinator libraries, a use case for fn@.)

Leveraging a proc keyword/expression

Then a third post, "Procedures, Continued" from 2013-05-15, refined the proc proposal a bit further. As stated in the background on closures, Rust has by-reference closures and copying closures; the choice of which variant to construct is based on the type expected by the context of the |x ...| { ... } expression. In this post, Niko proposed that the distinction here deserves a starker line between the two forms. (In that post, he proposed both a revision to English jargon and also to the Rust syntax; I'm going to focus solely on the Rust syntax changes, and let those guide the changes to my own jargon here.)

So Niko proposes distinguishing a by-reference closure from a copying closure via keywords. A stack-allocated closure would be constructed solely via fn, and a copying closure would be constructed solely via proc. While discussing this proposal henceforth, I will refer to a by-reference closure as an fn-closure and a copying closure as a proc-closure.

The type hierarchy that Niko then provides for this is:

1
2
3
4
5
6
7
8
9
10
11
12
13
T = S               // sized types
  | U               // unsized types
S = fn(S) -> S     // closures ()
  | &'r T           // region ptr
  | @T              // managed ptr
  | ~T              // unique ptr
  | [S, ..N]        // fixed-length array
  | uint            // scalars
  | ...
U = [S]             // vectors
  | str             // string
  | Trait           // existential ("exists S:Trait.S")
  | proc(S) -> S   // procedures ()

Now, fn-closures are considered sized types, because they are always represented by two words: a (borrowed) environment pointer (to the stack in Niko's proposal, though perhaps it could be generalized to point elsewhere) and a function pointer. proc-closures are unsized types, because their copied lexical environment is of some dynamically-determined size that they must carry in their record structure.

In this version of the proposal, proc can now be allocated to either the exchange heap (~proc) or the task heap (@proc). So this brings back the ability to express combinator libraries.

Niko's post provides further detail, such as dissection of the fn and proc closure types (which include important details like the lifetime and trait bounds for the closed-over variables; this is important since with a separate keyword, it is now reasonable for different defaults to be chosen for two cases; useful for making the common case succinct). He also describes a couple variations on the theme, including modeling proc closures via traits (i.e. boxed traits are objects carrying virtual method dispatch tables), and then expressing them via a proc! macro (which means they could be left out of the core language).

Other ways to express proc

In his next post, "Removing Procs", Niko elaborates further on the idea that proc need not be supported in the language at all. Stack-allocated fn-closures would remain, expressed via fn(S ...) -> T, and the language already supports raw (environment-less) function pointers via extern "ABI" fn(S ...) -> T. Niko points out two ways to re-express copying closures:

  1. One could pass around function pointers along with records that carry the captured environment; this is basically lambda-lifting (the variant that turns the free variables into fields of a single environment structure, rather than passing each variable as a separate parameter), or
  2. As stated earlier, (boxed) traits can used to express copying closures.

Niko surveyed how these patterns would look in his post, by considered existing use cases of @fn and ~fn in the standard libraries, namely task spawning and futures. Without more language support, the lambda-lifting transformation requires that one list the captures variables (at least once, though further repetitions can be avoided via appropriate macro definitions). I am personally hesistant to approve of removing non stack-allocated closures wholesale, though if it turns out that capture clauses are essentially unavoidable (or if understanding behavior without them is unworkable), then my main problem with the proc! macros (the explicit list of free variables) would go away.

Alternatively, if the macro system were somehow extended to allow a macro to query an expression for its free variables, then that might help.

A Personal Digression on Macros

Actually, this latter idea brings up a problem with the explicit list of captured variables that I had not thought of before: some macros may intentionally inject references to free variables, where the injected free variables are not meant to be part of the public interface of the macro (i.e., the macro is enforcing some protocol of usage, and the variable is meant to be otherwise private to the module where the macro is defined). I know we do not currently have macros exported from modules, but I thought it was supposed to be part of the long term plans for Rust.

  • Do we intend to disallow the use of such macros within copying closures?

  • Will we require the modules to expose those variable names, solely so that they can be included on the lists of free variables?

  • Or, if a macro could query an expression for its free variables (where even module-private identifiers might be included on such a list), that might help impose a usage discipline that would support a proc! macro,

  • Or, this whole example might serve as an argument for keeping copying closures as a primitive linguistic construct.

Okay, end of digression.

More followups on procs and fns

A few days passed, then Niko had a fourth post, "More on Fns", from 2013-06-03. This proposal renamed of a proposed Task trait to Thunk, since Niko felt that the concept at hand (an encapsulated function and the parameters it needs) is better reflected by that name.

More importantly, given the immediately preceding digression, the form thunk { ... } would automatically determine the captured variables instead of requiring an explicit list; this sidesteps the whole question of how to handle macros that inject new free variable references.

There is then much discussion of whether or not to support once fns, which I won't summarize here. The important detail of the post is that we do not necessarily have to list the captured variables explicitly.

After a few more days, Niko had a followup on the related topic of dynamically sized types (DST), "Reducing DST Annotation", from 2013-06-06. It took into account an investigation by Ben Blum on the implications of a Sized trait bound. This led to Niko exploring some alternatives to adopting DST with a Sized bound:

  • Abandon DST altogether: Niko summarizes what DST still buys us, but also points out where it does not live up to its original promises.
  • Make type parameters default to Sized, and adopt a different syntactic mechanism to distinguish Sized from Unsized (such as a keyword).
  • Use some sort of inference: the type-checker can use properties of a function's parameter list to provide feedback on whether the type parameter has an implicit Sized bound. (Niko wonders if this approach is too clever; I am inclined to affirm that it is.)

So where are we?

The above summarizes the series of blog posts from Niko. I had hoped to get through the actual proposals (and maybe also the team meeting notes), but at this point, it is late enough in the day and this post is long enough that I think I will stop here.

The language is young, and I am a Rust novice. So, grains of salt for everyone:

  • My intuition is that we should leave in copying closures in some form.
  • The thunk { ... } expression might suffice, but … I am not yet convinced that I would be satisfied using boxed traits to express the cases that need input arguments (like combinator libraries).
  • I am not thrilled by the idea of writing out lists of free variables. Of course, this is a systems programming language, and such a list may simply be the simplest way to accomplish certain goals (e.g. to indicate whether a referenced value is moved or copied).
  • If we do require a list of free variables in our copying proc/thunk/etc, please ensure that the question of free variables injected by macro invocations is addressed.

Designing Syntax for Associated Items in Rust

Executive summary: if you don't want or need the background information or the discussion motivating the proposal, then just jump straight to the proposal itself.

Background

Early in my experimentation with Rust, I thought a reasonable exercise would be to take the simple C++ programs from Elements of Programming (Stepanov and McJones), which make heavy yet disciplined use of abstraction and C++ templates to encode various mathematical concepts. The early chapters of the book use templates rather than classes as the means of code reuse, so translating those examples seemed like a good way to exercise Rust's generic type and trait systems.

However, almost immediately after starting the experiment, I encountered a problem: code that makes heavy use of C++ templates is quite likely to use particular features of C++ templates that are not a universal part of another language's generic type system.

In particular, the code from Elements of Programming (hereby abbreviated "EOP" in this post) almost immediately makes use of "associated types", such as in the following definition for distance:

1
2
3
4
5
6
7
8
9
10
11
12
13
template<typename F>
    requires(Transformation(F))
DistanceType(F) distance(Domain(F) x, Domain(F) y, F f)
{
    // Precondition: $y$ is reachable from $x$ under $f$
    typedef DistanceType(F) N;
    N n(0);
    while (x != y) {
        x = f(x);
        n = n + N(1);
    }
    return n;
}

The interesting thing about the above code is that it is parameterized over one type: F, but it uses other type expressions within the body of the procedure, namely:

  • Domain(F): this is a type -> type operator that, given a Transformation (which we can think of as some type classifying a set of T -> T functions for some type T), returns T.

  • DistanceType(F): this is a type -> type operator that, given a Transformation, returns a numeric type (think uint8_t, uint32_t, uintptr_t, BigNum, etc) suitable for counting the minimum number of applications of the transformation necessary to get from any particular T value to some other T value.

(Operators like DistanceType, to my mind, only makes sense when you look at things simultaneously in terms of bytes of memory in the machine and also in terms of pure abstract mathematical values. If you omit either perspective, then the operator appears either pointless or nonsensical.)

It also requires that F obeys a constraint, specified in the requires clause; I am going to conveniently ignore this detail for now. (The C++ code for EOP even macro-expands requires(..) into whitespace, so treating them as helpful comments for the time being is not absurd.)

Type expressions like triple<A, B, C> (assuming three type expressions A, B, and C), are the bread-and-butter of any generic type system. But these type -> type operators are interesting. How are they implemented? Here is a snippet from type_functions.h in the EOP source code distribution:

1
2
3
4
5
6
7
8
9
10
11
template<typename F>
    requires(Transformation(F))
struct distance_type;

// If all transformations on a type T have the same distance type,
// then DistanceType(T) is defined and returns that type.

// For any fixed-size type T, there is an integral type of the same
// size that is a valid distance type for T.

#define DistanceType(T) typename distance_type< T >::type

This code is making use of a C-style macro to define a easy-to-read interface for the DistanceType operator (the subset of C++ used for EOP's textbook examples is meant to be LL(1)), but the implementation of the operator is using C++'s template system to define a partial mapping from types to (integral) types. One can add new entries to this mapping by defining a new template instantiation of struct distance_type<F>, as illustrated in tests.h for the following transformation gen_orbit:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
template<typename I, typename N>
    requires(Integer(I) && Integer(N) && DistanceType(I) = N)
struct gen_orbit // transformation
{
    gen_orbit_predicate<I, N> p;
    gen_orbit(I x_0, N h, N c) : p(x_0, h, c)
    {
        // Precondition: h < N(MaximumValue(I)) && c < N(MaximumValue(I))
        // Precondition: !negative(h) && !negative(c)
    }
    I operator() (I x)
    {
        Assert(p(x));
        x = successor(x);
        if (x == p.x_0 + I(p.h) + I(p.c)) x = p.x_0 + I(p.h);
        return x;
    }
};

template<typename I, typename N>
    requires(Integer(I) && Integer(N) && DistanceType(I) = N)
struct distance_type< gen_orbit<I, N> >
{
    typedef N type;
};

Thus, the definition of gen_orbit (including its instantiation of distance_type) collaborates with the definition of DistanceType to indicate that DistanceType(gen_orbit<I, N>) is N. As one adds new structs (classes) representing other transformations, one is expected to instantiate distance_type (as well as a host of other template-abstracted structs) accordingly.


So, what's the problem here? Well, Rust, much like Java, does not provide a way to define general type -> type mappings like DistanceType(F).

One can try to work around this via a code transformation and lift any type of interest up to a generic class's parameter list, like this example in Rust:

1
2
3
trait Transformation<DISTANCETYPE, DOMAIN> {
    fn apply(&self, elem: DOMAIN) -> DOMAIN;
}
or if you prefer Java:
1
2
3
interface Transformation<DISTANCETYPE, DOMAIN> {
    DOMAIN apply(DOMAIN elem);
}

At first glance, one might think this does not look so bad; after all, the gen_orbit struct similarly was parameterized over a domain I and a distance type N. However, the problem comes when one then attempts to write a function like distance:

Rust:

1
2
3
fn distance<F: Transformation<DT, DOM> >(x: ???, y: ???, f: F) -> ??? {
    /* ... */
}

Java:

1
2
3
public static <F extends Transformation<DT, DOM> ??? distance(??? x, ??? y, F f) {
    /* ... */
}

What do we put in for the ??? portions? We already established that we do not have general type -> type operators, so we cannot just derive it form F. And for that matter, where did DT and DOM come from? In Rust and Java, we cannot just make up fresh type variables and then add constraints upon them after the fact. The only option is to make any type we wish to use an additional type parameter to the generic method.

Rust:

1
2
3
fn distance<DT, DOM, F: Transformation<DT, DOM> >(x: DOM, y: DOM, f: F) -> DT {
    /* ... */
}

Java:

1
2
3
4
public static <DT, DOM, F extends Transformation<DT, DOM> >
    DT distance(DOM x, DOM y, F f) {
    /* ... */
}

Encoding via parameters is unpalatable

The Rust and Java results above are made barely readable by using short (obscure) parameter names. More troubling is the fact that this pollution of the parameter list will bubble transitively backwards through the callers of distance until we reach the point where F is instantiated. Any use of Transformation needs to be parameterized in the same manner.

It also makes explicit instantiation of a parameterized method or class quite painful. (This pain is somewhat alleviated in the presence of type-inference, at least in terms of what text ends up in the final code, but I argue that that in this case the pain has in fact been shifted: instead of having pain while reading the code, one instead suffers when trying to wade through type-errors that inevitably arise during the compile-edit cycle.)

If anything, the above presentation understates the problem, since:

  1. Transformation has only one argument in its domain, and its codomain is the same as its domain; many real traits with associated types are each likely to require multiple parameters.
  2. The above example has direct uses of DOM and DT in the domain and codomain, respectively, of distance. However, every client of Transformation will be forced to be parameterized over DOM and DT; while it is likely that any client of Transformation is likely to need to refer to the type DOM, many are likely to not require use of the distance type DT in their public interface or even in the internals of their code. Thus, our abstraction is not very abstract at all.
  3. As a follow-on to the previous point: We are only illustrating one added concept: DistanceType; each additional concept would require a new type parameter to be threaded through the parameter lists of all methods and classes. This blows up to an unmaintainable mess fairly quickly, discouraging use of generics to define these abstractions (and instead relying on e.g. separate class-hierarchies).

Rust-specific issues

I encountered this problem while porting EOP code to Rust. After wrestling with the type parameter lists for a while, I eventually wised up and asked on the #rust IRC channel if there was a better option. Tim Chevalier informed me of the relevant terminology: the feature I want is called "associated types access" (or often just "associated types"). An associated type specifies a mapping from some type to another type.

"Associated type access" is listed as one of eight properties considered important in "A comparative study of language support for generic programming" (Garcia et al., 2003 ACM). If you found the argument above unconvincing, you should read the Garcia paper for a completely different example motivated by a Graph abstraction.

After I read the Garcia paper, I promptly filed an RFC on the Rust github repository requesting support for Associated Type Synonyms. After this, I had several discussions with Niko Matsakis, both over IRC and in person, on the problems that associated types present for Rust.

Niko's blog posts

You can see Niko's thorough overview of the matter, including his natural generalization of the topic from "associated types" to "associated items", on his pair of blog posts (part I, part II). The generalization to "associated items" enables one to define, in addition to type -> type mappings as illustrated above, also type -> function mappings (called in some languages "static" functions) and type -> (constant) value mappings, which may enable certain interesting coding patterns, such as allowing a type representing a vector in a multi-dimensional space to state, statically, how many dimensions it carries.

The following are the specific points that Niko makes in his posts (some of are just pointing out artifacts of current Rust language syntax).

Current Rust syntax focuses on deriving associated functions from traits

Rust does not currently offer general associated items, but it does offer a kind of associated function access.

If a trait T defines a function f that returns Self (which means that implementations of T are obligated to provide an implementation of f), and one has a type X implementing that trait, then one can derive f.

But in current Rust syntax, one does not write this derivation of f as something attached to the type X; instead, one writes T::f(..), and the compiler is responsible for inferring which implementation of the function f one is referring to, by using type-inference on the context of the invocation T::f(..) to determine that the return type of f must be X (and thus the f in question must be the one that the type X implements to satisfy the obligation established by the trait T).

Resolving ambiguities in general implies you need both the trait and type

The choice of deriving a function's implementation from the trait rather than the type is understandable when one considers that a software system may have multiple traits T, U, V, … that all define a function of the same name (say f), and a type may be specified as implementing more than one of these traits in a single piece of code. (It would be anti-modular to require every trait to choose globally unique names for its set of associated functions). So to handle this case, one must provide some way to disambiguate which f is being referenced. Rust did so by making the trait expression part of the invocation syntax. Niko points out that if one switches to a syntax where one derives f from the type X (e.g. "X::f") then one must tackle this problem in some manner; in his first blog post, he suggests doing so by allowing one to encode both the type and the trait in the referencing syntax (e.g. "X::(T::f)" or "X::(U::f)".

I dislike this syntax because I think it would be confusing for a reader to comprehend the distinct roles of the "::" path operator, both when learning the language and when casually skimming Rust code in general.

Rust type expressions do not naturally fit into Rust path expressions

Niko also points out that when one wants to write X::f where X is a type, it is not always the case that X is a type parameter; it could be a concrete type known to the programmer, such as the type of owned vecs of ints, denoted by the type expression ~[int]. So it seems natural to want to substitute such a type expression for (the meta-variable) X.

But the syntax ~[int]::f is not legal, because ~[int] is not a legitimate path component. Niko describes a couple of work-arounds, e.g. allowing one to wrap a type expression that appears in a path expression with brackets, yielding: <~[int]>::f.

All of the work-arounds presented by Niko do require allowing arbitrary type-expressions in some form to appear as a sub-expression, which would complicate the parser in the Rust compiler (there has been a slight push to try to simplify the path expression syntax, which this would conflict with).

Further syntactic exploration of encoding trait and type

In his second blog post, Niko provides some alternative syntactic forms for resolution:

  • X::(T::f), as described above.

  • T::f::<X> (from "Functional-style name resolution (take 1)"); here X is a synthetic type parameter added to the type parameter list (if any) of f; so now we get to retain syntactic backwards compatibility. Since Rust allows one to omit the explicit type instantiation ::<X, ...> when the compiler is able to infer the instantiation, this would be a natural way to continue doing return-type based inference of the desired type, the way it does already.

  • T::f::<for X> as a way of distinguishing the synthetic parameter from other entries on the parameter list.

I have already stated my problems with the first option.

For the second option, I anticipate being personally confused by the synthetic type parameter being injected into the type parameter list. I understand the appeal of enabling the compiler to continue doing heavy lifting and lighten the programmers syntactic load. Niko's post does a good job of laying out some of the unexpected interactions of the synthetic type parameter with the other forms of generic type parameterization.

The third option would reduce confusion somewhat, since the synthetic parameter would receive special attention at points of type instantiation, but I still think it is an abuse of the parameter list.

Simpler syntax: What about binding?

So I set about trying to come up with another syntactic form for associated item access. My primary focus initially was: all of these examples would be so much simpler, to my mind, if we were able to go back to using a single identifier for the relevant path component in the referencing form, the way that C++ uses C::f. How can Rust make its own analogous R::f (the "R" is for Rust).

Of course, we have already covered that this will be ambiguous if R is a mere type (and it is of course ambiguous if R is just a trait).

But what if R is a way of referring to the type X and the trait T together: the (type, trait) pairing (X,T)? Clearly once one specifies the pair, then it is easy to tell what items are associated with the pair. Even a human without a sophisticated IDE would know in that case to try invoking grep, searching for impl T.* for X.*; a compiler can do even better.

Another way of looking at this: What if we could introduce local names for the impl that corresponds to the (type, trait) pairing.

So I started working on ideas all centering around a declaration form like let R = trait T for type X; or use impl R = T for X and other variations (I think Patrick Walton actually deserves credit for that last one; we will revisit it later). But Niko quickly pointed the huge failing of all of these declaration forms: a very common use case for associated types (remember, that was our original goal) is for function signatures, like:

1
2
3
fn distance<F: Transformation>(x: Domain(F), y: Domain(F), f: F) -> DistanceType(F);

fn remove_edge<G: IncidenceGraph + EdgeCollection>(g: &mut G, e: Edge(G));
where Domain(F), DistanceType(F), and Edge(G) are replaced with appropriately Rust-friendly syntactic forms. There is no place there to put a declaration form let ... or use ... that refers to F. The same applies for other parameterized forms, such as structs, enums, and traits.

So, back to the drawing board.


An Insight

Even though my attempt to solve this problem via a declaration form had failed, I continued to focus on the fact that associated item access is all about the (type, trait) pairing. So how could I surmount the parameterized signature wall?

After reflecting on the parameterized signature itself, I said, "where is a natural place to put a binding from an identifier to a (type, trait) pair?" And this reduced to "where does the (type, trait) pair come from?" This was my insight: The parameterized signature <X: T> itself is where the pairing is defined; (or in the case of <X: T + U>: pairings).

My only problem was to put the identifier binding in there. Once I saw the pairing waiting right in the parameter list, the place for the identifier became clear: in-between the type and the trait: <X: R=T> binds R to the impl T for X; for multiple traits, we have <X: R=T + R2=U>, where R is bound as above, and R2 is bound to the impl U for X.

And now we can consider writing our examples like so:

1
2
3
fn distance<F: T=Transformation>(x: T::Domain, y: T::Domain, f: F) -> T::DistanceType;

fn remove_edge<G: IncidenceGraph + EC=EdgeCollection >(g: &mut G, e: EC::Edge);

The other cute insight is this: the only time we need to add these identifiers explicitly is when there are multiple trait bounds. When there is a single trait bound <X:R=T>, the identifier X is just as reasonable (or at least unambiguous) as R is as a way to reference the impl. So why not treat <X:T> as an abbreviation for <X:X=T>: boom! The biggest potential complaint with this extension (namely, the notational complexity of making people pepper their code with explicit bindings of the impls) goes away! And our first example becomes:

1
fn distance<F: Transformation>(x: F::Domain, y: F::Domain, f: F) -> F::DistanceType;

(our second example remains unchanged, since G has two trait bounds there, and so G alone cannot unambiguously denote a (type, trait) pair.

Note also that this binding form does not suffice on its own; in particular, if one wants to introduce a binding for a (type,trait) pairing that does not appear in the generic parameter bounds of the signature. But the latter is exactly the case that is handled by a declaration form such as those proposed earlier!

So neither solution suffices on its own, but the two together cover many use cases of interest.


The proposed syntax for associated items in Rust

So, with that insight explained, here is my proposal for associated items:

  1. A trait can now declare names for things besides methods. In terms of the grammar that John has been working on:

     trait_decl: TRAIT ident
                    (generic_decls)? (COLON trait_list)?
                    LBRACE trait_method* RBRACE ;
    

    is replaced with

     trait_decl: TRAIT ident
                    (generic_decls)? (COLON trait_list)?
                    LBRACE trait_item* RBRACE ;
     trait_item: trait_method | trait_constant | trait_type
     trait_type: TYPE ident (generic_decls)? SEMI
               | TYPE ident (generic_decls)? COLON boundseq SEMI ;
     trait_const: STATIC ident COLON ty SEMI ;
    
  2. The identifier bound by a trait types is in scope of its enclosing trait; trait method declarations and trait const declarations can reference it.

  3. Extend the Rust grammar to allow an optional binding of an identifier to a (type, trait) pair in a type parameter bound. In terms of the grammar:

     bound : STATIC_LIFETIME | trait | obsoletekind ;
    

    is replaced with:

     bound : STATIC_LIFETIME | trait | ident = trait | obsoletekind ;
    
  4. Extend the Rust grammar to allow a declaration binding an identifier to a (type, trait) pair. In terms of the grammar, I think this is close to what I want:

     view_item : attrs_vis use ;
    

    is replaced with:

     view_item : attrs_vis use | USE impl ident = trait for ty ;
    

    Of potential interest, we do not allow visibility attributes on use impl R = T for X;, because these definitions are always local shorthands and thus private to the module. (Maybe in the future we will see motivation to allow the bindings to be exposed, but I have not yet seen a motivation for this.)

    I am not attached to the particulars of the syntax above; in particular, if someone wants to throw in the trait and/or type keywords into the above to make the purpose all the more clear, I will not object. More so if it is somehow necessary for disambiguation, but I do not anticipate that being the case.

  5. A bound of the form R=T (ident = ty) in the context of a ty_param production X : ... [] ... (ident COLON bound + ... + [] + ... + bound) (where [] denotes the contextual hole that the R=T is plugged into) is treated as binding R to the code defined by the impl T for X. The scope of the binding for R encompasses: the rest of the boundseq (to the right of the "R=T") and the remainder of this decl that follows the generic_decls within which the R=T bound appears.

  6. This binding of R can shadow earlier bindings of the same identifier (either other impl-bindings, or module names). It seems like this should be a reasonable thing to signal via a lint-warning.

  7. A path identifier component can now be an R, binding an impl T for X.

    So one can access trait items (see trait_item above) as R::item. Associated items can be type-parametric whenever the corresponding item could be type-parameteric when exported from a module.

  8. A boundseq with a single bound of variant ty above, where ty is itself of the form ident (i.e. the <X:T> case) is implicitly expanded into <X:X=T>.


What the proposal does not cover

There are cases of interest that are not covered by the above proposal.

Most obvious to me are situations where one wants to describe mutual constraints between the items associated with type parameters. (An example of this is provided by the gen_orbit example with the constraint DistanceType(I) = N, and more generally much of the content of the requires(..) clauses from EOP that I deliberately ignored). For the examples from EOP, C++ handles this by doing the template instantiation blindly and applying the type checker to code after concrete types have been substituted for the parameters; this approach is not compatible with Rust's design where we want to type-check a generic body of code in terms of the guarantees provided by the trait-bounds, not delaying those checks until after the concrete types have been plugged in.

Also, in the changes I proposed above to the Rust grammar (and somewhat implicitly to its semantics), I deliberately constrained my focus to the cases Niko described in his blog posts: types, functions, and constants. But one might consider further extensions, such as allowing traits to define other traits. (I found that subject hard to wrap one's mind around, and I wanted to keep the focus limited for Rust 1.0; we can leave generalizations of this approach for after Rust 1.0.)

Also, I'm not sure whether there is need and/or utility in further generalizing this topic to associated data families. Again, I want to limit the scope of the work to something we believe we can accomplish for Rust 1.0.

What else have I missed? Let me know, leave a comment. (Or look for me in the #rust irc channel.)

Better Command Completion in Bash on OS X

(This post started as a personal e-mail to Niko, and then I figured it was blog worthy.)

There's plenty of problems when working atop "OS X"; but no need to be jealous of Shu's zsh setup (at least not for its tab-completion on git stuff), at least not if you are already using Homebrew. Just install brew's bash completion package!

Executive summary:

1
2
3
4
5
6
7
% brew install bash-completion

% echo >> ~/.bash_profile <<END
  if [ -f $(brew --prefix)/etc/bash_completion ]; then
    . $(brew --prefix)/etc/bash_completion
  fi
END

And voilà!

See also potentially related topics from super user, stack overflow, milkbox blog.


Note also that I did burn myself by trying to get too smart: In particular, after reading stack overflow, I over-eagerly attempted to address a purported problem by installing the homebrew newer git instead of the default (older) built-in git installed by Apple.

This was a little more painful than I expected, because there were a bunch of git-related commands already in my /usr/local/bin, probably I had likely already copied git to there once before by hand, and so brew kept aborting the installation because it did not want to overwrite the binaries that it was not already managing. I think brew was aborting the install in a sound transactional manner, but I am not 100% sure of that, because at least one point the command completion stopped working and at that point I just

  1. gave up on understanding where everything came from,
  2. moved the non-brew git-related material in /usr/local/bin/ out of the way, and
  3. redid the brew install git

Anyway, I should also give a shout-out to Axel Hecht; his post on Mozilla's Yammer instance is what got me to the point of even attempting to install this piece of marvelousness.

(Also, further posts on yammer are lightly pushing for readers to consider zsh as an alternative to bash. I do not think I am ready to switch to zsh, but I can at least link to the blog post arguing for zsh.)


Update (written 2013 april 16): Now that I have decent command/context sensitive completion in bash in my terminal, of course I want to have it in my Emacs M-x shell as well. At first I was dismayed that I did not just get that "out of the box"; then I was happy after some googling to discover: bash-completion.el, which forwards the completion requests onto a separate bash process, so that one inherits the same completions that bash provides in the terminal, with no Emacs hacking.

Well, at least, not very much Emacs hacking.

It turns out that I had to do a little bit of Emacs hacking in order to get the setup working, at least for my idiosyncratic bash setup. In particular, it seems like the Elisp code for bash-complete.el assumes that one is setting one's prompt via the PS1 environment variable, while mine is often set via the PROMPT_COMMAND environment variable. After determining what is going on, it is easy enough to fix this (and the corresponding solution has even been filed as a pull request in the github repo).

Rusty Chain Puzzle 1.

I have been trying to get my feet wet programming in Rust.

A month and a half ago, I thought "Maybe I will hack up an Earley parser in a variety of languages, including Rust." That sent me down a long path of learning about how Earley parsing works; I have not yet written up my results from that investigation, and I still have not written the Rust version of the code.

Last weekend, I sat down and said, "Let's try a simpler goal: A couple simple exercies, maybe taken from Knuth's TAOCP" This was indeed a much simpler goal, but it was more difficult than I had expected.

So, here is a Rust hacking puzzle that I struggled with.

I am representing piles of playing cards via linked structures. Here are the data structure declarations:

1
2
3
4
enum card_suit { clubs, diamonds, hearts, spades }
struct card { suit: card_suit,
              rank: u8, // 1..13
              next: Option<~card> }

Note that the next field is an (optional) owned pointer to the next card in the pile. Option<~card> will be generally used to represent a potentially empty pile (or "stack", "deck" or "hand", as the context dictates), while ~card is a non-empty pile (or, when its next is None, a single card, again as context dictates)

The goal

I want to write four functions: place_top, place_bot, pop_top, and pop_bot, which respectively:

  • place_top(stack, c) pushes a card c onto the top of the stack, represented by return the new top of the stack.

  • place_bot(stack, c) places a card beneath the stack. For an empty stack, the placed card is returned as the top of the newly formed stack; otherwise, the old stack top is returned (since the stack is imperatively modified).

  • pop_top(stack) pops the top of the stack, returning a tuple of the popped card and the remaining, potentially empty stack.

  • pop_bot(stack) removes the bottom of the stack (i.e. "deals from the bottom of the deck"), returning a tuple of the removed card and the new, potentially empty stack.

In code, here are the signatures for the desired functions, as well as one-line reminders of the behavior for each.

1
2
3
4
5
6
7
8
9
10
11
// [c1, ..., cN], cX -> [cX, c1, ..., cN]
fn place_top(pile: Option<~card>, newcard: ~card) -> ~card;

// [c1, ..., cN], cX -> [c1, ..., cN, cX]
fn place_bot(pile: Option<~card>, newcard: ~card) -> ~card;

// [c1, c2, ..., cN] -> (c1, [c2, ..., cN])
fn pop_top(pile: ~card) -> (~card, Option<~card>);

// [c1, ..., cN-1, cN] -> (Some(cN), [c1, ..., cN-1])
fn pop_bot(pile: ~card) -> (~card, Option<~card>);

(Some non-critical helper infrastructure follows, showing off Rust as language)

Here is some example code that puts together a hand and does a few manipulations using the above operations (as well as some printing routines to make looking at these cards nicer in the terminal output)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
fn make_hand() -> ~card {
    let hand = ~card { suit: clubs, rank: 10, next: None };
    let hand = ~card { suit: spades, rank: 3, next: Some(hand) };
    let hand = ~card { suit: diamonds, rank: 2, next: Some(hand) };
    hand
}

fn main() {
    let hand : ~card = make_hand();
    hand.report(~"initial hand: ");
    let AceD = ~card{ suit: diamonds, rank: 1, next: None };
    AceD.report(~"place top: ");
    let hand = place_top(Some(hand), AceD);
    hand.report(~"new hand: ");
    let SixD = ~card{ suit: diamonds, rank: 6, next: None };
    SixD.report(~"place bot: ");
    let hand = place_bot(Some(hand), SixD);
    hand.report(~"new hand: ");
    let (top, rest) = pop_top(hand);
    top.report(~"popped top: ");
    let hand = rest.unwrap();
    hand.report(~"new hand: ");
    let (bot, rest) = pop_bot(hand);
    bot.report(~"popped bot: ");
    let hand = rest.unwrap();
    hand.report(~"new hand: ");
}

// Below are "just" some notation niceties that should not effect
// the semantics of the code + algorithms above.

impl ToStr for card_suit {
    fn to_str(&self) -> ~str {
        match self { &spades   => ~"\u2664", &hearts   => ~"\u2665",
                     &diamonds => ~"\u2666", &clubs    => ~"\u2667" } }
}

fn rank_to_str(r:u8) -> ~str {
    match r {
        1     => ~"A",
        2..10 => r.to_str(),
        11    => ~"J",
        12    => ~"Q",
        13    => ~"K",
        _     => fail!()
    }
}

impl card {
    fn rank_to_str(&self) -> ~str { rank_to_str(self.rank) }
    fn report(&self, prefix: ~str) { io::println(prefix + self.to_str()); }
}

impl ToStr for card {
    fn to_str(&self) -> ~str {
        let mut ret = self.rank_to_str() + self.suit.to_str();
        match &self.next {
            &None => (),
            &Some(ref n) => ret = ret + "," + n.to_str()
        }
        ret
    }
}

In my terminal, I get the following output from the above main function:

initial hand: 2♦,3♠,10♣
place top: A♦
new hand: A♦,2♦,3♠,10♣
place bot: 6♦
new hand: A♦,2♦,3♠,10♣,6♦
popped top: A♦
new hand: 2♦,3♠,10♣,6♦
popped bot: 6♦
new hand: 2♦,3♠,10♣

(I will post my initial "solution" to the puzzle in a follow-up post; I wanted to share this first because I know my current solution is non-optimal and wanted to see what others had to offer for how to solve this first.)

Implicit Versus Explicit Finalization

(This post is largely a response to Niko Matsakis's blog post Destructors and Finalizers in Rust. I started composing it as a comment there, but eventually realized I needed more breathing room.)

I agree wholeheartedly with Niko's statement that the Boehm paper "Destructors, Finalizers, and Synchronization" is a really nice discussion of this topic. However, a significant portion of the destructor/finalizer design space is only briefly discussed in that paper, and I worry that Niko's post overlooks it.

There are designs that do not run finalizers directly from the garbage collection process (whether that collector be a coroutine with the mutator, or a concurrently running thread), and instead run finalization code at explicit points in the code of the mutator (or mutator threads).

To me, such an approach seems appropriate for systems-level programming; it seems to align with the spirit of giving the programmer access to the set of knobs they need for explicit sequencing and resource management (or rope to hang themselves with).

Explicit Cleanup

In the guardian and reference-queue family of systems (see also wills and executors), resource cleanup code is no longer asynchronously run by the GC. Instead, cleanup is the obligation of the mutator. The only asynchronous cleanup action of the garbage collector is to add entries to the appropriate guardians/reference queues (that is, the queues associated with an object that has been appropriately registered and subsequently discovered to be unreachable).

I have included a more explicit description of what a Guardian API is like in the appendix at the end of this blog post, in case the previous paragraph was too terse.

With such an API in hand, developers can build libraries that one can plausibly reason about, in a single- or multi-threaded context.

To be fair: Boehm does address these approaches briefly; see the beginning of section 3.5.1 of his paper, "Explicit Finalizer Invocation". However, he also mixes them in with Java's System.runFinalization() and the motivation for that method. Thus one must take care to distinguish which of Boehm's complaints apply to all explicit finalization systems, and which apply solely to systems such as Java with runFinalization that provide a mix of explicit and implicit finalization.

Passing the Buck

One important characteristic (some might say "drawback") of explicit finalization approaches is that the mutator does need to periodically process its associated guardians/reference queues. After all, with the transfer of responsibility for cleanup from the collector to the mutator, the mutator must meet this obligation eventually.

One standard way to do this is to sprinkle cleanup code (i.e. "check if guardian has entries; if so, process some of them") at points in the control flow of library routines using that guardian. (In other words, in languages with guardians, library designers can hopefully isolate the cleanup code behind the interface of the library that requires such cleanup.)

In fact, since there are distinct guardians/reference-queues, one can prioritize the scheduling (i.e. frequency and incremental-cost) of the cleanups according to the characteristics of individual libraries, within the mutator. Contrast this against relying on the scheduling of the garbage collector with its single finalization queue for the whole heap.

The two main problems with explicit cleanup from my point of view are:

  1. ensuring that the necessary processing does eventually happen (i.e. prevent resource leaks when control does not often (or ever) flow back into the developer's library utilizing the guardian), and

  2. inserting finalizer invocations across the code of a library detracts from its readability; they are a clear example of a cross-cutting concern that should be factored into its own "aspect."

Boehm essentially covers both of the points above (though on first reading I only interpreted him as describing the second point):

This appears to be the safest way to handle finalization in single-threaded code, although it has some clear disadvantages in certain contexts: Potentially large amounts of code, especially long running routines, must be explicitly sprinkled with finalizer invocations.

In the very worst case, in a "normal" imperative language with concurrent threads, these last two drawbacks could be addressed by the client-developer: the client-developer can set their associated cleanup code to run on a distinct thread (that the mutator manages, not the garbage collector). This avoids the ugly sprinkling/cross-cutting of concerns, and should ensure that cleanup does eventually occur (assuming correctly-written multi-threaded code, "ha ha").

Of course, that last suggestion is essentially reimplementing the GC's finalizer thread as a mutator process. But nonetheless, in principle this could be implemented as a library, as long as the appropriate primitives are available underneath.

By making explicit finalization expressible as a library, the developer community would be free to propose competing API's and implementations. That seems like a good thing for a young experimental language.

(One might even be able to develop finalization libraries that are "composable", in the sense that different finalization libraries could be used by distinct libraries in the same overall program. One could coin the term "composing decomposers" for such things.)

Wait, what was that about "normal" languages?

I wrote the end of the previous section intending for it to apply to Rust. Then I realized that I do not have enough experience writing Rust programs to be certain it is reasonable to develop a mutator-based cleanup process that runs on its own thread.

I am only discussing cleanup for structures held in managed-boxes (not in owned-boxes or stack-allocated). It might be feasible to express cleanup routines for managed boxes with relatively trivial types in Rust, at least for some libraries.

But it might be that in practice, managed boxes would generally have types that would make it impossible for a separate thread to extract them from a guardian and be able to access their contents.

There is also the serious problem that such a cleanup thread seems likely to require the use of mutex locks in order to coordinate with the "real" mutator; this in particular seems antithetical to the ideals of Rust.

(Hopefully I will soon acquire sufficient experience with Rust itself to be able to address this issue more coherently.)

Conclusion

I am not saying this is easy, and I am not saying that the systems I am referencing get everything right either. But implicit finalizers, even those invoked from a system-managed asynchronous thread, are not the only answer.

Perhaps my pithy summary is that: Implicit finalizers are indeed inherently asynchronous routines; but with explicit finalization, one has more options (yet still may be able to fall back on asynchrony if necessary).

So, what does all of this mean for Rust? Well, Niko already suggested limiting destructors solely to types that contain only "owned data."

I have no problem with that, since it clearly deals with all of the issues that Boehm described.

But my suspicion is that Rust developers will soon discover that one really does need the GC to feed information forward about the managed boxes that it is collecting. And so we will then be at a crossroads: Put in Java-style finalizers, or adopt another approach?

My goal is to make sure we remember to consider those other approaches when we hit that crossroads.

References

  1. "Destructors and Finalizers in Rust"
    Niko Matsakis
    Blog post, 2013
  2. "Destructors, Finalizers, and Synchronization"
    Hans Boehm
    HP Tech Report; POPL 2003
  3. "Guardians in a Generation-Based Garbage Collector"
    Dybvig, Bruggeman, and Eby
    PLDI, 1993
  4. "How to Handle Java Finalization's Memory-Retention Issues"
    Tony Printezis
    Tech Report, 2007
  5. "Wills and Executors"
    PLT Racket Reference Documentation
  6. "Implementing User-level Value-weak Hashtables"
    Aaron Hsu
    Scheme Workshop 2010
    (I only properly appreciated the value (and difficulties) of using guardians for such purposes after I read this paper)

Appendix A. What are Guardians?

I here outline a concrete example of how this works in the case of Guardians (adapted from Hsu). (To aid readability, I have replaced the use of procedure-arity-based-dispatch, as written by Hsu to match the Chez Scheme API, and I am rewriting his example with a new distinct named procedures .)

One can construct as many guardian instances (or simply "guardians") as one wants. Each guardian is associated with two things:

  1. reclaimable : a set of objects previously determined to be reclaimable by the garbage collector, and
  2. registry : a set of objects scheduled to be eventually enqueued in the first set.

Both of these sets are initially empty when the guardian is constructed.

> (define g (make-guardian))
> (define v "VAL")
> (define p (weak-cons v '())
> (guardian-register! g v)

> (set! v #f)                    ;; Now `"VAL"` is unreachable via strong-refs ...
> (guardian-fetch! g)            ;; ... but GC has not discovered that yet.
#f

> (collect-garbage)              ;; `"VAL"` is still unreachable ...
> p                              ;; ... though one can access via weak paths ...
("VAL")
> (define x (guardian-fetch! g)) ;; ... and the guardian held it in `reclaimable`
> x
"VAL"

                                 ;; At this point, "VAL" is again strongly reachable
                                 ;; (via `x`).  However, it is *not* in either of the
                                 ;; sets for the guardian `g`, and thus is not scheduled
                                 ;; to be enqueued in the `reclaimable` set.

> (set! x #f)                    ;; Now "VAL" is no longer strongly reachable...
> (collect-garbage)
> p                              ;; ... and thus can be reclaimed.
(#!blank-weak-pointer)

So, what does this have to do with finalization?

With the guardian API in hand, one could take care of closing individual file descriptors associated with heap-allocated file objects, by a protocol such as:

  1. Create one guardian G for the file library, whose sole purpose is closing file descriptors.

  2. In the constructor for file objects, register each constructed file object with G.

  3. In a periodic process, dequeue objects from G and close their associated file descriptors.

Appendix B. Another peeve about guardians

One idiosyncrasy about a lot of the guardian-like systems is that they enqueue the original object for processing, which is quite counter-intuitive to me given the effort that the GC went through to determine that the object was otherwise unreachable.

Perhaps this could be addressed by using something like the model described at the start of section 3.1 of Boehm's paper, "Alternatives"; namely, instead of enqueuing the unreachable object on a reference queue, the GC could instead enqueue an associated distinct cleanup object, and reclaim the originally registered object itself. (Boehm states that such a cleanup object falls victim to all the same problems, but as I understand it, that is only true if it is invoked by the GC in the same way that Java-style finalizers are invoked, as described in his paper.)

The associated cleanup object would need to carry any state necessary for the cleanup action (e.g., the file descriptor itself). So that seems like a potential for ugly redundancy and wastage (in either time or space, depending on whether uses a level of indirection or simply redundantly stores all the necessary state in the object and in its associated cleanup object.).

But nonetheless, a decoupled system like this may be easier to reason about, especially when one has scenarios where an object is registered with multiple guardians/reference-queues.

As far as I understand, the reference queue system in Java, as described by Printezis, is sufficient to express a structure like this. Still, it would be interesting to know whether any managed runtimes offer only guardians/reference-queues with this style of distinct associated cleanup objects; I am not aware of any that are so conservative. I might attempt to hack one up in the future.

Resurrected (Hello Again World)

It's Clobbering Time

Remember that thing I said back at the end of 2012? That thing? That thing about the important detail that:

the _deploy/ subdirectory is itself a clone of the targeted github repository, with the gh-pages branch checked out.

It turns out this is really important detail.

Here's why: For my first blogging act of the new year, I inadvertently destroyed my own blog.

I attempted to write a post from a computer other than the one out of which I had already worked all the octopress-compatibility kinks. In the hustle of dealing with rbenv and various other ruby-oriented dependencies, I forgot about the detail above.

And then when I ran rake deploy, I clobbered the live blog.

I may have been recovering from, or incapacitated by, New Years revelry at the time, it is not clear to me at the current moment. I believe I identified the disaster right after it happened, but immediately decided I did not have the time then to diagnose it, fix it, or even to attempt to rollback the state and repush to github. I vaguely remember considering that last option and deciding that even that was out of the question. (I think a pending trip to a Karaoke bar may have been involved in the decision-making process here.)

So, tonight I diagnosed and fixed the problem.

At first I was just going to let the matter lie undocumented, and pretend like it never happened.

But I realized that I may well again make the same mistake in the future, and that it behooved me to at least document the issue in my commit log for the blog source.

And after writing that commit log entry and pushing it, I decided that this story was in fact blog worthy; after all, what is the point of a blog if not to freely broadcast your mistakes? :)

So, directly from my commit message, here is the description of how I clobbered my own blog:

The easy way to sum it up is: The model employed by octopress when deploying to github is this: Your _deploy/ subdirectory must contain a checkout of the target repo, the one with the gh-pages branch, and you must have that _deploy/ subdirectory checked out and ready to go before running 'rake deploy'.

If you do not have a _deploy/ subdirectory at all and you let 'rake deploy' create it for you but you also let 'rake deploy' attempt to push to github, and you are also managing the source itself on github, you will enter a world of pain where the rake invocation will push this root directory, presumably in the master branch (or in my case, blog.pnkfx.org branch) to the target repo in the gh-pages/ branch. Which will bust things terribly, especially if that causes the CNAME file to get deleted from the gh-pages/ branch of the target repo.

A note on self-reference

Also, a quick half shout-out, or maybe corrective note, to seamusbradley for pointing out some details about linking back to one's own blog posts.

It is only a half shout-out because Seamus's note is only useful, I think, if you have, like him, a customized setting for the root: in your _config.yml. That, or Seamus has confused himself and changed his root setting in order to accommodate other url's that he observed, but those urls are in fact actually generated by settings for properties other than root.

Here's the concrete details: I read (misread?) Seamus's post at first as saying that a customized setting of root to /blog is a prerequisite for linking to your own posts. It seems to me that the relevant detail is what the permalink setting is, not the root. (But then again, I have not played with changing my root setting, apart from finding that when I did try changing it to /blog as Seamus suggested, it seems like doing so broke rake preview.)

In my case, the root and permalink for my _config.yml are set as follows:

root: /
permalink: /blog/:year/:month/:day/:title/

and I format links to my own posts, such as the one you are reading, like so: /blog/2013/01/08/resurrected-hello-again-world as you can see from looking at the source for the line above,

[`/blog/2013/01/08/resurrected-hello-again-world`](/blog/2013/01/08/resurrected-hello-again-world)

A bit of quoted self-reference is a good place to stop for the night.

OS X Tiled Window Management With Slate

I recently discovered Slate, an open-source window-management tool for Mac OS X.

It is very cool, mainly in that it is very configurable (but with a reasonably readable syntax for its configuration file).

Perhaps the most important thing to say is: Do not judge it solely based upon its default configuration file, which is very bare bones and does not illustrate anything near the full feature set that it offers.

Instead, I recommend one at least read over Tristan Hume'e blog post, which advertises Slate much more effectively than the project's github page. The blog post describes some of the crucial features that are not exposed in the default configuration. In particular, the window-switcher shortcut, which overlays each window with a letter to give that window focus, is much more tile-friendly if you also turn on

config windowHintsIgnoreHiddenWindows false
config windowHintsShowIcons true

You can see this and other custimzations I have made for myself in my own .slate file, which I keep with my other dotfiles in my public repository.

Hello World

First post! I am attempting to move my blog to GitHub Pages.

After seeing the results of others, I figure I will start with Octopress and see how that goes.

Just so I can remind myself of the Octopress basics in the immediate future:

  • Much of the page generation is controlled by configuration file _config.yml

  • The content is all stored in source/_posts/

  • This particular entry corresponds to the file 2012-12-31-hello-world.markdown

  • The first 7 lines of that file were originally generated via the rake command invocation:

    % rake new_post["Hello World"]

  • The command rake generate will convert the source into static html pages.

  • After generating the file (and during subsequent editting), one can preview the state locally in a local Ruby webserver via:

    % rake preview

    and then browsing localhost port 4000. The rake preview invocation will continuously monitor your post source files so that you can keep working on your post and then reload in your web browser without rerunning rake itself.

  • The command rake deploy is supposed to deploy the content into its intended live location. I have been having difficulty using this command, in part because I think it is written assuming you have your ssh-key already set up and integrated with github (or something similar) so that there would be no password prompts.

    • But of course I have not done this yet.
    • One important detail about rake deploy with github pages is that the _deploy/ subdirectory is itself a clone of the targetted github repository, with the gh-pages branch checked out. This can be confusing if your main source tree (the parent directory of _deploy/) is itself the same repository as the targetted github repository.
  • Update: rake deploy just worked fine for me, password prompts and all. I think my earlier difficulty was an artifact of some previous bad state, one of either:

    • I had put in a malformatted url for the target repository
    • My target repository already had a gh-pages branch (from earlier testing) that needed to be pulled-and-merged (or discarded in some fashion, which was what my merge amounted to).
  • Update (26 march 2012): there are still some hiccups with rake deploy; you need to be careful about what you store in the source/ directory. In particular, I was working on a draft post and threw various source files that I was hacking on in the same directory, along with some .gitignore files so that git would ignore build products generated when I compiled the source (to binaries or jars or fasls…).

    The headache came when I did rake deploy, and hit this error:

    % rake deploy
    cp -r source/_posts/.gitignore public/_posts/.gitignore
    rake aborted!
    No such file or directory - public/_posts/.gitignore
    /Users/pnkfelix/Dev/Sites/pnkfx-blog/Rakefile:230:in `block (2 levels) in <top (required)>'
    /Users/pnkfelix/Dev/Sites/pnkfx-blog/Rakefile:229:in `block in <top (required)>'
    /Users/pnkfelix/Dev/Sites/pnkfx-blog/Rakefile:219:in `block in <top (required)>'
    Tasks: TOP => copydot
    (See full trace by running task with --trace)
    %
    

    The problem here, as far as I can tell, is that octopress is aggressively trying to copy over all dotfiles it can find (Octopress Issue 104) and that code was not written to create any subdirectories as necessary.

    My Ruby development knowledge is sufficiently under-developed that I am not going to try to fix this myself. Instead I have simply moved all of the source code I was hacking out of the source/ directory and into a separate hacks/ directory. This seems to have addressed the problem; I have also filed an issue for this with Octopress.