40
\$\begingroup\$

Please note: By its nature, the spec for this challenge is difficult to understand. It probably requires at least a freshman course in computability theory, or equivalent background reading. In addition, the challenge itself is rather hard. Answering it will require writing an entire interpreter for some subset of your language of choice, and not only that but the interpreter will have to be in the form of a something like a quine. If your answer isn't doing all of this, it is almost certain not to meet the spec.

You don't need to solve the halting problem (even partially) in order to solve this challenge. However, you almost certainly do need to write an interpreter (of the language you are using, written in the same language it interprets), though it need not be feature complete. It's this that makes this an interesting challenge.

I promised to award a 500 point bounty to the first answer that meets the spec, and this will be awarded to Jo King's BF answer.

The challenge

A rough, simplified version of Alan Turing's proof of the unsolvability of the halting problem goes something like this:

Suppose I've written a program F that's meant to solve the halting program. That is, F takes the source code of another program as input, and F(G) is supposed to return 1 if G halts, and 0 otherwise.

But if I give you my program F then you can construct another program, H, that runs my program with H as its input. If F(H) returns 0 then H returns 0, but otherwise it deliberately goes into an infinite loop. This leads to a paradox, and we have to conclude that F can't solve the halting problem after all.

Your task is to write the program H, but with a twist: I'm not going to give you my program. Instead, your program will receive my program's source code as an input. That is:

  • Your program will receive my program as an input, in source code form. (E.g. as a file or as command line input, the details are up to you.)

  • My program will be written in the same language as your program, and also takes input in the form of a source code string.

  • If my program returns 0 when given your program as input, your program should halt (and return 0) when given my program as input. (The exact meaning of "returing 0" is up to you.)

  • if my program doesn't halt, or if it returns anything other than 0 when given your program as input, your program should keep running indefinitely.

The twist is that, just to make it really quite a lot harder, you have to obey the following rules:

  1. You can't use any kind of built-in exec or eval-type function.

  2. You can't use any "cheating" methods to get at your own program's source code. (E.g. you can't say "save this in a file called 'program'" and then have open(program) in your program.)

This means that your program has to be some kind of crazy super-quine that can not only reproduce its own source code in the form of a string, but is also capable of correctly parsing and interpreting the language it's written in.

To make it slightly less insanely hard, you're allowed to use just a (Turing-complete) subset of your chosen language. So if your program is written in Python and will only work if my program only contains ifs and while loops and basic string operations, then that's OK as long as your program only uses those things too. (This means that you don't have to worry about implementing your chosen language's entire standard library!) However, your program does have to actually run - you can't just make up your own language.

This is , so the answer with the most votes wins. However, as mentioned above, it's a serious challenge just to meet the spec at all, so I will award a 500 point bounty to the first answer that does so according to my judgement.

please note: no doubt there are many ways you can "cheat" at this challenge, given the exact wording I've used. However, I'm really hoping for answers that enter into the spirit of the question. The challenge as intended is very difficult but possible, and I'm really hoping to see genuine solutions to it. I won't award the bounty to an answer that feels cheaty in my judgement.


Note: this challenge was originally posted as , but it was closed in 2016 due to not having an "objective winning criterion", and I changed it to in order to get it reopened. However, I've found that, as of January 2018, s are not in fact banned on PPCG (with this being the most recent meta discussion) so closing it in the first place was against site policy. I understand that popcons are not popular these days, but this is an old challenge, and its nature makes it really unsuitable for the scoring system. If anyone still feels strongly that it shouldn't be allowed then let's have a meta discussion before close votes start getting thrown around. Finally, on the off-chance that someone's spent the last year attempting to golf their solution, rest assured that it will be just as competitive in this challenge, and just as worthy of the bounty, as it would have been in the version.

\$\endgroup\$
17
  • 1
    \$\begingroup\$ By returning, do you mean exit code or stdout? Or are both acceptable? \$\endgroup\$ Commented May 4, 2014 at 21:04
  • \$\begingroup\$ Both are acceptable. \$\endgroup\$
    – N. Virgo
    Commented May 5, 2014 at 0:52
  • \$\begingroup\$ @Nathaniel I take it it would be illegal to export the received code for F into a file and importing it? ;3 \$\endgroup\$
    – cjfaure
    Commented May 5, 2014 at 10:27
  • 1
    \$\begingroup\$ I like this question a lot but it is hard to understand. If anyone else is having trouble, these two slides (in Java psuedocode) made it much easier for me to understand: imgur.com/a/NRmyO \$\endgroup\$
    – habs
    Commented Jan 13, 2016 at 2:46
  • 1
    \$\begingroup\$ You mention the "spirit of the question" and "genuine solutions". What do you mean by that? Are we supposed to write an interpreter for our language ourselves? I can't imagine another way to do it. \$\endgroup\$
    – KSFT
    Commented Jan 14, 2016 at 0:10

2 Answers 2

34
+500
\$\begingroup\$

brainfuck, 6013 4877 4376 bytes

Edit: -1136 bytes. Switched to a better way of generating the data for the quine

Edit2: -501 bytes. Revisited my self-interpreter and cut it down a couple of hundred bytes

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

Try it online! The input here is a simple cat program (,[.,]) which will print the program itself.

"Return 0" is defined by ending the program on a cell with value 0.

A unholy combination of two programs I've written in the past, a quine and a self-interpreter. First section is the quine part, which takes the data and populates the tape with the the data generation followed by the source code. Next is the self-interpreter, which takes your program and runs it. This is pretty much a unchanged copy of a normal self interpreter, except that instead of taking input directly, it gets input from the beginning of the data section, setting the cell to 0 if there is no more input. Finally, end on the current cell of your program and run []. If the returned value was 0, my program will end on zero. If it is anything else, it will run an infinite loop. If your program runs forever, my program will run forever.

How It Works:

Part 1: Data Generation

->++>++++> ....... >+++++>>>+++>>+++>>>++++>+++

This part makes up the data section of the quine, and is by far the majority of the code at 3270 bytes. The beginning - is a marker for the beginning of the data. Each >+++ represents a character of the code after this section.

Number of Pluses
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
> | < | + | ] | [ | - | , | . |

Part 2: Generate the data section using the data

+[<+]>

[
    Add a right arrow
    >[>]>[>]>(10++++++++++)[-<(6++++++)>]<++[<]<[<]
    <+>>-
    Add the right amount of pluses
    [
        [>]>[>]>(7+++++++)[-<(6++++++)>]<+[<]<[<]<+>>-
    ]
    >
]
Add the beginning minus
<--[>+<++++++]>++

This uses the data from part one to add the characters that are used to generate the data to the code section. It adds a > to the end of the code section and that cell's value many pluses.

Part 3: Generate the rest of the code using the data

Initialises the 8 characters of brainfuck
>[>]+++++[->+++<]>[>+++>+++>+++>++++++>++++++>+++>++++>++++[<]>-]
>+>->>+>+++>-->>++[<]<<[<]<<[<]>

Tape looks like:
data 0 0 code 0 0 characters

Runs through the data destructively and adds the represented symbol to the code section
[
    [
        For each plus in this cell
            Shift the gap in the characters over one
        [>]>>[>]>>[>]<[->>+<<]
        <[<]<<[<]<<[<]>-
    ]
    Navigate to character
    >[>]>>[>]>>[>]>>
    Copy the character to the end of the code section
    [-<<+[<]<+>>[>]>]

    Shift the symbol section over one
    <<[[->+<]<]
    >>[>]>[[-<+>]>]

    Navigate to next byte of data
    <<[<]<<[<]<<[<]>
]

Remove characters
>>[>]>>[>]<[[-]<]

Destroys the data section and adds the rest of the source code to the code section

Part 4: Get inputted program

>>>,
[
    >(7+++++++)[<(6------)>-]+<-
    [>]>
    [plus <+<+>>>>]<<<
    -[>]>
    [comma <+<+>>>>]<<<
    -[>]>
    [minus <+<+>>>>]<<<
    -[>]>
    [dot <-<+++>>>>]<<<
    (14--------------)[>]>
    [left <++<+>>>>]<<<
    --[>]>
    [right <-<+++++++>>>>]<<
    (29++++[-<------>]+<+)
    [>]>
    [start loop <++<+>>>>]<<<
    --[>]>
    [end loop <-<+>>>>]<<
    -<[+]<[>]>,
]

Gets the inputted program. Removes non-brainfuck characters and represents each character with a number:

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
] | [ | . | - | , | + | > | < |

Represents the end of the program with 255.

Part 5: Interpreting the input

Initialise simulated tape
>>>+<<<<-

[<]>
[
    -[<<]>
    [end loop
        co 0 0 0 e:  _1 0 0 0 1 ?
        Check if current cell is one
        <+[>]>>[<]<<
        co 0 0 1 e _1: 0 0 !0 1
        or
        co 0 0 1 e _1 0: 0 0 1
        [ If current cell is one navigate to corresponding start loop
            Create counter
            >>+
            [
                co 0 0 de _1 0 c: !0 1
                checks if next instruction is an end loop
                <<[<]<<-
                [>>]<
                c !0 0: 0 de _1 0 c !0 1
                or
                c: 0 0  0 de _1 0 c !0 1
                [>>>>[>]>+<<[<]<] Add one to counter if it is
                checks if start loop
                <-[>>]<
                c !0 0: 0 de _1 0 c !0 1
                or
                c: 0 0  0 de _1 0 c !0 1
                [>>>>[>]>-<<[<]<] Subtract one from counter if it is
                c ? 0: 0 de _1 0 c !0 1
                Adds two to counteract checks and move to the next instruction
                <++[->>+<<]
                >>[>]>
                c 0 0 ode _1 0 c: !0 1
                End on the counter
                    If the counter is 0 then we have reached the corresponding bracket
            ]
            c 0 0 2 de _1 0 0: !0 1 0
            <
        ]
        c 0 0 1?2 de _1 0: 0 0 1 0
        Subtract one from current instruction
            This executes the start loop code next but that does nothing
        <[<]>-<
    ]
    >-[<<]>
    [start loop
        c 0 0 0 de:  _1 0 0 ? 1
        <++[>]>>[<<]>
        c 0 0 2 de _1 0 0 0 1:
        or
        c 0 0 2 de _1 0 0: !0 1
        [ If current cell is 0 navigate to corresponding end loop
            Initialise counter
            <<+
            c 0 0 ode _1 0 c: 0 1
            [ While counter is not 0
                Transfer current instruction over (first instruction is guaranteed to be start loop)
                <<[<]>[-<<+>>]>
                co 0 0 de _1 0 c: 0 1
                Check if start loop
                --[<<]>
                co 0 0: !0 e _1 0 c 0 1
                or
                co 0 0 0 e _1 0 c 0 1
                [[>]>+<<[<]<] Add one to counter if so
                checks if end loop
                >+[<<]>
                co 0 0: !0 e _1 0 c 0 1
                or
                co 0 0 0 e:  _1 0 c 0 1
                [[>]>-<<[<]<] Subtract one from counter if so
                Add one to counteract checks and navigate to counter
                >+[>]>
                co 0 0 de _1 0 c: 0 1
                End on counter
                    If counter is 0 then we have reached the corresponding end loop
            ]
            co 0 1 e _1 0 0: 0 1
        ]
        co 0 0 2?1 e _1 0 0: ? 1
        Subtract two from the current instruction to bring it back up to the right value
        <<[<]>--<
    ]
    3 of these are pretty self explanatory
    Navigate to the current cell and execute the instruction on it
    >-[<<]>
    [output
        [>]>>.<<<[<]<
    ]
    >-[<<]>
    [minus
        [>]>>-<<<[<]<
    ]
    >-[<<]>
    [input
        Reset current cell
        [>]>>, (no more input so this is set to 0)
        co 0 0 0 e:  _1 0 0 0: 1 b 1 a 0 d 1 e 1 f
        Navigate to start of code section
        <<<[<]<<<[<]<[<]>
        d: ata 0 co 0 0 0 e _1 0 0 0 1 b
        or
        0: co 0 0 0 e _1
        Transfer next instruction to current cell
        [[>]>[>]>>>[>]>>+<<<[<]<<<[<]<[<]>-]
        0: ata 0 co 0 0 0 e _1 0 0 d 1 b
        or
        0: co 0 0 0 e _1
        Navigate back to the normal spot
        >[>]>[>]>>[<]<
    ]
    >-[<<]>
    [plus
        [>]>>+<<<[<]<
    ]
    >-[<<]>
    [right
        Simulated tape looks like:
            a b c: d e f
        co 0 0 0 e:  _1 0 0 c 1 b 1 a 0 d 1 e 1 f
        Navigate to value of cell to the right
        [>]>>>[>>]>
        co 0 0 0 e _1 0 0 c 1 b 1 a 0 d: 1 e 1 f
        Transfer it to temporary cell
        [<<<[<<]<+>>>[>>]>-]
        co 0 0 0 e _1 d 0 c 1 b 1 a 0 0: 1 e 1 f
        Pop extra marker if it exists from the right cells and add one to the left
        >[-]<<+
        co 0 0 0 e _1 d 0 c 1 b 1 a 1: 0 0 e 1 f
        Transfer all left cells over 2 cells
        [<[->>+<<]<]<[->>+<<]
        co 0 0 0 e _1 0: 0 d 1 c 1 b 1: a 0 e 1 f
        Navigate back to normal spot
        <[<]<
    ]
    >-[<<]>
    [left
        Simulated tape looks like:
            a b c: d e f
        co 0 0 0: e _1 0 0 c 1 b 1 a 0 d 1 e 1 f
        Add temporary marker
        [>]>++
        co 0 0 0 e _1 0 2: c 1 b 1 a 0 d 1 e 1 f
        Remove temporary marker and transfer all left cells over two
        [-->[-<<+>>]>]
        co 0 0 0 e _1 c 0 b _1 a _1 0 0: d 1 e 1 f
        Add marker to right cells remove marker from left cells and reset left cell's markers
        +<<-[++<<]<
        co 0 0 0 e _1 c: 0 b 1 a 0 0 1 d 1 e 1 f
        Transfer current cell to to right cells
        [->>>[>>]>+<<<[<<]<]
        co 0 0 0 e _1 0: 0 b 1 a 0 c 1 d 1 e 1 f
        Navigate back to normal spot
        <[<]<
    ]
    Add 8 to reverse checks
    <(8++++++++)>>

    Execute next instruction
    [+<<->>]>
]

Interprets the program. The only difference from a normal one is that the input is taken from the beginning of the code section instead of the input.

Part 6: Halt if return is not 0

>>[]

Navigate to the ending cell of your program and run an infinite loop if the return is not 0. If it is 0, exit the loop and end on that same 0.

Test Inputs:

Always returns 0 (halts and returns 0)

(empty program)

Always returns 1 (runs forever)

+

Returns all input added together, mod 256 (returns 211, so it runs forever)

,[[->+<],]>

Returns 0 if the last two characters of a code are an infinite loop ([]) (your program returns 0 when given my program, therefore my program halts)

,[>,]>(9+++++++++)[-<(10++++++++++)>]<[-<-<->>]+<---[[-]>[-]<]<-[[-]>>[-]<<]>+>[-<->]<    

Fun Fact for those who are still reading

If the input for this program is the source code of this program, then it will start recursing, repeatedly creating self-interpreters that run this program and then give it the same program again. This gives me some interesting ideas on creating actual recursive programs in brainfuck. Instead of checking the return value and starting an infinite loop as in this question, the return value can be saved and acted upon. A simple example would be a factorial program that goes

If cell1 == 0:
    Get input into cell1
If cell1 == 1 or cell1 == 0:
    Return 1
Else:
    Initialise self-interpreter-quine function
    Pass cell1-1 into cell1 of the function
    Run function
    Multiply cell1 by the return value
    Return cell1

Of course, this is a completely insane way of coding brainfuck, given that running recursing self-interpreters will increase the runtime exponentially.

\$\endgroup\$
5
  • \$\begingroup\$ Yay! BTW if you wanted to golf this, given your return convention I think you could drop supporting .. Although since this is no longer a code-golf question, supporting the whole language may be more impressive. \$\endgroup\$ Commented Jan 3, 2018 at 16:48
  • \$\begingroup\$ @ØrjanJohansen, I can probably golf a thousand or so bytes off by switching to a different data generation method alone. Also, the self-interpreter isn't the smallest one I could write, as it supports negative cells. \$\endgroup\$
    – Jo King
    Commented Jan 3, 2018 at 17:32
  • \$\begingroup\$ This looks like it should win the bounty, but I want to take my time to understand it, not being a BF expert myself. Can you ping me if you don't hear back some time next week? \$\endgroup\$
    – N. Virgo
    Commented Jan 4, 2018 at 4:46
  • 1
    \$\begingroup\$ I confirm that this meets the spec, as far as I can tell. A bounty should be winging its way to you shortly. (There is a delay before the system will let me award it.) Thank you for the answer, it is much appreciated. \$\endgroup\$
    – N. Virgo
    Commented Jan 8, 2018 at 4:07
  • 2
    \$\begingroup\$ You may be interested in Muriel. \$\endgroup\$ Commented Dec 4, 2018 at 1:53
7
+500
\$\begingroup\$

Lazy K, 5891 5861 5841 bytes

````ssk``s``si``s``si`ks``s``si`kk``s``si``s``si`ks``s``si``s``si`ks``s``si`kk`k
s``s``si``s``si`ks``s``si``s``si`ks``s``si`kk`ks``s``si``s``si`ks``s``si`kk``s``
si`ks``s``si``s``si`ks``s``si``s``si`ks`ki``s``si`kk``s``si``s``si``s``si`ks`ki`
`s``si`ks``s``si`kk``s``si``s``si`ks``s``si``s``si`ks``s``si`kk`ks``s``si``s``si
`ks``s``si`kk``s``si`ks``s``si``s``si`ks``s``si``s``si`ks`ki``s``si`kk``s``si``s
``si`ks`ki`kk``s``si`kk`ki``s``si``s``si`ks``s``si`kk`kk``s``si``s``si`ks``s``si
`kk`kk``s``si``s``si`ks``s``si``s``si`ks``s``si`kk`ks``s``si``s``si`ks``s``si`kk
``s``si`ks`ki`kk``s``si``s``si`ks``s``si`kk`kk``s``si``s``si`ks``s``si``s``si`ks
``s``si`kk`ks``s``si``s``si`ks``s``si`kk`kk``s``si``s``si`ks``s``si`kk`ks``s``si
``s``si`ks``s``si`kk``s``si`ks`ki`kk``s``si`kk``s``si``s``si`ks``s``si`kk`kk``s`
`si`ks``s``si`kk``s``si``s``si`ks``s``si``s``si`ks``s``si`kk`ks``s``si``s``si`ks
``s``si`kk`kk``s``si``s``si`ks``s``si`kk`ks``s``si``s``si`ks``s``si`kk``s``si`ks
`ki`kk``s``si`kk`kk``s``si`kk``s``si``s``si`ks``s``si``s``si`ks``s``si`kk`ks``s`
`si``s``si`ks``s``si`kk`kk``s``si``s``si`ks``s``si`kk`ks``s``si``s``si`ks``s``si
`kk``s``si`ks`ki``s``si``s``si``s``si`ks`ks``s``si`ks``s``si``s``si`ks``s``si``s
``si`ks``s``si``s``si`ks``s``si``s``si`ks`ki``s``si`kk``s``si``s``si`ks``s``si``
s``si`ks`ki`ki`kk``s``si`kk`ki``s``si`kk``s``si`kk``s``si`kk`ki``s``si`kk``s``si
`kk`ks``s``si`kk`kk``s``si`kk`kk``s``si``s``si`ks`ki`ki``s``si`kk`kk``s``si``s``
si`ks``s``si`kk`kk``s``si``s``si`ks``s``si``s``si`ks``s``si``s``si`ks``s``si``s`
`si`ks``s``si``s``si`ks``s``si``s``si`ks``s``si``s``si`ks`ki``s``si`kk``s``si``s
``si`ks``s``si`kk``s``si`ks``s``si`kk``s``si``s``si`ks``s``si`kk`kk``s``si``s``s
i`ks``s``si`kk`kk``s``si``s``si`ks``s``si`kk`kk``s``si``s``si`ks``s``si`kk`kk`kk
``s``si``s``si`ks``s``si`kk``s``si`ks``s``si`kk``s``si`ks``s``si`kk``s``si``s``s
i`ks``s``si`kk``s``si`ks``s``si``s``si`ks`ki``s``si`kk``s``si``s``si``s``si`ks``
s``si``s``si``s``si`ks``s``si``s``si`ks`ki`ki``s``si``s``si`ks`ks`ks``s``si``s``
si`ks``s``si`kk`ks`kk``s``si``s``si`ks`ki``s``si``s``si`ks`ki`ki``s``si``s``si`k
s``s``si``s``si`ks``s``si`kk`ks`kk`ki`kk``s``si``s``si`ks``s``si``s``si`ks``s``s
i`kk`ks``s``si``s``si`ks``s``si``s``si`ks``s``si`kk`ks``s``si``s``si`ks``s``si`k
k`kk``s``si``s``si`ks``s``si`kk`ks``s``si``s``si`ks``s``si`kk``s``si`ks``s``si`k
k``s``si``s``si`ks``s``si`kk`ks`kk``s``si``s``si`ks``s``si`kk``s``si`ks`ki`kk``s
``si`kk``s``si``s``si`ks``s``si`kk``s``si`ks`ki`kk``s``si`kk``s``si`kk``s``si``s
``si`ks``s``si``s``si`ks``s``si``s``si`ks``s``si``s``si`ks``s``si``s``si`ks`ki``
s``si`kk``s``si`kk`ki``s``si`kk``s``si`kk``s``si`kk``s``si``s``si`ks`ki``s``si`k
k``s``si``s``si`ks`ks``s``si``s``si`ks``s``si``s``si`ks`ki``s``si``s``si`ks`ks``
s``si`kk`ki``s``si``s``si`ks`ks``s``si``s``si`ks``s``si``s``si`ks`ks`ks``s``si``
s``si`ks`ks``s``si``s``si`ks``s``si``s``si`ks`ks`ks``s``si``s``si`ks`ks``s``si`k
k`ki``s``si`kk``s``si`kk``s``si``s``si`ks`ki``s``si`kk``s``si``s``si`ks``s``si``
s``si`ks`ki``s``si``s``si`ks`ks``s``si``s``si``s``si`ks`ks`ki``s``si``s``si`ks`k
s``s``si`kk`ki``s``si``s``si`ks`ks``s``si``s``si`ks``s``si``s``si`ks`ks`ks``s``s
i``s``si``s``si`ks`ks`ki``s``si``s``si`ks`ks``s``si`kk`ki``s``si`kk``s``si``s``s
i`ks`ki``s``si`kk``s``si``s``si`ks``s``si``s``si`ks``s``si``s``si``s``si`ks`ks`k
i``s``si``s``si`ks`ks``s``si``s``si`ks`ks``s``si`kk`ki`ks``s``si``s``si`ks``s``s
i``s``si`ks`ks``s``si``s``si`ks``s``si``s``si`ks`ki`ks`ks``s``si``s``si`ks``s``s
i``s``si`ks`ks``s``si``s``si`ks`ks``s``si`kk`ki``s``si``s``si`ks`ks``s``si`kk`ki
``s``si`kk``s``si``s``si`ks``s``si``s``si`ks``s``si`kk`ks``s``si``s``si`ks``s``s
i`kk`kk``s``si``s``si`ks``s``si`kk`ks``s``si``s``si`ks``s``si`kk``s``si`ks`ki``s
``si``s``si`ks``s``si`kk`kk``s``si``s``si`ks`ki``s``si`kk``s``si``s``si`ks``s``s
i`kk`ks`kk``s``si`kk`kk``s``si`kk`ki``s``si`kk`ki``s``si`kk`ki``s``si`kk`ki``s``
si`kk`ki``s``si`kk``s``si``s``si``s``si`ks`ki``s``si`ks``s``si`kk``s``si``s``si`
ks``s``si`kk``s``si`ks``s``si``s``si`ks`ki``s``si`kk``s``si``s``si``s``si`ks``s`
`si``s``si`ks`ki`ki``s``si``s``si`ks`ki`ki``s``si``s``si`ks``s``si``s``si`ks``s`
`si`kk`ks`kk`ki`kk``s``si``s``si`ks`ki`ki``s``si`kk``s``si`kk``s``si``s``si``s``
si`ks`ki`ki``s``si``s``si`ks`ki`ki``s``si`kk``s``si`kk``s``si`kk`ki``s``si``s``s
i`ks``s``si``s``si`ks``s``si`kk`ks``s``si``s``si`ks``s``si`kk``s``si`ks`ki``s``s
i``s``si`ks``s``si`kk``s``si`ks``s``si``s``si`ks`ki``s``si``s``si`ks``s``si``s``
si`ks`ki``s``si``s``si`ks``s``si``s``si`ks`ki``s``si`kk`ks``s``si`kk`ks``s``si`k
k`kk``s``si``s``si`ks``s``si``s``si`ks``s``si``s``si`ks``s``si``s``si`ks``s``si`
`s``si`ks``s``si``s``si`ks`ki``s``si`kk``s``si``s``si`ks``s``si``s``si`ks``s``si
`kk`ks``s``si``s``si`ks``s``si``s``si`ks``s``si`kk`ks``s``si``s``si`ks``s``si`kk
`kk``s``si``s``si`ks``s``si`kk`ks``s``si``s``si`ks``s``si`kk``s``si`ks``s``si`kk
``s``si``s``si`ks``s``si`kk``s``si`ks``s``si`kk`kk``s``si``s``si`ks``s``si`kk``s
``si`ks``s``si`kk`kk``s``si``s``si`ks``s``si`kk``s``si`ks``s``si`kk`kk``s``si``s
``si`ks``s``si`kk``s``si`ks``s``si`kk`kk``s``si``s``si`ks``s``si`kk``s``si`ks``s
``si`kk`kk``s``si``s``si`ks``s``si`kk`ks``s``si``s``si`ks``s``si`kk``s``si`ks`ki
``s``si``s``si`ks``s``si`kk``s``si`ks``s``si``s``si`ks`ki``s``si`kk`ks``s``si`ks
``s``si``s``si`ks`ki``s``si``s``si`ks``s``si``s``si`ks`ki``s``si`kk`ks``s``si`kk
`ki``s``si``s``si`ks``s``si`kk``s``si`ks`ki`kk``s``si`kk``s``si``s``si`ks``s``si
`kk``s``si`ks`ki`kk``s``si`kk``s``si`kk``s``si``s``si`ks``s``si``s``si`ks``s``si
``s``si`ks``s``si``s``si`ks``s``si``s``si`ks`ki``s``si`kk``s``si`kk`ki``s``si`kk
``s``si`kk``s``si`kk``s``si``s``si`ks`ki``s``si`kk`ks``s``si`kk``s``si`kk``s``si
``s``si`ks`ki``s``si`kk`ki``s``si`kk``s``si``s``si`ks`ki``s``si`kk`kk``s``si`kk`
`s``si``s``si`ks``s``si`kk``s``si`ks``s``si``s``si`ks`ki``s``si`kk`kk`kk``s``si`
kk`ki``s``si`kk`ki``s``si`kk`ki``s``si`kk`ki``s``si`kk`ki``s``si`kk``s``si`kk`ki
i

Line breaks added for clarity.

This program is written in, and is capable of parsing, only the Unlambda-syntax subset of Lazy K; that is:

program ::= "s" | "k" | "i" | "`" program program.

It expects input to be encoded in the standard format for Lazy K: an input stream is a pair whose first element is a Church numeral, representing the first byte of the stream, and whose second element is the remaining input stream. However, the output is expected to be only a single Church numeral rather than a full output stream.

The parsing part

If we look at the character codes for the relevant bits of Lazy K syntax, we notice something interesting:

  • s is 115, or 1 mod 6;
  • k is 107, or 5 mod 6;
  • i is 105, or 3 mod 6;
  • ` is 96, or 0 mod 6.

If we assume the input program is part of the relevant subset, we can distinguish application using only a parity test, and then distinguish the combinators from each other using remainder mod 3.

Doing these tests effectively in combinatory logic requires a little cleverness, though.

  • mod 2: the idea is to find terms a, b, and f such that f a = b and f b = a, and then call N f a and examine the result. Traditionally the Church booleans are used for a and b and f is not, but not is annoyingly difficult to encode in SKI. Instead, I did an automated search for terms that would work, and it came up with this:
    • S I K I = I (K I) = K I;
    • S I K (K I) = K I (K (K I)) = I.
  • mod 3: similarly, we find distinct terms a, b, c, f with f a = b, f b = c, f c = a. A search yielded:
    • S (S I I) K I = I I (K I) = K I;
    • S (S I I) K (K I) = K I (K I) (K (K I)) = K (K I);
    • S (S I I) K (K (K I)) = K (K I) (K (K I)) (K ...) = I.

Given these, we can write a fairly conventional recursive-descent parser:

parse : stream -> (term, stream)
parse (c, rest) =
  match (c mod 2)

    0 -> let (f, rest') = parse rest
         let (x, rest'') = parse rest'
         (f x, rest'')

    1 -> ((match (c mod 3)
           0 -> I
           1 -> S
           2 -> K), rest)

The quining part

This is the fun part. One of the most important parts of any quine is figuring out a data format to represent the encoded form of the program. This ends up being the largest source of overhead since it essentially multiplies the program's length.

The representation I went with involves a lambda that substitutes its argument for every application in the encoded term, but leaves combinators unchanged. For example, the SKI-term (S S) (K I) would be encoded as:

λf. f (f S S) (f K I)

In terms of SKI, the encoding looks like this:

[e] denotes the encoded form of the expression e:

[S]   = (K S)
[K]   = (K K)
[I]   = (K I)
[a b] = S (S I [a]) [b]

This encoding introduces 3x overhead for combinators and 7x overhead for applications. There are about equally many applications and combinators in any Lazy K term, so this encoding has ~5x overhead. There are other encodings which are more efficient than this. For example, @msullivan's quine uses a representation which exploits the fact that top-level terms are applied together to have just 1.5x overhead. However, this approach has several disadvantages. It supports only the S and K combinators, making the body of the quine more verbose. It relies on going outside of the Unlambda subset of the syntax, so I would need to make the parser more complex. Finally, it lacks a very useful feature of my representation: it can be trivially "interpreted" into the term it represents by passing I as the argument, avoiding the need to store both the encoded and decoded form of the quine payload. Nevertheless, the savings from using a more efficient representation like this are so large that it would probably be worth doing.

Finally there is the task of stringifying the encoded quine to obtain the source code and passing it to the parsed input term. For this we need to construct the Church numerals 96, 105, 107, and 115. For golfing purposes I was able to find terms which are much more efficient than the constructions given in the standard library: 96 is reduced from 63 bytes to 45, 105 is reduced from 81 bytes to 57, 107 is reduced from 91 bytes to 69, and 115 is reduced from 89 bytes to 57. I obtained these using alternative representation of numbers which can be easily converted to and from Church numerals. This representation admits much more compact definitions of succ and +, and only slightly less compact definitions of * and ^.

Also, there is the problem of traversing the encoded form of the program to build up the stringified form. For this, we effectively need f x y to be able to distinguish the cases when its arguments are combinators and when its arguments are further applications of f. We accomplish this using a helper function:

helper(x) = x (K I) (K (K (λt. t foo))) (K (λt. t baz)) (λt. t bar) t

This evaluates to t foo, t bar, and t baz when passed S, K, and I as arguments respectively, but you can also pass (λ a b c d e. something else) to distinguish applications. This kind of function is unfortunately relatively cumbersome when encoded in SKI, but I haven't found anything better. We use a difference list to accumulate the stringified representations, since it makes it very cheap to append (just function composition) and doesn't require modification to work with infinite streams.

Further golfing

How to improve this:

  • Use a better data representation, even though this comes at the cost of easy interpretation.
  • Find a more efficient way to distinguish the S, K, and I combinators. If a better way exists, it's too large for my search program to find it as-is, so I would need to make it more efficient somehow or make assumptions to reduce the search space.
  • Find more efficient representations of each of the numbers. 96 in particular feels like it could be improved a lot, although it's probably also too large for the search program.
  • Better optimize parse, since it has some room for improvement.

The Lazier code used to generate this program can be found here.

\$\endgroup\$
1
  • \$\begingroup\$ This is a great answer! Another user has posted a bounty to reward it, which I'm very happy about. \$\endgroup\$
    – N. Virgo
    Commented Jun 7, 2022 at 2:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.