[Question]
  [
Based on a comment by George Edison to [this question](https://codegolf.stackexchange.com/questions/471/self-compiling-compiler), write the smallest self-interpreting interpreter.
* You may use the language of your choosing.
* Empty languages do not count. Your program must be at least two characters long.
* The program does not need to interpret the *entire* language, just a Turing-complete subset of language features (that contains the interpreter).
* Quines don't count.
* Do not use your language's built-in `eval` function or equivalent. Same goes for `apply`, etc.
  
[Answer]
# Binary Lambda Calculus, 232 *bits* (29 bytes)
`0101000110100000000101011000000000011110000101111110011110000101110011110000001111000010110110111001111100001111100001011110100111010010110011100001101100001011111000011111000011100110111101111100111101110110000110010001101000011010`
See
 <http://en.wikipedia.org/wiki/Binary_lambda_calculus#Lambda_encoding>
for details
[Answer]
## CI - 260
```
,(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](https://gist.github.com/938595)). 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](https://gist.github.com/938595#file_stack.ci) 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.
---
## Language reference:
*[Get the interpreter here](https://gist.github.com/938595)*
### Blocks
* `(` ... `)`
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)
```
### Stack manipulation
* 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
```
### Relational operators
* 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+ .
```
### I/O
* 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.
### Integer literals
* `'c`
Push the character c.
* *[0-9]+*
Push a decimal integer.
### Arithmetic
* a b `+`
* a b `-`
* 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.
### Miscellaneous
* 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.
[Answer]
[I can't take credit for this one](http://www.hevanet.com/cristofd/brainfuck/dbfi.b), but I thought I would share this amazing one:
## Brainf\*\*\* (423)
```
>>>+[[-]>>[-]++>+>+++++++[<++++>>++<-]++>>+>+>+++++[>++>++++++<<-]+>>>,<++[[>[
->>]<[>>]<<-]<[<]<+>>[>]>[<+>-[[<+>-]>]<[[[-]<]++<-[<+++++++++>[<->-]>>]>>]]<<
]<]<[[<]>[[>]>>[>>]+[<<]<[<]<+>>-]>[>]+[->>]<<<<[[<<]<[<]+<<[+>+<<-[>-->+<<-[>
+<[>>+<<-]]]>[<+>-]<]++>>-->[>]>>[>>]]<<[>>+<[[<]<]>[[<<]<[<]+[-<+>>-[<<+>++>-
[<->[<<+>>-]]]<[>+<-]>]>[>]>]>[>>]>>]<<[>>+>>+>>]<<[->>>>>>>>]<<[>.>>>>>>>]<<[
>->>>>>]<<[>,>>>]<<[>+>]<<[+<<]<]
```
[Answer]
## BlockScript - 535
```
{[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](http://en.wikipedia.org/wiki/Spaghetti_stack)-based language I created specifically for this challenge. The base interpreter is [blockscript.c](https://gist.github.com/917067) .
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](http://en.wikipedia.org/wiki/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.
---
## Language reference:
*[Get the interpreter here](https://gist.github.com/917067)*
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.
### Value selection
* `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).
### Blocks
* `{` ... `}`
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.
### Stack references
* `&`
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.
### Conditional expression
* `?` *<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>*.
### I/O
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.
### Integer/character literals
Note: Integers and characters are the same thing in BlockScript.
* `'c`
Push the character c.
* *[0-9]+*
Push a decimal integer.
### Arithmetic
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).
### Relational operators
These operators only work on integer values.
* `<` If `b` is less than `a`, push 1, else push 0.
* `>`
* `=`
### Miscellaneous
* `#` Comment to end of line
* The program must end with `;`
* All other characters are ignored.
[Answer]
# [Zozotez LISP](http://sylwester.no/zozotez/): 414
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](http://en.wikipedia.org/wiki/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)))
```
[Answer]
# [GORBITSA](https://esolangs.org/wiki/GORBITSA), 493 bytes
```
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.
# Explained
(Full pseudocode I translated this to AFTER I wrote this (yeah, I wrote this with no extra utilities) can be found [here](https://repl.it/@ZippyMagician/gAssembler#new/self_interpreter)).
## Header:
```
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.
## Letters:
```
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
## 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.
## Subtraction
```
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).
## Letter Evaluation
```
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.
[Answer]
# Concurrent Filesystem Befunge 98 - 53\18 bytes (almost certainly cheating)
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
><
```
[Answer]
# [CHIQRSX9+](https://esolangs.org/wiki/CHIQRSX9%2B) , 2 bytes
```
+I
```
There's no way to write a self-interpreting interpreter in this [HQ9+](https://esolangs.org/wiki/HQ9%2B)-based language without using `I`, which runs a built-in interpreter that processes STDIN.
]