The kcats Programming Language

See Releases. Binaries currently do not have installers, you will need to place the executable in a convenient place and chmod it (on mac/linux).

You can skip this section if you're using pre-built binaries described above.

It can be checked out from git or viewed here: Production Source

See emacs-ide.org in the source tree for more info.

Now that we know the very basics, we can explore and learn as we go. Kcats lets you treat the standard library (the dictionary) as data, and you can process it with… itself. Documentation is in there. You just need to know how to ask for it. So here's how you do it, and you'll understand how exactly it works later.

In all the examples in this document, you can run them on the command line, by running kcats -p, followed by the program in single quotes, like this:

kcats -p 'dictionary lingo [first] 🚜 ▶️ [] sort'

In case you want to view it in its entirety, the standard library is part of the source, it lives in the lexicon file.

This program retrieves the dictionary of the current environment, and prints just the name of each, sorted in alphabetical order.

dictionary lingo [first] 🚜 ▶️ [] sort

[#️⃣⛏️ * + - / < <= = > >= abs addmethod advance and animate assemble assert assign
 association association? assocify
 attend autoformat bail bailer bits both both? break breakpoint butlast bytes? cache
 capture catcher ceiling character close collect combinations compare
 compare-by confine contains? cram cut database days dec decache decide decodejson
 definition dictionary dictmerge dipped draft drain dropper dump each
 emit empty empty? encode encodeitem encodejson ends? entry environment environment?
 error? eval-step evaluate evaluator even? exp extractor fail file-in file-out
 finished? first flatten flip floor fold format frequencies future generator get group
 handle handoff hashbytes heatmap hours inc indexed indexer
 indexof inscribe inspect integer? integers interpose intersection keep key label
 last let liberator lingo list? log max max-by method? milliseconds
 min min-by minutes mod module namespace negative? number number? odd? or over pad
 pair pair? parse parse-edn parse-utf8 partition persist
 pipe-in pipe-out pipe? pop positive? prepend primrec print produce quot radix random
 range read reap receiver reduce rem remove repetition
 resolve rest restore resume retry reverse round second seconds select sender serversocket
 set set? sign skipper sleep slice slurp socket
 something? sort sort-indexed spawn spit splitter sprint sqrt stage standard starts?
 stepper string string? taker timer times timestamps top tos
 tracer triplet tunnel type unassign under unnamespace until update updates use using
 value verify walk when within? word word? words
 xor zero? zip ••🐋 ••👥 ••📮 ••🗑️ ••🛡️ ••🪄 •🐋 •👥 •📮 •🔀 •🗑️ •🛡️ •🪄 ↔️ ⏳ ▶️ ☯️
 ⚓ ⚖️ ⛏️ ✅ 🌀 🍫 🎁 🎒 🎭 🏷️⛏️ 🐋 👥 💉 💯 📏 📣 📤 📮 📸 🔀
 🔍 🔗 🗑️ 🚜 🛟 🛡️ 🧤 🧦 🧲 🧹 🩹 🪄 🪆 🪜]

Even though the rest of this document will explain a lot of these words and how they work, the above program does the following:

• dictionary retrieves the currently active dictionary
• lingo returns the active words of the dictionary on the stack
• [first] 🚜: for each word/definition pair in the dictionary, take the first, which is the word.
• [] sort: sort takes a program to transform each item in the list it's sorting, to use for comparison. We want to use the word itself for comparison, so we don't need to transform it at all, hence the empty program.

The specification of a word's input and output types is stored in the dictionary too. It's in the property called spec. Let's say you're interested in the word swap.

dictionary lingo [🔀 spec] 🔍

[[[item a]
  [item b]]
 [[item b]
  [item a]]]

What this program does is fetches the dictionary words, then looks up the swap definition, then within that definition, looks up the spec property.

In the result, what we have here is two lists - the spec of the input, and the spec of the output.

The input spec is [[item a] [item b]]. The output spec is [[item b] [item a]]. What it's telling you is that it requires two items on the stack, any two, we'll call them a (on top) and b beneath. There may be more items below that but they won't be touched. When swap is finished, a and b will have their places swapped so that b is on top. And in fact that's what we get:

"b" "a" 🔀

"b" "a"

For more details see 5.5.3.

Remember the top of the stack is printed first, and so b is now on top.

The format of an input or output spec is a list of either a type or a type/name pair. For example, an input spec of [[integer age] [string name]] means the function takes an integer representing an 'age' on top of stack, and a string representing a name beneath that. The names are for documentation only. You can also leave out any name eg [integer string] is functionally the same spec, just less descriptive. Not all inputs or outputs need to be named, [integer [string name]] is also a valid input spec.

Some words have arbitrary stack effects because, for example, they run an arbitrary program or replace the stack. The output spec for these types of words are specified as [*]. Some examples of such words are ▶️ or restore.

dictionary lingo [🔀 examples] 🔍

[[[1 2 3 🔀] [1 3 2] "Swap top two items"]
 [[🔳 ✅ 🔀] [✅ 🔳] "Swap boolean values"]
 [[42 "hello" 🔀] ["hello" 42] "Swap number and string"]
 [[🔳 "" 🔀] ["" 🔳] "Swap Nothing and empty string"]
 [["a" "b" 🔀] ["b" "a"] "Swap strings"]
 [[[1 2] [3 4] 🔀] [[3 4] [1 2]] "Swap lists"]
 [[[1 [2]] [3 [4]] 🔀] [[3 [4]] [1 [2]]] "Swap nested lists"]
 [[[[🔳]] 🔳 🔀] [🔳 [[🔳]]] "Swap deeply nested empty list with empty list"]
 [[1 2 3 🔀 🔀] [1 2 3] "Double swap"]
 [[1 2 🔀 3 🔀] [2 3 1] "Interleaved swaps"]
 [[1 2 🔀 🗑️] [2] "Swap then trash"]
 [[42 42 🔀] [42 42] "Swap identical numbers"]
 [[🔳 🔳 🔀] [🔳 🔳] "Swap identical empty lists"]
 [[[1 2] [1 2] 🔀] [[1 2] [1 2]] "Swap identical complex lists"]
 [[[🔀] [🗑️ "Need 2 items to swap"] 🩹 ▶️] ["Need 2 items to swap"] "Empty stack"]
 [[[1 🔀] [🗑️ "Need 2 items to swap"] 🩹 ▶️] ["Need 2 items to swap"] "Only one item on stack"]]

This is a list of examples, and each example is a pair or triple:

• A program that calls the given word
• A program that doesn't call the word that gives the same result ³
• An optional description of what the example is demonstrating

Use the same technique to explore other words. You can simply replace the word in the code snippets above with some other word. Here's how you find the examples for =, which tests for equality of two items - just replaced swap with =.

dictionary lingo [= examples] 🔍

[[[1 2 =] [[]] "Different Numbers are not equal"]
 [[1 1 =] [✅] "Same numbers are equal"]
 [[1 1 =] [✅] "Same value integer and float are equal"]
 [[[1] [] =] [[]] "Number and Nothing are unequal"]
 [[[1 [[]]] [1 [[]]] =] [✅] "Same nested list with numbers are equal"]
 [[[1 ["foo"]] [1 ["foo"]] =] [✅] "Same nested list with string are equal"]
 [["hi" "hi" =] [✅] "Same strings are equal"]
 [["hi" "there" =] [[]] "Different strings are unequal"]
 [[\h \h =] [✅] "Same characters are equal"]
 [[\h \i =] [[]] "Different characters are unequal"]
 [["hi" encode "hi" encode =] [✅] "Same bytes are equal"]
 [["hi" encode "there" encode =] [[]] "Different bytes are unequal"]
 [[[] ✅ =] [[]] "Different booleans unequal"]
 [[[1 ["foo"]] [1 ["bar"]] =] [[]] "Nested lists with different strings are unequal"]
 [[[] [] =] [✅] "'Nothing' is equal to itself"]
 [[[] [] association =] [✅] "List/Association empty container types are equal"]
 [[[] [] set =] [✅] "List/Set empty container types are equal"]
 [[[[a b]] [[a b]] association =] [[]] "Nonempty List/Association types are unequal"]
 [[[1 2 3] set [3 1 2] set =] [✅] "Sets constructed from different lists are equal"]]

Data types are automatically converted when needed.

For example, if you have a list of pairs and you use the word 🔍, it assumes your intention is to use the list as an associative data type, so it will be automatically converted, and remain converted after lookup completes.

You can often tell by the spec when the return type is a promoted type:

dictionary lingo [assign spec] 🔍

[[[item value]
  [list keys]
  sized]
 [association]]

Here you can see that the spec for assign takes a sized and returns an association. This allows you to do things like this:

[[name "Susie"] [age 25]] [sport] "bowling" assign

[[age 25]
 [name "Susie"]
 [sport "bowling"]]

The initial value of [[name "Susie"] [age 25]] is not an associative, it's just a list. You could explicitly convert it using the word association but assign will do it for you, because it is a function that operates on an associative type.

Note that the conversion can fail, because converting to associative requires that you have a list of pairs. If you don't, that's an error:

["foo" "bar"] [age] 25 assign

[[actual "foo"]
 [asked [pair]]
 [handled []]
 [reason "type mismatch"]
 [type error]
 [unwound [assign]]]
25 [age] ["foo" "bar"]

The most common promotion is from list to associative but there are others.

Kcats lets you see what the input an output for a given word should look like. You can specify what kinds of data should be at each place on the stack, both before and after the word executes.

Let's look at an example, for + that adds numbers:

dictionary lingo [+ spec] 🔍 

[[number number]
 [number]]

That means, the input is two numbers, and the output is one number. In terms of stack locations, the top of the stack comes first in the input or output spec.

When the actual stack values don't match, we get an error due to the spec check:

"foo" "bar" +

[[actual "bar"]
 [asked [number?]]
 [handled 🔳]
 [reason "type mismatch"]
 [trace 🔳]
 [type error]
 [unwound [+]]]
"bar" "foo"

Currently only input specs are enforced, and all specs are optional (they default to [[][]] which means "don't look at any stack items".

Specs can get more complicated, for example, instead of just specifying a type number, they can give a helpful name like [number x]. Names that match should be the equal values - for example:

dictionary lingo [👥 spec] 🔍

[[[item a]] [[item a]
             [item a]]]

The word 👥 takes an item called a, and leaves two items called a. So we can see 👥 duplicates the item on top of the stack.

Sometimes the word executes another program on the stack, that's not known until runtime, and therefore we can't predict what effect it will have. Specs show this unknown effect with *. For example:

dictionary lingo [🪄 spec] 🔍

[[program [item a]]
 [[item a]
  *]]

In this case, all we know about the output is [item a] will be on the top of the stack, what's beneath that depends on what the program does.

There are words that operate on multiple types, and it's helpful to talk about what those types have in common. Specs use these traits to describe groups of types that a word will accept or produce.

The most important expressive feature of kcats is that you can manipulate programs exactly the same way as you can any other data.

One thing you can do with a list, is treat it like a program and ▶️ (execute) it. Notice that on the 5th and 6th line of the execution trace below, the word ▶️ takes the list from the top of the stack on the left, and puts its contents back on the right, making it part of the program remaining to be run!

;;   stack  |  remaining program
;; ---------|--------------------
            | 4 5 6 [* +] ▶️ inc
          4 | 5 6 [* +] ▶️ inc
        4 5 | 6 [* +] ▶️ inc
      4 5 6 | [* +] ▶️ inc
4 5 6 [* +] | ▶️ inc
      4 5 6 | * + inc
       4 30 | + inc
         34 | inc
         35 |

Note that, when * + gets moved back to the program, it went in front of inc.

The same way we used 🔗 to combine two lists, we can combine two small programs into one, and then ▶️ it:

4 5 6 [+] [*] 🔗 ▶️ 

44

Note that words inside lists don't perform any action when the list is put on the stack. You can think of it as a quotation - a message being being passed along, not acted upon.

One important theme of programming kcats is combining program snippets in various ways, and then ▶️ them to actually carry them out. There are lots of program "modifiers" to help.

What are modifiers? They are programs that modify other programs.

Here's an example from everyday life: "When you're following the cake recipe, if any ingredients are missing, go to the bake shop on Main Street to get them. And when it calls for brown sugar, use molasses instead". You're taking the existing instuctions (the recipe of how to make a cake), and wrapping it in larger instructions that specify things outside the scope of the recipe (where to get ingredients) and also change the recipe (substitute ingredients). When you follow instructions in everyday life, you're running a program, and we routinely find modifiers to programs out there in written English instructions.

Let's look at some building blocks of kcats that modify existing programs.

Let's take a look at a simple example:

"foo" "bar" "baz"
[[a 1️⃣]
 [b 2️⃣]
 [z 3️⃣]]
🎒 

[[a "baz"]
 [b "bar"]
 [z "foo"]]

Notice that the numbered placeholders 1️⃣ 2️⃣ etc refer to places on the stack: 1️⃣ is the top, 2️⃣ is the 2nd stack item etc. 🎒 takes values from the stack and inserts them into the template.

Again, let's look at a simple example, that calculates the total cost of an inventory of smartphones.

[[smartphone [[pricing [[quantity 2]
                        [discount 0.15]
                        [price 699.00]]]
              [description "Worlds most advanced smart phone"]]]
 [laptop [[pricing [[quantity 4]
                    [discount 0.10]
                    [price 1699.00]]]
          [description "Worlds thinnest laptop computer"]]]] assocify

[[smartphone
  [[pricing [[price 1️⃣]
             [discount 2️⃣]
             [quantity 3️⃣]]]]]] assocify 
#️⃣⛏️ * * 

209.7

Notice that here we're doing the opposite of 🎒 - extracting values back out of the filed in structure and putting them on the stack. We mark the items to be extracted using numbered markers, that correspond to places on the stack.

But why do we need to call assocify here? Answer: If we don't, then kcats does list matching, where order matters. What happens if we forget assocify?

[[smartphone [[pricing [[quantity 2]
                        [discount 0.15]
                        [price 699.00]]]
              [description "Worlds most advanced smart phone"]]]
 [laptop [[pricing [[quantity 4]
                    [discount 0.10]
                    [price 1699.00]]]
          [description "Worlds thinnest laptop computer"]]]] 

[[smartphone
  [[pricing [[price 1️⃣]
             [discount 2️⃣]
             [quantity 3️⃣]]]]]]  
#️⃣⛏️ * * 

[[asked [price quantity =]]
 [handled 🔳]
 [reason "match failed"]
 [trace [#️⃣⛏️]]
 [type error]
 [unwound [⛏️ 🗑️ reverse 🍫 * *]]]

Here we see a mismatch because in the pricing association, in the data quantity is first, but in the pattern, price is first. The error message is telling us what specifically didn't match.

Wildcards are supported inside lists. Use the word _ to indicate that any value should match at that position:

[a 12 "foo" "mydata" 13]
[a _ _ 1️⃣ 13]
#️⃣⛏️

"mydata"

Wildcards aren't used in associations - if you want to match "any value" for an association key, just leave it out of the pattern. Matching "any key" for a given value, is not supported.

If you want to destructure a bunch of values, or just don't want to put multiple values onto the stack, you can also destructure into an association. Instead of numbered placeholders, you'll use names. But in order to differentiate between placeholders and other words, you'll need to prefix the word with the tag character 🏷️, and use the word 🏷️⛏️ to execute the destructuring.

[[name "Alice"]
 [age 25]
 [sex f]
 [address [[street "Main St."]
           [number 123]
           [zip 12345]]]] assocify
[[name 🏷️cust-name]
 [age 🏷️cust-age]
 [address [[zip 🏷️cust-zip]]]] assocify
🏷️⛏️

[[cust-age 25]
 [cust-name "Alice"]
 [cust-zip 12345]]

One unusual and important feature of kcats is that you can program the runtime. What does that mean? It means you can control exactly how a program is executed.

Why would you want to do that? Well, one common use case is that you want to debug the program: you'd like to manually control execution while you examine the state of the program, to figure out where it's going wrong.

Another use case is security: you want to execute a program but not allow it to access things that programs normally can access (like the filesystem or network). You also don't want the program to be able to permanently redefine what words mean.

So how exactly do we alter how programs are executed? A kcats program keep track of 3 things as it is running, its state: the stack (the data the program is working with), the program (the remaining instructions left to be executed), and the dictionary (the words that have meaning in a program). We call the whole state an environment, and we can create and work with environments in kcats just like any other data, including executing the progams within them.

First let's look at how to create an environment:

[[program [1 2 +]]] environment

[[dictionary [[modules [#b64 "core"]]
              [words 274_entries]]]
 [program [1 2 +]]
 [stack 🔳]]

Notice how `environment` takes an association and fills out the `dictionary` and `stack`. Why does it say `270<sub>entries</sub>`? Normally dictionaries would be printed out in their entirety, just like any other data, but because they're large (there are hundreds of words) by default the runtime prints it as the count of the words.

So this is an environment. What words are useful here? Well, first of all we can treat it as an association, which it is. Here we replace the last item in the program so we're subtracting instead of adding.

[[program [1 2 +]]] environment
[program] [pop 🗑️ [-] 🔗] update

[[dictionary [[modules [#b64 "core"]]
              [words 274_entries]]]
 [program [1 2 -]]
 [stack 🔳]]

Ok, well, this is not that exciting, if environment is just another kind of association right? Point taken, but now let's use the word `eval-step`:

[[program [1 2 +]]] environment
eval-step

[[dictionary [[modules [#b64 "core"]]
              [words 274_entries]]]
 [program [2 +]]
 [stack [1]]]

That evaluates the environment one step! We can do two more steps to finish the program:

[[program [1 2 +]]] environment
[eval-step] 3 times ▶️ 

[[dictionary [[modules [#b64 "core"]]
              [words 274_entries]]]
 [program 🔳]
 [stack [3]]]

One hard rule of kcats: "an environment cannot change its own dictionary".

What does this mean for being able to define new behavior? If we can't alter the current dictionary to add or modify words, what can we do? Answer: you can run your program inside another environment, with a different dictionary.

This has some important security benefits that most languages do not have.

• There are no global redefinition attacks that communities like Javascript and Python have suffered through many times. (Where a compromised library replaces a common function with an attack payload, and the user's own code trips over it later when calling the common function)
• It's possible to completely disable further modifications, for use cases where security takes precedence over expressivity. This is not possible in other dynamic languages.

Let's look at how kcats accomplishes this. The word dictionary retrieves the current dictionary and places it on the stack. Then we can treat it like any other data and alter it. Then we can create a new environment and evaluate that environment, and retrieve its stack.

Doing this with low level constructs looks like this:

;; Fetch the current dictionary
dictionary
;; Create a new set of words
[[square [👥 *]]] draft
;; apply the change to the dictionary
[words] 🔀 update
;; The program to run with the new dictionary
[9 square]
;; Create an environment and evaluate it
[program dictionary] label
environment evaluate
;; make the inner stack the new stack
[stack] 🔍 restore
;; note the current dictionary is not altered
dictionary [words square] 🔍

🔳 81

Obviously this is quite cumbersome, so there are higher level words to do all of this for you, like let.

The most straightforward and common change you can make to the dictionary, is to add a word that wasn't in there before, and use it in some limited scope after which it is no longer accessible.

The word let is handy for small bits of code where you don't want to repeat yourself:

[[square [👥 *]]]
[9 square 8 square +]
let ▶️

145

Let's break this down. The word let takes two arguments, a list of new words paired with their definitions, and a program to run that uses those words. We define a new word square to mean [👥 *], and then we create a program that runs [9 square 8 square +] inside an environment with the new word square defined. Then finally execute that program to get 145.

The list of new words can even refer to another word from the same list:

[[square [👥 *]]
 [fourth [square square]]]
[3 fourth]
let ▶️

81

Words you're defining can refer to themselves - recursive functions are great!

[[factorial [[🔀 positive?] 🛡️
             [🗑️ [*] •🛡️ ▶️ [dec] 🪄 factorial]
             when ▶️]]]
[9 1 factorial •🗑️]
let ▶️

362880

Creating new words is relatively safe - presumably no one is using those words, so giving them meaning doesn't cause any confusion. It's when you start changing an existing meaning that things get a bit complicated.

As we have seen, words perform actions, and those actions are specified by other words. So a word foo can use the word bar as part of its execution. So let's say I change the meaning of the word bar. Does that mean I changed the meaning of foo as well (because bar is part of the meaning of foo)?

The answer is it depends.

In kcats, by default, the answer is no. When you are changing the meaning, it's for you own immediate use of the word. Let's go over some examples.

Let's say we want to alter the meaning of a rather important word that's used all over the place in the standard library: 🗑️. "When I say 🗑️ I want to just insert the number 5."

[[🗑️ [5]]]
["a" "b" "c" 🗑️]
let ▶️ 

5 "c" "b" "a"

Ok, straightforward enough, right? But what happens if we call another word that uses 🗑️, like times? First let's look at the definition of times, to see that it really does call 🗑️:

[times] definition

[[1️⃣ [positive?] 🛡️ [🗑️ dec [2️⃣ 👥 🪄] 🪄 times ▶️] [🗑️] ⚖️ ▶️]
 🎒]

It calls swap quite a bit! Now let's alter the meaning of swap and call times.

[[🗑️ [5]]]
[["hi"] 3 times ▶️ 🗑️]
let ▶️

[[asked [execute]]
 [handled 🔳]
 [reason "word is not defined"]
 [type error]
 [unwound [execute]]]
[[[dictionary [[modules [#b64 "DRRitpxIz3S3HZ-keSV_EEMSscTJkFRzVwGI-4TTu4s"]]
               [words 261_entries]]]
  [program [["hi"] 3 times 🗑️]]
  [stack 🔳]]
 capture evaluate [stack] 🔍 restore]

Notice that times still works as expected! Even though it calls swap internally, it didn't insert any 5's. Only our own swap did that.

You can even refer to the old behavior of a word when defining new behavior:

[[swap [5 swap]]]
[["hi"] 3 times swap]
let 

"hi" 5 "hi" "hi"

Here we redefine swap to mean "insert 5, and then do whatever swap did before". This works even though swap is an axiom word:

[swap] definition

builtin

There are two other words related to let that are more flexible for times when you need to do a bit more complex alterations of existing meaning. One of the primary use cases is adding a method. You've got a word that behaves differently depending on its argument and you want to add a new behavior.

[[hash [[type [foo] 🍫 =]
        [drop "foo" hash]
        addmethod]]]
[[[foo myfoo]] association hash] revise
"foo" hash =

yes

What have we done here? We're taking the word hash, which is just a decide:

[first] definition

[📤 •🗑️]

See how it behaves differently for a byte array by calling hashbytes and by default it calls encode and then tries hash again? So now we've added a new logic branch there:

[[hash [[type [foo] 🍫 =]
        [drop "foo" hash]
        addmethod]]]
[[hash] definition] revise

[[[[type [foo] 🍫 =] [drop "foo" hash]]
  [[bytes?] [hashbytes]]
  [[yes] [encode hash]]]
 decide]

When the type is 'foo', we use the hash of the string "foo".

Sometimes in programming, having the concept of an indefinite sequence is handy. You have part of your program producing data, and another consuming it, but the producer doesn't know how much the consumer will actually need. A producer might calculate a huge number of items at great expense, only for the consumer to only need a tiny fraction of them. Generators allow the consumer to tell the producer when to produce, but the producer still retains all the logic of how that's done.

In kcats there's no special sauce for generators, we can implement them as a pattern with just the standard words we've already seen.

Let's say you want to create the fibonacci sequence. Let's see how we can code that without worrying about how many items in the sequence we'll eventually need.

A generator consists of two things: state, and a program. Each time we want to generate an item, we run the program. The program should produce a new item and update the state. We just put however many state items we need on the stack, and then a program that can work with those items.

1 0 [[+] •🛡️ ▶️ 🔀 👥]

So here we start with 1 0. That's the starting state. Normally we'd start fibonacci with 1 1 but this isn't the actual first two numbers in the sequence, it's starting values we use to calculate them. Then we have a program that takes two numbers as input and leaves one new number. Let's just ▶️ that program and see the result:

1 0 [[+] •🛡️ ▶️ 🔀 👥] ▶️

1 1 1

We can see the 0 is now 1 and there's an extra 1 on the stack. Remember the generator must do two things, produce a new item and update the state. It updated the state from 0 1 to 1 1, and produced the first item, 1.

This gets us one number, but not the whole fibonacci sequence. Let's look at the word generator. It creates a recurrence - a program that when you run it, may leave another copy of itself on the stack ready to be run again.

You can ▶️ this recurrence and get the next item in the fibonacci sequence, and beneath that you get another copy of it ready to be run again, when you've done what you need to with the first item it gave you.

[#b64 "zubPuf7fwUx1W6i8RJqAE8DR43dHFfnjx1xulAZ0D_U"]
[fibonacci generator ▶️]
;use
stage 🔀 ;; lm env
[[stack] [📸] •🐋 assign] 🪄 ;; capture the stack at runtime
using ;; set up the resolver 
evaluate ;; execute the program in the inner environment
[stack] 🔍 restore

[[asked [fibonacci]]
 [handled 🔳]
 [reason "word is not defined"]
 [trace 🔳]
 [type error]
 [unwound [fibonacci generator ▶️]]]

Notice here that the only difference from before is that the program is sandwiched between the fibonacci number we produced, and the state.

Let's keep going and execute again! But wait, before we do that we need to do something with item we just produced, to get it out of the way. For now we'll just 🗑️ it. We've seen it and we want to see what's next.

1 0 [[+] •🛡️ ▶️ 🔀 👥] generator ▶️
🗑️ ▶️ 

1 [[[+] •🛡️ ▶️ 🔀 👥] 🔳 🔳 [🔀] 🪆 ▶️] 1 2

Ok, so the 2nd item is 1 and we can see the state is updated - instead of 1 1 we have 1 2.

One more time:

1 0 [[+] •🛡️ ▶️ 🔀 👥] generator ▶️
🗑️ ▶️ 
🗑️ ▶️ 

2 [[[+] •🛡️ ▶️ 🔀 👥] 🔳 🔳 [🔀] 🪆 ▶️] 2 3

Ok we can see that we can get items one at a time by calling generate, but this is not very useful. What we really want is to get the first 20 numbers in the fibonacci sequence, and collect them into a list. We can do exactly that:

1 0 [[+] •🛡️ ▶️ 🔀 👥] generator
20 taker
collect

[1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765]
6765 10946

There's the fibonacci sequence! And the state is still there beneath in case we want to use it again.

So what is happening here? We're building up generators by wrapping one in another. Starting with the last, we have collect which will repeatedly call ▶️ generator inside it. It keeps going and collecting the generated items in a list, until the inner generator returns 🔳. Then it stops and returns what it collected.

Then inside collect we have a generator 20 taker - what that does is keeps its own state of how many items we want it to take. It counts down as it generates items inside it, passing them up to collect and when it hits zero, it returns 🔳 (even if the generator below it would have produced something, taker won't even ask). That will signal collect to stop.

We have other handy generators we can stack up. Let's say for whatever reason we want to know what are the first 20 odd fibonacci numbers? Well, we have keep:

1 0 [[+] •🛡️ ▶️ 🔀 👥] generator ;; our original generator
[odd?] keep ;; a generator that keeps calling the one
            ;; below it until it gets something that
            ;; passes the predicate we specified
20 taker ;; another generator that calls generate 20 times
collect  ;; collects all the generated items into a list

[1 1 3 5 13 21 55 89 233 377 987 1597 4181 6765 17711 28657 75025 121393 317811 514229]
514229 832040

There it is, the first 20 odd fibonacci numbers!

Let's say instead we wanted to know the prime factors that make up each of the first 20 fibonacci numbers. We can do that with each:

1 0 [[+] •🛡️ ▶️ 🔀 👥] generator ;; our original generator

[🔳 🔀 2
 [[sqrt] 🪄 >=] 🛡️ 
 [🗑️ mod zero?] 🛡️ 
 [🗑️ 🗑️ under ;; c-d i c-d r
  [📮] •🪄 ;; c-d i new-r
  / 2] ;; dividend new-r
 [🗑️ inc] ;; c-d++ i r
 ⚖️ ⏳ ▶️
 🗑️ 📮] each

20 taker ;; another generator that calls generate 20 times
collect  ;; collects all the generated items into a list

[[1] [1] [2] [3] [5] [2 2 2] [13] [3 7] [2 17] [5 11]
 [89] [2 2 2 2 3 3] [233] [13 29]
 [2 5 61] [3 7 47] [1597] [2 2 2 17 19] [37 113] [3 5 11 41]]
6765 10946

There we have it. We can see that [2 2 2] is what makes up 8, etc.

Other included generators are:

dropper

Inverse of taker - drops the first n items of the sequence and returns the rest.

joiner

Joins items together

integers

all the numbers starting with 0

reduce will consume what a generator produces. You provide a program that takes 2 arguments, and reduce will generate all the items, and pass to your program: the result so far and the next item generated, and repeat that until there are no items left:

[integers
 1 dropper ;; drop 0 so we start with 1
 10 taker
 [3 *] each
 [+] reduce]
shield

135

Let's say you go to the trouble of making a beautiful stack of transformations and you want to re-use it, but you don't have a generator, you have a list! Our transformation stack needs a generator! How are we supposed to use it? Never fear, there is a simple way to adapt transformations to work on anything that works with the word take. You can use the word liberator to adapt a list to a generator.

One pitfall with generators is that sometimes you want to transform generated items and use some item from the stack to help do it. The problem with this is that generators can be arbitrarily deep and you won't know exactly how deep that item is.

The solution is to capture the items you want.

Let's look at a simple example. Let's say we want to generate every multiple of n (where n is some number on the stack). We can already generate every integer, we just need to multiply each one by n. A naive solution would be to just use each, but it doesn't work:

3 integers generator
10 taker
[*] each
;1 dropper ;; drop 0
;10 taker
collect

[0 8 14 18 20 20 18 14 8 0]
9 3

This doesn't work because n and the last integer we generated aren't next to each other on the stack, there's a bunch of generator machinery in between. We could try to guess exactly how deep the machinery is, but then our generators aren't composable anymore - we couldn't move that call to each somewhere else in the generator stack, without having to change the program. What we really should do is create our program for each first, before we start stacking up generators, and bind n:

3 
[*] bind
[integers] dip ;; insert the integers generator below the each program
each
1 dropper
10 taker collect

[3 6 9 12 15 18 21 24 27 30]
[[positive?] [dec [generate] dive] [[]] if] 0 [[[positive?] [[generate drop]
                                                             dip dec]
                                                while [generate swap]
                                                dip float]
                                               bail]
0 [generate [[3 *]
             bail]
   shielddown]
[inc 👥]
10

What exactly is this doing? We're taking values from the current stack, and prepending them to a program, so that later when the program executes, it'll find that value on the top of the stack. Put another way, we're binding the value of the first argument to the program now, rather than letting it take a value from the top of the stack later.

In kcats, both coordination and input/output are done with pipes. See the definition for pipe.

Let's take a common example of coordination. Your program has to do several very long and intensive calculations but doesn't want to make the user wait to do other things. The way that's done in kcats is by creating multiple environments, and have them communicate with each other using pipes. You can send any item through a pipe that you could put onto the stack, including other pipes. You can clone a pipe to give access to it to more than one environment.

There are two main operations a pipe supports: put and take. You either put an item in, or take an item out. Either one of those operations may block, if the pipe is either full (when putting) or empty (when taking). Your environment would have to wait for some other environment to take something out so there's space to put, or put something in so that there's something to take out.

All pipes share the put and take operations but they can differ in other ways.

Note that put and take can also be used on plain lists. put adds to the end, and take removes the first item. Neither will ever block when used on a list. Another slight difference is what happens when you've reached the end of the content (either the list is empty or the pipe has, for example, hit the end of file condition): a take from an empty list will just return nothing, but a take from a pipe that is at EOF will result in an error.

Let's look at how we do I/O using files as an example - let's say we want to write the word foo to a file called bar:

[[file "bar"]] pipe-in ;; create the pipe to the given file "foo"
"foo" encode ;; we have to convert string to bytes first, using the word
            ;; =encode=.
put ;; finally, put the bytes into the pipe, and they are written to
    ;; the file

[[to [[file "bar"]]]
 [type tunnel]
 [values [[type bytes]]]]

Note the representation of the pipe shows where it leads (the to field), and what types of items it can carry (the values field).

Neither put nor take consume the pipe from the stack, for convenience, as most of the time you'll want to use it again.

Let's look at reading from a file:

[[file "bar"]] pipe-out
take string

"Hello World!" [[type tunnel]
                [values [[type bytes]]]
                [to [[file "bar"]]]]

Note that the amount of bytes you'll get from a file on each take, is limited. You will only get the entire contents if the file is small. We'll want to repeatedly take until there's nothing left, and put all the taken parts together.

Here's how we do it:

• turn the pipe that provides chunks of a file into a generator, with [take].
• Assemble the chunks with reduce. It requires a program to say how to combine the chunks. We want to join them, so the program is [join].

We can also use the word file-out as a shortcut to get a pipe given a file's name.

"bar" file-out [take] join reduce string

"Hello World!" [take] [[type tunnel]
                       [values [[type bytes]]]
                       [to [[file "bar"]]]]

Finally there's a convenient alias for [take] [join] reduce string, it's called slurp:

dictionary [slurp] 🔍

[[definition [[take] [join] reduce string [drop drop]
              dip]]
 [spec [[pipe] [item]]]]

It actually drops the generator for you as well, since we know it's already been fully read from. So you can do this:

"bar" file-out slurp

"Hello World!"

It's tempting to want the flexibility of EAV (where there's basically just one big db table with 3 columns and every attribute is a row).

However this may be a little hasty. Perhaps what we're really after here is custom tables - the idea being that each user's db schema might be different depending on what data is important to them.

We've basically got a database schema consensus problem. Maybe Alice has a table CATS with columns SIZE COLOR AGE and Bob has a table CATS with columns HEIGHT COAT-COLOR AGE. How do they share data? The two tables are not really compatible without a specialized conversion tool and even then some data would be missing. So Alice and Bob ideally should agree on what a CATS schema is, otherwise they can't really share CAT facts. The advantage of EAV might be that even if they had different schemas they could stlil perhaps meaningfully talk about AGE and possibly even COLOR (with a bit of intervention, or even another fact that equates COLOR and COAT-COLOR in CATS).

The drawback of EAV is of course that it would perform rather terribly as the database grows. I can't say for sure how many facts could potentially be stored here, but here are some constraints:

• Assume individual data only (no facebooks that store millions of people's data)
• Assume popularity of the app (users may try to cram every fact they "know" into this db)

• Assume there's some kind of garbage collection - Alice may collect weather observations or predictions constantly but doesn't need to keep old data. Maybe facts have a TTL? Not sure how that could be determined automatically.

  It's hard to estimate how large the db might get, but I suspect a lower bound of supporting 1M words is safe. As for upper bound, it's more difficult to say, but I would think the hardware limits of mobile devices would come into play. As of 2023 I think a db size on the order of 10gb would be approaching the device's capability limits, so maybe 100M words or so. I think it would be difficult to get an EAV database to perform well at that size, especially on mobile. Note datomic can handle that size so it's theoretically within reach.

  It may be possible to pick a standard db now (sqlite maybe) and not worry too much about performance. As long as the facts are portable to another db (which shouldn't be that hard), the issue can be revisited when it becomes an issue.

  Even using sqlite though, just building proper queries may be difficult. It may be possible to skirt that problem too and just do a minimal query to get a dataset that fits easily in memory and then post-process the rest. Let's say the query is "List all predictors (people who made predictions) and their accuracy", you could get all the unique predictor ids in a query, then one by one get all their predictions, then get all the relevant observations and compare them. Slow but not the type of query that will be done often, and possibly indexable.