litceysel.ru
добавить свой файл
1
ЛЕКЦИЯ 3


1.7 Функции ввода-вывода и работа с файлами

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

Функция LOAD
подает файл на вход интерпретатору Лиспа для дальнейшей обработки. Результатом работы функции будет имя файла, если файл был найден и успешно обработан или nil в противном случае. Вызов функции имеет вид:

(LOAD ‘имя_файла).

Имя файла должно начинаться с буквы! Если не указано расширение файла, то автоматически приписывается расширение lsp. Файл ищется в текущей папке, откуда был запущен Лисп. Для доступа к файлу, находящемуся во вложенной в текущую папку папке, следует указать путь от текущей папки. В остальных случаях следует набрать полный путь, заменив каждый \, встречающийся в описанном пути, на \\.

Примеры:


  1. (LOAD ‘lab1)  lab1.lsp, успешно загружен файл lab1.lsp, находящийся в текущей папке;

  2. (LOAD ‘..\\labs\\lab5)  lab5.lsp, успешно загружен файл lab5.lsp, находящийся в папке labs на уровень выше, чем текущая папка;

  3. (LOAD ‘c:\\lang\\lisp\\labs\\lab2.txt)  lab2.txt, успешно загружен файл lab2.txt, находящийся по указанному пути.

Для ввода с клавиатуры (по умолчанию) или из открытого для ввода файла, используется функция READ. Функция возвращает введенное с клавиатуры s-выражение. Вызов функции имеет вид:


( READ).

Для ввода значений в переменную используют композицию функций SETQ
и READ:

(SETQ
переменная (READ)).

Мы уже видели, что все значения, возвращаемые функциями, и значения переменных, набранных в командной строке, автоматически выводятся на экран. Если обращение к функции производится из файла, который обрабатывается интерпретатором, то для вывода возвращаемых значений на экран используют функции PRINT
, PRINC.

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

( PRINT S), где S – s-выражение или строка, заключенная в кавычки.

Функция PRINC возвращает значение аргумента и, в качестве побочного эффекта, выводит на экран или в открытый для вывода файл это значение. Вызов функции имеет вид:

(PRINC S), где S – s-выражение или строка, заключенная в кавычки.

В Лиспе можно использовать строки, при этом строка заключается в кавычки. Вывод строки сопровождается заключением ее в специальные символы: ||. Для того чтобы убрать эти специальные символы, следует установить значение специальной системной переменной print-escape равным nil с помощью функции SETQ
: (SETQ *print-escape* nil).

Функция TERPRI всегда возвращает nil и, в качестве побочного эффекта, осуществляет переход на следующую строку указанное значением параметрa количество раз. Вызов функции имеет вид:

( TERPRI вычислимое_выражение).

Пример:

Пусть с клавиатуры вводятся два числа и знак операции. Следует вывести в файл сформированное для вычисления выражение и результат вычисления.

( TERPRI 2) ; Перевод строки 2 раза

(SETQ *print-escape* nil) ; Запрет выводить специальные символы


(PRINT “vvedite chislo znak chislo”) ; Приглашение ввести число, знак, число

(SETQ
a (READ) zn (READ) b (READ)) ; Ввод данных с клавиатуры

(SETQ
rez (EVAL (LIST zn a b))) ; Формируется выражение для вычисления в прединфиксной форме, вычисляется и результат вычислений связывается с переменной rez

( TERPRI 3) ; Перевод строки 3 раза

(PRINC a) ; Вывод первого числа

(PRINC zn) ; Вывод знака операции

(PRINC b) ; Вывод второго числа

(PRINC “=”) ; Вывод знака равно

(PRINC rez) ; Вывод результата операции

После точек с запятыми идут комментарии. Если с клавиатуры будет введено 3 + 5, то на экран выведется 3 + 5 = 8 с четвертой строки.

1.8 Последовательные вычисления

В Лиспе имеются структуры, управляющие последовательностью вычислений. Такие структуры будем называть предложениями. Предложения выглядят внешне как вызовы функции. Предложение записывается в виде скобочного выражений, первый элемент которого является именем управляющей структуры, а остальные элементы «аргументами». Результатом вычисления так же, как и у функций, является значение. Но следует помнить, что предложения не являются вызовами функций и разные предложения по-разному используют свои аргументы.

Предложения PROG1, PROGN позволяют работать с несколькими вычисляемыми формами. Они имеют следующую структуру:

(PROG1 V1 V2  Vn)

(PROGN V1 V2  Vn), где V1 V2  Vn – вычислимые выражения.

У этих специальных форм переменное число аргументов, которые они последовательно вычисляют и возвращают в качестве значения предложения значение первого (для PROG1) или последнего (для PROGN) аргумента.


Пример: (PROGN (SETQ x 2) (SETQ y (* 3 x))) –> 6

1.9 Разветвление вычислений

Предложение COND является основным средством разветвления вычислений. Это синтаксическая форма, позволяющая управлять вычислениями на основе определяемых предикатами условий. Предложение имеет следующую структуру:

(COND

(P1 V1)

(P2 V2)



(Pn Vn)

), где Pi – предикат, Vi – вычислимое выражение (i = 1,n).

Значение предложения COND определяется следующим образом: слева направо (сверху вниз) вычисляются предикаты P1, P2,  до тех пор, пока не встретится предикат, возвращающий значение отличное от nil. Пусть это будет предикат Pk. Вычисляется выражение Vk и полученное значение возвращается в качестве значения предложения COND. Если все предикаты предложения COND возвращают nil, то предложение COND возвращает nil. Рекомендуется в качестве последнего предиката использовать специальный символ t, тогда соответствующее ему выражение будет вычисляться во всех случаях, когда ни одно другое условие не выполняется.

При составлении предикатов можно использовать встроенные логические функции AND (и), OR (или) и NOT (отрицание). Число аргументов функций AND и OR может быть произвольным. В случае истинности предикат AND возвращает значение своего последнего аргумента, а предикат OR - значение своего первого аргумента, отличного от nil.

Пример 1: Примем, что возможны три типа выражений: пустой список, атом, список. Определим функцию TYPE, определяющую тип выражения.

(defun TYPE (l)

(COND

((NULL l) ‘pustoi_spisok)


((LISTP l) ‘spisok)

(t ‘atom)

)

)

Рассмотрим примеры обращения к функции TYPE.

(TYPE ‘(1 2)) –> spisok

(TYPE (ATOM ‘(a t o m))) –> pustoi_spisok

(TYPE ‘a) –> atom

Пример 2: Определим функцию TWO_EQ, возвращающую t, если в двух списках совпадают два первых элемента.

(defun TWO_EQ (l1 l2)

(COND

((OR (NULL l1) (NULL l2)) nil) ; Нет элементов в одном из списков

((OR (NULL (CDR l1)) (NULL (CDR l2))) nil) ; В одном из списков один элемент

((EQUAL (CAR l1) (CAR l2)) (EQUAL (CADR l1) (CADR l2))

(t nil)

)

)

Рассмотрим примеры обращения к функции TWO_EQ.

( TWO_EQ ‘(1 2) (1)) –> nil

( TWO_EQ ‘(1 2 (3 4)) ‘(1 2 8)) –> t

В условном предложении может отсутствовать вычислимое выражение Vi (соответствующая строка имеет вид (Pi)) или на его месте может стоять несколько вычислимых выражений (соответствующая строка имеет вид
(Pi Vi1 Vi2  Vik)). Если предикат Pi возвращает значение отличное от nil, в первом случае результатом предложения COND будет являться значение Pi, а во втором – выражения Vi1, Vi2, , Vik последовательно вычисляться слева направо и результатом предложения COND будет значение Vik (неявный PROGN).

1.10 Рекурсия

Функция называется рекурсивной, если в ее определяющем выражении содержится хотя бы одно обращение к ней самой (явное или через другие функции). Будем говорить о рекурсии по значению, если рекурсивный вызов является выражением, определяющим результат функции. Если в качестве результата функции возвращается значение некоторой другой функции и рекурсивный вызов участвует в вычислении аргументов этой функции, то будем говорить о рекурсии по аргументам. Рекурсия в Лиспе основана на математической теории рекурсивных функций. В этой области математики изучаются вопросы, связанные с вычислимостью. Под вычислимыми понимаются такие задачи, которые можно запрограммировать и решить с помощью компьютера. Основная идея рекурсивного определения заключается в том, что функцию с помощью рекуррентных формул можно свести к некоторым начальным значениям, к ранее определенным функциям или к самой определяемой функции, но с более «простыми» аргументами. Вычисление такой функции заканчивается в тот момент, когда оно сводится к известным начальным значениям. При определении рекурсивных функций в Лиспе применяется такой же подход. Во-первых, определение рекурсивной функции должно содержать хотя бы одну рекурсивную ветвь. Во-вторых, в рекурсивном описании должно быть условие окончания рекурсии. При написании рекурсивных функций следует обратить внимание на следующее. Когда выполнение функции доходит до рекурсивной ветви, функционирующий вычислительный процесс приостанавливается, а запускается с начала новый такой же процесс, но уже на новом уровне. Прерванный процесс запоминается, он начнет исполняться лишь при окончании запущенного им нового процесса. В свою очередь, новый процесс так же может приостановиться и т.д. Таким образом, образуется стек прерванных процессов, из которых выполняется лишь последний запущенный процесс. Функция будет выполнена, когда стек прерванных процессов опустеет.


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

Далее рассмотрим различные виды рекурсии, используемые в Лиспе.

1.10.1 Простая рекурсия

Рекурсия называется простой, если вызов функции встречается в некоторой ветви лишь один раз. В процедурном программировании простой рекурсии соответствует обыкновенный цикл. Простую рекурсию можно разделить на два класса:


  • рекурсия по значению, когда рекурсивный вызов функции определяет результат функции;

  • рекурсия по аргументу, когда результатом функции является значение другой функции, у которой одним из аргументов является рекурсивный вызов определяемой функции.

Перечислим наиболее часто встречающиеся ошибки при написании рекурсивных функций:

  1. ошибочное условие (например, список не укорачивается), которое приводит к бесконечной рекурсии;

  2. неверный порядок условий;

  3. отсутствие проверки какого-нибудь случая.

При написании рекурсивных функций для предотвращения бесконечной рекурсии условия остановки рекурсии следует ставить в начале тела функции. В этих условиях следует проверить все особые случаи.

Пример 1: Определим функцию STEP, возводящую число в целую неотрицательную степень. Воспользуемся рекурсивным определением степени:




(defun STEP (x n)

(COND

((= n 0) 1) ; Условие остановки рекурсии

(t (* x (STEP x ( n 1)))

)

)

В данном случае имеем рекурсию по аргументу (рекурсивный вызов STEP является аргументом функции *).

Обращение к функции STEP:

(STEP 2 3) –> 8

Пример 2: Определим предикат ATOM_IN_LIST, проверяющий есть ли среди элементов списка атомы. Запишем определение функции словесно:


(defun ATOM_IN_LIST (l)

(COND

((NULL l) nil)

((ATOM (CAR l)) t)

(t (ATOM_IN_LIST (CDR l)))

)

)

В данном случае имеем рекурсию по значению (рекурсивный вызов ATOM_IN_LIST определяет результат функции).

Обращение к функции ATOM_IN_LIST:

(ATOM_IN_LIST ‘((1 2) (3))) –> nil

Пример 3: Определим функцию COPY, копирующую список на верхнем уровне (без учета вложенностей). Запишем определение функции словесно:

  • скопировать список – это значит соединить голову списка со скопированным хвостом;

  • копией пустого списка является пустой список (условие остановки рекурсии).

(defun COPY (l)

(COND

((NULL l) l)

(t (CONS (CAR l) (COPY (CDR l)) ) )


)

)

В данном случае имеем рекурсию по аргументу (рекурсивный вызов COPY является аргументом функции CONS).

Обращение к функции COPY:

(COPY ‘((1 2) 3 4)) –> ((1 2) 3 4)

Выполнив небольшие изменения, эту функцию можно использовать для различных преобразований списка на верхнем уровне.

Пример 4: Определим функцию MEMBER_S, проверяющую принадлежность s-выражения списку на верхнем уровне. В случае, если s-выражение принадлежит списку, функция возвращает часть списка, начинающуюся с первого вхождения s-выражения в список. В Лиспе имеется аналогичная встроенная функция MEMBER (но она использует в своем теле функцию EQ, поэтому не работает для вложенных списков). Запишем определение функции MEMBER_S словесно:


  • если s-выражение совпадает с головой списка, то возвращаем этот список (условие остановки рекурсии);

  • в противном случае ищем первое вхождение s-выражения в хвосте списка;

  • если дошли до конца списка, то s-выражение не входит в список (условие остановки рекурсии).

(defun MEMBER_S (x l)

(COND

((NULL l) l)

((EQUAL x (CAR l)) l)

(t (MEMBER_S x (CDR l)) )

)

)

В данном случае имеем рекурсию по значению.

Обращения к функции MEMBER_S:

(MEMBER_S 1 ‘(2 (3) 1 5)) –> (1 5)

(MEMBER_S 1 ‘(2 (1) 3 5)) –> nil

(MEMBER_S ‘(1 2 3) ‘(6 (8) (1 2 3) 1 5)) –> ((1 2 3) 1 5))

Заметим, что встроенная функция MEMBER для последнего примера вернула бы nil, т.к. в теле функции для сравнения используется функция EQ.

( MEMBER ‘(1 2 3) ‘(6 (8) (1 2 3) 1 5)) –> nil