Сравнение элементов Alloy Analyzer из набора

Немного предыстории: мой проект состоит в том, чтобы сделать компилятор, который компилирует C-подобный язык в Alloy. Язык ввода, имеющий синтаксис, подобный Си, должен поддерживать контракты. На данный момент я пытаюсь реализовать операторы if, которые поддерживают операторы pre и post условие, подобные следующим:

int x=2
if_preCondition(x>0)
if(x == 2){
   x = x + 1
}
if_postCondtion(x>0)

Проблема в том, что я немного запутался с результатами Alloy.

sig  Number{
    arg1: Int,
}

fun addOneConditional (x : Int) : Number{
    { v : Number | 
            v.arg1 = ((x = 2 ) => x.add[1] else x)
    }
}

assert conditionalSome {
    all n: Number|  (n.arg1 = 2 ) => (some field: addOneConditional[n.arg1] | { field.arg1 = n.arg1.add[1] }) 
}

assert conditionalAll {
    all n: Number|  (n.arg1 = 2 ) => (all field: addOneConditional[n.arg1] | { field.arg1 = n.arg1.add[1] }) 
}

check conditionalSome
check conditionalAll

В приведенном выше примере conditionalAll не генерирует Counterexample. Однако conditionalSomeгенерирует Counterexamples. Если я правильно понимаю квантификаторы all и some, то это ошибка. Поскольку из математической логики мы имеем Ɐx expr(x) => ∃x expr(x) ( т. е. Если выражение expr(x) истинно для всех значений x, то существует единственный x, для которого выражение expr(x) истинно)


person Koko Nanahji    schedule 18.03.2020    source источник
comment
Я потерял то, что вы пытаетесь сделать здесь, даже после редактирования вашей проблемы, потому что ее было трудно читать без какого-либо форматирования. Не могли бы вы свести проблему к минимуму? т.е. у вас есть проблемы, это помогает свести к абсолютному мин. Один совет, не используйте Int. Есть некоторые существенные недостатки с Ints, которых вы хотите избежать при изучении сплава. Попробуйте создать небольшую проблему, которая показывает вашу проблему, не возвращаясь к Int.   -  person Peter Kriens    schedule 19.03.2020
comment
Чем вы за ваше время. Я отредактировал вопрос, надеюсь, он стал лучше.   -  person Koko Nanahji    schedule 20.03.2020


Ответы (1)


Во-первых, вам нужно смоделировать свои операции до, после и. Функции ужасны для этого, потому что они не могут не возвращать что-то, что указывает на сбой. Поэтому вам необходимо смоделировать операцию как предикат. Значение предиката указывает, выполняются ли условия pre/post, аргументы и возвращаемые значения могут быть смоделированы как параметры.

Насколько я понимаю вашу операцию:

pred add[ x : Int, x' : Int ] {
  x > 0             -- pre condition
  x = 2 => 
    x'=x.plus[1] 
  else 
    x'=x
  x' > 0            -- post condition
}

В Alloy нет переменных для записи (в отличие от Electrum), поэтому вам нужно смоделировать состояние до и после с помощью символа штрих (').

Теперь мы можем использовать этот предикат для расчета набора решений вашей проблемы:

fun solutions : set Int {
  { x' : Int | some x : Int | add[ x,x' ] }
}

Мы создаем набор с целыми числами, для которых у нас есть результат. Главный символ не представляет собой ничего особенного в Alloy, это всего лишь условность для пост-состояния. Я немного злоупотребляю этим.

Этого источника Alloy более чем достаточно, чтобы делать ошибки, так что давайте проверим это.

run { some solutions }

Если вы запустите это, вы увидите в представлении Txt:

skolem $solutions={1, 3, 4, 5, 6, 7}

Это ожидаемо. Операция add работает только для положительных чисел. Проверить. Если вход равен 2, результат равен 3. Следовательно, 2 никогда не может быть решением. Проверить.

Признаюсь, меня немного смущает то, что вы делаете в своих утверждениях. Я пытался воспроизвести их точно, хотя я удалил ненужные вещи, по крайней мере, я думаю, что мы не нужны. Сначала ваше дело some. Ваш код выполнял all, но затем выбирал 2. Поэтому удалил внешнюю количественную оценку и жестко закодировал 2.

check  somen {
    some x' : solutions | 2.plus[1] = x'
}

Это действительно не дает нам никакого контрпримера. Так как solutions было {1, 3, 4, 5, 6, 7}, то в наборе 2+1=3, т.е. условие some выполнено.

check  alln {
    all x' : solutions  | 2.plus[1] = x'
}

Однако не все решения имеют 3 в качестве ответа. Если вы проверите это, я получу следующий контрпример:

skolem $alln_x'={7}
skolem $solutions={1, 3, 4, 5, 6, 7}

Заключение. Дэниел Джексон советует не учить Alloy с Ints. Глядя на свой класс Number, вы поняли его буквально: вы по-прежнему основываете свою проблему на Ints. Он имел в виду не использовать Int, не прятать их под ковер в поле. Я понимаю, откуда взялся Даниэль, но Ints очень привлекательны, поскольку мы так хорошо с ними знакомы. Однако, если вы используете Ints, позвольте им хотя бы использовать всю свою славу и не прячьте их.

Надеюсь это поможет.

И вся модель:

pred add[ x : Int, x' : Int ] {
    x > 0               -- pre condition
    x = 2 => 
        x'=x.plus[1] 
    else 
        x'=x
    x' > 0              -- post condition
}   
fun solutions : set Int { { x' : Int | some x : Int | add[ x,x' ] } }

run { some solutions }
check  somen { some x' : solutions | x' = 3 }   
check  alln { all x' : solutions  | x' = 3 }
person Peter Kriens    schedule 20.03.2020
comment
Спасибо за ваше время и подробное объяснение. У меня есть дополнительный вопрос. Я хотел бы создать утверждение, которое проверяет, что pred add (т.е. переведенный оператор if) выполняется (истинно) для всех возможных значений int x (конечно, домен x ограничен). Это означает, что он проверяет, что если выполняется предварительное условие оператора if, то выполняется и последующее условие оператора if. Будет ли работать следующее утверждение? check postCondition{ { all x : Int | some x' : Int | (x>0) => add[ x,x' ] } } - person Koko Nanahji; 21.03.2020
comment
Вы пробовали? - person Peter Kriens; 21.03.2020
comment
да. Я попробовал несколько тестовых случаев, и, похоже, он делает то, что я ожидал. Я просто хотел убедиться, что я не ошибаюсь, учитывая, что я новичок в мире проверки программного обеспечения и Alloy. - person Koko Nanahji; 22.03.2020