K4 now
In the last post we covered some basics on how K4 accepts input, looks up words in a dictionary executes them and even how new words are defined. In this post I’ll talk about what K4 has been developed for, and how you could run it for yourself.
I want to develop this Blog as a story of K4. This project has been going now for about six months. The language was prototyped in C++ (on OSX) and has been ported to Linux, our ESP32 BOB boards and ATSAMD51 (ARM Cortex-M4+) CPU’s in our EDDIE project. Work is underway to put a miniaturized version on ATSAMD21 (Cortex-M0) CPU’s we use.
At this time, K4 is being expanded to allow for:
Improved string handling (eg comparison, appending and copying)
Boot strapping behaviour to allow loading of dictionaries and applications on start-up
Interrupts for reactive and real-time applications
Local variables and arguments for words: simplifies stack handling in frequently used words.
Multiple vocabularies (aka dictionary namespaces)
Rudimentary “objects” which is very experimental
Word linking to ease building complex data structures
Optionally embedding a web server.
Variable and object persistence: saving and loading of the current values of some words to NV memory
“System” interfaces - dictionaries unique to particular ports:
K4-Kairos - adds seven segment display drivers, WiFi
K4-51 - Control of Eddie busses and communications interfaces
etc..
K4 is a very extensive and exciting project. I will bring the blog up to date with its complete features. These blogs read backwards - the latest blog entry is at the top of the page, so it is hard to make it read as a story - so please bear with me and we will work it through.
Let’s build a real K4 program
The saying is that the “proof is in the pudding”. So we present som “pudding” in the form of a two player tic-tac-toe game. Two player means the two people are playing and the computer is not your opponent. A version with a computer opponent would be an interesting project later.
I will break the code down and explain each part. The final code will be available on our github repo at (????).
Initializing: Our board consists of nine cells, so we need to declare an array of nine elements (bytes). We also need byte sized constants for an EMPTY cell, a cell with an X in it and obviously an O as well:
." stdext.k4" include
#
variable board 9 allotc
#
# Cell values for empty, x and o
#
0 constant EMPTY
1 constant O
2 constant X
This code loads the K4 standard extensions: K4 comes with a lot of built-in words. These are compiled from C++ code into the K4 binary. There is good reason to standardise other useful words (for portability, readability etc). These are being standardised into a file ‘stdext.k4’ that comes with K4:
#
# K4 Standard Extensions (non-built-in)
# (use: 'include stdext.k4' to read into your dictionary
# ----------------------------------------
#
# <n> historic : print the nth last item in the history
#
: historic $cmd $> . ;
#
# .r, .xr, ..r, ..xr - prints with returns
#
: nl 10 emit ;
: .r . nl ;
: .xr .x nl ;
: ..r .. nl ;
: ..xr ..x nl ;
# tab : emits a tab character
: tab 9 emit ;
If you care to study this code, you will see words for emitting a new line and nicer versions of the ‘dot’ words that print the stack.
After including this code, we initialise a variable ‘board’ with 9 bytes of storage. The reason should be obvious that this is an array containing all the cells of our tic-tac-toe board.
Lastly, we declare constant values that are stored in cells of the board for a nought, a cross and an empty cell.
You will notice that any line that starts with ‘#’ in the leftmost column is a comment line. At this time this is the only way that a comment can be put into a K4 program - and I think its enough of a shortcoming to warrant fixing at some point in the near future!
2. Lets have some way of displaying a cell! We write another word ‘xo’ that uses the cell number and prints ‘X’, ‘O’ or ‘ ‘. We have two ways of addressing cells in the program: the raw way numbers the cells 0 to 8 left to right, top to bottom. In a moment we will introduce a row/column method of addressing the cells instead.
#
# given a cell number (0..8) load the cell
# and print X, O or ' '. If the cell value
# is not expected, print '?'
#
: xo 1 0 {
1 () X = if
\X emit
else
1 () O = if
\O emit
else
1 () EMPTY = if
20 emit
else
\? emit
then
then
then
} ;
This section of code introduces a couple of important K4 concepts. The first is our invention called “frames”, and the second this the ‘if-else-end’ construct.
The ‘if’ statement takes a true/false value off the stack. If the value is true, execution continues at the word after the ‘if’. If the value is ‘false’, execution will continue after the ‘else’ statement. (If there is no ‘else’ then it continues after the ‘then’ at the end of the block. Note that the statement just before the ‘else’ continues after the ‘then’, it doesn’t proceed into the ‘else’ bit.
Frames are a more difficult concept. Frames begin at ‘{‘ words and end at ‘}’ words. Preceding the ‘{‘ you will see two numbers:
<args> <locals> { … }
The <args> number is the number of stack entries expected before the frame to treat as ‘arguments’ inside the frame code. The <locals> number allocates this many entries on the stack that can be directly addressed inside the frame. When the frame ends at ‘{‘ the stack is returned to the position it was at before the frame started. We can address arguments with:
<n> ()
Which pushes a copy of the nth argument onto the stack. (Arguments are numbered 1 to n, with 1 being the top of stack at the start of the frame, 2 being the next down and so on. We address local variables with:
# get the nth local and push a copy onto the stack
<n> #ld
# pop the stack and store it in the nth local.
<n> #st
The code here doesn’t yet use locals, we meet them a bit later int the program.
So this code takes the argument it was supplied and compares it to the constant X. If it is an X, the program emits the ‘X’ character. If it isn’t, it has another look at the first argument and compares it to the O constant and likewise emits an ‘O’ if it is. If it isn’t that, it checks if the cell is empty using the same expressions and emits a space if it is. If it’s still none of those it prints ‘?’ to signal its confusion at the odd value in the cell.
3. Some little worker words. These words do what’s on the tin:
#
# <col> <row> cell - push cell number
# (col, row range is 0..2)
#
: cell 3 * + ;
#
# <col> <row> cell@ - push the value at cell
#
: cell@ cell board _ @c ;
: xcell@ cell board _ @c dup 0 = if 4 then ;
#
# <mark> <col> <row> cell - mark the board
# at row, col with X, O or EMPTY
#
: cell! cell board _ !c ;
#
# <col> <row> cell! - print the mark on the
# board at <col> and <row>
#
: .cell cell@ xo ;
The word ‘cell’ multiplies a row number by 3 and its it to the column number magically providing a number from 0 to 8 to address the cells on the board. This is our second way of addressing the board.
The word ‘cell@’ takes row/col on the stack, calculates cell number then the expression ‘board _’ adds the cell number to the board address and gets the cell address. Finally ‘@c’ loads the value at that address and pushes it onto the stack. The word ‘xcell@’ is similar, however if the cell value is EMPTY (0), it returns 4 on the stack - the reason for this will be explained shortly.
The word ‘cell!’ does the reverse work of ‘cell@’ - it calulates the cell address from the row, column and board. Then it stores the value (X, O or EMPTY) which is lowest on the stack (after the row/col values) into the cell.
Finally ‘.cell’ uses the row and column to get the cell value. Then it uses the previous ‘xo’ word to display its symbol.
4. Displaying the board. We can put all the previous words together and display the board:
#
# display the board with the # markers
#
: bar ." -+-+-\n" ;
: board?
X 0 0
3 0 do
3 0 do
I J .cell
I 2 < if
\| emit
then
loop
10 emit
I 2 = not if
bar .
then
loop
nl ;
Output (for example)… (this uses commands to set cells on the board and display it)
The ‘bar’ word defines a string literal that we can load just by invoking the ‘bar’ word. Typing ‘bar .’ would print ‘-+-+-’.
The ‘board?’ word uses two ‘do’ loops that we haven’t discussed before. A do loop is of the form:
<end> <start> do <words> loop
Given an starting value, the do loop counts up until its loop value is equal to or greater than the end value. Usefully the word ‘I’ pushes a copy of the loop value for the nearest loop. The word ‘J’ pushes a copy of the loop value in the next loop out. (There are no words for even deeper nested loops, but there are ways around this issue). Note also that ‘do’ loops (like if statements and other flow control constructs can only be compiled, not iterpreted on the command line)
So we see two loops, then the line ‘I J .cell’ which uses the loop values as the row and column to get the cell value.
Crafty tests with ‘if’ statements place the vertical bars and the horizonal lines between cells. See that prior to each if statement there is a construct like:
<expr1> <expr2> <comparison> [ <not> ] if …
The comparison could be ‘=’, ‘<‘ or ‘>’ (from the available builtin words). This reads as <expr1> compares to <expression2> and the result is used by the if. We can invert the comparison logic with the word ‘not’. If you think about it, ‘<=’ is the same as ‘not >’ so only the three simple comparators are needed.
5. Clearing the board for a new game:
#
# Empty the board for a new game
#
: newgame 9 0 do EMPTY board I _ !c loop ;
This is very simple code to fill every cell in the board with the EMPTY value by using a loop, ‘_’ for indexing and ‘!c’ to store the value.
6. Testing rows, columns and diagonals for a winning situation. This big chunk of code creates words for the three possible winning permutations on the board:
#
# <row> checkrow
# push X, O or EMPTY if X wins row, O wins
# or nobody's winning
#
: checkrow 1 1 {
0 1 #st
3 0 do
I 1 () xcell@ 1 #ld or 1 #st
loop
1 #ld X = 1 #ld O = or not
if
EMPTY 1 #st
then
1 #ld
1 ->} ;
#
: checkrows
0
3 0 do
I checkrow
ifnz
swap drop leave
else
drop
then
loop ;
#
This first chunk introduces more interesting aspects of K4. First of all we actually make use of a single local variable inside the frame. We start by setting the local variable to zero with ‘0 1 #st’ - this is put 0 on the stack and store in local 1. Then inside the do loop, we get each cell value by combining the input argument ‘1 ()’ as the row number with I from the do loop as the column number. Notice we are using ‘xcell@’ here - which returns the value 4 for an empty cell. Consider a row of all ‘X’ values (1) ‘ored’ together will give 1 which is ‘X’. Likewise for ‘O’ which is 2. If the row contains ‘X’ and ‘O’ we or together 1 and 2 and get 3. If the row has any empty cell we could get 5,6 or 7 using binary arithmetic. Only the values ‘2’ and ‘4’ represent rows that are all X’s or all O’s. Outside the do loop, the statement ‘1 #ld X = 1 #ld O = or not’ is read as ‘if the result is not X or O’ push ‘true’. Then the if statement converts that ‘true’ value into EMPTY which is what we want to return if nobody’s winning. Finally we ensure the result is put on the stack.
Then there is a more curious ending to the frame. Previously I said that frames were ended with ‘}’. But what if we want to return a value from a frame’s calculation? In this case we can use:
<n> ->}
This construct tells K4 to put aside the <n> values at the top of the stack, reset the stack to the state before the frame began and push those <n> values for the code outside the frame to see. Effectively ‘checkrow’ returns the result on the stack this way.
Lastly we define the word ‘checkrows’ that uses a ‘do’ loop to run through rows 0, 1, 2 looking for a win. In that code there are more new things!
ifz
ifnz
We use ‘ifnz’ here, but the logic for ifz is the same. These built-in words look at the top of the stack - without popping that value from the stack - and compare it with zero. ‘ifz’ executes if the value is zero and ‘ifnz’ executes if it is not. In this case, if it the result is non zero, we swap the result and the 0 that’s already on the stack and drop the 0, then we ‘leave’ the loop. If it is the result is just dropped and the loop continues with a balanced stack. Consequently if ‘checkrows’ exits with a non zero value, someone has won.
To leave the loop we use the word:
leave
This sets the loop variable to the limit and the loop will exit the next time the ‘loop’ word is executed.
So the code to check the columns follows the same pattern only we swap the loop variable and the column argument. The rest of the logic is the same.
# <col> checkcol
# push X, O or EMPTY if X wins col, O wins
# or nobody's winning
#
: checkcol 1 1 {
0 1 #st
3 0 do
1 () I xcell@ 1 #ld or 1 #st
loop
1 #ld X = 1 #ld O = or not
if
EMPTY 1 #st
then
1 #ld
1 ->} ;
#
: checkcols
0
3 0 do
I checkcol
ifnz
swap drop leave
else
drop
then
loop ;
#
Finally we have a word that scans the columns left to right and right to left, using two local variables this time. At the end out logic tests both variables and returns non zero if someone wins.
# Check the left-right and right to left diagonals and
# push X, O or EMPTY if X wins , O w ‘checkdiains
# or nobody's winning
: checkdia 0 2 {
0 1 #st
0 2 #st
3 0 do
I I xcell@ 1 #ld or 1 #st
2 I - I xcell@ 2 #ld or 2 #st
loop
1 #ld X = 1 #ld O = or not
if
EMPTY 1 #st
then
2 #ld X = 2 #ld O = or not
if
EMPTY 2 #st
then
1 #ld 2 #ld or 1 #st
1 #ld X = 1 #ld O = or not
if
EMPTY 1 #st
then
1 #ld
1 ->} ;
We have three words: ‘checkrows’, ‘checkcols’ and ‘checkdia’ we can use to test if there’s a winner.
If there is a winner we use ‘win?’ in this block to print who won and return true or false (using the frame and 1 ->} mechanism:
#
: Xwin ." X Wins!" ;
: Owin ." O Wins!" ;
#
# win? - print who wins, return true if
# game is over
#
: win? 1 0 {
1 () X = if
Xwin .
true
else 1 () O = if
Owin .
true
else
false
then
then
1 ->} ;
Putting all these words in one place, we can write a single word that checks for and prints a win and subsequently returns true for a win or false:
#
# full - return true if the board is full
#
: full 9 0 do
I board _ @c
ifz
drop false leave
else
drop true
then
loop ;
#
# gameends
#
: gameends
checkrows
checkcols
checkdia
or
or
win?
if
true
else
full if
." Its a draw!" .r
true
else
false
then
then
;
We have to take care of the situation where the board becomes full but there is no winner. We have a word: ‘full’ that tests that there are no empty cells and returns true if there aren’t any. Now if win? returns false, we also check for a full board and indicate a draw if so.
This is a good example of how K4 programs build up from basic to more and more sophisticated functions in layers of words in the dictionary.
Now we can start working out the logic to play a game. Firstly, we have a variable called player that takes on the value X or O. We use this to control who is playing now and who will play next. The simple word ‘toggleplayer’ switches to the opposite player every time it is invoked:
variable player
: toggleplayer
player @ X =
if
O player !
else
X player !
then ;
To tell the users who is playing we use ‘player?’ that tests the player variable and displays a string on the console:
: player?
player @ X =
if
." 'X' to play:\n" .
else
." 'O' to play:\n" .
then ;
Then we have to ask for the row and column the player wants to play in. Since the row number is a single digit from 1 to 3 we can read this in. We also know that the same is true for the column number. So how about one word that prints a prompt and asks for input. It verifies that input is a single digit from 1 to 3. If it isn’t it loops until it is re-prompting the user for the correct input.
#
: rowcolstr ." Enter 1,2 or 3 please! " ;
: readrc 1 2 {
false 2 #st
begin
1 () .
input
$> strlen 2 = if
$> @c \0 - 1 #st
1 #ld 1 < 1 #ld 3 > or if
rowcolstr .
else
true 2 #st
then
else
rowcolstr .
then
2 #ld
until
1 #ld 1 ->} ;
See that the ‘readrc’ word takes on argument (the prompt string) and uses two local variables. Variable 1 is the output value and variable 2 is used as a flag to control the loop. Notice the two new words used here:
input
$>
strlen
begin .. <words> .. until
The word input waits for a line of input from the user. The text that is typed is put into a global variable known as the ‘StringBuffer’. There are various words that access and manipulate the StringBuffer. Used here is the ‘>$’ word that puts the address of the StringBuffer on the stack. The ‘strlen’ word uses the top of the stack as the address of a string and returns the number of characters in the string (Strings in K4 are null terminated). We use strlen to make sure the typed input is just one character long.
Lastly we’ve introduced the begin..until control construct. The words between begin and until are executed at least once. When the program gets to the until word, a boolean (true/false) should be on the stack. A false value causes the program to jump back to the begin and try again. A true value lets the program continue.
Now we have a the general purpose word ‘readrc’ we can wrap it in two words to set the prompt for Row? or Col? The result from readrc is simply passed out to the calling program:
#
: readrow 0 0 {
." Row? " readrc
1-
1 ->}
;
#
: readcol 0 0 {
." Col? " readrc
1-
1 ->}
;
Now we can make a move for a specific player:
#
: empty cell@ 0 = not
if
." Cell is not empty! Try Again\n" .
false
else
true
then ;
#
#
: move
player?
begin
clear
player @
readcol
readrow
over over
empty
until
cell!
;
Here we start with the word ‘empty’. This returns true if the cell at the given row and column is empty. Otherwise it prints a message and returns false;
The ‘move’ word prints out the ‘player?’ and reads a row then a column. Notice the use of the word ‘clear’ at the beginning of the loop. This stops the stack from growing out of hand from unused values. After reading the row and the column we use the peculiar word ‘over’. This word copies the word one below the top of the stack to the top. Using ‘over over’ duplicates the top two values on the stack:
Example: with 3, 2, 1 on the stack, execute ‘over over’ to duplicate 1 and 2
The two two values on the stack are now copies of the row and column. We use ‘empty’ to see if that cell is empty. If it is ‘empty’ returns true on the stack and the until allows the program to store the player symbol at the row and column on the stack. If it isn’t empty the program loops around.
Finally we use the built in ‘random’ word (returns a random integer on the stack). Take this value modulo two to get a value of 0 or 1. Since X and O are numbers 1 and 2 we add one and have a way to choose a random player to start the game:
#
# randomplayer - chose a random player to start
#
: randomplayer random 2 % 1 + ;
And now we can play(2)! The program initiailizes the board, chooses a random player to start and begins looping:
#
# play2 - two player (non computer) game
#
: play2
newgame
randomplayer player store
board?
begin
toggleplayer
move
board?
gameends
until ;
The loop switches players, asks for and makes a move and shows the new board. To see if it should keep looping, it uses the ‘gameends’ word to test for some form of win or a draw. That word is kind enough to return true if the game ends and false otherwise. We can use the ‘until’ to keep playing until a conclusion is reached.
Finally!
If youve read all that you are almost a K4 pro!. This program covers many practical and real aspects of our language. It should serve to demonstrate the K4 is a fully fledged programming language - albeit limited to the console in this demonstration.
In coming posts we’ll talk about K4’s implementation and some more advanced aspects of the language that make it useful in embedded environments.
