An increasing number of systems rely on programming language technology to ensure safety and security of low-level code. Unfortunately, these systems typically rely on a complex, trusted garbage collector. Region-based type systems provide an alternative to garbage collection by making memory management explicit but verifiably safe. However, it has not been clear how to use regions in low-level, type-safe code. We present a compiler intermediate language, called the Capability Calculus, that supports region-based memory management, enjoys a provably safe type system, and is straightforward to compile to a typed assembly language. Source languages may be compiled to our language using known region inference algorithms. Furthermore, region lifetimes need not be lexically scoped in our language, yet the language may be checked for safety without complex analyses. Finally, our soundness proof is relatively simple, employing only standard techniques. The central novelty is the use of static capabilities to specify the permissibility of various operations, such as memory access and deallocation. In order to ensure capabilities are relinquished properly, the type system tracks aliasing information using a form of bounded quantification. 1 A current trend in systems software is to allow untrusted extensions to be installed in protected services, relying upon language technology to protect the integrity of the service instead of hardware-based protection mechanisms [19, 39, 2, 25,24,17,14]. For example, the SPIN project [2] relies upon the Modula-3 type system to protect an operating system kernel from erroneous extensions. Similarly, web browsers rely upon the Java Virtual Machine byte-code verifier [19] to protect users from malicious applets. In both situations, the goal is to eliminate expensive communications or boundary *This research was performed while the first author was at Cornell University. This material is based on work supported in part by the AFOSR grant F49620-97-1-0013 and ARPA/RADC grant F30602-96-l-0317. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not reflect the views of these agencies. Permission to make digital or hard copies of all or part of this work for personal or classroom use is grmted without fee probided that copies are not wade or distributed for prolit or commercial advantage and that topics bear this notice and the fill citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and!or a fee. crossings by allowing extensions to directly access the resources they require. Recently, Necula and Lee 126, 251 have proposed ProofCarrying Code (PCC) and Morrisett et al. [24] have suggested Typed Assembly Language (TAL) as language technologies that provide the security advantages of high-level languages, but without the overheads of interpretation or just-in-time compilation. In both systems, low-level machine code can be heavily optimized, by hand or by compiler, and yet be automatically verified through proof-or type-checking. However, in all of these systems (SPIN, JVM, TAL, and Touchstone [27], a compiler that generates PCC), there is one aspect over which programmers and optimizing compilers have little or no control: memory management. In particular, their soundness depends on memory being reclaimed by a trusted garbage collector. Hence, applets or kernel extensions may not perform their own optimized memory management. Furthermore, as garbage collectors tend to be large, complicated pieces of unverified software, the degree of trust in language-based protection mechanisms is diminished. The goal of this work is to provide a high degree of control over memory management for programmers and compilers, but as in the PCC and TAL frameworks, make verification of the safety of programs a straightforward task. Tofte and Talpin [35, 361 suggest a type and effects system for verifying the soundness of region-based memory management. In later work, Tofte and others show how to infer region types and lifetimes and how to implement their theory [34, 3, 41. There are several advantages to region-based memory management; from our point of view, the two most important are: 1. Deallocation is explicit but provably safe. 2. The run-time routines necessary for region-based memory management are relatively simple constant-time operations and, in principle, could be formally verified. The Tofte-Talpin calculus uses a lexically scoped expression (letregion r in e end) to delimit the lifetime of a region r. Memory for the region is allocated when control enters the scope of the letregion construct and is deallocated when control leaves the scope. This mechanism results in a strictly LIFO (last-in, first-out) ordering of region lifetimes. Both Birkedal et al. [4] and Aiken et al. [l] observed that a completely LIFO (de)allocation of regions would make poor use of memory in many cases. They proposed a series of optimizations that often alleviate efficiency concerns and even improve upon traditional tracing garbage collection in some cases. Although their optimizations are safe, there is no simple proof-or type-checker that an untrusting client can use to check the output code. Similarly, even the most straightforward code-generation requires that we stray from the Tofte-Talpin framework and allow arbitrary separation of allocation and deallocation points. Therefore, while region inference brings us half way to our goal, in order to construct a strongly-typed region-based assembly language we must re-examine the fundamental question: "When can we free an object x?" One solution is to free x when you can guarantee that it will no longer be accessed. Operating systems such as Hydra [41] have solved the access control problem before by associating an unforgeable key or capability with every object and requiring that the user present this capability to gain access to the object. Furthermore, when the need arises, these systems revoke capabilities, thereby preventing future access. In the rest of this paper, we describe a strongly typed language called the Capability Calculus. Our language's type system provides an efficient way to check the safety of explicit, arbitrarily ordered region allocation and deallocation instructions using a notion of capability. As in traditional capability systems, our type system keeps track of capability copies carefully in order to determine when a capability has truly been revoked. Unlike traditional capability systems, our calculus supports only voluntary revocation. However, the capabilities in our calculus are a purely static concept and thus their implementation requires no run-time overhead. We have a purely syntactic argument, based on Subject Reduction and Progress lemmas in the style of Felleisen and Wright [40], that the type system of the Capability Calculus is sound. In contrast, Tofte and Talpin formulate the soundness of their system using a more complicated greatest fixed point argument [36], and the soundness of Aiken et aI.'s optimizations [l] depend upon this argument. Part of the reason for the extra complexity is that Tofte and Talpin simultaneously show that region inference translates lambda calculus terms into operationally equivalent region calculus terms, a stronger property than we prove. However, when system security is the main concern, soundness is the critical property. The simplicity of our argument demonstrates the benefits of separating type soundness from type inference or optimization correctness. We have a formal translation of a variant of the TofteTalpin language into our calculus. We describe the translation in this paper by example; the full details appear in the companion technical report [5]. We also illustrate how some region-based optimizations may be coded in our language, taking advantage of our extra freedom to place allocation and deallocation points. We have adapted the type system for the Capability Calculus to the setting of Typed Assembly Language, providing for the first time the ability for "applets" to explicitly control their memory management without sacrificing memoryor type-safety. As the typing constructs at the intermediate and assembly levels are so similar, we discuss here only the intermediate language and refer the interested reader to the companion technical report [5] for details on the assembly level. The central technical contribution of this paper is the Capability Calculus, a statically typed intermediate language that supports the explicit allocation, freeing and accessing of memory regions. Programs in the Capability Calculus are written in continuation-passing style (CPS) [29]. That is, functions do not return values; instead, functions finish by calling a continuation function that is typically provided as an argument. The fact that there is only one means of transferring control in CPS-rather than the two means (call and return) in direct style-simplifies the tracking of capabilities in our type system. A direct style formulation is possible, but the complications involved obscure the central issues. In the remainder of this paper, we assume familiarity with CPS. The syntax of the Capability Calculus appears in Figure 1. In the following sections, we explain and motivate the main constructs and typing rules of the language one by one. The complete static and operational semantics are specified in Appendix A. We specify the operational behavior of the Capability Calculus using an allocation semantics [22, 23, 241, which makes the allocation of data in memory explicit. The semantics is given by a deterministic rewriting system P I-+ P' mapping machine states to new machine states. A machine state consists of a pair (M, e) of a memory and a term being executed. A memory is a finite mapping of region names (v) to regions where a region is a block of memory that holds a collection of heap-allocated objects. Regions are created at run time by the declaration neurgnp, z, which allocates a new region in the heap, binds p to the name of that region, and binds z to the handle (handle(v)) for that region. Region names and handles are distinguished in order to maintain a phase distinction between compile-time and runtime expressions. Region names are significant at compile time: The type-checker identifies which region an object inhabits via a region name (see below). However, region names, like other type constructors, have no run-time significance and may be erased from executable code. In contrast, region handles hold the run-time data necessary to manipulate regions. In addition to accounting for a phase distinction, the separation of region names and handles also allows us to refine the contexts in which region handles are needed. Handles are needed when allocating objects within a region and when freeing a region, but are not needed when reading data from a region. Regions are freed by the declaration freergnv, where v is the handle for the region to be freed. Objects h large enough to require heap allocation (i.e., functions and tuples), called heap vaZues, are allocated by the declaration z = h at v, where v is the handle for the region in which h is to be allocated. Data is read from a region in two ways: functions are read by a function call, and tuples are read by the declaration z = r;(v), which binds x to the data residing in the ith field of the object at address v. Each of these operations may be performed only when the region in question has not already been freed. Enforcing this restriction is the purpose of the capability mechanism discussed in Section 2.2. A region maps locations (e) to heap values. Thus, an address is given by a pair v.e of a region name and a location. In the course of execution, word-sized values (v) will be substituted for value variables and type constructors for constructor variables, but heap values (h) are always allocated in memory and referred to indirectly by an address. Thus, when executing the declaration z = h at r (where r is handle(v), the handle for region v), h is allocated in region v (say at a) and the address v.e is substituted for x in the following code. A term in the Capability Calculus consists of a series of declarations ending in either a branch or a function call (or a halt). The class of declarations includes those constructs discussed above, plus two standard constructs, x = v for binding variables to values and x = vi p 212 (where p ranges over +, -and x) for arithmetic. The types of the Capability Calculus include type constructor variables and integers, a type of region handles, as well as tuple and function types. If r is a region, then r handle is the type of r's region handle. The tuple type (Tl , . . . , TV) at r contains the usual n field tuples, but also specifies that such tuples are allocated in region r, where r is either a region name v or, more frequently, a region variable P. For example, a polymorphic identity function that is allocated in region r, but whose continuation function may be in any region, may be given type V[a:Type, p:Rgn].(C, cy, (C, a) + 0 at p) + 0 at r for some appropriate C. Let f be such a function, let w be its argument with type r, and let g be its continuation with type (C, 7) -+ 0 at r. Then f is called by The typing rules also make use of region types (T), which assign a type to every location allocated in a region, and memory types (@), which assign a region type to every region allocated in memory. 2.2 The central problem is how to ensure statically that no region is used after it is freed. The typing rules enforce this with a system of capabilities that specify what operations are permitted. The main typing judgement is *;A;I';C!-e 264 which states that (when memory has type X!?, free constructor variables have kinds given by A and free value variables have types given by I') it is legal to execute the term e, provided that the capability C is held. A related typing judgement is which states that if the capability C is held, it is legal to execute the declaration d, which results in new constructor context A', new value context I" and new capability C'. Capabilities indicate the set of regions that are presently valid to access, that is, those regions that have not been freed. Capabilities are formed by joining together a collection of singleton capabilities {r} that provide access to only one region, and capability variables E that provide access to an unspecified set of regions. Capability joins, written Cr @ Cz, are associative and commutative, but are not always idempotent; in Section 2.3 we will see examples where C @ C is not equivalent to C. The empty capability, which provides access to no regions, is denoted by 8. We will often abbreviate the capability {ri} $ . . . @ {T,,} by {PI,. . . , T,,}. In order to read a field from a tuple in region r, it is necessary to hold the capability to access r, as in the rule: A I-C = C' @ {r} : Cap *;A;l?t-~:(ri,...,r~)atr 9; A; l?; C I-z = A;(W) + A; l?{z:ri}; C (z G Dam(r)) The first subgoal indicates that the capability held (C) is equivalent to some capability that includes {r}. A similar rule is used to allocate an object in a region. Since the type of a heap value reflects the region in which it is allocated, the heap value typing judgement (the second subgoal below) must be provided with that region. A l-C = C' @ {r} : Cap \k;A;I't-hatr:r 'P;A;I'fv:r handle ~;A;r;Ct-~==atv~A;r{z:r};C (z @ oom(r)) Functions are defined by the form fixf[A](C,zi:rr ,..., z,,:r,,).e, where f stands for the function itself and may appear free in the body, A specifies the function's constructor arguments, and C is the function's capability precondition. When A is empty and f does not appear free in the function body we abbreviate the fix form by X(C,zi:ri,. . . ,z":r,,).e. In order to call a function residing in region r, it is again necessary to hold the capability to access r, and also to hold a capability equivalent to the function's capability precondition: A k C = C" @ {r} : Cap A I-C = C' : Cap *;A;lYt-v:(C',ri,...,r,)+Oatr O;A;I't-wi:ri The body of a function may then assume the function's capability precondition is satisfied, as indicated by the capability C in the premise of the rule:' *; A; I'{zi:ri, . . . , G:T,,}; C I-e 9; A; r E X(C, zl:rl,. . . , z,,:r,).e Often, we will extend the required capability for a function with a quantified capability variable (similar to a row variable). This variable may be instantiated with whatever capabilities are leftover after satisfying the required capability. Consequently, the function may be used in a variety of contexts.  The most delicate issue is the typing of region allocation and deallocation. Intuitively, the typing rules for the newrgn and freergn declarations should add and remove capabilities for the appropriate region. Naive typing rules could be: This function is well-formed according to the naive typing rule: The function begins with the capability {pi,pz} and pi is removed by the freergn declaration, leaving {pz}. The tuple y is allocated in pz, so the projection is legal. However, this code is operationally incorrect if pi and pz are instantiated by the same region r. In that case, the first declaration frees r and the second attempts to read from r. This problem is a familiar one. To free a region safely it is necessary to delete all copies of the capability. However, instantiating region variables can create aliases, making it impossible to tell by inspection whether any copies exist. We desire a system for alias control that can easily be enforced by the type system, without expensive and complex program analyses. One possibility is a linear type system [12, 37, 381. In a linear type system, aliasing would be trivially controlled; any use of a region name would consume that name, ensuring that it could not be used elsewhere. Thus, in a linear type system, the naive rules for allocating and deallocating regions would be sound. Unfortunately, a linear type system is too restrictive to permit many useful programs. For example, suppose f has type V[pl:Rgn, pz:Rgn]. ({p~,pz}, (int) at pl, (int) at ~2,. . .) + 0 at d and vi and w2 are integer tuples allocated in the same region r. Then f could not be called with vi and 2)~ as arguments, because that would require instantiating pl and pa with the same region. More generally, one could not type any function that takes two arguments that might or might not be allocated in the same region. Approaches based on syntactic control of interference [30, 311 are more permissive than a linear type system, but are still too restrictive for our purposes; it is still impossible to instantiate multiple arguments with the same region. 265 Our approach, instead of trying to prevent aliasing, is to use the type system to track aliasing. More precisely, we track non-aliasing, that is, uniqueness. We do this by tagging regions with one of two multiplicities when forming a capability. The first form, {r+}, is the capability to access region r as it has been understood heretofore. The second form, {ri}, also permits accessing region P, but adds the additional information that P is unique; that is, r represents a different region from any other region appearing in a capability formed using {r'}. For example, the capability {r ,', ri} not only indicates that it is permissible to access ri and rz, but also indicates that ri and ~2 represent distinct regions. Since {r'} guarantees that r does not appear anywhere else in a capability formed using it, it is the capability, not just to access r, but also to free r. Thus we may type region deallocation with the rule: Note that joining capabilities is only idempotent when the capabilities in question contain no unique multiplicities. For instance, the capabilities {r+} and {r+, r+} are equivalent, but the capabilities {r'} and {r',r'} are not; the latter capability ({r', r'}) asserts that r is distinct from itself and consequently that latter capability can never be satisfied. The rules for capability equivalence appear in Appendix A. When C is equivalent to C@C, we say that C is duplicatable. Note that capability variables are unduplicatable, since they can stand for any capability, including unduplicatable ones. Occasionally this prevents the typingof desired programs, so we provide a stripping operator C that replaces all 1 multiplicities in C with + multiplicities. For example, {r:,rz} = {rt,r,'}. For any capability C, the capability c is duplicatable. When programs need an unknown but duplicatable capability, they may use a stripped variable 7. The capabilities {r'} and {r+} are not the same, but the former should provide all the privileges of the latter. We therefore say that the former is a subcapability of the latter and write {r'} 5 {r+}. In the complete system, the various rules from Section 2.2 are modified to account for subcapabilities. For example, the function call rule becomes: If we hold capability {r+}, we may call f b ating pi and p2 with r, since {r+} = {r+,r P instanti-}. Using the subcapability relation, we may also call f when we hold {rl}, again by instantiating pi and p2 with r, since {r'} 5 {r+} = {P+,r+}. The subcapability relation accounts only for the forgetting of uniqueness information. Intuitively there could be a second source of subcapabilities, those generated by forgetting an entire capability. For example, {rt,r$} seems to provide all the privileges of {rt}, so it is reasonable to suppose {r;',r,'} to be subcapability of {r;'}. Indeed, one can construct a sound Capability Calculus incorporating this axiom, but we omit it because doing so allows us to specify memory management obligations and to prove a stronger property about space usage. One may write a function that can be called with extra capabilities using a capability variable, as discussed in Section 2.2. By omitting the axiom Cl @ C2 5 Ci, our type system may formally specify who has responsibility for freeing a region. Failure to follow informal conventions is a common source of bugs in languages (such as C) that use manual memory management. Our type system rules out such bugs. For example, consider the type: ({pi} @ e, p handle, (E) -+ 0 at r') + 0 at r In our system e @ {p'} f E. Consequently, before any function with this type can return (i.e., call the continuation of type (E) + 0 at r'), it must take action to satisfy the capability E, that is, it must free p. In general, our type system prevents "region leaks": programs must return all memory resources to the operating system before they terminate (Theorem 2.4). The operating system does not have to clean up after a program halts. The typing rule for halt states that no capabilities may be held, and since capabilities may not be forgotten, this means that all regions must have been freed.  The system presented to this point is sound, but it is not yet sufficient for compiling real source languages. We need to be able to recover uniqueness after a region name is duplicated. To see why, suppose we hold the capability {r') and f has type: Pa, * * * 9 ({pt,pt}, . . .) + 0 at r') + 0 at r" We would like to be able to instantiate pl and p2 with r (which we may do, since {r'} 5 {r+,r+}), and then free r when f calls the continuation in its final argument. Unforyftel? the continuation only poss;sses the capability {r ,r } -{r+}, not the capability {r } necessary to free r. It does not help to strengthen the capability of the continuation to (for example) {pi}, because then f may not call it. We may recover uniqueness information by quantifying a capability variable. Suppose we again hold capability {r'} and g has type: V[pi:Rgn, pz:Rgn, e:Cap].(e, . . . , (E, . . .) + 0 at T') + 0 at r" We may instantiate e with {r'} and then the continuation will possess that same capability, allowing it to free r. Unfortunately, the body of function g no longer has the capability to access pl and ~2, since its type draws no connection between them and E. We solve this problem by using bounded quantification to relate pi, pr and e. Suppose h has type: V[~l:~,Ggn,c 5 {P:,P;)]. E,. . . , (E,. . .) + 0 at r ) + 0 at r" If we hold capability {r'}, we may call h by instantiating pi and pz with r and instantiating c with r'}. This instantiation is permissible because {r'} 5 {r i,r+J. As with g, the continuation will possess the capability {r }, allowing it to free r, but the body of h (like that of f) will have the capability to access pi and pa, since e 5 {pt,pt}. Bounded quantification solves the problem by revealing some information about a capability e, while still requiring the function to be parametric over E. Hence, when the function calls its continuation we regain the stronger capability (to free r), although that capability was temporarily hidden in order to duplicate T. More generally, bounded quantification allows us to hide some privileges when calling a function, and regain those privileges in its continuation. Thus, we support statically checkable attenuation and amplification of capabilities. 2.4 The most important properties of the Capability Calculus are Type Soundness and Complete Collection. Each can be proven from the formal semantics in Appendix A. Type Soundness states that we will never enter a stuck state during the execution of a well-typed program. A state (M,e) is stuck if there does not exist (M', e') such that (M,e) e (M',e') and e is not halt i. For example, a state that tries to project a value from a tuple that does not appear in memory is stuck. Theorem The proof of soundness is straightforward, making use of the standard Subject Reduction and Progress lemmas. Progress states that well-typed states are not stuck, and Subject Reduction states that evaluation steps preserve welltypedness. Lemma 2 (Subject Reduction) Ift-(M,e) and (M,e) w (M',e') then F (M',e') Lemma 3 (Progress) Ift-(M,e) then either: 1. There exists (M',e') such that (M,e) c-) (M',e'), or The Complete Collection property guarantees that welltyped terminating programs return all of their memory resources to the system before they halt. By Subject Reduction and Progress, terminating programs end in well-formed machine states (M, halt i). The typing rule for the halt expression requires that the capability C be empty. Using this fact, we can infer that the memory M contains no regions. Our work provides a type system in which to check regionannotated programs for safety, but we do not provide any new techniques for determining those annotations. Instead, we rely on existing region inference strategies [34, l] to infer appropriate region annotations. In this section we illustrate how a variant of the Tofte-Talpin region language can be translated into the Capability Calculus. The translation is formalized in the companion technical report [5]. By composing Tofte and Birkedal's region inference algorithm [34] with this translation, we have a way to compile high-level languages into the Capability Calculus. Our example considers a function count that counts down to zero. In order to have interesting allocation behavior the integers involved in the count are boxed, and hence are allocated in a region.  The count function is stored in region pl and takes two arguments, a handle for region p and a boxed integer x allocated in region p. If x is nonzero, count decrements it, storing the result again in p, and recurses. The function has two effects: a read on pl, resulting from the recursive call, and a read/write effect on p, resulting from line l's read and line 2's store. Therefore, we give the function count the effect (acce88 (PI), access (pz)}. Operationally, the letregion command serves a purpose similar to a pair of newrgn and freergn declarations. A new region is allocated at the beginning of the letregion block and is automatically deallocated at the end of the block, resulting in a stack-like (LIFO) allocation pattern. Hence, the code above allocates two regions (pl and pz), stores count in pl, stores a boxed integer in pz, calls count, and then deallocates pl and pa. The translation of this program into the Capability Calculus rewrites it in continuation-passing style, and converts effects information into capability requirements. One of the main tasks of the translation is the compilation of letregion blocks into nevrgn and freergn declarations. The resulting program appears below. In the interest of clarity, we have simplified the actual output of the formal translation in a few ways. The translated program begins by allocating regions pi and ps, and also allocates a third region ps to hold count's continuation. The count function requires a capability E at least as good as the capability {p~,p+,p~,t} needed to access itself, its argument, and its continuation; and it passes on that same capability E to its continuation. The continuation requires the capability {p:,p:,p:} in order to free the three regions. Hence E is instantiated with the stronger capability needed by the continuation. The power of bounded quantification comes into play when a function is called with several regions, some of which may or may not be the same. For example, the above example could be rewritten to have ten and cant share a region, without changing the code of count in any way: %%% count vith ten and cant sharing ps let newrgn pr,xP1 in let neurgn p2,xPz in % capability held is {p:,pi} let count = . . . as before . . . let ten = (10) at xP2 in let cant = 0 (G,P:}) . . .I at xp2 in count IPZ, ~2~ ipi, piI1 (xp2, ten, cant) In this example, pcont is instantiated with ,os and E is instantiated with {pt, pt} (which is again the capability required by cant). However, count proceeds exactly as before because c is still as good as {pf,p+,pL,t) (since tp:, P:) 5 {PL P,'> = MY Pzs, Pz+D In the examples above, even though count is tailrecursive, we allocate a new cell each time around the loop and we do not deallocate any of the cells until the count is complete. However, since p never contains any live values other than the current argument, it is safe to reduce the program's space usage by deallocating the argument's region each time around the loop, as shown below. Note that this optimization is not possible when region lifetimes must be lexically scoped. XVI count with efficient memory usage let newrgn pi,xPl in let newrgn pz, xP2 in let newrgn ps,xP3 in % capability held is {p:,p:,p:} let count = (fix count [pz, ~3, {pi, pill (xP2, ten, cant) In order to deallocate its argument, the revised count requires a unique capability for its argument's region p. Note that if the program were again rewritten so that ten and cant shared a region (which would lead to a run-time error, since ten is deallocated early), the program would no longer typecheck, since {pi, pi} g {p;',p$, pi}. However, the program rewritten so that count and cant share a region does not fail at run time, and does typecheck, since {P:> PiI I {P;', PL PiI. We believe the general framework of our capability system is quite robust. There are several ways to extend the language and a number of directions for future research. 4.1 The primary goal of this work was the development of a low-level, type-safe language that gives compilers and programmers control over the allocation and deallocation of data. The language that we have described so far is relatively high-level as it includes abstract closures and high-268 level operations such as the atomic allocation and initialization of data. In the companion technical report [5], we show that the capability constructs interact benignly with the process of type-preserving compilation described by Morrisett et al. [24] and we use the techniques described in this paper to modify their typed assembly language to allow explicit deallocation of data structures. In this paper, we have concentrated on using the Capability Calculus to implement safe deallocation of memory, but with a few changes, we believe our capability apparatus may be used in a variety of other settings as well. One potential application involves reducing the overhead of communication across the user-kernel address space boundary in traditional operating systems. Typically, in such systems, when data in user space is presented to the kernel, the kernel must copy that data to ensure its integrity is preserved. However, if a user process hands-off a unique capability for a region to the kernel, the kernel does not have to copy that region's data; without the capability, the user can no longer read or modify the contents of that region. Capabilities can also be used to ensure mutually exclusive access to shared mutable data in a multi-threaded environment, by viewing locks as analogous to regions. If we associate each piece of sensitive data with a lock, we can statically check that every client to sensitive data obtains the corresponding lock and its associated capability before accessing that data. When the code releases the lock, we revoke the capability on the data, just as we revoke a capability when we free a region. In general, whenever a system wishes statically to restrict access to some data, and/or to ensure a certain sequence of operations are performed, it may consider using capabilities to check that the appropriate invariants are maintained. 4.2 The Capability Calculus derives its lineage from the work of Gifford and Lucassen on type and effect systems [ll, 201 and the subsequent study by many others [16, 33, 36, 341. The relationship between effects and capabilities is quite close. A necessary prerequisite for the use of either system is type inference, performed by a programmer or compiler, and much of the research into effects systems has concentrated on this difficult task. Because of the focus on inference, effect systems are usually formulated as a bottom-up synthesis of effects. Our work may viewed as producing verifiable evidence of the correctness of an inference. Hence, while effect systems typically work bottom-up, specifying the effects that might occur, we take a top-down approach, specifying by capabilities the effects that are permitted to occur. The addition of aliasing information to our capabilities also separates them from earlier work on effects systems. However, capabilities only express the simplest aliasing relationships: a region is either completely unaliased or it may alias any other region. Our capabilities reveal very little of the structure of the store. A number of other researchers [lo, 7, 321 have studied static analyses that infer the shapes of data structures and the aliasing relationships between them. We plan to investigate how to use these finergrained memory models to increase the flexibility of our type system. A connection can also be drawn between capabilities and monadic type systems. Work relating effects to monads [21, 28, 18, 81 has viewed effectful functions as pure functions that return state transformers. This might be called an ex post view: the effect takes place after the function's execution. In contrast, we take an ex ante view in which the capability to perform the relevant effect must be satisfied before the function's execution. Nevertheless, there is considerable similarity between the views; just as the monad laws ensure that the store is single-threaded through a computation, our typing rules thread a capability (which summarizes aspects of the store) along the execution path of a program. The experience of Birkedal et al. [4] with the ML Kit region compiler shows that there are many refinements to the basic system that will be necessary to make our Capability Calculus a practical intermediate language. In particular, Birkedal found that allocation often occurs in two diierent contexts: one context in which no live object remains in the region and a second context in which there may be live objects remaining in the region. In order to avoid code duplication and yet ensure efficient space usage, they check at run time to find out which situation has occurred. In the former case, they reset the region (deallocate and reallocate in our formalism) and in the latter case, they do not reset but continue allocating at the top of the region. The type system we present here is not powerful enough to encode these storage-mode polymorphic operations. In fact, it must be refined in two ways. First, this optimization demands finergrained aliasing specifications that declare a region p does not alias some particular region p' but may alias other regions. Second, after we dynamically check which of the two contexts above we are in, we must refine the type of our capability. Harper and Morrisett's typecase [13] mechanism developed for the TIL compiler and further refined by Crary et al. [6] allows the sort of type refinement required here. Aiken et al. [l] have also studied how to optimize the initial Tofte-Talpin region framework and they also allow regions to be independently deallocated. Furthermore, their system separates the naming of a region from its allocation. Our language, as presented, does not make such a distinction, but it is straightforward to add one. With such a mechanism in place, we conjecture, based on the soundness proof for Aiken et al.'s analyses, that those analyses may be used to produce type correct code in the Capability Calculus. Gay and Aiken [9] have developed a safe region implementation that gives programmers control over region allocation and deallocation. They use reference counting to ensure safety. Hawblitzel and von Eicken [15] have also used the notion of a region in their language Passport to support sharing and revocation between multiple protection domains. Both of these groups use run-time checking to ensure safety and it would be interesting to investigate hybrid systems that combine features of our static type system with more dynamic systems. We have presented a new strongly typed language that admits operations for explicit allocation and deallocation of data structures. Furthermore, this language is expressive enough to serve as a target for region inference and can be compiled to a typed assembly language. We believe that the notion of capabilities that support statically checkable attenuation, amplification, and revocation is an effective new tool for language designers.
The construction of our type system bears similarity to the seminal work on calculus of capabilities REF .
Typed memory management in a calculus of capabilities
POPL '99
Computer Science