Контрольные вопросы

1) Что называется определением имени?

2) Сформулируйте понятие I – индексированного семейства множеств.

3) Сформулируйте формальное определение понятия «сигнатура».

4) Что такое редукт, расширение, приращение сигнатуры?

4.2. Алгебры

Как было показано в разд. 1.1, все операции могут быть представлены как функции:

Т₁, Т₂, … , Т_n  Т_р или функция (Т₁, Т₂, … , Т_n) Т_р.

В отличии от математической трактовки функций, при которой способ получения результата функции Т_р по набору аргументов Т₁, Т₂, … , Т_n лишь подразумевается и не является основным объектом изучения, при программистском рассмотрении функции процесс переработки аргументов-данных в результат выдвигается на передний план. Употребление типов данных в качестве аргументов функций влечет за собой зависимость от них типа результата и/или зависимость типов одних аргументов от других. Поэтому перед нами будут стоять: задача реализации функций и задача анализа функций (рассуждения о функциях). Вследствие этого при указании области определения функции каждый из типов-аргументов при необходимости будем сопровождать соответствующим именем. При таких исходных посылках обозначение типа функции приобретает вид:

функция (p₁ : Т₁, p₂ : Т₂, … , p_n : Т_n) Т_р ,

где Т_i и p_i, i = {1, 2, … , n}, - тип, определяющий i – й аргумент (i – е множество значений из области определения), а Т_р – тип, определяющий результат функции (множество значений области результата). В дальнейшем в зависимости от потребности будем выбирать любой из перечисленных способов представления функции.

Сигнатуры являются чисто синтаксическим образованием и от них мало пользы до тех пор, пока мы не придадим смысл применяемым в них именам (т.е. пока не будет задана семантика имен): каждому имени основы мы сопоставим конкретное множество, а каждому имени операции - конкретную функцию. «Осмысление» сигнатуры приводит к алгебре. Задание конкретной алгебры для сигнатуры будем называть реализацией сигнатуры. Например, реализация основ и операций нашего примера средствами «компьютерного языка» могла бы выглядеть следующим образом:

реализация основ bool = {0, 1};

nat = {множество комбинаций битов одной ячейки памяти};

setofnat = {множество ячеек памяти};

реализация операций

false : функция bool = 0;

true : функция bool = 1;

not : функция (p : bool) bool = если p = 0 то 1 иначе 0;

or : функция (p : bool, q : bool) bool = если p = 0 то (если q = 0 то 0 иначе 1) иначе 1;

and : функция (bool, bool) bool bool = если p = 1 то (если q = 1 то 1 иначе 0) иначе 0;

zero : nat = заполненная нулями ячейка памяти;

succ : функция (n : nat) nat = машинное сложение (n, 1);

 : функция (n1 : nat, n2 : nat) bool = машинное сравнение (n1, n2);

 : функция (n1 : nat,n2 : nat) bool = машинное вычитание (n1, n2);

empty : setofnat = пустая последовательность ячеек памяти;

insert : функция (s : setofnat, n : nat) setofnat = если s не содержит n

то добавить ячейку памяти с n;

has : функция (s : setofnat, n : nat) bool = если s содержит n то 1 иначе 0.

Здесь с основой bool связываемся множество из двух значений 0 и 1, одно из которых сопоставляется затем константе false, а другое – константе true. Основе nat сопоставляется множество комбинаций битов ячейки памяти, из которых комбинация с нулями во всех битах выбирается в качестве значения константы zero. Операция succ реализуется посредством команды сложения числа n с единицей, а операции  и  реализуются командами сравнения и вычитания двух чисел, записывающими в определенный регистр признак результата с помощью сопоставляемого основе bool множества значений (1 – плюс, 0 – минус). Основа setofnat связывается с множеством ячеек памяти, а соответствующие операции empty, insert и has реализуются командами над ячейками памяти. Заметим, что в реализации операций, как аргументы, так и результаты операций являются объектами сопоставленных основам множеств. Таким образом, можно сказать, что алгебра – это сигнатура с парой функций, одна из которых отображает имена основ во множества, а другая - знаки операций в функции. Если множество S содержит одну основу, алгебра называется одноосновной, в противном случае – многоосновной.

Ранее мы рассмотрели многоосновную алгебру. Простым примером одноосновной алгебры может служить алгебра целых чисел, взятых по модулю 4 с сигнатурой

{number}, {zero, one :  number; plus, times : number, number  number},

которая может быть реализована следующим образом:

number = {0, 1, 2, 3}; zero = 0; one = 1;

Plus =		0	1	2	3		Times =		0	1	2	3
	0	0	1	2	3			0	0	0	0	0
	1	1	2	3	0			1	0	1	2	3
	2	2	3	0	1			2	0	2	0	2
	3	3	0	1	2			3	0	3	2	1

У этой алгебры всего одна основа number, представляющая множество из четырех объектов. Реализация операций plus и times задана таблицами.

Семейство множеств, сопоставленных именам основ сигнатуры, называется носителем алгебры, для алгебры А носитель обычно обозначается как А.

Определение 1.2. Пусть  =  S,   есть сигнатура. Тогда  - алгебра А – это S - индексированное семейство множеств А, называемое носителем А, вместе с (S^* S) - индексированным семейством функций _us : _us  _us, где us – индекс знака операции, u  S^*, u=u₁ … u_n, s S, _us = {A_uA_s} – множество сопоставленным знакам операций _us функций реализации, и A_u = А_{u1 … un}= А_u1  …  А_un.

Таким образом, каждая _us сопоставляет некоторому знаку операции _us _us конкретную функцию реализации _us_us.

Определение 1.3.  - алгебра А называется  - редуктом  ^ - алгебры А, если S^A  S^A, для всех s S,    ; соответственно А называется расширением А. Совокупность основ и операций, добавление которых превращает алгебру А в алгебру А , будем называть А - приращением алгебры А.

Рассматривая пример алгебры множеств, в ней можно выделить в качестве редукта алгебру натуральных чисел (с основами nat и bool ), сама она является расширением обеих этих алгебр.