beeswax

From Esolang
Jump to navigation Jump to search

beeswax is a stack-based 2 dimensional esoteric programming language developed by user:Albedo (Manuel Lohmann). Beeswax draws inspiration from bees moving around on a honeycomb, and is partly inspired by languages like Cardinal etc. and the abstract board game Hive which uses hexagonal game pieces. The instruction pointers (bees) move around on a 2D hexagonal grid (the honeycomb). beeswax programs can manipulate their own source code, change the program size, and can read and write files.


  >       NN      p
> d#_8~2~(P~3~.~1~>{` bottles of beer on the wall, `{` bottles of beer.`q
d`.llaw eht no reeb fo selttob `{pLM` ,dnuora ti ssap dna nwod eno ekaT`N<
q`.llaw eht no reeb fo elttob ` {<
 >        NN       >{` bottle of beer on the wall, `{` bottle of beer.`N  q
pN `.llaw eht no reeb fo selttob erom on ,dnuora ti ssap dna nwod eno ekaT`<
>N`No more bottles of beer on the wall, no more bottles of beer.`N  q
;`.llaw eht no reeb fo selttob 99 ,erom emos yub dna erots eht ot oG`<

beeswax example program: 99 bottles of beer


Introduction

Honeycomb structure and source code layout

The programming language draws inspiration from bees and honeycombs, so the instruction pointers (“bees”) travel through the program (“honeycomb”) along a hexagonal grid. Every honeycomb location has 6 neighbors.

Honeycomb structure

 a — b — c — d
  \ / \ / \ / \
   e — f — g — h
    \ / \ / \ / \
     i — j — k — l


Beeswax programs are stored in a rectangular format. A program using the layout of the honeycomb structure above would look like this:


 abcd
  efgh
   ijkl

Movement directions

Bees (IPs) can move in one of 6 directions that are determined like below:

(β marks the IP/bee)


   2 — 1
  / \ / \
 3 — β — 0
  \ / \ /
   4 — 5

The analogous neighborhood layout in a beeswax program looks like this:

 21
 3β0
  45

Stack layout and types of stacks

Local stacks

Every bee has a “personal” fixed size stack, carrying three UInt64 values, called local stack or lstack. Every local stack is initialized to [0,0,0]• at the start of the program. marks the top of the stack.

Global stacks

To store bigger amounts of data there is also a global stack (gstack) available where bees can drop values onto and pick up values from.

The global stack is not limited in size and only allows basic stack operations.

All arithmetic, bit manipulation and other operations have to be executed by bees on their local stacks. So, before any data on the global stack can be used for calculations etc. a bee has to pick up values from the global stack. After executing the instructions the resulting values can be put back onto the global stack.

Source code manipulations, self modification, coordinate system

Bees can also drop values anywhere in the source code, and can pick up values from anywhere (analogous to flying to a location and manipulating certain cells in the honeycomb). So, self-modifying source code can be realized.

Source code coordinate system

The origin of the coordinate system [row,column] = [1,1] is in the upper left corner. beeswax uses 1-based indexing. Bees that step outside the given honeycomb area are deleted, unless they are dropping values to cells that lie outside the current area of the honeycomb, which would let the honeycomb grow to the proper dimensions.

Examples of self modification

Positive growth of the honeycomb

 *PF((F(D

The command P increments the top value of lstack.

[0,0,1]•

Then F sets all lstack values to the top value.

[1,1,1]•

(( executes two arithmetic shifts left.

[1,1,4]•

F sets all lstack values to the top value again.

[4,4,4]•

The next ( executes 4 arithmetic shifts, because the 2nd lstack value is 4 now.

[4,4,64]•

And the final D drops the lstack top value (its according character) to [row,column] = lstack[2nd,3rd].

So, the value 64 (its associated unicode character @) is dropped at (row,column)=(4,4). This extends the source code to a rectangle encompassing all code:

 *PF((F(D
 
 
    @

“Negative” growth of honeycomb, coordinate system reset

Because the coordinate indices of the honeycomb are 1-based, growth in negative direction (‘up’ and ‘left’ in the source code) is only possible if the 2nd and/or 3rd local stack values are set to zero. Growth in negative direction can only be realized by steps of 1. The coordinate origin of the resulting source code is reset to (row,column) = (1,1) again:

 *4F(@0~0@D

results in

 @
  *4F(@0~0@D

The new coordinate origin (1,1) of the honeycomb is set to the new upper left corner, where the @ was put.

Available instructions in beeswax

Beeswax makes use of almost the entire range of printable ASCII characters for instructions.

Initial pointer creation

These instructions only get active at the beginning of the program.

instruction explanation
* Create bees moving in all directions 0,1,2,3,4,5
\ Create bees moving along the main direction 2/5
/ Create bees moving along the main direction 1/4
_ Create bees moving along the main direction 0/3

Cloning and deleting bees

Instruction Explanation
m Catch and delete bees coming from the 2/5 direction. Bees coming from other directions are not affected.
n Catch and delete bees coming from the 1/4 direction. Bees coming from other directions are not affected.
o Catch and delete bees coming from the 0/3 direction. Bees coming from other directions are not affected.
# Catch and delete bees coming from any direction.
X Spread identical copies of incoming bee in all directions, except the direction the bee came from.
E Spread identical copies of incoming bee in 0/3 direction, except the direction the bee came from.
H Spread identical copies of incoming bee in 1/4 direction, except the direction the bee came from.
W Spread identical copies of incoming bee in 2/5 direction, except the direction the bee came from.

Important notes about bee creation and bee execution order

At the beginning of a beeswax program, during initialization, bees are created in a fixed order as follows:

First, the interpreter reads in the program code and creates the according honeycomb. Then, the honeycomb is scanned for the initial bee creation instructions \*, \, / and _. The honeycomb is scanned column-wise, starting with the leftmost column. The column is scanned from top to bottom, then the process is continued in the next column, until the whole honeycomb is scanned.

Each of the instructions creates a set of bees, which are pushed on a pointer/bee stack in order of creation. For each creation instruction, the standard creation order of bees always follows the pattern below, in a counterclockwise fashion, starting at the lowest number. This always leaves the bee that was created last on top of the pointer stack:

   2   1
       
 3   β   0
       
   4   5


In the following examples marks the top of the stack.

* → [... 0 1 2 3 4 5]•

\ → [... 2 5]•

/ → [... 1 4]•

_ → [... 0 3]•

During program execution, the instructions are executed according to the order of the bees on the pointer stack, from top to bottom. The last created bee is always on top of the stack and, every tick, its instruction is always executed first.

The cloning instructions X, E, H and W create bees in an analogous fashion, always leaving out the opposite direction the bee is coming from:

X: Check directions from 0 to 5, if the original bee is already moving in this direction, just let the bee move on. If the original bee is moving in the opposite direction, don’t create a clone. For every other position, clone the original bee and set its direction to the appropriate direction and push it on the pointer stack.

E: Check direction 0, then direction 3. If the original bee is moving in one of these directions, just let the bee move on and don’t create a clone. If the original bee is coming from any different direction, change the direction of the original bee to 0, push a clone of that bee on the pointer stack, moving in direction 3.

H: Check direction 1, then direction 4. If the original bee is moving in one of these directions, just let the bee move on and don’t create a clone. If the original bee is coming from any different direction, change the direction of the original bee to 1, push a clone of that bee on the pointer stack, moving in direction 4.

W: Check direction 2, then direction 5. If the original bee is moving in one of these directions, just let the bee move on and don’t create a clone. If the original bee is coming from any different direction, change the direction of the original bee to 2, push a clone of that bee on the pointer stack, moving in direction 5.


Here is a beeswax example program that prints Hello, World! to the console. This should demonstrate quite nicely how the bees that are created during initialization end up on the pointer stack. I leave it to the user to figure out the details. It shouldn’t be too hard:

 W o    l   `
  ``     e  H
  `*`r`#`l`_`ld!
   ``      \/
   , o


If a bee leaves the honeycomb during program execution, it gets marked as dead. Once all instructions of the pointer stack are executed, the dead bees get deleted, and the stack gets cleaned up, leaving the general orders of bees intact.

Program termination

Instruction Explanation
; Terminate program


Movement and redirection related instructions

Instruction Explanation
> Redirect bee to the right/direction 0
d Redirect bee to the upper right/direction 1
b Redirect bee to the upper left/direction 2
< Redirect bee to the left/direction 3
p Redirect bee to the lower left/direction 4
q Redirect bee to the lower right/direction 5
a Turn direction 1 step clockwise
x Turn direction 1 step counterclockwise.
s Mirror direction along the main diagonal 2/5. Bees moving along the mirror axis are not affected.
t Mirror direction along the main diagonal 1/4. Bees moving along the mirror axis are not affected.
u Mirror direction along the main diagonal 0/3. Bees moving along the mirror axis are not affected.
j Mirror direction along the half axis │ between 1/4 and 2/5.
k Mirror direction along the half axis / between 0/3 and 1/4.
l Mirror direction along the half axis \ between 0/3 and 2/5.
O Mirror direction to opposite direction.

Table with all reflections and direction changes

incoming x a s t u j k l O
0 1 5 4 2 0 3 1 5 3
1 2 0 3 1 5 2 0 4 2
2 3 1 2 0 4 1 5 3 1
3 4 2 1 5 3 0 4 2 0
4 5 3 0 4 2 5 3 1 5
5 0 4 5 3 1 4 2 0 4
Instruction Explanation
J Jump to [row,column] = lstack[top, 2nd] value; keep direction of movement.

Table with all cloning and deletion directions

incoming m n o # X E H W
0 - - X X 12345 3 1/4 2/5
1 - X - X 02345 0/3 4 2/5
2 X - - X 01345 0/3 1/4 5
3 - - X X 01245 0 1/4 2/5
4 - X - X 01235 0/3 1 2/5
5 X - - X 01234 0/3 1/4 2

Program flow control/conditional operations

Instruction Explanation
' if lstack top value = 0 then skip next instruction, otherwise don’t skip next instruction.
" if lstack top value > 0 then skip next instruction, otherwise don’t skip next instruction.
K if lstack top value = 2nd value then skip next instruction, otherwise don’t skip next instruction.
L if lstack top value > 2nd value then skip next instruction, otherwise don’t skip next instruction.
Q unconditionally skip next instruction.
v Pause movement for 1 tick.
^ Pause movement for 2 ticks.

Pick up/drop values in the honeycomb (code manipulation)

[r,c] describes the [row,column] of a honeycomb cell.

Absolute addressing

Instruction Explanation
D Drop lstack top value to location [r,c]=lstack[2nd,3rd] value. Extend honeycomb if needed to suit the requirement.
G Get value from honeycomb[r,c]=[2nd,3rd] and put it as top value on local stack. If [r,c] outside honeycomb, then lstack top value=0

Relative addressing

Instruction Explanation
Y Drop local stack top value to cell at relative [r,c]=[2nd,3rd]. If relative [r,c] are lower than absolute [1,1], nothing is dropped.
Z Get value from cell at relative [r,c]=[2nd,3rd] and put it as top value on local stack. If relative [r,c] are lower than absolute [1,1], then lstack top value=0.

As everyone knows, bees don’t have a concept of negative numbers, but they discovered that they can use the most significant bit of an address to get around that. Thus, coordinates relative to a bee’s position are realized by the [two’s complements](https://en.wikipedia.org/wiki/Two's_complement) of the coordinates. This way, half of the 64-bit address space is available for local addressing without wraparound in each direction.

The maximum positve 64-bit two’s complement address is 9223372036854775807 or 0x7fffffffffffffff in 64 bit hex. All values from 0 up to this value translate identically to the same 64 bit value. All values n in the opposite (negative) direction translate to 2^64-n. For example: n=-1 is addressed by 18446744073709551615. n=-9223372036854775808 is addressed by 9223372036854775808.

Always keep the UInt64 wrap-around in mind!

Local and global stack manipulations

  • marks the top of the stack.

Local stack (lstack) instructions

Instruction Explanation Example
~ Flip top and 2nd lstack values. lstack[3,2,1]• → lstack[3,1,2]•
@ Flip top and bottom lstack values. lstack[3,2,1]• → lstack[1,2,3]•
F Set all lstack values to top value. lstack[3,2,1]• → lstack[1,1,1]•
z Set all lstack values to zero. lstack[3,2,1]• → lstack[0,0,0]•

Global stack (gstack) instructions

- inside lstack stands for irrelevant values for executing an instruction.

Instruction Explanation Example
y Rotate global stack down by [-,steps,depth]•, depth=0 or depth>stack len.→depth=stack len., steps>depth → steps= steps%depth local [-,2,4]•, gstack[5,4,3,2,1]• → gstack[5,2,1,4,3]•
h Rotate global stack up by [-,steps,depth]•, depth=0 or depth>stack len. → depth=stack len., steps>depth → steps= steps%depth local [-,5,4]•, gstack[5,4,3,2,1]• → gstack[5,3,2,1,4]•
= Duplicate top value of gstack. gstack[4,3,2,1]• → gstack[4,3,2,1,1]•
? Pop top gstack value. gstack[4,3,2,1]• → gstack[4,3,2]•
A Push gstack length on top of gstack. gstack[4,3,2,1]• → gstack[4,3,2,1,4]•

Local/global stack interaction

Instruction Explanation
e Flush all lstack values on the gstack and set lstack to [0,0,0]•

lstack[a,b,c]• is pushed on gstack[...,c,b,a]•

U Flush top three gstack values on lstack and pop top three values from gstack. Reverse operation to e.

gstack[...,c,b,a]• → lstack[a,b,c]•, gstack[...]•

f Get top value from lstack and push it on top of gstack.
g Get top value from gstack and put it as top value of lstack.

Arithmetic operations

Instruction Explanation Example
+ top=top+2nd lstack[3,2,1]• → lstack[3,2,3]•
- top=top-2nd lstack[3,2,1]• → lstack[3,2,18446744073709551615]• (64-bit wrap-around)
. top=top*2nd lstack[3,2,1]• → lstack[3,2,2]•
: top=top/2nd lstack[3,2,1]• → lstack[3,2,0]• (integer division)
% top=top%2nd lstack[3,2,5]•→ lstack[3,2,1]• (mod operator)
0,...,9 set top to value e.g: '7' → [3,2,1]• → [3,2,7]•
P top=top+1 lstack[3,2,1]• → [3,2,2]• (increment top value)
M top=top-1 lstack[3,2,1]• → [3,2,0]• (decrement top value)
B top=top^2nd lstack[1,2,3]• → lstack[1,2,9]•

Bitwise operations

Instruction Explanation Example
& top=top AND 2nd lstack[3,2,1]• → lstack[3,2,0]•
| top=top OR 2nd lstack[3,2,1]• → lstack[3,2,3]•
$ top=top XOR 2nd lstack[3,2,1]• → lstack[3,2,3]•
! top=NOT top lstack[3,2,1]• → lstack[3,2,18446744073709551614]•
( top=top << 2nd lstack[3,2,1]• → lstack[3,2,2]• (arithmetic shift left)
) top=top >>> 2nd lstack[3,2,1]• → lstack[3,2,0]• (logical shift right)
[ top=top<<(2nd%64)+top>>>(64-2nd%64) lstack[3,2,8646629796688953342]• → lstack[3,2,16274878703619526647]• (roll bits left)
] top=top>>>(2nd%64)1+top<<(64-2nd%64) lstack[3,2,8646629796688953342]• → lstack[3,2,2143642225978703743]• (roll bits right)

Local/global I/O operations

Local stack related I/O

Instruction Execution Explanation
, top=Int(STDIN) Read character from STDIN and push its value on top of lstack.
T top=(STDIN) Read integer from STDIN and push its value ont top of lstack.
{ STDOUT=top Return lstack top value as integer to STDOUT.
} STDOUT=Char(top) Return lstack top value as character(Unicode) to STDOUT.

Global stack related I/O

Instruction Execution Explanation
C top=Int(STDIN) Example
V Read string from STDIN and push its content as Unicode codepoint values on gstack in reverse order. The last character of the input string ends on top of gstack and is always guaranteed to be CR (\n) on both CR and CRLF (\r\n) operating systems.
i top=(STDIN) Read integer from STDIN and push its value on gstack.
I STDOUT=top Return gstack top value as integer to STDOUT.
C STDOUT=Char(top) Return lstack top value as character to STDOUT.
` Toggle STDOUT Return all following encountered symbols as characters(ASCII/Unicode) directly to STDOUT. The next ` switches back to normal mode again.
N STDOUT=newline Output newline character to STDOUT.

File related I/O

Instruction Format Explanation
r lstack[-,-,namebytes]• namebytes: the number of bytes to take from gstack to determine the name of the file to be read.

The file bytes are reinterpreted as UInt64 words (big-endian). If the byte count of the file does not add up to full 64-bit words, the end of the file is padded to the next full 64-bit word length with 8-length%8 zero bytes. The UInt8 stream is reinterpreted as UInt64 words and pushed on top of gstack, 64-bit word by 64-bit word.

Instruction Format Explanation
w lstack[-,filebytes,namebytes]• namebytes: number of bytes taken from gstack to determine the file name, filebytes: number of bytes (counting after namebytes) to take from gstack to determine the file content.

The 64 bit words are reinterpreted as groups of 8 bytes in big-endian order! UInt64[0x11000000000000ff] is reinterpreted as UInt8[0xff,0x00,0x00,0x00,0x00,0x00,0x00,0x11]•

Example beeswax programs

Cat program

 _,}

Hello world

 _`Hello, World!

Infinite output of '1's

 _P~P{J

Squaring an entered number, return the result to STDOUT

 _`Enter number:`TN{` squared=`~+.{


Output numbers from 1 to 100

 *3~5~(~4+~0>P{Kp
             b N<

Return n-th Fibonacci number

Clear version

                         #>'#{;
 _`enter n: `TN`Fib(`{`)=`X  ~P~K#{;    >@{;
                          #>~P~L#MM@>+@"dM@~p
                                    d       <

Compact version

           ;{#'<>~P~L#MM@>+@'p@{;
 _`n`TN`F(`{`)=`X~P~K#{; d~@M<

Proof of Turing completeness

By translating brainfuck instructions to beeswax.

Initialize the cells

Use the gstack to simulate the cells. For example, initialize gstack to hold 32768 cells:

   _8F(~4~(    lstack[8,4,32768]

append loop to create the gstack:

   >~0f~M'p
    b     <

resulting in the full construct:

   _8F(~4~(>~0f~M'p
            b     <

Then put translated brainfuck code after the p.

Translate brainfuck instructions to beeswax equivalents

< and > instructions

   <       1~0h    if used for multiple instances, every following < in this group of <’s is appended as beeswax instruction h
   >       1~0y    if used for multiple instances, every following > in this group of >’s is appended as beeswax instruction y

alternatively, for multiple instances:

   <       ✔~0h    with ✔ being the number of <’s
   >       ✔~0y    with ✔ being the number of >’s

The stack wraps around in both directions.

+ and - instructions

For 64 bit cell size

   +       g?Pf
   -       g?Mf

alternatively, for multiple instances:

   +       ✔~g?+f      ✔ being the number of +’s in the bf code
   -       ✔~g?-f      ✔ being the number of -’s in the bf code

For 8 bit cell size

If we want to emulate 8 bit cells, we prepare the cells like below:

   8F(~4~(>~0f~M'pz5~8(@
          d      <

In this case, the translated bf code is appended after the @.

Take the result after each + or - instruction %256 for 8 bit brainfuck emulation. In the examples below, 5~8( =256, which is equivalent to 8 shifted left 5 times.

This ensures that the value 256 is readily available for +/- instructions and does not have to be created from scratch everytime, which also shortens the beeswax program.

Single instance:

   +       @Fg?P%f
   -       @Fg?M%f

Multiple instances:

   +       ✔~g?+~@~%f~@      ✔ being the number of +’s in the bf code
   -       ✔~g?-~@~%f~@      ✔ being the number of -’s in the bf code

If we use the preparation routine from the beginning, we have to create the value 256 everytime we use the + or - instructions:

   +       5~8(~g?P%f
   -       5~8(~g?M%f

Alternatively, for multiple instances:

   +       5~8(@✔~g?+~@~%f   ✔ being the number of +’s in the bf code
   -       5~8(@✔~g?-~@~%f   ✔ being the number of -’s in the bf code

[ and ] instructions

Translate the loop instructions to actual beeswax loops, using its 2d capabilities ;)

              >
   [       >g"d                       bee enters at the leftmost >
           d


              p
   ]       g'p>                       bee enters at the g
             <

The examples have to be adjusted for the rank of the loop. The examples shown demonstrate the innermost loop, equivalent to a brainfuck structure like [ ], using only one pair of brackets. Outer brackets grow larger in beeswax.

A brainfuck construct like [[ ][ ]] would look like:

      >                        p
           >    p    >    p
   >g"d >g"d g'p> >g"d g'p> g'p>
        d      <  d      <
   d                          <

So, brainfuck loops become visibly loops in the beeswax translation.

. and , instructions

   .       C
   ,       ,?f

External Resources