lМонитор — это программная конструкция, в которой общие данные объединены вместе с множеством процедур, реализующих доступ к этим данным.
lПроцедуры монитора обладают следующим свойством: в каждый момент времени только один процесс может активно выполнять мониторную процедуру в данном мониторе.
lМонитор является конструкцией высокого уровня, позволяющей осуществлять взаимно исключающий доступ к общим ресурсам.
lПо своей мощности мониторы эквивалентны семафорам — с помощью семафоров и базовых средств языка программирования можно реализовать мониторы и, наоборот, с помощью мониторов смоделировать семафоры.
Преимущества мониторов
lМожно написать и отладить монитор отдельно от процессов, которые им будут пользоваться, так как все обращения к общим ресурсам должны выполняться с помощью мониторных процедур
lПолучение более ясных программ, которые легче понимать, отлаживать, модифицировать.
lГарантируется целостность ресурсов, которые монитор защищает, а правильность его функционирования не может быть нарушена при добавлении содержащего ошибки процесса.
lТранслятор может проверить, чтобы все обращения к общим ресурсам были законными
Аппаратная поддержка критических интервалов
lЗапрещение прерываний
lНеделимые операции
Запрещение прерываний
Достоинство
lПростота и эффективность реализации
Недостаток
lЗапрещение прерываний может негативно отразиться на работе системы в целом
lНе имеет смысла в многопроцессорных системах
Неделимые операции
lВ систему команд современных процессоров входит неделимая команда «проверить и установить»
lЗа одну неделимую операцию происходит проверка переменной на равенство нулю и ее установка в единицу.
lЕсли переменная была равна нулю, то результат операции – единица, иначе 0.
Средства для реализации параллельной обработки
lСредства обеспечения работы процессов (описание, создание, завершение, обработка исключений)
lМеханизмы, реализующие взаимное исключения и синхронизацию для процессов с общей памятью
lМеханизмы передачи сообщений
Механизмы передачи сообщений
lПредназначаются для связи между процессами, не имеющими общего адресного пространства.
lДолжны поддерживаться операционной системой или средой, в которой выполняются процессы.
lНаиболее общие:
nСопрограммы – возможность приостанавливать и продолжать выполнение одного процесса из другого.
nРандеву – возможность передачи данных между процессами без дополнительного буфера (сначала ожидается готовность процессов к передачи и приему, после этого осуществляется синхронный обмен)
lСпециализированные
nПочтовые ящики – передача сообщений между процессами через посредника.
nПорты – возможность менять посредника
nТранспортеры – перенаправление ввода/вывода.
Основные понятия для ОС Windows
lПроцесс – экземпляр выполняемой программы, состоит из адресного пространства, в котором располагается код программы и данные.
lПроцессы инертны. Чтобы процесс что-либо выполнил в нем нужно создать поток (thread). Именно потоки отвечают за выполнение кода программы.
lПроцесс содержит как минимум один поток, который создается автоматически при запуске программы и осуществляет ее выполнение.
lПрограмма может создавать дополнительные потоки по мере необходимости.
lПотоки одного процесса работают в едином адресном пространстве.
lНа однопроцессорных компьютерах операционная система предоставляет последовательно каждому потоку квант времени, на многопроцессорных компьютерах одновременно может выполняться столько потоков, сколько есть процессоров.
Средства синхронизации процессов в С/С++ отсутствуют
lОбъекты API (используются функции С)
nВзаимоисключения (mutex)
nСобытия (event)
nСемафоры (semaphore)
nКритические интервалы (critical section)
nЗащищенный доступ к переменным
lКлассы VCL Borland C++ Builder
nTMultiReadExclusiveWriteSynchronizer
nTCriticalSection
nTEvent
Общие особенности
lОтсутствует какая-либо связь между объектом синхронизации и защищаемым ресурсом
lГарантируется, что все операции с объектами синхронизации являются неделимыми.
Возможные состояния потоков
lАктивен – идет выполнение потока на процессоре.
lГотов – поток готов к выполнению, ждет предоставления процессорного времени.
lЗаблокирован – потоку не выделяется процессорное время, он не планируется на выполнение.
Управление потоками в Borland C++ Builder
lДля упрощения работы с потоками в Borland C++ Builder предусмотрен специальный класс TThread.
Взаимоисключения
lОбъекты-взаимоисключения (мьютексы, mutex - от MUTual EXclusion) позволяют координировать взаимное исключение доступа к разделяемому ресурсу.
lСигнальное состояние объекта (т. е. состояние "установлен") соответствует моменту времени, когда объект не принадлежит ни одному потоку и его можно "захватить".
lСостояние "сброшен" (не сигнальное) соответствует моменту, когда какой-либо поток уже владеет этим объектом.
lДоступ к объекту разрешается, когда поток, владеющий объектом, освободит его.
lДля того, чтобы объявить взаимоисключение принадлежащим текущему потоку, надо вызвать одну из ожидающих функций.
lПоток, которому принадлежит объект, может его "захватывать" повторно сколько угодно раз (это не приведет к самоблокировке), но столько же раз он должен будет его освобождать.
Пример использования Mutex
#include <windows. h>
#include <iostream. h>
void main() {
DWORD res;
// создаем объект-взаимоисключение
HANDLE mutex = CreateMutex(NULL, FALSE, "APPNAME-MTX01");
// если он уже существует, CreateMutex вернет дескриптор существующего
// объекта, а GetLastError вернет ERROR_ALREADY_EXISTS
// в течение 20 секунд пытаемся захватить объект
cout<<"Trying to get mutex...\n";
cout. flush();
res = WaitForSingleObject(mutex,20000);
if (res == WAIT_OBJECT_0) // если захват удался
{ // ждем 10 секунд
cout<<"Got it! Waiting for 10 secs...\n"; cout. flush();
Sleep(10000);
// освобождаем объект
cout<<"Now releasing the object.\n"; cout. flush(); ReleaseMutex(mutex);
}
// закрываем дескриптор
CloseHandle(mutex);
}
События (Event)
lОбъекты-события используются для уведомления ожидающих потоков о наступлении какого-либо события.
lРазличают два вида событий - с ручным и автоматическим сбросом.
lРучной сброс осуществляется функцией ResetEvent. События с ручным сбросом используются для уведомления сразу нескольких потоков.
lПри использовании события с автосбросом уведомление получит и продолжит свое выполнение только один ожидающий поток, остальные будут ожидать дальше.
lФункция CreateEvent создает объект-событие.
lSetEvent - устанавливает событие в сигнальное состояние.
lResetEvent-сбрасывает событие.
lФункция PulseEvent устанавливает событие, а после возобновления ожидающих это событие потоков (всех при ручном сбросе и только одного при автоматическом), сбрасывает его.
lЕсли ожидающих потоков нет, PulseEvent просто сбрасывает событие.
Семафоры
lОбъект-семафор - это фактически объект-взаимоисключение со счетчиком.
lСемафор позволяет "захватить" себя определенному количеству потоков.
lПосле этого "захват" будет невозможен, пока один из ранее "захвативших" семафор потоков не освободит его.
lСемафоры применяются для ограничения количества потоков, одновременно работающих с ресурсом.
lОбъекту при инициализации передается максимальное число потоков, после каждого "захвата" счетчик семафора уменьшается.
lСигнальному состоянию соответствует значение счетчика больше нуля.
lКогда счетчик равен нулю, семафор считается не установленным (сброшенным).
Критические интервалы
lОбъект - критический интервал помогает программисту выделить участок кода, где поток получает доступ к общему ресурсу, и предотвратить одновременное использование ресурса.
lПеред использованием ресурса поток входит в критический интервал (вызывает функцию EnterCriticalSection).
lЕсли после этого какой-либо другой поток попытается войти в тот же самый критический интервал, его выполнение приостановится, пока первый поток не покинет интервал с помощью вызова LeaveCriticalSection.
lПохоже на взаимоисключение, но используется только для потоков одного процесса.
lСуществует также функция TryEnterCriticalSection, которая проверяет, занят ли критический интервал в данный момент.
lС ее помощью поток в процессе ожидания доступа к ресурсу может не блокироваться, а выполнять какие-то полезные действия.
Критические интервалы
//Для использования критического интервала, нужно объявить переменную типа CRITICAL_SECTION
CRITICAL_SECTION CS;
// Потом эту переменную CS нужно инициализировать (создать критический интервал)
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
InitializeCriticalSection(&CS);
}
// используем критический интервал в потоке, когда нужно блокировать доступ к данным
void __fastcall TMyThread::Execute()
{
FreeOnTerminate = true; // освободить занятую потоком память по окончании его работы
for(int i=0; i<10000; i++)
{
// -- какие-то сложные вычисления в цикле
if(Terminated) break; // прекратить извне поток
// блокировать доступ к данным (войти в критический интервал)
EnterCriticalSection(&Form1->CS);
... доступ к глобальным данным
// закрыть критический интервал (покинуть критический интервал)
LeaveCriticalSection(&Form1->CS);
}
}
// Когда критический интервал становиться не нужен, удаляем его
void __fastcall TForm1::FormClose(TObject *Sender, TCloseAction &Action)
{
DeleteCriticalSection(&CS); // удалить критический интервал
}
Защищенный доступ к переменным
lСуществует ряд функций, позволяющих работать с глобальными переменными из всех потоков не заботясь о синхронизации, т. к. эти функции сами за ней следят.
lЭто функции:
nInterlockedIncrement
nInterlockedDecrement,
nInterlockedExchange,
nInterlockedExchangeAdd
nInterlockedCompareExchange
lНапример, функция InterlockedIncrement увеличивает значение 32-битной переменной на единицу - удобно использовать для различных счетчиков.
TMultiReadExclusiveWriteSynchronizer
Методы
void BeginRead();
void EndRead();
bool BeginWrite();
void EndWrite();
TMultiReadExclusiveWriteSynchronizer
Нить 1
while(!Sync->BeginWrite()){
Sleep(1000);
Sync->EndWrite();
}
…
// обработка общего ресурса
…
Sync->EndWrite();
Нить 2
Sync->BeginRead();
…
// обработка общего ресурса
…
Sync->EndRead();
TCriticalSection
Методы
void Enter();
void Acquire();
void Leave();
void Release();
TCriticalSection
Нить 1
sect->Enter();
…
// обработка общего ресурса
…
sect->Leave();
TEvent
Методы
void ResetEvent()
void SetEvent()
TWaitResult WaitFor(int Timeout)
enum TWaitResult {
wrSignaled,
wrTimeout,
wrAbandoned,
wrError
};
TEvent
Нить 1
TWaitResult w;
w = Event->WaitFor(1000);
if(w == wrSignaled)
// дождались сигнала
else
// не дождались
Вопросы к экзамену
lПараллельная обработка. Основные понятия. Средства обеспечения работы процессов.
lПараллельная обработка. Средства реализации взаимных исключений и синхронизации нитей процессов.
nПрограммное решение проблемы взаимного исключения
nДвоичные семафоры
nПростые критические интервалы
nМониторы
lПараллельная обработка. Механизмы передачи сообщений между процессами.
lСредства синхронизации процессов в Windows
nОбъекты API
nКлассы VCL Borland C++ Builder
Декларативное программирование
История развития языков программирования
•40гг. – первые цифровые компьютеры – программирование путем коммутации проводов.
•программирование на машинном языке
•появление ассемблеров – машинные команды получают мнемонические имена (LOAD, STORE, ADD, …)
•конец 50х – создание первого компилятора для языка FORTRAN (FORmula TRANslator – транслятор формул)
–более удобное средство для написания формул, чем ассемблер
–переносимость кода
История развития языков программирования
•Архитектура языков программирования должна быть максимально приближена к архитектуре компьютеров для наиболее эффективного использования его ресурсов.
•Компьютер состоит из процессора и памяти – значит программа должна состоять из последовательности инструкций, выполняемых процессором и модифицирующих память.
Парадигма языка программирования
•Компьютер представляется в виде туповатого исполнителя, тем не менее поддающегося обучению.
•Исполнитель может исполнять некоторые простейшие команды.
•Обучение происходит путем формирования процедур из команд и использования их в дальнейшем вместо повторения последовательности команд.
•Программа описывает процесс последовательного, пошагового решения задачи.
Наклонения предложений в грамматике
•изъявительное (повествовательные)
•вопросительное
•повелительное (императивное)
•Изученные языки С/C++ относятся к императивным языкам.
•Другие названия – директивные, процедурные.
Программирование в повествовательном наклонении
•Стиль программирования, в котором программа представляется в как совокупность утверждений получил название декларативный.
•Программа на императивном языке программирования предписывает, как достичь требуемую цель; декларативная программа заявляет (декларирует), что должно быть достигнуто в качестве цели.
•Наиболее важные разновидности
–функциональное программирование
–логическое (реляционное) программирование
Особенности декларативного программирования
•Особое внимание уделяется тому, что нужно сделать, а не тому как этого достичь.
•Описание вычислений производится используя уравнения, функции, логические выводы и т. п
Не используют понятия состояния и не содержат переменных, отсюда:
–не могут использовать операторы присваивания, так как нечему присваивать;
–понятие последовательности выполнения команд становится бессмысленным и, значит, бесполезными становятся операторы управления процессом вычислений.
Предположим, требуется пройти в городе из пункта А в пункт Б.
•Декларативная программа - это план города, в котором указаны оба пункта, плюс правила уличного движения. Руководствуясь этими правилами и планом города, курьер сам найдет путь от пункта А к пункту Б.
•Императивная программа - это список команд примерно такого рода: от пункта А по ул. Садовой на север до площади Славы, оттуда по ул. Пушкина два квартала, потом повернуть направо и идти до Театрального переулка, по этому переулку налево по правой стороне до дома 20, который и есть пункт Б.
Виды декларативного программирования
•Функциональное программирование основывается на математическом понятии функции, которая не изменяет свое окружение (в отличии от функций в процедурных языках, допускающих побочные эффекты)
•Логическое программирование - программы выражены в виде формул математической логики и компьютер для решения задачи пытается вывести логические следствия из них.
Достоинства декларативных языков
•В основе декларативных языков лежит не какая-то машинная модель, а логика и математика.
Появляется возможность формализовать знания о проблеме непосредственно в терминах языка программирования.
•Необходимость иметь дело только (или главным образом) с логическим компонентом значительно упрощает программирование.
•Декларативные языки хорошо подходят для программирования параллельных компьютеров.
•Пригодность для формальных рассуждений.
Недостатки декларативных языков
•Существующие формы декларативного программирования плохо справляются с временными аспектами многих задач.
•Отсутствует возможность адекватно выразить в программе естественный параллелизм задачи.
•Низкая эффективность.
Логическое программирование
•Основано на логике предикатов.
•Основное внимание уделяется описанию структуры прикладной задачи, а не выработке предписаний компьютеру, что ему следует делать.
•Наиболее известный язык логического программирования PROLOG (от французского PROgrammation LOGique)
•Пролог часто называют языком искусственного интеллекта - с его помощью решаются задачи создания экспертных систем и систем обработки естественных языков.
Пролог
•Как и для других декларативных языков, при работе с Прологом мы описываем ситуацию (правила и факты) и формулируем цель (запрос), позволяя интерпретатору Пролога найти решение задачи за нас.
•Под интерпретатором Пролога мы будем понимать механизм решения задачи при помощи языка Пролог. Другими словами, интерпретатор языка Пролог - это исполнитель Пролог-программ, т. е. та "активная сила", которая выполняет программы, написанные на Прологе.
Круг задач Пролог
•задачи, связанные с разработкой систем искусственного интеллекта (различные экспертные системы, программы-переводчики, интеллектуальные игры).
•обработка естественного языка
•обладает мощными средствами, позволяющими извлекать информацию из баз данных
•решении задач составления сложных расписаний
•не является универсальным языком программирования и не предназначен, например, для решения задач, связанных с графикой или численными методами
Программа на языке Пролог
•Программа на языке Пролог представляет собой набор фактов и (возможно) правил.
•Если программа содержит только факты, то ее называют база данных.
•Если она содержит еще и правила, то часто используют термин база знаний.
•Запрос (вопрос) вводится после приглашения и обязательно заканчивается точкой, например,
?- 5+4<3.
No
Пролог анализирует запрос и выдает ответ Yes (Да) в случае истинности утверждения и No (Нет) в противном случае или когда ответ не может быть найден.
Хранение программ
•Хранят программы на языке Пролог в текстовых файлах, чаще всего имеющих расширение pl, например, example1.pl.
•Для того чтобы Пролог мог оперировать информацией, содержащейся в файле, он должен ознакомится с его содержимым (проконсультироваться с ним).
?- [example1].
или
?- consult(example1).
Термы и объекты
•Программа на языке Пролог обычно описывает некую действительность.
•Объекты (элементы) описываемого мира представляются с помощью термов.
•Терм интуитивно означает объект.
•Существует 4 вида термов: атомы, числа, переменные и составные термы.
•Атомы и числа иногда группируют вместе и называют простейшими термами.
Атом
•Атом - это отдельный объект, считающийся элементарным.
•В Прологе атом представляется последовательностью букв нижнего и верхнего регистра, цифр и символа подчеркивания '_', начинающейся со строчной буквы.
•Любой набор допустимых символов, заключенный в апострофы является атомом.
•Комбинации специальных символов + - * = < > : & также являются атомами
Числа
•Целые (Integer)
•Вещественные (Float)
Переменные
•Переменными в Прологе являются строки символов, цифр и символа подчеркивания, начинающиеся с заглавной буквы или символа подчеркивания
X, _4711, X_1_2, Результат, _x23, Объект2
Анонимная переменная
•Анонимная переменная (обозначается одним символом подчеркивания) применяется, когда ее значение не используется в программе.
Составные термы (функции)
•Составные термы (функции) состоят из имени функции (нечислового атома) и списка аргументов (термов Пролога, то есть атомов, чисел, переменных или других составных термов), заключенных в круглые скобки и разделенных запятыми.
•Группы составных термов используют для составления фраз Пролога.
итого(клиент(X,23,_), 71)
'Что случилось?'(ничего)
Факты
•Программировать на Прологе - значит описывать некий мир.
•Программа на этом языке состоит из множества фраз, задающих взаимосвязь между термами.
•Каждый терм обозначает ту или иную сущность, принадлежащую миру. Один из способов описания - это задание фактов.
Факт
•Факт - это утверждение о том, что соблюдается некоторое конкретное отношение. Он является безусловно верным. В разговорной речи под фактом понимается нечто вроде "Сегодня солнечно" или “Коле 10 лет". На Прологе это запишется в виде
'Сегодня солнечно'.
'Коле 10 лет'.
Предикат
•Предикат - это логическая функция от одного или нескольких аргументов, то есть функция, действующая в множество из двух значений: истина и ложь. Предикат Пролога записывается в виде составного терма: имя_предиката(аргументы).
Аргументы предикатов
•Аргументы перечисляются через запятую и представляют собой какие-то объекты или свойства объектов, а имя предиката обозначает связь или отношение между аргументами.
•Предикат однозначно определяется парой: имя и количество аргументов.
Пример
Факт "Коля работает слесарем" на Прологе запишется следующим образом:
профессия(коля, слесарь).
База данных
•База данных на Прологе - это совокупность фактов.
•В процессе работы в базу данных можно добавлять новые факты, удалять или изменять старые.
Пример
Составим базу данных из следующих фактов: "слон больше, чем лошадь", "лошадь больше, чем осел", "осел больше, чем собака" и "осел больше, чем обезьяна":
больше(слон, лошадь).
больше(лошадь, осел).
больше(осел, собака).
больше(осел, обезьяна).
Запросы к базе данных
Запрос - это последовательность предикатов, разделенных запятыми и завершающаяся точкой.
•На естественном языке запятая соответствует союзу "и", а на языке математической логики обозначает конъюнкцию.
•С помощью запросов можно "спрашивать" базу данных о том, какие утверждения являются истинными.
•Предикат запроса называется целью.
Примеры запросов
?- 5+4<3.
No
?- больше(слон, лошадь).
Yes
?- больше(лошадь, слон).
No
?- больше(лошадь, корова).
No
Правила
•Правило задает новый предикат через определенные ранее.
•Правило состоит из головы (предиката) и тела (последовательности предикатов, разделенных запятыми). Голова и тело разделены знаком :-
•Правило должно заканчиваться точкой.
•Запятая в теле правила означает конъюнкцию (&&, логическое и).
Правила
•Знак :- есть схематическая запись стрелки (<-) и показывает, что из правой части следует левая. Этот знак читается как "если".
•Интуитивный смысл правила состоит в том, что цель, являющаяся головой, будет истинной, если Пролог сможет показать, что все выражения (подцели) в теле правила являются истинными.
Пример
Правило, определяющее отношение ребенок/2 через отношение отец/2, запишется следующим образом:
ребенок(X, Y) :- отец(Y, X).
Это означает, что если человек Y является для человека X отцом, то X является ребенком Y. Здесь X и Y - переменные.
Правила с рекурсией
•Т. к. в Прологе отсутствуют операторы управления, то более сложные правила создаются с помощью рекурсии.
•В Прологе рекурсия встречается, когда предикат содержит цель, которая ссылается на саму себя.
•В рекурсивном правиле более сложные входные аргументы должны выражаться через менее сложные.
•Используя рекурсию как прием программирования мы должны быть уверены, что рекурсивная процедура будет завершена.
Пример рекурсии
больше(слон, лошадь).
больше(лошадь, осел).
больше(осел, собака).
больше(осел, обезьяна).
больше_2(X, Y) :- больше(X, Y).
больше_2(X, Y) :- больше(X, Z), больше_2(Z, Y).
Результат использования рекурсивных правил
?- больше(слон, обезьяна).
No
?- больше_2(слон, обезьяна).
Yes
Функциональное программирование
(пример - Excel)
•Функциональное программирование ставит своей целью придать каждой программе простую математическую интерпретацию.
•Эта интерпретация должна быть независима от деталей исполнения.
Семантика ЯП
Семантика ЯП задается определением средств описания данных и действий.
Функциональное программирование использует математическое понятие функции для выражения концепции действия.
Подобно обычным математическим функциям, процедуры («функции») функциональных языков отображают одни объекты (аргументы) в другие (значения).
В отличие от процедур (функций) императивных языков, значения функций однозначно определяются их аргументами и не зависят от истории вычислительного процесса.
Важное различие между математическими функциями и императивными процедурами заключается в том, что процедуры должны быть эффективно определены.
Понятие функции используется в функциональных языках программирования и для выражения концепции данных.
Функции в функциональных языках являются объектами «первого класса».
Элементы первого класса - это элементы с наименьшим количеством ограничений. Важные свойства таких первоклассных элементов:
• На них можно ссылаться посредством переменных.
• Их можно включать в структуры данных.
• Их можно передавать как параметры.
• Они могут быть возвращены в качестве результата.
Язык Лисп
•Лисп – интерпретатор
•Обычно работа с интерпретатором Лиспа происходит по следующему сценарию:
–Пользователь вводит выражение.
–Интерпретатор вычисляет значение этого выражения и печатает результат.
Элементарные выражения
Выражения и значения выражений.
Числовые константы обозначают числа, которые и являются их значениями. Разнообразие доступных типов чисел зависит от реализации языка, но все реализации поддерживают целые и вещественные числа, а многие ещё и рациональные и комплексные.
10
10
Последовательность букв, цифр и специальных знаков, отличающаяся от числа называется символом. Главное их назначение - именовать объекты. Поэтому, значением символа является объект, поименованный этим символом.
Hello
Error: undefined variable
С именем «+» связана встроенная функция, вычисляющая сумму чисел, которая и является значением.
+
#<procedure +>
Значением выражения '<символ> является сам этот символ. Лисп нечувствителен к регистру букв и значение символа приведено к стандартному виду.
'Hello
hello
Строковые константы записываются в двойных кавычках и представляют последовательности отображаемых знаков.
"Hello"
"Hello"
Две логические константы #t и #f обозначают истину и ложь.
#f
#f
Константы и символы носят общее имя атомы, поскольку представляют собой простейшие элементы языка, из которых строятся выражения.
Для записи выражений (форм в терминологии Лиспа) используется единая префиксная форма: имя функции стоит перед аргументами и записывается внутри скобок
(+ 2 2)
4
(* 1.1 2)
2.2
(= 1 2)
#f
Подобные выражения, описывающие применение функции к аргументам, называются комбинационными формами или комбинациями.
Значение комбинации - результат применения функции, указанной первым элементом списка (оператором) к параметрам, которые являются значениями остальных элементов (операндов).
В данном случае, операторы - встроенные функции +,*,=.
Пример более сложного выражения.
(+ (* 3
20
Общее правило вычисления значения комбинации следующее:
Вычислить значение всех подвыражений.2. Применить функцию, которая является значением оператора к аргументам, которые являются значениями операндов.
Таким образом, в Лиспе используется аппликативный порядок вычислений
В традиционной математической нотации имя функции стоит перед аргументами, заключенными в скобках. Кроме того, используется инфиксная запись арифметических выражений, разнообразные индексы и специальные знаки.
Математическая запись | Запись на Лиспе |
f(x) | (f x) |
g(x, y) | (g x y) |
h(x, g(y, z )) | (h x (g y z)) |
sin x | (sin x) |
x + y | (+ x z) |
x + y·z | (+ x (* y z)) |
xy | (expt x y) |
|x| | (abs x) |
x = y | (= x y) |
x + y < z | (< (+ x y) z) |
В сравнении с этим многообразием и даже с синтаксисом большинства языков программирования префиксная форма кажется несколько непривычной и громоздкой. Но она обладает, по крайней мере, одним неоспоримым достоинством - описание синтаксиса умещается на одной строчке:
<выражение> ::= <атом> | ( <выражение>)
Чтобы сделать выражения более читаемыми, многие реализации допускают использование квадратных скобок.
(/ [+ (* 3] 2)
10
Несмотря на то, что Лисп - бестиповый язык и любое сочетание аргументов является синтаксически допустимым, в процессе выполнения для каждого значения определяется его тип и попытка применить + к логическому значению вызывает ошибку.
Поэтому Лисп называют динамически типизированным языком.
Заметим что правила типизации соблюдаются гораздо более строго, чем в Си или даже в Паскале - нет никакой возможности подсунуть функции аргумент не того типа.
(
Error: attempt to apply a non-procedure
1 не является функцией. Поэтому попытка применить её приводит к ошибке.
(+ 1 (= 1 2))
Error in +: #f is not a number.
Базовые функции.
В Лиспе определён большой набор базовых функций, рассмотрим некоторые из них. Это во-первых арифметические операции (+,-,*,/). Функции + и * имеют произвольное количество аргументов. В принципе, это не очень хорошая практика, но в данном случае она себя оправдывает.
(+ | (+ 1) | (* |
Поскольку операции вычитания и деления не ассоциативны, попытка расширить их определение на произвольное количество аргументов может привести к путанице. Однако, для одного аргумента определено, что (- a)выдаёт -a, а (/ a)- 1/a.
(- 5) | (/ | (/ 2 3) |
Неожиданность. Ожидалось скорее 0 или 0.666667 в зависимости от типа данных. Но для непредубежденного человека вполне естественно. Впрочем, если реализация не поддерживает рациональных чисел (что допускается для Scheme) получим 0.666667.
Для деления с остатком предназначены функции quotient и remainder, возвращающие целую часть и остаток от деления.
Логические функции
Функции, возвращающие логические значения, называются предикатами. В Lisp принято названия предикатов (кроме распространённых арифметических операций сравнения =,>,<,<=,>= ) завершать вопросительным знаком или - буквой "p"(от слова predicate).
(= 1 2) | (odd? 2) |
(< 1 2) | even? 2) |
(Подобно + и *, операции сравнения допускают произвольное число аргументов (но, конечно же, не менее двух). Это сделано всё с той же целью - уменьшить сложность выражений. Например (< x1 x2 …xn)вернёт #t, только если аргументы упорядочены по возрастанию.
Для символов единственная осмысленная операция - сравнение на идентичность.
(eq? 'a 'a)
#t
Может показаться странным использование специального предиката, а не символа равенства. Но мы часто подразумеваем совершенно разные вещи, когда говорим, что два объекта равны. Предикат = сравнивает численные значения двух выражений, а предикат eq? проверяет, что эти выражения именуют один и тот же объект. Поэтому:
(= 1 1.0) | (eq? 1 1.0) | (eq? 1 1) |
Типовые предикаты
Поскольку переменные Лиспа могут принимать значение любого типа, необходимо иметь возможность определять этот тип. Для этого предусмотрены типовые предикаты.
(boolean? 1) | (integer? 1) | (real? 1.1) | (procedure? '+) |
(number? 1) | (integer? 1.1) | (procedure? +) | (symbol? '+) |
Логические связки
Для представления логических связок используются функции not, or и and.
(not x)
возвращает #t, если значение аргумента равно #f и #f в противном случае.
(or x1 x2 … xn)
возвращает значение первого аргумента, не равного #f. Если же все аргументы имеют значение #f, то оно и возвращается.
(and x1 x2 … xn)
возвращает значение #f, если оно встречается среди значений аргументов. В противном случае возвращается значение последнего аргумента.
Любое значение, отличное от #f интерпретируется как истина.
(not #f) |
|
(not 0)Условные выражения
Если зависимость значений истинности от значений других типов выражается предикатами, а зависимость значений истинности от других значениях истинности логическими связками, то условные выражения - средство для выражения зависимости значений произвольного типа от значений истинности.
(if p et ef)
возвращает значение ef, если значение p - #f, и et в противном случае.
(cond (p1 e1) (p2 e2) … (pn en))
возвращает значение ei, для первого i при котором значение pi отлично от #f.
Средства объединения объектов
Определения
Для определения новых объектов, применяются определяющие формы.
(define n e)
связывает имя n со значением выражения e.
(define (f a1…an) e)
определяет новую функцию с именем f.
a1…an - формальные параметры, т. е. имена, используемые внутри тела функции для ссылок на соответствующие параметры.
e - тело функции, выражение, определяющее её значение
(define x 1) x 1 (+ x x) 2 | (define x 2) (+ x x) 4 |
(define & and)
(& (< 1 2) (< 2 3))
#t
Значение and, то есть встроенная функция связывается с именем &, после чего & можно использовать вместо and.
(define (sqr x) (* x x))
sqr
#<procedure>
(sqr 5)
25
Теперь с именем sqr связана вновь определённая функция и ее можно использовать для возведения в квадрат. Подобно встроенным функциям, она не отображается. Дело в том, что интерпретатор не сохраняет определения как синтаксические деревья, а компилирует их в байт-код.
Лямбда-выражения
В Лиспе можно отделить два понятия - определение функции, и её именование.
Дать имя функции можно все той же конструкцией define
(define sqr <функция возведения в квадрат>) а определить - с помощью специальной формы: лямбда-выражения.
(lambda (a1…an) e)
возвращает функцию, вычисляющую значение выражения e при подстановке фактических параметров вместо a1…an.
Например, sqr можно было бы определить и так
(define sqr (lambda (x) (* x x)))
Лямбда-выражение может использоваться всюду, где используется имя функции, например как оператор в комбинации вида.
([lambda (x) (* x x)] 2)
4
Связывающие формы
Иногда выражение содержит повторяющиеся части. Чтобы упростить запись таких выражений этим частям можно присвоить локальные имена с помощью связывающий формы let.
(let ((a1 e1)(a2 e2) … (an en)) e)
Значением этой формы будет значение выражения e, в котором каждое ai заменено значением выражения ei.
Например, функция для вычисления площади треугольника по формуле Герона.
(define (square-triangle a b c)
(let ((p (/ 2 (+ a b c))))
(sqrt (* p (- p a) (- p b) (- p c))))
Того же эффекта можно было бы добиться применяя лямбда-выражение.
(define (square-triangle a b c)
(lambda (p) (sqrt (* p (- p a) (- p b) (- p c))) (/ 2 (+ a b c))))
Семантически это одно и то же, но, запись с let намного нагляднее
Составные данные
Любые два объекта можно объединить в новый объект, называемый (точечной) парой с помощью примитивной функции cons. Чтобы получить составные части пары, используются функции car и cdr.
(cons a b) - возвращает составной объект - пару (a . b)
(car a) - возвращает первый элемент пары
(cdr a) - возвращает второй элемент пары
(define x (cons 1 2))
x
(1 . 2)
(car x)
1
(cdr x)
2
При обработке таких структур необходимо иметь возможность определить является ли выражение атомом или парой. Это делается встроенным предикатом pair?.
(pair? a)
возвращает #t, если аргумент представляет собой пару и #f в противном случае.
Вложенные цепочки пар называются списками.
(cons 1 (cons 2 (cons 3
(1 2 3)
Списки играют особую роль в Лиспе. Чтобы упростить их формирование, предусмотрена специальная функция list.
(list a1…an) возвращает список объектов (a1…an), то есть (a1 .(a2 . …(an . nil)…)).
(list
(1 2 3)
(car (list
1
(cdr (list
(2 3)
В действительности, выражения Лиспа представляют собой ни что иное, как списки. Это даёт возможность обрабатывать их как данные. Чтобы получить выражение как таковое, а не его значение используется специальная форма quote.
(quote a) - возвращает в качестве значения свой аргумент, не вычисляя его. Аналог – знак апострофа.
(quote a) а | ''a (quote a) | (car '(+ 1 2)) + |
'а а | '(+ 1 2) (+ 1 2) | 䦋㌌㏒㧀좈琰茞ᓀ㵂Ü |
Противоположность quote - функция eval, вычисляющая значение выражения.
(eval '(+ 1 2))
3
(eval (list + 1 2))
3
Рекурсивные определения.
Для того чтобы рекурсивное определение было полезным необходимо выполнение следующих двух условий:
Наличие нерекурсивного определения для базового случая. Параметр рекурсивного обращения должен быть «проще», чем параметр определяемой функции.Вычисление факториала
Факториал положительного целого числа n определяется как произведение всех чисел от 1 до n.
n!=1*2*3*…*n.
Для любого n>1 n! = n*(n-1)!. Таким образом, мы можем вычислить n!, вычисляя (n - 1)! и умножая результат на n. Если мы прибавим соглашение что 1! = 1, получим следующее определение:
(define (fac n)
(cond ((= n 1) 1)
((> n 1) (* n (fac (- n 1))))))
(fac 20)
(/ (fac 100) (fac 99))
100
Числа Фибоначчи
Определение чисел Фибоначчи само по себе рекурсивно. Каждое число в последовательности, кроме двух первых является суммой двух предшествующих.
F1 = 1
F2 = 1
Fn = Fn-1+ Fn-2.
Это определение непосредственно записывается на Лиспе.
(define (fib n)
(cond ((= n
((= n
((> n 2) (+ (fib (- n 1)) (fib (- n 2))))))
Наибольший общий делитель (НОД)
НОД двух натуральных чисел a и b определен, как наибольшее натуральное число, которое делит a и b без остатка. Если число n делит оба числа а и b, то оно делит их сумму и разность, и отсюда
НОД(a, b) = НОД(a+b, b) = НОД(a, a+b) = НОД(a-b, b) = НОД(a, a-b).
Можно найти ещё множество интересных свойств НОД, но уже здесь мы замечаем, что НОД(a-b, b) выглядит несколько «проще» чем НОД(a, b) в том смысле, что приходится иметь дело с меньшими числами. Добавляя сюда тот очевидный факт, что НОД(a, a) = a, приходим к знаменитому алгоритму Евклида.
(define (gcd a b)
(cond ((= a b) a)
((> a b) (gcd (- a b) b) )
((< a b) (gcd (- b a) a) )))
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 |
