Лекция RAISE Specification Language: базовые типы, логика, декартовы произведения, множества и операции с множествами. - презентация

1 Лекция RAISE Specification Language: базовые типы, логика, декартовы произведения, множества и операции с множествами

2 ВМиК МГУ, сентябрь-декабрь 2001 Формальные спецификации программ-I, Лекция 3. А.К.Петренко План лекции Описания Базовые типы Логика Декартовы произведения Множества. Свойства множеств Описание типов Литералы и агрегаты Операции с множествами Диаграмма Гогена Пример

3 ВМиК МГУ, сентябрь-декабрь 2001 Формальные спецификации программ-I, Лекция 3. А.К.Петренко Описания Типы(type) Значения(value) Переменные(variable) Каналы(channel) Схемы(scheme)

4 ВМиК МГУ, сентябрь-декабрь 2001 Формальные спецификации программ-I, Лекция 3. А.К.Петренко Описания типов type type_definition 1,... type_definition n Примеры type My_Nat = Nat, ST1 = T1-set Подтипы type limited_text = {|t : Text :- len t > 0|} Максимальные типы

5 ВМиК МГУ, сентябрь-декабрь 2001 Формальные спецификации программ-I, Лекция 3. А.К.Петренко Описания значений value value_definition 1,... value_definition n Описание констант value V : Nat = 10**N Описание функций Всюду вычислимые функции, тотальные (total) value f : Int -> Nat f (x) is if x>0 then 1 else 0 end Частично вычислимые функции, не тотальные value f : Real -~-> Real f (x) is 1 / x pre x ~= 0

6 ВМиК МГУ, сентябрь-декабрь 2001 Формальные спецификации программ-I, Лекция 3. А.К.Петренко Описания переменных variable variable_definition 1,... variable_definition n Пример variable v : Nat := 10**N, t : Real

7 ВМиК МГУ, сентябрь-декабрь 2001 Формальные спецификации программ-I, Лекция 3. А.К.Петренко Базовые типы Bool-- {true, false} Nat-- Int-- Real Char-- 'a', 'A',... Text-- "abc" -- Unit

8 ВМиК МГУ, сентябрь-декабрь 2001 Формальные спецификации программ-I, Лекция 3. А.К.Петренко Логика (1)

9 ВМиК МГУ, сентябрь-декабрь 2001 Формальные спецификации программ-I, Лекция 3. А.К.Петренко Логика (2)

10 ВМиК МГУ, сентябрь-декабрь 2001 Формальные спецификации программ-I, Лекция 3. А.К.Петренко Декартовы произведения Описание типа PT1 = T1 > < T3 PT2 = T1 > < T3) Литералы и агрегаты (1,2,3) (1,(2,3)) Операции = ~=

11 ВМиК МГУ, сентябрь-декабрь 2001 Формальные спецификации программ-I, Лекция 3. А.К.Петренко Множества. Свойства множеств каждый элемент встречается не более одного раза (не мультимножества) не определен порядок

12 ВМиК МГУ, сентябрь-декабрь 2001 Формальные спецификации программ-I, Лекция 3. А.К.Петренко Описание типов. Литералы и агрегаты Описание типов type ST1 = T1-set ST2 = {| s : ST1 :- (card s < maxset) |} NST1 = T1-infset Литералы и агрегаты {1,2,3} {} {x : Text :- x(1) = a}

13 ВМиК МГУ, сентябрь-декабрь 2001 Формальные спецификации программ-I, Лекция 3. А.К.Петренко Операции с множествами inter isin union << <<= >> >>= card

14 ВМиК МГУ, сентябрь-декабрь 2001 Формальные спецификации программ-I, Лекция 3. А.К.Петренко Диаграмма Гогена T Bool T-set Задание: Нарисуйте связи, которые задают операции над множествами между этими типами данных Nat

15 ВМиК МГУ, сентябрь-декабрь 2001 Формальные спецификации программ-I, Лекция 3. А.К.Петренко Пример: SET_DATABASE SET-DATABASE = class type Record = Key >< Data, Database = {( rs : Record-set is_wf_Database(rs) )}, Key, Data value is_wf_Database : Record-set -> Bool is_wf_Database(rs) is ( k : Key, d1,d2 : Data ((k,d1) d1 = d2), empty : Database is {}, insert : Key > Database insert(k,d,db) is remove(k,db) U {(k,d)}, remove : Key > Database remove(k,db) is db \ {(k,d) ) d : Data true}, defined : Key > Bool defined(k,db) is ( d : Data. (k.d) db), lookup : Key > Data lookup(k,db) as d post (k,d) db pre defined(k,db) end