Чтение и запись информации в файлы
ЛЕКЦИЯ 10.
Чтение и запись информации в файлы
Содержание
10.1 Задание параметров при определении функций.
При определении функции можно использовать механизм ключевых слов для того чтобы при вызове функций аргументы трактовать по разному.
С помощью ключевых слов в лямбда-списке можно выделить
необязательные аргументы (optional) параметр, связываемый с хвостом списка аргументов изменяющейся длины (rest) ключевые параметры (key)
Ключевые слова начинаются с символа & и их записывают перед соответствующими параметрами в лямбда-списке.
Действие ключевого слова распростроняется до следующего ключевого слова.
Параметры, перечисленные в лямбда-списке до первого ключевого слова, являются обязательными.
10.1.1 Необязательные параметры &optional
Вы можете определить необязательные аргументы для вашей функции. Любой аргумент после символа &optional необязательный:
* ( Defun bar ( x &optional y) ( if y x 0 )) bar * ( Defun baaz ( &optional ( x 3 ) ( z 10 )) ( + x z) ) BAAZ * ( bar 5 ) 0 * ( bar 5 t) 5 * ( Baaz 5 ) 15 * ( Baaz 5 6 ) 11 * (Baaz) 13
Можно вызывать функцию bar или с одним или с двумя аргументами. Если она вызвана с одним аргументом, x будет связано со значением этого аргумента и незаданный аргумент y будет связан с nil; если она вызвана с двумя аргументами,x и y будут свя- заны со значениями первого и второго аргумента, соответственно.
Функция baaz имеет два необязательных аргумента. Кроме этого она определяет недостающие знaчения для каждого из них: если пользователь определит только один аргумент, z будет связано с 10 вместо nil, и если пользователь не определит никаких аргументов, x будет связана с 3 и z с 10.
Такое определение значений называется определение по умолчанию.
10.1.2 Переменное количество аргументов &rest
Вы можете задавать вашу функцию принимающей любое число аргументов, заканчивая список аргументов &rest параметром.
LISP будет собирать все аргументы не попавшие в обязательные параметры в список и связывать &rest параметр с этем списком.
Итак:
* ( Defun foo ( x &rest y) y)
FOO
* ( Foo 3 )
NIL
* ( Foo 4 5 6 )
(5 6)
* ( defun fn ( x &optional y &rest z)) (list x y z)) fn
* (fn 'a)
(A NIL NIL)
* ( a b (c d))
10.1.3 Ключевые параметры Можно задать функции другой вид необязательного аргумента называемого аргументом ключевого слова. Пользователь может задавать эти аргументы в последующем в любом порядке, потому что они маркированы ключевыми словами. Символы t и nil называются константами-символами, потому-что они при выполнении дают сами себя.
Существует целый класс таких символов, которые называются ключевыми словами; любой символ, чье имя начинается с двоеточия является ключевым словом.
(Ниже приведены некоторые использования ключевых слов).
Примеры:
* :this-is-a-keyword
:THIS-IS-A-KEYWORD
* :so-is-this :SO-IS-THIS
* :me-too :ME-TOO
( Defun foo ( &key x y) ( cons x y) )
FOO
* ( Foo :x 5 :y 3 )
(5 . 3)
* ( Foo :y 3 :x 5 )
(5 . 3)
* ( Foo :y 3 )
( NIL. 3 )
* (Foo)
(NIL)
&key параметр может иметь также значение по умолчанию:
* ( Defun foo ( &key ( x 5 )) x )
FOO
* ( Foo :x 7 )
7
* (Foo)
5
(defun test ( x &optional (y 3) (z 4) &rest a) (cons z ( list x a y)))
(test 1 2 3)
(test 1)
(test 3 4 5)
(test 3 2 1 1 2 3)
10.2 Входные и выходные потоки. При вводе и выводе информации в Лиспе используется понятие потоков - stream
Для потока определены ИМЯ , операции открытия open операции закрытия clouse направления output и input
10.3 Определение выходных и входных потоков.
Для открытия файла для записи задается его имя, производится операция open и указывается направление output:
(setq our-output-stream (open "sesame" :direction :output))
Зададим
(setq s 'e)
Можно вывести это значение в файл
(princ s our-output-stream) ;
Можно занести список
(print '(a b c d) our-output-stream)
Чтобы правильно закрыть поток необходимо в конец поместить
(terpri our-output-stream)
Затем файл закрывается
(close our-output-stream)
Можно посмотреть информацию в файле.
Откроем файл для чтения:
(setq our-input-stream (open "sesame" :direction :input))
Прочитае информацию
(read our-input-stream)
Закроем файл
(close our-input-stream)
10. 4 Чтение символов из файла
Предположим, что в файле хранится символьная информация, необходимая нам для обработки. Причем нас интересует каждый символ в файле. До сих пор мы могли вводить только атомы, числа и списки.
Сформируем файл
Пусть
(setq s "---+++")
(setq p "+++---")
Определим поток вывода
(setq our-output-stream (open "picture.spl" :direction :output)) (princ s our-output-stream) ; записываем первую стороку (terpri our-output-stream) ; заканчиваем ее (princ p our-output-stream) ; записываем вторую строку (terpri our-output-stream) ; заканчиваем файл
Тепрь файл закрывается
(close our-output-stream)
В файле теперь находится
---+++ +++---
Для чтения символов из файла будем использовать функцию
(READ-CHAR )
Данная функция позволяет читать печатные символы ( CHAR) из файла. В качестве значения получается десятичное представление кода символа.
Используе эту функцию для посимвольного ввода информации из файла для ее последующего анализа
Определим
(setq our-input-stream (open "picture.spl" :direction :input))
Для чтения символа используем
(read-char our-input-stream)
Будем получать последовательность значений
43 43 43 45 45 45 10 и т.д.
Для восстановления содежимого файла применяется перекодировка
(setq x (read-char our-input-stream)
То содержимое x можно показать
(cond (( = x 43) (prin1'+)) (( = x 45) (prin1 '-)) (( = x 10 ) (terpri)))
Можно представить информацию без искажений, если использовать цикл
(loop (progn (setq x (read-char our-input-stream) ) (cond (( = x 43) (prin1'+)) (( = x 45) (prin1 '-)) (( = x 10 ) (terpri))))))
После вывода имеем
---+++ +++---
Закрытие входного потока
(close our-input-stream)
Для поиска конца файла можно анализировать ошибку чтения, но лучше знать длину файла до начала работы с ним.
Функции. Базовые функции
ЛЕКЦИЯ 2.Функции. Базовые функции.
Содержание
Понятие функции.
В математике функция отображает одно множество в другое. Записывается: Y = F (x)
Для х из множества определения (Domain) ставится в соответствие Y из множества значений (range) функции F. |
|||
Можно записать:
У функции может быть любое количество аргументов, в том числе их может не быть совсем. Функция без аргументов имеет постоянное значение. | ||
Примеры функций:
abs( -3 ) --> 3 абсолютная величина.
+ ( 2 , 3 ) --> 5 сложение
union ( ( a , b ), ( c , b ) ) --> ( a , b , c ) объединение множеств.
количество_букв ( слово ) --> 5
Типы аргументов и функций.
Функция в общем случае задает отображение из нескольких множеств в множество значений. |
||
Можно записать :
Это функция двух аргументов: первый х принадлежит А, второй у принадлежит В, значение z принадлежит С. В этом случае говорят, что аргументы и значение имеют разные типы.
Пример:
1.2 Префиксная нотация.
В математике принята префиксная нотация, в которой имя функции стоит перед аргументами заключенными в скобках. | В Лиспе для записи арифметических выражений и функций используется единая префиксная форма записи, в которой имя функции или действия стоит перед аргументами и записывается внутри скобок. | |
f ( x ) g ( x , y ) h ( x , g ( y , z ) ) |
( f x ) ( g x y ) ( h x ( g y z ) ) ( + x y ) ( - x y ) ( * x ( + x z ) ) |
|
в арифметических выражениях используется инфиксная запись : | ||
x + y x - y x * ( x + z ) |
Достоинства :
упрощается синтаксческий анализ выражений, так как по первому
символу текущего выражения система уже знает, с какой структурой
имеет дело.
появляется возможность записывать функции в виде списков, т.е. данные (списки) и программа (списки) представляются единым образом.
Диалог с интерпретатором ЛИСПА.
Транслятор Лиспа работает как правило в режиме интерпретатора.
Read-eval-print цикл
loop { read evaluate print)
В Лиспе сразу читается , затем вычисляется (evaluate) значение функции и выдается значение.
Пример :
* ( + 2 3 ) 5 |
||
Иерархия вызовов.
В вводимую функцию могут входить функциональные подвыражения :
* (* ( + 1 2 ) ( + 3 4 )) 21 |
||
Блокировка QUOTE.
В некоторых случаях не требуется вычисления значений выражений, а требуются само
выражение. Если прямо ввести * ( + 2 3 ) , то 5 получится как значение. Но можно понимать ( + 2 3 ) не как функцию, а как список. S-выражения, которые не надо вычислять,
помечают для интерпретатора апострофом " ' " (quote).
QUOTE - специальная функция с одним аргументом, которая возвращает в качестве значения этот аргумент. |
||
* ' ( + 2 3 ) ( + 2 3 ) Или * ' y y |
||
* ( quote ( + 2 3 ) ) ( + 2 3 ) * ( quote y ) y |
Вместо апострофа можно использовать функцию QUOTE. |
* ' ( a b ' ( c d ) ) (a b ( quote c d ) ) |
Апостроф автоматически преобразуется в QUOTE. |
* ( quote ' y ) ( QUOTE Y ) * '' y ( QUOTE Y ) * ( QUOTE QUOTE ) QUOTE |
||
* ' 3.17 3.17 * ( + ' 2 3 ) 5 * t T * ' t T * ' nil NIL |
||
/FONT>.4 Функция EVAL.
Функция EVAL обеспечивает дополнительный вызов интерпретатора Лиспа. При этом вызов может производится внутри вычисляемого S-выражения. Функция EVAL позволяет снять блокировку QUOTE. |
||
* ( quote ( + 1 2 ) ) ( + 1 2 ) * ( eval ( quote ( + 1 2 ) ) ) 3 |
quote и eval действуют во взаимно противоположенных направлениях и аннулируют эффект друг друга. |
* ( setq x ' ( a b c ) ) ( a b c ) * ' x x |
* x ( a b c ) * ( eval ' x ) ( a b c ) |
EVAL - это универсальная функция Лиспа, которая может вычислить любое правильно составленное s-выражение. |
||
/p>
Использование символов в качестве переменных.
Изначально символы в Лиспе не имеют значения. Значения имеют только константы.
* t
T
* 1.6
1.6
Если попытаться вычислить символ, то система выдает ошибку.
Значения символов хранятся в ячейках, закрепленных за каждым символом. Если в эту ячейку положить значение, то символ будет связан (bind) сo значением. В процедурных языках говорят "будет присвоено значение". | ||
Не оговаривается, что может хранится в ячейке: целое, атом, список, массив и т.д. В ячейке может хранится что угодно.
С символом может быть связана не только ячейка со значением, а многие другие ячейки, число которых не ограничено.
Для связывания символов используется три функции:
Функция SET.
Функция SET cвязывает символ со значением, предварительно вычисляя значения аргументов. | ||
В качестве значения функция SET возвращает значение второго аргумента. |
Если перед первым аргументом нет апострофа, то значение будет присвоено значению этого аргумента. |
* ( set 'd ' ( x y z ) ) ( x y z ) |
* ( set a ' e ) e |
* ( set ' a ' b ) b |
* a b * b e |
На значение символа можно сослаться записав его без апострофа.
Функция SETQ.
Она аналогична , но не вычисляет значение первого аргумента. Буква q на блокировку.
* ( setq m ' k ) k |
* m k |
Обобщенная функция SETF.
Действует аналогично , но может использоваться для присвоения символу не только значения.
Базовые функции.
В Лиспе для обработки списков, т.е. для разбора, анализа и построения списков
существуют базовые функции. Они образуют систему аксиом языка, к которым
сводятся символьные вычисления. В этом смысле их можно сравнить с основными арифметическими операциями. Простота базовых функций и их малое число -
одно из достоинств Лиспа.
Базовые функции:
ATOM EQ
Функции CAR и CDR извлекают информацию из списка, или обеспечивают доступ к элементам списка. CONS объединяет элементы в список. ATOM и EQ проверяют аргументы. |
||
/p>
Функция CAR.
Первый элемент списка - голова. Список без головы - хвост. |
||
Функция CAR возвращает в качестве значения первый элемент списка, т.е. голову. | ||
CAR < список > |
* ( car '(( head ) tail )) -> ( head )
* ( car ( a b )) ошибка - имя несуществующей функции. |
car применяется только для списков, т.е. если есть голова списка. |
* ( car nil ) nil * ( car ' nil ) nil |
* ( car ' ( nil a ) ) nil |
Функция CDR.
* (cdr ' ( a ) ) nil * ( cdr nil ) nil |
Так как список из одного элемента ,его хвост - пустой список. |
атомов
* ( cdr ' kat ) ошибка, т.к. не список.
* ( cdr ' ( ( a b) ( c d ) ) )
( ( c d ) )
Имена функций и возникли по историческим причинам. Автор Лиспа реализовывал свою первую систему на машине IBM 605. Для хранения адреса головы списка
использовался регистр CAR (content of address registr) Для хранения адреса хвоста списка использовался регистр CDR (contеnt of decrement registr)
В MCL можно наряду с CAR и CDR использовать имена FIRST REST. * ( FIRST ' ( a b c ) ) a |
||
* ( FIRST ( REST ' ( 1 2 3 4 ) ) 2 * ( FERST ' ( REST ' ( 1 2 3 4 ) ) ) REST |
||
Рассмотрим ( сar ( cdr ' ( ( a b ) c d ) ) ) Первым выполняется cdr ,а затем car, т.е. в Лиспе первым выполняются внутренние функции, а затем внешние. Исполнение идет "изнутри наружу". |
||
Функция CONS.
Функция CONS строит новый список из своих аргументов. cons: s-выражение + список = список |
||
CONS < s-выражение > <список > |
Примеры:
* ( cons ' a ' ( b c ) ) ( a b c ) |
* ( cons ' ( a b ) ' ( c d ) ) ( ( a b) c d ) |
* ( cons ' ( a b ) ' ( ( a b ) ) ) ( ( a b ) ( a b ) ) * (cons ( + 1 2 ) ' ( + 3 4 ) ) ( 3 + 3 4 ) |
* (cons ' ( + 1 2 ) ( + 3 4 ) ) error * ( cons ' ( + 1 2 ) ' ( + 3 4 ) ) ( ( + 1 2 ) + 3 4 ) |
/p>
Примеры манипуляции с пустым списком:
* ( cons ' ( a b c ) nil ) ( ( a b c ) ) * ( cons nil ' ( a b c ) ) ( nil a b c ) |
* ( cons nil nil ) ( nil ) |
* ( cons ' a nil ) ( a ) |
Очень полезно, т.к. позволяет превращать элемент в список. |
Связь между CAR, CDR и CONS.
Таким образом функции по принципу их использования делятся на группы:
Назначение
запись
результат
* ( cons ( car '( голова хвост )) ( сdr '( голова хвост ))) ( голова хвост) |
Селекторы и являются обратными для конструктора . Список, разбитый с помощью функции CAR и CDR на голову и хвост, можно восстановить функцией CONS. |
Комбинации функций CAR и CDR.
Комбинируя функции и можно выделить произвольный элемент списка :
* ( cdr ( cdr ( car ' ( ( a b c ) d )))) ( a b c ) ( b c ) ( c ) |
Можно записать проще : ( CDDAR ' ( ( a b c ) d ) ) Т.е. записывается (C...R список) А - CAR D - CDR |
N - элемент.
Функция NTH извлекает n-й элемент из списка. |
||
NTH < n > <список > |
Пример :
Извлекаем седьмой элемент :
*( NTH 7 '( 1 2 3 4 5 6 7 8 9 10 ) )
7
6.7 Функция LIST.
Функция LIST создает список из s- выражений (списков или атомов). |
||
Форма записи:
Число аргументов может быть любое.
Примеры:
* ( list 1 2 ) ( 1 2 ) * ( list ' a ' b ( + 1 2 ) ) ( a b 3 ) * ( list ' a ' ( b c ) ' d ) ( a ( b c ) d ) |
* ( list nil ) ( nil ) * ( list ' a ) ( a ) * ( list ' a nil ) ( a nil ) |
Функция LENGTH.
Функция LENGTH возвращает в качестве значения длину списка. т.е. число элементов на верхнем уровне |
||
Примеры:
2.7 Арифметические функции.
Арифметические функции могут быть использованы с целыми или действительными аргументами.
Число аргументов для большинства арифметических функций может быть разным.
(+ x1 x2 ... xn) возвращает x1 + x2 + x3 + ... + xn.
(- x1 x2 ... xn) возвращает x1 - x2 - x3 - ... - xn.
(* y1 y2 ... yn) возвращает y1 x y2 * y3 * ... * yn.
(/ x1 x2 ... xn) возвращает x1/x2/... /xn.
Специальные функции для прибавления и вычитания единицы: (1+ x) и (1- x).
Let. Циклические предложения
ЛЕКЦИЯ 5.
LET. ЦИКЛИЧЕСКИЕ ПРЕДЛОЖЕНИЯ
Содержание
5.1 L E T
В том случае, когда используется вычисление последовательности форм, удобно бывает ввести локальные переменные, сохраняемые до окончания вычислений. Это делается с помощью предложения LET.
В общем виде LET записывается
(LET ((var1 знач1) (var2 знач2)...) форма1 форма2 ... формаN)
LET вычисляется следующим образом:
1. Локальные переменные var1, var2, ...varM связываются одновременно со знач1, знач2, ..., значМ.
2. Вычисляются последовательно аргументы форма1, форма2, формаN.
3. В качестве значения предложения принимается значение последнего аргумента (неявный PROGN).
4. После выхода из предложения связи переменных var1, var2, ...varM ликвидируются.
Предложение LET удобно использовать, когда надо временно сохранять промежуточные значения.
Пример.
Рассмотрим функцию rectangle, которая имеет один аргумент - список из двух элементов, задающих длину и ширину прямоугольника. Функция рассчитывает и печатает площадь периметр прямоугольника.
(defun rectangle (dim) (let ((len (car dim)) (wid (cadr dim))) (print (list 'area (* len wid))) (print (list 'perimeter (* (+ len wid) 2)))))) * (rectangle '(4 5)) |
Можно сначала рассчитать площадь, т.е. определить
(defun rectangle (dim) (let ((len (car dim)) (wid (cadr dim)) (area (* len wid)) (print ( 'area area)) (print (list 'perimeter (* (+ len wid))))))) Обращение * (rectangle '(4 5))
|
Надо использовать предложение LET* , в котором значение переменных задается последовательно.
(defun rectangle (dim) (let* ((len (car dim)) (wid (cadr dim)) (area (* len wid))) (print (list 'area area)) (print (list 'perimeter (* (+ len wid) 2))))))) |
5.2 Условный выход из функции: PROG RETURN
Встречаются ситуации, когда из тела функции, представленного последовательностью форм, требуется выйти, не доходя до последней формы. Это можно сделать используя предложения PROG RETURN, которые используются вместе.
Рассмотрим пример.
Необходимо написать функцию которая вводит два значения. Если это числа функция печатает их сумму и разность.
Если хотя бы одно не является числом, печатается nil.
* (defun s-d () (prog (x y); локальные переменные (print '(type number)) (setq x (read)) (and (not (numberp x)) (return nil)) (print '(type number)) (setq y (read)) (and (not (numberp y)) (return nil)) (print (+ x y)) (print (- x y)))) * (s-d) (type number)8 (type number) (1) nil |
Если return не встретился - результат prog будет nil .
* (s-d) (type number)8 (type number)1 9 7 nil |
5.3 Дополнительные функции печати
PRINT печатает значение аргумента без пробела и перевода на другую строку:
* (progn (print 1) (print 2) (print 3)) 123 |
"string" |
* "(+ 1 2)" "(+ 1 2)" |
PRINC печатает строки без "".
PRINC печатает аргумент без пробела и перевода строки
Пример
* (progn (setq x 4) (princ " x = ") (prin1 x) (princ " m ")) x = 4 m |
PRINC обеспечивает гибкий вывод.
TERPRI производит перевод строки. Как значение возвращает nil.
* (progn (setq x 4) (princ "xxx ") (terpri) (princ "xox ")) xxx xox " xox" |
5.4 Циклические предложения
Циклические вычисления в лиспе выполняются или с помощью итерационных (циклических) предложений
или рекурсивно.
Познакомимся вначале с циклическими предложениями
5.4.1 LOOP
Предложение LOOP реализует бесконечный цикл
(LOOP форма1 форма2 .....)
в которoм формы вычисляются до тех пор, пока
не встретится явный оператор завершения RETURN.
5.4.1. 1 Применение LOOP для численных итераций.
Определим функцию add-integer, которая будет брать один аргумент, являющийся положительным целым, и возвращает сумму всех чисел между 1 и этим числом.
1+2+3+4+ ... +N 1+2+3+4=10 * (add-integers 4) 10 (defun add-integers (last) (let (( count 1) (total 1)) (loop (cond (( equal count last) (return total))) (setq count (+ 1 count)) (setq total (+ total count))))) |
Например, 3 x 4 это 3 + 3 + 3 + 3 = 12 * (int-multiply 3 4) 12 (defun int-multiply (x y) (let ((result 0)( count 0)) (loop (cond (( equal count y) (return result))) (setq count (+ 1 count)) (setq result (+ result x))))) |
(defun < имя-функции > < список-параметров >
(let (< инициализация переменной индекса >
< инициализация переменной результата >)
(loop
(cond < проверка индекса на выход > (return результат))
< изменение переменной счетчика >
< другие действия в цикле,
включая изменение переменой результата >)))
Еще пример. Определим функцию factorial
* (factorial 5) 120 1 x 2 x 3 x 4 x 5 = 120 (defun factorial ( num ) (let ((counter 0)( product 1)) (loop (cond (( equal counter num) (return product))) (setq counter (+ 1 counter)) (setq product (* counter product ))))) |
( progn (setq x 0) (loop (if ( = 3 x) (return 't) (print x)) (setq x (+ 1 x)))) 0 1 2 t |
" Enter the next number: " перед каждым вводом.
* ( read-sum) Enter the next number: 15 Enter the next number: 30 Enter the next number: 45 Enter the next number: stop 90 (defun read-sum () (let ((input) (sum 0)) (loop (princ "Enter the next number:") (setq input (read)) (cond (( not (numberp input)) (return sum))) (setq sum (+ input sum))))) |
/p>
5.4.1. 2 Применение LOOP для итераций co списками.
Предположим, что нам необходима функция double-list, принимающая список чисел и возвращает новый список в котором каждое число удвоено.
* (double-list '(5 15 10 20)) (10 30 20 40) (defun double-list ( lis ) (let ((newlist nil)) (loop (cond (( null lis ) (return newlist))) (setq newlist (append newlist (list (* 2 (car lis))))) (setq lis (cdr lis ))))) |
list | newlist | |
Начальное состояние | (5 15 10 20) | () |
итерация 1 | (15 10 20) | (10) |
итерация 2 | (10 20) | (10 30) |
итерация 1 | (20) | (10 30 20) |
итерация 4 | () | (10 30 20 40) |
результат | (10 30 20 40) |
5.5 DO
Это самое общее циклическое предложение
Общая форма
( DO (( var1 знач1 шаг1) ( var2 знач2 шаг2)....)
( условие-окончания форма11 форма12...)
форма21
форма21 ...)
1) Вначале локальным переменным var1 ..varn присваиваются начальные значения знач1..значn. Переменным, для которых не заданы начальные значения присваивается nil.
2) Затем проверяется условие окончания, если оно выполняется вычисляются форма11, форма12... В качестве значения берется значение последней формы.
3) Если условие не выполняется, то вычисляются форма21, форма22...
4) На следующем цикле переменным vari присваиваются одновременно новые значения определяемые формами шагi и все повторяется.
Пример
* ( do (( x 1 ( + 1 x))) (( > x 10) ( print 'end)) ( print x)) |
В конце end.
Можно сравнить итерационное вычисление с LOOP и DO.
Напишем функцию list-abs, которая берет список чисел и возвращает список абсолютных величин этих чисел.
(defun list-abs (lis) (let ((newlist nil)) (loop (cond (( null lis ) (return (reverse newlist)))) (setq newlist (cons (abs (car lis)) newlist)) (setq lis (cdr lis ))))) * (list-abs '(-1 2 -4 5)) |
(defun list-abs (lis) (do ((oldlist lis (cdr oldlist)) (newlist nil (cons (abs (car oldlist)) newlist))) ((null oldlist) (reverse newlist))))) |
Может одновременно изменяться значения нескольких переменных
* ( do (( x 1 (+ 1 x)) ( y 1 (+ 2 y)) ( z 3)); значение не меняется (( > x 10) ( print 'end)) (princ " x=") ( prin1 x) (princ " y=") ( prin1 y) (princ " z=") ( prin1 z) (terpri)) |
* ( do (( x 1 (+ 1 x))) (( > x 10)) ( do (( y 1 (+ 2 y))) (( > y 4)) ( princ " x= ") ( prin1 x) ( princ " y= ") ( prin1 y) (terpri) )) |
5.5.1 Обработка списков c DO.
Напишем функцию, которая будет читать элементы с клавиатуры и объединять в список. Ввод будет закончен, когда будет введен последний элемент end
( defun appen-read () ( do (( x ( list ( read)) ( append x (list (read))))) (( equal (last x) '(end))); ???? '(end) (print x))) ( appen-read) |
5.6 DOTIMES
DOTIMES можно использовать вместо DO, если надо повторить вычисления заданное число раз.
Общая форма
(DOTIMES ( var num форма-return) ( форма-тело))
здесь var - переменная цикла,
num - форма определяющая число циклов,
форма - return - результат, который должен быть возвращен.
Прежде всего вычисляется num-форма, в результате получается целое число-count.
Затем var меняется от 0 до count (исключая count) и соответственно каждый раз вычисляется форма-тело.
Последним вычисляется форма-return.
Если форма-return отсутствует, возвращается nil.
Например,
* (dotimes ( x 3 ) ( print x)) 0 - автоматически 1 2 t * (let ((x nil)) (dotimes (n 5 x) (setq x (cons n x)))) ( 4 3 2 1 0) |
Логические функции. Управляющие структуры
ЛЕКЦИЯ 4.
Логические функции. Управляющие структуры. Простые функции печати. PROGN.
Содержание
4.1 MEMBER.
Функция проверяет, находится ли первый аргумент внутри списка, представленного вторым аргументом. Если элемента в списке нет, MEMBER возвращает nil. |
Функция MEMBER имеет два аргумента: Первый аргумент - это s-выражение, Второй - обязательно список. |
( MEMBER < s-выражение > < список > ) |
* ( member ' b ' ( c d b a ) ) ( b a ) | Если элемент в списке есть, то MEMBER возвращает хвост второго аргумента, начинающийся с этого элемента. | |
Таким образом member в качестве истины возвращает не Т , а величину не-NIL.
В Лиспе для предикатов значение не-NIL означает истину.
* ( member ' с ' ( a b ( c ) ) ) NIL |
Т.к. элемент находится не на том уровне. |
4.2 Логические функции.
Для объединения предикатов в сложные выражения и для выделения элементов - NIL в Лиспе
используются логические функции
,
и
.
4.2.1 NOT.
Функция NOT берет один аргумент и возвращает значение, противоположное значению аргумента. Если аргумент NIL, |
NOT имеет один аргумент, который может быть |
( NOT < s-выражение >) |
Примеры:
* ( not ( zerop 1 ) ) |
* ( not nil ) T |
* ( not ' ( a b c ) ) NIL |
4.2.2 OR.
Логическая функция OR берет один или несколько аргументов. Она выполняет эти аргументы слева направо и возвращает значение первого аргумента, который не NIL.Если все аргументы OR имеют значение NIL, то OR возвращает NIL. |
В OR , аналогично NOT, аргументами могут быть любые выражения. |
( OR < arg-1 >< arg-2 >< arg-3 > . . . ) |
Примеры:
* ( or t nil ) T |
* ( or nil nil ) NIL |
* ( or ( atom 1) ( > 3 4 ) '( a b c ) ) ) ( a b c ) |
Таким образом:
OR возвращает значение не-NIL, если по крайней мере один аргумент не NIL. OR используется для выделения первого не пустого элемента в списке. |
/ul>
4.2.3 AND.
Логическая функция AND берет один или несколько аргументов. Она выполняет эти аргументы слева направо. Если она встречает аргумент, значение которого NIL, она возвращает NIL, не продолжая вычисления остальных. Если NIL аргументов не встретилось, то возвращается значение последнего аргумента. |
( AND < arg-1 >< arg-2 >< arg-3 > . . . ) |
* ( and 5 nil ) NIL |
* ( and ' a ' b ) b |
* ( and ( listp nil ) ( atom nil ) ) T |
Таким образом: AND возвращает NIL значение, если хотя бы один из аргументов NIL, в противном случае возвращается значение последнего аргумента. AND используется для выделения пустого элемента в списке. |
Управляющие структуры.
В обычных языках программирования существуют средства управления вычислительным процессом: организация разветвлений и циклов. В Лиспе для этих целей используются управляющие структуры - предложения (clause). |
Внешне предложения записываются как вызовы функций: Первый элемент предложения - имя; остальные - аргументы. В результате вычисления предложения получается значение. Отличие от вызова функции в использовании аргументов. |
Управляющие структуры делятся на группы. Одна из групп - разветвления вычислений. В нее входят: - условные предложения: |
4.3.1 COND.
Предложение СOND является основным средством организации разветвления вычислений. |
Структура условного предложения :
( COND ( < проверка-1 > < действие-1 > ) ( < проверка-2 > < действие-2 > ) ............................................................... ( < проверка-n > < действие-n > )) |
В качестве аргументов < проверка > и < действие > могут быть произвольные формы.
Значение COND определяется следующим образом: Выражения < проверка-i >, выполняющие роль предикатов вычисляются последовательно, слева направо, до тех пор, пока не встретится выражение, значением которого не является NIL. Вычисляется результирующее выражение, соответствующее этому предикату, и полученное значение возвращается в качестве значения всего предложения COND. Если истинного значения нет, то значением COND будет NIL. |
/p>
Обычно в качестве последнего условия пишется t, соответствующее ему выражение будет вычислятся в тех случаях, когда ни одно другое условие не выполняется.
Последнюю строку можно записать: ( t ' atom ) ) )
Пример: ( функция проверяет тип аргумента)
( defun classify ( arg ) ( cond ( ( null arg ) nil ) ( ( list arg ) 'list ) ( ( numberp arg ) 'number ) ( t 'atom ) ) | * ( classify 'a ) atom * ( classify 5 ) number |
( defun double1 ( num ) ( cond ( ( numberp num ) ( * num 2 ) ( t ' не-число ) ) | Эта функция гарантировано удваивает число, отбрасывая не числовые аргументы. |
В COND могут отсутствовать результирующие выражения для предикатов, а так же присутствовать несколько действий.
( COND ( < проверка-1 > ) ( < проверка-2 > < действие-2 > ) (< проверка-3 > < дейст.-31 > < дейст.-32 > < дейст.-33 >)) |
Если нет действия - результат значение предиката. Если не одно действие - результат значение последнего аргумента. |
4.3.2 Другие условные предложения.
СOND наиболее общее условное предложение. Часто пользуются более простыми условными предложениями.
( IF < условие > < то форма > < иначе форма > ) |
Пример:
( if ( atom x ) 'аtоm 'not - аtom )
Условные предложения WHEN и UNLESS являются часными случаями условного предложения IF:
Если условие соблюдается, то выполняются формы.
( WHEN < условие > < форма-1 > < форма-2 > < форма-3 > ... ) |
( UNLESS < условие > < форма-1 > < форма-2 > < форма-3 > ... ) |
4.3.3 Связь между COND и логическими функциями.
Любую логическую функцию можно заменить COND-выражением и наоборот.
Пример:
car-функция с проверкой: ( defun gcar ( l ) ( cond ( ( listp l ) ( car l ) ) ( t nil ) ) ) |
то же через логические функции: ( defun gcar1 ( l ) ( and ( listp l ) ( car l ) ) ) |
* (gcar '(a b))
a
* (gcar 'a)
nil
4.4 Ввод и вывод информации.
До сих пор в определяемых функциях ввод и вывод результатов осуществлялись в процессе диалога с интерпретатором. Интерпретатор читал вводимое пользователем выражение, вычислял его значение и возвращал его пользователю. Теперь мы рассмотрим специальные функции ввода и вывода Лиспа. |
4.4.1 READ.
| READ отличается от операторов ввода-вывода других языков пpогpаммиpования, тем что он обрабатывает вводимое выражение целиком, а не одиночные элементы данных. |
Вызов функции осуществляется в виде:
( READ ) функция без аргументов. |
Как только интерпретатор встречает READ, вычисления приостанавливаются до тех пор пока пользователь не введет какой-либо символ или выражение.
* ( READ )
new - выражение пользователя
new - значение функции.
READ не указывает на ожидание информации. Если прочитанное выражение необходимо для дальнейшего использования, то READ должен быть аргументом какой либо формы, которая свяжет полученное выражение:
| * ( setq x ' ( read ) ) ( + 1 2 ) - вводимое выражение ( + 1 2 ) - значение * x ( + 1 2 ) * ( eval x ) 3 |
( defun tr ( arg ) ( list ( + arg ( read ) ) ( read ) ) ) | * ( tr 8 ) 14 cat ( 22 cat) |
4.4.2 PRINT.
| Функция PRINT - это функция с одним аргументом. Она выводит значение аргумента на монитор, а затем возвращает значение аргумента. |
( PRINT < arg >) |
а после него выводит пробел.
* ( print ( + 2 3 ) )
5 - вывод
5 - значение
print и read - псевдофункции, у которых кроме значения есть побочный эффект.
Значение функции - значение ее аргумента.
Побочный эффект - печать этого значения.
Это не значит, что всегда две строки. Только когда print на высшем уровне, чего практически не бывает.
Пример:
* ( setq row ' ( x x x ) )
( x x x )
* ( print ( cdr row ) ) ( x x ) - печать ( x x ) - значение | * ( cons 'o ( print ( cdr row ) ) ) ( x x ) - печать ( o x x ) - значение |
br>
4.5 PROGN, PROG1, PROG2.
| Функции PROGN, PROG1, PROG2 относятся к управляющим структурам, к группе объединяющей последовательные вычисления. |
Предложения PROGN, PROG1, PROG2 позволяют работать с несколькими вычисляемыми формами:
( PROGN < форма-1 > < форма-2 > ...... < форма-n >) ( PROG1 < форма-1 > < форма-2 > ...... < форма-n >) ( PROG2 < форма-1 > < форма-2 > ...... < форма-n >) |
У этих предложений переменное число аргументов, которые они последовательно вычисляют:
Пример:
* ( progn ( setq x 2 ) ( setq y ( * 3 2 ) ) )
6
* ( prog1 ( setq x 2 ) ( setq y ( * 3 2 ) ) )
2
* y
6
В Лиспе часто используется так называемый неявный PROGN , т.е вычисляется последовательность форм, а в качестве значения берется значение последней формы.
4.5.1 Определение функций с использованием неявного PROGN.
При определении функций может использоваться неявный PROGN .
( defun < имя функции > < список параметров > < форма1 форма2 .... формаN > ) |
Тело функции состоит из последовательности форм отражающих,
последовательность действий.
В качестве значения функции принимается значение последней формы.
Пример:
Определим функцию, которая печатает список, вводит два числа, и печатает их сумму.
( defun print-sum ( ) ; функция без аргументов ( print ' ( type two number ) ) ( print ( + ( read ) ( read ) ) ) ) | *( print-sum ) ( type two number ) 3 4 7 7 |
Массивы. Макросы. Пример программы на лиспе
ЛЕКЦИЯ 9.
Массивы. Макросы. Пример программы на лиспе. Дифференцирование выражений.
Содержание
9.1 Массивы.
Для хранения большого количества данных в лиспе используются массивы.
Массив - это переменных, ячеек, имеющих одно имя, но разные номера, обеспечивающие доступ к этим ячейкам.
9.1.1 Определение массива
Для определения массива заданной размерности используется функция make-array
(make-array ) поддерживаются только одномерные массивы-векторы.
Пример :
(setq data (make-array 10))
#
(0 0 0 0 0 0 0 0 0 0)
data - имя массива,
0 - начальное наполнение.
9.1.2 Доступ к ячейке массива.
Доступ производится с помощью функции aref. AREF имеет два аргумента - имя массива и индекс и возвращает значение ячейки
(aref )
* (aref data 8)
0,
так как там записан 0.
Особенности: первый аргумент не блокируется, первая ячейка имеет номер 0.
9.1.3 Запись данных в массив.
Поместить данные в массив можно ,используя функцию setf
* (setf (aref data 2) 'dog)
aref -вызывает значение ячейки, функция setf помещает значение.
Рассмотрим массив testdata
(setq testdata (make-array 4))
#
* (setf (aref testdata 1) 'dog)
* (setf (aref testdata 0) 18 )
* (setf (aref testdata 2) '(a b) )
* (setf (aref testdata 3) 4 )
Можно (setq testdata ( vector 18 'dog '(a b) 0)) (aref d 1)
В результате получим
testdata 0 1 2 3
18 dog (a b) 0
Можно использовать эти данные
(cons (aref testdata 1) (list (aref testdata 3)
(aref testdata 2)))
(dog 0 ( a b))
(aref testdata (aref testdata 3))
18
9.1.4 Обработка массивов.
Так как доступ к элементам массива производится по номерам, то удобно использовать численные итерации и рекурсии.
Рассмотрим функцию, которая берет два аргумента имя массива и его длину и возвращает все значения, помещенные в список
(defun array-list (arnam len)
(do (( i 0 ( + 1 i))
( result nil (append result (list (aref arnam i)))))
(( equal i len) result)))
(array-list testdata 4)
( 18 dog (a b) 0)
9.1.5 Длина массива.
(array-length ) возвращает длину массива.
(array- length testdata) возвращает длину массива 4.
9.2 Обратная блокировка.
Обычная блокировка не позволяет вычислять выражения
* '(a b c)
(a b c)
Иногда возникает необходимость вычислить только часть выражения.
Если
(setq b '(x y z))
И мы запишем
* `( a ,b c) ,то
b - будет вычислено и мы получим
(a (x y z) c)
` - обратная верхняя запятая обозначает блокировку, которая может частично сниматься запятой.
Обратная блокировка может использоваться при печати:
(setq n 'john)
(setq m 'Robert)
(print `(boys ,n and ,m))
(boys john and roberts)
Наиболее часто обратная блокировка используется в мощном средстве лиспа - макросах.
9.3.1 Макросы.
Это специальное средство,позволяющее формировать вычисляемое выражение в ходе выполнения программы.
Рассмотрим например функцию blancs, которая производит n переводов каретки (пропускает n линий)
(defun blancs (n)
(do ((count n ( - count 1)))
(( zerop count) nil)
(terpri)))
(blancs 4) пропустит четыре строки.
Будем писать программу, которая позволит выполнять некоторое действие n раз
Для blancs:
(do-times '(terpri) 4)
Или
(do-times '(print 'hello) 3)
Напечатает hello три раза
Можно через
eval определить
(defun do-times (operation n)
(do ((count n ( - count 1)))
(( zerop count) nil)
(eval operation)))
Это можно сделать также через специальную форму :
defmacro
(defmacro do-times (operation n)
` (do ((count ,n ( - count 1)))
(( zerop count) nil)
,operation))
Как видно, форма макро похожа на определение функции, но есть отличия:
1. Аргументы макро не вычисляются перед их использованием.
Тогда обращение записывается:
(do-times (print 'hello) 3)
2. Когда макро вызывается, лисп сначала вычисляет тело макро, а затем выполняет получившееся выражение.
Например,после обращения
(do-times (print 'hello) 3)
Получим
(do ((count 3 ( - count 1)))
(( zerop count) nil)
(print 'hello))
Этот список потом вычисляется.
Таким образом при вызове макро сначала вычисляется тело (этап называется расширением) и формируется выражение.
На втором этапе вычисляется полученное выражение, и полученное значение возвращается как результат.
Вызывая macro с разными аргументами получим разные результаты. Если мы вызываем:
(do-times (print count) 10)
После вычисления тела получим:
(do ((count 10 ( - count 1)))
(( zerop count) nil)
(print count))
Печатается числа от 10 до 1.
Можно определить функцию обратной печати чисел
(defun print-number (n)
(do-times (print count) n))
( print-number 5)
9.3.2 Разработка макро
При разработке макро необходимо выполнить три шага:
Написать пример функции,которую должна формировать макро, Выделить общие части для нескольких функций и переменные. Переменные части обозначить переменными, выделить запятыми и вынести в аргументы. Постоянные части записать напрямую. Определить макро,которое реализует этот вызов.
Пример. Надо определить макро
term-search, которая будет просматривать список и выделять первый элемент удовлетворяющий заданному условию.
Шаг1. Сформулируем пример. Запишем тело для поиска чисел:
(setq l '(s d 3 d)) (setq item 5) _ (do (( tail l (cdr tail))) ((null tail) nil) ( cond ((numberp (car tail)) (return (car tail))))) ~~~~~~~
Шаг2. Выделяем общие части список
lis - l и предикат
predicate - number.
Шаг3.Формируем макро
(defmacro term-search ( predicate lis) ` (do (( tail , lis (cdr tail))) ((null tail) nil) (cond ((,predicate (car tail)) (return (car tail))))))
9.4 Пример программы на лиспе. Дифференцирование выражений.
Напишем программу дифференцирования алгебраических выражений. Для наглядности ограничимся алгебраическими выражениями в следующей форме:
(+ x y) (* x y)
Сложение и умножение можно свободно комбинировать.
Например,
(*(+ a ( * a b)) c)
Программируя непосредственно получаем
(defun diff0 ( l x) (cond (( atom l) (if (eq l x) 1 ;l=1 0));l=константа (( eq (first l) '+) (list '+ (diff0 (second l) x) (diff0 (third l) x))) (( eq (first l) '*) (list '+ (list '* (diff0 (second l) x) (third l)) (list '* (diff0 (third l) x) (second l)))) (t l)))
Испoльзуем
(diff0 '(+ x (* 3 x)) 'x) ( + 1 (+ (* 0 x) (* 1 3))) = 4 (diff0 '(- x (* 3 x)) 'x) return (- x (* 3 x)) Why? (diff0 '(* x ( + x 1)) 'x) (+ (* 1 ( x 1))(*(1 0) x))
Вычисляемые выражения не упрощаются,хотя это не трудно сделать.
9.5.1 Модульный подход.
Эта программа неудобна,так как трудно расширять,приходится все группировать в один
cond.Она не является модульной.
Мы получим более удобное решение, если для каждого действия определим свою дифференцирующую функцию и через свойство diff свяжем эту функцию с символом ,обозначающим действие.
Прoстим запись самой дифференцирующей функции:
(defun dif1 (l x) (cond (( atom l) (if (eq l x) 1 0)) ( t (funcall (get (first l) 'diff) (cdr l) x))))
Функции дифференцирования становятся значениями свойства 'diff:
(setf (get '+ 'diff) 'dif+) (setf (get '* 'diff) 'dif*)
Таким образом извлекаем действие из данных. Сами функции записываются:
(defun dif* (l x) (list '+ (list '* (dif1 (first l) x) (second l)) (list '* (dif1 (second l) x) (first l)))) (defun dif+ (l x) (list '+ (dif1 (first l) x) (dif1 (second l) x)))
Благодаря модульности можно дополнить для -
(defun dif- (l x) (list '- (dif1 (first l) x) (dif1 second l) x)))
Таким образом, первоначальное упрaвление вычислительным процессом, связанное со структурой программы, мы преобразовали в динамическое управление основанное на данных.
Можно использовать макросы.
Определим макрос
defdif , c помощью которого определяются дифференцирующие функции для новых действий:
(defmacro defdif (act args body) `(setf (get ',act 'diff) '(lambda,args,body)))
Тогда дифф. функции задаются:
(defdif + (l x) (list '+ (dif1 (first l) x) (dif1 (second l) x))) (defdif * (l x) (list '+ (list '* (dif1 (first l) x) (second l)) (list '* (dif1 (second l) x) (first l)))) (dif1 '(+ x x) 'x) (defdif - (l x) (list '- (dif1 (first l) x) (dif1 (second l) x))) (dif1 '(+ x (* 3 x)) 'x) (dif1 '(- x (* 3 x)) 'x) (dif1 '(* x ( - x 1)) 'x)
9.5.2 Интерфейс программы.
Дополним программу несколькими функциями,обеспечивающими ввод информации:
Чтение дифф. списка
(defun read-list () (princ " diff-list ? ") (setq l (read)))
Пусть продолжает вычисления до тех пор пока не будет введено не d.
(defun d () (princ "enter command : d -diff;q - quit") (terpri) (if (eq (read) 'd) (progn (read-list) (print (dif1 l 'x )) (terpri) (d)) 'end))
Вызов программы теперь (d)
9.5.3 Загрузка программы.
Можно сразу загружать программу и начать ее выполнение, для этого используют функцию
load
(load )
Записываются обычным образом,но \\ надо использовать двойные.
(load "diff1")
и сразу начинается выполнение.
Основные понятия лиспа
ЛЕКЦИЯ 1.
Введение. Основные понятия Лиспа. |
Содержание
ЛИСП - язык функционального программирования.
Язык ЛИСП (LISP) был разработан в 1958 году американским ученым Джоном Маккарти как функциональный язык, пред- назначенный для обработки списков. ( LISt Processing). Lisp - означает "лепетать". С появлением этого языка машина стала пока лепетать, a не говорить по-человечески. |
|||
В основу языка положен серьезный математический аппарат:
лямбда-исчисление Черча
алгебра списочных структур
теория рекурсивных функций
Долгое время язык использовался узким кругом исследователей. Широкое распространение язык получил в конце 70-х - начале 80-х годов с появлением необходимой мощности вычислительных машин и соответствующего круга задач. В настоящем - Лисп одно из главных инструментальных средств систем искусственного интеллекта. Он принят как один из двух основных ЯП для министерства обороны США и постепенно вытесняет второй ЯП - АДА.
Система AutoCAD разработана на Лиспе.
Основные особенности Лиспа.
До изучения языка трудно говорить об его особенностях, но
тем не менее...
Представление программы и данных производится одинаково - через списки.
Это позволяет программе обрабатывать другие программы и даже саму себя.
Лисп как правило является интерпретирующим языком, также как BASIC.
Лисп безтиповый язык, это значит что символы не связываются по умолчанию
с каким-либо типом.
Лисп имеет необычный синтаксис. Из-за большего числа скобок LISP
расшифровывают как Lots of Idiotic Silly Parentheses.
Программы, написанные на Лиспе во много раз короче, чем написанные на процедурных языках.
ЛИСП. Элементарные понятия.
Символьные данные: выражения
и представление данных.
1 Выражения.
Основу ЛИСПа составляют символьные выражения, которые
называются S-выражениями и образуют область определения
для функциональных программ.
S-выражение (Simbolic expresion) - основная структура данных
в ЛИСПе.
(ДЖОН СМИТ 33 ГОДА) \ S-ВЫРАЖЕНИЯ ((МАША 21) (ВАСЯ 24) (ПЕТЯ 1)) /
S-выражение - это либо атом, либо список.
2 Атомы.
Атомы - это простейшие объекты Лиспа, из которых
строятся остальные структуры.
Атомы бывают двух типов - символьные и числовые.
Символьные атомы - последовательность букв и цифр,
при этом должен быть по крайней мере один символ
отличающий его от числа.
ДЖОН АВ13 В54 10А
Символьный атом или символ - это не идентификатор
переменой в обычном языке программирования.
Символ как правило обозначает какой либо предмет, объект
вещь, действие.
Символьный атом рассматривается как неделимое целое.
К символьным атомам применяется только одна операция:
сравнение.
В МCL в состав символа могут входить:
+ - * / @ $ % ^ _ \ <>
Числовые атомы - обыкновенные числа
124
-344
4.5 3.055Е8
Числа это константы.
Типы чисел зависят от реализации ЛИСПа
Атом - простейшее S-выражение.
3 Списки.
В ЛИСПЕ список это последовательность элементов (list).
Элементами являются или атомы или списки.
Списки заключаются в скобки, элементы списка разделяются
пробелами.
(банан) 1 атом
(б а н а н) 5 атомов
(a b (c d) e) 4 элемента
Таким образом список - это многоуровневая или иерархическая структура данных, в которой открывающиеся и закрывающиеся скобки находятся в строгом соответствии.
(+ 2 3) 3 атома
(((((первый) 2) второй) 4) 5) 2 элемента
Список, в котором нет ни одного элемента, называется пустым
списком и обозначается "()" или символом NIL.
NIL - это и список и атом одновременно.
Пустой список играет такую же важную роль в работе со списками,
что и ноль в арифметике.
Пустой список может быть элементом других списков.
(NIL) ;список состоящий из атома NIL
(()) ;то же самое, что и (NIL)
((())) ;- " -((NIL))
(NIL ()) ;список из двух других списков
4 Логические константы.
NIL обозначает кроме этого, в логических выражениях
логическую константу "ложь" (false).
Логическое "да"(true) задается символом "Т".
Атомы и списки - это символьные выражения или S-выражения.
Соотношение рассмотренных основных типов ЛИСПА поясняет
диаграмма:
Поиск на лиспе. Функционалы. Свойства символов
ЛЕКЦИЯ 7.
ПОИСК НА ЛИСПЕ. ФУНКЦИОНАЛЫ. СВОЙСТВА СИМВОЛОВ
Содержание
7.1 Алгоритм поиска на Лиспе.
( Функциональный подход к задаче о фермере,волке,козе и капусте.)
Фермер (Farmer), волк (Wolf), козел (Goat) и капуста (Cabbidge) находятся на одном берегу. Надо перебраться на другой берег на лодке.
Лодка перевозит только двоих. Нельзя оставлять на одном берегу козу и капусту, козу и волка.
Главная проблема в формировании алгоритма - найти эффективное представление структурой данных Лиспа информации о задаче.
Процесс перевозки может быть представлен последовательностью состояний. Состояние представляется списком из четырех элементов, каждый из которых отражает размещение объектов F, W, G, C:
(e w e w) - F, G на восточном берегу (e - east);
F W G C - W, C на западном берегу (w - west).
Определим две функции:
конструктор - make-state, которая берет в качестве аргументов размещение F, W, G, C
и возвращает состояние
(defun make-state (f w g c) (list f w g c)) |
и четыре функции доступа, каждая из которых берет состояние и возвращает размещение.
(defun farmer-side (state) (nth 0 state)) (defun wolf-side (state) (defun goat-side (state) (defun cabbage-side (state) |
Оставшаяся программа основывается на этих функциях доступа и конструкторах. В частности, они используются для реализации четырех возможных действий фермера:
- перевоз через реку или самого себя или W, G, C.
Эти функции используют четыре функции доступа для разбиения состояния на его компоненты.
Функция opposite ( определена позже ) определяет новое размещение объектов, которые пересекли реку, а make-state собирает их в новое состояние.
Например, функция farmer-takes-self может быть определена:
(defun farmer-take-self (state) (safe (make-state (opposite (farmer-side state)) (wolf-side state) (goat-side state) (cabbage-side state)))) |
Отметим, что эта функция возвращает новое состояние, независимо от того, безопасно оно или нет.
Если состояние безопасно, оно будет возвращено без изменений.
(defun safe (state) (cond ((and (equal (goat-side state) (wolf-side state)) (not (equal (farmer-side state) (wolf-side state)))) nil) ((and (equal (goat-side state) (cabbage-side state)) (not (equal (farmer-side state) (goat-side state)))) nil) (t state))) |
(defun path (state goal) (cond ((equal state goal)) (t (or (path (farmer-takes-self state) goal))) (path (farmer-take-wolf state) goal) (path (farmer-take-goat state) goal) (path (farmer-take-cabbage state) goal)) |
Напомним,что OR выполняет свои аргументы до тех пор, пока один из них не вернет не-nil величину. Когда это случается, OR завершается без выполнения других аргументов и возвращает это не-nil, как результат.
Таким образом, OR используется не только как логический оператор, но также обеспечивает способ управления поиском пути. OR используется здесь вместо cond, потому что величина, которая тестируется, и величина, которая возвращается в случае не-nil, одна и та же.
Одна проблема с этим определением заключается в том,что функция перемещения может вернуть значение nil, если перемещение не может быть сделано, когда оно ведет не к безопасному состоянию, чтобы предотвратить
path от попытки генерировать дочерние состояния от состояния
nil, она ( path), должна сначала проверять, является ли текущее состояние nil, если да, то path должна вернуть nil.
Другая проблема,которая возникает в реализации path, заключается в возможности возникновения петель в пространстве состояний. Если данную реализацию path запустить, фермер будет ездить взад-вперед между двумя берегами бесконечно, то есть алгоритм приведет к бесконечным переходам между двумя одинаковыми состояниями.
Чтобы предотвратить это, в path надо ввести третий параметр, been-list, список всех состояний, которые уже были достигнуты.
Аргумент, значением которого является функция, называют
функциональным аргументом , а функцию, имеющую функциональный аргумент -
функционалом.
Различие между понятиями
"данные" и
" функция", определяются не на основе их структуры, а в зависимости от использования.
Если аргумент используется в функции, как объект участвующий в вычислениях, то это данные..
Если аргумент используется как средство, определяющее вычисления, то это функция.
Отображающий функционал MAPCAR
Важный класс функционалов используемых в лиспе -
отображающие функционалы (МАР функционалы)
МАР функционалы - функции, которые некоторым образом отображают (map) список в новый список.
(MAPCAR f '(x1 x2 x3 ... xN))
MAPCAR функционал имеет два аргумента.
Первый аргумент - функция,
а второй - аргумент список.
Когда MAPCAR выполняется , функция определенная первым аргументом применяется к каждому элементу, списка, определенному вторым аргументом и результат помещает (отображает) в новый список. |
* (mapcar 'add1 '( 1 2 3)) (2 3 4) (MAPCAR f '(x1 x2 x3 ... xN)) эквивалентно (list (f 'x1) (f 'x2) .... (f 'xN)) |
(defun list-add1 (lis) (mapcar 'add1 lis)) * (list-add1 '(1 2 3)) (2 3 4) |
может быть использовано значение символа
* (setq x '(a b (d))) * (setq y 'atom) * (mapcar y x) (t t nil) |
MAPCAR для нескольких списков
MAPCAR может обрабатывать больше списков, если в функциональном аргументе несколько аргументов.
* (defun addlist (l1 l2) (mapcar '+ l1 L2)) * (addlist '( 1 2 3) '(1 2 3)) (2 4 6) т.е. (list (+ 1 1) (+ 2 2) (+ 3 3)) |
Лямбда выражения
Структура МАР функций ограничивает формы отображаемых функций.
Так, если мы желаем получить список с элементами
x * x + 1 Мы должны определить функцию (defun f1 (x) (+ 1 (* x x))) * (mapcar 'f1 '(1 2 3)) |
/p>
Таким образом определяется специальная функция, которая используется только в MAPCAR.
Аналогично происходит с add1.
Более эффективно в этом случае использовать, т.н.
лямбда выражения:
(mapcar '(lambda (x) (+ 1 (* x x))) '(1 2 3)) сравни (defun f1 (x) (+ 1 (* x x))) (mapcar '(lambda (x) (+ 1 x)) '(1 2 3)) |
Лямбда-выражения определяют функцию не имеющую имени.
Общая форма:
(lambda (параметры) )
Cвойства символов
В лиспе с символом можно связывать, не только
значение, но и информацию, называемую списком
свойств (property list).
Например, рассмотрим информацию o Mary:
|
(aqe 28 occupation lawyer salary 90 children ( Bill Alice Susan))
Чтение свойства
Узнать свойство атома можно используя функцию:
(GET <cимвол> <свойство>) возвращает значение
* ( get 'Mary 'age) 28 * ( get 'Mary 'children) ( Bill Alice Susan)) * ( get 'Mary 'hobby) nil |
Присвоение свойства
Чтобы задать свойство необходимо использовать обобщенную функцию присвоения
setf
( setf ( get <символ> <свойство>) <значение>)
* ( setf ( get 'Mary 'salary) 90) 90 |
putprop:
( putprop <символ> <значение> <свойство>)
<свойство> - нечисловой атом;
<значение> - любое выражение ;
Можно определить
(defun putprop ( atom value property) (setf (get atom property) value)) |
Свойств у атома может быть много, но у каждого только одно значение.
При внесении нового свойства, оно помещается вначале списка свойств.
* (putprop 'Mary 'cinema 'hobby) ( hobby cinema .....) |
Замена свойства
Замена значения свойства производится
повторным присвоением.
Например,
(putprop 'mary 29 'age) (get 'mary 'age) |
(putprop 'mary (+ 1 (get 'mary 'age)) 'age) |
Удаление свойства
Удаление свойства и его значения производится функцией
(remprop <символ> <свойство>)
*(remprop 'Mary 'age) T |
SYMBOL-PLIST
SYMBOL-PLIST даст информацию о списке свойств
* ( SYMBOL-PLIST 'Mary) (aqe 28 occupation lawyer salary 90 children ( Bill Alice Susan)) |
Рекурсия
ЛЕКЦИЯ 6.
РЕКУРСИЯ.
6. Р Е К У Р С И Я
Функция является рекурсивной, если в ее определении содержится вызов самой этой функции.
Рекурсия основной и самый эффективный способ организации повторяющихся вычислений в функциональном программировании и в лиспе.
ПРИМЕР.
Определим функцию MEMBER
(defun MEMBER (item list) (cond ((null list) nil) ((eql (car list) item) list) (t (MEMBER item (cdr list))))) |
6.1 Численная рекурсия
Предположим, что необходимо написать функцию sumall, которая имеет один аргумент, целое положительное число и возвращает сумму всех целых чисел между нулем и этим числом.
Например (sumall 9) должно вернуть 45
Это можно решить циклически; мы решим рекурсивно.
Отметим два факта:
1. Если n=0, сумма чисел между 0 и n равна 0.
2. Если n>0, сумма чисел между 0 и n
равна n плюс сумма чисел между 0 и n-1.
Эти два факта переводятся непосредственно в определение функции:
(defun sumall (n) (cond ((zerop n) 0) (t (+ n (sumall (- n 1)))))) |
Производится проверка n : равно нулю или нет.
Если значение n=0, то функция возвращает 0 .
В противном случае , функция вызывает сама себя для вычисления суммы чисел между 0 и n-1 и и добавляет n к этой сумме.
6.2 Как работает рекурсивная функция.
Посмотрим как работает рекурсивная функция. Проследим за несколькими вызовами.
Как работает (sumall 0) все ясно. Функция возвращает 0.
Эта ветвь в cond называется терминальной (terminating) завершающей, так как функция дает значение без рекурсивного вызова.
Если (sumall 1), то идет расчет по второй ветке,
которая называется рекурсивной, так как идет вызов самой себя.
В этом случае (+ 1 (sumall 0) и значение 1.
Если (sumall 2) , то по рекурсивной ветке (+ 2 (sumall 1)) и возвращает 3.
Если посмотреть,
(sumall 3) вызывает (sumall 2)
(sumall 1) вызывает (sumall 0).
После того как (sumall 0) вернет 0,
(sumall 1) вернет 1,
(sumall 2) вернет 3,
(sumall 3) это вызов верхнего уровня даст значение 6.
6.2.1 Трасса.
6.2.2 Правила записи рекурсивной функции.
Этот простой случай иллюстрирует несколько
правил в записи рекурсивной функции.
1. Терминальная ветвь необходима для окончания вызова. Без терминальной ветви рекурсивный вызов был бы бесконечным. Терминальная ветвь возвращает результат, который является базой для вычисления результатов рекурсивных вызовов. | |
2. После каждого вызова функцией самой себя, мы должны приближаться к терминальной ветви. В нашем случае вызовы уменьшали n и и была гарантия, что на некотором шаге будет вызов (sumall 0). Всегда должна быть уверенность, что рекурсивные вызовы ведут к терминальной ветви. |
Таким образом мы должны уметь писать рекурсивные функции, без того чтобы представлять точно порядок вычисления.
Как писать рекурсивные функции.
При написании рекурсивных функций мы должны планировать терминальные и рекурсивные ветви.
Таблица. Рекурсивная функция SUMALL
Шаг 1. Завершение (Терминальная ветвь)
n=0 - аргумент
(sumall 0) = 0 - значение
Шаг 2. Рекурсивная ветвь
Рекурсивные отношения между (sumall n) и (sumall(- n 1 )
2а. Примеры рекурсии
(sumall n) | (sumall(- n 1) |
(sumall 5)=15 | (sumall 4)=10 |
(sumall 1)=1 | (sumall 0)=0 |
(sumall n) может быть получена из (sumall (- n 1)
прибавлением N
1. Планирование терминальной ветви.
При написании рекурсивной функции мы должны решить, когда функция может вернуть значение без рекурсивного вызова.
2. Планирование рекурсивной ветви.
В этом случае мы вызываем функцию рекурсивно с упрощенным аргументом и используем результат для расчета значения при текущем аргументе.
Таким образом мы должны решить:
1. Как упрощать аргумент, приближая его шаг за шагом к конечному значению.
2. Кроме этого необходимо построить форму, называемую рекурсивным отношением, которая связывает правильное значение текущего вызова со значением рекурсивного вызова.
В нашем случае это (sumall n) и (sumall (- n 1)).
Иногда просто найти это отношение, а если не получается надо выполнить следующую последовательность шагов.
a. Определить значение некоторого простого вызова функции и ее соответствующего рекурсивного вызова.
b. Определить соотношение между парой этих функций.
Пример. Определим функцию power. Она берет два численных аргумента m и n вычисляет значение m в степени n.
(power 2 3) возвращает 8
Вначале составим рекурсивную таблицу.
Шаг 1. Завершение (Терминальная ветвь)
n=0 - аргумент
(power 2 0) = 1 - значение
Шаг 2. Рекурсивная ветвь
Рекурсивные отношения между
(power m n) и (power m (- n 1 ))
2а. Примеры рекурсии
(power 5 3) =125 (power 5 2) = 25
(power 3 1)=3 (power 3 0 )=1
2b. Характеристическое рекурсивное отношение
(power m n) может быть получена из (power m (- n 1)
умножением на m
(defun power (m n) (cond ((zerop n) 1) (t (* m (power m (- n 1)))))) |
6.4 CDR рекурсия.
Рассмотрена рекурсивная обработка чисел. Когда информация представлена в виде списка, то появляется необходимость рекурсивной обработки списков. Основная рекурсия над списками CDR рекурсия.
Пример. Написать функцию list-sum
которая берет один аргумент, список чисел, и возвращает сумму этих чисел.
Последовательно упрощающимся аргументом в этом случае будет список. Упрощение списка (cdr lis). Последнее значение аргумента nil.
Составим рекурсивную таблицу для (list-sum lis)
Шаг 1. Завершение (Терминальная ветвь)
(list-sum nil) = 0 - значение
Шаг 2. Рекурсивная ветвь
Рекурсивные отношения между
(list-sum lis) и (list-sum (cdr lis))
2а. Примеры рекурсии
(list-sum '(2 5 3)) =10 (list-sum '(5 3)) = 8
(list-sum '(3)) =3 (list-sum nil )=0
2b. Характеристическое рекурсивное отношение (list-sum lis) может быть получена из
(list-sum (cdr lis))
сложением с (car lis).
Текст функции.
(defun list-sum (lis ) (cond ((null lis) 0) (t (+ (car lis) (list-sum (cdr lis)))))) |
/p>
6.4.1 Вычисление (list-sum '(2 5 3)).
6.5 Несколько терминальных ветвей.
Мы рассмотрели случай рекурсии с одной терминальной и одной рекурсивной ветвью.
Однако в определении рекурсивной функции может быть несколько терминальных ветвей.
Две терминальные ветви будут в том случае, когда ведется поиск цели в последовательности значений и мы желаем получить результат, как только цель найдена.
Ветвь 1. Цель найдена и надо вернуть ответ
Ветвь 2. Цель не найдена и нет больше элементов.
Она имеет два аргумента : список чисел и заданное число. Функция возвращает первое число в списке превышающее заданное. Если этого числа нет - возвращается заданное число.
Программа.
(defun greaternum (lis num) (cond ((null lis) num) ((> (car lis) num) (car lis)) (t (greaternum (cdr lis) num)))) |
6.6 Несколько рекурсивных ветвей.
Несколько рекурсивных ветвей может понадобиться, если функция обрабатывает все элементы в структуре, но использует некоторые элементы отлично от других.
В этом случае составляются два рекурсионных отношения.
Пример. Напишите функцию negnums, которая получает список чисел и возвращает список, который содержит только отрицательные числа (0 положителен).
(negnums '(-1 5 -6 0 2)) возвращает (-1 -2)
Шаг 1. Завершение (Терминальная ветвь)
(negnums nil) = nil
Шаг 2. Рекурсивная ветвь
Рекурсивные отношения между (negnums l) и
(negnums (cdr l))
1. (car l ) < 0
2а. Примеры рекурсии
(negnums '(-5 3)) =(-5)
(negnums '(3)) = nil
(negnums '(-5 3 -6 0 )) =(-5 -6)
(negnums '( 3 -6 0 )) =(-6)
2b. Характеристическое рекурсивное отношение (negnums l) может быть получена из (negnums (cdr l))
(cons (car l) (negnums (cdr l))
2. (car l ) >= 0
2а. Примеры рекурсии
(negnums '(1 -5 3 -6 0 )) =(-5 -6)
(trace negnums) '(- 5 3 -6 0 )) = (-5 -6)
2b. Характеристическое рекурсивное отношение (negnums l) может быть получена из (negnums (cdr l))
(negnums l) = (negnums (cdr l)
Программа
(defun negnums (l) (cond ((null l) nil) ((< (car l) 0) (cons (car l) (negnums (cdr l)))) (t (negnums (cdr l))))) |
6.7 Общая форма.
Общая форма определения рекурсионной функции
(defun <имя> <параметры>
(cond (терминальная ветвь1)
(терминальная ветвь2)
...................
(терминальная ветвьn)
(рекурсивная ветвь1)
(рекурсивная ветвь2)
....................
(рекурсивная ветвьn)))
Внутреннее представление списков. Применяющие функционалы
ЛЕКЦИЯ 8.
ВНУТРЕННЕЕ ПРЕДСТАВЛЕНИЕ СПИСКОВ. ПРИМЕНЯЮЩИЕ ФУНКЦИОНАЛЫ
Содержание
8.1 Внутреннее представление списков
8.1.1 Структура памяти
Каждый атом занимает ячейку.
Списки, являются совокупностью атомов, и связываются вместе специальными элементами памяти, называемыми списочными ячейками или
cons-ячейки.
Каждая списочная ячейка состоит из двух частей, полей.
Первое поле - CAR, второе CDR
Поля типа списочная ячейка содержат указатели на другие ячейки, или nil.
Если обе ячейки содержат указатели на атомы, то можно записать проще
Этому случаю соответствует структура (a.b)
которая называется точечной парой.
8.1.2 Представление списков через списочную ячейку.
Список из одного атома, представляется, как
NIL указывает на конец списка.
Вместо nil пишут - \.
Список получается как операция (cons 'a nil)
Список из двух элементов (b a)
Правое поле указывает на cdr списка (хвост).
Левое поле, на саr
списка(голову).
Каждому элементу списка соответствует списочная ячейка.
Список (a b c d) будет представлен как :
Если список не одного уровня (a (b c) d), то каждому элементу списка соответствует списочная ячейка.
Причем саr поле второй списочной ячейки указывает на вложенный список.
8.1.3 Представление списков через точечные пары.
Любой список можно записать в точечной нотации.
(a) (a.nil) |
(a b c) (a.(b.(c.nil)))
Выражение представленное в точечной нотации можно привести к списочной если cdr поле является списком.
(a.(b c)) <=> (a b c)
(a.(b.c)) <=> (a b.c)
8.1.4 Списочная ячейка и базовые функции.
Результатом действия функции car
будет значение левого поля первой списочной ячейки
* (сar '(a (b c) d)
a
Результатом действия функции cdr
будет значение правого поля первой списочной ячейки.
* (сdr '(a (b c) d)
((b c) d)
CONS создает новую списочную ячейку, car поле которой указывает на первый элемент, а cdr на второй
(cons 'x '(a b c)) |
* (list 'a '(b c)) (a (b c)) |
1. Создается списочная ячейка для каждого аргумента функции
2. В car поле ставится указатель на соответствующий элемент
3. В cdr поле ставится указатель на следующую списочную ячейку
8.1.5 Переменные и списки.
Рассмотрим выражение
(setq y '(a b c))
Переменная Y будет иметь значение '(a b c)
(setq x (cons 'd y))
Если в функции присвоения список задается явно, то под него отводятся новые списочные ячейки.т.е.
(setq z '(a b c))
Переменная z будет иметь значение '(a b c)
8.1.6 EQ и EQUAL.
EQ проверяет физическое равенство списков, и EQUAL -логическое, т.е. для EQ необходимо, чтобы списки имели одинаковую стpуктуpу, а для EQUAL одинаковые элементы. (Структура списка определяется списочными ячейками).
* (setq lis2 '(a b))
Другая структура списка
* (setq lis3 lis1) * (equal lis1 lis2) t * (equal lis1 lis3) t * (eql lis1 lis2) nil * (eql lis1 lis3) t * (eq lis1 lis2) nil * (eq lis1 lis3) t |
* (setq m 'abc) * (setq n 'abc) * (eq m n) t |
8.1.7 Cборка мусора
В результате вычислений в памяти могут возникнуть структуры, на которые нельзя ссылаться. Это происходит, когда вычисляемая структура не сохраняется с помощью setq, или когда теряются ссылки на старое значение.
Например
(setq l1 '((a) b c)) (setq l1 (cdr l1)) |
Для повторного использования ставшей мусором памяти в лисп системах предусмотрен специальный сборщик мусора, (garbage collector) GC, который автоматически запускается когда в памяти остается мало места.
8.2 Обработка списков без разрушения.
(rplaca x y) (setf (car x) y) (rplacd x y) (setf (cdr x) y) |
Например, рассмотрим функцию, replace-item, которая имеет три элемента: первый элемент должен быть списком. Функция разрушающе замещает первое местоположение второго аргумента в списке на третий аргумент.
(defun replace-iteme (lis old new) (rplaca (member old lis) new). |
8.3.3 Использование разрушающих функций.
Разрушающие функции необходимо использовать при работе с большими списками, чтобы не увеличивать расход памяти, например использовать nconc вместо append.
Однако использование разрушающих функций приводит к побочным эффектам.
Можно получить бесконечные списки:
* (setq v1 '(a b c)) (a b c) * (setq v2 v1) (a b c) * (setq v2 (nconc v1 v2)) (a b c a b c....) |
8.4 Применяющие функционалы.
Одним из видов функционалов, используемых в лиспе являются применяющие функционалы. Они применяют функциональный аргумент к его параметрам.
Так как применяющие функционалы вычисляют значение функции, в этом смысле они аналогичны функции EVAL,
вычисляющей значение выражения.
8.4.1 APPLY.
Предположим мы хотим объединить в один список несколько вложенных списков, т.е. из
((a b c) (d e f) (k l)) получить (a b c d e f k l).
Для этой задачи используем функцию apply. APPLY имеет два аргумента: имя функции и список, и применяет названную функцию к элементам списка, как к аргументам функции.
(defun list-mean (lis) (/ (apply '+ '(lis) (length lis))) * (list-mean '(1 2 3 4)) 2.5 |
Мы хотим найти общее число элемент в списках
(countall '((a b c) (d e f) (k l))) (defun countall (lis) (apply '+ (mapcar 'length lis))) |
Например
* (countatom '(a (a (b) c) (d) e (f g)))
8
(defun countatom (lis) (cond ((null lis) 0) ((atom lis) 1) (t (apply '+ (mapcar 'countatom lis))))) |
8.4. 2 Cочетание apply, nconc, mapcar - mapcan.
Построить функцию list-last, образующую список из хвостов списков.
Например
* (list-last '((a b) (b c) (c d))) возвращает (b c d)
(defun list-last (lis) (apply 'append (mapcar 'last lis))) |
Можно это сделать через nconc:
(defun list-last (lis) (apply 'nconc (mapcar 'last lis))) |
(mapcan fn x1 x2 ... xN) (apply 'nconc (mapcar fn x1 x2 ... xN)) |
(defun list-last (lis) (mapcan 'last lis)) |
8.4.3 Функционал FUNCALL.
Применяющий функционал FUNCALL
аналогичен APPLY, но аргументы он
принимает, не в списке, а по отдельности:
(funcall fn x1 x2 ... xN) (fn x1 x2 ... xN)
Здесь fn - функция с n aргументами.
Например, * (funcall '+ 1 2) * (+ 1 2) 3 * (funcall (car '(+ - / *)) 1 2) 3 |
Рассмотрим использование funcall для построения функции map2, которая действует аналогично mapcar, но берет в качестве аргументов два элемента из списка, а не один.
Например:
* (map2 'list '(A Christie V Nabokov K Vonnegut))
дает ((A Christie) (V Nabokov) (K Vonnegut))
Эта функция имеет вид:
(defun map2 (f2 lst) (if (null lst) nil (cons (funcall f2 (car lst) (cadr lst)) (map2 f2 (cddr lst))))) |