ЗАДАНИЯ И МЕТОДИЧЕСКИЕ УКАЗАНИЯ
к лабораторной работе
по дисциплине «Функциональное программирование»
для студентов 4 курса
дневного отделения факультета АВТ,
обучающихся по направлению
09.04.01 Программная инженерия
Лабораторная работа №1.
Основы функционального программирования
(4 часа)
Цель работы:
Приобретение практических навыков написания и отладки программ на языке функционального программирования Lisp.
Задание:
В соответствии с вариантом написать программу на языке функционального программирования Lisp.
Вариант 1:
- Определить рекурсивную функцию, возвращающую значение n-го члена ряда Фибоначчи: f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2).
- Определить функцию, вычисляющую, сколько всего атомов в списке (списочной структуре).
Вариант 2:
- Определить рекурсивную функцию для удаления последнего элемента списка.
- Определить функцию, вычисляющую глубину списка (самой глубокой ветви).
Вариант 3:
- Определить рекурсивную функцию, возвращающую произведение двух целых положительных чисел (использовать суммирование).
- Определить функцию, возвращающую предпоследний элемент списка.
Вариант 4:
- Определить рекурсивную функцию, возвращающую последний элемент списка.
- Определить функцию, подсчитывающую число элементов списка без какого-либо указываемого элемента.
Вариант 5:
- Определить рекурсивную функцию, возвращающую значение суммы ряда целых четных чисел от 2 до n.
- Определить функцию (first_elem x y), которая возвращает первый элемент, входящий в оба списка x и y, в противном случае nil.
Вариант 6:
- Определить рекурсивную функцию, возвращающую значение n-го члена ряда Фибоначчи: f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2).
- Определить функцию, вычисляющую, сколько всего атомов в списке (списочной структуре).
Вариант 7:
- Определить рекурсивную функцию для удаления последнего элемента списка.
- Определить функцию, вычисляющую глубину списка (самой глубокой ветви).
Вариант 8:
- Определить рекурсивную функцию, возвращающую произведение двух целых положительных чисел (использовать суммирование).
- Определить функцию, возвращающую предпоследний элемент списка.
Вариант 9:
- Определить рекурсивную функцию, возвращающую последний элемент списка.
- Определить функцию, подсчитывающую число элементов списка без какого-либо указываемого элемента.
Вариант 10:
- Определить рекурсивную функцию, возвращающую значение суммы ряда целых четных чисел от 2 до n.
- Определить функцию (first_elem x y), которая возвращает первый элемент, входящий в оба списка x и y, в противном случае nil.
Содержание отчета (отчет в электронном виде):
- титульный лист (образец можно скачать по адресу http://ermak. cs. nstu. ru/funcprog/fp_labwork_title_page. doc);
- цель работы;
- задание;
- исходные тексты программ;
- выводы по работе.
Теоретические сведения
Базовые функции
В Lisp’е существует пять основных функций, называемых базовыми:
- (car list) — отделяет голову списка (первый элемент списка);
- (cdr list) — отделяет хвост списка (все элементы, кроме первого, представленные в виде списка);
- (cons head tail) — соединяет элемент и список в новый список, где присоединенный элемент становится головой нового списка;
- (equal object1 object2) — проверяет объекты на равенство;
- (atom object) — проверяет, является ли объект атомом.
Так как функции equal и atom возвращают значения nil или t, их можно назвать базовыми предикатами.
Рассмотрим примеры для перечисленных функций:
> (car ‘(one two three))
ONE
> (car ‘(one))
ONE
> (car ‘())
NIL
> (cdr ‘(first second third))
(SECOND THIRD)
> (cdr ‘(first))
NIL
> (cdr ‘())
NIL
> (cons 1 ‘(2 3))
(1 2 3)
> (cons 1 nil)
(1)
> (cons nil nil)
(NIL)
> (equal ‘(1 2 3) ‘(1 2 3))
T
> (equal ‘(1 2 3) ‘(3 2 1))
NIL
> (equal ‘one ‘two)
NIL
> (atom ‘one)
T
> (atom 1)
T
> (atom (1))
NIL
Предложения prog1, prog2, progN
(progX form1 form2 … formN)
Назначение: выполнение последовательных вычислений.
Пример:
>(progn (setq x 2) (setq y (* 3 x)))
6
Предложение cond
(cond (predicate1 form1) (predicate2 form2) … (predicateN formN))
Назначение: выполнение ветвления.
Пример: функция, определяющая тип выражения (пустой список, атом или список).
>(defun deftype(arg)
(cond ((null arg) ‘empty) ((atom arg) ‘atom) (t ‘list)))
DEFTYPE
>(deftype ‘(a b c))
LIST
>(deftype (atom ‘(a t o m)))
EMPTY
Предложение if
(if (condition) thenform elseform)
Назначение: выполнение ветвления.
Пример:
>(setq x ‘(a b c))
(A B C)
>(if (atom x) ‘atom ‘list)
LIST
Предложение do
(do ((var1 value1) (var1 value1) … (var1 value1))
(endcondition form11 form12)
form 21 form 22)
Назначение: выполнение циклических вычислений.
Пример: вычисление суммы целых чисел от n до 0.
>(defun count (n)
(do ((result n)) ;;начальное значение
((= n 0) result) ;;условие окончания цикла
(setq n (- n 1))
(setq result (+ result n))
)
)
COUNT
>(count 5)
15
Простая рекурсия
Функция является рекурсивной, если в ее определении содержится вызов этой же функции. Рекурсия является простой, если вызов функции встречается в некоторой ветви лишь один раз. Простой рекурсии в процедурном программировании соответствует обыкновенный цикл.
Пример: построение копии списка.
>(defun listcopy (list)
(cond ((null list) nil) ;;граничное условие
(t (cons (car list) (listcopy (cdr list)))))) ;;рекурсия
LISTCOPY
>(listcopy ‘(a b c))
(A B C)
Трассировка программы
Для отладки программы можно использовать возможности трассировки. Трассировка позволяет проследить процесс нахождения решения.
Для того, чтобы включить трассировку, можно воспользоваться следующей директивой:
(trace function)
Назначение: включает режим трассировки.
Пример:
>(trace listcopy)
(LISTCOPY)
>(listcopy '(a b))
Entering: LISTCOPY, Argument list: ((A B))
Entering: LISTCOPY, Argument list: ((B))
Entering: LISTCOPY, Argument list: (NIL)
Exiting: LISTCOPY, Value: NIL
Exiting: LISTCOPY, Value: (B)
Exiting: LISTCOPY, Value: (A B)
(A B)
(untrace function)
Назначение: отключает режим трассировки.
Пример:
>(untrace listcopy)
NIL
