FFM/FFB
| Paradigm(s) | Declarative |
|---|---|
| Designed by | User:Enoua5 |
| Appeared in | 2017 |
| Memory system | Cell based |
| Computational class | Finite-state automaton |
| 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 not Turing complete.
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=