There Once was an Esolang Named Fred

TOWAENF ('Fred') is a minimalistic, stack-based language created by User:Baidicoot named by two random users that just happened to be in the conversation. It is turing-complete. An example implementation can be found on GitHub.

Syntax

Fred programs, in stack-based tradition, are almost entirely constructed of 'words'. A word is either the name of a definition, or a 'quoted' definition (a 'quoted word'), denoted by a definition prefixed with an `'`. The only place where Fred syntax is used is when defining words as the composition of other words:

word-name: more words
another-word: yet more words
fred: 'a 'very 'good language

If a word which does not correspond to a definition, the program is invalid. When the program executes, it executes the word 'main'. Therefore, any program which does not define 'main' is invalid.

In User:Baidicoot's implementation, a line beginning with `#` denotes a comment, and a line beginning with `@` denotes an import.

Built-ins

All of Fred's functionality comes from its built-in words, which are:

pair: (a b) -> ({a b}) - take the top two elements on the stack and form a pair out of them
uncons: ({a b}) -> (b a) - push the elements of a pair onto the stack in reverse order
reorder: ({a {b c}}) -> ({b {a c}}) - reorder nested stacks

drop: (a) -> ()
dup: (a) -> (a a)

call: pop a symbol off the stack, call the corresponding word

You can define all rotation operations (i.e. rot 0 = swap, rot 1 = rot, etc.) like so:

swap: rot 0
unpair: uncons swap
rot n: [(n+1) * pair] [n * reorder unpair] uncons

N.B. Fred has no syntax for procedural definitions, so you will have to define all the rots you want yourself.

Since you can define all rotation operations, you can arbitrarily change the permutation of the stack, and, since you have `dup` and `drop`, you can manipulate the stack in any way you want.

Example Programs

Add two numbers

unit:

true: drop
false: swap drop
if: call call
branch: 'unit swap if
not: 'false 'true rot3 if

zero: 'unit 'true pair
_constzero: drop zero
succ: 'false pair
pred: unpair '_constzero swap 'unit swap if

iszero: uncons drop

add_internal: swap succ swap pred dup iszero not 'add_internal swap branch
add: dup iszero not 'add_internal swap branch drop

# main: 3 + 2
main: zero succ succ succ zero succ succ add

evaluates to:

((((((unit, true), false), false), false), false), false)

which is:

zero succ succ succ succ succ

which is five.

Turing-Completeness

Fred is provably TC, as it is able to implement a 3-cell, unbounded natural number, dialect of BF, which was in turn proven TC by User:Palaiologos, as it is able to implement Collatz. The implementation is on GitHub in `programs/tc.fred`.

Compilation

I am currently in the process of writing a Fred->C compiler for god knows what reason, and this requires the addition of some more syntax to Fred. Firstly, Fred files can import other Fred files in the same directory using @, as in the current Fred interpreter:

# main.fred
@std.fred
main: stuff

# std.fred
stuff: # whatever

Secondly, the compiler will expose a C-FFI by the use of 'modules'. Modules are essentially a blob of C with some metadata packaged. Module format is as follows:

data-point: value1 value2
more-data: all the datas
----
/* C blob */

Modules can be included in projects via the ~ directive, for example:

~debug.fmod
main: 'main debug.printLabel

The compiler accepts a number of datapoints, including requires, defines and declares. For example, the debug module looks something like:

defines: debug.printLabel debug.stackdump
declares: on_print
requires: stdio
----
void on_print();
void debug_printLabel { /* code */ };
void debug_stackdump { /* code */ };