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-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.
Language reference:
Get the interpreter here
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.
@ SHiNKiROU: Thanks, I didn't think of that as a test. Updated. – Hoa Long Tam – 2011-02-06T02:57:12.843
Related: Language w/ the smallest interpreter written in itself on Stack Overflow, though are are few (only one?) answers that actually abide by the rules given here.
– dmckee --- ex-moderator kitten – 2011-02-06T03:56:58.1131Do we have to rewrite that Scheme sexp parser, or can we consider the host language's ok? – J B – 2011-02-06T15:40:23.137
@J B: The language's string processing utilities are fine, including the
sexpparser. – Hoa Long Tam – 2011-02-06T20:22:41.493@HoaLongTam For my- oh, I mean, everyone's sake can you clarify whether a valid answer must use a Turing-complete language or not?
– user8397947 – 2016-06-14T01:13:51.583See DBFI. The page declares that it is "the shortest known Brainfuck self-interpreter and possibly the shortest self-interpreter amongst all imperative languages".
– Joey Adams – 2011-04-12T01:12:10.147This could end up being very short if you assume the existence of something similar to
evalbut not quite the same, for example a function that reads in a string and converts it to program code. – Michael Dickens – 2011-04-23T18:42:29.530@Michael Dickens: I think that's what my CI answer does. I reluctantly omitted an operator that takes a character and converts it to its corresponding code fragment, but I did add support for defining and joining code fragments. – Joey Adams – 2011-04-23T22:16:21.603
1(Hmm.. I should do something with
/usr/bin/cat) what about Turing-completeness? – Ming-Tang – 2011-02-06T02:36:27.277