So, I didn’t actually mean to post that previous post, I had intended to think more on the idea. But oh well, cat’s out of the bag. In any case, I’ve been thinking about the “closures” vs “procedures” idea that I jotted down there and decided to try and elaborate on it a bit more, since I find it has a lot of appeal. In particular I think that the current collection of closure types is addressing too many distinct use cases and the result is confusing.

UPDATE 2013.05.14: Edited to tweak various errors and to add some variations at the end that I prefer.

Today: by-reference vs copying closures

Today we offer three different kinds of closures (&fn, @fn, and ~fn), but these closures can really be divided into two basic categories: by-reference and copying closures. A by-reference closure is the usual kind: it is allocated on the stack and has full access to the variables in the creating stack frame. It can read them, write them, and borrow them. These are used with for loops and the like.

Copying closures, on the other hand, are somewhat different. They are not tied to any particular stack frame. Instead, they copy the current values of the variables which they close over into their environment (like all the default Rust copies, this is a shallow copy, so if the value being closed over contains ~ pointers, it will no longer be accessible from the creator). These closures are used primarily as task bodies and for futures. There are some scattered uses of @fn closures in the compiler but as far as I can tell they are all legacy code that should eventually be purged and rewritten to use traits (i.e., the visitor, the AST folder).

Loosely speaking, a &fn closure is by-reference and @fn and ~fn closures are copying closures. But this is not strictly true. In fact, an the &fn type can be either a by-reference closure or a copying closure, because you are permitted to borrow a @fn or ~fn to a &fn. So the type in isolation does not tell you whether a closure is by-reference or not. In fact, there is no explicit indication at all—instead, when you create a closure today (i.e., with a |x, y| ...) expression, the compiler infers based on the expected types whether this should be a by-reference closure or a copying closure. Because the semantics of these two vary greatly, I find this potentially quite confusing and unfortunate.

Tomorrow (perhaps): closures and procedures

In general, I would prefer to draw a starker line between copying and by-reference closures. I propose to use the term closure to refer only to by-reference, stack-allocated closures. We could then use another term, perhaps procedure, to refer to the copying closures. This would mean that our type hierarchy would look like:

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 (*)

This chart is basically the same as the one you will find in the dynamically sized types post from before with one crucial difference: closure types have been split from procedures, and closure types have moved into the category of sized types, meaning that you no longer write an explicit sigil when you use one. This is because the representation of a closure would always be a pair of a borrowed pointer into the stack and a function pointer: the type has a fixed size (two words) and requires no memory allocation.

I have chosen to leave procedures as unsized, since a procedure must allocate memory on the heap, and this allows the user to select which heap is used; in earlier drafts of this idea, I had modified procedures to implicit use the exchange heap, meaning that a type like proc() always represented an exchange heap allocation. But I think it’s more consistent to have that type be written ~proc, and it maintains the general Rust invariant “you don’t have allocation unless you see a sigil”.

UPDATE: bstrie on IRC asked about fn items, which never have any environment. As today, these would continue to be coercable to either a closure or a procedure.

Closure and procedure expressions

Closures would still be created with the form |x, y| expr. Procedures would be created using the keyword proc: proc(x, y) expr. If desired, we could integrate procedures into do using some syntax like one of the following, depending on whether we wish to make the sigil explicit:

do spawn proc { ... }   // sigil inferred

do spawn ~proc { ... }  // sigil explicit

Closure and procedure types in more detail

The full function or procedure type would look something like this ([] indicates optional content):

 [once] (fn|proc) [:['r] [Bounds]] <'a...> (S*) -> S
 ^~~~~^           ^~~~~~~~~~~~~~~^ ^~~~~~^ ^~~^    ^
   |                     |            |     |      |
   |                     |            |     |  Return type
   |                     |            |    Argument types
   |                     |          Bound lifetime names
   |               Lifetime and trait bounds
Onceness

Here the “onceness” indicates whether the closure/procedure can be called more than once. The “lifetime and trait bounds” indicate constraints on the environment. The lifetime bound 'r indicates the minimum lifetime of the variables that the closure/procedure closes over, and the “bounds” (if any) would give bounds on the types of those variables. Finally, you have the argument and return types.

If omitted, the default bounds for a closure would be a fresh lifetime and no type bounds. The default bounds for a procedure would be the static lifetime and Owned.

Use cases

Let’s look briefly at the use cases I listed before.

Higher-order and once functions

Typical uses for higher-order and once functions look much the same as before, but minus a sigil.

impl<T:Sized> for [T] {
    pub fn map<U:Sized>(f: fn(&T) -> U) -> ~[U] { ... }
                        // ^~~~~~~~~~~
}

impl<T:Sized> for Option<T> {
    // `each` on an option type can only execute at most once:
    pub fn each(f: once fn(&T) -> bool) -> bool { ... }
                // ^~~~~~~~~~~~~~~~~~~
    }
}

For contrast, these are &fn(&T) -> U and &once fn(&T) -> bool today.

Sendable functions and sendable once functions

Here is an example of a sendable once function:

fn spawn(f: ~once proc()) {...}
         // ^~~~~~~~~~

As we saw before, one would write one of the following to call this function:

do spawn proc { ... }
spawn(proc { ... })

Creating a future would look like future(proc expr) (vs future(|| expr) today).

Const closures

One could still use const closures to achieve lightweight parallelism:

impl<T:Sized> for [T] {
    pub fn par_map<U:Sized>(f: fn:Const(&T) -> U) -> bool { ... }
                            // ^~~~~~~~~~~~~~~~~
}

However, I have been thinking that we’ll have to be careful here, we need some way to guarantee that the closure does not move from its environment and then replace the moved value. Today this is illegal, but if we can prevent closures from recursing (which we must do anyhow) then we could make such moves legal, and it would be useful sometimes. On simple solution is to stay that if the closure type has a Const bound, moves are illegal, but it’s a bit…ad-hoc, since the bounds are only supposed to be constraining the types of the variables that are closed over. Still, it might be good enough.

Sendable const functions and combinators

As I argued before, I think these are not important use cases, but with procedures they actually work out fine (though not with variations 2 and 3 below). A sendable const function can be expressed with the type ~proc:Owned+Const(), which is complex, but then it is a complex idea. Combinator types would likely look like @proc or @proc:'r, in the case where the combinator closes over borrowed data.

Variation #1: Leaving procedures out of the core language

In fact, I think proc types need not be built into the language, you could model them with traits, though you’d probably want a macro like proc!(...) for defining the proc body. This would also mean the procedures can’t be used with do form.

Variation #2: Limit procedures to execute once

I don’t know of any (good) uses cases for non-once procedures. I think they should just always be once. This would mean that the only closure types that are commonly needed would be:

1. fn(T) – normal higher-order functions
2. once fn(T) – higher-order functions that execute at most once
3. ~proc(T) – procedures

Because procedures can always be desugared into a struct and a trait, this would not lose no expressiveness.

Variation #3: Limit procedures to execute once and use exchange heap

For maximum streamlining, we could make proc implicitly use ~, in which case it would be written:

1. fn(T) – normal higher-order functions
2. once fn(T) – higher-order functions that execute at most once
3. proc(T) – procedures

These types read pretty well, I think.

Summary

I have long been unsatisfied with the implicit and confusing divide between “by reference” and “copying” closures. Splitting them into two concepts seems to address a lot of issues and be an overall win to me.

I’ve been thinking about what I wrote in my last post regarding closures and I am beginning to change my opinion about the correct solution. fn~ just seems so unfortunate. So, besides writing fn~, what are the other options? I just thought I’d write down a few of the other ideas I’ve come up with for later reference. Not saying any of the ideas in this post are good yet.

Just write &mut fn()

Maybe it’s not so bad. It is advertising the possibility that the closure may mutate its environment. This would mean that while &fn() is a valid type, it is a type that does not permit the function to be called, much as &&mut (pointer to a mutable borrowed pointer) does not permit the mutable borrowed pointer to be used.

At first I was thinking that there is also a valid interpretation for &fn, meaning a function that does not mutate the variable in its environment, but then I realize that per the DST proposal any &mut fn could be borrowed to &fn, and so that would not be sound.

Remove everything but borrowed closures

We could just only have borrowed closures. The type would be written fn[:bounds]() or once fn[:bounds](). There’d be no need to notate the kind of environment pointer: it’s always a borrowed pointer. All other uses of closures would be expressed using traits and impls.

Mainly this means that code which spawns traits would get somewhat verbose, because you would need to create a struct or some other type to capture all of the upvars. For larger tasks, this is not a big deal, but for some code it could be rather annoying. I imagine futures in particular would become much more verbose; enough so as to be nearly unusable.

On the upside, there’d be no more confusion about whether a closure copies its environment or not (no, it never does). Closure types would be simpler (no need to worry about sigils). You’d write fn() or once fn() in all but the most esoteric cases. The code to manage closures would become much simpler.

Add a new keyword for what is now called an “owned closure”

This is basically the fn~ solution with another name. Rather than writing fn~ to indicate a closure value that owns its environment, we could write proc (for procedure) or something like that. This avoids the annoying “sigil after the name”, at the cost of a new keyword.

Procedures could probably always be single-shot (that is, once). Almost all use cases for them (futures, tasks, etc) are single-shot, and the others could probably be accommodated with traits instead. But we could also distinguish between a proc and a once proc if we wanted.

Procedures would probably be less interoperable with functions, since the name does not particularly suggest interoperability. For example, I imagine you could not use a proc where a fn is expected. I don’t know of any time that this is actually important.

Using a different name also helps to draw a clear line between between “closures” (which reference the variables in the stack frame that created them) and “procedures” (which copy out from that stack frame). I personally would prefer to designate procedures with a different syntax, e.g., proc(x, y) { ... } in place of |x, y| ..., but this is not necessary (as an aside, I had hoped to write some today about why I think our current use of || to designate any kind of closure is troublesome and should be changed, before I realized that we’d have to address this problem I’m thinking over instead).

More ideas?

Ok, that’s most of the more radical ideas I’ve had so far. I’ll have to keep thinking on it.

I realized today that there is an unfortunate interaction between the proposal for dynamically sized types and closure types. In particular, in the case of the recurring closure, I described the soundness issues that arise in our language when closures are able to recurse.

My solution for this was to make the type system treat a &fn() value the same way it treats &mut T pointers: they would be non-copyable, and when you invoke them, that would be effectively like a “mutable borrow”, meaning that for the duration of the call the original value would become inaccessible. So in short the type system would guarantee that when you call a closure, that same closure is not accessible from any other path in the system, just as we now guarantee that when you mutate a value, that same value is not accessible from any other path in the system.

This is all well and good, and I think this treatment would be largely invisible to the user under common access patterns. However, it does not play well with the proposal for dynamically sized types, because under this proposal all things written &T must behave the same, no matter what T is. This is in fact the whole point of the proposal! But here I want to treat &fn specially.

I’ve been pondering various solutions this morning. I have come up with two possible avenues:

1. Instead of writing &fn() you could write &mut fn(). This is perhaps the “principled” solution, but I consider it rather a non-starter. Writing &fn() for a closure is…tolerable, but &mut fn() is not. It’s verbose and it seems sort of nonsensical (although there is some logic to it, when you consider that calls to the function may mutate the environment and so forth).

2. We go back to the older notation and move sigils for closures after the fn. This actually has some notational perks. For example, rather than writing &fn() we can just write fn() (if there is no sigil, we can default to &). On the minus side, a sendable closure would be written fn~()—but, then again, under the dynamically sized types proposal, sendable closures were going to be written ~fn:Owned(), so is fn~() really so bad?

More details after the fold.

Recently, separate discussions with pnkfelix and graydon have prompted me to think a bit about “dynamically sized types” once again. Those who know Rust well know all about the sometimes annoying discrepancy between a type like ~T (owned pointer to T) and ~[S] (owned vector of S instances)—in particular, despite the visual similarity, there is no type [S], so ~[S] is not an instance of ~T for any T. This design was the outcome of a lot of back-and-forth and I think it has generally served us well, but I’ve always had this nagging feeling that we can do better. Recently it occurred to me how we could, though it’s not without its price.

In the spirit of “no stone left unturned”, I thought I’d write out this idea. At first I thought this was a rather futile exercise, since any large changes to Rust have to pass a pretty high bar at this point, but now that I’ve thought the idea through, I think it has a lot of merit and is worth considering.

I want to look at an interesting topic: what subset of JavaScript do we intend to support for parallel execution, and how long will it take to get that working? As my dear and loyal readers already know, our current engine supports a simple subset of JavaScript but we will want to expand it and make the result more predictable.

From my point of view, the subset below includes basically all the JavaScript syntax that I ever use. There are two primary limitations that I think people will encounter in practice:

1. The fact that mutating shared state boots you out of parallel mode. This restriction is (I think) easy to understand, but it will often take some restructuring to obey it.
2. The fact that strings and many native objects (regular expressions, DOM objects, etc) are currently not supported. I expect we’ll improve the support for strings in the near term and also for some native objects, but for others—notably DOM—it will be very challenging to make things work in parallel, due to the many complex implementation details.

OK, let’s get to the details. In the list that follows, we often refer to a plain old JavaScript object (POJO), which means an object defined in JavaScript, not a built-in object. It should be created either with a literal ({...}, [...]) or a new C expression where C is a user-defined function. I’ve also written bug for cases where the current implementation is more limited than it should be.

• a: Variable access
  • You should be able to access any variable in scope, so long as you do not use with or eval. I think this all works fine today, though there may be errors in the implementation today relating to infrequently used access patterns, such as "use strict".
• a.b: Property access
  • If a is a POJO and b is a data property
    • no getters (should work someday)
• a[e]: Element access
  • If a is a POJO or a TypedArray
• a + b, a - b, etc: Binary operators
  • for any primitive values (someday we should be able to support all objects)
  • bug: today, only works if a and b are both numbers or bools (in any combination)
• a === b, a !== b: Strict equality and unequality
  • always works
• a == b, a > b, etc: Loose relational operators
  • works if a and b are both numbers or bools (in any combination)
• a[i] = b: Numeric property assignment
  • if a is a POJO or TypedArray owned by current task, and i <= a.length (no holes—not yet, anyway)
  • bug: today, we must successfully predict that a will be an array or typed array. In practice, this preciction is reasonably successful, but problems arise when the same function is called many times from different contexts.
• a.e = b or a["e"] = b: String property assignment
  • if a is a POJO owned by the current task
  • bug: today, we must successfully predict the offset of e within a. In practice, this prediction often fails, as the code must be written very, very carefully for it to work.
• {...}, [...], new C(...): object literals and creation
  • for new C(...), C must be a JavaScript function
• f() and a.m(...): Function and method calls
  • If the function being called is a user-implemented function, or one of the functions in the following list:
    • higher-order functions like map, reduce, etc
    • parallel higher-order functions like pmap, preduce, etc
    • Array.push (presuming the receiver is writable)
      • bug: today only a[a.length] = e works, not a.push(e)
    • Math.*
      • bug: today, most but not all Math functions work, and only if we predict the function that will be called and are able to inline it. In practice, this prediction is almost always successful.
    • (more to come)
• function(a, b) { ... } or (a, b) => { ... }: closure creation
  • this should basically always work, I think
  • bug: the => syntax doesn’t work yet in parallel execution, I don’t believe
• if, while, etc
  • works fine

One caveat I should point out in the current implementation: even if you stick to the above subset, it is possible that some parallel iterations will abort, generally because of mispredicted types or other transient errors. But I consider a parallel abort to be ok if the engine will eventually stabilize and all subsequent runs will be successful. This is the same as what happens with JIT engines, which often generate code that is later invalidated and recompiled.

Yesterday I realized that you can violate Rust’s memory safety guarantees by using “stack closures”, meaning closures that are allocated on the stack which have can refer to and manipulate the local variables of the enclosing stack frame. Such closures are ubiquitous in Rust, since every for loop makes use of them (and virtually every higher-order function). Luckily, this hole can be fixed with (I think) very little pain—in fact, I think fixing it can also help us make other analyses a little less strict.

The problem stems from the fact that, if you are clever, you can get a stack closure to recurse (that is, to call itself again with the same environment). This would mean that while the stack closure has a new set of local variables, the variables it inherits from its environment are the same. When the borrow checker was first written, this was not true, but it is now, since closures were generalized in the meantime.

Executive Summary

My proposed fix is a change that will guarantee statically that stack closures cannot recurse (that is, cannot call themselves with the same environment). I’ll go into the details of the problem and my proposed fix in the post, but I wanted to start by briefly summarizing what the effects would be on end-users.

• Almost all if not all existing higher-order functions would still work fine. In particular, you can call &fn closures normally and pass them as a parameter to another function and so on. What would be a little more subtle is storing &fn closures into data structures; it’d still be supported, but some patterns that would be legal today would become illegal.

• The “liveness” pass, which checks that all variables are initialized, can be generalized to permit closures to move out from local variables so long as they move a new value back in. This means that foldl can be implemented without copies:

  function foldl<A,B,I:Iterable<B>>(a0: A,
                                    iter: &I,
                                    op: &fn(A,&B) -> A) -> A {
      let mut result = a0;
  
      // Here I am deliberately desugaring the `for` syntax,
      // because I want to emphasize that this is a closure:
      iter.each(|b| {
          // Note: A is not copyable, therefore this call
          // *moves* from result into `op()` and then restores
          // it. This did not used to be legal because we are
          // executing in a closure, and we were afraid
          // that `op` might in fact somehow recurse, in which
          // case it would find that `result` is uninitialized.
          result = op(result, b);
          true
      })
  }
  

What would not work would be:

• Passing the same &fn closure as a parameter more than once, or calling a &fn closure with itself as an argument (no Y combinators).

• Making a struct S that contains &fn closures and then calling those closures via an @S or &S pointer, like so:

  struct S {f: &fn()}
  fn foo(s: &S) { s.f() } // would be illegal
  

  You could write this code using an &mut S pointer, though:

  struct S {f: &fn()}
  fn foo(s: &mut S) { s.f() } // would be illegal
  

  The reason for this is that &mut pointers are non-aliasable. Similar rules arise in the revised borrow checker I’ve been working on for various corner cases where aliasing is a concern. I’ll have a post on that at some point too.

While working on issue #5656 I encountered an interesting problem that I had not anticipated. The result is a neat little extension to the region type system that increases its expressive power. The change is completely internal to the type rules and involves no user-visible syntax or anything like that, though there are some (basically nonsensical) programs that will no longer compile. Anyway I found it interesting and thought I would share.

In my last post about ParallelJS, I discussed the ForkJoin() intrinsic and showed how it was used to implement the parallel map operation. Today I want to write about the high-level changes to IonMonkey that are needed to support ForkJoin(). IonMonkey, of course, is our JavaScript engine.

Parallel execution mode

To support ParallelJS, we introduce a second mode of compilation called parallel execution mode. JavaScript compiled in this mode produces executable code that is suitable to be run in parallel. To accommodate this new mode, each JSScript* potentially contains pointers to two IonScript* data structures, one for standard sequential mode and one for parallel mode.

Execution normally stays confined within one mode. So if you are running a function f in sequential mode and it invokes another function g, then we will run the sequential mode version of g. But if you are running f in parallel mode, it will call the parallel version of g. The only place where we move between modes is in the ForkJoin intrinsic, which invokes the parallel mode script for the first time.

You may wonder why we permit each script to be compiled in both modes simultaneously. The reason is that it is possible to have helper functions and code that runs in both sequential and parallel mode. Imagine, for example, that you have a helper function for searching an array to find the object with a given name:

function findObject(list, name) {
    for (var i = 0; i < list.length; i++) {
        if (list[i].name === name)
            return list[i];
    }
    throw Error("No object with name " + name + " found!");
}

It is perfectly reasonable to want to invoke this helper function both from sequential and from parallel code. If we only permitted a function to be compiled in one mode or the other, we would always be recompiling findObject each time we started or finished a parallel operation.

Differences between parallel and sequential execution mode

The biggest difference between parallel and sequential mode is that code executing in parallel mode is guaranteed to be pure. That is, it can never write to any shared state that might be visible from other threads. This purity requirement generally includes not only user-visible JavaScript state but also internal engine details. For example, in sequential mode code, after we have done several property lookups on an object that has a large number of properties, we will “hashify” the property chain, meaning that we convert it from an array into a dictionary to make later lookups faster. This hashification operation is not visible to the JavaScript user (except insofar as subsequent property lookups are faster), but it is still disallowed in parallel execution mode because it would cause data races.

There are some exceptions to the purity requirement. The first and most obvious is the UnsafeSetElement intrinsic I discussed in part one, which is used to track the progress of parallel work. The second exception is that it is ok to modify internal engine details so long as those modifications are threadsafe. For example, in bug 846111, Shu has implemented threadsafe inline-caching, which is of course a mutation to shared state.

Generally speaking, though, when you call a parallel mode function you can be sure that it will either complete successfully or bailout. In either case, you know that it has no lasting effects that are visible to end-user JavaScript code, except those that might have occurred via the UnsafeSetElement intrinsic (which of course is only usable from self-hosted code and which must be carefully audited).

Changes to the Ion compilation process

There are two major changes when compiling in ParallelExecutionMode: The first change is the so-called “parallel array analysis”, which analyzes the actions that the scripts take and modifies them as needed to ensure that each action is either threadsafe (and pure) or else that the script bails out. The second change is that do not compile a single script in isolation but rather attempt to compile the transitive closure of a starting script and all scripts that it may call.

Parallel array analysis

The parallel array analysis can be found in js/src/ion/ParallelArrayAnalysis.cpp, in the function ParallelCompileContext::analyzeAndGrowWorklist(). It runs after the normal suite of optimizations have taken place. Its primary goal is to ensure that the parallel code will be pure and threadsafe.

To that end, it performs a walk of the control-flow graph and examines each MIR instruction using a visitor. The MIR instructions are categorized into one of several categories, as follows:

• Safe operations are operations that can be safely executed in parallel without changes, such as Constant or Box.
• Write-guarded operations are operations that are safe as long as the value being modified is not shared. To verify this, we insert a write guard before the operation in question. The write guard will cause a bailout should the object be shared (more on the details of this check to come in a later post). N.B.—write guards are not to be confused with write barriers, which have to do with incremental and generational garbage collection.
• Specialized operations are numeric operations that are safe so long as they are operating over scalar data, such as Add, Mul, etc.
• Unsafe operations are operations that are just plain disallowed in parallel execution, generally because we have not made an equivalent threadsafe path. An example is RegExp.
• Custom operations are, well, everything else. Generally speaking these are operations that are not safe by default in parallel mode, but where there exists an alternative version that is safe, such as NewArray or NewObject.

The categorization of instructions is done using macros. The visitor expects one method per MIR instruction type. There are various macros for each of the above categories, and the macro expands into a pre-canned method definition (in the case of custom operations, the macro expands to an out-of-line method, and the method body appears later in the file).

I’ll talk a little bit more about the safe and unsafe operations now, and I’ll cover the other cases (write guards, memory allocation, etc) in later posts.

Safe operations are simply left unchanged, and they execute just as they would in sequential mode (though in some cases there are checks in the CodeGenerator so that the MIR behaves somewhat differently).

When an unsafe operation is encountered, the basic block in which it resides is removed from the graph along with its dominated subtree. In its place, we add a bailout block that will cause parallel execution to bailout should it ever execute. This ensures that unsafe operations that never execute do not prohibit safe code from running.

Transitive compilation

In normal sequential mode, if we encounter a call to a script that is not compiled, we just invoke the interpreter. In parallel mode this option is not available. So what we do instead is to take advantage of the information that TI makes available and, when compiling a script x, collect all scripts that x might call. Then, once we have compiled x, we go on and compile those scripts. The process is transitive, meaning that we will then continue on to compile the scripts that x’s callees might call and so forth until we reach a fixed point.

Note that we do not monitor for hot paths, as we do in sequential mode. That is, we don’t care if the script has been called 10 times or 100 times before. This is for two reasons: one, we assume that parallel paths are going to be hot, since they are going to be called over all the entries in a large array. Two, seeing as we will have to bailout if we encounter a call to an uncompiled script, it’s worth erring on the side of more compilation rather than less. We do however check that the use count of the script is at least one, so as to avoid compiling things that never run.

At runtime, when we see a call to a JavaScript function, we check whether it has been compiled for parallel execution. If so, we can simply call it as normal and carry on. This is the expected case, of course.

If we encounter a call to an uncompiled script, which can happen either because our transitive compilation was incomplete or because the callee was invalidated or garbage-collected in the mean-time, we bailout with an “uncompiled script” error. At this point, control returns to the ForkJoin function I described in my previous post. Presuming that we haven’t encountered too many bailouts yet, ForkJoin will cycle around and try to compile the uncompiled script.

When compiling an uncompiled script, we also set a flag on all the currently executing scripts in the stack trace. This flag is a warning that execution of that script is likely to encounter an uncompiled script. The purpose for this flag is to notify later callers that while the script itself is valid, it likely has callees that have not been compiled, so before running the script in parallel we should re-walk the transitive closure of things it might call and check for anything that is missing.

I want to finish my discussion of associated items by taking a look at how they are handled in Haskell, and what that might mean in Rust.

These proposals have the same descriptive power as what I described before, but they are backwards compatible. This is nice.

I’ve been doing a lot of thinking about Rust’s trait system lately. The current system is a bit uneven: it offers a lot of power, but the implementation is inconsistent and incomplete, and in some cases we haven’t thought hard enough about precisely what should be allowed and what should not. I’m going to write a series of posts looking at various aspects of the trait system and trying to suss out what we should be doing in each case. In particular I want to be sure that our trait design is forwards compatible: that is, I expect that we will defer final decisions about various aspects of the trait system until after 1.0, but we should look now and try to anticipate any future difficulties we may encounter.

As the inaugural post in this series, I want to take a look at associated items (e.g., associated types, constants, functions, etc). Associated items are requested often, though under various names. When I first started this post, it was actually part of a larger post, but I quickly found that the topic of associated items was too large to be a footnote of another post. In fact, I’m finding it’s too large to fit into one post at all. So I’ll be breaking this post up until multiple pieces. This first post will cover what an associated item is and what you might want to use it for, and it will do so from a C++ perspective.

I will also propose some changes to how we handle so-called “static” fns (which I will be calling “associated” functions, because the name “static” gives all the wrong connotations). These changes are not backwards compatible. I do not take such an idea lightly; we are trying very hard to stabilize Rust so such changes must pass a high bar (I personally think the change would be worth it, but opinions will vary). In the next post, I will present the Haskell approach to associated items, which is closer to what we have today and which can be adapted in a mostly backwards-compatible fashion.