Recursive Generators

Example

Let’s take a look at an example.

Let’s say we have a robot and want to give it directions. We might want to test things such as whether it can go through a room without hitting obstacles, whether it can cover all areas, and so on. But before we can test our bot, we’ll need to be able to create and plan an itinerary for it. Let’s say our robot works on a grid with coordinates and can go left, right, up, or down. A simple generator might look like this:

path() -> list(oneof([left, right, up, down])).

This would be fine if we wanted to eliminate things like “going left then right” or “going up then down” where moves cancel each other out. A ?LET() would probably work well. We’d just scan the list, and every time two opposite directions are taken, drop them from the list.

But what if we wanted to generate a path such that the robot never crosses a part of its path it has already covered? Doing so with a ?SUCHTHAT might not be super-efficient, and ?LET() would certainly be difficult to navigate. To solve this problem, we’d use recursion.

Tracking whether we’ve been somewhere before would require us to internally track coordinates with {X, Y} values. This is how it would work.

• Our robot always starts at {0,0}.
• Going left means subtracting 1 from the X value: {-1,0}.
• Going right means adding 1 to the X value: {+1,0}.
• Going up means adding 1 to the Y value: {0,+1}.
• Going down means subtracting 1 from the Y value: {0,-1}.

All we need to do then is track coordinates in a map; if a value exists in the map, we finish. Also, to put an upper bound on the path length, we’ll use a low-probability event of terminating right away. Let’s look at what our generators would look like:

path() ->
    % Current, Acc, VisitedMap        ToIgnore 
    path({0,0}, [], #{{0,0} => seen}, []).

path(_Current, Acc, _Seen, [_,_,_,_]) ->  %% all directions tried 
    Acc; % we give up

path(Current, Acc, Seen, Ignore) -> 
    frequency([
        {1, Acc}, % probabilistic stop
        {15, increase_path(Current, Acc, Seen, Ignore)} 
    ]).

So, this is an interesting bit of code. The first function is a wrapper, where path() calls out to a recursive path function. That function takes the current coordinate ({X, Y}), the current path it has built (up, down, left, etc.), the map of visited coordinates, and a list of directions to ignore. These directions are those that have been attempted recently and that resulted in a conflict. If the list contains all four of them, then we know there’s no way to go that won’t result in a repeated run, and so we’d just have to give up.

The second function clause uses frequency/1 to ensure that we stop once in a while. This will prevent a case where we’d just go forward forever and never finish generating data. In the vast majority of cases (with a 15-1 probability), we’ll try and lengthen the path. The function that lengthens the path is defined as follows:

increase_path(Current, Acc, Seen, Ignore) ->
    DirectionGen = oneof([left, right, up, down] -- Ignore), 
    ?LET(Direction, DirectionGen,
        begin 
            NewPos = move(Direction, Current), 
            case Seen of
                #{NewPos := _} -> % exists
                    path(Current, Acc, Seen, [Direction|Ignore]); % retry
                _ ->
                    path(NewPos, [Direction|Acc], Seen#{NewPos => seen}, [])
            end 
        end).

move(left, {X,Y}) -> {X-1,Y}; 
move(right, {X,Y}) -> {X+1,Y}; 
move(up, {X,Y}) -> {X,Y+1}; 
move(down, {X,Y}) -> {X,Y-1}.

Let’s break down the function first. The first thing we did was called oneof([left, right, up, down] -- Ignore). This generator tries to pick a random direction that has not been chosen yet. By default, this Ignore list is [], which means all directions are attempted. The tricky bit is that this call to oneof() returns a generator, not an actual value. PropEr will take care of changing the generator into a value.

If we want to use the value of that generator within the current generator, the ?LET() macro lets us do that. Remember that ?LET() chains up operations to be run once PropEr actualizes generators into data. So, writing the function as above lets us use the Direction result from the DirectionGen generator within the macro’s transformed expression.

Within that expression, we call move/2 on the current position to know the next one and look it up in the Seen map. If it is found there, it means that this direction crosses a path we’ve taken before, so we can retry while ignoring it. If the position has not been visited before, we’ll call path again with the new data.

If we try to run this generator in the shell, the generator might take a very long time to return. Not to mention, if we’re using generators that only probabilistically stop, it may never return. The more branches, the more costly the project becomes. This is because of the order of evaluation in Erlang. To evaluate frequency(), which is a regular function, its arguments need to be expanded. Since the arguments to frequency() include the generator itself, the generator must be called first, and the process loops deeper and deeper until memory runs out.

For those specific cases, PropEr provides a ?LAZY() macro, which allows us to defer the evaluation of an expression until it is required by the generator. Using this macro our generators should look like the following:

path(_Current, Acc, _Seen, [_,_,_,_]) -> %% all directions tried 
    Acc; % we give up

path(Current, Acc, Seen, Ignore) -> 
    frequency([
        {1, Acc}, % probabilistic stop
        {15, ?LAZY(increase_path(Current, Acc, Seen, Ignore))} 
    ]).

This macro allows us to defer the evaluation of its contents until they are needed, which means that we can now safely use it within alternative clauses. Now we can safely run the generator in our shell. To test the generators we will have to call the commands:

• proper_gen:pick(prop_generators:path()).
• proper_gen:sample(prop_generators:path()).

Let’s check out our generators in the code widget below: