-
-
Notifications
You must be signed in to change notification settings - Fork 2
Home
Kilns is a distributed and concurrent programming language based on the kell calculus. In addition to managed memory, it also has managed concurrency and managed networking. It is a “higher-order” distributed programming language, which means that running processes can be paused and resumed, or even moved between machines. Everything in the language is a process. It takes advantage of the data is code idea so that processes are the data structures.
You can think of this as a function definition to some extent, except with a much richer argument syntax (similar to pattern matching in Haskell or Erlang) – a pattern consists of some combination of messages and kells (the specifics of the patterns allowed depends on the pattern language currently in effect). When the pattern is successfully matched, any variables in the pattern are substituted into the process, and then that process is executed. Some standard pattern pieces are described in the section below called “patterns”.
It is important to note however, is that unlike functions, the execution of a trigger does not return a result.
This sends a message (similar to calling a function), containing the process as an argument. When this message is received, the continuation will be executed. The process and continuation are both optional.
This is a “locality”. You might also think of it as a namespace or something similar. Nested kells give you a hierarchical module structure. Execution occurs within kells. The process is executed. This is the most interesting structure of the language, as they give rise to so many different features. The process and continuation are both optional. Like a message,it can be matched in a pattern, at which point the continuation is executed. This allows for some cool things, IE, suspending processing:
(trigger [foo ?x]
{suspended-foo ?x})
and then when you want to continue running the process later:
(trigger {suspended-foo ?x}
[foo x])
The pattern in a trigger may contain variables which bind parts of the matched processes to be used in the body of the trigger. There are two types of variables - "process variables" which can occur anywhere a process may occur, and "name variables" which may occur only where the name of a message would normally occur. EG, in {?x {test} {?y ?z}}, ?x and ?y are name variables and ?z is a process variable. Also, name variables are only valid in some pattern languages.
The ? prefix is only used when binding (in patterns in forms like trigger and define), to distinguish new variables from variables defined in the lexical context and from names.
A restriction is a scoping mechanism. It guarantees that the name specified will not be visible outside the scope. Therefore you can do something like
(new foo
[foo (some process ...)])
and be sure that nothing outside that restriction can trigger on [foo ?x] and make your process disappear.
Parallel composition allows you to include multiple kells, messages, triggers, and restrictions at the same level of a process or pattern. Since the language is concurrent, the basic collection is a set rather than a list - all the processes in a parallel composition execute concurrently.
The null process does nothing. It is the default value for omitted processes and continuations.
If trigger is a function, define is a macro. It is an abstraction of a process. It allows you to define complex processes that you want to use in multiple places, with a few key pieces changed.
Various very basic pieces are built on top of of those primitives and provided with the language. Here are a few.
This is basically identical to trigger, but while trigger will only match once then disappear, trigger* will match repeatedly.
Sometimes you don't want to have to tag every parameter with a name. In cases like subtraction, order is important, and you don't want to have to say {- (par {minuend 5} {subtrahend 3})} when {- (list 5 3)} should suffice.
This runs your process in isolation, so no messages can get in or out. Once your computation is finished (which is indicated by process sending the result over result-channel), any leftover kells, messages, triggers, etc. in process are destroyed.
To some extent, a pattern looks just like a process. The exact details differ based on the pattern language, but some parts are pretty consistent.
It looks like a process, but can't contain triggers, restrictions, or the null process. The processes can have “holes” represented by process variables. These are like the function parameters. When triggered, the processes that map to the variables will be substituted throughout the body of the trigger.
The top level of a pattern is somewhat special – it's the part of the pattern that maps to the currently-live messages and kells that will be captured.
Where something that behaves like a normal function might look like:
;;; receives a message named "one" with two slots, and executes one of the two
;;; (non-deterministically).
(trigger {one (par ?x ?y)}
x)
kilns also allows triggers that match on multiple messages or kells
;;; receives a message named "add-process" and adds the process to the
;;; process-collector kell
(trigger (par {add-process ?x} [process-collector ?y])
[process-collector x y])
Messages matched at this top level can be tagged with a direction. Without this, triggers can only match on messages in the current scope, and that would mean that each kell is completely isolated from every other kell – making them a rather uninteresting feature. The direction tag allows messages to be matched from either the parent kell (up) or a nested subkell (down).
Here are some examples:
;;; local pattern
[outer [inner {test}]
{test}
(trigger {test} {matched})]
{test}
after a reaction, what will be left is:
[outer [inner {test}]
{matched}]
{test}
You can see that {test} in the "outer" kell and the trigger that received it are gone. In their place is the result of the trigger, {matched}. This is the default behavior. But if you add a tag in the trigger, it changes:
;;; down pattern
[outer [inner {test}]
{test}
(trigger (down {test}) {matched})]
{test}
results in:
[outer [inner]
{test}
{matched}]
{test}
Now {matched} is in the same place, but rather than {test} in the outer kell going away, this time the one in the inner kell has disappeared. The down tag made it look for a message one level more deeply nested. The up tag has the opposite effect:
;;; up pattern
[outer [inner {test}]
{test}
(trigger (up {test}) {matched})]
{test}
results in:
[outer [inner {test}]
{test}
{matched}]
Now the outermost {test} is gone. This is the mechanism used to share data between different levels. You can only ever talk across one barrier. The usefulness of this limitation will be explained.
Now, you might be thinking, "What happened to the trigger after it matched?" If it's supposed to approximate a function, shouldn't it stick around? After all, you can call a function more than once.
It's true, they disappear, but using the primitives we already have, we can define the Y combinator, and use that to define trigger*, which is just like trigger, but sticks around after a match. This is the real function approximation. For details on how this is done, check “replication.kiln”.
As mentioned before a kell is a “locality”. It's a space within which execution is isolated, except by explicit use of the direction tags in a message pattern. Kells are multi-purpose. As mentioned, they allow us to isolate execution. This gives us a way to build namespaces/packages/modules/components/etc. so libraries can be created with encapsulation and public/private “methods”.
But there are other places where such isolation is helpful. Distributed programming has had a number of failures with names such as RPC, CORBA, etc. The problem with these approaches is that they try to make processing across machines transparent. It looks like a function call, but it may have long latency, or the machine on the other end may be down. [find the Steele (I think) article about the insurmountable problems with this approach].
Kells allow you to model distributed processing, with a kell at some level representing a machine and communication above this level being network traffic. In fact, since kells are nestable, you can create a hierarchical model of accessibility. The outermost level might represent communication over the Internet, the next depth could be LANs in various locations around the world, the next could be clusters of machines with low-latency connections, followed by kells representing machines. And those machine kells could be further split into kells that represent a chunk of accessible memory (which could be useful if you're on a NUMA architecture, where different CPUs have different areas of memory that are considered “local”).
Kilns can also model failure of nodes, so in tests on a single machine, you can see how your system is affected if some chunk of the production cluster were to just disappear from the network.
Unfortunately, I haven't yet implemented the distributed aspect of the language. Some considerations include:
- simple tagging of what layers require ssl/encryption
- communication protocol at different layers (TCP/IP would work for all, and probably a valid initial approach, but will need to add more)
- informing each instance which kell should be considered "top" for that instance. Above which all behavior is networked
Kells also allow for clean hot upgrades. The file “simple-components” provides very short definitions to illustrate this. You can load a component with (load-component "xml-component" xml), which effectively does
[xml (load "xml-component")]
with very little extra magic added. If you later make changes to xml-component.kiln, (replace-component "xml-component" xml) will update it, doing
(trigger [xml ?state] (load-component "xml-component" xml))
This completely removes the previous component, then loads the new version fresh. Unlike with languages like Common Lisp, old methods or functions that are no longer defined in the component will get deleted – they won't linger around causing transient bugs.
Kells allow us to model IO functionally. If there is a file "sample" with the bytes "abc", then this is represented in our model as:
;;; A string "abc" is actually the process (par {1 "a"} {2 "b"} {3 "c"}), which can
;;; be shortened to (list "a" "b" "c") using the definition in utilities.kiln
[sample (list "a" "b" "c")]
with triggers like the following:
(trigger* {append-to-kell {?name ?process}}
(trigger [name ?original-state] [name (list original-state process)])
(trigger* {print {name {?name}} {string ?string}}
{append-to-kell {name string}})
the message:
{print {name {sample}} {string "def"}}
will result in a new kell that looks like
[sample (list "abc" "def")]
Ta-da! File operations, modeled cleanly.
Here are a few things that I consider “unsolved” at this point.
- The kell calculus has no mechanism for sharing components. If you want to use a component in multiple places it gets loaded multiple times and exists in each place. There have been extensions proposed to add this, but none seem very attractive.