FarTooGeneral

= FarTooGeneral =
FarTooGeneral (FTG) is an esoteric 'execution architecture' created by User:Baidicoot during the COVID-19 pandemic as a means of not becoming bored. It is characterised by its runtime reprogramming, reflection, and ability to create continuations. It has a reference implementation on Pastebin. The primary idea for FTG is that all data structures, including data structures used for program state, should be accessible and modifiable by the program itself.
== 'Execution Architecture'? ==
Yeah, I didn't know how to phrase it. FTG, instead of being a concrete programming language, is simply a specification for a programming language that is implemented using/on top of FTG.
== Specification ==
Every data store in FTG is an 'Element', which is defined in haskell as:
 data Elem a
 = Leaf --'Nil' element
 | Node a
 | Branch (Elem a) (Elem a)
where `a` is a store of data that can be interpreted as an instruction and defines an equality function.
Program state in FTG is defined as being a branch, where the first element is a linked list that forms the stack, and a lookup table (hence the need for an equality operation) that serves as a heap/function code repository.
=== Execution ===
A program in FTG is stored as a linked list, where each `Node a` denotes an instruction to be executed. As execution progresses, outer layers of the linked list are popped off, until only a `Leaf` is left, at which point the program returns.
Therefore, an `Exec` instruction is needed for function calls, which executes the top element on the stack, throwing a TypeError if it is not a linked list (i.e. it has an unexpected structure).
Items from the 'heap' are moved to the stack through a `Lookup a` instruction, which pushes the corresponding element onto the stack, throwing a `NotInHeap` error if `a` is not in the heap, as well as a `Define a` instruction, which moves the top element of the stack into the heap at 'address' `a`.
To make programming more readable, it is advisable to bundle an `Elemify :: [a] -> Elem a` function with the interpreter/compiler/whatever, which takes a list of instructions and parses them into an `Elem`.
To allow for continuations, a `PutState` and `TakeState` instruction should also be present, which push the state onto the stack and takes the state from the top element of the stack, respectively.
=== Example Data Structures using `Elem` ===
==== Linked List ====
 Branch (Node data) (Branch (Node data0) (Branch ...))
==== Lookup/Function Table ====
 Branch (Branch (Node name) code) (Branch (Branch (Node name0) code0) ...))
== Example Program ==
 -- computes factorial of an integer
 -- the instruction set for this is:
 -- Int i; Bool b - push literal
 -- Call s - synonym for 'Lookup a, Exec'
 -- Prc l - turns l into an elem linked list of instructions, and pushes that onto the stack
 -- Dec - decrements the top element of the stack
 -- Mult - pops top two elements, pushes product
 -- IsZero - 'Bool True' if the top element is zero, 'Bool False' if not; pops top element
 -- If - pops two linked lists of instructions, and a bool, executes first if the top element is true, executes second otherwise
 -- Dup - duplicates top element
 -- Pop - removes top element of stack
 
 Prc [ -- start definition for the fac function
 Dup; IsZero; -- check if top element is zero
 Prc [ -- if it is
 Pop; Int 1; -- pop top element, push 1
 ];
 Prc [
 Dup; Dec; Call "fac"; -- call 'fac(n-1)'
 Mult; -- multiplies top two: 'n*fac(n-1)'
 ]; If; -- if expression in fac: 'if n==0 1 else n*fac(n-1)'
 ]; Define "fac";
 Int 5; Call "fac";
=== Minified ===
 Prc [Dup; IsZero; Prc [Pop; Int 1;]; Prc [Dup; Dec; Call "fac"; Mult;]; If;]; Define "fac";
 Int 5; Call "fac";
Category:2020
= Extensions =
As FTG is really more of a specification, it is pretty easy to create implementations/extensions to the 'language'. This is a big ol' list of them, detailing what they do.
* Rofth-FTG: This extends FTG by incorperating the instructions that are being executed into the runtime state. Instead of the execution/runtime state being a pair of the 'heap' and the 'stack', it is now organised like: `(instructions, (stack, heap)`, where `instructions` is a list of lists of instructions (haskell `[[Ins]]`), with each sub-list being the code of a function (haskell `[Ins]`). As instructions are executed, they are popped off their function stack, and when a function has no instructions left, it is popped off the program stack.