Error en Dafny “llamada puede violar la cláusula ‘modifies’ del contexto” al utilizar una invocación de método dentro de un bucle while donde el invariante “fresh” no es una opción.

18 Jun, 2023 Programación 0

A continuación se presenta una versión simplificada (y, por lo tanto, inútil) de una clase Cola construida con listas vinculadas. Hay un método Añadir que agrega otro nodo de lista vinculado (fresco) al final de la cola. Si escribo otro método que toma una q: Cola como argumento, y ejecuto q.Añadir repetidamente en un bucle while, obtengo un error de “la llamada puede violar la cláusula de modificaciones de contexto” que no puedo resolver usando una invariante fresco, porque q puede tener nodos ya asignados. ¿Hay alguna forma de manejar esta situación?

“`
class LL { /* nodos de lista vinculada <em>/
var elem: int;
var next: LL?; /</em> puede ser nulo */

constructor (x: int)
ensures elem == x && next == null
{
elem, next := x, null;
}
}

class Cola { // versión simplificada de colas de enteros
var hd: LL; // implementado utilizando lista vinculada
var tl: LL;

ghost var nodes: seq<ll>; // nodos de lista vinculada

predicate invar() // invariante de clase (ignora el elemento)
reads this, nodes
{
nodes != [] && nodes[0] == hd && nodes[|nodes| – 1] == tl &&
nodes[|nodes| – 1].next == null &&
(forall i: nat {:trigger nodes[i].next} ::
i < |nodes| – 1 ==> nodes[i].next == nodes[i + 1])
}

constructor () // empezamos con un nodo
ensures invar() && |nodes| == 1 && fresh(nodes)
{
var l: LL := new LL(0);
hd, tl := l, l;
nodes := [l];
}

method Añadir(d: int) // agrega otro nodo
requires invar()
ensures invar()
ensures
nodes != [] && nodes[.. |nodes| – 1] == old(nodes) &&
fresh(nodes[|nodes| – 1])
modifies this, nodes
{
var l: LL := new LL(d);
tl.next := l;
tl := l;
nodes := nodes + [l];
}

method Foo(q: Cola)
// si asumimos esto:
// requires q.nodes == []
// pero queremos que q ya pueda tener algunos nodos, a los que añadiremos
requires q.invar()
modifies q, q.nodes
{
var i: nat := 0;
while (i < 10)
invariant i <= 10
invariant q.invar()
// entonces agregar esta invariante fresca funciona:
// invariant fresh(q.nodes)
decreases 10 – i
{
q.Añadir(i); // error: "la llamada puede violar la cláusula de modificaciones de contexto"
i := i + 1;
}
}
}“`

davy.ai

June 18, 2023 at 6:24 am

El problema surge porque el método Add modifica la referencia this y el campo nodes, y no se permite modificar un campo de un objeto que pueda tener nodos asignados.

Una solución potencial podría ser introducir un nuevo método en la clase Queue que agregue un nodo nuevo a una cola que ya tenga nodos asignados. Este método se encargaría de crear un nodo nuevo, actualizar los enlaces entre nodos y agregar el nodo nuevo a la secuencia nodes.

Entonces, en el método Foo, podemos verificar primero si la secuencia nodes está vacía o no. Si está vacía, simplemente podemos llamar al método Add como antes. Sin embargo, si la secuencia no está vacía, podemos llamar al nuevo método que agrega un nodo nuevo a la cola.

De esta manera, aseguramos que no violamos la cláusula “modifies” del contexto actual porque no estamos modificando directamente los nodos que puedan estar asignados.

Implementación de ejemplo del nuevo método:

método AddFreshNode()
    requiere invar()
    garantiza invar()
    garantiza |nodes| == old(|nodes|) + 1
    modifica this, nodes
{
    var l: LL := new LL(0);
    tl.next := l;
    tl := l;
    nodes := nodes + [l];
}

Implementación actualizada del método Foo:

método Foo(q: Queue)
    requiere q.invar()
    modifica q, q.nodes
{
    var i: nat := 0;
    si (q.nodes == []) {
        mientras (i < 10)
            invariante i <= 10
            invariante q.invar()
            invariante fresh(q.nodes)
            disminuye 10 - i
        {
            q.Add(i);
            i := i + 1;
        }
    } else {
        mientras (i < 10)
            invariante i <= 10
            invariante q.invar()
            invariante q.nodes != []
            disminuye 10 - i
        {
            q.AddFreshNode();
            i := i + 1;
        }
    }
}

Answer

davy.ai

June 18, 2023 at 6:24 am
El problema surge porque el método Add modifica la referencia this y el campo nodes, y no se permite modificar un campo de un objeto que pueda tener nodos asignados.

Una solución potencial podría ser introducir un nuevo método en la clase Queue que agregue un nodo nuevo a una cola que ya tenga nodos asignados. Este método se encargaría de crear un nodo nuevo, actualizar los enlaces entre nodos y agregar el nodo nuevo a la secuencia nodes.

Entonces, en el método Foo, podemos verificar primero si la secuencia nodes está vacía o no. Si está vacía, simplemente podemos llamar al método Add como antes. Sin embargo, si la secuencia no está vacía, podemos llamar al nuevo método que agrega un nodo nuevo a la cola.

De esta manera, aseguramos que no violamos la cláusula “modifies” del contexto actual porque no estamos modificando directamente los nodos que puedan estar asignados.

Implementación de ejemplo del nuevo método:
```
método AddFreshNode()
    requiere invar()
    garantiza invar()
    garantiza |nodes| == old(|nodes|) + 1
    modifica this, nodes
{
    var l: LL := new LL(0);
    tl.next := l;
    tl := l;
    nodes := nodes + [l];
}
```
Implementación actualizada del método Foo:
```
método Foo(q: Queue)
    requiere q.invar()
    modifica q, q.nodes
{
    var i: nat := 0;
    si (q.nodes == []) {
        mientras (i < 10)
            invariante i <= 10
            invariante q.invar()
            invariante fresh(q.nodes)
            disminuye 10 - i
        {
            q.Add(i);
            i := i + 1;
        }
    } else {
        mientras (i < 10)
            invariante i <= 10
            invariante q.invar()
            invariante q.nodes != []
            disminuye 10 - i
        {
            q.AddFreshNode();
            i := i + 1;
        }
    }
}
```

Comments are closed.

es.davy.ai

¿Tienes una pregunta?

Error en Dafny “llamada puede violar la cláusula ‘modifies’ del contexto” al utilizar una invocación de método dentro de un bucle while donde el invariante “fresh” no es una opción.

Answer

davy.ai