11 April 2017

Lately in Kitten #2: Closures, Boxing, Permissions, and Assumptions

Recent work on Kitten has been focused on design rather than implementation, so those of you who’ve been following the project might have noticed an apparent lull in development activity. Having figured out a few issues, I’ll be getting back to the code this week. Here’s an overview of the stuff I’ve been thinking about.

Closure Conversion

Closure conversion and lambda lifting are two operations central to the implementation of a compiler for a functional programming language. The goal is to convert anonymous functions that implicitly capture variables from the enclosing scope into closures that explicitly indicate which variables they capture, as well as lift inline anonymous functions into top-level definitions.

For instance, the expression -> x; { x } takes a value from the stack and wraps it in a function that simply returns that value when called. The quotation { x } captures the local variable x from the enclosing scope. Currently, the compiler transforms this into an explicit “capture” expression, represented in pseudo-Kitten as:

$(local.0){ closure.0 }

When execution reaches this expression, the local variable (local.0) is copied into the closure; when the closure is executed, closure.0 refers to this captured value.

However, the implementation of this process is overly complex, and makes a needless distinction between closure variables and local variables. I’ve figured out a much nicer (and more traditional) implementation that represents closure variables simply as extra parameters passed on top of the stack when a closure is invoked. Again in pseudo-Kitten, this yields:

local.0 { -> closure.0; closure.0 } new.closure.1

The advantage here is that it makes it very simple to produce unboxed closures: the new.closure.n internal instruction simply coerces the top of the stack—from a series of n variables followed by a function pointer into a single opaque closure value. When the closure is invoked with call, the coercion is performed in reverse, yielding the captured values as ordinary arguments on the stack beneath a function pointer, which is then called just like any other function.

Furthermore, this implementation of unboxed closures maps very nicely to existential types. Briefly, we can represent a closure as an unboxed pair of the captured values and a function pointer, using existential quantification to hide the actual types of the captured values. With this change, you’ll be able to pass closures around as ordinary stack-allocated values. Because the closure type is abstract, it doesn’t unify with any other type—as in Rust, internally each closure will get a unique anonymous type.


After unboxed closures are implemented, you will only need to pay the cost of boxing a closure when you want to store it in another data structure, and this will be explicit. For example, currently you might write a list of functions of type List<(Int32 -> Int32)> as:

[\(+ x), \(* x), \(/ x)]

Once unboxed closures are implemented, you will need to write:

[\(+ x) box, \(* x) box, \(/ x) box]

This is essentially the same as std::function<int32_t(int32_t)> in C++, which performs boxing internally.

Likewise, the list literal notation [1, 2, 3] will be changed to produce an unboxed array of known size, with a type like Array<Int32, 3>—the same as the type int32_t[3] in C or C++. You will only need to allocate memory when you want this size to be dynamic: [1, 2, 3] box will have the type List<Int32>, equivalent to std::vector<int32_t> in C++.

In the future, I may introduce more concise notations such as {| … |} and [| … |] for boxed closures and lists, respectively. However, the box word has the advantage of being more searchable.

In addition, the box trait will require the +Alloc permission, which will be implicitly granted to all definitions by default. You will be able to waive the permission to allocate by adding -Alloc to a type signature, and this should be very useful for statically guaranteeing that critical code paths allocate no heap memory.


While adding the implicit +Alloc permission, I plan to make other permissions granted by default. For example, +Fail is the permission to abort the program with an assertion failure, and this will be used by default for overflow-checked arithmetic operations. If you waive this permission by adding -Fail to the signature of a definition, then it will be statically guaranteed not to raise any assertion failures.

Because these implicit permissions will be backward-compatible, we will be able to add additional permissions in the future for easy, fine-grained control over low-level performance and safety details. For example, if we make it possible to give type parameters to a permission, then we might add such permissions as +Read<R> and +Write<R> for reasoning about accesses to some region of memory R; with some metadata, the compiler will be able to tell that reads and writes to different memory regions are commutative, enabling it to safely reorder instructions to produce more instruction-level parallelism. This, in turn, should make it easier to write correct high-performance lock-free code.

Furthermore, I plan to extend the permission system to allow permissions to provide data; this could be used to implement such things as dynamic scoping, typeclasses, and Scala-style implicits. Because all terms denote functions, there’s no material difference between an effect (an action the code is allowed to take on the environment) and a coeffect (a constraint on the environment in which some code is allowed to run). So with this small change, Kitten’s permission system will be able to neatly represent both.

As with the free monad approach to extensible effects, these changes will enable the same permission to be executed with different handlers. So you will be able to write a single definition with a user-defined permission (such as +Database) then interpret the same code in different ways (such as accessing a mock, test, or production database) to enable more code reuse and easier testing.


Finally, I’ve been working on figuring out the details of an additional extension to the permission system, which I term assumptions. Whereas permissions are attached to function types to describe their side effects and constraints, assumptions will be attached to values to describe simple invariants. I haven’t quite figured out the syntax for this, but for example, the type List<Int32> @Sorted @NonEmpty might describe a list of integers that is both sorted and non-empty.

The compiler should be able to use these assumptions to produce better error messages, as well as better compiled code, e.g., by eliminating redundant checks. I envision an unshared mutable reference type Owned<T> and a shared reference-counted variant Shared<T>. Assumptions would let you safely claim ownership of a shared reference with a function such as claim with the type Shared<T> @Unique -> Owned<T>.

I can also see this being used to constrain the ranges of numeric types, such as Int32 @Range<0, 1024>.

Like permissions, assumptions will have a subtyping property. It’s fine to pass a List<Int32> @Sorted to a function expecting any old List<Int32>, but not the other way around: you can’t pass any old List<Int32> to a function expecting a List<Int32> @Sorted.

You will be able to imbue a value with assumptions safely using a static or dynamic check:

assumption Sorted<T> (List<T>):
  dup tail \<= zip_with and

Or unsafely using a coercion such as imbue (@Sorted). Various standard functions will produce values with standard assumptions; for example, sort may have the type List<T> -> List<T> @Sorted.

Thinking Forth

As always, contributors are more than welcome—a programming language is a massive undertaking, and I am only one person. Even if you have no experience with compilers, concatenative programming, or Haskell (in which Kitten’s compiler is written), there are plenty of tasks available for a motivated contributor of any skill level. Feel free to look at the current issues, email me directly, or write to the Kitteneers mailing list and I’ll gladly help you help me!


  1. Thanks, this is generally helpful.
    Still, I followed step-by-step your method in this Python Online Training
    Python Online Course

  2. Thanks for sharing this in here. You are running a great blog, keep up this good work.
    Online degree courses
    Distance education

  3. Thanks for sharing this amazing and nice post. In need of the best cheap assignment help uk turnout to Assignments Planet for all assignment services at a cheap price.

  4. Amazing post!I have read all the content of this past.We are offering Research Proposal Writer service to the students at a reasonable price.

  5. It is soo informative. This is such an amazing post.Are you also searching for assignment writing help we are the best solution for you. We are best known for delivering the best services to students without having to break the bank

  6. A very awesome blog post. We are really grateful for your blog post. combat, law enforcement You will find a lot of approaches after visiting your post. I was exactly searching for. Thanks for such post and please keep it up. Great work.

  7. Really impressed! Everything is very open and very clear clarification of issues. It contains truly facts. Your website is very valuable. Thanks for sharing.

  8. I got too much interesting stuff on your blog. I guess I am not the only one having all the enjoyment here! Keep up the good work.

  9. Pretty good post. I just stumbled upon your blog and wanted to say that I have really enjoyed reading your blog posts. Any way I'll be subscribing to your feed and I hope you post again soon. Big thanks for the useful info.

  10. If you are looking to write my assignment uk, your search is to end. Try our Professional Content Writing Services to achieve a higher position in your academic career.

  11. Thanks for sharing this marvelous post. I m very pleased to read this article.

  12. Great blog article. Really looking forward to read more.

  13. Sohbet ve Chat yapmanızı kolay ve güvenli hale getiren Sohbet odaları sorunsuz ve kesintisiz Mobil Sohbet siteleri ile arkadaşlık ve yeni kişilerle tanışma imkanı.

  14. Hey friend, it is very well written article, thank you for the valuable and useful information you provide in this post. Keep up the good work! FYI, shih tzu hair products , axis bank magnus credit card, a thousand splendid suns pdf,10 Lines on Myself In English

  15. Nice post,thanks for the update its an informative post,Truly amazing.
    Backup data

  16. The Ace Data Virtual Vault Cloud backup solution for Office 365 offers an easy way to protect your data.

    Cloud backup solutions

    Office 365 backup

  17. Super interesting. The free monad stuff and handlers sound like all the recent talks on algebraic effect handlers. Which leads me to: do you see something like coroutines making sense in a concatenative language like kitten? I'm general I don't get what asynchronous and concurrent code should like; do we lost the concatenative property? (I.e homomorphism from strings to semantics)