False! in K

False is an extremely simple concatenative language created by Wouter van Oormerssen. His page on False is here, the manual is here, and my K implementation of False!, a variant of the original language, is here.

False!

False supports just the 26 single-letter variable names a - z. To define and use a function, for example [2+], one says:

  [2+]f:	{ define f as [2+] }
  3 f;!		{ get the value of f, apply it to 3 }
5

In False!, the capital letters A - Z are the value forms of a - z:

  [2+]f:	{ as above }
  3F!		{ get the value of f, apply it to 3 }
5

The truth-values of False are -1 (true) and 0 (false). False! uses 1 and 0. In particular, 'if' and 'while' treat all non-zero integers as true.

In False, a comment is text between matching curlies:

  10 20 { ignore this } 30 40
10 20 30 40

In False!, an unmatched right curly is "stop":

  10 20 } 30 40
type error
{`0;(x;y)}
 ^
>  x
10 20
>  y
" 30 40 "
>  :
:
10 20 30 40

This allows the False! programmer to halt execution and manually examine the result and program stacks. Continue with

  :

Two of van Oormerssen's primitives use non-standard untypable glyphs:

	pick
	flush

False! moves pick to ')' and dispenses with flush.

I've also added the Joy combinator "dip", which lives on the left paren '(':

  10 20 30 [1+] (
10 21 30

Integer is the only numeric type in False!. Since '<' is not used by False, I've given it to the 'mod' function:

/	integer division
<	mod

In False, "`" (backtick) is used to denote 16 bit values in connection with adding inline assembly. In the present implementation it is used to toggle the trace bit:

  2 3 +
5
  `
  3 4 * /
                                5  3 4 * /
                              5 3  4 * /
                            5 3 4  * /
                             5 12  /
  `
0

The first column shows the result stack. The second column shows the program stack. Display width defaults to 30 (.f.D) characters for each of columns 2 and 3.

The evaluation algorithm

Since False! is so simple, I implement 'eval' without a preliminary parsing step. That is, the program input to eval is the raw, unprocessed source code in the form of a string.

Eval is the function e of two arguments x and y:

e:{*(a . t .)/(x;y,*|B)}

x is the result stack and y is the program stack, a string. For example:

x:()
y:"2 3+"

e appends an ASCII null to the program stack, and repeatedly processes the pair consisting of the result stack and the program stack until it's the same twice in a row, at which point it returns the result stack.

e processes each step by first passing the pair to the trace function t. If the trace bit (T) is 1, the current state is dumped to the console. In any case, t returns the pair, which is then passed to the apply function a.

a is:

a:{:[~#y;k;~_n~A;`.f@*A;y[0]_in*O;o;y[0]_in V;v;m][x;*y;1_ y]}

Initially, the evaluation state variable A is null. When a special symbol is encountered, the interpreter enters the corresponding state.

The logic of apply is:

If the input is empty, the k function simply returns the result stack and program stack unchanged, thereby causing apply to terminate (since the result is the same twice in a row.)

If we encounter "'" we enter character mode, and we stay there for exactly one step. The h function resets the mode to normal and places the current character on the result stack.

If we encounter "{" we enter comment mode. As long as we are in comment mode, we simply throw away input. We exit comment mode when we encounter "}".

If we encounter a quote mark """ we enter quote mode. While in quote mode, we accumulate input, appending it to the result stack. When we enounter an unescaped quote mark, we exit quote mode, the accumulated string is printed and deleted from the result stack.

If we encounter a digit we enter numeric mode. While in numeric mode, we accumulate digits, appending them to the result stack. When we encounter a non-digit, we exit numeric mode, and the accumulated digits are cast to integer in place.

If we encounter "[" we enter lambda mode. While in lambda mode, we accumulate characters, appending them to the result stack. As we encounter opening and closing brackets, we record depth. When we encounter the closing mate of the first opening bracket, we exit lambda mode.

If we encounter an operator -- a symbol in O[0] -- we enter operator mode. In operator mode, we find the index of the input in O[0], index out the corresponding K function in O[1], and apply it to the result stack and the program stack.

If we encounter a character we enter variable mode, and we stay there for exactly one step. The v function casts the character on the stack to symbol, and exits variable mode.

In normal mode, the m function looks for digits, upper-case letters, "{", """, "'", and "[", and then enters the appropriate state. If none of those is detected, mode is set to normal, and processing proceeds to the next input character. I.e., the character is assumed to be "out of the language", and is bypassed.

Operation

Say

k false

to start the False! interpreter.

k false .. <file.f> ..

starts the interpreter, then reads and evaluates the False! scripts .. <file.f> .. . For example, let fac.f be:

[$1=$[\%1\]?~[$1-f;!*]?]f:
6f;!

Then

C:k false fac
K 2.95 2004-02-11 Copyright (C) 1993-2004 Kx Systems

false! 2006-06-10
[space] to exit to K, [return] to clear, .f.i() for false!

720				result of evaluating 6f;!
  				type a single blank to exit to K
  f				the factorial "lambda"
"[$1=$[\\%1\\]?~[$1-f;!*]?]"	is a string

Boolean values on the command line turn trace 'on' and 'off' between read-eval steps:

k false 1 fib 0 fac

The interpreter prompts with two spaces:

  2 3 + 4
5 4

Exit to K by entering a single space.

Clear the stack by pressing <return> with null input.

The interpreter preserves its state across lines:

  [2 3 +			enter lambda mode, type type type ..
[2 3 +				(on the stack)
  *]q:				.. complete lambda, assign
				(stack is empty)
  				exit to K
  q	
"[2 3 + *]"

The interpreter code lives in the .f directory on the K tree.

Variables are saved in the .k directory of the K tree:

  [2+i]i:


  i
"[2+]"

Observe that False! lambdas are K strings.

Ackermann's Function (from Manfred von Thun)

Ackermann's function is:

A(0, n) = n + 1
A(m+1, 0) = A(m, 1)
A(m+1, n+1) = A(m, A(m+1,n))

In pseudocode:

ack(m, n) = 
    IF m = 0  THEN n + 1 
    ELSEIF n = 0  THEN ack(m - 1, 1) 
    ELSE ack(m - 1, ack(m, n - 1)) 

In Joy:

r-ack ==
    [ [ [pop null] popd succ ] 
      [ [null] pop pred 1 r-ack ] 
      [ [dup pred swap] dip pred r-ack r-ack ]
    ] cond.

Recoded in False!:

[0=]			z:
[1+]			s:
[1_+]			p:
[\$Z!@\]		b:
[\S!@%\]		c:
[$Z!]			d:
[%%P!1A!1]		e:
[[$P!\](P!A!A!]	        f:
[B!$C?~[D!$E?~F?]?]	a:
	
  3 4 A!
125

Appendix 1: Modified Language Summary

syntax:		pops:		pushes:		example:
		-->top		-->top
--------------- --------------- --------------- ----------------------------------------

`		-		-		`		{ toggle trace }
}		-		-		1 2 } 4 5	{ stop - use : to continue }
{comment}	-		-				{ this is a comment }
[code]		-		function	[1+]		{ (lambda (x) (+ x 1)) }
a .. z		-		varadr		a		{ use a: or a; }
A .. Z		-		value of a..z   A  		{ [1+]a: 3 A! }
integer		-		value		1
'char		-		value		'A		{ 65 }
num`		-		-		0`		{ emitword(0) }

:		n,varadr	-		1a:		{ a:=1 }
;		varadr		varvalue	a;		{ a }
!		function	-		f;!		{ f() }
(		-		-		1 2 3[+](	{ apply [+] to 1 2 }

+		n1,n1		n1+n2		1 2+		{ 1+2 }
-		n1,n2		n1-n2		1 2-
*		n1,n2		n1*n2		1 2*
/		n1,n2		n1/n2		1 2/
<		n1,n2		n1<n2           3 2<    	{ mod(3,2) }
_		n		-n		1_		{ -1 }

=		n1,n1		n1=n2		1 2=~		{ 1<>2 }
>		n1,n2		n1>n2		1 2>

&		n1,n2		n1 and n2	1 2&		{ 1 and 2 }
|		n1,n2		n1 or n2	1 2|
~		n		not n		0~		{ 0,1 }

$		n		n,n		1$		{ dupl. top stack }
%		n		-		1%		{ del. top stack }
\		n1,n2		n2,n1		1 2\		{ swap }
@		n,n1,n2		n1,n2,n		1 2 3@		{ rot }
)        	n		v		1 2 1)		{ pick }

?		bool,fun	-		a;2=[1f;!]?     { if a=2 then f(1) }
#		bool,fun	-		1[$100<][1+]#   { while a<100 do a:=a+1 }

.		n		-		1.		{ printnum(1) }
"string"	-		-		"hi!"		{ printstr("hi!") }
,		ch		-		10,		{ putc(10) }
^		-		ch		^		{ getc() }