Source: http://xfront.com/Alloy/3-ways-to-model-the-set-of-non-negative-even-numbers.html
Роџер Л. Костело /Roger L. Costello/
Вовед
Еве зошто мислам дека треба да го прочитате овој труд:
- Ви покажува Alloy и Alloy е навистина корисна. Ефикасно користен, Alloy може да ви помогне да создадете подобар, посигурен софтвер.
- Овој труд е краток и лесен за читање и ќе ви даде добро чувство за тоа што можете да направите со Alloy.
Еве ја лошата страна на овој труд: Она што се моделира – множеството на негативни парни броеви – не е интересно, ниту е типично за работите што вообичаено би ги моделирале со Alloy. Alloy обично се користи за моделирање на софтвер и/или системи.
И покрај лошите страни, сметам дека овој труд е доста корисен и вреди да се прочита.
Претпоставам дека сè уште читате, па да започнеме со преглед на она што ќе го видите во овој труд.
Овој труд прикажува 3 различни начини за моделирање на множеството на негативни парни броеви. Тоа покажува како можете да добиете повисоко ниво на уверување дека вашиот модел е точен со наведување и проверка на некои дефинирачки својства. На крај, тоа покажува како можете да проверите дали два различни модели се еквивалентни.
Изјава за проблем: Конкретно претставете (моделирајте) ја оваа инстанца: 0, 2, 4, …
Модел на список
Да почнеме едноставно. Наместо да моделирате бесконечна листа, ајде да ја моделираме оваа конечна листа: 0, 2, 4, 6.
Еве го моделот Alloy:
one sig List {
numbers: set Int
}{
numbers = 0 + 2 + 4 + 6
}
sig е резервиран збор. Тоа се залага за потпис. А декларација потпис дефинира множество. Во овој случај, декларацијата за потпис дефинира множество со име Список. Сетот има само еден член. Можете да го замислите списокот како објект (во објектно-ориентирана смисла). Објектот има едно поле наречено numbers. Его задржи посакуваниот список на вредности (0, 2, 4, 6). Вредноста на numbers е set на Int (цели броеви).
Сепак, не сакаме вредноста на numbers да содржи стара група на цели броеви. Ние сакаме да содржи само цели броеви 0, 2, 4, 6. Значи, дополнете ја декларацијата за потпис со факт на потпис што е во спротивност со множеството. (Фактот за потпис е работи во вториот пар на кадрави загради) Симболот плус ( + ) не значи додавање, тоа значи поставена унија. Во Alloy секоја вредност е множество, на пример, 0 е {0}, 1 е {1} и 0 + 1 е {0, 1}. Значи, вредноста на numbers е посакуваниот сет.
Модел на предикација
Записот на списокот може да се користи само за моделирање на конечни множества. Предативната нотација може да се користи за моделирање на бесконечни множества.
Пристапот што го зема нотацијата на предикатот е да претставува множество со специфицирање на својствата што мора да ги има секој член на множеството. Во нашиот случај, секој цел број во множеството мора да ги има овие две својства:
- Целиот број мора да биде рамномерен.
- Целиот број мора да биде негативен.
Овие се нарекуваат „дефинирачки својства“.
Еве го моделот Alloy:
one sig List {
numbers: set Int
}{
numbers = {i: Int | i >= 0 and (rem[i,2] = 0)}
}
Фактот за потпис користи разбирање на множества за да ја одреди вредноста на numbers: Множеството од целиот интеграл i, така што i е поголем или еднаков на 0, а остатокот од делењето на i со 2 е 0.
Модел на генератор
Да претпоставиме дека постои модел на бројна линија во која секој цел број i е поврзан со i+2
Потоа, посакуваниот сет на цели броеви може да се моделира како: Синџирот на цели броеви, почнувајќи од 0.
Подобро е да се моделира бројната линија како низа каде што секој цел број i има i.next и i.prev отколку i+1 и i-1. Еве зошто: Бидејќи компјутерите се конечни, инстанците се исто така конечни. Инстанците моделирани со додавање на 2 на секој цел број, на крајот ќе пропаднат со аритметичко прелевање или со додавање што кружи околу негативните вредности. Значи, наместо инстанцата да го поврзе i со i+2, инстанцата го поврзува i со цел број што е оддалечен два чекори од низата: i.next.next
Еве го моделот Alloy:
one sig NumberLine {
connections: Int -> Int
} {
all i: Int | connections[i] = i.next.next
}
Декларацијата за потпис ја дефинира NumberLine, која има поле наречено врски. Вредноста на врските е збир на (int, int) парови. Операторот на стрелката (->) значи „сите можни комбинации на множеството лево од стрелката со множеството десно од стрелата“. Можеби ќе се сетите од часот по математика во средно училиште дека ова се нарекува картезиски производ.
Сепак, не сакаме вредноста на врските да биде сите можни (int, int) парови. Ние сакаме само (i, i.next.next) парови. Фактот за потпис ги ограничува паровите: За целиот цел број, вредноста на i’th врската е i.next.next
Сега, кога бројната линија е дефинирана, подготвени сме да ја моделираме посакуваната листа. Вредноста на numbers е ланецот кој започнува од 0.
one sig List {
numbers: set Int
} {
numbers = 0.*(NumberLine.connections)
}
Операторот на рефлексивно транзитивно затворање (*) значи „во збир на парови, каде и да има пар (A, B) и пар (B, C), потоа додадете ги овие парови: (A, A) и (A, C)”. Со други зборови, создадете парови за сите вредности што А може да ги достигне, вклучително и за себе. За нашиот случај, множеството парови содржи (0, 2) и (2, 4), така што операторот * ќе ги додаде овие парови: (0, 0) и (0, 4).
0.*(NumberLine.connections) значи “сите цели броеви до кои може да се стигне од 0”, што е: 0, 2, 4, 6, …
За да се подигне нивото на доверба дека овој модел генерира инстанца со посакуваната листа на цели броеви, можеме да провериме дека секој цел број во броеви ги има двете дефинирачки својства што ги видовме порано:
- Дури и својство: секој цел број мора да биде рамномерен.
- Не-негативно својство: секој цел број мора да биде негативен.
Alloy тврдат се користи за проверка модел. Следното тврди дека проверува дали секој цел број во numbers ги има двете дефинирачки својства:
assert only_positive_even_numbers {
all i: List.numbers | i >= 0 and rem[i, 2] = 0
}
Прочитајте како: За сите броеви i во List.numbers, јас мора да бидат поголеми или еднакви на 0, а остатокот од делењето i со 2 мора да биде нула.
Кога од Анализаторот на Alloy е побарано да го провери тврдењето, тој одговара со: “Не е пронајден против-пример.” Со други зборови, анализаторот на Alloy не е во состојба да најде член на броеви што не е негативно и/или не е рамномерно.
Еквивалентност на моделите на предика и генератор
Моделот на предикатот концизно ја претставува (моделира) листата: 0, 2, 4, 6, … Моделот на генераторот исто така концизно ја претставува (моделира) листата: 0, 2, 4, 6,… Ние би сакале да покажеме дека двата модели се еквивалентни; односно и двајцата ја претставуваат (моделираат) истата инстанца.
Подолу се дадени двата модели и тврдење кое ја тестира нивната еквивалентност. Забележете дека фактот за потпис за потписот на Списокот го нема. Наместо тоа, има два pred (предикати). Пред името Predicate, кога се повикува, ги ограничува броевите со користење на множество разбирање. Пред именуваниот Генератор, кога се повикува, ги ограничува numbers во ланецот на цели броеви во NumberLine, почнувајќи од 0. Исто така, забележете дека во секој pred полето за numbers е експлицитно квалификувано со „List“ да се означи дека броевите се поле во списокот. Претходно, кога се користи факт за потпис, „Списокот“. беше имплицитно. На дното е тврдење. Го вели ова: Ако инстанцата ги задоволува ограничувањата наведени во Предикатот, тогаш инстанцата ќе ги задоволи и ограничувањата наведени во Генераторот и обратно. Со други зборови, инстанцата претставена од Predicate е истата инстанца претставена од Generator. Кога од Анализаторот на Alloy се бара да го провери тврдењето, тој одговара со: „Не е пронајден контра-пример“. Со други зборови, моделот Predicate и моделот Generator се еквивалентни. Многу кул.
Еве го моделот Alloy:
one sig NumberLine {
connections: Int -> Int
} {
all i: Int | i.connections = i.next.next
}
one sig List {
numbers: set Int
}
pred Predicate {
List.numbers = {i: Int | i >= 0 and (rem[i,2] = 0)}
}
pred Generator {
List.numbers = 0.*(NumberLine.connections)
}
assert Equivalent {
Predicate iff Generator
}
Роџер Л. Костело. 5 јули 2018 година