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. ! forunquote)- 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
takeanddrop)- 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
upgradeandenumreturn 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 ("[";...;"]"). minfra,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.

DyadMonad==== =====KFKF- - - - + plus + flip ) - minus - negateneg* times * firstfirst% divide % reciprocalrec& min/and & where ) | max/ormax,orreverse ( > more > downgradedown< lesslessupgrade < = equal = group @ ^ power ^ shape # ! mod/rotate } enum < ~ match ~ notnot, join , enlist ' # take/reshape { countcount_ drop/cut } floor _ $ form/format NA formatstate? find/invert ? uniqueunique@ at NA atomatom. dot . value . : dex / identityid

KF- - 'each/over,do,while,vector,matrix\Over,Do,While,Vector,Matrix':prior/:right\:left

KF- - $ 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.