How to make grammar recursive

[Harjas12]

HI PROSE Team! My group and I are using PROSE for a synthesis project for image transformations. We are running into an issue where we can't make the grammar work recursively. We initially started to generate programs using this DSL:

@input Image input_image;

@start Image program := single;

Image single := FilterColor(input_image, color)
             | Recolor(input_image, color);

int color;

This works as expected and we are able to synthesize correct programs. However, the obvious limitation is that the grammar doesn't allow recursive operations, so we can only synthesize very simple programs. We then modified the grammar to be in the format:

@input Image input_image;

@start Image program := single;

Image single := FilterColor(single, color)
             | Recolor(single, color)
             | input_image;
	

int color;

However, with the same input / output test cases we weren't able to synthesize any program. From what I have been able to tell by googling around a bit is that we need another witness function for the 'single 'arguments for each of these grammar rules, however, I am not sure what those witness functions are meant to do. It was very clear what the witness functions for the color argument for the operators should be. Our repo is available here: https://github.com/RyanLuu/ArChEs/tree/recursive/demo/arches_v1/synthesis

Any help or suggestions on how to get our grammar working recursively would be greatly appreciated!

[danpere]

The issue you're having is unrelated to the grammar being recursive: as you observe, it's that you need witness functions for every parameter. In your initial grammar, it wasn't relevant because there's only one program for the AST input_image (or any AST which is just a variable reference with no other options), so PROSE just lets you omit the witness function in that case.

To better understand what's going on, the semantics of the witness function is, given a Spec, how should PROSE compute the Spec to use for learning the specified argument. Given a concrete program, a Spec can be verified (e.g., for an ExampleSpec just run the program on the given input and check if the output equals the given output). But otherwise, PROSE needs a Spec to recursively learn a ProgramSet (version space algebra over ASTs) for.

In your case, if you're learning, say, a FilterColor program, you can find the color from the output image. But the valid input images would be any image where the pixels of that color match. As there are a lot of possible images for which that is true, you will likely want to define your own Spec type (PartialImageExampleSpec? or DisjunctivePartialImageExamplesSpec?) to abstract over them whose semantics would probably be for each input, the specified pixels will have the specified values but the unspecified pixels may have any value (or maybe any value except some list of colors to clarify that those must be filtered out?). These kinds of domain-specific partial example specs are common in our DSLs (we define some somewhat generic ones like subsequence and prefix sequence, for example).

(I'm a little confused by the semantics of making your grammar recursive. Since FilterColor/Recolor allow only a single color in an image, I don't see how any program applying them more than once could be an interesting program. I assume you intend to add a "combine" operator of some kind?)

[Harjas12]

Thank you for the prompt response!

I am still a little confused on how to go about the Specs. So should the witness function for the recursive argument in the operators return a spec that models all possible images inputs for that function. And if so wouldn't that set of possible image inputs be dependent on what color you are tying to filter out. Lastly, is there any documentation or examples on how to write your Spec?

To address why we want the grammar to be recursive is so that we can solve problem like:

1 0 2             0 0 0
3 4 1      ->     0 5 0
5 4 2             0 5 0

The program that we would want to generate that could solve this would be Recolor(FilterColor(input_image, 4), 5). The reason for the confusion is probably related to the fact that we treat 0 as a special color in our semantics. We want FilterColor to take all pixels not equivalent to the filter color and set it to 0. And we want Recolor to take all pixels, expect pixels with color 0, and set them to the passed in color value.

[danpere]

A witness function is a function from the Spec on the output to a Spec on a parameter. There's a DependsOn option that can be used to make the witness function also get an ExampleSpec for concrete values for the requested other parameters, so you could use that to know what color is being filtered/recolored. Using DependsOn means it will need to learn that entire branch of the AST in order to compute the concrete values that AST could evaluate to.

Sorry, I don't think we have any example code of defining your own Spec. This isn't the first time it's come up; we apologize for our samples/documentation being limited.

Okay, I see that Recolor(FilterColor()) is a sensible program, but any deeper than that isn't. And Recolor without a filter doesn't seem to make sense, so you could specify that structure in your grammar if that's what you want to allow.

[Harjas12]

I took your advice and wrote a PartialImageSpec over here: https://github.com/RyanLuu/ArChEs/tree/main/demo2/arches_v1. They way that the spec works is that I am still using a 2d int array to represent the image. However, I have some special color values. 0-9 are my normal predetermined colors, 10 means any color except 0, and -x means any color except x. I was able to get my code running by only implementing 2 of the functions of the spec.

        protected override bool CorrectOnProvided(State state, object output)
        {
			var space = (examples[state] as List<int[][]>)[0];
			var candidate = output as int[][];
			for (int i = 0; i < space.Length; i++) {
				for (int j = 0; j < space[0].Length; j++) {
					if (space[i][j] == 10) {
						if (candidate[i][j] == 0) return false;
					} else if (space[i][j] < 0) {
						if (candidate[i][j] == -space[i][j]) return false;
					} else {
						if (space[i][j] != candidate[i][j]) return false;
					}
				}
			}
			return true;
        }

         protected override Spec TransformInputs(Func<State, State> transformer)
        {
			var result = new Dictionary<State, IEnumerable<object>>();
			foreach (var input in examples.Keys) {
				result[transformer(input)] = examples[input];
			}
			return new PartialImageSpec(result);
        }

With these changes I made my grammar recursive again:

@input int[][] image;

@start int[][] program := single;

int[][] single := Recolor(@recurse[5] single, color)
				  | Filter(@recurse[5] single, color)
				  | image;

int color;

And I was able to synthesize simple Recolor(image, color) and Filter(image, color) programs. This is an improvement from before, because before my synthesizer would not work at all if I had written it recursively. However, I am still not able to synthesize Recolor(Filter(...)). I was hoping you could take a look and see if there is something obvious that I am missing. I would assume that my mistake is either in the PartialImageSpec or my witness functions.

Another thing I noticed was that the function pointer sent to TransformInputs doesn't seem to do anything to the arguments. I can't tell if thats intended or not.

[Harjas12]

We were able to solve our issues. We were making an error where one of your Witness functions wasn't accepting our custom partial image spec as a parameter, this resulted in the search ending earlier than it should have. After correcting that witness function we were able to start synthesizing interesting programs!