[samsquire]

Hi, this is interesting, thanks for this :-)

I am interested in the future of computing too.

I especially enjoyed what you said about genetic programming for instruction sets.

I recently wrote a program that uses the A* graph search algorithm to generate assembly code. I call it program synthesis. In ChatGPT you can get ChatGPT to generate code, so this kind of already exists.

My program synthesis/codegeneration is for searching through state space of a program to allocate variables to values and arrange state for function calls. It is meant to automate the boring part of programming which is boilerplate and moving things into place. It learns the hidden states - the function calls to get the register and memory to be what they should be.

My program takes two states: a beginning state and and end state, including memory locations and infers the instructions used to reach the end state. Functional programmers love types, I use the idea of types but value tracing.

  start_state = {
    "memory": [0, 0, 0, 0],
    "rax": 0,
    "rbx": 1,
    "rcx": 2,
    "rdx": 3,
    "rsp": -1,
    "rdi": -1,
    "rbp": -1
  }

  end_state = {
    "memory": [3, 1, 2, -1],
    "rax": 3,
    "rbx": 2,
    "rcx": 1,
    "rdx": 0,
    "rsp": 6,
    "rdi": -1,
    "rbp": -1
  }
  # These functions take in an argument of value type given by that number and return a value type given by the second paramter.
  minus_1_to_four = Function("minus1", -1, 4)
  four_to_five = Function("fourtofive", 4, 5)
  five_to_six = Function("fivetosix", 5, 6)

This generates the following sequence of instructions.

[start, mov %rax, (%rdx), mov %rbx, (%rbx), mov %rcx, (%rcx), mov %rdx, (%rsp), mov %rax, %rsp, mov %rdx, %rax, mov %rsp, %rdx, mov %rcx, %rsp, mov %rbx, %rcx, mov %rsp, %rbx, call minus1(rdi=-1) -> rsp=4, call fourtofive(rsp=4) -> rsp=5, call fivetosix(rsp=5) -> rsp=6]

Code is here:

https://replit.com/@Chronological/SlidingPuzzle3

Please take this with love but I notice the theme of the Bible and God in this post, if you have not studied God, I recommend studying God it shall transform for your mind and you will no longer be conformed to the pattern of this world. I would stay away from the occult though (some of the text in the diagrams in your article resemble spirit texts)

[abeppu]

> I call it program synthesis. In ChatGPT you can get ChatGPT to generate code, so this kind of already exists.

This is cool, but to be clear work on program synthesis predates ChatGPT by _decades_. For a long time the work was searching for a program which met some behavioral specification. Emphasis shifted later towards inductive "programming-by-example" where we synthesize a program based on a small set of inputs and outputs, in part because providing those examples is often easier than thinking through an exact "specification" of what you want.

Some work from the '70s https://dl.acm.org/doi/10.1145/362566.362568 https://dl.acm.org/doi/10.5555/1624626.1624666

Some 21st century work on inductive synthesis https://link.springer.com/chapter/10.1007/978-3-319-21690-4_...

ML + symbolic inductive synthesis: https://arxiv.org/pdf/1809.02840v1.pdf

[samsquire]

Thank you for your reply and thank you for links to 3 (!) whitepapers.

What do you think is a good behavioural specification? I have often thought that: given a log (read: a highly accurate trace of what the program did) of a program, the log indicates what the program does and there are relations between the fields in the log and log lines.

If some program generates the same log, with the same input and output, is the behaviour of that program identical?

Now I want to do these things:

* provide example logs, which are desired behaviour and let the computer work out the code to fulfil that example

* combine the behaviours of one or more programs

* convert log into a tree or graph that resembles invocation stack (for functional application synthesis, such as "this log resembles a post order traversal" or "a normal form")

* tweak the behaviour of one program with the behaviour of another program, "use one program as a tool in the other program"

Could we wire up the logs and cause things to the code that generated them? The log is a bidirectional view into the program's operations and code that generated it.

In other words, modify code and behaviour by modifying behaviours directly and rely on causality feeding backwards through a chain of logic.

[abeppu]

I think different contexts call for different kinds of specification, but most commonly, I do think "synthesize a _function_ which for inputs x1, x2, ..., xk produces outputs y1, y2, ..., yk respectively", is a pretty good setup provided you then are willing to test it on xk+1 ... xn. The "programming-by-example" research direction aligned nicely with TDD, and functions provide a nice abstraction layer.

I _don't_ think a detailed program trace is the best "specification" in most cases because constructing that log includes making a lot of choices of _how_ the program arrives at its outputs. The full trace for meaningful programs might be quite large, and onerous to specify (or you'd just produce one from an already-working program, in which case what's the point?).

For me, the benefit of synthesis should be that the programmer can describe what should be done, rather than how. However, this can quickly lead to a complex "specification language" which can be just as burdensome to write in as the desired target language, which is why examples are appealing. But perhaps some combination, where we provide some examples and also some formally specified restrictions ("the `get_work_history` method returns `jobs: List[Jobs]` such that `map(_.start_date, jobs)` is non-decreasing according to the default comparator on Dates ...") is best, since examples will generally underspecify the program.

Update: the 'different contexts' I think is mostly that sometimes, some specific attributes of 'how' the synthesized program accomplishes its goals do matter -- e.g. you may want to synthesize some mathematical optimization code which really ought to use the GPU, and that isn't indicated in just input/output examples, or you may want to ensure that part of an embedded system uses constant memory and returns after a constant number of steps.

[adamthekiwi]

Wow this is really cool, I'll check this out! Also, thank you for the feedback!