Foreach

Foreach

Paradigm(s)	Imperative
Designed by	Ashli Katt
Appeared in	2023
Computational class	Turing Complete
Reference implementation	[1]
File extension(s)	.forx

About

Foreach is an imperative esolang where the only data-type is arrays, and the only flow control is for-each loops and recursion.

Overview

A Foreach program consists of any number of variable, constant, and function declarations; they may be declared like so:

varName = value;
constName := value;
funcName parameterName <statement>

varName, constName, funcName, etc are all identifiers. An identifier in Foreach can contain any characters except for whitespace or the following: []{};.

A value is either a variable name, an array literal, or function call. Arrays are written in the form [x] where x is 0 or more values separated by ;s. The following are all valid values:

a
[]
[a]
[[];[]]
[a;[];[[];[b]];[c;[]]]
[ab]
[a;b]

Functions

Functions are written in the form funcName paramName statement. All functions have exactly one parameter. Both funcName and paramName are identifiers representing the name of the function or the name of the parameter, respectively. statement is any valid statement in Foreach. Valid statements are as follows:

• Variable declaration/assignment (varName = value;)
• Constant declaration (constName := value;)
• Foreach (constName := value => <statement>, taking another statement)
• Function return (-> value;)
• 0 or more statements surrounded in {}

A a := b => statement will work like a usual for-each loop, running the statement once for each element in b, with a assigned to that element for the iteration.

A function return works as expected, immediately exiting the function and returning that value. If a function ends without encountering a return, [] is returned by default.

Statements inside of {} will be executed linearly, as expected.

Functions may be called with the form funcName value, where value is supplied as the parameter.

IO Format

Input and output are done using four functions:

• io.next x Will return the next bit. x is ignored.
• io.bits x Will return an array of all input bits, does not affect io.next. x is ignored.
• io.out x Will push x to the output buffer.
• io.debug x Will directly print x to the console in array format.

Input and output are both strings. Given an input, say "abc", it must be converted into an array representation. First, each character will be converted into its UTF-16 binary representation, with the LSD on the left. Thus it becomes the bitstring 0000000001100001 0000000001100010 0000000001100011. 1 is treated as [[]] while 0 is treated as [].

• io.next[] would return [], then [[]], then [[]], and so on.
• io.bits would return [[];[];[];[];[];[];[];[];[[]];[[]];[]...]

io.out [[]] would push a 1 to the output buffer. The output buffer is a similar bitstring that, upon reaching a multiple of 16 bits, will reset and print as a character. [] is treated as 0, anything else is 1.

Notes

• There is no way to continue/break outside of a for loop except for early-returning.
• All arrays are immutable.
• A for loop will create a clone of the array and loop over it; changing a variable will not affect the loop.
• An identifier is any string of non-whitespace characters that don't contain []{};, so long as it isn't equal to one of the keywords =, :=, =>, or ->.
• There is no variable shadowing. When a variable is set, it will only create a new variable if it doesn't exist in an outer scope already.
• Variable names have higher precedence than function names.
• There is no order of operations, as the only "operation" is calling a function, which only has one parameter and is prefix.
• There is no grouping construct like ().

Examples

Cat program:

main _ { // Declare main function, ignore input (always []).
  bit := io.bits[] => { // Loop over bits of io.bits[].
    io.out bit; // Print each bit in order
  }
}

Explanation: The input bits are collected into an array via io.bits[] ([] is a dummy input because the function takes none). The bits are then iterated over and printed out one-by-one using io.out.

Hello, World!:

0 := []; 1 := [0]; main _ i := [
0;0;0;0;0;0;0;0;0;1;0;0;1;0;0;0; // H
0;0;0;0;0;0;0;0;0;1;1;0;0;1;0;1; // e
0;0;0;0;0;0;0;0;0;1;1;0;1;1;0;0; // l
0;0;0;0;0;0;0;0;0;1;1;0;1;1;0;0; // l
0;0;0;0;0;0;0;0;0;1;1;0;1;1;1;1; // o
0;0;0;0;0;0;0;0;0;0;1;0;1;1;0;0; // ,
0;0;0;0;0;0;0;0;0;0;1;0;0;0;0;0; //  
0;0;0;0;0;0;0;0;0;1;0;1;0;1;1;1; // W
0;0;0;0;0;0;0;0;0;1;1;0;1;1;1;1; // o
0;0;0;0;0;0;0;0;0;1;1;1;0;0;1;0; // r
0;0;0;0;0;0;0;0;0;1;1;0;1;1;0;0; // l
0;0;0;0;0;0;0;0;0;1;1;0;0;1;0;0; // d
0;0;0;0;0;0;0;0;0;0;1;0;0;0;0;1  // !
] => io.out i;

Simple boolean definition

false :=   [];
true  := [[]];

not inp {
  v := inp => {
    -> false;
  }
  -> true;
}

Explanation: The not function will loop over the input array, and will immediately return false inside the loop. In other words, if the length of the input array is greater than 0, return false. Otherwise return true.

Extended definition:

false :=   [];
true  := [[]];

// True -> False, False -> True
! inp { v := inp => -> false; -> true; }

// True if input array contains only truthy values.
&& inp {
  v := inp => _ := ! v => -> false;
  -> true;
}

// True if input array contains at least 1 truthy value.
|| inp v := inp => _ := v => -> true;

// True if number of truthy values in input array is odd 
^ inp {
  out = false;
  v := inp => _ := v => out = ! out;
  -> out;
}

Simple array static indexing: (Assumed booleans are implemented)

(0) arr i := arr => -> i;

(1) arr {
  skip = false;
  i := arr => {
    _ := skip => -> i;
    skip = true;
  }
}


// Can be extended with skip2, skip3, etc vars. 
// A general-purpose solution may be made if numbers are implemented.

Peano number implementation, including general indexing (with all above):

++ num -> [num];
-- num i := num => -> i;

0 := []; 1 := ++ 0; 2 := ++ 1; 3 := ++ 2; 4 := ++ 3; 5 := ++ 4; 6 := ++ 5; 7 := ++ 6; 8 := ++ 7; 9 := ++ 8;

// Call like this: index[arr; i];
index inp {
  arr := (0) inp;
  index = (1) inp;
  v := arr => {
    _ := ! index => -> v;
    index = -- index;
  }
}

Turing Completeness

This is an implementation of Wolfram Code Rule 110 in Foreach, proving that the language is Turing Complete.

// Boolean stuff (No possible name collisions)
bool.false := [];
bool.true := [[]];
bool.not inp {a := inp => {v := a => -> bool.false;-> bool.true;}}
bool.and inp {v := inp => _ := bool.not[v] => -> bool.false;-> bool.true;}
bool.or inp v := inp => _ := v => -> bool.true;
bool.xor inp {out = bool.false;v := inp => _ := v => out = bool.not[out];-> out;}
// Bindings
false := bool.false;
true := bool.true;
AND x -> bool.and x;
OR x -> bool.or x;
NOT x -> bool.not x;
XOR x -> bool.xor x;

// Natural Numbers (No possible name collisions) - Requires booleans
nat.0 :=[];
nat.1 :=[nat.0];
nat.2 :=[nat.1];
nat.3 :=[nat.2];
nat.4 :=[nat.3];
nat.5 :=[nat.4];
nat.6 :=[nat.5];
nat.7 :=[nat.6];
nat.8 :=[nat.7];
nat.9 :=[nat.8];
nat.inc v ->[v];
nat.dec v a := v => -> a;
// Bindings
0 := nat.0;
1 := nat.1;
2 := nat.2;
3 := nat.3;
4 := nat.4;
5 := nat.5;
6 := nat.6;
7 := nat.7;
8 := nat.8;
9 := nat.9;
inc x -> nat.inc x;
dec x -> nat.dec x;

// Indexing helper functions (No possible name collisions) - Requires natural numbers
index.0 x a := x => -> a;
index.1 x {h = bool.false;p := x => {. := h => -> p;h = bool.true;}}
index.i x {list := index.0 x;num = index.1 x;a := list => {. := bool.not[num] => -> a;num = nat.dec num;}}
// Bindings
(0) x -> index.0 x;
(1) x -> index.1 x;
index x -> index.i x;

// List "type" (No possible name collisions) - Requires indexing
list.Empty _ ->[];
list.Cons x -> x;
list.isEmpty x{a := x => -> bool.false;-> bool.true;}
list.append inp{list := index.0 inp;val := index.1 inp;if := list.isEmpty list =>{-> list.Cons[val;list.Empty[]];}-> list.Cons[list.head list;list.append[list.tail list; val]];}
list.head x -> index.0 x;
list.tail x -> index.1 x;
list.length l -> list.internal.length[index.0 l; nat.0];
list.internal.length l{list := index.0 l;if := list.isEmpty list =>{-> index.1 l;}-> list.internal.length[list.tail list; nat.inc index.1 l];}list.index l{list := index.0 l;index := index.1 l;if := bool.not[index] =>{-> list.head list;}-> list.index[list.tail list; nat.dec index];}
// Bindings
List x -> list.Empty x;
List.isEmpty x -> list.isEmpty index.0 x;
List.append x -> list.append x;
List.tail x -> list.tail x;
List.head x -> list.head x;
List.length x -> list.length x;
List.index x -> list.index x;

// Start of main program
15 := [[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]; // Hardcoded nat num lol
ITERATIONS := [0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0]; // Lazy


// Expected input format: "00000000000000000100000000000000000" (Something like that)
// Main
main _ {
  // Read input into a boolean list
  userInput = List[];
  
  count = 15;
  bit := io.bits[] => {
    if := NOT[count] => {
      count = inc 15;
      userInput = List.append[userInput; bit];
    }
    count = dec count;
  }

  // Main loop
  it := ITERATIONS => {
    print110 userInput;
    userInput = apply110 userInput;
  }
}

// Prints out list as 1s and 0s with a newline after
print110 x {
  print110.internal x;
  printChar[0;0;0;0;0;0;0;0;0;0;0;0;1;0;1;0];
}
print110.internal x {
  if := List.isEmpty[x] => -> []; // Return if empty
  if := List.head x => { // 1
    printChar [0;0;0;0;0;0;0;0;0;0;1;1;0;0;0;1];
    -> print110.internal List.tail x;
  }
  printChar [0;0;0;0;0;0;0;0;0;0;1;1;0;0;0;0];
  -> print110.internal List.tail x;
}

// Helper
printChar x c := x => io.out c;

// Used to avoid sending a ton of data between recurse iterations
prev2 = 0;
prev1 = 0;
current = 0;

// Handles the beginning and end of generating a new list "iteration"
apply110 x {
  new = List[];
  prev2 = 0;
  prev1 = List.head x;
  tail := List.tail x;
  current = List.head tail;
  out := apply110.internal[new; tail];
  prev2 = prev1;
  prev1 = current;
  current = 0;
  -> List.append[out; bit110[prev2; prev1; current]];
}
// Generates the middle of the new list "iteration" recursively
apply110.internal inp {
  newList = (0) inp;
  curList = (1) inp;
  if := List.isEmpty[curList] => -> newList;
  prev2 = prev1;
  prev1 = current;
  current = List.head curList;
  newList = List.append[newList; bit110[prev2; prev1; current]];
  -> apply110.internal[ newList; List.tail curList ];
}

// Calculates next bit from previous 3
bit110 i {
  a := (0) i;
  b := (1) i;
  c := index[i; 2];
  if := a => {
    -> XOR[b;c];
  }
  -> OR[b;c];
}