Folk Computer

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Database (folk2) ======

//If you want to follow along in the code, all of these things are implemented in trie.c, db.c, folk.c,
and prelude.tcl.//

Folk's database stores all Wishes, Claims, and Whens. Essentially, it stores everything that happens
in Folk. The data type of this database is a Statement. Statements are inserted when calling
Wish, Claim, and When.

===== Statements =====

So, what is a Statement? A Statement consists of two parts: the Clause and the child matches*.
Let's start with the Clause: a Clause is an array of words, with each word known as a Term†. An example
Clause, "the sky is blue", would become ["the", "sky", "is", "blue"]. We'll cover child matches in a bit.

=== Wishes and Claims ===
Statements are inserted when running the core commands—Wish, Claim, and When—by calling a command called
Say. Say inserts the provided Statement into the database.

Since Wish is a command that inserts a Statement, let's see what happens when we run it.

<code>Wish the sky is blue</code>

When this code runs, it will generate a Clause containing "current-file.folk wishes the sky is blue".
Notice there's a part that was prepended to the beginning, "current-file.folk wishes". This tells the
database what file this Wish came from, and that it's a Wish, not a Claim. This same thing applies to
Claim, except with "claims" instead of "wishes".

=== When ===
One other important thing is Whens are also stored in the database. Let's continue with the previous example,
except with a When this time:
<code>
set foo bar
When /someone/ wishes the sky is /color/ { # code here }
</code>
This will insert the following: "when the sky is /color/ { # code here } with environment {foo bar}".
There's quite a bit happening here, so let's break it down:

  - We add "when" to the beginning, so the database knows this is a When.
  - We preserve both the query and the code (that's the "the sky is /color/ { # code here }" part).
  - We add "with environment {foo bar}"‡, as Tcl doesn't capture scopes. We manually capture the parent scope instead (containing the variable "foo" with the value of "bar"). We'll use this to execute the When later.

==== Reacting to Statements ====
Now that you're familiar with the concepts at play, let's look at what happens when we insert a When followed
by a Wish. I'll italicize the new parts.

<code>
set foo bar
When /someone/ wishes the sky is /color/ { # code here }
</code>
DB inserts: "when /someone/ wishes the sky is /color/ { # code here } with environment {foo bar}"
<code>Wish the sky is blue</code>
DB inserts: "current-file.folk wishes the sky is blue"

//database queries for "when the sky is blue /lambda/ with environment /env/".//

//database gets back the When, and schedules it to be run with this Statement.//

Wait wait, what?? That was a lot all at once. Let's break it down.

First, the context. We just inserted a Statement, so we need to check if there's any existing
Whens that match. So, we do a database query. But what kind of query? Well, let's convert this Wish into
what a When would look like for this Statement. The easiest way to explain this is to just look at a
before and after.
Before: "current-file.folk wishes the sky is blue"
After: "when current-file.folk wishes the sky is blue /lambda/ with environment /env/"
Now, if you line up the When term-by-term with the Wish, you'll see these line up beautifully:
<code>
when  /someone/          wishes  the   sky   is    /color/   { # code here }  with  environment  {foo bar}
same  variable           same    same  same  same  variable  variable         same     same      variable
when  current-file.folk  wishes  the   sky   is    blue      /lambda/         with  environment  /env/
</code>
Note that it doesn't matter if a variable is on top or below, as they're essentially a wildcard.

Our "whenized" statement is now a query that will find all the applicable Whens, as it does in this example.

=== When scheduling ===
One exciting thing about folk2 is its support for multithreading. It supports this by scheduling each When
to run on a thread pool. That means that when a Statement matches with a When, it needs to be queued for the next
available thread to pick it up. That's exactly what happened in this example. The Wish got inserted,
it checked for matching Whens, and then when it found a match, it pushed it to the work queue to be run
as soon as a thread is available.

In fact, when this queued item runs, it is known as a Match. This Match contains a list of child
statements, which we'll get to in a bit.

=== Statements and Matches ===
The interplay of Statements and Matches is how Folk tracks dependant statements. That sounds like a lot,
so let me break it down with some pictures:

We start with the When Statement, "When /someone/ wishes the sky is /color/ { # code here }":

{{:notes:internals:db-statement-1.jpg?600|}}

Now let's add the Wish, "Wish the sky is blue":

{{notes:internals:db-statement-2.jpg?600|}}

And presto! The database matched the two together, and now there's a match running.

{{notes:internals:db-statement-3.jpg?600|}}

Now let's say instead of just having "When /someone/ wishes the sky is /color/ { # code here }", we added
a label to it:
<code>
When /someone/ wishes the sky is /color/ {
    Wish $this is labelled $color
}
</code>

{{notes:internals:db-statement-4.jpg?600|}}

Note how "Wish $this is labelled blue" is a //child// of the Match. This is very important. We'll see why
when we need to remove Statements.

Let's add one more Wish, "Wish the sky is pink":

{{notes:internals:db-statement-5.jpg?600|}}

Its Match:

{{notes:internals:db-statement-6.jpg?600|}}

And finally its sub-Statement:

{{notes:internals:db-statement-7.jpg?600|}}

This tree (well, technically a directed acyclic graph) of alternating Statements and Matches is how all
facts and running code is tracked in Folk. Hopefully you're still following, we're just about done!

==== Statement removal ====
What happens if we were to remove a Statement? Let's what happens if we remove "Wish the sky is pink".

First off, we'll look at its children, which is really just one child in this case.

{{notes:internals:statement-removal-1.jpg?600|}}

We'll go ahead and remove that Match.

{{notes:internals:statement-removal-2.jpg?600|}}

In the process, we'll also note that that Match also had a child Statement, and we'll remove that too:

{{notes:internals:statement-removal-3.jpg?600|}}

Now you see why we had to keep track of what caused what? That way when we need to remove a Statement,
we recursively remove its children as well.

==== Conclusion ====
Hopefully by now you understand what Statements are, how Wishes merge with Whens, how Matches work,
how code is executed, and how Statements are removed!

If you'd like to learn about how database queries work, head over to the [[notes:internals:trie|The Trie]]
article.

If you'd like to learn more about the guts of the database, be sure to check out db.c. Some good functions
to start with are dbInsertOrReuseStatement, dbInsertMatch, statementRemoveSelf, and matchRemoveSelf.
There's also some goodies in folk.c, namely runWhenBlock, whenizeClause, and reactToNewStatement.

=== Footnotes ===
* Also metadata and keep time, but this article is already long enough.

† This is a little misleading, as a Statement can have Terms with spaces in them. For example,
the last Term in `Wish $this has name "Mason Jones"` has spaces in it. It's just that in Tcl, lists are
space seperated by default, and all the database commands are called from Tcl.

‡ This is simplified for explanation reasons. This is actually a list of environments, with each
entry being one level higher in the call stack.