Monday, July 15, 2024
Google search engine

F (2006)

F is a pure functional concatenative
language originally designed as an extension of False. F contains the list-operations of K3 and the dip combinator
of Joy. Floating-point and symbolic datatypes are supported. One-time assignment
is enforced in syntax. A theory of function-valence and -charge is outlined. F also contains a general continuation
primitive $, and the pattern sublanguage of XY. G is a variant of F in which the K3 adverbs are implemented as primitives.

0. Introduction

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 implements one as a primitive and derives the
other. For example, and is primitive (&) and or
is derived. The criterion for dividing related pairs is simply
this: the derived definition must not be egregiously inefficient
when compared to the primitive it supplants.

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:

  1. The symbol is in common use for the mapped function
    (e.g. + for addition)
  2. The symbol is mapped to that function in K (e.g. ?
    for find) or False (e.g. ! for unquote)
  3. The name of the symbol is a homonym for the mapped
    function (e.g. ‘ for quote)
  4. A pair of related functions (inverses, or
    near-inverses) are mapped to a pair of related
    symbols (e.g. / and for take and drop)
  5. 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 <.

1. Datatypes

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, 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 if it’s a shuffle
it’s applied; otherwise, a variable is created (in the environment)
having the top of the stack as the value.

If the first item is a defined symbol, 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 =] [] [dup ! pred ! fac ! *] ♦ cond !
                                     3 2 ♦ fac ! *
     3 2 [1 =] [] [dup ! pred ! fac ! *] ♦ cond ! *
                                   3 2 1 ♦ fac ! * *
   3 2 1 [1 =] [] [dup ! pred ! fac ! *] ♦ cond ! * *
6
F>

F>[] "t"

F>3 fac!
6

2. Primitives

Operators (O)

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]

;		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]

!		unquote		2 [3 +] ! -> 5
`		dip		2 3 4 [+] ` -> 5 4
'		quote		'+ -> [+]

,		join  		[1][2 3] , -> [1 2 3]

$		state		1 2 3 ' $ 4 5 6 -> 4 5 6 1 2 3

)		s -> s		stack->stack pattern
(		s -> q		stack->queue pattern

}		q -> s		queue->stack pattern
{		q -> q		queue->queue pattern

System Functions (K)

The K system functions have reserved names:

type (4::)
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

Literals (L)

F has nine reserved names for literals:

Nan		minint (0N)
Inf		maxint (0I)

nan		NaN (0n)
inf		infinity (0i)

null		null (_n)
sym		prototype sym (`)

ints		empty integer vector (!0)
floats		empty float vector (0#0.)
syms		empty sym vector (0#`)

Commands (I)

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
"j"		Joy		"j" 2 unit	set Joy semantics, clear
"k"		K		1 2 "k" 3 4	exit to K
"l"		load		'x "l"		load f/x.f|x.j
"m"		measure		[10<] "m"	measure time in ms
"o"		words		'map "o"	show word form
"p"		precision	3 "p"		print precision (p)
"r"		read		1 2 "r" 3 4	read, parse, eval
"s"		store		y 'x "s"	store f/x.f|x.j
"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
"w"		write		1 2 "w" 3 4	format, write
"z"		halt		1 2 "z" 3 4	: to continue

Names and numbers

Spaces (blank, tab, return) are
necessary to separate names from names and numbers from numbers,
but not names from numbers.

A name must begin with a letter and may contain letters, .,
or a single -. A name containing a - is a shuffle-symbol.

A numerical expression must begin with either a digit or -
followed by a digit, and must end with a digit. A floating-point
numerical expression must contain exactly one . which
must be flanked by digits.

Operators

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]

In several instances, distinct K operations have been mapped
to one symbol:

int <			enum			!x
~atom <			upgrade			

Iterators

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

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

Quotation

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>

State

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 $:

[[[|uncons!|swap!]`swap!unit!,]$]       queue
[[|uncons!|[unit!,]`]$]                 unqueue

[[[dup!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.

Stack Operations

The False stack operators pop, dup, and swap
are defined using shuffles:

[a-]                            pop
[ab-ba]                         swap
[a-aa]                          dup

List Operations

The list operations cons and uncons are
total:

F>1 2 cons!
[1 2]
F>

F>[1 2] uncons!
1 [2]
F>

F>[1] uncons!
1 ints
F>

F>[] uncons!
null []
F>

F>2 uncons!
2 ints

These are defined using the ( and ) operators:

[[[[a A]]a A])]                 uncons
[[[a b][a]b,](]                 cons

Errors

F stack			The stack-valence greater than the stack-size.

F queue			The queue-valence is greater than the queue-size.

F pattern		The stack-size is greater than the pattern scheme-size.

F char: 		x is an illegal character.

F nonce: 		Primitive x is not defined for the arguments supplied.

3. Implementation

The implementation consists of a single script which defines a
node (.f) on the K tree.

Globals

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.

Functions

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.

4. Operation

Say

k f

to start the F interpreter.

k f .. 
RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -
Google search engine

Most Popular

Recent Comments