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

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.