Searching through all program of a stack-based language with little memory 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 --&gt; test it
 else --&gt; 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:


Observe that, for certain program fragments, nothing that can be appended to them will make them valid
Define an ordering over each token that may appear in a program.
Define a "mayBeAppendedToToMakeAValidProgram" over a incomplete program.
For n = 0 to infinity:
Start with a program of n tokens; set each token to the first
Increment token-0 until mayBeAppendedToToMakeAValidProgram(token-0)
Increment token-1 until mayBeAppendedToToMakeAValidProgram(token-0 + token-1)
Etc. until the last token
Increment the last token until the program is valid; test that program
On to the next one
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.