Е.А. Кузьменкова, А.К. Петренко - практикум на языке RSL (Е.А. Кузьменкова, А.К. Петренко - практикум на языке RSL.pdf), страница 5

Конечныйсписок из последовательных целых чисел можно задать, указав диапазонизменения значений элементов списка, т.е. выражением вида <.v1..v2.>, где v1 иv2 задают соответственно нижнюю и верхнюю границы диапазона, причем приv1 > v2 список пуст.Использование такого способа записи иллюстрируют следующие примеры:<.3..7.> =<.3, 4, 5, 6, 7.><.3..3.> = <.3.><.3..2.> = <..>24Значение списка можно задать также по аналогии с множествами и с помощьютак называемого сокращенного выражения (comprehended list expression),имеющего вид <.

value_expr | list_limitation .>. Этот способ применяется в томслучае, когда новый список строится на основе какого-то уже существующего.Здесь value_expr определяет общую формулу для вычисления значенийэлементов нового списка, list_limitation задает базовый список, на основекоторого строится данный, с возможным указанием некоторого предиката дляотбора элементов из базового списка.Например, в выражении:<.2∗n | n in <.0 .. 3.>.>базовымявляетсясписок <.0 .. 3.>, предикатотбораотсутствуети,следовательно, в результате вычисления получается список  <.0,2,4,6.>, причемупорядоченность элементов нового списка полностью определяется порядкомследования элементов в базовом списке. Примером использования предиката дляотбора элементов базового списка может служить выражение:<.n | n in <.1 ..

100.> :- is_a_prime(n).>,где предикат is_a_prime(n) позволяет определить, является ли n простым числом.С помощью данного выражения задается список, элементами которого являютсявсе простые числа из диапазона 1 .. 100 в возрастающем порядке, т.е. <.2,3,5,7,...,97.>.Для доступа к какому-либо конкретному элементу списка в RSLпредусмотрено понятие индекса. В качестве индекса используются натуральныечисла, причем индексация элементов списка начинается с 1 и для конечныхсписков заканчивается числом, равным длине списка. Например:<.2,5,3.> (2) = 5<.<.2,5,3.>, <.3.>.> (1) = <.2,5,3.><.<.2,5,3.>, <.3.> .> (1)(2) = <.2,5,3.> (2) = 5В случае отсутствия в списке элемента с указаннымсоответствующее выражение принимает значение chaos.

Например:индексом<.1 .. 50.> (51) = chaosЗначение бесконечного списка может быть задано с помощью аксиом,определяющих правила формирования списка. Так, список, содержащий всенатуральные числа в возрастающем порядке, может быть определен в видеконстанты all_natural_numbers следующим образом:valueall_natural_numbers : Nat-inflistaxiomall_natural_numbers(1) = 0,exists idx : Nat :idx >= 2 =>all_natural_numbers(idx) = all_natural_numbers(idx −1) + 1На основе уже определенного бесконечного списка с помощью сокращенноговыражения можно задавать новые бесконечные списки. Например, список,25элементами которого являются все простые числа в возрастающем порядке, можетбыть определен посредством выражения:<.n | n in all_natural_numbers :- is_a_prime(n).>Операции над спискамиНад списками в RSL определены следующие операции:^ : T-list >< T-inflist -> T-inflisthd : T-inflist -∼-> Ttl : T-inflist -∼-> T-inflistlen : T-inflist -∼-> Natelems : T-inflist -> T-infsetinds : T-inflist -> Nat-infsetКроме того к спискам, как и к любому типу в RSL, применимы операции = и~=.Операция ^ означает конкатенацию двух списков, первый из которыхобязательно должен быть конечным.Результатом применения операций hd и tl являются соответственноголовной элемент списка и «хвост» списка - оставшаяся после удаления головногоэлемента часть списка, причем обе эти операции определены только для непустогосписка.

Для любого непустого списка L верно соотношение:hd L is L(1)Операция len возвращает длину конечного списка (для пустого спискавозвращается 0), при применении к бесконечному списку результатом является chaos.Операция elems выдает в качестве результата множество, состоящее изэлементов заданного списка. Например:elems <..> = {}elems <.1,3,1.> = {1, 3}elems all_natural_numbers = {n | n : Nat}Количество различных элементов списка L можно определить с помощьювыражения card elems L.Результатом применения операции  inds является множество индексовзаданного списка.

Например:inds <..> = {}inds <.1,3,1.> = {1, 2, 3}Таким образом, для конечного списка FL:inds FL = {1 .. len FL},для бесконечного списка IL:inds IL = {idx | idx : Nat :- idx >= 1}.26Для произвольного списка L верно соотношение:elems L is {L(x) | x : Nat :- x isin inds L}Встроенный тип Text представляет собой конечный список из элементов типаChar, т.е. Text = Char-list, следовательно, к значениям этого типа применимы всеоперации со списками. Например:“abc”(2) = <.’a’, ‘b’, ‘c’.>(2) = ‘b’tl “abc” = “bc”Выражение caseДостаточно часто при работе со списками используется выражение case, спомощью которого осуществляется выбор одного из нескольких различныхвариантов значения некоторого выражения.

В общем случае выражение case имеетследующий вид:case value_expr ofpattern1 -> value_expr1,...patternn -> value_exprnend, где n ≥ 1.Здесь выражение value_expr задает селектор выбора, pattern1,…,patternn –шаблоны подстановки, каждый из которых определяет соответствующий вариантзначения выражения. При вычислении выражения значение селектора value_exprпоследовательно (сверху вниз) сопоставляется с указанными шаблонами допервого совпадения. В случае успешного сопоставления с шаблоном patterniдальнейшее сопоставление не производится и в качестве результирующегозначения всего выражения принимается значения выражения value_expri. Еслипопытка сопоставления для всех шаблонов закончилась неуспешно, имеет местонеполная спецификация (недоспецификация).В RSL определено несколько видов шаблонов, мы ограничимсярассмотрением только трех из них.

Простейшими видами шаблонов являютсялитеральный шаблон (в качестве шаблонов используются литералы RSL) и шаблонуниверсальной подстановки (_), сопоставление с которым всегда приводит куспешному результату. В силу своей специфики шаблон универсальнойподстановки всегда должен располагаться последним в списке шаблоноввыражения case. Использование указанных видов шаблонов иллюстрирует примерспецификации функции, вычисляющей числа Фибоначчи.type Nat1 = {|n : Nat :- n > 0|}value Fib: Nat1 -> Nat1Fib(n) iscase n of1 -> 1,2 -> 1,_ -> Fib(n - 2) + Fib(n - 1)end27Списочный шаблон представляет собой некоторое выражение списочноготипа, основное назначение которого – ввести именование отдельных компонентданного выражения, т.е.

шаблон фактически заменяет конструкцию if (let ...).Примером использования данного вида шаблонов может служить следующаяспецификация функции, переставляющей элементы конечного целочисленногосписка в обратном порядке:value reverse : Int-list -> Int-listreverse(L) iscase L of<..> -> <..>,<.i.> ^ Lr-> reverse(Lr) ^ <.i.>endУпражнения1. Вычислить значение выражения:(a)(b)<.n * n | n in <.1..20.> :- n \ 2 = 1.>(7),<.n * n | n in <.1..20.> :- n \ 2 = 1.>(12).2.

Определить список, элементами которого являются:(a) четные числа в диапазоне от 2 до 16,(b) все полные квадраты в диапазоне от 1 до 100.Указания: используйте оба способа задания значения списка - непосредственноеперечисление его элементов и сокращенное выражение.3. Определить список, элементами которого являются числа Фибоначчи, непревосходящие 1000.Указания:•определите с помощью аксиом список из всех чисел Фибоначчи,•использую построенный список в качестве базового, определите искомыйсписок.4. Определить функцию is_sorted,  проверяющую конечный целочисленныйсписок на упорядоченность по возрастанию.Указания: воспользуйтесь аксиоматическим описанием функции.5.

Пусть конечный список образован из элементов типа Elem. Определитьследующие функции:(a) length – вычисляет длину списка без использования встроенной операции len,(b) rev – переставляет элементы списка в обратном порядке,(c) del – удаляет из списка все вхождения заданного элемента,(d) number_of – подсчитывает количество вхождений в список заданногоэлемента.Указания:28• используйте рекурсивное определение функций с помощью операций hd и tl;• в рекурсивном определении воспользуйтесь условным выражением иливыражением case,• в пунктах (c) и (d) помимо рекурсивного определения функции предложитетакже выражение, с помощью которого вычисляется результат функции.6. Определить функцию max для вычисления максимального элемента непустогоконечного списка из вещественных элементов.7.

Предложитьспецификацию следующей упрощенной модели системыобработки текстов: текст разделен на страницы, каждая страница состоит изстрок каких-то слов. Определить схему PAGE, обеспечивающую описание:(a) типов Page, Line, и Word для описания соответственно страницы,строки и слова текста,(b) функции is_on, проверяющей, встречается ли указанное слово назаданной странице,(c) функции number_of, подсчитывающей количество вхождений указанногослова в текст заданной страницы.Указания:• в пункте (a) воспользуйтесь конечными списками для описания типов Page и Line,• в пункте (b) используйте квантифицированное выражение и операции inds и elems,• в пункте (c) опишите с помощью сокращенного выражения множество париндексов (номер строки, номер слова в строке), определяющее всевхождения указанного слова в строки данной страницы, и воспользуйтесьоперацией card.29ГЛАВА 5.

ОСНОВНЫЕ АБСТРАКЦИИ ДАННЫХ ВМОДЕЛЕ-ОРИЕНТИРОВАННЫХ СПЕЦИФИКАЦИЯХ.ОТОБРАЖЕНИЯПонятие отображения, конечные детерминированные отображения. Способыопределения отображений. Операции над отображениями. Использованиеабстракцииотображенийвмоделе-ориентированнныхспецификациях.Упражнения.Понятие отображенияОтображением называется неупорядоченный набор пар значений, которыйотображает значения одного типа в значения другого типа, при этом множествоотображаемых значений называется областью определения или доменом (domain)отображения, а множество значений, в которые осуществляется отображение,называется его областью значений (range). Например:[3 +> true, 5 +> false][″Klaus″ +> 7, ″John″ +> 2, ″Mary″ +> 7]Первый пример задает отображение из натуральных чисел в значения типа Bool,второй – из типа Text в тип Nat.