> How are you accounting for this; trying every possible program length?

Part of the mutation function involves probabilistically growing and shrinking the program size (i.e., inserting and removing random instructions).

> And you are considering the simpler case where the search space is discrete, unlike the continuous spaces in most machine learning problems.

All "continuous spaces" that embody modern machine learning techniques are ultimately discrete.

No, they are not. Model outputs can be discretized but the model parameters (excluding hyperparameters) are typically continuous. That's why we can use gradient descent.