Self-Interpreting Interpreter

Binary Lambda Calculus, 232 bits (29 bytes)

0101000110100000000101011000000000011110000101111110011110000101110011110000001111000010110110111001111100001111100001011110100111010010110011100001101100001011111000011111000011100110111101111100111101110110000110010001101000011010

See http://en.wikipedia.org/wiki/Binary_lambda_calculus#Lambda_encoding for details

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). 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.

---

Language reference:

Get the interpreter here

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.

I can't take credit for this one, but I thought I would share this amazing one:

Brainf*** (423)

>>>+[[-]>>[-]++>+>+++++++[<++++>>++<-]++>>+>+>+++++[>++>++++++<<-]+>>>,<++[[>[
->>]<[>>]<<-]<[<]<+>>[>]>[<+>-[[<+>-]>]<[[[-]<]++<-[<+++++++++>[<->-]>>]>>]]<<
]<]<[[<]>[[>]>>[>>]+[<<]<[<]<+>>-]>[>]+[->>]<<<<[[<<]<[<]+<<[+>+<<-[>-->+<<-[>
+<[>>+<<-]]]>[<+>-]<]++>>-->[>]>>[>>]]<<[>>+<[[<]<]>[[<<]<[<]+[-<+>>-[<<+>++>-
[<->[<<+>>-]]]<[>+<-]>]>[>]>]>[>>]>>]<<[>>+>>+>>]<<[->>>>>>>>]<<[>.>>>>>>>]<<[
>->>>>>]<<[>,>>>]<<[>+>]<<[+<<]<]