Comment by sparkie

A capability is basically a reference which both designates some resource to be accessed and provides the authority to access it. The authority is not held somewhere else like an Access Control List - the reference is the authority. Capabilities must be unforgeable - they're obtained by delegation.

---

To give an example of where this has been used in a programming language, Kernel[1] uses a capability model for mutating environments. Every function (or operative) has an environment which holds all of its local variables, the environment is encapsulated and internally holds a reference to the parent environment (the surrounding scope). The rule is that we can only mutate the local variables of an environment to which we have a direct reference, but we cannot mutate variables in the parents. In order to mutate the variables in the parent, we must have a direct reference to the parent, but there is no mechanism in the language to extract the parent reference from the environment it is encapsulated in.

For example, consider the following trivial bit of code: We define some variable `x` with initial value "foo", we then mutate it to have the value "bar", then look up `x`.

    ($define! x "foo")
    ($set! (get-current-environment) x "bar") 
    x

As expected, this returns "bar". We have a direct reference to the local environment via `(get-current-environment)`.

Technically we could've just written `($define! x "bar")`, where the current environment is assumed, but I used `$set!` because we need it for the next example.

When we introduce a new scope, the story is different.

    ($define! x "foo")
    ($define! foo
      ($lambda ()
        ($set! (get-current-environment) x "bar")))
    (foo)
    x

Here we create a function foo, which has its own local environment, with the top-level environment as its parent. We can read `x` from inside this environment, but we can't mutate it. In fact, this code inserts a new variable `x` into the child environment which shadows the existing one within the scope of the function, but after `foo` has returned, this environment is lost, so the result of the computation is "foo". There is no way for the body of this lambda to mutate the top-level environment here because it doesn't have a direct reference to it.

So far basically the same static scoping rules you are used to, but environments in Kernel are first-class, so we can get a reference to the top-level environment which grants the child environment the authority to mutate the top level environment.

    ($define! x "foo")
    ($define! env (get-current-environment))
    ($define! foo
      ($lambda ()
        ($set! env x "bar")))
    (foo)
    x

And the result of this computation is "bar".

However, by binding `env` in the top-level environment, all child scopes can now have the ability to mutate the top-level.

To avoid polluting the environment in such way, the better way to write this is with an operative (as opposed to $lambda), which implicitly receives the caller's environment as an argument, which it binds to a variable in its local environment.

    ($define! x "foo")
    ($define! foo
      (wrap ($vau () caller-env
        ($set! caller-env x "bar"))))
    (foo)
    x

Now `foo` specifically can mutate it's caller's local environment, but it can't mutate the variables of the caller of the caller, and we have not exposed this authority to all children of the top-level.

---

This is only a trivial example, but we can do much more clever things with environments in Kernel. We can construct new environments at runtime, and they can have multiple parents, ultimately forming a DAG, where environment lookup is a Depth-First-Search, but the references to the parent environments are encapsulated and cannot be accessed, so we cannot mutate parent scopes without a direct reference - we can only mutate the root node of the DAG for an environment to which we have a direct reference. The direct reference is a capability - it's both the means and the authority to mutate.

---

We can use these first-class environments in conjunction with things like `$remote-eval`, which evaluates some piece of code in an environment provided by the user, which may contain only the bindings they specify, and does not capture anything from the surrounding scope.

  ($define! calculator-environment
    ($bindings->environment (+ +) (- -) (* *) (/ /)))

  ($remote-eval (+ 1 2) calculator-environment)

However, if we try to use some feature like IO, to write an output to the console.

  ($remote-eval (write (+ 1 2)) calculator-environment)

We get an error, `write` is unbound - even though `write` is available in the scope in which we performed this evaluation. We could catch this error with a guarded continuation so the program does not crash.

This combination of features basically let you create "mini sandboxes", or custom DSLs, with more limited capabilities than the context in which they're evaluated. Most languages only let you add new capabilities to the static environment, by defining new functions and types - but how many languages let you subtract capabilities, so that fewer features are available in a given context? Most languages do this purely at compile time via a module/import system, or with static access modifiers like `public` and `private`. Kernel lets you do this at runtime.

---

One thing missing from this example, which is required for true capabilities, is the ability to revoke the authority. The only way we could revoke the capability of a function to mutate an environment is to suspend the program.

Proper capabilities allow revocation at any time. If the creator of a capability revokes the authority, this should propagate to all duplicated, delegated, or derived capabilities with immediate effect. The capabilities that were held become "zombies", which no longer provide the means nor the authority - and this is why it is essential that we don't separate designation from authority, and why these should both be encapsulated in the capability.

This clearly makes it difficult to provide proper capabilities in programming languages, because we have to handle every possible error where we attempt to access a zombie capability. The use of such capabilities should be limited to where they really matter such as access to operating system resources, cryptographic keys, etc. where it's reasonable to implement robust error handling code. We don't want capabilities for every programming language feature because we would need to insert error checks on every expression to handle the potential zombie. Attempting to check if a capability is live before using it is no solution anyway, because you would have race conditions, so the correct approach to using them is to just try and catch the error if it occurs.

Another take-away from this is that if capabilities are provided in a language via a type system, it must be a dynamic type system. You cannot grant authority in a static type system at compile time if the capability may have already been revoked by the time the program is run. Capabilities are inherently dynamic by nature because they can be revoked at any time. This doesn't mean you can't use capabilities in conjunction with a static type system - only that the static type system can't really represent capabilities.

You can find out a lot more about them on the erights page that others have linked, and I would recommend looking into seL4 if you're interested in how they're applied to operating systems.

---

[1]:http://web.cs.wpi.edu/%7Ejshutt/kernel.html