Ноябрь 2007 1 Декларативное программирование. Ноябрь 20072 История развития языков программирования 40 гг. – первые цифровые компьютеры – программирование. - презентация

1 Ноябрь Декларативное программирование

2 Ноябрь История развития языков программирования 40 гг. – первые цифровые компьютеры – программирование путем коммутации проводов. 40 гг. – первые цифровые компьютеры – программирование путем коммутации проводов. программирование на машинном языке программирование на машинном языке появление ассемблеров – машинные команды получают мнемонические имена (LOAD, STORE, ADD, …) появление ассемблеров – машинные команды получают мнемонические имена (LOAD, STORE, ADD, …) конец 50 х – создание первого компилятора для языка FORTRAN (FORmula TRANslator – транслятор формул) конец 50 х – создание первого компилятора для языка FORTRAN (FORmula TRANslator – транслятор формул) более удобное средство для написания формул, чем ассемблер более удобное средство для написания формул, чем ассемблер переносимость кода переносимость кода

3 Ноябрь Особенности архитектуры аппаратной платформы определяют особенности языков программирования Архитектура языков программирования должна быть максимально приближена к архитектуре компьютеров для наиболее эффективного использования его ресурсов. Архитектура языков программирования должна быть максимально приближена к архитектуре компьютеров для наиболее эффективного использования его ресурсов. Компьютер состоит из процессора и памяти – значит программа должна состоять из последовательности инструкций, выполняемых процессором и модифицирующих память. Компьютер состоит из процессора и памяти – значит программа должна состоять из последовательности инструкций, выполняемых процессором и модифицирующих память.

4 Ноябрь Понятие парадигмы Термин «парадигма» - означает набор теорий, стандартов и методов, которые совместно представляют собой способ организации знаний, способ видения мира. Термин «парадигма» - означает набор теорий, стандартов и методов, которые совместно представляют собой способ организации знаний, способ видения мира.

5 Ноябрь Парадигма языка программирования Компьютер представляется в виде туповатого исполнителя, тем не менее поддающегося обучению. Компьютер представляется в виде туповатого исполнителя, тем не менее поддающегося обучению. Исполнитель может исполнять некоторые простейшие команды. Исполнитель может исполнять некоторые простейшие команды. Обучение происходит путем формирования процедур из команд и использования их в дальнейшем вместо повторения последовательности команд. Обучение происходит путем формирования процедур из команд и использования их в дальнейшем вместо повторения последовательности команд. Программа описывает процесс последовательного, пошагового решения задачи. Программа описывает процесс последовательного, пошагового решения задачи.

6 Ноябрь Наклонения предложений в грамматике изъявительное (повествовательные) изъявительное (повествовательные) вопросительное вопросительное повелительное (императивное) повелительное (императивное)

7 Ноябрь Изученные языки С/C++ относятся к императивным языкам. Изученные языки С/C++ относятся к императивным языкам. Другие названия – директивные, процедурные. Другие названия – директивные, процедурные.

8 Ноябрь Программирование в повествовательном наклонении Стиль программирования, в котором программа представляется в как совокупность утверждений получил название декларативный. Стиль программирования, в котором программа представляется в как совокупность утверждений получил название декларативный. Программа на императивном языке программирования предписывает, как достичь требуемую цель; декларативная программа заявляет (декларирует), что должно быть достигнуто в качестве цели. Программа на императивном языке программирования предписывает, как достичь требуемую цель; декларативная программа заявляет (декларирует), что должно быть достигнуто в качестве цели. Наиболее важные разновидности Наиболее важные разновидности функциональное программирование функциональное программирование логическое (реляционное) программирование логическое (реляционное) программирование

9 Ноябрь Особенности декларативного программирования Особое внимание уделяется тому, что нужно сделать, а не тому как этого достичь. Особое внимание уделяется тому, что нужно сделать, а не тому как этого достичь. Описание вычислений производится используя уравнения, функции, логические выводы и т. п Описание вычислений производится используя уравнения, функции, логические выводы и т. п Не используют понятия состояния и не содержат переменных, отсюда: Не используют понятия состояния и не содержат переменных, отсюда: не могут использовать операторы присваивания, так как нечему присваивать; не могут использовать операторы присваивания, так как нечему присваивать; понятие последовательности выполнения команд становится бессмысленным и, значит, бесполезными становятся операторы управления процессом вычислений. понятие последовательности выполнения команд становится бессмысленным и, значит, бесполезными становятся операторы управления процессом вычислений.

10 Ноябрь Предположим, требуется пройти в городе из пункта А в пункт Б. Декларативная программа - это план города, в котором указаны оба пункта, плюс правила уличного движения. Руководствуясь этими правилами и планом города, курьер сам найдет путь от пункта А к пункту Б. Декларативная программа - это план города, в котором указаны оба пункта, плюс правила уличного движения. Руководствуясь этими правилами и планом города, курьер сам найдет путь от пункта А к пункту Б. Императивная программа - это список команд примерно такого рода: от пункта А по ул. Садовой на север до площади Славы, оттуда по ул. Пушкина два квартала, потом повернуть направо и идти до Театрального переулка, по этому переулку налево по правой стороне до дома 20, который и есть пункт Б. Императивная программа - это список команд примерно такого рода: от пункта А по ул. Садовой на север до площади Славы, оттуда по ул. Пушкина два квартала, потом повернуть направо и идти до Театрального переулка, по этому переулку налево по правой стороне до дома 20, который и есть пункт Б.

11 Ноябрь Виды декларативного программирования Функциональное программирование основывается на математическом понятии функции, которая не изменяет свое окружение (в отличии от функций в процедурных языках, допускающих побочные эффекты) Функциональное программирование основывается на математическом понятии функции, которая не изменяет свое окружение (в отличии от функций в процедурных языках, допускающих побочные эффекты) Логическое программирование - программы выражены в виде формул математической логики и компьютер для решения задачи пытается вывести логические следствия из них. Логическое программирование - программы выражены в виде формул математической логики и компьютер для решения задачи пытается вывести логические следствия из них.

12 Ноябрь Достоинства декларативных языков В основе декларативных языков лежит не какая-то машинная модель, а логика и математика. Появляется возможность формализовать знания о проблеме непосредственно в терминах языка программирования. В основе декларативных языков лежит не какая-то машинная модель, а логика и математика. Появляется возможность формализовать знания о проблеме непосредственно в терминах языка программирования. Необходимость иметь дело только (или главным образом) с логическим компонентом значительно упрощает программирование. Необходимость иметь дело только (или главным образом) с логическим компонентом значительно упрощает программирование. Декларативные языки хорошо подходят для программирования параллельных компьютеров. Декларативные языки хорошо подходят для программирования параллельных компьютеров. Пригодность для формальных рассуждений. Пригодность для формальных рассуждений.

13 Ноябрь Недостатки декларативных языков Отсутствует возможность адекватно выразить в программе естественный параллелизм задачи. Отсутствует возможность адекватно выразить в программе естественный параллелизм задачи. Низкая эффективность. Низкая эффективность. - А на той планете есть охотники? - Нет. - Как интересно! А куры там есть? - Нет. - Нет в мире совершенства! - Вздохнул лис. Антуан де Сент-Экзюпери "Маленький принц".

14 Ноябрь Логическое программирование Основано на логике предикатов. Основано на логике предикатов. Основное внимание уделяется описанию структуры прикладной задачи, а не выработке предписаний компьютеру, что ему следует делать. Основное внимание уделяется описанию структуры прикладной задачи, а не выработке предписаний компьютеру, что ему следует делать. Наиболее известный язык логического программирования PROLOG (от французского PROgrammation LOGique) Наиболее известный язык логического программирования PROLOG (от французского PROgrammation LOGique) Пролог часто называют языком искусственного интеллекта - с его помощью решаются задачи создания экспертных систем и систем обработки естественных языков. Пролог часто называют языком искусственного интеллекта - с его помощью решаются задачи создания экспертных систем и систем обработки естественных языков.

15 Ноябрь Пролог Как и для других декларативных языков, при работе с Прологом мы описываем ситуацию (правила и факты) и формулируем цель (запрос), позволяя интерпретатору Пролога найти решение задачи за нас. Как и для других декларативных языков, при работе с Прологом мы описываем ситуацию (правила и факты) и формулируем цель (запрос), позволяя интерпретатору Пролога найти решение задачи за нас. Под интерпретатором Пролога мы будем понимать механизм решения задачи при помощи языка Пролог. Другими словами, интерпретатор языка Пролог - это исполнитель Пролог-программ, т. е. та "активная сила", которая выполняет программы, написанные на Прологе. Под интерпретатором Пролога мы будем понимать механизм решения задачи при помощи языка Пролог. Другими словами, интерпретатор языка Пролог - это исполнитель Пролог-программ, т. е. та "активная сила", которая выполняет программы, написанные на Прологе.

16 Ноябрь Круг задач Пролог задачи, связанные с разработкой систем искусственного интеллекта (различные экспертные системы, программы- переводчики, интеллектуальные игры). задачи, связанные с разработкой систем искусственного интеллекта (различные экспертные системы, программы- переводчики, интеллектуальные игры). обработка естественного языка обработка естественного языка обладает мощными средствами, позволяющими извлекать информацию из баз данных обладает мощными средствами, позволяющими извлекать информацию из баз данных решении задач составления сложных расписаний решении задач составления сложных расписаний не является универсальным языком программирования и не предназначен, например, для решения задач, связанных с графикой или численными методами не является универсальным языком программирования и не предназначен, например, для решения задач, связанных с графикой или численными методами

17 Ноябрь Внешний вид SWI-Prolog

18 Ноябрь Программа на языке Пролог Программа на языке Пролог представляет собой набор фактов и (возможно) правил. Программа на языке Пролог представляет собой набор фактов и (возможно) правил. Если программа содержит только факты, то ее называют база данных. Если программа содержит только факты, то ее называют база данных. Если она содержит еще и правила, то часто используют термин база знаний. Если она содержит еще и правила, то часто используют термин база знаний. Запрос (вопрос) вводится после приглашения и обязательно заканчивается точкой, например, Запрос (вопрос) вводится после приглашения и обязательно заканчивается точкой, например, ?- 5+4<3. No Пролог анализирует запрос и выдает ответ Yes (Да) в случае истинности утверждения и No (Нет) в противном случае или когда ответ не может быть найден.

19 Ноябрь Хранение программ Хранят программы на языке Пролог в текстовых файлах, чаще всего имеющих расширение pl, например, example1.pl. Хранят программы на языке Пролог в текстовых файлах, чаще всего имеющих расширение pl, например, example1.pl. Для того чтобы Пролог мог оперировать информацией, содержащейся в файле, он должен ознакомится с его содержимым (проконсультироваться с ним). Для того чтобы Пролог мог оперировать информацией, содержащейся в файле, он должен ознакомится с его содержимым (проконсультироваться с ним). ?- [example1]. или ?- consult(example1).

20 Ноябрь Термы и объекты Программа на языке Пролог обычно описывает некую действительность. Программа на языке Пролог обычно описывает некую действительность. Объекты (элементы) описываемого мира представляются с помощью термов. Объекты (элементы) описываемого мира представляются с помощью термов. Терм интуитивно означает объект. Терм интуитивно означает объект. Существует 4 вида термов: атомы, числа, переменные и составные термы. Существует 4 вида термов: атомы, числа, переменные и составные термы. Атомы и числа иногда группируют вместе и называют простейшими термами. Атомы и числа иногда группируют вместе и называют простейшими термами.

21 Ноябрь Атом Атом -это отдельный объект, считающийся элементарным. Атом -это отдельный объект, считающийся элементарным. В Прологе атом представляется последовательностью букв нижнего и верхнего регистра, цифр и символа подчеркивания '_', начинающейся со строчной буквы. В Прологе атом представляется последовательностью букв нижнего и верхнего регистра, цифр и символа подчеркивания '_', начинающейся со строчной буквы. Любой набор допустимых символов, заключенный в апострофы является атомом. Любой набор допустимых символов, заключенный в апострофы является атомом. Комбинации специальных символов + - * = : & также являются атомами Комбинации специальных символов + - * = : & также являются атомами

22 Ноябрь Числа Целые (Integer) Целые (Integer) Вещественные (Float) Вещественные (Float)

23 Ноябрь Переменные Переменными в Прологе являются строки символов, цифр и символа подчеркивания, начинающиеся с заглавной буквы или символа подчеркивания Переменными в Прологе являются строки символов, цифр и символа подчеркивания, начинающиеся с заглавной буквы или символа подчеркивания X, _4711, X_1_2, Результат, _x23, Объект 2

24 Ноябрь Анонимная переменная Анонимная переменная (обозначается одним символом подчеркивания) применяется, когда ее значение не используется в программе. Анонимная переменная (обозначается одним символом подчеркивания) применяется, когда ее значение не используется в программе.

25 Ноябрь Составные термы (функции) Составные термы (функции) состоят из имени функции (нечислового атома) и списка аргументов (термов Пролога, то есть атомов, чисел, переменных или других составных термов), заключенных в круглые скобки и разделенных запятыми. Составные термы (функции) состоят из имени функции (нечислового атома) и списка аргументов (термов Пролога, то есть атомов, чисел, переменных или других составных термов), заключенных в круглые скобки и разделенных запятыми. Группы составных термов используют для составления фраз Пролога. Группы составных термов используют для составления фраз Пролога. итого(клиент(X,23,_), 71) итого(клиент(X,23,_), 71) 'Что случилось?'(ничего) 'Что случилось?'(ничего)

26 Ноябрь Факты Программировать на Прологе - значит описывать некий мир. Программировать на Прологе - значит описывать некий мир. Программа на этом языке состоит из множества фраз, задающих взаимосвязь между термами. Программа на этом языке состоит из множества фраз, задающих взаимосвязь между термами. Каждый терм обозначает ту или иную сущность, принадлежащую миру. Один из способов описания - это задание фактов. Каждый терм обозначает ту или иную сущность, принадлежащую миру. Один из способов описания - это задание фактов.

27 Ноябрь Факт Факт - это утверждение о том, что соблюдается некоторое конкретное отношение. Он является безусловно верным. В разговорной речи под фактом понимается нечто вроде "Сегодня солнечно" или Коле 10 лет". На Прологе это запишется в виде Факт - это утверждение о том, что соблюдается некоторое конкретное отношение. Он является безусловно верным. В разговорной речи под фактом понимается нечто вроде "Сегодня солнечно" или Коле 10 лет". На Прологе это запишется в виде 'Сегодня солнечно'. 'Коле 10 лет'.

28 Ноябрь Предикат Предикат - это логическая функция от одного или нескольких аргументов, то есть функция, действующая в множестве из двух значений: истина и ложь. Предикат - это логическая функция от одного или нескольких аргументов, то есть функция, действующая в множестве из двух значений: истина и ложь. Предикат Пролога записывается в виде составного терма: имя_предиката(аргументы). Предикат Пролога записывается в виде составного терма: имя_предиката(аргументы).

29 Ноябрь Аргументы предикатов Аргументы перечисляются через запятую и представляют собой какие-то объекты или свойства объектов, а имя предиката обозначает связь или отношение между аргументами. Аргументы перечисляются через запятую и представляют собой какие-то объекты или свойства объектов, а имя предиката обозначает связь или отношение между аргументами. Предикат однозначно определяется парой: имя и количество аргументов. Предикат однозначно определяется парой: имя и количество аргументов. Пример Факт "Коля работает слесарем" на Прологе запишется следующим образом: Пример Факт "Коля работает слесарем" на Прологе запишется следующим образом: профессия(коля, слесарь).

30 Ноябрь База данных База данных на Прологе - это совокупность фактов. База данных на Прологе - это совокупность фактов. В процессе работы в базу данных можно добавлять новые факты, удалять или изменять старые. В процессе работы в базу данных можно добавлять новые факты, удалять или изменять старые. Пример Составим базу данных из следующих фактов: "слон больше, чем лошадь", "лошадь больше, чем осел", "осел больше, чем собака" и "осел больше, чем обезьяна": Пример Составим базу данных из следующих фактов: "слон больше, чем лошадь", "лошадь больше, чем осел", "осел больше, чем собака" и "осел больше, чем обезьяна": больше(слон, лошадь). больше(лошадь, осел). больше(осел, собака). больше(осел, обезьяна).

31 Ноябрь Запросы к базе данных Запрос - это последовательность предикатов, разделенных запятыми и завершающаяся точкой. Запрос - это последовательность предикатов, разделенных запятыми и завершающаяся точкой. На естественном языке запятая соответствует союзу "и", а на языке математической логики обозначает конъюнкцию. На естественном языке запятая соответствует союзу "и", а на языке математической логики обозначает конъюнкцию. С помощью запросов можно "спрашивать" базу данных о том, какие утверждения являются истинными. С помощью запросов можно "спрашивать" базу данных о том, какие утверждения являются истинными. Предикат запроса называется целью. Предикат запроса называется целью.

32 Ноябрь Примеры запросов ?- 5+4<3. No ?- больше(слон, лошадь). Yes ?- больше(лошадь, слон). No ?- больше(лошадь, корова). No

33 Ноябрь Правила Правило задает новый предикат через определенные ранее. Правило задает новый предикат через определенные ранее. Правило состоит из головы (предиката) и тела (последовательности предикатов, разделенных запятыми). Голова и тело разделены знаком :- Правило состоит из головы (предиката) и тела (последовательности предикатов, разделенных запятыми). Голова и тело разделены знаком :- Правило должно заканчиваться точкой. Правило должно заканчиваться точкой. Запятая в теле правила означает конъюнкцию (&&, логическое и). Запятая в теле правила означает конъюнкцию (&&, логическое и).

34 Ноябрь Правила Знак :- есть схематическая запись стрелки (<-) и показывает, что из правой части следует левая. Этот знак читается как "если". Знак :- есть схематическая запись стрелки (<-) и показывает, что из правой части следует левая. Этот знак читается как "если". Интуитивный смысл правила состоит в том, что цель, являющаяся головой, будет истинной, если Пролог сможет показать, что все выражения (подцели) в теле правила являются истинными. Пример Правило, определяющее отношение ребенок/2 через отношение отец/2, запишется следующим образом: Интуитивный смысл правила состоит в том, что цель, являющаяся головой, будет истинной, если Пролог сможет показать, что все выражения (подцели) в теле правила являются истинными. Пример Правило, определяющее отношение ребенок/2 через отношение отец/2, запишется следующим образом: ребенок(X, Y) :- отец(Y, X). Это означает, что если человек Y является для человека X отцом, то X является ребенком Y. Здесь X и Y - переменные.

35 Ноябрь Правила с рекурсией Т.к. в Прологе отсутствуют операторы управления, то более сложные правила создаются с помощью рекурсии. Т.к. в Прологе отсутствуют операторы управления, то более сложные правила создаются с помощью рекурсии. В Прологе рекурсия встречается, когда предикат содержит цель, которая ссылается на саму себя. В Прологе рекурсия встречается, когда предикат содержит цель, которая ссылается на саму себя. В рекурсивном правиле более сложные входные аргументы должны выражаться через менее сложные. В рекурсивном правиле более сложные входные аргументы должны выражаться через менее сложные. Используя рекурсию как прием программирования мы должны быть уверены, что рекурсивная процедура будет завершена. Используя рекурсию как прием программирования мы должны быть уверены, что рекурсивная процедура будет завершена.

36 Ноябрь Пример рекурсии больше(слон, лошадь). больше(лошадь, осел). больше(осел, собака). больше(осел, обезьяна). больше_2(X, Y) :- больше(X, Y). больше_2(X, Y) :- больше(X, Z), больше_2(Z, Y).

37 Ноябрь Результат использования рекурсивных правил ?- больше(слон, обезьяна). No ?- больше_2(слон, обезьяна). Yes

38 Ноябрь Арифметические действия Для вычисления арифметических выражений в Прологе используется встроенный бинарный оператор is, который интерпретирует правый терм как арифметическое выражение, после чего унифицирует (если возможно) результат вычисления с левым термом (обычно с переменной). Для вычисления арифметических выражений в Прологе используется встроенный бинарный оператор is, который интерпретирует правый терм как арифметическое выражение, после чего унифицирует (если возможно) результат вычисления с левым термом (обычно с переменной). Приоритет выполнения арифметических операций является традиционным. Приоритет выполнения арифметических операций является традиционным. Круглые скобки используются для изменения порядка вычислений. Круглые скобки используются для изменения порядка вычислений. ?- X is X = 5 Yes

39 Ноябрь Встроенные функции X + Y Сумма X и Y X - Y Разность X и Y X * Y Произведение X и Y X / Y Деление X на Y X mod Y Остаток от деления X на Y X // Y Деление нацело X на Y X ** Y Возведение X в степень Y - X Смена знака X abs(X) Абсолютная величина числа X max(X,Y) Большее из чисел X и Y min(X,Y) Меньшее из чисел X и Y sqrt(X) Квадратный корень из X random(Int) Случайное целое число в диапазоне от 0 до Int sin(X) Синус X cos(X) Косинус X tan(X) Тангенс X log(X) Натуральный логарифм (ln) числа X log10(X) Десятичный логарифм (lg) числа X

40 Ноябрь Функциональное программирование (пример - Excel) Функциональное программирование ставит своей целью придать каждой программе простую математическую интерпретацию. Функциональное программирование ставит своей целью придать каждой программе простую математическую интерпретацию. Эта интерпретация должна быть независима от деталей исполнения. Эта интерпретация должна быть независима от деталей исполнения.

41 Ноябрь Семантика ЯП Семантика ЯП задается определением средств описания данных и действий. ЯП Средства описания данных Средства описания действий Базовые средства описания данных Абстрактные типы данных Дополнительные возможности Базовые средства описания действий

42 Ноябрь Язык программирования Средства абстрагирования Средства объединения объектов Элементарные выражения Элементарные выражения – средства для описания и манипулирования примитивными данными Средства объединения объектов – для объединения простых данных и операций в более сложные. Средства абстрагирования – позволяют отвлечься от конкретного устройства сложных объектов и манипулировать ими как едиными сущностями

43 Ноябрь Функциональное программирование использует математическое понятие функции для выражения концепции действия. Подобно обычным математическим функциям, процедуры («функции») функциональных языков отображают одни объекты (аргументы) в другие (значения). В отличие от процедур (функций) императивных языков, значения функций однозначно определяются их аргументами и не зависят от истории вычислительного процесса. Важное различие между математическими функциями и императивными процедурами заключается в том, что процедуры должны быть эффективно определены.

44 Ноябрь Понятие функции используется в функциональных языках программирования и для выражения концепции данных. Функции в функциональных языках являются объектами «первого класса». Элементы первого класса - это элементы с наименьшим количеством ограничений. Важные свойства таких первоклассных элементов: На них можно ссылаться посредством переменных. Их можно включать в структуры данных. Их можно передавать как параметры. Они могут быть возвращены в качестве результата.

45 Ноябрь Язык Лисп Лисп – интерпретатор Лисп – интерпретатор Обычно работа с интерпретатором Лиспа происходит по следующему сценарию: Обычно работа с интерпретатором Лиспа происходит по следующему сценарию: Пользователь вводит выражение. Пользователь вводит выражение. Интерпретатор вычисляет значение этого выражения и печатает результат. Интерпретатор вычисляет значение этого выражения и печатает результат. Мы можем сказать, что все языки отличаются друг от друга, но некоторые отличаются значительно больше, чем другие. Эдуард Сепир

46 Ноябрь Элементарные выражения

47 Ноябрь Выражения и значения выражений. Числовые константы обозначают числа, которые и являются их значениями. Разнообразие доступных типов чисел зависит от реализации языка, но все реализации поддерживают целые и вещественные числа, а многие ещё и рациональные и комплексные Последовательность букв, цифр и специальных знаков, отличающаяся от числа называется символом. Главное их назначение - именовать объекты. Поэтому, значением символа является объект, поименованный этим символом. Hello Error: undefined variable С именем «+» связана встроенная функция, вычисляющая сумму чисел, которая и является значением. + #

48 Ноябрь Значением выражения ' является сам этот символ. Лисп нечувствителен к регистру букв и значение символа приведено к стандартному виду. 'Hello hello Строковые константы записываются в двойных кавычках и представляют последовательности отображаемых знаков."Hello" Две логические константы #t и #f обозначают истину и ложь.#f Константы и символы носят общее имя атомы, поскольку представляют собой простейшие элементы языка, из которых строятся выражения. Выражения и значения выражений.

49 Ноябрь Для записи выражений ( форм в терминологии Лиспа) используется единая префиксная форма: имя функции стоит перед аргументами и записывается внутри скобок (+ 2 2) 4 (* 1.1 2) 2.2 (= 1 2) #f Подобные выражения, описывающие применение функции к аргументам, называются комбинационными формами или комбинациями. Значение комбинации - результат применения функции, указанной первым элементом списка (оператором) к параметрам, которые являются значениями остальных элементов (операндов). В данном случае, операторы - встроенные функции +,*,=. Выражения и значения выражений.

50 Ноябрь Пример более сложного выражения. (+ (* 3 5) (- 10 5)) 20 Общее правило вычисления значения комбинации следующее: 1. Вычислить значение всех подвыражений. 2. Применить функцию, которая является значением оператора к аргументам, которые являются значениями операндов. Таким образом, в Лиспе используется аппликативный порядок вычислений

51 Ноябрь В традиционной математической нотации имя функции стоит перед аргументами, заключенными в скобках. Кроме того, используется инфиксная запись арифметических выражений, разнообразные индексы и специальные знаки. Математическая запись Запись на Лиспе 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)) xyxyxyxy (expt x y) |x| (abs x) x = y (= x y) x + y < z (< (+ x y) z)

52 Ноябрь В сравнении с этим многообразием и даже с синтаксисом большинства языков программирования префиксная форма кажется несколько непривычной и громоздкой. Но она обладает, по крайней мере, одним неоспоримым достоинством - описание синтаксиса умещается на одной строчке: ::= | ( ) Чтобы сделать выражения более читаемыми, многие реализации допускают использование квадратных скобок. (/ [+ (* 3 5) (- 10 5)] 2) 10

53 Ноябрь Несмотря на то, что Лисп - бестиповый язык и любое сочетание аргументов является синтаксически допустимым, в процессе выполнения для каждого значения определяется его тип и попытка применить + к логическому значению вызывает ошибку. Поэтому Лисп называют динамически типизированным языком. Заметим что правила типизации соблюдаются гораздо более строго, чем в Си или даже в Паскале - нет никакой возможности подсунуть функции аргумент не того типа. (1 2 3) Error: attempt to apply a non-procedure 1 не является функцией. Поэтому попытка применить её приводит к ошибке. (+ 1 (= 1 2)) Error in +: #f is not a number.

54 Ноябрь Базовые функции. В Лиспе определён большой набор базовых функций, рассмотрим некоторые из них. Это во- первых арифметические операции (+,-,*,/). Функции + и * имеют произвольное количество аргументов. В принципе, это не очень хорошая практика, но в данном случае она себя оправдывает. Поскольку операции вычитания и деления не ассоциативны, попытка расширить их определение на произвольное количество аргументов может привести к путанице. Однако, для одного аргумента определено, что (- a)выдаёт -a, а (/ a)- 1/a. Неожиданность. Ожидалось скорее 0 или в зависимости от типа данных. Но для непредубежденного человека вполне естественно. Впрочем, если реализация не поддерживает рациональных чисел (что допускается для Scheme) получим Для деления с остатком предназначены функции quotient и remainder, возвращающие целую часть и остаток от деления. ( ) 15 (+ 1) 1 (* ) 120 (- 5) -5 (/ 10 5) 2 (/ 2 3) 2/3

55 Ноябрь Логические функции Функции, возвращающие логические значения, называются предикатами. В Lisp принято названия предикатов (кроме распространённых арифметических операций сравнения =,>, = ) завершать вопросительным знаком или - буквой "p"(от слова predicate). (Подобно + и *, операции сравнения допускают произвольное число аргументов (но, конечно же, не менее двух). Это сделано всё с той же целью - уменьшить сложность выражений. Например (< x1 x2 …xn)вернёт #t, только если аргументы упорядочены по возрастанию. (= 1 2) #f (odd? 2) #f (< 1 2) #t (even? 2) #t

56 Ноябрь Для символов единственная осмысленная операция - сравнение на идентичность. (eq? 'a 'a) #t Может показаться странным использование специального предиката, а не символа равенства. Но мы часто подразумеваем совершенно разные вещи, когда говорим, что два объекта равны. Предикат = сравнивает численные значения двух выражений, а предикат eq? проверяет, что эти выражения именуют один и тот же объект. Поэтому: (= 1 1.0) #t (eq? 1 1.0) #f (eq? 1 1) #t

57 Ноябрь Типовые предикаты Поскольку переменные Лиспа могут принимать значение любого типа, необходимо иметь возможность определять этот тип. Для этого предусмотрены типовые предикаты. (boolean? 1) #f (integer? 1) #t (real? 1.1) #t (procedure? '+) #f (number? 1) #t (integer? 1.1) #f (procedure? +) #t (symbol? '+) #t

58 Ноябрь Логические связки Для представления логических связок используются функции not, or и and. (not x) возвращает #t, если значение аргумента равно #f и #f в противном случае. (or x1 x2 … xn) возвращает значение первого аргумента, не равного #f. Если же все аргументы имеют значение #f, то оно и возвращается. (and x1 x2 … xn) возвращает значение #f, если оно встречается среди значений аргументов. В противном случае возвращается значение последнего аргумента. Любое значение, отличное от #f интерпретируется как истина. (not #f) #t (not 0) #f

59 Ноябрь Условные выражения Если зависимость значений истинности от значений других типов выражается предикатами, а зависимость значений истинности от других значениях истинности логическими связками, то условные выражения - средство для выражения зависимости значений произвольного типа от значений истинности. (if p et ef) возвращает значение ef, если значение p - #f, и et в противном случае. (cond (p1 e1) (p2 e2) … (pn en)) возвращает значение ei, для первого i при котором значение pi отлично от #f.

60 Ноябрь Средства объединения объектов

61 Ноябрь Определения Для определения новых объектов, применяются определяющие формы. (define n e) связывает имя n со значением выражения e. (define (f a1…an) e) определяет новую функцию с именем f. a1…an - формальные параметры, т.е. имена, используемые внутри тела функции для ссылок на соответствующие параметры. e -тело функции, выражение, определяющее её значение. (define x 1) x1 (+ x x) 2 (define x 2) (+ x x) 4

62 Ноябрь (define & and) (& (< 1 2) (< 2 3)) #t Значение and, то есть встроенная функция связывается с именем &, после чего & можно использовать вместо and. (define (sqr x) (* x x)) sqr # (sqr 5) 25 Теперь с именем sqr связана вновь определённая функция и ее можно использовать для возведения в квадрат. Подобно встроенным функциям, она не отображается. Дело в том, что интерпретатор не сохраняет определения как синтаксические деревья, а компилирует их в байт-код.

63 Ноябрь Лямбда-выражения В Лиспе можно отделить два понятия - определение функции, и её именование. Дать имя функции можно все той же конструкцией define (define sqr ) а определить - с помощью специальной формы: лямбда-выражения. (lambda (a1…an) e) возвращает функцию, вычисляющую значение выражения e при подстановке фактических параметров вместо a1…an. Например, sqr можно было бы определить и так (define sqr (lambda (x) (* x x))) Лямбда-выражение может использоваться всюду, где используется имя функции, например как оператор в комбинации вида. ([lambda (x) (* x x)] 2) 4

64 Ноябрь Связывающие формы Иногда выражение содержит повторяющиеся части. Чтобы упростить запись таких выражений этим частям можно присвоить локальные имена с помощью связывающий формы let. (let ((a1 e1)(a2 e2) … (an en)) e) Значением этой формы будет значение выражения e, в котором каждое ai заменено значением выражения ei. Например, функция для вычисления площади треугольника по формуле Герона. (define (square-triangle a b c) (let ((p (/ (+ a b c) 2))) (sqrt (* p (- p a) (- p b) (- p c))))

65 Ноябрь Того же эффекта можно было бы добиться применяя лямбда-выражение. (define (square-triangle a b c) [(lambda (p) (sqrt (* p (- p a) (- p b) (- p c)))) (/ (+ a b c) 2 )]) Семантически это одно и то же, но, запись с let намного нагляднее.

66 Ноябрь Составные данные Любые два объекта можно объединить в новый объект, называемый (точечной) парой с помощью примитивной функции cons. Чтобы получить составные части пары, используются функции car и cdr. (cons a b) - возвращает составной объект - пару (a. b) (car (cons 1 2) ) - возвращает первый элемент пары (1) (cdr (cons 1 2) ) - возвращает второй элемент пары (2) (define x (cons 1 2)) x (1. 2) (car x) 1 (cdr x) 2

67 Ноябрь При обработке таких структур необходимо иметь возможность определить является ли выражение атомом или парой. Это делается встроенным предикатом pair?. (pair? a) возвращает #t, если аргумент представляет собой пару и #f в противном случае.

68 Ноябрь Вложенные цепочки пар называются списками. (cons 1 (cons 2 (cons 3 () ))) (1 2 3) Списки играют особую роль в Лиспе. Чтобы упростить их формирование, предусмотрена специальная функция list. (list a1…an) возвращает список объектов (a1…an), то есть (a1.(a2. …(an. nil)…)). (list 1 2 3) (1 2 3) (car (list 1 2 3)) 1 (cdr (list 1 2 3)) (2 3)

69 Ноябрь В действительности, выражения Лиспа представляют собой ни что иное, как списки. Это даёт возможность обрабатывать их как данные. Чтобы получить выражение как таковое, а не его значение используется специальная форма quote. (quote a) - возвращает в качестве значения свой аргумент, не вычисляя его. Аналог – знак апострофа. (quote a) а''a (car '(+ 1 2)) + 'аа '(+ 1 2) (+ 1 2)

70 Ноябрь Противоположность quote - функция eval, вычисляющая значение выражения. (eval '(+ 1 2)) 3 (eval (list + 1 2)) 3

71 Ноябрь Рекурсивные определения. Для того чтобы рекурсивное определение было полезным необходимо выполнение следующих двух условий: 1. Наличие нерекурсивного определения для базового случая. 2. Параметр рекурсивного обращения должен быть «проще», чем параметр определяемой функции.

72 Ноябрь Вычисление факториала Факториал положительного целого числа 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

73 Ноябрь Числа Фибоначчи Определение чисел Фибоначчи само по себе рекурсивно. Каждое число в последовательности, кроме двух первых является суммой двух предшествующих. F1 = 1 F2 = 1 Fn = Fn-1+ Fn-2. Это определение непосредственно записывается на Лиспе. (define (fib n) (cond ((= n 1) 1) ((= n 2) 1) ((> n 2) (+ (fib (- n 1)) (fib (- n 2))))))

74 Ноябрь Наибольший общий делитель (НОД) НОД двух натуральных чисел 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) )))

75 Ноябрь Вопросы к экзамену Декларативное программирование. Парадигма, особенности, достоинства и недостатки. История развития. Пример. Декларативное программирование. Парадигма, особенности, достоинства и недостатки. История развития. Пример. Логическое программирование. Особенности. Круг задач. Логическое программирование. Особенности. Круг задач. Язык Пролог. Язык Пролог. Особенности реализации. Программа на языке пролог. Особенности реализации. Программа на языке пролог. Термы и объекты. Атомы, числа, переменные и составные термы, переменные. Термы и объекты. Атомы, числа, переменные и составные термы, переменные. Факты и предикаты. Факты и предикаты. Базы данных, запросы, правила, рекурсии. Пример программы. Базы данных, запросы, правила, рекурсии. Пример программы.

76 Ноябрь Вопросы к экзамену (продолжение) Функциональное программирование. Использование понятия функции. Функциональное программирование. Использование понятия функции. Язык Лисп. Язык Лисп. Особенности реализации. Порядок работы. Простейшие выражения. Описание синтаксиса выражений. Особенности реализации. Порядок работы. Простейшие выражения. Описание синтаксиса выражений. Типизация. Базовые функции. Логические функции. Типовые предикаты. Условные выражения. Типизация. Базовые функции. Логические функции. Типовые предикаты. Условные выражения. Средства объединения объектов. Определения. Лямбда- выражения. Связывающие формы. Пример нахождения наибольшего общего делителя. Средства объединения объектов. Определения. Лямбда- выражения. Связывающие формы. Пример нахождения наибольшего общего делителя. Составные данные. Списки. Обработка выражений как списков. Пример вычисления чисел Фибоначчи. Составные данные. Списки. Обработка выражений как списков. Пример вычисления чисел Фибоначчи. Рекурсивные определения. Пример вычисления факториала. Рекурсивные определения. Пример вычисления факториала.