Specification-Based Testing and Debugging

Dear seminar participants,

Stanimir discovered another problem in the current assignment. In the function "test_tiny_c_interpreter_with_wrong_dict," the "wrong_dict" was initialized only once. However, every call to "interpret_tiny_c" changes the dictionary, resulting in the interpreter being called with a potentially different dictionary every time. A correct implementation of the function looks like this:

def test_tiny_c_interpreter_with_wrong_dict():
    """
    This function tests the Tiny-C interpreter with the metamorphic
    oracle provided by `get_transformation_pair`. It completes normally
    in the case of success and raises an `AssertionError` otherwise.

    This version of `test_tiny_c_interpreter_with_wrong_dict` passes
    a non-trivial initial dictionary to the interpreter to test the
    error-finding capabilities of the metamorphic tester.

    :return: Nothing.
    """

    wrong_dict = tuple({var: 1 for var in string.ascii_lowercase}.items())

    for _ in range(20):
        generator = generate_transformation_pair(
            DEAD_CODE_INSERTION_GRAMMAR_2, TINY_C_GRAMMAR, constraint
        )

        for pair in itertools.islice(generator, 5):
            left = str(pair.filter(lambda node: node.value == "<left>")[0][1])
            right = str(pair.filter(lambda node: node.value == "<right>")[0][1])

            result_left = interpret_tiny_c(left, dict(wrong_dict), gas=20)
            result_right = interpret_tiny_c(right, dict(wrong_dict), gas=20)

            assert result_left == result_right

Mutable data structures are a constant source of trouble in programming. For this reason, I mostly work with immutable types in my research prototypes. Unfortunately, I was not that disciplined when implementing the current assignment.

This could be a nice lesson to be learned. However, you were affected by this problem and might have lost time when trying to work around it. For this, I am very sorry. We will consider this context when grading this part of the assignment.

All the best,
Dominic

Dear seminar participants,

Justin (thanks!) pointed out that the final assertion/check in the "Metamorphic Testing" lab is wrong; it does not call the function `test_tiny_c_interpreter_with_wrong_dict`, but the original `test_tiny_c_interpreter`. Please correct these yourselves.

However, I found a bug at this second call to `test_tiny_c_interpreter`, which is why I missed that problem. The root cause of this bug is the ambiguity of the Tiny-C grammar. For example, the program

{a = 17;if(0) if(1) ; else a = 42;}

has two parses: One equivalent to

{a = 17;if(0) {if(1) ; else a = 42;}}

which is the intended one, and one equivalent to

{a = 17;if(0) {if(1) ;} else a = 42;}

which is the first result returned by the EarleyParser. This latter alternative is not "dead code" and can alter the semantics.

This is an excellent lesson on language ambiguity and the problems one may face when dealing with "grammarware." To solve this, we could resolve the ambiguity in the grammar, replace the grammar-based parser altogether, or adapt the grammar to work with ISLa's "packrat parser." This parser is currently not used since, for the current grammar, packrat runs into an infinite recursion problem.

Long story short:

1. Please change the mentioned function call, and don't be surprised if the original call occasionally also finds an error :)
2. The test routines we're building here, even these simple ones, WORK!
3. Thanks, Justin! For the others: Keep reporting suspicious stuff ;)

Best,
Dominic

Dear seminar participants,

I just updated the solution for the lab on "Oracles." The previous "solution" did not contain solutions; I apologize.

The speakers for our upcoming Delta Debugging/Input Reduction session will be Justin, Moritz, and Sasha. This implicitly defines the three speakers for our final regular seminar session.

Best,
Dominic

bexps_strategy: st.SearchStrategy = st.recursive(
    # The non-recursive base cases.
    st.builds(BTrue) |… Read more

Dear all,

I wanted to share an alternative solution strategy proposed by Stanimir (thanks!) for the arithmetic expressions example in Lab 06.

My proposed solution was

bexps_strategy: st.SearchStrategy = st.recursive(
    # The non-recursive base cases.
    st.builds(BTrue) | st.builds(BFalse) | st.builds(BVar, st.text()),
    # The recursive cases.
    lambda children: (
        st.builds(BNot, children)
        | st.builds(BAnd, children, children)
        | st.builds(BOr, children, children)
    )
)

This approach is inspired by a JSON example using standard Python datatypes such as dicts. In that case, the powerful "builds" strategy cannot work since obtaining information about the intended structure from the ADT definitions is impossible.

I used "recursive" since "build" failed when applied to the abstract "BExp" dataclass. Yet, Stanimir found out that you can join the "builds" for all the cases:

alternative_bexps_strategy: st.SearchStrategy = st.builds(BTrue) | st.builds(BFalse) | st.builds(BVar) | st.builds(BNot) | st.builds(BAnd) | st.builds(BOr)

This more straightforward solution approach should be preferred in practice (for maintainability reasons etc.).

You may also find this helpful. I recommend using Hypothesis where appropriate if you're developing in Python!

Best,
Dominic

Dear all,

Due to conflicting appointments, I have to move our next seminar meeting. We will not meet on Monday, but instead on Wednesday. June 14, 17:00 at the same Zoom link. If you cannot make it on this date, please drop me a note.

Manuel and Mohamad are the designated presenters of the next paper.

Note that the assignment dates stay as they are, so your current assignment will be due on Monday, and the next assignment will also be published on Monday again.

Looking forward to seeing you next Wednesday -- Andreas Zeller