Differences

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

--- notes:internals:db [2025/09/07 00:06] – [Reacting to statements] smj-edison
+++ notes:internals:db [2025/09/08 19:27] (current) – smj-edison
@@ Line 1: / Line 1: @@
-====== Database ======
+====== 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, Whens, and Holds. Essentially, it stores everything that happens
+Folk's database stores all Wishes, Claims, and Whens. Essentially, it stores everything that happens
-in Folk. The database works with Statements, either inserting or removing them. All those verbs I mentioned—
+in Folk. The data type of this database is a Statement. Statements are inserted when calling
-Wish, When, etc—are functions that insert a Statement into the database by calling the Say function.
+Wish, Claim, and When.
-We'll cover Statement removal later.
 ===== Statements =====
-So, what is a Statement? A Statement consists of three parts: the Clause, the child matches, and metadata.
+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
+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 and metadata
+Clause, "the sky is blue", would become ["the", "sky", "is", "blue"]. We'll cover child matches in a bit.
-in a bit.
-=== Wish and Claim ===
+=== Wishes and Claims ===
-Let's see what happens when we run Wish.
+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>
@@ Line 38: / Line 39: @@
   - 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.
+  - 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 ====
+==== 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.
@@ Line 52: / Line 53: @@
 DB inserts: "current-file.folk wishes the sky is blue"
-//DB queries the database for "when the sky is blue /lambda/ with environment /env/".//
+//database queries for "when the sky is blue /lambda/ with environment /env/".//
-//DB gets back the When, and schedules it to be run with this Statement.//
+//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, back to the context. We just inserted a Statement, so we need to check if there's any existing
+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 if for this Statement. The easiest way to explain this is to just look at a
+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"
@@ Line 66: / Line 67: @@
 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}
+when  /someone/          wishes  the   sky   is    /color/   { # code here }  with  environment  {foo bar}
-same  variable           same    same  same  same  variable variable         same     same      variable
+same  variable           same    same  same  same  variable  variable         same     same      variable
-when  current-file.folk  wishes  the   sky   is    blue     /lambda/         with  environment  /env/
+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.
@@ Line 75: / Line 76: @@
 === When scheduling ===
-One exciting thing about folk2 is its support for multithreading. It does this by running each When
+One exciting thing about folk2 is its support for multithreading. It supports this by scheduling each When
-on its own thread. That means that when a When matches with a Statement, it needs to be queued for the next
+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.