Pyke, 5 characters
0h.CE
This is capable of producing an infinitely large number, turning it into a string and then evaluating it as Pyke code.
Explanation of the code:
0 - Add 0 to the stack. This is required to start a number
h - Increment the number before. By repeating this an arbitrary amount of times, you can create numbers that are infinitely big. Pyke supports bignums as it is written in Python, which uses them as a default.
.C - Turn a number into a string using the following algorithm: (Github link)
def to_string(num):
string = ""
while num > 256:
num, new = divmod(num, 256)
string = chr(new) + string
string = chr(num) + string
return string
By this point, we can create an arbitrary amount of strings and natural numbers in Pyke with arbitrary values. Numbers can be created in the form corresponding to the regex 0(h)* and strings can be created with 0(h)*.C. They can be interweaved with each other to create an arbitrary mixture of strings and integers.
E - evaluate a string as Pyke code. This uses the same environment as the Pyke code already running so will share things like the input.
Attempted proof that Pyke is Turing Complete.
One of the simplest ways of showing a language is turing complete is by implementing Brainf*ck in it. This is probably much harder in Pyke than many other languages because it's list and dictionary operations are pretty much non-existent due to the lack of needing them in the area Pyke is designed to run in: code-golf.
Firstly we create an interpreter for brainf*ck and encode it using our algorithm above to create a number and then express that number with 0 and h. We then create the string containing the code to be ran in exactly the same way. If we were to leave it at that, we would have the stack as
string containing brainf*ck code
string containing brainf*ck interpreter
This means the code has to be in the opposite form as the Pyke stack is first in last out.
Now for the fun part: the brainf*ck interpreter with a whopping 216 bytes!
Q~B"><ht.,".:=B;Z]1=L;W~Bo@D=c"ht"{I~c~LZ@EZ]1~LR3:=L)~c\,qIz.oZ]1~LR3:=L)~c\[email protected])~c"<>"{I~c"<>""th".:ZE=ZZ1_qI0=Z~L0"":0]10:=L)Z~LlqI~L~Ll"":1_]10:=L))~c\[qI~LZ@0qI\]~B~o>@~o+h=o))~c\]qI~o\[~B~o<_@-t=o)~o~BlN
Try it here!
If you want to try the code in semi-completed but editable form, try it here!
To convert from a string into a number, you can use the following Python code:
def conv(string, t=0):
t *= 256
t += ord(string[0])
if len(string) != 1:
return conv(string[1:], t)
return t
The (almost) final solution can be tried here!
Explanation of Brainf*ck interpreter
First lets separate the program into parts:
Q~B"><ht.,".:=B;Z]1=L; - The initialisation part
Q~B"><ht.,".: - input.replace("><+-.,[]", "><ht.,")
- replace the characters in brainf*ck with some modified ones.
- this means we can `eval` the add and subtract bits easily.
=B; - set `B` to this.
- The `B` variable contains the instructions
Z]1=L; - set `L` to [0]
- `L` contains the stack, initialised with 0
W~Bo@D=c !code! ~o~BlN - The main loop
W - do
~Bo@D=c - c=B[o++]
- the c variable is used to store the current character.
~o~BlN - while
~o - o
N - ^ != V
~Bl - len(B)
- this stops the program running once it's finished.
- The instructions
- Increment/Decrement:
+-
"ht"{I~c~LZ@EZ]1~LR3:=L) - The bit that does incrementing and decrementing
"ht"{I ) - if c in "ht"
~LZ@ - L[Z]
- `Z` contains the current stack pointer
~c E - eval current character with ^ as an argument
- returns the contents of `Z` either incremented or decremented
Z]1~LR3:=L - L[Z] = ^
~c\,qIz.oZ]1~LR3:=L) - The code for output
~c\,qI ) - if character == ",":
z.o - ord(input)
Z]1~LR3:=L - L[Z] = ^
~c\[email protected]) - The code for input
~c\.qI ) - if c == ".":
~LZ@ - L[Z]
.C - chr(^)
pK - print(^)
- Shift Left/Right:
<>:
~c"<>"{I~c"<>""th".:ZE=Z - main part
~c"<>"{I - if "<>" in c:
~c"<>""th".: - c.replace("<>", "th")
ZE=Z - Z = eval(char, Z)
Z1_qI0=Z~L0"":0]10:=L) - lower bound check
Z1_qI ) - if Z == -1:
0=Z - Z = 0
~L0"": - L.insert("", 0)
0]10:=L - L[0] = 0
Z~LlqI~L~Ll"":1_]10:=L) - upper bound check
Z~LlqI ) - if Z == len(L):
~Ll"": - L.insert("", len(L))
~L 1_]10:=L - L[-1] = 0
- The conditionals:
[:
~c\[qI~LZ@0qI\]~B~o>@~o+h=o)) - Code for `[`
~c\[qI ) - if c == "[":
~LZ@0qI ) - if L[Z] == 0:
~B~o> - B[o:]
\] @ - ^.find("]")
~o+h=o - o = o + ^ + 1
- And ]:
~c\]qI~o\[~B~o<_@-t=o) - Code for `]`
~c\]qI ) - if c == "]":
~B~o<_ - reversed(B[:o])
\[ @ - ^.find("[")
~o -t=o - o = o - ^ -1
