# Serenity

Jump to navigation Jump to search
Paradigm(s) Object-oriented User:Hakerh400 2020 Turing complete Interpreter .txt

Serenity is an object-oriented esoteric programming language. In this language everything is an object, including boolean values, numbers, object keys, symbols, arrays, strings, functions, etc. There are no constraints regarding what you can do with each type of object, so you can multiply strings like numbers, call integers like functions, push a value into a literal identifier like it is an array, modify function body like it is an ordinary object, and so on. You can even modify values of literal constants: for example you can change constant ${\displaystyle 2}$ to be ${\displaystyle 3}$ and from that point on, all operations and functions that would normally return ${\displaystyle 2}$ as the result will return ${\displaystyle 3}$ instead. The are no runtime errors (all syntactically valid programs do not produce any errors).

This language has a lot of features, so documenting every single detail would require a lot of effort and will probably just introduce unnecessary complexity to this article, so we tend to explain the most important features, while the interpreter provided at the end of this article can be considered the formal specification (except if there are bugs the author is not aware of).

## Object

An object is a value that lies somewhere in the memory. All objects are unique. We access objects via references.

Each object contains a prototype (which is also an object) and can contain zero or more key-value pairs. All object must have a prototype. Any object can contain any number of key-value pairs.

Null is an object, like any other object. Its prototype is null itself. Initially it has no key-value pairs, but they can be added to it.

Prototype chain of an object is the sequence of objects that we obtain by following the prototypes recursively. Each prototype chain must end with null. If we explicitly change a prototype of an object and it creates a cyclic prototype chain (that does not end with null), the prototype of the last object in the prototype chain that did not yet create the cycle will implicitly be set to null. Null is not considered a part of a prototype chain when getting and setting key values recursively.

Keys are objects (not only strings). Each key maps to a single value. Duplicate keys cannot co-exist (the second value will overwrite the first one). Keys can be added (together with values) and they can be deleted. Accessing a key will search accross the prototype chain if the key does not exist in the current object. This applies both to getting and setting a key. It is also possible to ignore the prototype chain and search only in the current object. Each object keeps track of two arrays of keys (keys1 and keys2). The first array contains all keys sorted from the least recently added to the most recently added key. The second array contains all keys sorted from the least recently updated to the most recently updated key. The term "property" is used interchangeably with the term "key" in this article.

Hidden properties are some properties that are implicitly defined for each object, but which are not accessible or examinable directly. For example, each object has an integer value, which is ${\displaystyle 0}$ for all objects except integers (and of course integer ${\displaystyle 0}$ also has integer value ${\displaystyle 0}$).

## Types of objects

### Null

We already explained what null is. All null values reference the same null object (the null object is unique). Null can be accessed explicitly by executing instruction null, which pushes null to the stack (we explain all instructions in details in some of the next paragraphs), or it can be obtained implicitly by trying to access a non-existing key of an object.

### Root

Root is the global object. It contains all other accessible objects. There are special cases when we can store some objects that cannot be reached by recursively following key-value pairs of the root: for example null is not by default anywhere in the root (recursively) and integers (there are infinitely many of them) are also not stored anywhere (except if they literally appear in the source code), but they can be obtained by performing math operations and since all integers are also objects, we can store key-value pairs in them.

### Symbol

A symbol is a type of object which is represented by a uniqueue identifier in the source code. For example, abc is a unique symbol. All identifiers abc that appear in the source code will represent references to the same symbol. Symbols by default do not contain any keys. Some of the symbols represent instructions. When they appear in a function body, they can be executed. The list of all instructions is posted below.

### Integer

An integer is a type of object which contains integer value as a hidden property. All integers with the same integer value are also the same object. Also, by defult, they have no keys. An integers can be either positive or negative, or it can be zero. They are represented as integral values in the source code.

### Character

It is very similar to an integer, but it is limited to the range ${\displaystyle [0,255]}$ and it has different prototype. In most cases, characters are interchangeable with integers.

### Array

An array is an object which contains symbol length as a key and its value is an integer representing the length of the array. It also contains keys that are integers in range ${\displaystyle [0,{\text{length}}-1]}$ and their values are elements of the array. Note that this is how arrays are supposed to be used. It is possible to set any value as the length and even to delete the length. Adding/deleting keys does not implicitly change the length, nor does modifying the length adds/removes other keys. In general, it is impossible to distinguish arrays from non-array objects.

### String

Strings are arrays of characters.

### Function

A function is an object that contains symbol insts as a key and its value is an array of instructions that represent the function body. Functions can be called (but not only functions - any object can be called). A function can also contain other useful keys, such as symbol scope, which points to the current scope. A function can also contain symbol prototype, which can be used to instantiate new objects. Functions can also contain any number of other keys.

### Scope

A scope is an object that is usually bound to a function. It contains variables and/or arguments. Scopes can be linked in a prototype chain, so that we can achieve the effect of closures and shadowing variables. A scope can also contain key this, which can be used in functions that are bound to a specific object (methods).

## Syntax

### Objects

Integers are literal integral values in decimal or hexadecimal. Examples: 35, -0x123, 0

Symbols are literal identifiers. They can contain alphanumeric characters and hyphens (underscores are not allowed). Example: someIdent

Objects are represented as key-value pairs (no commas) surrounded by a pair of braces. Example:

{
someKey: someValue
someOtherKey: 123
}


Arrays are denoted by elements surrounded by a pair of brackets (no commas). Example: [a b c].

Arrays can also contain labels. A label definition is an identifier followed by a colon, while label reference is a colon followed by an identifier. Label definitions are removed from arrays, while label references are replaced with corresponding index (in the array) of the label definition with the same name. Example: [x lab: y z :lab r] (it is equivalent to [x y z 1 r]).

Characters are surrounded by '. Character \ can be used to escape any other character. Examples: 'a', '\\', '\''

Strings are denoted by characters surrounded by a pair of ". Character \ can be used to escape any other character. Example: "abc\\de\"fgh"

### Program

Program consists of a single object, which is interpreted as a function and implicitly called.

## Structure of the root object

### Root

The root object initially contains a single property mainStack, which contains the main stack.

### Main stack

The main stack is an array that contains stack frames for all functions that are currently called.

### Stack frame

Each stack frame contains the following properties:

• func - The current function
• inst - Instruction pointer (integer)
• scope - The current scope
• stack - Local stack for that function

### Local stack

A local stack is contained in each stack frame. Everything that the function does operates on the local stack, except calling another function or returning from the current function, which operates on the main stack (calling a function creates a new stack frame, while returning from a function deletes the last stack frame).

## Instructions

Here is the table of all instructions. Everything that appears in the function body and is not an instruction will be pushed to the stack. All instructions implicitly increment the inst (instruction pointer) of the current stack frame, unless stated otherwise. All instructions must be symbols.

Operands are taken (popped) from the top of the stack. If an instruction takes two operands x and y, the last element on the stack is y and the second last element is x. Same applies to more arguments. Arithmetical operations implicitly retrieve the integer value of the arguments.

The last element of the stack is laso called the top of the stack. When we say ${\displaystyle n}$-th element of the stack, it mans from the top of the stack (${\displaystyle 0}$-th element if the last element of the stack, ${\displaystyle 1}$-th is the second last element, and so on).

Instruction Operands Description
nop No effects besides incrementing the instruction pointer
plus ${\displaystyle x}$ Convert ${\displaystyle x}$ to an integer (get its integer value) and push it to the stack
minus ${\displaystyle x}$ Push ${\displaystyle -x}$
not ${\displaystyle x}$ If ${\displaystyle x}$ is nonzero push ${\displaystyle 0}$, otherwise push ${\displaystyle 1}$
neg ${\displaystyle x}$ Push ${\displaystyle -(x+1)}$
inc ${\displaystyle x}$ Push ${\displaystyle x+1}$
dec ${\displaystyle x}$ Push ${\displaystyle x-1}$
and ${\displaystyle x,y}$ Push binary AND of ${\displaystyle x}$ and ${\displaystyle y}$
or ${\displaystyle x,y}$ Push binary OR of ${\displaystyle x}$ and ${\displaystyle y}$
xor ${\displaystyle x,y}$ Push binary XOR of ${\displaystyle x}$ and ${\displaystyle y}$
shl ${\displaystyle x,y}$ Push ${\displaystyle \left\lfloor x\cdot 2^{y}\right\rfloor }$
shr ${\displaystyle x,y}$ Push ${\displaystyle \left\lfloor x\cdot 2^{-y}\right\rfloor }$
add ${\displaystyle x,y}$ Push ${\displaystyle x+y}$
sub ${\displaystyle x,y}$ Push ${\displaystyle x-y}$
mul ${\displaystyle x,y}$ Push ${\displaystyle x\cdot y}$
div ${\displaystyle x,y}$ If ${\displaystyle y\neq 0}$ push ${\displaystyle \left\lfloor {\frac {x}{y}}\right\rfloor }$, otherwise push null
mod ${\displaystyle x,y}$ If ${\displaystyle y\neq 0}$ push ${\displaystyle (x\mod y)}$, otherwise push null
exp ${\displaystyle x,y}$ If ${\displaystyle y>0}$ or ${\displaystyle y=0\land x\neq 0}$ push ${\displaystyle x^{y}}$, otherwise push null
lt ${\displaystyle x,y}$ If ${\displaystyle x push ${\displaystyle 1}$, otherwise push ${\displaystyle 0}$
gt ${\displaystyle x,y}$ If ${\displaystyle x>y}$ push ${\displaystyle 1}$, otherwise push ${\displaystyle 0}$
le ${\displaystyle x,y}$ If ${\displaystyle x\leq y}$ push ${\displaystyle 1}$, otherwise push ${\displaystyle 0}$
ge ${\displaystyle x,y}$ If ${\displaystyle x\geq y}$ push ${\displaystyle 1}$, otherwise push ${\displaystyle 0}$
push Push the next element from the function body to the stack and increment the instruction pointer once again
pop ${\displaystyle x}$ Delete the ${\displaystyle x}$-th element from of the stack (the ${\displaystyle 0}$-th element is the top element after popping ${\displaystyle x}$)
disc ${\displaystyle x}$ Simply discard ${\displaystyle x}$. It is effectively the same as pop with operand ${\displaystyle 0}$
move ${\displaystyle x}$ Move the ${\displaystyle x}$-th element from of the stack to the top of the stack (the size of the stack does not change, except from implicitly popping ${\displaystyle x}$)
copy ${\displaystyle x}$ Push the ${\displaystyle x}$-th element from of the stack (but also leave it in the original position)
dupe ${\displaystyle x}$ Duplicate the last element of the stack. It is effectively the same as copy with argument ${\displaystyle 0}$
swap ${\displaystyle x,y}$ Swap ${\displaystyle x}$-th and ${\displaystyle y}$-th element from the stack
eq ${\displaystyle x,y}$ If both ${\displaystyle x}$ and ${\displaystyle y}$ are references to the same object then push ${\displaystyle 1}$, otherwise push ${\displaystyle 0}$
neq ${\displaystyle x,y}$ If both ${\displaystyle x}$ and ${\displaystyle y}$ are not references to the same object then push ${\displaystyle 1}$, otherwise push ${\displaystyle 0}$
has ${\displaystyle x,y}$ If ${\displaystyle x}$ has ${\displaystyle y}$ as a key (including prototype chain search), then push ${\displaystyle 1}$, otherwise push ${\displaystyle 0}$
get ${\displaystyle x,y}$ If ${\displaystyle x}$ has ${\displaystyle y}$ as a key (including prototype chain search), then push ${\displaystyle x[y]}$, otherwise push null
set ${\displaystyle x,y,z}$ Perform ${\displaystyle x[y]=z}$. If ${\displaystyle x}$ does not contain ${\displaystyle y}$, then find the first object in the prototype chain that contains ${\displaystyle y}$ as a key and set its value to ${\displaystyle z}$. However, if no objects in the prototype chain contain ${\displaystyle y}$, then set it into ${\displaystyle x}$.
setk ${\displaystyle x,y,z}$ Similar to set, but keeps ${\displaystyle x}$ on the stack (does not pop it). It is useful if you want to set multiple properties in a row.
delete ${\displaystyle x,y}$ Delete key ${\displaystyle y}$ from object ${\displaystyle x}$ (include prototype chain search)
deletek ${\displaystyle x,y}$ Similar to delete, but keeps ${\displaystyle x}$ on the stack
hasl ${\displaystyle x,y}$ Similar to has, but performs local operations in the object ${\displaystyle x}$ (does not include prototype chain search)
getl ${\displaystyle x,y}$ Similar to get, but local
setl ${\displaystyle x,y,z}$ Similar to set, but local
setlk ${\displaystyle x,y,z}$ Similar to setk, but local
deletel ${\displaystyle x,y}$ Similar to delete, but local
deletelk ${\displaystyle x,y}$ Similar to deletek, but local
getProto ${\displaystyle x}$ Push the prototype of ${\displaystyle x}$
setProto ${\displaystyle x,y}$ Set ${\displaystyle y}$ as the prototype of ${\displaystyle x}$
keys1 ${\displaystyle x}$ Push keys1 of ${\displaystyle x}$
keys2 ${\displaystyle x}$ Push keys2 of ${\displaystyle x}$
prod ${\displaystyle x,y}$ Push dictionary product of ${\displaystyle x}$ and ${\displaystyle y}$, as explained in User:Hakerh400/Code_golf_challenges#Product_of_two_dictionaries
prod* ${\displaystyle x}$ Replace each object that was ever created in the program with the dictionary product of that object with ${\displaystyle x}$ (this also applies to constants like integers and chars, and it also applies to all other objects like root, null, etc). Note that the asterisk * is literally a part of the symbol name and it is the only identifier that is allowed to contain * in its name.
raw ${\displaystyle x}$ Push a new object that has prototype ${\displaystyle x}$ and no keys
obj Push a new object that has the same prototype as all other objects that appear in the source code as literal objects
int ${\displaystyle x}$ Alias for plus
char ${\displaystyle x}$ Push ${\displaystyle x}$ converted to a character
arr ${\displaystyle x_{0},x_{1},\dots ,x_{y-1},y}$ Push an array containing elements ${\displaystyle x_{0},x_{1},\dots ,x_{y-1}}$
str ${\displaystyle x_{0},x_{1},\dots ,x_{y-1},y}$ Similar to arr, but converts each element to a character and pushes the string to the stack
clone ${\displaystyle x}$ Push a new object that has the same prototype, key-value pairs, keys1 and keys2 as ${\displaystyle x}$. Hidden properties, such as integer value, are not copied (the new object has integer value ${\displaystyle 0}$).
pusha ${\displaystyle x,y}$ Interpret ${\displaystyle x}$ as an array and push ${\displaystyle y}$ into it (to the end).
pushk ${\displaystyle x,y}$ Similar to pusha, put keeps ${\displaystyle x}$ on the stack
popa ${\displaystyle x}$ Pop the last element of array ${\displaystyle x}$ and push it to the stack
null Push null
root Push the root
mainStack Push the main stack
frame Push the current stack frame
func Push the current function
scope Push the current scope
this Push this from the current scope
getv ${\displaystyle x}$ Get the value of the key ${\displaystyle x}$ from the current scope (effectively the variable ${\displaystyle x}$ from the current function)
setv ${\displaystyle x,y}$ Set the value of the key ${\displaystyle x}$ from the current scope to ${\displaystyle y}$
setvk ${\displaystyle x,y}$ Similar to setv, but keeps ${\displaystyle y}$ on the stack
getvl ${\displaystyle x}$ Similar to getv, but does not consider the scopes prototype chain of the scope
setvl ${\displaystyle x,y}$ Similar to setv, but does not consider the scopes prototype chain of the scope
setvlk ${\displaystyle x,y}$ Similar to setvl, but keeps ${\displaystyle y}$ on the stack
enter Update the current stack frame scope to be a new object whose prototype is the old scope
leave Update the current stack frame scope to be the prototype of the current scope
bind ${\displaystyle x}$ Set the key scope of x to to the scope of the current stack frame. Keeps ${\displaystyle x}$ on the stack.
arg ${\displaystyle x}$ Push a new object whose prototype is the value of the key scope of ${\displaystyle x}$. Keeps ${\displaystyle x}$ on the stack.
args ${\displaystyle x,y_{0},y_{1},\dots ,y_{z-1},z}$ Push an array containing elements ${\displaystyle y_{0},y_{1},\dots ,y_{z-1}}$ and whose prototype is the value of the scope property of ${\displaystyle x}$. Keeps ${\displaystyle x}$ on the stack.
crg ${\displaystyle x,y_{0},y_{1},\dots ,y_{z-1},z}$ Alias for args call
cbs ${\displaystyle x,y}$ Alias for clone bind setv
jz ${\displaystyle x,y}$ If ${\displaystyle x=0}$ set the instruction pointer of the current stack frame to ${\displaystyle y}$
jnz ${\displaystyle x,y}$ If ${\displaystyle x\neq 0}$ set the instruction pointer of the current stack frame to ${\displaystyle y}$
jmp ${\displaystyle x}$ Set the instruction pointer of the current stack frame to ${\displaystyle x}$
alt ${\displaystyle x,y}$ If ${\displaystyle x\neq 0}$ set the instruction pointer of the current stack frame to ${\displaystyle y}$, otherwise set the instruction pointer of the current stack frame to ${\displaystyle z}$
call ${\displaystyle x,y}$ Call function ${\displaystyle x}$ with scope ${\displaystyle y}$. It creates a new stack frame (and pushes it to the main stack) whose func is ${\displaystyle x}$ and scope is ${\displaystyle y}$. Instruction pointer is ${\displaystyle 0}$ and the stack of that stack frame is a new array.
method ${\displaystyle x,y,z}$ Set property this of ${\displaystyle z}$ to ${\displaystyle y}$ and then call ${\displaystyle x}$ with scope ${\displaystyle z}$
new ${\displaystyle x,y}$ Set property this of ${\displaystyle y}$ to a new object whose prototype is the value of the prototype property of ${\displaystyle x}$ and then call ${\displaystyle x}$ with scope ${\displaystyle y}$
ret ${\displaystyle x}$ Pop the last stack frame and push ${\displaystyle x}$ to the stack of the new last stack frame (effectively returns ${\displaystyle x}$ to the previous function)
retv / Pop the last stack frame (effectively returns void). This instruction is performed implicitly if the instruction pointer becomes greater or equal to the length of the insts array of the current function.
in / Push the input string (reads the entire input at once). Pushes the same string each time it is called.
out ${\displaystyle x}$ Output string ${\displaystyle x}$ and halt the program. Note that this is the only way to halt the program. Reaching the end of the main function does not implicitly halt the program (and what happens if the end of the main function is reached can be deduced from the rest of this article).

## Examples

### Hello, World!

{insts: [
"Hello, World!" out
]}


### Cat program

{insts: [
in out
]}


### Print digits from 0 to 9

{insts: [
s 0 str setv
i 0 setv

loop:
i getv 10 eq :end jnz
s getv i getv 0x30 or char pusha
i i getv inc setv
:loop jmp

end:
s getv out
]}


### Reverse the input string

{insts: [
a in setv
b 0 str setv

loop:
a getv length get :end jz
b getv a getv popa pusha
:loop jmp

end:
b getv out
]}


### Add two integers

Input contains two non-negative integers separated by a space character.

{insts: [
rev {insts: [
a 0 getv clone setv
b 0 str setv

loop:
a getv length get :end jz
b getv a getv popa pusha
:loop jmp

end:
b getv ret
]} cbs

split {insts: [
str1 0 getv clone setv
str2 0 str setv

loop:
str1 getv dupe length get dec get ' ' eq :end jnz
str2 getv str1 getv popa pusha
:loop jmp

end:
str1 getv dupe popa disc
rev getv str2 getv 1 crg
2 arr ret
]} cbs

map {insts: [
array 0 getv setv
fn 1 getv setv

arrayNew 0 arr setv
len array getv length get setv
index 0 setv

loop:
index getv len getv eq :end jnz
enter
elem array getv index getv get setv
arrayNew getv fn getv elem getv index getv 2 crg pusha
leave
index dupe getv inc setv
:loop jmp

end:
arrayNew getv ret
]} cbs

str2int {insts: [
s 0 getv clone setv
num 0 setv
mask 1 setv

loop:
s getv length get :end jz
num dupe getv s getv popa 0x30 xor mask getv mul add setv
mask dupe getv 10 mul setv
:loop jmp

end:
num getv ret
]} cbs

int2str {insts: [
num 0 getv setv
s 0 str setv

loop:
num getv :end jz
s getv num getv 10 mod 0x30 or char pusha
num dupe getv 10 div setv
:loop jmp

end:
s dupe getv rev getv 1 move 1 crg setv
s getv dupe length get :ret jnz
'0' pushk
ret: ret
]} cbs

nums {insts: [
f {insts: [
str2int getv 0 getv 1 crg ret
]} cbs

map getv split getv 0 getv 1 crg f getv 2 crg ret
]} cbs

x y
nums getv in 1 crg dupe
1 2 swap popa setv
popa setv

int2str getv
x getv y getv add
1 crg out
]}


### Test

This example is used to test the correctness of the interpreter. It should output string PQcdefgRQ8

{insts: [rev {insts: [output 0x50 char dupe inc char 2 str setv i 1 2 3 j k 0 5 swap 1 move disc j
input getv length get 1 pop setv i i getv dec setv i getv 0 lt 75 jnz c input getv i getv get setv
output getv 5 output getv 1 pop length get c getv setk length output getv length get inc set output
getv dupe popa inc char pusha 29 jmp push this null setv null root mainStack frame func scope this
obj null output getv setk prod* this clone ret]} bind setv rev getv arg input rev getv arg input
"abcde" setk call setk call 2 3 exp 0x30 or char pushk out]}


### Replace a constant

{insts: [
obj 12345 12347 setk prod*
0x30 12345 10 mod or 1 str out
]}


This program outputs 7. It first replaces constant ${\displaystyle 12345}$ with ${\displaystyle 12347}$, then pushes ${\displaystyle 12345}$ to the stack (which is now actually ${\displaystyle 12347}$), takes the last digit and converts it to a string. We could also replace, say, ${\displaystyle 5}$ with ${\displaystyle 7}$ and then push ${\displaystyle 5}$ (which should push ${\displaystyle 7}$ instead) and output it, but it would cause problems, because it would interfere with the value of the instruction pointer and may cause very unpredictable and weird side effects. For example, this program:

{insts: [
obj 5 7 setk prod*
0x30 5 or 1 str out
]}


outputs the zero byte \x00 instead of 7, because when the instruction pointer becomes ${\displaystyle 5}$, it will actually be ${\displaystyle 7}$ and it will execute or on the empty stack (because 0x30 5 are skipped), which will push ${\displaystyle 0}$ onto the stack, and then converts it to a string of ${\displaystyle 1}$ character and outputs it. Now consider this example:

{insts: [
obj 5 11 setk prod*
0x30 5 or 1 str out
]}


It is an infinite loop. It does not halt, because the instruction out is never executed.

### Rename an instruction

It is also possible to rename any instruction. For example, we can rename (actually keeping the old name too) instruction out to print, as can be seen in the following example:

{insts: [
obj print push out setk prod*
"ok" print
]}


It prints ok, and we achieved it by executing the instruction print, which we defined to be an alias for out.