FFM/FFB

From Esolang
Jump to: navigation, search
Foxrabbit's Finite-state Map /
Foxrabbit's Finite-state Binary
Paradigm(s) Declarative
Designed by User:Enoua5
Appeared in 2017
Memory system Cell based
Computational class Turing complete
Major implementations Python Compiler Python Runtime
File extension(s) .ffm/.ffb


Introduction

Foxrabbit's Finite-state Map and its compiled form, Foxrabbit's Finite-state Binary, are mappings for a finite-state automaton. They define the rules and relationships for each state.see below

The Machine

The machine itself is imagined to be sitting over an tape of unsigned 8-bit cells, all starting at 0, extending to infinity in both directions. The machine can move left and right along the tape, increment and decrement the cells, and output the value it is looking at as well as save it's input there. When the machine starts, it enters the first state defined. Whenever any state is entered (including the initial state), the command that is associated with that state is run. The machine then checks the value of the pointed to cell and compares it to the bar that is associated with the current state. If the cell is greater than or equal to the bar then it is a pass, otherwise it is a fail. The state has associated with it two other states, one it will enter if the test passes, the other if the test fails. Execution continues until a halt command is received.

Syntax

FFM

In FFM code, each line represents a state the machine can be in and is formatted like this: name;command;bar;fail:pass. The name is simply an identifier for the other states to refer to. It can be any string that does not contain whitespace nor semicolons. The command is a three character token (not case sensitive) that represents the state's command to be run on entry (list of commands here). The bar is the number between 0 and 255 that is used for the test. The fail is the name of a state to be entered if the test fails. The pass is the name of a state to be entered if the test passes.
All whitespace (with the exception of line breaks) is completely ignored. A comment starts with a # and cannot be placed on the same line as a state definition.

FFB

In FFB code, the first byte holds the program's byte-width. This represents how many 8-bit bytes each address takes up. The number can go up to 255, although most modern computers can only handle up to 4 or 5. After this, the binary is split up into chunks of length 2 plus twice the byte width bytes. For example, a program with a byte width of 4 is split up into 2+(2*4)=10 byte groups. The first byte of each group is the command, the second is the bar, the next bytewidth bytes are the fail, and the remaining is the pass. The pass and fail use big endian byte order. The command is a number from 0 to 7 that represents the state's command to be run on entry (list of commands here). The bar is the number between 0 and 255 that is used for the test. The fail is the address of a state to be entered if the test fails. The pass is the address of a state to be entered if the test passes. The states are given address by the order they are defined, with the first being address 0, and the addresses counting up by 1 for each state.

Commands

FFM FFB Description
lft 0 Moves the pointer one cell left
rgt 1 Moves the pointer one cell right
inc 2 Adds one onto the pointed to value
dec 3 Subtracts one from the pointed to value
inp 4 Gets a byte of input and saves it to the pointed to cell
out 5 Outputs the byte in the pointed to cell
nop 6 Does nothing
hlt 7 Halts execution

Edge Cases

Overflow: running dec on 0 will result in 255. running inc on 255 will result in 0.
EOF/No input on an inp command: a -1 is saved into the pointed to cell.
Test with -1 in cell: will fail regardless of the bar.
Trying inc or dec a -1: inc will set the value to 0, dec will set it to 255.
Output a -1: instead outputs 0.

Turing Completeness

FFM/FFB represent finite-state automata, and therefore can perfectly emulate a finite-state automaton, making the languages Turing complete.
If for some strange reason you don't believe me, a Brainf*** to FFM compiler can be found here: link

Examples

FFM

Cat

Copies input to output.

in;inp;0;hlt:out
out;out;0;in:in
hlt;hlt;0;hlt:hlt

Reverse Cat

Takes input and outputs it in reverse.

in;inp;1;lft:rgt
rgt;rgt;0;in:in
lft;lft;1;hlt:out
out;out;1;hlt:lft
hlt;hlt;0;hlt:hlt

Truth Machine

Description can be found here.

start;inp;49;outZ:checkHigher
checkHigher;nop;50;output:start
output;out;0;output:output
outZ;out;0;halt:halt
halt;hlt;0;halt:halt

Hello, world!

Outputs "Hello, world!"

0; inc; 72; 0:1
1; out; 0; 2:2
2; rgt; 0; 3:3
3; inc; 101; 3:4
4; out; 0; 5:5
5; rgt; 0; 6:6
6; inc; 108; 6:7
7; out; 0; 8:8
8; rgt; 0; 9:9
9; inc; 108; 9:10
10; out; 0; 11:11
11; rgt; 0; 12:12
12; inc; 111; 12:13
13; out; 0; 14:14
14; rgt; 0; 15:15
15; inc; 44; 15:16
16; out; 0; 17:17
17; rgt; 0; 18:18
18; inc; 32; 18:19
19; out; 0; 20:20
20; rgt; 0; 21:21
21; inc; 119; 21:22
22; out; 0; 23:23
23; rgt; 0; 24:24
24; inc; 111; 24:25
25; out; 0; 26:26
26; rgt; 0; 27:27
27; inc; 114; 27:28
28; out; 0; 29:29
29; rgt; 0; 30:30
30; inc; 108; 30:31
31; out; 0; 32:32
32; rgt; 0; 33:33
33; inc; 100; 33:34
34; out; 0; 35:35
35; rgt; 0; 36:36
36; inc; 33; 36:37
37; out; 0; 38:38
38; rgt; 0; 39:39
39; inc; 10; 40:40
40; out; 0; hlt:hlt
hlt; hlt; 0; hlt:hlt

Hello, world! (Brainf*** port example)

Outputs "Hello World!"

#Ported from Brainf***.
0;inc;0;1:1
1;inc;0;2:2
2;inc;0;3:3
3;inc;0;4:4
4;inc;0;5:5
5;inc;0;6:6
6;inc;0;7:7
7;inc;0;8:8
8;inc;0;9:9
9;inc;0;10:10
10;nop;1;41:11
11;rgt;0;12:12
12;inc;0;13:13
13;inc;0;14:14
14;inc;0;15:15
15;inc;0;16:16
16;inc;0;17:17
17;inc;0;18:18
18;inc;0;19:19
19;rgt;0;20:20
20;inc;0;21:21
21;inc;0;22:22
22;inc;0;23:23
23;inc;0;24:24
24;inc;0;25:25
25;inc;0;26:26
26;inc;0;27:27
27;inc;0;28:28
28;inc;0;29:29
29;inc;0;30:30
30;rgt;0;31:31
31;inc;0;32:32
32;inc;0;33:33
33;inc;0;34:34
34;rgt;0;35:35
35;inc;0;36:36
36;lft;0;37:37
37;lft;0;38:38
38;lft;0;39:39
39;lft;0;40:40
40;dec;0;41:41
41;nop;1;42:10
42;rgt;0;43:43
43;inc;0;44:44
44;inc;0;45:45
45;out;0;46:46
46;rgt;0;47:47
47;inc;0;48:48
48;out;0;49:49
49;inc;0;50:50
50;inc;0;51:51
51;inc;0;52:52
52;inc;0;53:53
53;inc;0;54:54
54;inc;0;55:55
55;inc;0;56:56
56;out;0;57:57
57;out;0;58:58
58;inc;0;59:59
59;inc;0;60:60
60;inc;0;61:61
61;out;0;62:62
62;rgt;0;63:63
63;inc;0;64:64
64;inc;0;65:65
65;out;0;66:66
66;lft;0;67:67
67;lft;0;68:68
68;inc;0;69:69
69;inc;0;70:70
70;inc;0;71:71
71;inc;0;72:72
72;inc;0;73:73
73;inc;0;74:74
74;inc;0;75:75
75;inc;0;76:76
76;inc;0;77:77
77;inc;0;78:78
78;inc;0;79:79
79;inc;0;80:80
80;inc;0;81:81
81;inc;0;82:82
82;inc;0;83:83
83;out;0;84:84
84;rgt;0;85:85
85;out;0;86:86
86;inc;0;87:87
87;inc;0;88:88
88;inc;0;89:89
89;out;0;90:90
90;dec;0;91:91
91;dec;0;92:92
92;dec;0;93:93
93;dec;0;94:94
94;dec;0;95:95
95;dec;0;96:96
96;out;0;97:97
97;dec;0;98:98
98;dec;0;99:99
99;dec;0;100:100
100;dec;0;101:101
101;dec;0;102:102
102;dec;0;103:103
103;dec;0;104:104
104;dec;0;105:105
105;out;0;106:106
106;rgt;0;107:107
107;inc;0;108:108
108;out;0;109:109
109;rgt;0;110:110
110;out;0;111:111
111;hlt;0;111:111

FFB

All FFB examples listed are compiled from their corresponding FFM examples with a bytewidth of 1.
All FFB examples listed are base 64 encoded.

Cat

Copies input to output.

AQQAAgEFAAAABwACAg==

Reverse Cat

Takes input and outputs it in reverse.

AQQBAgEBAAAAAAEEAwUBBAIHAAQE

Truth Machine

Description can be found here.

AQQxAwEGMgIABQACAgUABAQHAAQE

Hello, world!

Outputs "Hello, world!"

AQJIAAEFAAICAQADAwJlAwQFAAUFAQAGBgJsBgcFAAgIAQAJCQJsCQoFAAsLAQAMDAJvDA0FAA4O
AQAPDwIsDxAFABERAQASEgIgEhMFABQUAQAVFQJ3FRYFABcXAQAYGAJvGBkFABoaAQAbGwJyGxwF
AB0dAQAeHgJsHh8FACAgAQAhIQJkISIFACMjAQAkJAIhJCUFACYmAQAnJwIKKCgFACkpBwApKQ==

Hello, world! (Brainf*** port example)

Outputs "Hello World!"

AQIAAQECAAICAgADAwIABAQCAAUFAgAGBgIABwcCAAgIAgAJCQIACgoGASkLAQAMDAIADQ0CAA4O
AgAPDwIAEBACABERAgASEgIAExMBABQUAgAVFQIAFhYCABcXAgAYGAIAGRkCABoaAgAbGwIAHBwC
AB0dAgAeHgEAHx8CACAgAgAhIQIAIiIBACMjAgAkJAAAJSUAACYmAAAnJwAAKCgDACkpBgEqCgEA
KysCACwsAgAtLQUALi4BAC8vAgAwMAUAMTECADIyAgAzMwIANDQCADU1AgA2NgIANzcCADg4BQA5
OQUAOjoCADs7AgA8PAIAPT0FAD4+AQA/PwIAQEACAEFBBQBCQgAAQ0MAAEREAgBFRQIARkYCAEdH
AgBISAIASUkCAEpKAgBLSwIATEwCAE1NAgBOTgIAT08CAFBQAgBRUQIAUlICAFNTBQBUVAEAVVUF
AFZWAgBXVwIAWFgCAFlZBQBaWgMAW1sDAFxcAwBdXQMAXl4DAF9fAwBgYAUAYWEDAGJiAwBjYwMA
ZGQDAGVlAwBmZgMAZ2cDAGhoAwBpaQUAamoBAGtrAgBsbAUAbW0BAG5uBQBvbwcAb28=