Описание лабораторных работ по функциональному программированию на языке ЛИСП

Описание лабораторных работ по функциональному программированию на языке ЛИСП

Рекурсивные функции

Лисп специально создавался для рекурсивных вычислений, и вся си­ла языка как раз и заключена в возможности широкого использования ре­курсивных функций. К примеру вычисления фак­ториала:

(defun factorial (n)

(cond ((zerop n) 1)

(t (* (factorial (- n i)) n))))

Процесс рекурсивных вызовов можно исследовать, используя воз­можности трассировки. Включение и выключение меха­низма трассировки выполняется с помощью входящих в состав интерпре­татора директив TRACE и UNTRACE:

 

Рис. 1. Схема рекурсивных вызовов при вычислении факториала числа 4.

Лисп позво­ляет также эффективно определять рекурсивные функции для обработки символьных данных. Определим упрощенную версию функции MEMBER. Чтобы отличать ее от функции, встроенной в систему назовём ее MY-MEMBER. Функция проверяет, входит ли элемент X в список Y и воз­вращает подсписок Y, который начинается с обнаруженного элемента:

(defun my-member (x у)

(cond ((null у) nil)

((equal x (first у)) у)

(t (my-member x (rest у)))))

В функции выполняется сравнение элемента X с первым элементом списка Y. Если обнаруживается совпадение, то функция возвращает спи­сок У. Если совпадение не обнаружено, то продолжается поиск элемента X в хвосте списка У. Для этого рекурсивно вызывается функция MY-MEMBER. Первое условие формы COND на каждом шаге рекурсии контролирует спи­сок У. Если этот список исчерпан, то определяемая функция MY-MEMBER возвратит значение NIL. Функция MY-MEMBER использует простую рекур­сию.

Примером функции, выполняющей символьную обработку и осно­ванной на параллельной рекурсии, может служить рекурсивная версия функции MY-INTERSECTION:

(defun my-intersection (a b) (cond

((null a) nil)                       ;1)

((member (first a) b)           ;2)

(cons (first a)(my-intersection (rest a) b)))
(t (my-intersection (rest a) b))));3)

Данная функция вычисляет список общих элементов двух списков А и В. В определении функции реализованы три правила:

1. если список А исчерпан, то список общих элементов пустой;

2. если первый элемент списка А входит в список В, то этот элемент   

добавляется к списку общих элементов списков (REST А) и В; такой     

список формируется рекурсивным вызовом функции MY- INTERSECTION, применяемой к хвосту списка А и исходному списку В;

3. если первый элемент списка А не входит в список В, то строится список общих элементов из хвоста списка А и списка В с помощью рекурсивного вызова функции MY-INTERSECTION.

 Ввод-вывод

При работе с интерпретатором Лиспа ввод-вывод выполняется ав­томатически. Интерпретатор читает вводимое пользователем s-выражение (READ), вычисляет его (EVAL) и выводит результаты (PRINT). В простей­шем случае функция READ не требует аргументов. После вызова этой функции происходит обращение к стандартному входному потоку и счи­тывание введенного пользователем s-выражения. Введенное выражение возвращается в точку вызова READ.

Определим функцию, которая находит сумму четырех введенных с клавиатуры чисел:

(defun sum4 ()

(+ (read) (read) (read) (read))

Для вызова этой функции необходимо напечатать (sum4), а затем ввести четыре числа:

> (sum 4)

1 234

─ > 10

 >

Если требуется вводить данные из файлов, то сначала необходимо открыть с помощью функции OPEN соответствующий входной поток:

(setf vvod (open "extern.dat" direction:input))

Для чтения выражений из открытого потока WOD необходимо со­общить его имя функции READ, т.е.

(read vvod)

В этом случае произойдет обращение к файлу "extern.dat", и из него будет считано одно s-выражение. Результатом вызова функции READ будет s-выражение, введенное из файла.

Для вывода значений в Лиспе используется функция PRINT. Эта функция имеет один аргумент, значение которого выводится в выходной поток. Функция PRINT перед выводом значения осуществляет переход на новую строку, а после печати значения выводит пробел

(print '(abc))

(a b с)

─ > (А В С)

Здесь список (А В С) дважды отображается на экране. Дополнительный автоматический вызов функции PRINT происходит в цикле READ-EVAL-PRINT интерпретатора.

Для вывода значений могут также использоваться функции PRIN 1 и PRINC. Функция PRIN 1 аналогична PRINT, но не выполняет переход на но­вую строку и не выводит пробел. Функция PRINC дает возможность напе­чатать строку без ограничивающих кавычек:

(princ "lisp") ─ > lisp

Для перехода при выводе значений на новую строку можно исполь­зовать функцию TERPRI. У функции TERPRI нет аргументов. Если требует­ся вывести на печать имя символа, содержащее пробелы, скобки или строчные и заглавные буквы, то применяют знак отмены "\" или ограничи­вающие вертикальные линии "|". Все рассмотренные функции вывода по­зволяют осуществлять вывод в выходной поток открытый, с помощью функции OPEN:

(serf stran (open "extern.dat" direction:output:if-exists:append))

(print '|a b с d| stran) ─>  |a b с d|

(print '\a\C \ \d stran) ─>  |aC d|

(princ '|a b с d| stran) ─ > |a b с d|

Здесь вторым аргументом функции является выходной поток STRAN, связанный с файлом EXTERN. DAT.

При работе с файлами удобно использовать макроформу WITH-OPEN-FILE. Она позволяет открыть поток, задать режим работы с ним, выполнить необходимую его обработку и закрыть его:

(with - open - file (поток имя-файла {опция}*) {декларация}* {форма}*)

Вызов WITH-OPEN-FILE базируется на использовании функции OPEN. Ре­жимы открытия потока задаются с помощью аргумента опция. Они полно­стью соответствуют ключевым параметрам, указываемым при вызове функции OPEN. Формы вызова WITH-OPEN-FILE вычисляются последова­тельно. В качестве результата возвращается значение последней формы. В приведенном ниже примере открывается поток с именем STORE, который связывается с файлом TEST1.LSP. В файл циклически записываются s-выражения, вводимые с клавиатуры. Формирование файла завершается, если с клавиатуры вводится атом EOF:

(defun writer ()

(with-open-file (store "testl.lsp": direction:output

    : if-exists: append

    : if-does-not-exist:create)

(princ "Введите s -выражение")

(terpri)

(princ "Для завершения ввода напечатайте EOF ")

(terpri)

(do ((item (read) (read))); чтение s- выражения

((eq item 'eof) 'end-of-session)

(print item store))))

Для управления формой вывода в Коммон Лиспе применяется функ­ция FORMAT:

(format поток шаблон & REST аргументы)

Если поток задан символом Т, то функция осуществляет вывод на экран. Шаблон представляет собой строку, которая может содержать коды для управления печатью. Перед управляющими кодами записывается знак "~" (тильда). Если в шаблоне нет управляющих кодов, то функция FORMAT выводит строку шаблона так же, как и функция PRINC.

 

Практическая часть

1. Представить следующие списки в виде списочных ячеек:

· '(open close halph)           

· '((TOOL) (call))  

· '((open1) (close2) (halph3))    

· '((TOOL1) (call2)) ((sell)))

· '((one) for all (and(me(for you))))

· '(((TOOL) (call)) ((sell)))

 

2. Используя только функции CAR и CDR, написать выражения,

возвращающие:

1) второй; 2) третий; 3) четвертый элементы заданного списка.

     

3. Что будет в результате вычисления выражений

а) (CAADR '((blue cube) (red pyramid))) c) (CADR '((abc) (def) (ghi)))

b) (CDAR '((abc) (def) (ghi)))       d) (CADDR '((abc) (def) (ghi)))

    

4. Напишите результат вычисления выражений:

(list 'Fred 'and Wilma)      (cons 'Fred '(and Wilma))

(list 'Fred '(and Wilma))    (cons 'Fred '(Wilma))

(cons Nil Nil)               (list Nil Nil)

(cons T Nil)                 (list T Nil)

(cons Nil T)                 (list Nil T)

(list Nil)                       (cons T (list Nil))

(cons (T) Nil)               (list (T) Nil)

(list '(one two) '(free temp)) (cons '(one two) '(free temp))  

   

5. Написать функцию (f ar1 ar2 ar3 ar4) -> ((ar1 ar2) (ar3 ar4)).

Написать функцию (f ar1 ar2) -> ((ar1) (ar2)).

Написать функцию (f ar1) -> (((ar1))).

Представить результаты в виде списочных ячеек.    

6. Запишите последовательности вызовов CAR и CDR, выделяющие из

приведенных ниже списков символ «а».

    а) (1 2 3 а 4)

    б) (1 2 3 4 а)

    в) ((1) (2 3) (а 4))

    г) ((1) ((2 3 а) (4)))

    д) ((1) ((2 3 а 4)))

    е) (1 (2 ((3 4 (5 (6 а))))))

 

  7. Каково значение каждого из следующих выражений:

• (ATOM (CAR (QUOTE ((1 2) 3 4))));

• (NULL (CDDR (QUOTE ((5 6) (7 8)))));

• (EQUAL (CAR (QUOTE ((7)))) (CDR (QUOTE (5 7))));

• (ZEROP (CADDDR (QUOTE (3 2 1 0))));

 

  8. Проделайте следующие вычисления с помощью интерпретатора Лиспа:

    а) 3.234*(45.6+2.43)

    б) 55+21.3+1.54*2.5432-32

    в) (34-21.5676-43)/(342+32*4.1)

 

  9. Определите значения следующих выражений:

    а) ‘(+ 2 (* 3 5))

    б) (+ 2 ‘(* 3 5))

    в) (+ 2 (’ * 3 5))

    г) (+ 2 (* 3 ’5))

    д) (quote ‘quote)

       е) (quote 6)

Оформление отчета

Отчет по работе должен включать исходные тексты выполненных программ и целями, с которыми они работали, и должен содержать:

· Цель работы.

·    Описание всех заданий с внутренними целями и полученными результатами

 

 

Практическая часть

Выполните индивидуальные задания из Приложения 1.

Оформление отчета

Отчет по работе должен включать исходные тексты выполненных программ и целями, с которыми они работали, и должен содержать:

· Цель работы.

·    Описание всех заданий с внутренними целями и полученными результатами

 

Практическая часть

Выполните индивидуальные задания из Приложения 1.

Оформление отчета

Отчет по работе должен включать исходные тексты выполненных программ и целями, с которыми они работали, и должен содержать:

· Цель работы.

·    Описание всех заданий с внутренними целями и полученными результатами

 

Практическая часть

Выполните индивидуальные задания из Приложения 3.

Оформление отчета

Отчет по работе должен включать исходные тексты выполненных программ и целями, с которыми они работали, и должен содержать:

· Цель работы.

·    Описание всех заданий и полученные результаты.

Описание лабораторных работ по функциональному программированию на языке ЛИСП