New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Every Novel Generator #120

Open
cpressey opened this Issue Nov 27, 2017 · 5 comments

Comments

Projects
None yet
5 participants
@cpressey

cpressey commented Nov 27, 2017

In the spirit of all those "every X" bots on that bird site, this is a novel generator generator; it generates every novel generator, one by one, in sequence. It also runs these generators, interleaving their outputs, so it is itself also a novel generator, generating a novel consisting of every possible novel generated in every possible way.

Code

This novel generator generator is written in 204 lines of Python 2.7 code. I can't make you read them, but I can at least make you scroll down over them to get to the novel.

class Collector(object):
    def __init__(self, title, stream, limit=None):
        self.stream = stream
        self.count = 0
        self.limit = limit
        self.closed = False
        self.write('<html><head><title>{}</title></head><body><h1>{}</h1>'.format(title, title))

    def write(self, s):
        if self.closed:
            return
        self.stream.write(s)
        self.stream.flush()

    def recv(self, word, sender=None):
        if sender:
            self.write('<span title="{}">{}</span>\n'.format(sender.replace('<', '&lt;').replace('>', '&gt;'), word))
        else:
            self.write('{} '.format(word))
        self.count += 1
        if self.limit is not None and self.count >= self.limit:
            self.close()

    def close(self):
        self.write('</body></html>')
        self.closed = True

class Buffer(object):
    def __init__(self, title, collector, printable):
        self.title = title
        self.collector = collector
        self.printable = printable
        self.word = ''

    def flush(self):
        if self.word:
            self.output()
            self.word = ''

    def accum(self, chars):
        for char in chars:
            if char in self.printable:
                self.word += char
            else:
                self.flush()

    def output(self):
        self.collector.recv(self.word, sender=self.title)

class Alphabet(object):
    def __init__(self, chars):
        self.chars = list(chars)
        self.succ_map = dict([(c, chars[i + 1] if i < len(chars) - 1 else chars[0]) for i, c in enumerate(chars)])
        self.pred_map = dict([(c, chars[i - 1] if i > 0 else chars[-1]) for i, c in enumerate(chars)])

    def __contains__(self, c):
        return c in self.chars

    def first(self):
        return self.chars[0]

    def last(self):
        return self.chars[-1]

    def succ(self, c):
        return self.succ_map[c]

    def pred(self, c):
        return self.pred_map[c]

class IncrementableString(object):
    def __init__(self, alphabet, value):
        self.alphabet = alphabet
        self.value = list(value)

    def __str__(self):
        return ''.join(self.value)

    def zero(self):
        return self.alphabet.first()

    def succ_value(self, value):
        if not value:
            return [self.zero()]
        if value[0] == self.alphabet.last():
            return [self.zero()] + self.succ_value(value[1:])
        else:
            return [self.alphabet.succ(value[0])] + value[1:]

    def incr(self):
        self.value = self.succ_value(self.value)

class Interpreter(object):
    def __init__(self, program, buffer_, alphabet):
        self.program = program
        self.buffer = buffer_
        self.alphabet = alphabet
        self.pc = 0
        self.tape = {}
        self.head = 0L
        self.halted = False

    def read_tape(self):
        return self.tape.get(self.head, self.alphabet.first())

    def write_tape(self, symbol):
        self.tape[self.head] = symbol

    def step(self):
        instruction = self.program[self.pc]

        if instruction == '<':
            self.head -= 1L
        elif instruction == '>':
            self.head += 1L
        elif instruction == '+':
            self.write_tape(self.alphabet.succ(self.read_tape()))
        elif instruction == '-':
            self.write_tape(self.alphabet.pred(self.read_tape()))
        elif instruction == '.':
            self.buffer.accum(self.read_tape())
        elif instruction == '[':
            if self.read_tape() == self.alphabet.first():
                depth = 0
                while True:
                    if self.program[self.pc] == '[':
                        depth += 1
                    if self.program[self.pc] == ']':
                        depth -= 1
                        if depth == 0:
                            break
                    self.pc += 1
        elif instruction == ']':
            depth = 0
            while True:
                if self.program[self.pc] == '[':
                    depth -= 1
                if self.program[self.pc] == ']':
                    depth += 1
                self.pc -= 1
                if depth == 0:
                    break

        self.pc += 1
        if self.pc >= len(self.program):
            self.buffer.flush()
            self.halted = True

class ProgramGenerator(object):
    def __init__(self, start):
        self.source = IncrementableString(Alphabet('+-<>[].'), start)

    def next(self):
        program = str(self.source)
        self.source.incr()
        while not self.is_balanced(program):
            program = str(self.source)
            self.source.incr()

        return program

    def is_balanced(self, s):
        level = 0
        for c in s:
            if c == '[':
                level += 1
            elif c == ']':
                level -= 1
                if level < 0:
                    return False
        return level == 0

class Orchestrator(object):
    def __init__(self, collector, printable, starting_at):
        self.collector = collector
        self.printable = Alphabet(printable)
        self.alphabet = Alphabet(" " + printable)
        self.generator = ProgramGenerator(starting_at)
        self.interpreters = {}
        self.halted = False

    def step(self):
        reap = set()
        for program, interpreter in self.interpreters.iteritems():
            interpreter.step()
            if interpreter.halted:
                reap.add(program)
        for program in reap:
            del self.interpreters[program]

        program = self.generator.next()
        buffer_ = Buffer(program, self.collector, self.printable)
        self.interpreters[program] = Interpreter(program, buffer_, self.alphabet)

    def run(self):
        while not self.collector.closed:
            self.step()

if __name__ == '__main__':
    import string
    import sys
    title = "The Collected Works of Every Novel Generator Ever (Abridged Version)"
    collector = Collector(title, sys.stdout, limit=50000)
    Orchestrator(collector, string.lowercase + """.,!:;'"-""" + string.uppercase, starting_at='+').run()

Result

The first 50,000 words of output have been collected into a single document. This is, itself, a novel, to which I have given the title "The Collected Works of Every Novel Generator Ever (Abridged Version)". You can view or download it here:

The Collected Works of Every Novel Generator Ever (Abridged Version)

Note that, as a convenience, hovering over any word shows which novel generator produced it.

Discussion

Does it really generate every novel generator?

Yes, if given sufficient resources, and if by "novel generator" you mean "program in a minor variant of Everybody's Favourite Esolang".

Since it runs the novel generators that it generates, is this novel generator generator also a novel generator?

Yes.

Since this novel generator generator is also a novel generator, will it eventually generate itself?

Yes, given sufficient resources.

Since some novel generators run on and on forever, how does this run them all?

It keeps track of a set of generators that have been generated thus far, runs each generator one step, then adds a new generator to the set, and does this over and over again. The generators that never halt just keep "wasting cycles in the background", but this doesn't stop the overall process.

As a point of trivia, this is also the method used in the standard proof that a non-deterministic Turing machine is no more powerful than a deterministic one. It's worth studying the code if you're curious about how it works in detail.

Since it only generates programs in Everybody's Favourite Esolang, it won't generate my generator.

Everybody's Favourite Esolang is Turing-complete, so if your novel generator is written in some other language which is no more than Turing-complete (which is, y'know, all known programming languages), this will generate its equivalent in Everybody's Favourite Esolang.

So what it produces is only an equivalent of my generator in Everybody's Favourite Esolang. It's not my generator.

Well, actually, given enough resources, it will eventually generate e.g. a Python interpreter (in Everybody's Favourite Esolang) and an initial sequence of code that writes your-generator-written-in-Python to the tape and then runs the Python interpreter on it. So, yes. It will eventually produce your generator.

But my generator reads an input corpus from text files.

Given sufficient resources, this generator will eventually generate a program in Everybody's Favourite Esolang that, before running your novel generator, writes the content of those text files to the tape, where they can be read by your novel generator.

But my generator reads random files on the Internet to generate its result.

Given sufficient resources, this generator will eventually generate a program in Everybody's Favourite Esolang that, before running your novel generator, writes THE ENTIRE CONTENT OF THE INTERNET to the tape, where it can be read by your novel generator.

And actually it generates an infinite number of such generators, each of which writes a different content of the Internet to the tape.

But my generator writes a novel with interrobangs! This doesn't output interrobangs!

Indeed, these generators do not even output digits. I chose the character set that I did for aesthetic purposes (it makes the "early" novels look slightly more sensible); still, I am comforted that many well-known novels could in fact be rendered fully in it.

I'm sure with a little thought you will see the lack of interrobangs here is either a basically insurmountable problem (can we not always define "text" to include symbols which currently no computer can represent?) or a trivially surmountable problem (define an encoding between strings in the character set you have and the character set you want -- just like Unicode already does with bits, really).

Will this eventually generate a generator which generates all the novels of Ernest Hemingway?

Given sufficient resources, yes. Of course, you realize that such a generator could be just a big print statement.

Will this eventually generate Ernest Hemingway?

This is a philosophical question. If you are David Deutsch, or someone else who firmly believes the universe is just a big ol' Turing machine (quantum or otherwise), then presumably you believe it will. Including writing, not the entire contents of the Internet, but THE ENTIRE CONTENTS OF HEMINGWAY'S LIVED EXPERIENCE, to the tape at the beginning.

But not everyone shares Deutsch's views.

You keep saying "sufficient resources". What does that mean?

Well, there are an infinite number of novel generators, so if you actually wanted to generate them all you'd need infinite time and infinite storage. Whether that's even possible is another philosophical question. But it's safe to say that few people claim to have access to these.

The time and memory required to generate any particular generator might be difficult to estimate, but certain bounds can be drawn, e.g. a generator that writes the entire contents of the Internet to its tape will require a tape at least as big as the Internet, and will take at least as many steps as that simply to write it out.

@hugovk hugovk added the completed label Nov 27, 2017

@hugovk

This comment has been minimized.

Show comment
Hide comment
@hugovk

hugovk Nov 27, 2017

Member

Generates every novel generator? We can now declare this the end of NaNoGenMo and do something else next November!

Member

hugovk commented Nov 27, 2017

Generates every novel generator? We can now declare this the end of NaNoGenMo and do something else next November!

@schas002

This comment has been minimized.

Show comment
Hide comment
@schas002

schas002 Nov 27, 2017

<...> We can now declare this the end of NaNoGenMo and do something else next November!

↑_↑

Please no.

schas002 commented Nov 27, 2017

<...> We can now declare this the end of NaNoGenMo and do something else next November!

↑_↑

Please no.

@greg-kennedy

This comment has been minimized.

Show comment
Hide comment
@greg-kennedy

greg-kennedy Nov 27, 2017

But my generator writes a novel with interrobangs! This doesn't output interrobangs!

Also, this generator will eventually output a completely valid PDF document consisting of 500 valid PNG images containing pictures of interrobangs.

greg-kennedy commented Nov 27, 2017

But my generator writes a novel with interrobangs! This doesn't output interrobangs!

Also, this generator will eventually output a completely valid PDF document consisting of 500 valid PNG images containing pictures of interrobangs.

@tra38

This comment has been minimized.

Show comment
Hide comment
@tra38

tra38 Nov 28, 2017

Note that, as a convenience, hovering over any word shows which novel generator produced it.

Hovering doesn't seem to work for me. I'm actually curious about the hovering, since it is proof that this does contains multiple novel generators.

tra38 commented Nov 28, 2017

Note that, as a convenience, hovering over any word shows which novel generator produced it.

Hovering doesn't seem to work for me. I'm actually curious about the hovering, since it is proof that this does contains multiple novel generators.

@cpressey

This comment has been minimized.

Show comment
Hide comment
@cpressey

cpressey Oct 18, 2018

@tra38 A belated reply to your bug report: in the document in question, around every word, there's a span tag with a title tag that contains the generator that produced it.

Most browsers will show the title tag of an element after you hover over it (often not instantaneously, only after a second or two), but if yours doesn't, you can also View Source to see them. (Note that in the HTML source, the < and > characters are percent-encoded, as usual.)

cpressey commented Oct 18, 2018

@tra38 A belated reply to your bug report: in the document in question, around every word, there's a span tag with a title tag that contains the generator that produced it.

Most browsers will show the title tag of an element after you hover over it (often not instantaneously, only after a second or two), but if yours doesn't, you can also View Source to see them. (Note that in the HTML source, the < and > characters are percent-encoded, as usual.)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment