Функциональное программирование

          

Чтение и запись информации в файлы


ЛЕКЦИЯ 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




 
В MCL можно использовать только три буквы, в других реализациях больше.

Функциональное программирование

Функциональное программирование

Функциональное программирование

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))
(area 20)
(perimetr 18)
(perimetr 18)

Можно сначала рассчитать площадь, т.е. определить

Функциональное программирование
(defun rectangle (dim)
(let ((len (car dim)) (wid (cadr dim))
(area (* len wid))
(print ( 'area area))
(print (list 'perimeter (* (+ len wid)))))))

Обращение

* (rectangle '(4 5))


даст ошибку, т.к значение area неопределено.


Надо использовать предложение 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.

Если return не встретился - результат prog будет nil .
Функциональное программирование
* (s-d)
(type number)8
(type number)1
9
7
nil

Если локальных переменных нет записывается (prog ()...)

Функциональное программирование

5.3 Дополнительные функции печати



PRINT печатает значение аргумента без пробела и перевода на другую строку:
Функциональное программирование
* (progn (print 1) (print 2) (print 3))
123

СТРОКИ - последовательность знаков заключенная в кавычки.
Функциональное программирование
"string"

СТРОКА - специальный тип данных в лиспе. Это атом, но не может быть переменной. Как у числа значение строки сама строка.
Функциональное программирование
* "(+ 1 2)"
"(+ 1 2)"

Строки удобно использовать для вывода с помощью оператора PRINC.

PRINC печатает строки без "".

PRINC печатает аргумент без пробела и перевода строки

Пример

Функциональное программирование
* (progn (setq x 4) (princ " x = ")
(prin1 x) (princ " m "))
x = 4 m

" 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)))))

Еще один пример численной итерационной функции. Определим функцию выполняющую умножение двух целых чисел через сложение. Т.е. умножение x на y выполняется сложением x с самим собой y раз.
Функциональное программирование
Например,

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))

То же, только через DO

Функциональное программирование
(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)

Если есть необходимость можно использовать DO* аналогично LET*.

Функциональное программирование

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 возвращает Т. Если аргумент любое значение не-NIL,
NOT возвращает NIL.


Функциональное программирование

NOT имеет один аргумент, который может быть
любым s-выражением (не только предикатом).

( NOT < s-выражение >)

Примеры:

Функциональное программирование

* ( not ( zerop 1 ) )
T


Функциональное программирование

* ( 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.

( PRINT < arg >)
print перед выводом аргумента переходит на новую строку,

а после него выводит пробел.


* ( 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)
(nth 1 state))

(defun goat-side (state)
(nth 2 state))

(defun cabbage-side (state)
(nth 3 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))

Эта версия функции path является простым переводом и содержит несколько ошибок, которые надо исправить. В частности, отметим использование формы OR для управления выполнением ее аргументов.

Напомним,что OR выполняет свои аргументы до тех пор, пока один из них не вернет не-nil величину. Когда это случается, OR завершается без выполнения других аргументов и возвращает это не-nil, как результат.

Таким образом, OR используется не только как логический оператор, но также обеспечивает способ управления поиском пути. OR используется здесь вместо cond, потому что величина, которая тестируется, и величина, которая возвращается в случае не-nil, одна и та же.

Одна проблема с этим определением заключается в том,что функция перемещения может вернуть значение nil, если перемещение не может быть сделано, когда оно ведет не к безопасному состоянию, чтобы предотвратить

path от попытки генерировать дочерние состояния от состояния

nil, она ( path), должна сначала проверять, является ли текущее состояние nil, если да, то path должна вернуть nil.

Другая проблема,которая возникает в реализации path, заключается в возможности возникновения петель в пространстве состояний. Если данную реализацию path запустить, фермер будет ездить взад-вперед между двумя берегами бесконечно, то есть алгоритм приведет к бесконечным переходам между двумя одинаковыми состояниями.

Чтобы предотвратить это, в path надо ввести третий параметр, been-list, список всех состояний, которые уже были достигнуты.



Аргумент, значением которого является функция, называют

функциональным аргументом , а функцию, имеющую функциональный аргумент -

функционалом.

Различие между понятиями

"данные" и

" функция", определяются не на основе их структуры, а в зависимости от использования.

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

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

Функциональное программирование

Отображающий функционал MAPCAR

Важный класс функционалов используемых в лиспе -

отображающие функционалы (МАР функционалы)

МАР функционалы - функции, которые некоторым образом отображают (map) список в новый список.

Функциональное программирование
MAPCAR один из основных отображающих функционалов.

(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)

В качестве аргумента для MAPCAR

может быть использовано значение символа
Функциональное программирование
* (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
свойство значение
Список свойств в этом случае выглядит

(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). Всегда должна быть уверенность, что рекурсивные вызовы ведут к терминальной ветви. Функциональное программирование
3. Проследить вычисления в рекурсии чрезвычайно сложно. Очень трудно мысленно проследить за действием рекурсивных функций. Это практически невозможно для функций более сложных, чем sumall.

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

Функциональное программирование

Как писать рекурсивные функции.

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

Таблица. Рекурсивная функция 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
2b. Характеристическое рекурсивное отношение

(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 рекурсия.

Функциональное программирование
Логика и структура СDR рекурсии сходна с численной рекурсией.

Пример. Написать функцию 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. Цель не найдена и нет больше элементов.

Функциональное программирование
Пример. Написать функцию greaternum.

Она имеет два аргумента : список чисел и заданное число. Функция возвращает первое число в списке превышающее заданное. Если этого числа нет - возвращается заданное число.

Программа.
Функциональное программирование
(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

* (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))

Функциональное программирование
CONS не изменяя структуры, увеличивает список.

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

(setq z '(a b c))

Переменная z будет иметь значение '(a b c)

Функциональное программирование
Функциональное программирование

8.1.6 EQ и EQUAL.

EQ проверяет физическое равенство списков, и EQUAL -логическое, т.е. для EQ необходимо, чтобы списки имели одинаковую стpуктуpу, а для EQUAL одинаковые элементы. (Структура списка определяется списочными ячейками).
Функциональное программирование
*(setq lis1 '(a b))

* (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

Часто apply используют вместе c марсаr.

Мы хотим найти общее число элемент в списках

Функциональное программирование
(countall '((a b c) (d e f) (k l)))

(defun countall (lis)

(apply '+ (mapcar 'length lis)))

Можно определить более сложную функцию countatom, которая считает элементы на в любом списке.

Например

* (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)))

APPEND работает медленно и оставляет много мусора.

Можно это сделать через nconc:

Функциональное программирование
(defun list-last (lis)

(apply 'nconc (mapcar 'last lis)))

В лиспе имеется отображающий функционал mapcan

Функциональное программирование
(mapcan fn x1 x2 ... xN)

(apply 'nconc (mapcar fn x1 x2 ... xN))

T.е. mapcan объединяет результаты в один список, используя функцию nconc.
Функциональное программирование
(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)))))

Функциональное программирование