0
$\begingroup$

I wrote a simple stack based language, and am looking to exhaustively generate all programs for it, to find the shortest program that generates a particular output.

Given a program fragment, I can determine if it is terminated, and, if not, how many operands it requires. Currently, my search strategy is:

 If program is terminated --> test it
 else --> add all programs with one additional operand to the queue

However, the queue ends up using too much space. Instead, I'd rather keep the queue small, and find a way to produce all valid programs efficiently (more efficiently than just trying all program text). What is a good strategy to generate all valid programs for a simple stack language?

UPDATE The language is guaranteed to halt (and is of course not Turing complete).

UPDATE: The approach I am working on is as follows:

  1. Observe that, for certain program fragments, nothing that can be appended to them will make them valid
  2. Define an ordering over each token that may appear in a program.
  3. Define a "mayBeAppendedToToMakeAValidProgram" over a incomplete program.
  4. For n = 0 to infinity:
  5. Start with a program of n tokens; set each token to the first
  6. Increment token-0 until mayBeAppendedToToMakeAValidProgram(token-0)
  7. Increment token-1 until mayBeAppendedToToMakeAValidProgram(token-0 + token-1)
  8. Etc. until the last token
  9. Increment the last token until the program is valid; test that program
  10. On to the next one
$\endgroup$
  • 1
    $\begingroup$ Does your language guarantee halting? If not, such an exhaustive search isn't possible, unless you bound the number of execution steps that are allowed. $\endgroup$ – jmite Feb 23 '16 at 4:36
  • $\begingroup$ @jmite An enumerator (by program length, say) is still possible. Here, we know that we have to find a fitting program eventually! $\endgroup$ – Raphael Feb 23 '16 at 10:27
  • $\begingroup$ The question you are asking is "how do I generate all programs with generating all programs". $\endgroup$ – Raphael Feb 23 '16 at 10:28
  • $\begingroup$ @Raphael an enumerator is possible, but testing the program's behaviour is not if some don't halt. $\endgroup$ – jmite Feb 23 '16 at 16:39
  • 1
    $\begingroup$ @jmite Also not necessarily true. We don't know anything about the language the OP has defined; it may very well have a decidable halting problem. (As per an edit, all programs halt. I don't know what the check is supposed to do then, but well.) $\endgroup$ – Raphael Feb 23 '16 at 19:55
1
$\begingroup$

I can give you a answer about the principles.

Find a computable bijection between your programs and the natural numbers. In essence, you would construct an admissible numbering. Then, you can just iterate over the naturals, compute the program corresponding to each number and perform your checks. You do not need to store any programs but the one under consideration.

The challenge is, of course, to find this bijection; it will depend on your language. If that helps you can relax injectivity; it is not necessary but duplicates will have performance impacts, obviously.

One concrete idea is: represent your language by a context-free grammar. Enumerate left-derivations along rule precedences, going from one program to the next using backtracking. It may even be possible to encode the derivation process in numbers, yielding a mapping as mentioned above.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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