Babalang

Babalang is a thematic, Turing-complete esoteric programming language inspired by the rule system within the (also Turing-complete) indie game Baba Is You. The language is based around statements (akin to rules in Baba Is You), each with a subject, verb, one or more targets, and an optional condition. The language supports variables, loops, functions, structs, and basic IO operations. Babalang was written in March of 2020 by User:RocketRace, and is currently in version 1.1.1.
==Syntax==
A Babalang program (marked with a .baba file extension) consists of a stream of statements. Each statement consists of words. The program will execute each statement successively until it reaches EOF, after which the program halts.
===Words (and comments)===
A word is a string of alphanumeric ASCII characters (plus underscores), surrounded by any amount of whitespace. Valid words include, but are not limited to: baba, VALID_Word_123, 0123456789, and _____. Note that the language is case-insensitive by default, meaning baba and BABA are parsed as the same word. Any other characters are interpreted as whitespace, with the exception of comments. A comment, or any text following // until a line break, will be ignored by the parser.
A word may be either a keyword or an identifier. Keywords are reserved words associated with actions in the program. Identifiers represent names, such as variable, function or struct names. A word can be further divided into the following seven categories: 
Word type	Valid words
Noun 	All identifiers (and therefore all words not specified here) are, by default, nouns. The following keywords are nouns: all, empty, image, and level.
Verb 	The following keywords are verbs: is, has, make, fear, follow, eat, and mimic.
Property 	The following keywords are properties: you, win, defeat, move, fall, turn, more, right, up, left, down, chill, you2, group, shift, sink, swap, text, word, done, tele, float, and power.
Condition	The following keywords are conditions: on, near, facing, and without.
Prefix 	The following keywords are prefixes: lonely, idle, often, seldom.
Not 	Only the literal not is in this category.
Note: where-ever NOT is valid, any amount of NOT may be used instead. This will have the effect of repeatedly negating the target, meaning two NOTs will cancel each other out.
And 	Only the literal and is in this category.
These will all be detailed later on.
===Statements===
A statement is built of words in a specific pattern. Most statements are of the following pattern:
 [noun] [verb] ([noun] | [property])
Examples of this pattern include BABA IS YOU, SKULL IS EMPTY and ALL IS DONE.
While this pattern suffices for most use cases, the language supports more syntax. 
The actual pattern used for validating statements is more complex:
 [not]? [prefix]? [noun] ([not]? [condition] [noun] ([and] [noun])* [verb] [not]? ([noun] | [property]) ([and] [not]? ([noun] | [property]))* ([and] [verb] [not]? ([noun] | [property]))?
Here, [noun] represents a noun, [verb] a verb, and so on.
An abstract representation of this pattern is shown below:
 [some_prefix]? [subject] [some_conditions]? [major_action] ([AND] [minor_action])?
Here is a rundown of each of these, in order of relevance: 
subject 	Each statement must define a subject. A subject can be any noun.
major_action 	Each statement must define a major action. This begins with a verb, followed by one or more targets separated by AND. If the verb is IS, targets may be nouns or properties. If the verb is any other word, targets must be nouns. Targets may be optionally negated with NOT. Multiple NOT words will cancel each other out. A NOT word will carry its effect to all the targets following it.
Examples of major actions include: IS YOU, MAKE EMPTY, HAS A AND B, IS ALL AND MOVE, and IS NOT WIN AND DEFEAT
some_conditions	Statements can define optional conditions. If the conditions pass, the rest of the statement will be executed. This begins with a condition word, followed by one or more targets separated by AND. Each target must be a noun. The condition word may be prefixed by NOT, reverse the condition being checked for. (Note: unlike with major_action, each target in a condition may not be prefixed with NOT.)
Examples of valid conditions include: ON BABA, NOT FACING 2_OBJ, NEAR X AND Y AND Z, and NOT WITHOUT ALL AND VAR.
some_prefix 	Similar to above, a statement can define an optional prefix. If the prefix passes, the rest of the statement will be executed. A prefix is simply a prefix word, optionally prefixed with NOT to reverse its effects.
Examples of valid prefixes include: LONELY and NOT IDLE.
minor_action 	This is similar to major_action, but only allows one target. A minor action still occupies the same statement as a major action, meaning they will utilize the same conditionals.
Examples of valid minor actions include: FEAR FLAG and IS NOT FALL.
So, considering these rules, here are some valid statements:
* BABA IS YOU 
* BABA NEAR KEKE IS FALL AND NOT MOVE 
* NOT NOT NOT IDLE KEKE NOT ON KEKE HAS BABA AND BABA AND IS DEFEAT
* BABA FACING KEKE AND ALL IS ALL AND NOT BABA AND KEKE AND EMPTY
* LONELY BABA FEAR KEKE AND IS WIN
And equally, here are some invalid statements:
* BABA AND KEKE IS YOU (only one subject allowed)
* BABA HAS YOU (properties can only be used in IS statements)
* LONELY AND IDLE BABA IS YOU (only one prefix allowed)
* BABA FACING NOT KEKE IS MOVE (can't negate condition-targets)
* BABA IS (incomplete statement)
==Runtime==
Since Babalang is an interpreted language, a majority of its grunt work is done at runtime. This includes its object creation, type system, scope management and pointers.
===Objects===
As a rule of thumb, most things in Babalang are objects. Functions, structs, user-defined variables, the null-like EMPTY object... All of these are considered objects.
Objects in Babalang behave like objects in some other languages; Babalang objects are bound to variables and can be accessed like so, as well as having a type. A way to explicitly bind objects is below:
 variable_name IS some_type
where some_type is a type (see below). 
There are many ways to implicitly define / bind a variable:
An object may be copied using the following syntax:
 variable_name IS other_variable_name
This will bind the value of other_variable_name to variable_name, implicitly defining variable_name.
===Types===
There are six builtin types and two types, designed to emulate custom types. While objects are typed, the typing is dynamic (when implicitly defined). Objects may also have their object type casted to a different type, or even shadowed with a new object, by functions and methods.
Methods can be called on objects of the appropriate type.
====YOU====
YOU is a primitive type, equivalent to an unsigned 8-bit integer 2-tuple. An object can be explicitly declared as YOU like so:
 variable_name IS YOU
A YOU object contains the following information:
* x, a wrapping unsigned 8-bit integer,
* y, a wrapping unsigned 8-bit integer, and
* dir, a wrapping unsigned 2-bit integer (representing the 4 cardinal directions, starting from RIGHT and going counterclockwise).
(These fields are not accessible directly.)
The following methods can be called on YOU objects:
Method	Syntax 	Behavior
MOVE 	[YOU] IS NOT? MOVE 	Moves the X or Y position of the object one unit in the direction it is facing. Note that this is wrapping, and that an object facing UP (dir=1) with a Y position of 255 (max value) will wrap back to Y=0.
When called with NOT, moves in the opposite direction instead.
FALL 	[YOU] IS NOT? FALL 	Resets the X or Y position of the object, depending on the direction the object is facing.
If facing left or right, resets the X position. Otherwise, resets the Y position.
If called on its own, sets the value of the axis to 0. If instead called with NOT, sets the value to 255 instead.
TURN 	[YOU] IS NOT? TURN 	If called on its own, rotates the object clockwise. If instead called with NOT, rotates counterclockwise instead.
MORE 	[YOU] IS NOT? MORE 	Shifts the binary representation of the X or Y value of the object.
If facing left or right, shifts the X value. Otherwise, shifts the Y value.
If called on its own, shifts the value left by one bit. If instead called with NOT, shifts the value right by one bit.
Any values shifted outside of the range of u8 will be discarded, i.e. a value of 1 shifted right once turns into 0.
RIGHT 	[YOU] IS NOT? RIGHT	Sets the direction of the object to 0 (right).
When called with NOT, sets the direction to 2 (left) instead.
UP 	[YOU] IS NOT? UP 	Sets the direction of the object to 1 (up).
When called with NOT, sets the direction to 3 (down) instead.
LEFT 	[YOU] IS NOT? LEFT 	Sets the direction of the object to 2 (left).
When called with NOT, sets the direction to 0 (right) instead.
DOWN 	[YOU] IS NOT? DOWN 	Sets the direction of the object to 3 (down).
When called with NOT, sets the direction to 1 (up) instead.
CHILL 	[YOU] IS NOT? CHILL	Sets the X or Y value of the object to a random value between (and including) 0 and 255.
If facing left or right, randomizes the X value. Otherwise, randomizes the Y value.
This has no behavior when called with NOT.
New since version 1.1
TEXT 	[YOU] IS TEXT 	Prints the ASCII representation of the X or Y value of the object to STDOUT.
If facing left or right, prints the X value. Otherwise, prints the Y value.
This has no behavior when called with NOT.
WORD 	[YOU] IS WORD 	Copies one byte from STDIN into the X or Y value of the object.
If facing left or right, copies into the X value. Otherwise, copies into the Y value.
This has no behavior when called with NOT.
WIN 	[YOU] IS WIN 	Exits the program with return code 0.
This has no behavior when called with NOT.
DEFEAT	[YOU] IS DEFEAT 	Exits the program with return code 1.
This has no behavior when called with NOT.
SLEEP 	[YOU] IS SLEEP 	Sleeps for seconds equal to the X or Y value of the object.
If facing left or right, sleeps for X seconds. Otherwise, sleeps for Y seconds.
This has no behavior when called with NOT.
New since version 1.1
YOU objects also define the following special syntax:
 [YOU] IS NOT? [YOU] AND NOT? [YOU] AND [...]
This will go through each object in the right-hand-side of the statement, take the sum of each object's X and Y positions (modulo 256) and set the subject's X and Y values to the result. Anything prefixed with NOT will be subtracted from the final sum instead of being added to it. The keyword ALL may also be used instead of a YOU-type object to replace any object: ALL here represents the sum of all YOU-objects' values in the current scope.
For instance, the following will compute A = B + C - D:
 A IS B AND C AND NOT D
And the following will compute A = [sum of every YOU object] - C:
 A IS ALL AND NOT C
=====Edge case: ALL=====
Every method of a YOU object can also be applied to the keyword ALL. When this is done, the method will be applied to every YOU object in the current scope simultaneously, such that:
 BABA IS YOU 
 KEKE IS YOU
 BABA IS MOVE AND TURN
 KEKE IS MOVE AND TURN
is equivalent to:
 BABA IS YOU 
 KEKE IS YOU
 ALL IS MOVE AND TURN
====YOU2====
New since version 1.1
YOU2 is equivalent to YOU, except its maximum value is 2^16 - 1 (65535) rather than 2^8 - 1 (255). In general, whenever YOU deals with 255, YOU2 deals with 65535. YOU2 objects may be used whereever YOU objects are valid. Here are all the other differences between YOU2 and YOU:
Instruction	Change
SLEEP 	Instead of sleeping for seconds equivalent to the x or y value, sleeps for milliseconds instead. This allows for finer control over timing.
TEXT 	If the top 8 bits of the object's active axis value (x / y) are 0, prints the ASCII equivalent of the bottom 8 bits only. Otherwise, prints the ASCII representation of the top 8 bits, then the bottom 8 bits.
====GROUP====
GROUP is a primitive type, equivalent to an unbounded stack. A GROUP object can contain any objects, including other GROUP objects. An object can be explicitly declared as GROUP like so:
 variable_name IS GROUP
A GROUP object, in addition to functioning as a stack, has an index attribute which can be manipulated (see below) to effectively grant array access into the object.
GROUP objects define the following syntax:
 [GROUP] HAS variable_name AND variable_name AND [...]
This will push elements (the [OBJECT]s) to the GROUP, in sequential order.
GROUP objects also define the following syntax:
 [GROUP] MAKE variable_name
This will pop the last element of the GROUP and bind that object to the variable on the right side. If the variable is already bound, this will shadow the variable!
The following methods can be called on GROUP objects:
Method	Syntax 	Behavior
SHIFT 	[GROUP] IS NOT? SHIFT	Increments or decrements the index attribute of the object. If the index goes out of bounds of the stack, it will wrap around.
If called on its own, increments the index. If instead called with NOT, decrements the index.
SINK 	[GROUP] IS SINK 	Discards the last element of the stack.
This has no behavior when called with NOT.
SWAP 	[GROUP] IS SWAP 	Swaps the last element of the stack with the element at the position of its index attribute. (Swaps the last element and the i-th element)
This has no behavior when called with NOT.
TURN 	[GROUP] IS TURN 	Reverses the contents of the GROUP object in place.
This has the exact same behavior when called with NOT. (Pretend the GROUP is being rotated π radians around an axis: Rotating clockwise and counterclockwise has the same effect!)
New since version 1.1
TEXT 	[GROUP] IS TEXT 	Calls IS TEXT on every element of the GROUP.
This has no behavior when called with NOT.
WORD 	[GROUP] IS WORD 	Reads one line of input from STDIN, creates YOU objects with their X value set to each byte of the input, and finally pushes each object to the GROUP.
For example, reading foo\n (line feed) will append four elements to the GROUP.
This has no behavior when called with NOT.
====EMPTY====
This is the nil object. It is always accessible through the EMPTY noun keyword.
All methods called on EMPTY will throw an error, except TEXT, which does nothing at all.
====LEVEL====
LEVEL objects are functions. They take in arguments, execute a callback when called, and return values.
A LEVEL object is defined using the following syntax:
 variable_name IS LEVEL
 // Any amount of statements of the form `variable_name HAS argument_name AND argument_name AND [...]`
 // Any amount of statements
 variable_name IS DONE
(Note that HAS argument_name, or even IS DONE, can be fulfilled using the minor_action behavior outlined previously.)
The following syntax is the equivalent of a return statement in normal languages:
 [LEVEL] MAKE variable_name
This is only valid inside function bodies, and will return the object on the right hand side from the function. LEVEL objects will implicitly return the EMPTY object.
Already-defined LEVEL objects define the following syntax:
 [LEVEL] HAS variable_name AND variable_name AND [...]
This pushes arguments to the LEVEL object, like adding arguments to a normal-language function (fn(args)).
The following method can be called on a defined LEVEL object:
Method	Syntax 	Behavior
POWER 	[LEVEL] IS POWER	Calls the LEVEL object, binding each of its arguments to the parameter names in its definition.
This will throw an error if the amount of arguments supplied does not match the amount of parameters in the definition.
The return value of the LEVEL object will be bound to the variable. 
This cannot be called with NOT.
====IMAGE====
IMAGE objects are structs with a constructor. They hold mutable attributes which may be bound to any object.
There are two distinct types of IMAGEs: IMAGE definitions and IMAGE instances.
IMAGE definitions are defined with the following syntax:
 variable_name IS IMAGE
 // Any amount of statements of the form `variable_name HAS attribute_name AND attribute_name AND [...]`
 // A constructor is mandatory
 variable_name IS LEVEL 
 // The constructor must take AT LEAST one argument. This will be bound to `self`, like in normal object-oriented languages.
 variable_name HAS argument_name AND argument_name AND [...]
 // Any amount of statements
 variable_name IS DONE
 variable_name IS DONE
The constructor takes at least one argument. The first argument will be bound to the new instance of the IMAGE, whenever created. The constructor will implicitly return the first argument at the end of its block. It's discouraged to explicitly return from the constructor, as that introduces unintuitive behavior to your program.
IMAGE instances are instantiated the same way LEVEL objects are called: They are initialized with:
 variable_name IS [IMAGE_DEFINITION]
, after which arguments are provided and the whole thing is called with variable_name IS POWER. This will bind the object returned from the constructor into variable_name, which usually should be an IMAGE instance.
IMAGE definitions and instances have an attribute pointer, which is used to access and modify attributes of the IMAGE definition or instance.
IMAGE definitions and instances define the following syntax:
 [IMAGE] FOLLOW attribute_name
This will set the attribute pointer to any valid name provided.
 [IMAGE] MAKE variable_name
This will copy the attribute pointed to by the attribute pointer into variable_name.
 [IMAGE] EAT variable_name
This will copy the object bound to variable_name into the attribute pointed to by the attribute pointer.
===References===
A reference to an object may be created by calling [OBJECT] MIMIC [OTHER_OBJECT]. This will bind OBJECT to a reference to OTHER_OBJECT. Any operations performed on OBJECT will be performed on OTHER_OBJECT instead.
===Scopes===
Variables in Babalang are defined in their own scope.
The program scope is the outermost scope, which contains inner (potentially nested) scopes.
LEVEL callbacks, as well as IMAGE constructors are inner scopes.
By default, every variable is only accessible from the local scope, that is, they are not accessible from within an inner scope. So BABA defined in the program scope is not accessible from within the callback of KEKE, a LEVEL.
The arguments for a LEVEL are only bound in the scope of their callback. The same applies for the arguments for an IMAGE constructor.
It is possible to make a variable FLOAT, that is, it will be accessible (and mutable) from within any inner scopes. This is possible for explicit definitions, using the following syntax:
 variable_name IS FLOAT
 variable_name IS TYPE // May be YOU, GROUP, LEVEL or IMAGE
 // Continue definition like normal
This has the effect of making the variable a static variable.
Additionally, it is possible to make the result of a function call global, by prepending a FLOAT statement to a POWER statement:
 // variable_name is an instance of LEVEL or IMAGE (class)
 variable_name IS FLOAT
 variable_name IS POWER
===Loops===
A loop may be defined using the following syntax:
 variable_name IS TELE
 // Any amount of statements to loop
 variable_name IS DONE
When executed, this will repeatedly execute the statements inside the loop. The following syntax may be used to break from a loop:
 other_variable FEAR variable_name // where `variable_name` is the same as above
This will break from whatever loop variable_name is bound to! This means that you can break through multiple layers of loops with a single statement.
FEAR will unconditionally break from the loop. However, this is not very useful for most loops in which you want to break once a condition is met. This is where conditionals come in:
===Conditionals===
Any statement can be defined with conditionals. As seen under the Statements heading, there are four types of binary conditionals (ON, NEAR, FACING, WITHOUT) and two types of unary conditionals (LONELY, IDLE).
A statement with a conditional attached to it will only execute if that conditional returns true. A conditional is bound to the subject of a sentence. This means that BABA ON KEKE IS MOVE will call BABA IS MOVE iff the conditional BABA ON KEKE returns true.
Here is a reference of each binary conditional:
Conditional	Syntax 	Behavior
ON 	[OBJECT] NOT? ON [OTHER_OBJECT] AND [OTHER_OBJECT] AND [...]	"Equals" conditional
If called with NOT, the result of this conditional will be flipped!
Returns true if the subject is equal to each of the conditional-targets.
Throws an error if the objects are not of the same type!
For YOU objects, returns true if the positions are equal.
For GROUP objects, returns true if each of the elements of the GROUPs are equal.
For EMPTY objects, always returns true.
For LEVEL objects, returns true if the arguments and callbacks of the LEVELs are equivalent.
For IMAGE definitions, returns true if the attributes & constructor of the IMAGEs are equivalent.
For IMAGE instances, returns true if the attributes of the IMAGEs are equivalent, and the instances come from the same IMAGE definition.
For references, returns true if the objects point to the same object.
If the RHS is ALL, this will check this condition for every value in the current scope!
NEAR 	[OBJECT] NEAR [OTHER_OBJECT] AND [OTHER_OBJECT] AND [...] 	"Type-equals" conditional
If called with NOT, the result of this conditional will be flipped!
Returns true if each of the objects are of the same type.
If the RHS is ALL, this will check this condition for every value in the current scope!
For IMAGE instances, this also considers the IMAGE definition they were instantiated from.
FACING 	[OBJECT] FACING [OTHER_OBJECT] AND [OTHER_OBJECT] AND [...] 	"Less-than" conditional
If called with NOT, the result of this conditional will be flipped!
Returns true if [left_hand_side] < [right_hand_side].
Throws an error if the objects are not of the same type!
For YOU objects, this returns true if:
* LHS is facing right, and HLS.x < RHS.x
* LHS is facing up, and HLS.y < RHS.y
* LHS is facing left, and HLS.x > RHS.x
* LHS is facing down, and HLS.y > RHS.y
For GROUP objects, this returns true if the length of the left-hand-side is less than the length of the right-hand-side.
If the RHS is ALL, this will check this condition for every value in the current scope!
Throws an error for EMPTY, LEVEL, IMAGE objects, as well as references.
WITHOUT 	[OBJECT] WITHOUT [OTHER_OBJECT] AND [OTHER_OBJECT] AND [...]	"Does Not Contain" conditional
If called with NOT, the result of this conditional will be flipped!
Returns false if [right_hand_side] is an element of [left_hand_side].
This throws an error if the LHS is not a GROUP object!
(Note that this will copy the values of the RHS and check whether the GROUP contains the values, not the objects themselves.)
If the RHS is ALL, this will check whether every value in the current scope (even the LHS) is an element of RHS! Therefore, this would always return false.
Here is a reference of both unary conditionals:
Conditional	Syntax 	Behavior
LONELY 	NOT? LONELY [OBJECT]	"Null" conditional
If called with NOT, the result of this conditional will be flipped!
Returns true if the object is "null".
For YOU objects, returns true if the X and Y values of the object are both 0.
For GROUP objects, returns true if the length of the GROUP is 0.
For EMPTY objects, returns true.
For LEVEL objects, returns false.
For IMAGE definitions and instances, returns true if none of the attributes are defined (i.e. [IMAGE] EAT [OBJECT] has never been called)
IDLE 	NOT? IDLE [OBJECT] 	"Callable" conditional
If called with NOT, the result of this conditional will be flipped!
Returns true if the object can be called right this instant (using [OBJECT] IS POWER). 
For LEVEL objects, returns true if the number of attributes is equal to the number of parameters supplied.
For IMAGE definitions, returns true if the number of attributes is equal to the number of parameters supplied minus one (to account for the self binding).
For any other objects, returns false.
OFTEN 	NOT? OFTEN [OBJECT] 	"Probably" conditional
If called with NOT, the result of this conditional will be flipped!
Returns true randomly with 0.75 probability.
New since version 1.1
SELDOM 	NOT? SELDOM [OBJECT]	"Probably not" conditional
If called with NOT, the result of this conditional will be flipped!
Returns true randomly with 0.1667 (1 in 6) probability.
New since version 1.1
===Errors===
If the interpreter encounters a problem with your program, it will complain and throw an error.
Whenever an error is thrown, a short message is printed to the console with context to the error, and the program will halt.
Errors are not first-class. 
==Examples (commented)==
===Hello, world!===
 // Initialize constants
 // Even though these are numbers, the interpreter considers them variables.
 // This is important to keep in mind.
 1 is you and move 2 is 1 and 1 4 is 2 and 2 8 is 4 and 4 
 16 is 8 and 8 32 is 16 and 16 64 is 32 and 32
 
 // Initialize a stack
 hello_world is group
 
 // Initialize character with value "H" (decimal 72)
 H is 64 and 8
 
 // Initialize the rest of the characters
 e is 64 and 32 and 4 and 1
 l is 64 and 32 and 8 and 4
 // `X and not Y` stands for `X + (-Y)`
 o is 64 and 32 and 16 and not 1
 comma is 32 and 8 and 4
 sp is 32
 w is 64 and 32 and 16 and 8 and not 1
 r is 64 and 32 and 16 and 2
 d is 64 and 32 and 4
 excl is 32 and 1
 newline is 8 and 2
 
 // Push the appropriate characters to the stack
 hello_world has H and e and l and l and o and comma and sp 
 and w and o and r and l and d and excl and newline
 
 // Print the contents of the stack
 hello_world is text
===Echo===
 // Simple program to echo user input
 // If the input is blank, halt the program
 
 baba is group
 keke is group
 flag is tele // Loop:
 baba is word // Take input
 keke is baba and sink // Strip newline
 lonely keke fear flag // Check for empty input
 baba is text // Print output
 flag is done
===Fibonacci===
See this gist.
===99 bottles of beer===
See this gist. Written by FLeckami#3853 (@691193184251805774) on Discord!
===Truth machine===
See the truth machine page for a program, written by FLeckami#3853 (@691193184251805774) on Discord.
==External resources==
* (Official) Babalang interpreter, in Rust
Category:Languages
Category:Turing complete
Category:Implemented
Category:Thematic
Category:2020