Differences

This shows you the differences between two versions of the page.

--- notes:internals:db [2025/09/06 22:51] – smj-edison
+++ notes:internals:db [2025/09/08 19:27] (current) – smj-edison
@@ Line 1: / Line 1: @@
-====== Database ======
+====== Database (folk2) ======
-Folk's database stores all Wishes, Claims, Whens, and Holds. Essentially, it stores everything that happens
+//If you want to follow along in the code, all of these things are implemented in trie.c, db.c, folk.c,
-in Folk. The database works with Statements, either inserting or removing them. All those verbs I mentioned—
+and prelude.tcl.//
-Wish, When, etc—are functions that insert a Statement into the database. We'll cover removal later.
-So, what is a Statement? A Statement consists of three parts: the Clause, the child matches, and metadata.
+Folk's database stores all Wishes, Claims, and Whens. Essentially, it stores everything that happens
-Let's start with the Clause: a Clause is an array of words, with each word known as a Term. An example
+in Folk. The data type of this database is a Statement. Statements are inserted when calling
-Clause, "the sky is blue", would become ["the", "sky", "is", "blue"]. We'll cover child matches and metadata
+Wish, Claim, and When.
-in a bit.
-Let's see what happens when we run Claim.
+===== Statements =====
-<code>Claim the sky is blue</code>
+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.
-When this code runs, it will generate a Clause containing  "current-file.folk claims the sky is blue".
+=== Wishes and Claims ===
-Notice there's a part that was prepended to the beginning, "current-file.folk claims". This tells the
+Statements are inserted when running the core commands—Wish, Claim, and When—by calling a command called
-database what file this Claim came from, and that it's a Claim, not a Wish. This same thing applies to
+Say. Say inserts the provided Statement into the database.
-Wishes, except with "wishes" instead of "claims".
+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 the sky is /color/ { # code here }
+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
+  - We add "when" to the beginning, so the database knows this is a When.
-  - We add "with environment {foo bar}", as tcl doesn't capture scopes. We manually capture the scope
+  - We preserve both the query and the code (that's the "the sky is /color/ { # code here }" part).
-instead. We'll use this to execute the When later
+  - 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.