- •Введение
- •Понятие функционального программирования
- •Языки функционального программирования
- •Лямбда-исчисление Введение в лямбда-исчисление
- •Алонсо Черч
- •Иллюстрация ромбического свойства на примере
- •Прикладные лямбда-исчисления
- •Данные и выражения языка Lisp. Понятия списков и атомов, вычисление функций.
- •Организация памяти Lisp-машины
- •Функции проверки типов и логические функции
- •Манипуляция элементами списков
- •Основные конструкции Лямбда - выражения и пользовательские функции
- •Последовательности вычислений
- •Условные операторы и циклы
- •Рекурсия
- •Проверка на вхождения атома в список
- •Удаление из списка n-ного элемента
- •Добавление в список элемента в позицию n
- •Функционалы
- •Макросы
- •Ввод и вывод
- •Типы данных Иерархия типов
- •Символы
- •Последовательности
- •Массивы
- •Структуры
- •Лабораторные работы Лабораторная работа 1
- •Лабораторная работа 2
- •Лабораторная работа 3
- •Дана схема метрополитена, найти кратчайший путь между станциями.
- •Игра в 15.
- •Задача о 8-ми ферзях.
- •Задача о 8-ми ферзях 2.
- •Задача о Ханойской башне.
- •Задача о составлении расписания
- •Раскрасить плоскую карту четырьмя цветами, так что бы любые две смежные области не были окрашены в один цвет
- •Задача о коммивояжере.
- •Лабораторная работа 4
Последовательности вычислений
В языке Lisp существует возможность организации последовательностей вычислений, вплоть до поддержки процедурного стиля программирования. Для этого служат различные специфичные конструкции, часть из которых будут описана в этом разделе.
let |
(LET ( (локальная_переменная1 значение1) ( локалная_переменная2_значение2 )… ) форма1 форма2 … ) Создаёт локальную связь. Содержит в своём первом параметре список, каждый элемент которого представляет собой пару "локальная переменная - значение" и выполняется в начале вычисления оператора. Остальными параметрами LET являются вычисляемые формы, значение последней из которых возвращается в качестве результата. Необходимо отметить, что результат модификации локальных переменных по завершении оператора не сохраняется. |
>(SETQ A 1) 1 >(LET ((A 2)) (+ A 1)) 3 >A 1 |
Отметим, что в данном случае оператор LET содержал в себе одну форму (+ A 1) и, в то же время, естественно, сам являлся формой. В качестве параметра-формы LET вполне мог использоваться другой оператор LET или любой другой оператор.
prog1 prog2 prong |
(progn форма1 форма2 форма3…) Позволяет выполнять последовательные вычисления форм. Возвращается значение, соответственно, первой, второй и последней формы. |
>(PROG1 1 2 3) 1 >(PROG2 1 2 3) 2 >(PROGN 1 2 3) 3 |
Естественно, применение этой конструкции может быть и более сложным:
>(progn (setq A 5) (setq B 7)) 7 >A 5 >B 7 |
Условные операторы и циклы
Для того, чтобы решать задачи, необходимо обеспечивать разветвление алгоритмов, в частности, языку особенно необходимы условные конструкции и циклы. Здесь мы рассмотрим некоторые из них, имеющие наиболее частое применение, и начнём с операторов условия.
cond |
(cond (условие1 форма1) (условие форма2)…) Реализует таблицу решений. В зависимости от выполняемого условия возвращает сопоставленное ему выражение. Аргументами COND являются списки из двух элементов, первый из которых указывает на условие, а второй определяет, какое значение при выполнении этого условия должен вернуть COND. Если ни одно условие не подойдёт, возвращается NIL. Ветви просматриваются последовательно, и как только одно из условий оказывается истинным, выполнение COND завершается |
COND является наиболее общей формой условного оператора. Все остальные условные операторы могут быть выражены через него. Примером использования может быть некая таблица решений, например, вывести день недели по его номеру:
>(SETQ DAY 3) 3 >(COND ((EQL DAY 1) "Monday") ((EQL DAY 2) "Tuesday") ((EQL DAY 3) "Wednesday") ((EQL DAY 4) "Thursday") ((EQL DAY 5) "Friday") ((EQL DAY 6) "Saturday") ((EQL DAY 7) "Sunday") (T "Check your calendar") ) "Wednesday" |
При попытке выполнить пример необходимо обратить внимание, что дни недели, написанные по-русски, некоторые интерпретаторы не понимают. Также заметим, что последним условием является T - это условие по умолчанию, оно всегда выполнится, если только до него не выполнилось уже какое-то другое. Естественно, условие NIL бессмысленно.
if |
(if условие форма-для-истинности форма-для-ложности) Реализует простой условный оператор. Содержит три аргумента - условие, результат, если условие истинно, результат, если условие ложно. Соответствует оператору (cond (Условие результат-при-истинном-условии) (T результат-при-ложном-условии)) |
В качестве примера приведём следующий код, пытающийся определить, является ли число натуральным:
>(SETQ NUMBER 100) 100 >(IF (> NUMBER 0) "Natural" "Not Natural") "Natural" >( SETQ NUMBER -100) -100 >(IF (> NUMBER 0) "Natural" "Not Natural") "Not Natural" |
Наконец, можно использовать также дополнительные виды условных операторов, такие как WHEN, UNLESS, CASE.
when |
(when условие значение-при-истинности) Модифицированный вариант оператора COND, содержит в качестве параметров одно условие (первый параметр) и несколько форм, которые вычисляются последовательно при истинности условия. Возвращается значение последней вычисленной формы. |
unless |
(unless значение-при-ложности) То же самое, что и WHEN, однако формы вычисляются, если условие ложно. |
case |
(case ключ (список-ключей форма1 форма2…) (список-ключей форма1 форма2…)…) Традиционная таблица решений (сходна с соответствующим оператором языка Pascal). Содержит первый параметр - ключ, который вычисляется перед обработкой всех остальных параметров. Остальные параметры состоят каждый из списка ключей и последовательности вычисляемых форм, причём вычисляются формы (и возвращается последняя из них) в том случае, если значение ключа CASE было найдено в списке ключей одного из параметров. |
Приведём примеры использования соответствующих функций. Используем наш старый пример с определением того, является ли число натуральным (в противном случае возвращается NIL):
>(SETQ NUMBER 100) 100 >(SETQ NUMBER 100) 100 >(WHEN (> NUMBER 0) "Natural") "Natural" >(UNLESS (> NUMBER 0) "Not Natural") NIL >( SETQ NUMBER -100) -100 >(WHEN (> NUMBER 0) "Natural") NIL >(UNLESS (> NUMBER 0) "Not Natural") "Not Natural" |
А также модифицированная версия таблицы решений относительно дней недели:
>(SETQ DAY 3) 3 >(CASE DAY (1 "Monday") (2 "Tuesday") (3 "Wednesday") (4 "Thursday") (5 "Friday") (6 "Saturday") (7 "Sunday") (T "Check your calendar") ) "Wednesday" |
Теперь рассмотрим операторы циклов
do |
(do ((переменная начальное-значение приращение)…) (условие-окончания форма1 форма2 …) форма 11 форма12…) Функция является наиболее общим вариантом организации циклов. Реализуется в форме DO Инициализация Условие Тело цикла. Инициализация является списком правил, каждое из которых состоит из имени переменной, начального значения и приращения, Условие состоит из собственно условия выхода и вычисляемых форм, которые вычисляются при возврате функцией значения (как обычно, возвращается последняя). Наконец тело представляет собой последовательность вычисляемых форм, которые выполняются каждый раз при новой итерации. К сожалению, не во всех версиях Lisp поддерживается приращение итератора. В таких слуяаях необходимо выполнять её приращение отдельным кодом. |
Примером работы с оператором DO может служить программа, вычисляющая факториал числа (этот пример достаточно показателен в следствие последующего изложения эквивалентности решений с помощью циклов и рекурсии).
>(defun f1 (x) (do ((res 1) (rs 1)) ((eql x 0) rs) (setq rs (* res rs)) (setq x (- x 1)) (setq res (+ res 1)) )) F1 >(f1 5) 120 |
Существует и более простой в обращении цикл LOOP:
loop |
(loop форма 1 форма2…) Функция повторяет вычисление своих форм до тех пор, пока среди них не встретится оператор RETURN |
return |
(return результат) Функция позволяет выйти из цикла и вернуть значение для операторов LOOP и PROG. |
Модифицируем факториал с помощью LOOP:
>(defun f1 (x) (progn (setq res 1) (loop (setq res (* res x)) (setq x (- x 1)) (if (eql x 0) (return res)) ))) F1 >(f1 5) 120 |
Наконец, последним алгоритмическим средством, рассматриваемым в этом разделе, является оператор PROG, позволяющий выполнять программирование в традиционном процедурном стиле. Сразу отметим, что оператор PROG не имеет почти ничего общего с PROG1 и PROGN.
prog |
(prog(переменная1 переменная2… ) оператор1 оператор2…) позволяет программировать в традиционном процедурном стиле, используя передачу управления между последовательными операторами. Позволяет использовать в качестве своих форм операторы GO и RETURN |
go |
(go метка) Функция позволяет выполнить внутри оператора PROG переход на некоторую метку. Форма считается меткой если она является символом или числом. |
Приведём в качестве примера работы с функцией PROG следующий код, вычисляющий степень некоторого числа.
>(defun exp1 (x n) (prog (res) (setq res x) loop (if (= n 1) (return res)) (setq res (* res x)) (setq n (- n 1)) (go loop) ) ) EXP1 >(exp1 2 3) 8 |
