F is a pure functional variant of Wouter van Oormerssen's concatenative language False. F adds the list-operations of K3, and the dip combinator of Joy to the basic stack vocabulary of False. Floating-point and symbolic datatypes are added. One-time assignment is enforced. A theory of function-valence and -charge is outlined. F programs are functions from (environment;stack;queue) to (environment;stack;queue) triples. A general continuation primitive $ is supported. The pattern sublanguage of XY is supported.
F has the following properties:
- The language is concatenative
- The language is purely functional
- All K verbs are implemented
- All primitives are denoted by single symbols
- Primitive symbols are as mnemonic as possible
The language is concatenative. F tokens are words, words denote functions, and the concatenation of words denotes the composition of functions. In classical concatenative languages, everything is a function from stacks to stacks. In F, everything is a function from triples of (environment;stack;queue) to triples of (environment;stack;queue).
The language is purely functional. There are no side-effects. F has assignment, but not reassignment. This means that you can't use a variable to store dynamic state. F assignment associates names with values in an environment which is passed as an argument and returned as a value. F also has commands for interacting with the run-time environment and the file-system, but these operations are notationally differentiated from the operators of F: "h", "r", &c. They are intended as debugging aids only.
All K verbs are implemented. Some K verbs are implemented as primitives, and some are derived in the F prelude. For example, the atom primitive @ of K is defined as [#ints~]; i.e. shape matches the empty integer vector. Where K provides a pair of functions, one of which is easily defined in terms of the other, F provides one as a primitive and defines the other. For example, and is primitive (&) and or is defined.
All primitives are denoted by single symbols. Although list-notation ([x y z]) is supported, any list can be constructed functionally with ' (quote) and , (join).
Primitive symbols are as mnemonic as possible. There are five ways the mapping of a function to a symbol can be mnemonic:
- The symbol is in common use for the mapped function (e.g. + for addition)
- The symbol is mapped to that function in K (e.g. ? for find) or False (e.g. ! for unquote)
- The name of the symbol is a homonym for the mapped function (e.g. ' for quote)
- A pair of related functions (inverses, or near-inverses) are mapped to a pair of related symbols (e.g. { and } for take and drop)
- Where several K primitives are mapped to one symbol, the primitives should form an easily remembered group based on some common property; e.g. both upgrade and enum return indices based on an ascending relation, so both are mapped to <.
The initial state of the interpreter consists of an environment containing the F words of the prelude, an empty result stack, and a string (character-vector) to be evaluated. The input string is tokenized and parsed to obtain the initial queue.
The input queue is a K list, possibly containing integers, floats, symbols, null, functions, symbols, and lists ("quotations"). The result stack is initially empty. The environment is a K dictionary. F processes the environment, stack, and queue repeatedly until the queue is empty.
If the first item on the queue is an integer, float, null, the prototype symbol `, or a list, the item is pushed onto the stack.
If the first item is an undefined symbol then a variable is created (in the environment) having the top of the stack as the value.
If the first item is a defined symbol then its value is retrieved (from the environment) and pushed onto the stack.
If the first item is a function, then it is applied to the environment, stack, and queue to produce a new environment, stack, and queue.
Observe that the domain of the result stack is a proper subset of the domain of the input queue. On the queue we may find character-atoms, such as "r", and strings, such as "blah". But character-atoms are executed away when they are evaluated, and no F primitive ever produces one, and strings are comments, which are not processed.
The trace command displays the stack and queue for selected objects in the trace list T:
F>[fac] "t"
F>3 fac!
3 ♦ fac !
3 2 ♦ fac ! *
3 2 1 ♦ fac ! * *
6
F>
F>[fac cond] "t"
F>3 fac!
3 ♦ fac !
3 [1 =] [] [| pred ! fac ! *] ♦ cond !
3 2 ♦ fac ! *
3 2 [1 =] [] [| pred ! fac ! *] ♦ cond ! *
3 2 1 ♦ fac ! * *
3 2 1 [1 =] [] [| pred ! fac ! *] ♦ cond ! * *
6
F>
F>[] "t"
F>3 fac!
6
09*- int 123 -> 123
09*.09*- float 123.45 -> 123.45
az.AZ* name myName -> value or null
az*:AZ* shuffle 10 20 ab:ba -> 20 10
[..] list [10 + [3 a]] -> [10 + [3 a]]
+ add 1 2 + -> 3
- sub 2 3 - -> 1
* mul 3 4 * -> 12
% div 5 3 % -> 1.666667
^ power 2 3 ^ -> 8
_ floor 3.2 _ -> 3
= equal 2 2 = -> 1
> more 4 6 > -> 0
& and/min 4 3 & -> 3
~ match [1 2][1 2] ~ -> 1
# shape [1 2 3] # -> [3]
( reverse [1 2 3] ( -> [3 2 1]
) where [0 1 1 0 1] ) -> [1 2 4]
) flip [[1 2 3][4 5 6]] ) -> [[1 4][2 5][3 6]]
{ take 2[1 2 3] { -> [1 2]
{ reshape [3 2][1 2 3] { -> [[1 2][3 1][2 3]]
} drop 2[1 2 3] } -> [3]
} cut [0 2][1 2 3] } -> [[1 2][3]]
} rotate [1 2 3 4] 2 } -> [3 4 1 2]
? find [10 20 30] 20 ? -> 1
? mod 2 [3 4 5] ? -> [1 0 1]
@ partition [10 20 10 10 30] @ -> uniques group
@ unique [10 20 10 10 30] @ / -> [10 20 30]
@ group [10 20 10 10 30] @ \/ -> [[0 2 3][1][4]]
< enum 3 < -> [0 1 2]
< upgrade [10 30 20] < -> [0 2 1]
. infra 1 2 [[2 3 +]] . 3 4 -> 1 2 [5] 3 4
. index [[1 2 3][[1 0]]] . -> [2 1]
. monad [[1 2 3][[1 0]][1-*]] . -> [1- 2- 3]
. dyad [[1 2 3][[1 0]]+[3 8]] . -> [9 5 3]
/ pop 2 3 / -> 2
| dup 2 | -> 2 2
\ swap 2 3 \ -> 3 2
! unquote 2 [3 +] ! -> 5
` dip 2 3 4 [+] ` -> 5 4
' quote '+ -> [+]
, join [1][2 3] , -> [1 2 3]
; cons [1][2 3] ; -> [[1]2 3]
: uncons [[1]2 3] : -> [1][2 3]
$ state 1 2 3 '\ $ 4 5 6 -> 4 5 6 1 2 3
Spaces (blank, tab, return) are necessary to separate names from names and number from numbers, but not names from numbers.
A dot adjacent to a letter or a dot is part of the name containing that character. A name must begin with a character.
A symbol containing a single colon is a shuffle-symbol, and the colon must be preceded by at least one letter. A colon preceded by anything but a letter is uncons.
A number followed immediately by - is a negative number. - preceded by anything but a digit is subtraction.
Floating point numerical expressions must begin and end with a digit; i.e. they cannot begin or end with decimal point.
The math, logic, and relational operators are atomic functions. For example,
F>[1 2 3][[4 5 6] 7 8]+ [[5 6 7] 9 11]
The False stack-operators are pop (/), dup (|), and swap (\).
In several instances, distinct K operations have been mapped to one symbol:
int < enum !x ~atom < upgrade <x atom < nonce ~atom ( reverse |x atom ( nonce int/ints ) where &x list ) flip +x nonce atom y ? mod y!x ~atom y ? find x?y list atom } rotate y!x atom list } drop x _ y atom atom } drop x _(),y list list } cut x _ y 1=#x . infra x . index/monad/dyad . x
In one case, two K operations have been mapped to a single invocation of an F operator:
F>[10 20 30 20 10]@ [10 20 30] [[0 4] [1 3] '2]
That is, @ combines =: and ?: into a single operation, leaving two items on the stack: the uniques, followed by the group.
The False combinators if and while have been eliminated, and cond, if, and while have been defined as words in the prelude. The truth-values of F are more general than those of K: 0 is false, any other value is true.
Assignment has the form value unassigned_name. An assigned name may not be re-assigned.
Reserved names cannot be assigned:
F>12 inf 12 inf
Use of an assigned name (a variable) places the value assigned to it on the stack:
F>10 a F>a 10 F>12 a 10 12 10 F>a 10 12 10 10
A symbol can be produced indirectly:
F>10 foo F>foo 10 F>[foo] first! foo F>! 10
The quote primitive ' takes the next item on the queue and quotes it:
F>'+ [+] F> F>'[1 2 3] [[1 2 3]] F> F>'' [']
The unquote combinator ! is Joy's i. ! takes the top item x on the stack and prepends the elements of x to the queue:
F>2 3 '+ ! 5
The dip combinator is defined as it is in Joy. ` takes the top two items x y on the stack and prepends y,,x to the queue. For example, with trace on, the input queue is displayed to the right of the diamond and the result stack to the left:
F>10 2 3 4 20 [+*]`
♦ 10 2 3 4 20 [+ *] `
10 ♦ 2 3 4 20 [+ *] `
10 2 ♦ 3 4 20 [+ *] `
10 2 3 ♦ 4 20 [+ *] `
10 2 3 4 ♦ 20 [+ *] `
10 2 3 4 20 ♦ [+ *] `
10 2 3 4 20 [+ *] ♦ `
10 2 3 4 ♦ + * 20
10 2 7 ♦ * 20
10 14 ♦ 20
10 14 20 ♦
F>
F has two programs for manipulating the stack, and two for manipulating the queue:
stack push the stack onto the stack unstack set the stack to the top of the stack queue move the top of the stack to the queue unqueue move the end of the queue to the stack
These are defined using the state combinator $:
[[[(:(\]`\unit!,]$] queue [[(:([unit!,]`]$] unqueue [[[|unit!,]`]$] stack [[[last!]`]$] unstack
$ expects a program on top of the stack. The program expects two quotations beneath it: the current queue, and beneath that, the current stack. F expects the program to return two quotations: the new queue, and beneath that, the new list.
The list operations cons and uncons are total:
F>1 2 ; [1 2] F> F>[1 2] : 1 [2] F> F>[1] : 1 ints F> F>[] : null [] F> F>2 : 2 ints
The K system functions have reserved names:
log exp abs sqr sqrt floor dot mul inv lsq sin cos tan asin acos atan sinh cosh tanh draw in lin bin binl dv dvl di vs sv
F has eleven reserved names for literals:
Nan minint (0N) Inf maxint (0I) Infn minint+1 (-0I) nan NaN (0n) inf infinity (0i) infn negative infinity (-0i) null null (_n) sym prototype sym (`) ints empty integer vector (!0) floats empty float vector (0#0.) syms empty sym vector (0#`)
F has the following interactive commands:
".." comment 1 "skip" 2 comment not processed
"b" break 'x "b" signal error ('x)
"c" clear 1 2 "c" 3 4 clear, load f, prelude
"d" defined 'foo "d" is foo defined?
"e" error 0 "e" set/unset error trap (\e)
"f" F "f" 2 unit! set F semantics, clear
"h" halt 1 2 "h" 3 4 : to continue
"j" Joy "j" 2 unit set Joy semantics, clear
"k" K 1 2 "k" 3 4 exit to K
"m" measure [10<] "m" measure time in ms
"o" words 'map "o" show word form
"p" precision 3 "p" print precision (\p)
"t" trace null "t" 3 4 set trace-list (T)
"u" undefine x "u" undefine vars in x
"v" variables 1 2 "v" 3 4 show vars (!environment)
"x" exit 1 2 "x" 3 4 _exit 0
"r" read 1 2 "r" 3 4 read, parse, eval
"w" write 1 2 "w" 3 4 format, write
"R" Read 'x "R" read f/x.f|x.j
"W" Write y 'x "W" write f/x.f|x.j
"s" s -> s stack->stack pattern
"q" s -> q stack->queue pattern
"S" q -> s queue->stack pattern
"Q" q -> q queue->queue pattern
A command is a single quoted symbol.
A comment is a sequence of two or more symbols enclosed in quotation marks.
F has five errors:
F stack if the stack-valence of the primitive or command is greater than the number of items on the stack.
F queue if the queue-valence of the primitive or command is greater than the number of items on the queue.
F pattern if the stack contains fewer element than the pattern-scheme.
F character: <x> if x is an illegal character.
F nonce: <x> if primitive x is not defined for the arguments supplied.
The implementation consists of a node (.f) on the K tree.
J 0 (F semantics) 1 (Joy semantics). O Look-up table of operator character, operator I I.x is an interactive (or interpreter) command. L L.x is a literal whose representation is x. K K.x is a K system function C C i is a vector of characters of lexical category i. V A string of state-names. W A string of final-state-names. X In V i read a character in C j, go to X[i;j]. T 0 (no trace) 1 (trace). E Global environment. S Global stack. Z (states x 256) transition matrix.
F F interpreter.
n Interpret pattern.
q Interpret shuffle-symbol.
i Transform dictionary -> list.
j Transform list -> dictionary.
l Load and interpret a .f script.
s Format an F value and save it to a .f script.
u Update the stack (S) and environment (E).
p Tokenize and parse an input string to create a queue.
v Evaluate token.
r Recursively construct a list from ("[";...;"]").
m infra, index, monadic amend, dyadic amend.
e Evaluate the queue (z) on the stack (y) in the environment (x).
a Apply the top of the queue to the stack in the environment.
b Evaluate symbol.
k Create a variable in the environment.
c Process the value of a defined symbol (J-sensitive).
x Apply n-ad f, append the enlisted result to the stack.
y Apply n-ad f, append the result to the stack.
z Apply n-ad f, prepend the result to the queue.
w Apply n-ad f to stack, queue, return new stack, new queue.
t If T is a non-empty list, trace the impending step.
d Display the trace.
f Format the stack.
g Format an element on the stack.
h Pretty printer
o Translate symbols into names.
Say
k f
to start the F interpreter.
k f .. <script> ..
starts the interpreter, then reads and evaluates the F scripts. For example
k f f/fac
Joy or F semantics may be specified with an initial boolean value of J:
k f 1 f/fac
The prompt is F> for F semantics and J> for Joy semantics.
If, in a .f or .j script, the interpreter encounters a single unmated ", evaluation on that script terminates. (Analogous to \ in .k scripts.)
Exit to K, or from the current trace or stop, by entering a single space. Clear the stack by pressing <return> with null input.
The F prelude is here.
An F implementation of factorial is here:
F>[[1=][][|!pred!fac!*]cond!]fac F>6fac! 720
An F script containing synonyms for the symbolic operations is here.
Versions of the prelude and factorial function adapted for Joy semantics are here and here.
In Joy, use of a name causes the value associated with the name to be executed against the stack:
plustwo == 2 +
3 plustwo . 5
In F, use of a name causes the value associated with the name to placed on the stack:
F>[2 +] plustwo F>3 plustwo 3 [2 +]
The value may then be executed with !:
3 [2 +] F>! 5
In Joy, adjacent names must be separated by a blank, or the equivalent. The corresponding F code has greater visual density, but is nearly as concise. For example, the reduce combinator is:
[swap!dup!proto!swap!unit!bot!over!]
as opposed to:
[swap dup proto swap unit bot over]
One might say that F occupies a middle-ground between Joy, which evaluates names aggressively, and False, which breaks the semantics of name evaluation into even smaller steps:
[swap;!dup;!proto;!swap;!unit;!bot;!over;!]
In False, a name leaves its address on the stack. ; takes an address and leaves the value of the name on the stack. ! executes values.
In addition, F semantics makes it easy for one program to modify the code of another: invoke the program by name, which leaves a quotation on the stack, modify the quotation, execute.
In any case, it should be noted that switching F to Joy semantics is a trivial matter. The c function takes the value of a defined symbol z, the stack x, and the queue y and appends it to the stack:
(x,,z;y)
For Joy, we change this to:
(x;z,y)
which prepends the contents of z to the queue. Subsequent processing will evaluate elements of the value one-by-one.
It is important to note that in both dialects, some primitives have names. For example, stack and in are both primitive system functions, so:
F>10 [2 3 4 10 12 2] in 1
is valid code in both Joy and F dialects.
Note: this switch has been implemented in the script for F, viz. J is 0 for F semantics, 1 for Joy semantics.
Note: The "o" command spells out F programs. In Joy mode:
F>'map "o" [[dup count [] top] dip swap [quote uncons dip dup top [cons unit eval first swons] dipd] do pop pop rev]
It is possible to write programs in this way, using the words defined in the f scripts.
In Joy, a quotation is a list and also a program. All programs are lists, and vice-versa. Intuitively, there does seem to be a difference between [1 2 3] and [2 +]. It cannot be that the former contains "data elements" and the latter a data element and a function, since numbers are just as much functions as the + operator. Both 2 and + are functions from stacks to stacks.
The difference between quotations-as-lists and quotations-as-programs reduces to this: a quotation is list-like when we want to examine or manipulate its parts or structure; and a quotation is program-like when want to execute it. So the same object can appear list-like in certain contexts and program-like in others. Indeed, it can appear to be neither if we are merely pushing it onto the stack without regard to its structure or execution-properties, or both if we first manipulate contents and structure and then execute it.
The valence of a program is a pair of integers. The first element of the pair is the stack-valence. The stack-valence of a program is the number of elements it takes from the stack. The second element is the queue-valence. The queue-valence is the number of elements it takes from the queue.
The quote operator ' is the only primitive having non-zero queue-valence: it expects to find one element on the queue, which it enlists and pushes onto the stack. Hence, quote has stack-valence 1.
The + operator has stack-valence 2. It takes two elements from the stack and pushes the sum onto the stack.
The charge of a program is also a pair of integers. The first element is the stack-charge, and the second is the queue-charge.
+ has stack-charge 1 (it pushes a single element onto the stack) and queue-charge 0. | (dup) has stack-valence 1 and stack-charge 2. \ (swap) has stack-valence 2 and stack-charge 2.
! (unquote) has stack-valence 1 and infinite queue-charge: it takes a quotation off the stack and pushes as many elements onto the queue as there are in the quotation.
` (dip) has stack-valence 2 and infinite queue-charge: it takes two things off the stack: a quotation and an element X and pushes first X, and then the quotation onto the queue.
All primitives have non-negative charge and valence. A negative value means that the program operates on the bottom of the stack or queue.
If the stack has fewer elements than the (absolute value of the) stack-valence, an F stack error is signalled. If the queue has fewer elements than the (absolute value of the) queue-valence, an F queue error is signalled.
F implements four XY operators:
The stack program takes the stack, enlists it, and appends it to the stack:
F>1 2 3 stack! 1 2 3 [1 2 3]
The unstack program expects a quotation q at the top of the stack, and sets the stack to the contents of q:
F>1 2 3 [4 5 6] unstack! 4 5 6
The queue program expects a quotation at the top of the stack, and appends it to the end of the queue:
F>1 2 3 [4 5 6] queue! 7 8 9 1 2 3 7 8 9 [4 5 6]
The unqueue program expects a quotation at the end of the queue, and pushes it onto the stack:
F>1 2 3 unqueue! 4 5 6 [7 8 9] 1 2 3 [7 8 9] 4 5 6
The XY programs have valence and charge:
operator stack-valence stack-charge queue-valence queue-charge -------- ------------- ------------ ------------- ------------ stack inf 1 0 0 unstack 1 inf 0 0 queue 1 0 0 -1 unqueue 0 1 -1 0
The implementation of $ is one of two primitives which recursively calls the F evaluator e. $ is a K function which takes x, the environment, y the stack, and z the queue, and is defined:
{x,e[x;(-1_ y;z);*-1#y]1}The implementation of . is the other primitive which recursively calls the F evaluator e.
m:{:[1=#y;e[x;();*y]1 / infra
2=#y;(*y). e[x;();y 1]1 / index
3=#y;.@[y;2;{{*e[*x;y,();x 1]1}[(x;y)]}[x]] / monad
.@[y;2;{{*e[*x;y,,z;x 1]1}[(x;y)]}[x]]]} / dyad
where y is the quotation on top of the stack and x is the environment.
For example, if the expression to be evaluated is
[[10 20 30][[0 1]]] .
then the count of y is 2. m indexes the first element of y, which is 10 20 30, by the value of the second element of y in the environment x, which is ,0 1.
F incorporates a version of the pattern sublanguage of XY.
A pattern is a list whose head is a scheme and whose tail is a template
A scheme is a name or a list of schemes. The case of the first letter in a name is significant. If lower-case, the name matches a single element. If upper-case, the name must occur as the final element in a list of schemes, and will match zero or more elements, viz. the remainder of the list whose initial elements are matched by schemes preceding the terminal name.
A template is a list. If s is a symbol in the template which also occurs in the scheme, the value matched by s is substituted for s in the template.
F contains four operations on patterns. Both are implemented as commands, rather than primitives.
"s" applies a pattern to the stack and pushes the result onto the stack.
"q" applies a pattern to the stack and prepends the result to the queue.
"S" applies a pattern to the queue and pushes the result onto the stack.
"Q" applies a pattern to the queue and prepends the result to the queue.
Several of the F primitives can be defined with patterns:
[[[a b]b a]"s"] Swap [[a]"s"] Pop [[a a a]"s"] Dup [[[[a A]]a A]"s"] Uncons [[[a b][a]b,]"q"] Cons [[[a p]p!a]"q"] Dip
F also supports shuffle-symbols, a simplified, weaker version of "s". For example, swap is:
F>10 20 ab:ba 20 10
Note: This material has benefited greatly from discussions with William Tanksley, Jr.
See Randall Holmes' functional extensions to False, Strictly False, which stimulated the present project.
Dyad Monad
==== =====
K F K F
- - - -
+ plus + flip )
- minus - negate neg
* times * first first
% divide % reciprocal rec
& min/and & where )
| max/or max,or reverse (
> more > downgrade down
< less less upgrade <
= equal = group @
^ power ^ shape #
! mod/rotate } enum <
~ match ~ not not
, join , enlist '
# take/reshape { count count
_ drop/cut } floor _
$ form/format NA format state
? find/invert ? unique unique
@ at NA atom atom
. dot . value .
: dex / identity id
K F - - ' each / over, do, while, vector, matrix \ Over, Do, While, Vector, Matrix ': prior /: right \: left
K F
- -
$ format state
| reverse dup
\ scan swap
/ over pop
! enum unquote
` symbol dip
' each quote
; seperator cons
: dex uncons
[ open apply open list
] close apply close list
{ open lambda take/reshape
} close lambda drop/cut/rotate
( open expr reverse
) close expr where/flip
? find find/mod
@ at group
" quotation command/comment
Copyright (c) 2006, Stevan Apter. All Rights Reserved.