Based on a comment by George Edison to this question, write the smallest self-interpreting interpreter.
eval function or equivalent. Same goes for apply, etc.0101000110100000000101011000000000011110000101111110011110000101110011110000001111000010110110111001111100001111100001011110100111010010110011100001101100001011111000011111000011100110111101111100111101110110000110010001101000011010
See http://en.wikipedia.org/wiki/Binary_lambda_calculus#Lambda_encoding for details
,(1p0(2d())(41(2d())('#((1p0()(10()(1d,1p$)=)<)$2d,1p$)(40(1d,1c$^)(''(1d,^)('0
'9('0-(,'0'9('0-2p10*+1p$)(!1d)~)$^)(0($)'$(^)'^(&)'&(c)'c(p)'p(d)'d(=)'=(<)'<(
>)'>(~)'~(.)'.(,)',(!)'!(+)'+(-)'-(*)'*(/)'/(%)'%()38p(1p3p0(3d)((2)(3)=p1d1p$)
=)$)~)=)=,2p$&)=)=)<)$$
320 → 260: Push simple character-to-instruction mappings, then fold over them. This halves the code size per case (there are 18 cases), but costs 30 characters to do the folding.
This is another one of my constructed languages, (base interpreter hosted on Gist). It's unique in that the language reifies code fragments. That is, strings of instructions in this stack-based language are used to the same effect as data structures or closures in other languages:
1^ # Push a 1, and "lift" it to be a code literal.
(5 +) # Define a code literal.
& # Join the two code literals, forming (1 5 +)
$ # Execute the code literal.
The interpreter builds a code fragment of the entire program before running it, so it can also be considered a compiler. Because of this, stacking the interpreter does not result in exponential run-time overhead.
The interpreter derives all of its operators directly from the host interpreter. However, it does the parsing by itself, so the majority of the code is just sequences that translate characters into their respective code literals. This isn't the same as using eval, but it reveals how dependent any programming language implementation is on the semantics of its host language/architecture.
( ... )
Create a "block", which is effectively a list of instructions with no context. Internally, it could even be machine code.
block $
Call a block. The callee is handed the global stack, which includes the block being called.
value ^
Lift a value. Namely, turn it into a block that pushes that value.
Example:
1 ^
== (1)
block1 block2 &
Join two blocks, forming one that runs both in sequence.
Example:
(1) (2) &
== (1 2)
n c
Copy the nth value of the stack.
Example:
5 4 3 2 1 0 3c
== 5 4 3 2 1 0 3
n p
Pluck the nth value of the stack (remove it, and bring it to front).
Example:
5 4 3 2 1 0 3p
== 5 4 2 1 0 3
n d
Drop n values from the stack. 0d is a no-op.
Example:
5 4 3 2 1 0 3d
== 5 4 3
a b (on_true) (on_false) =
Test if a equals b. Consume all but the first argument, and call on_true or on_false. If one argument is zero and the other is any other type, the result will be false. Otherwise, a and b must be integers.
Example:
3 3 ('0+ .) (1d) =
== 3 '0+ .
a b (on_true) (on_false) <
Test if a is less than b. a and b must be integers.
Example:
3 5 (1d 5) () <
== 3 1d 5
== 5
a b (on_true) (on_false) >
Test if a is greater than b. a and b must be integers.
Example:
3 5 (1d 5) () >
== 3
a lo hi (on_true) (on_false) ~
Test if lo <= a <= hi. a, lo, and hi must be integers.
Example:
3 0 10 ('0+ .) (1d) ~
== 3 '0+ .
c .
Put the character c (consuming it from the stack).
,
Get a character and push it to the stack. If the end of file has been reached, -1 is pushed.
c !
Unget a character. Just like ungetc in C, only one pushback is allowed.
'c
Push the character c.
[0-9]+
Push a decimal integer.
+-a b *
Add/subtract/multiply two numbers.
Example:
3 5 + 7 3 + *
== 80
a b /
a b %
Division and modulus. Unlike in C, these round toward negative infinity.
code # comment
The # character comments out everything to the end of the line.
)
Used to end blocks. Can be used to end the whole program, too.
All other characters are ignored.
I can't take credit for this one, but I thought I would share this amazing one:
>>>+[[-]>>[-]++>+>+++++++[<++++>>++<-]++>>+>+>+++++[>++>++++++<<-]+>>>,<++[[>[
->>]<[>>]<<-]<[<]<+>>[>]>[<+>-[[<+>-]>]<[[[-]<]++<-[<+++++++++>[<->-]>>]>>]]<<
]<]<[[<]>[[>]>>[>>]+[<<]<[<]<+>>-]>[>]+[->>]<<<<[[<<]<[<]+<<[+>+<<-[>-->+<<-[>
+<[>>+<<-]]]>[<+>-]<]++>>-->[>]>>[>>]]<<[>>+<[[<]<]>[[<<]<[<]+[-<+>>-[<<+>++>-
[<->[<<+>>-]]]<[>+<-]>]>[>]>]>[>>]>>]<<[>>+>>+>>]<<[->>>>>>>>]<<[>.>>>>>>>]<<[
>->>>>>]<<[>,>>>]<<[>+>]<<[+<<]<]
{[B':=?0:B';=?0:B'}=?0:B'{=?,A!,A!d1c&:B'?=?,A!,A!2e&:B''=?,,A!d3c&:B{[B'0<?0:B
'9>?0:1}!?B'0-{[,g!?c'0-B10*d+A!:Bd]A!d3c&}!:B'#=?{[,10=?,]A!:A!}!:,A!Bb&}{[AC[
B]DB?[AB{[Bh&hbhn!}{[B[AB]C?1-eA!:b}&[C1=?E[C]FHc&B!:C2=?{G?D:E[C}!FHcI!:C3=?E[
C]B!:C'!=?G[ABC]Hc&dbh&D?b@I!B!:b@I!:C'&=?HB!:C'@=?FGDI!:C'[=?GF&HDI!:C']=?F[A]
HDI!:C',=?,B!:C'.=?G.FHDI!:C'a'z{[DC<?0:DB>?0:1}!?Ce-HA!B!:C'A'Ze!?F[B]Cg-dA!B!
:{C'+=?{[CB+}:C'-=?{[CB-}:C'*=?{[CB*}:C'/=?{[CB/}:C'%=?{[CB%}:C'<=?{[CB<}:C'>=?
{[CB>}:C'==?{[CB=}:0}!?H[A][B]Ge!B!:FHDI!:c},c!0ac&0&0&0bho!;
BlockScript is a trivial spaghetti stack-based language I created specifically for this challenge. The base interpreter is blockscript.c .
Sample program (prints the first 15 Fibonacci numbers):
{[B?B10/A!B10%d&:0}
{[B0<?'-.0B-A!:{B?Bh!{[B?B[A]A!B[B]'0+.:}!:'0.}!10.}
{[B?Dd!DC+B1-CecA!:}
0 1 15d!
;
The interpreter reads both source code and program input from standard input, in that order. This means that to run an interpreter within an interpreter within an interpreter, simply copy and paste:
# Level 1
{[B':=?0:B';=?0:B'}=?0:B'{=?,A!,A!d1c&:B'?=?,A!,A!2e&:B''=?,,A!d3c&:B{[B'0<?0:B
'9>?0:1}!?B'0-{[,g!?c'0-B10*d+A!:Bd]A!d3c&}!:B'#=?{[,10=?,]A!:A!}!:,A!Bb&}{[AC[
B]DB?[AB{[Bh&hbhn!}{[B[AB]C?1-eA!:b}&[C1=?E[C]FHc&B!:C2=?{G?D:E[C}!FHcI!:C3=?E[
C]B!:C'!=?G[ABC]Hc&dbh&D?b@I!B!:b@I!:C'&=?HB!:C'@=?FGDI!:C'[=?GF&HDI!:C']=?F[A]
HDI!:C',=?,B!:C'.=?G.FHDI!:C'a'z{[DC<?0:DB>?0:1}!?Ce-HA!B!:C'A'Ze!?F[B]Cg-dA!B!
:{C'+=?{[CB+}:C'-=?{[CB-}:C'*=?{[CB*}:C'/=?{[CB/}:C'%=?{[CB%}:C'<=?{[CB<}:C'>=?
{[CB>}:C'==?{[CB=}:0}!?H[A][B]Ge!B!:FHDI!:c},c!0ac&0&0&0bho!;
# Level 2
{[B':=?0:B';=?0:B'}=?0:B'{=?,A!,A!d1c&:B'?=?,A!,A!2e&:B''=?,,A!d3c&:B{[B'0<?0:B
'9>?0:1}!?B'0-{[,g!?c'0-B10*d+A!:Bd]A!d3c&}!:B'#=?{[,10=?,]A!:A!}!:,A!Bb&}{[AC[
B]DB?[AB{[Bh&hbhn!}{[B[AB]C?1-eA!:b}&[C1=?E[C]FHc&B!:C2=?{G?D:E[C}!FHcI!:C3=?E[
C]B!:C'!=?G[ABC]Hc&dbh&D?b@I!B!:b@I!:C'&=?HB!:C'@=?FGDI!:C'[=?GF&HDI!:C']=?F[A]
HDI!:C',=?,B!:C'.=?G.FHDI!:C'a'z{[DC<?0:DB>?0:1}!?Ce-HA!B!:C'A'Ze!?F[B]Cg-dA!B!
:{C'+=?{[CB+}:C'-=?{[CB-}:C'*=?{[CB*}:C'/=?{[CB/}:C'%=?{[CB%}:C'<=?{[CB<}:C'>=?
{[CB>}:C'==?{[CB=}:0}!?H[A][B]Ge!B!:FHDI!:c},c!0ac&0&0&0bho!;
# Level 3
{[B?B10/A!B10%d&:0}
{[B0<?'-.0B-A!:{B?Bh!{[B?B[A]A!B[B]'0+.:}!:'0.}!10.}
{[B?Dd!DC+B1-CecA!:}
0 1 15d!
;
Like the movie Inception, you pretty much can't go any deeper than three levels. It's not a matter of time, but space. BlockScript leaks memory profusely, and this has to do with how the language itself is designed.
In BlockScript, the "stack" is not an array that is overwritten by subsequent operations like you may be used to. It is actually implemented as an immutable linked list, and a stack persists for the duration of the program. Also, no operator (except @) removes values from the stack. However, stack modifications only affect the block in which they occur.
a through z
Fetch the 0-25th item from the stack, and push it to the stack. a refers to the head, or most recently pushed item, of the stack.
A through Z
Fetch the 0-25th item of the current frame, and push it to the stack.
[
Open a "frame" to select items from the stack reference (see below) on the head of the stack. [ doesn't require a matching ], but frames are lexically scoped. In BlockScript, "scope" is determined by braces ({ ... }) that form blocks. Thus, opening a frame inside of a block will have no effect on code outside of the block.
]
Close the current frame, returning to the previous frame (if any).
{ ... }
Create a "block", and push it to the stack. Inside a block, the stack will start at what it was before the block, except the stack of the caller will be pushed on top. Stacks are persistent and immutable in BlockScript, so blocks are closures. The idiom {[ means open a block, then open a frame to start selecting arguments (using A through Z). The return value of a block is the head of the stack when } is reached.
Example:
'3 '2 '1 {[ b. d. f. B. C. D. A! } 'D 'C 'B d!;
This prints 123BCD123DCB123BCD123DCB… . The lowercase letters refer to stack values, while the uppercase letters refer to arguments (because the frame is set to the stack of the caller). A! takes the head of the caller (which is guaranteed to be the block being called) and calls it. If you're wondering why it reverses BCD every other time, it's because B. C. D. pushes those arguments in reverse order right before the block calls itself.
!
Call a block. Push the return value to the stack.
&
Create a stack reference, and push it to the stack. Think of this as "super-cons", as it effectively takes every item on the stack and forms a "tuple" out of it. The idiom &[ means that whatever a, b, c referred to before can now be accessed with A, B, C (for the remainder of the block or until ] is encountered).
In part because & captures more values than it usually needs, BlockScript leaks memory by design.
@
Switch to the stack pointed to by the stack reference a. This operator is rather weird, but the BlockScript self-interpreter uses it a couple times to avoid having to push the same arguments twice. The effects of @ (or any stack operation, for that matter) are confined to the block in which it is invoked. Also, the frame is unaffected by @, so the frame can be used to grab values you need after switching stacks.
? <on true> : <on false>
Conditional expression, just like the ternary operator in C. That is, if a is "true" (that is, not equal to the integer zero), then do <on true>, otherwise do <on false>.
Note: Input and output are done in UTF-8. A "character" is an integer corresponding to a Unicode index.
,
Get the next character of input, and push it to the stack. If the end of input is reached, push -1 instead.
.
Output the character on the head of the stack.
Note: Integers and characters are the same thing in BlockScript.
'c
Push the character c.
[0-9]+
Push a decimal integer.
These operators only work on integer values.
+ Compute b + a (pushing the result, but not discarding either value).- Compute b - a.* Compute b * a./ Compute b / a (integer division; rounds toward negative infinity).% Compute b % a (integer modulus; rounds toward negative infinity).These operators only work on integer values.
< If b is less than a, push 1, else push 0.>=# Comment to end of line;linefeeds added to get a nice block is not needed and not counted.
((\(E V A L)(E(r)'(())))(\(x e)(?(s x)(V x e)((\(b j)(?(= b ")(a j)(?(= b \)x
(?(= b ?)(?(E(a j)e)(E(a(d j))e)(E(a(d(d j)))e))(?(s b)(A b(E(a j)e)(E(a(d j)
)e))(E(a(d(d b)))(L(a(d b))j e)))))))(E(a x)e)(d x))))(\(x g)(? g(?(= x(a(a
g)))(d(a g))(V x(d g)))x))(\(f h v)(?(= f r)(r)(?(= f p)(p h)(?(= f s)(s h)(?
(= f a)(a h)(?(= f d)(d h)(?(= f =)(= h v)(c h v))))))))(\(k v i)(? k(L(d k)(
d v)(c(c(a k)(E(a v)i))i))i)))
In theory it should be able to run itself, but since the original interpreter is a BrainFuck binary and itself an interpreter I have only been able to test each part. When given itself and a simple expression (p p) I think it needs more time than the 40 minutes I have waited so far and I'm using my fast jitbf to run it which (mis)uses Perl Inline-C to run C code on the fly.
It's impossible to implement the whole Zozotez in Zozotez since it does not have means of mutating cons and : (setq/define) need that to update bindings. I also didn't implement explicit begin/progn or &rest argument, macros and special printing arguments since I didn't use it in the interpreter. I did include p (print) even though I don't use it so programs need to explicit print their calculations just like the original interpreter.
The same ungolfed:
;; A stand alone Zozotez script need to be
;; contained in one expression, here with
;; all functions provided as arguments to
;; get them bound in the dynamic environment
((\ (E V A L)
(E(r)'(())))
;; E (EVAL)
(\ (x e)
(? (s x)
(V x e)
((\ (b j)
(? (= b ") (a j)
(? (= b \) x
(? (= b ?) (? (E(a j)e) (E(a(d j))e) (E(a(d(d j)))e))
(? (s b)
(A b (E(a j)e) (E (a(d j))e))
(E (a(d(d b))) (L(a(d b))j e)))))))
(E (a x) e)(d x))))
;; V (VALUE / symbol->value)
(\ (x g)
(? g
(? (= x (a (a g)))
(d (a g))
(V x (d g)))
x))
;; A (APPLY) but just for primitives
(\ (f h v)
(? (= f r) (r)
(? (= f p) (p h)
(? (= f s) (s h)
(? (= f a) (a h)
(? (= f d) (d h)
(? (= f =)
(= h v)
(c h v))))))))
;; L ( joint evLis / extend-env)
(\ (k v i)
(? k
(L (d k)
(d v)
(c (c (a k)
(E (a v) i))
i))
i)))
S255 O253 R I188 B12 I68 o252 S1 O250 i252 S0 B2 S71 O255 S18 O254 S0 B134 B143 S79 O255 S25 O254 S0 B134 B149 S82 O255 S32 O254 S0 B134 B155 S66 O255 S39 O254 S0 B134 B158 S73 O255 S46 O254 S0 B134 B168 S84 O255 S53 O254 S0 B134 B172 S83 O255 S60 O254 S0 B134 B175 S65 O255 S67 O254 S0 B134 B179 S103 O255 S74 O254 S0 B134 B185 S111 O255 S81 O254 S0 B134 B193 S114 O255 S88 O254 S0 B134 B201 S98 O255 S95 O254 S0 B134 B207 S105 O255 S102 O254 S0 B134 B219 S116 O255 S109 O254 S0 B134 B224 S115 O255 S116 O254 S0 B134 B230 S97 O255 S123 O254 S0 B134 B239 G251 s253 I1 A252 B255 S2 i251 i250 S0 B12 g251 s253 I1 A255 b254 S1 i254 S0 b254 g250 O248 g248 O249 S0 B124 g250 O248 G249 o248 S0 B124 r249 S0 B124 G249 B162 S0 B124 g250 O251 I1 O250 S0 B12 g250 i249 S0 B124 t249 S0 B124 g250 O249 S0 B124 g250 O248 g248 i249 S0 B124 g250 O248 g248 O248 g248 O249 S0 B124 g250 O248 g248 O248 G249 o248 S0 B124 g250 O248 R o248 S0 B124 G249 B211 S0 B124 g250 O248 g248 O251 I1 O250 S0 B12 g250 A249 o250 S0 B124 g250 O248 g248 T S0 B124 g250 O248 g248 O248 G249 s248 O249 S0 B124 g250 O248 g248 O248 G249 a248 O249 S0 B124
Since GORBITSA is kind of strange, I will specify that this runs in ROM mode, while the code it interprets is in RAM mode. Explaining this is kind of weird, but I'll do my best. The 256 command limit on ROM mode killed me for a while.
(Full pseudocode I translated this to AFTER I wrote this (yeah, I wrote this with no extra utilities) can be found here).
S255 O253 R I188 B12 I68 o252 S1 O250 i252 S0 B2
Essentially, this part takes the input. It reads STDIN and stores it in the next free spot in memory (starting at 0). If the input is char code 68 ("D"), it will branch to the letter parsing script. Otherwise, it branches back to the beginning of the header and takes another bit of STDIN.
S71 O255 S18 O254 S0 B134 B143
S79 O255 S25 O254 S0 B134 B149
S82 O255 S32 O254 S0 B134 B155
S66 O255 S39 O254 S0 B134 B158
S73 O255 S46 O254 S0 B134 B168
S84 O255 S53 O254 S0 B134 B172
S83 O255 S60 O254 S0 B134 B175
S65 O255 S67 O254 S0 B134 B179
S103 O255 S74 O254 S0 B134 B185
S111 O255 S81 O254 S0 B134 B193
S114 O255 S88 O254 S0 B134 B201
S98 O255 S95 O254 S0 B134 B207
S105 O255 S102 O254 S0 B134 B219
S116 O255 S109 O254 S0 B134 B224
S115 O255 S116 O254 S0 B134 B230
This section is rather self-explanatory. For each letter, you increment by an amount and then branch to subtraction. If it is 0 (i.e. the current letter is whatever the line is checking) it will then branch to the letter's parsing. Otherwise, it jumps to the next letter. When all letters are done being checked, it jumps to Potential Exit
S97 O255 S123 O254 S0 B134 B239 G251 s253 I1 A252 B255 S2 i251 i250 S0 B12
This section checks to see if there are no letters left to execute. If there are, it increments the pointers so they reference the next character + its argument, and then jump to the beginning of Letters. Otherwise, it terminates by branching to a null instruction.
g251 s253 I1 A255 b254 S1 i254 S0 b254
Very simple. Uses XOR subtraction to check if the current character is equal to a character stored in another part of memory (set by the letters section).
g250 O248 g248 O249 S0 B124
g250 O248 G249 o248 S0 B124
r249 S0 B124 G249 B162 S0 B124
g250 O251 I1 O250 S0 B12 g250 i249 S0 B124 t249 S0 B124
g250 O249 S0 B124
g250 O248 g248 i249 S0 B124
g250 O248 g248 O248 g248 O249 S0 B124
g250 O248 g248 O248 G249 o248 S0 B124
g250 O248 R o248 S0 B124 G249 B211 S0 B124
g250 O248 g248 O251 I1 O250 S0 B12 g250 A249 o250 S0 B124
g250 O248 g248 T S0 B124
g250 O248 g248 O248 G249 s248 O249 S0 B124
g250 O248 g248 O248 G249 a248 O249 S0 B124
Each line corresponds to the same line in the Letters section. These simply interpret each character (G O R B I T S A g o r b i t s a) in descending order and then branch to Potential Exit.
Full 53 byte interpreter with no restrictions (although I haven't tested complicated timing interactions involving IP splitting and wrapping):
v ;;;;;;;;
>]390'ai@
t;;;;;;;;
;>zzzzz#;
Reads input from a file named a and executes it. It isn't specifed in the rules that we can't use self-modifying code.
18 byte interpreter that does not allow wrapping (the IP moving of one edge of the code and starting at the opposite edge):
]210'ai@
t
><
+I
There's no way to write a self-interpreting interpreter in this HQ9+-based language without using I, which runs a built-in interpreter that processes STDIN.
eval, which is for expressions, not programs.
\$\endgroup\$
Commented
Jun 7, 2016 at 16:45
X is supposed to make the language Turing-complete (thus able to compute primes) in an implementation-dependent manner.
\$\endgroup\$
Commented
Jun 13, 2016 at 19:50
X command randomly perturbs the program and the executes it, meaning that one cannot use than command to deterministically compute primes. Can you give me of an example interpreter that lets you use X in the way you specified?
\$\endgroup\$
Commented
Jun 13, 2016 at 20:03
/usr/bin/cat) what about Turing-completeness? \$\endgroup\$