c - 如何用 Hoare Triple 验证该功能？

Question

正如标题所说，我如何用霍尔三元组验证下面的功能？我阅读了有关它的各种讲座，但我不知道该怎么做。

int uguaglianza_insiemi(elem_lista_t *insieme_A,
                        elem_lista_t *insieme_B)
{
    int esito;  

    if ((insieme_A == NULL) && 
        (insieme_B == NULL))
        esito = 1;

    else if (insieme_A == NULL ||
            insieme_B == NULL)
            esito = 0;

    else if (insieme_A->valore != insieme_B->valore) 
            esito = 0;

    else esito = uguaglianza_insiemi(insieme_A->succ_p,
                                     insieme_B->succ_p);

    return (esito);
}

Answer 1

为了避免在评论中进行冗长的讨论，我将尝试编写一些前置条件和后置条件。

由于无法在函数内部测试是否使用指向有效列表对象的指针来调用它，因此它落在父/调用者身上:

// The following function must be called with pointers that are either null
// or point to valid list elements. The lists must be correct (no malloc bugs etc).
// The compiler must have checked that it is called with pointers to the proper types,
// as C has no typeof operator.
//
int uguaglianza_insiemi(elem_lista_t *insieme_A,
                        elem_lista_t *insieme_B)
{
    int esito;  

    if ((insieme_A == NULL) && 
        (insieme_B == NULL))
        esito = 1;    // both pointers are null: equal

    // not both pointes are null
    else if (insieme_A == NULL ||
            insieme_B == NULL)
            esito = 0;    // not both pointers are null, but one is: not equal

    // neither pointer is null and so they may be dereferenced
    else if (insieme_A->valore != insieme_B->valore) 
            esito = 0;    // neither pointer is null, but their element values aer not equal: not equal


    // the function can be called recursively now because its precondition has been met,
    // that both successor pointers are null or point to valid list elements (induction).
    else esito = uguaglianza_insiemi(insieme_A->succ_p,
                                     insieme_B->succ_p);
    // the post condition is that esito reflects equality of both (partial) lists                    
    return (esito);
}

我希望这是您和您的教授可以合作的东西。

---

{P}: The function must be called with pointers that are either null or point to valid list elements.

C: uguaglianza_insiemi( *A, *B)

{Q}: function result reflects equality of the lists

在函数内部，这继续使用组合规则的 if 语句。