Презентация на тему Функции

Презентация на тему Презентация на тему Функции, предмет презентации: Разное. Этот материал содержит 102 слайдов. Красочные слайды и илюстрации помогут Вам заинтересовать свою аудиторию. Для просмотра воспользуйтесь проигрывателем, если материал оказался полезным для Вас - поделитесь им с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций ThePresentation.ru в закладки!

Слайды и текст этой презентации

Слайд 1
Текст слайда:

Логика и управление

Функции

Eugeny L Yakimovitch http://desk.by/~ewger 2008


Слайд 2
Текст слайда:

Содержание главы

Другие функции работы со списками
Еще раз о представлении списков в памяти
Базовые предикаты
Формы и пользовательские функции
Управление вычислением


Слайд 3
Текст слайда:

Вступление

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

Каким образом связаны между собой следующие составляющие языка Lisp:
Организация списков в памяти
Символьное представление программы
Вычисление логических выражений в виде T и NIL
Ветвление (cond), цикличность (loop) и рекурсивность исполняемой программы при помощи управляющих конструкций

Как работает ЛИСП ?


Слайд 4
Текст слайда:

Для того чтобы, хорошо понимать механизмы вычисления Lisp программ, необходимо следующее:
знание способа представления списочных структур в памяти
возможность обхода данных структур на основании вычислений списка символьных выражений
понимание булевской алгебры для вычисления простых утверждений


Слайд 5
Текст слайда:

Составляющая управления
В этом смысле любая задача управления превращается в задачу выбора (отсечения) для определения направления ветвления программы.
Логическая составляющая
Операции выбора способа вычисления символьного выражения предшествует вычисление условий выбора


Слайд 6
Текст слайда:

ДРУГИЕ ФУНКЦИИ РАБОТЫ СО СПИСКАМИ



Слайд 7
Текст слайда:

Дополнительные функции обработки списков

APPEND
REVERSE
LAST


Слайд 8
Текст слайда:

APPEND

Функция APPEND объединяет два и более списков в один.

( APPEND < список - 1 > < список - 2 > )
Пример:

>( append ' ( a b ) ' ( c ) )
( a b c )

APPEND объединяет элементы, не изменяя их.
>( append ' ( list ) ' ( ' ( a b ) ' ( c ) ) )
( list ( quote ( a b ) ) ( quote ( c ) ) )


Слайд 9
Текст слайда:

Объединяющие функции

Рассмотрим несколько примеров, чтобы показать отличие APPEND, LIST, CONS.

Примеры:
>( list ' ( a b ) ' ( c d ) )
( ( a b ) ( c d ) )
>( cons ' ( a b ) ' ( c d ) )
( ( a b ) c d )
>(append ' ( a b ) ' ( c d ) )
( a b c d )

cons всегда берет два аргумента и помещает первый в начало второго.
list берет один или больше аргументов и образует список, помещая аргументы в скобки.
append образует новый список, убирая скобки вокруг аргументов и помещая их в один список


Слайд 10
Текст слайда:

Сравнение CONS, LIST, APPEND


Слайд 11
Текст слайда:

REVERSE

Функция REVERSE изменяет порядок элементов в аргументе.

( REVERSE < список > )

Пример:
>( reverse ' ( a b c ) )
( c b a )

Аргументом reverse должен быть список. reverse не меняет порядок в списках более нижнего уровня.

>( reverse ' ( ( a b c ) e ) )
( e ( a b c ) )


Слайд 12
Текст слайда:

LAST

Функция LAST удаляет из списка все элементы кроме последнего

( LAST < список > )

Пример:
>( last ' ( a b c ) )
( c )


Слайд 13
Текст слайда:

ВНУТРЕННЕЕ ПРЕДСТАВЛЕНИЕ СПИСКОВ



Слайд 14
Текст слайда:

Лисповская память состоит из списочных ячеек
Значение представляется указателем
CAR и CDR выбирают поле указателя
CONS создает ячейку и возвращает на нее указатель
У списков могут быть общие части
Логическое и физическое равенство не одно и то же
Точечная пара соответствует списочной ячейке
Варианты точечной и списочной записей
Управление памятью и сборка мусора
Вычисления, изменяющие и не изменяющие структуру
RPLACA и RPLACD изменяют содержимое полей
■ Изменение структуры может ускорить вычисления


Слайд 15
Текст слайда:

Лисповская память состоит из списочных ячеек

Оперативная память машины, на которой работает Лисп-система, логически разбивается на маленькие области, которые называются списочными ячейками. Списочная ячейка состоит из двух частей, полей CAR и CDR. Каждое из полей содержит указатель. Указатель может ссылаться на другую списочную ячейку или на некоторый другой лисповский объект, как, например, атом.


Слайд 16
Текст слайда:

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

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


Слайд 17
Текст слайда:

Графически списочная ячейка представляется прямоугольником (рис.), разделенным на части (поля) CAR и CDR. Указатель изображается в виде стрелки, начинающейся в одной из частей прямоугольника и заканчивающейся на изображении другой ячейки или атоме, на которые ссылается указатель.


Слайд 18
Текст слайда:

Значение представляется указателем

Указателем списка является указатель на первую ячейку списка. На ячейку могут указывать не только поля CAR и CDR других ячеек, но и используемый в качестве переменной символ, указатель из которого ссылается на объект, являющийся значением символа. Указатель на значение хранится вместе с символом в качестве его системного свойства.


Слайд 19
Текст слайда:

Побочным эффектом функции присваивания SETQ является замещение указателя в поле значения символа. Например, следующий вызов:
_(setq список '(а Ь с))
(А В С)
создает в качестве побочного эффекта изображенную на рис. штриховую стрелку.


Слайд 20
Текст слайда:

Графически ссылку на пустой список изображают в виде перечеркнутого поля. Указатели из полей CAR ячеек списка ссылаются на структуры, являющиеся элементами списка, в данном случае на атомы А, В и С.


Слайд 21
Текст слайда:

CAR и CDR выбирают поле указателя

_(саг список)
А
_(cdr список)
(В С)


Слайд 22
Текст слайда:

CONS создает ячейку и возвращает на нее указатель

Допустим, что у нас есть два списка:
_(setq голова'(Ь с))
(В С)
_(setqхвост '(a b с))
(А В С)
Вызов функции
_(cons голова хвост)
((В С) А В С)
строит новый список из ранее построенных списков ГОЛОВА и ХВОСТ так, как это показано на рис.


Слайд 23
Текст слайда:

Заметим, что применение функции CONS не изменило структуры списков, являющихся аргументами, и не изменило значений переменных ГОЛОВА и ХВОСТ.


Слайд 24
Текст слайда:

У списков могут быть общие части

На одну ячейку может указывать одна или более стрелок из списочных ячеек, однако из каждого поля ячейки может исходить лишь одна стрелка. Если на некоторую ячейку есть несколько указателей, то эта ячейка будет описывать общее подвыражение. Например, в списке
(кто-то приходит кто-то уходит)
символ КТО-ТО является общим подвыражением, на которое ссылаются указатели из поля CAR из первой и из третьей ячейки списка.


Слайд 25
Текст слайда:

Если элементами списка являются не атомы, а подсписки, то на месте атомов будут находится первые ячейки подсписков. Например, построенная вызовом
_(setq список '((Ь с) a b с)
((В С) А В С)
структура изображена на рис.


Слайд 26
Текст слайда:

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


Слайд 27
Текст слайда:

_(car список1)
(B С)
_(cddr список1)
(B С)
являются логически одинаковым списком
(В С), хотя они и представлены различными cписочными ячейками:
_(equal (car список1) (cddr список1))
Т


Слайд 28
Текст слайда:

Однако список (В С), как видно из следующего рис., может состоять и из тех же ячеек.


Слайд 29
Текст слайда:

Эту структуру можно создать с помощью следующей последовательности вызовов:
_(setq bс ‘(b c))
(В С)
_(setq abc (cons 'a bc))
(ABC)
_(setq список2 (cons bc abc))
((В С)А В C)
_Список2
((В С)А В C)


Слайд 30
Текст слайда:

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


Слайд 31
Текст слайда:

Логическое и физическое равенство

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


Слайд 32
Текст слайда:

Точечная пара соответствует списочной ячейке

Определяя базовую функцию CONS, мы предполагали, что ее вторым аргументом является список. Это ограничение не является необходимым, так как при помощи списочной ячейки можно было бы, например, результат вызова
(cons 'а 'Ь)
представить в виде структуры, изображенной на рис.


Слайд 33
Текст слайда:

На рис. показан не список, а более общее символьное выражение, так называемая точечная пара. Для сравнения на следующем рис. мы изобразили список (А В).


Слайд 34
Текст слайда:

Название точечной пары происходит из использованной в ее записи точечной нотации, в которой для разделения полей CAR и CDR используется выделенная пробелами точка:
_(cons 'а 'b)
(А . В)
Выражение слева от точки (атом, список или другая точечная пара) соответствует значению поля CAR списочной ячейки, а выражение справа от точки - значению поля CDR. Базовые функции CAR и CDR действуют совершенно симметрично:


Слайд 35
Текст слайда:

_(саr '(а . b)) ; обратите внимание на А ; пробелы, выделяющие точку
_(cdr '(а . (b . с))) (В . С)
Точечная нотация позволяет расширить класс объектов, изображаемых с помощью списков.


Слайд 36
Текст слайда:

Варианты точечной и списочной записей

Любой список можно записать в точечной нотации. Преобразование можно осуществить (на всех уровнях списка) следующим образом:
(al a2 ... aN)

(al . (a2 . ...(aN . NIL)...))


Слайд 37
Текст слайда:

Приведем пример:
(a b(c d) e)
(а . (b . ((с . (d . NIL)) . (e . NIL))))
Признаком списка здесь служит NIL в поле CDR последнего элемента списка, символизирующий его окончание.
Транслятор может привести записанное в точечной нотации выражение частично или полностью к списочной нотации.
(al . (а2 аЗ)) ⬄ (al a2 аЗ)
(al . (а2 . аЗ)) ⬄ (al a2 . аЗ)
(al a2 . NIL) ⬄ (al a2 . ())


Слайд 38
Текст слайда:

_'(а . (b .(с .(d)))
(А В С D)
_'((а Ь) .(Ь с))
((А В) В С)
_'(а . nil)
(А)
_'(а . (Ь .с))
(А В . С)
_'((((nil .а) .b) . с) . d)
((((NIL . A) . В). С) . D)


Слайд 39
Текст слайда:

Использование точечных пар в программировании на Лиспе в общем-то излишне. Точечные пары применяются в теории. Часто с их помощью обозначают список заранее неизвестной длины в виде
(голова . хвост)
Точечные пары используются совместно с некоторыми типами данных и с ассоциативными списками.


Слайд 40
Текст слайда:

Управление памятью и сборка мусора

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


Слайд 41
Текст слайда:

Если списку СПИСОКЗ
_(setq списокЗ)
'((это станет мусором) cdr часть))
(ЭТО СТАНЕТ МУСОРОМ) CDR ЧАСТЬ)
присвоить новое значение
_(setq списокЗ (cdr списокЗ))
(CDR ЧАСТЬ)
то CAR-часть отделяется, поскольку указатель из атома СПИСОКЗ начинает ссылаться так, как это изображено на рисунке при помощи штриховой стрелки. Теперь уже нельзя через символы и указатели добраться до четырех списочных ячеек. Говорят, что эти ячейки стали мусором.


Слайд 42

Слайд 43
Текст слайда:

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


Слайд 44
Текст слайда:

Вычисления, изменяющие и не изменяющие структуру

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


Слайд 45
Текст слайда:

RPLACA и RPLACD изменяют содержимое полей

Основными функциями, изменяющими физическую структуру списков, являются RPLACA (replace CAR) и RPLACD (replace CDR) которые уничтожают прежние и записывают новые значения в поля CAR и CDR списочной ячейки:
(RPLACA ячейка значение-поля)
(RPLACD ячейка значение-поля)


Слайд 46
Текст слайда:

Обе функции возвращают в качестве результата указатель на измененную списочную ячейку.
_(setq поезд ‘(паровоз1 А В C))
(ПАР0ВОЗ1 A B C)
_(rplaca поезд 'паровоз2)
(ПАР0В032 А В С)
_поезд
(ПАР0В032 A B C)
_(грlаса (cdr поезд) 'тендер)
(ТЕНДЕР В С)
_поезд
(ПАР0В032 ТЕНДЕР В С)


Слайд 47
Текст слайда:

Функция RPLACD выполняется так же, как RPLACA, с той разницей, что меняется значение поля CDR:
_(rplacd поезд '(к l m))
(ПАР0В032 К L M)
_поезд
(ПАР0В032 К L М)


Слайд 48
Текст слайда:

Используя функцию RPLACD, можно, например, определить функцию КРУГ, превращающую произвольный список в кольцо:
_(defun круг (х) (делай-круг х х))
КРУГ
_(defun делай-круг (х у)
(cond ((null x) x)
((nail (cdr x)) (rplacd x у))
(t (делай-круг (cdr x) у)))) ДЕЛАИ-КРУГ
(круг '(а b с))


Слайд 49
Текст слайда:

БАЗОВЫЕ ПРЕДИКАТЫ



Слайд 50
Текст слайда:

Определение

Предикат в Лиспе - это функция, которая определяет, обладает ли аргумент определенным свойством, и возвращает в качестве значения T или NIL.

Обычно, такие функции заканчиваются на p (predicate – англ. утверждение)


Слайд 51
Текст слайда:

Предикат ATOM

ATOM проверяет, является ли аргумент атомом. Значение будет Т, если атом, и nil в обратном случае.

( ATOM < S - выражение >)
Примеры:
>( atom 'x )
t
>( atom '( a b ) )
nil
>( atom ( cdr ' ( a b ) ) )
nil
>( atom ( car ' ( a b ) ) )
t
Предикат atom с пустым списком nil:
>( atom nil )
t
>( atom ( ) )
t


Слайд 52
Текст слайда:

Предикат EQ

Предикат EQ сравнивает два символа и возвращает Т, если они одинаковые, и nil в обратном случае.
( EQ < выражение 1 > < выражение 2 > )
Примеры:
>( eq ' cat ' cat )
t
>( eq ' cat ' dog )
nil
>( eq ' cat ( car ' ( cat dog ) )
t
>( eq t ' t )
t
EQ можно применять к числам, если они представлены одним типом.
>( eq 123 123 )
t


Слайд 53
Текст слайда:

Предикат =

Предикат "=" сравнивает числа различного типа.
( = < число - 1 > < число - 2 > )
>(= 3 3.0 )
t
>(= 3 0.3F 01 )
t

Замечание: диалект arc http://arclanguage.org/

Использует синтаксис (= x 1) как присваивание


Слайд 54
Текст слайда:

Предикат EQL

Сравнивает и числа и символы. ( EQL arg1 arg2 )

Истина только в том случае, если arg1 arg2 эквивалентны по ЕQ, или это числа одного и того же типа, имеющие одно и тоже значение.

( EQL < аргумент - 1 > < аргумент - 2 > )
>( eql ' a ' a )
t
>( eql ' 12 ' 12 )
t


Слайд 55
Текст слайда:

Предикат EQUAL

EQUAL - самый общий предикат. Сравнивает не только символы, числа ну и списки:
числа эквивалентны по equal,
символы эквивалентны по equal,
списки эквивалентны по equal,
если их изображения совпадают.
( EQUL < аргумент - 1 > < аргумент - 2 > )
>( equal ' (a b c ) ' ( a b c ) )
t
>( equal nil ' ( ( ) ) )
nil


Слайд 56
Текст слайда:

Предикат NULL

Предикат NULL проверяет, является ли аргумент пустым списком.
( NULL < аргумент >)
>( null ' ( ) )
T
>( null nil )
T
>( null t )
nil


Слайд 57
Текст слайда:

Предикаты типов


Слайд 58
Текст слайда:

Числовые предикаты



Слайд 59
Текст слайда:

ФОРМЫ И ФУНКЦИИ



Слайд 60
Текст слайда:

Понятие формы

Любой вычислимый объект
Символ, композиция форм (сложная форма), или самовычисляемый объект
(<> form) сложная форма включающая оператор как первый элемент. Блокировка формы есть константная форма.


Слайд 61
Текст слайда:

Определение формы

Форма есть любой вычислимый объект, представленный в виде вложений и сочетаний других форм или способа собственного вычисления.
В Lisp различают следующие формы:
Символьные выражения
Функции и операторы
Макросы


Слайд 62
Текст слайда:

Определение функций

Для задания новых функций в Лиспе используется специальная форма defun
( defun < имя-функции > < параметры > < тело-функции >)

Пример:
*( defun cons-2 ( x y oldlist )
( cons x ( cons y oldlist ) ) ) )

Имя функции - символ.
Параметры - список аргументов.
Tело функции - вычисляемая форма от аргументов
Значение определения функции defun - имя функции.


Слайд 63
Текст слайда:

Пример использования функции

Задача: необходимо поместить два элемента в начало списка, причем эту операцию мы хотели бы выполнять несколько раз с различными элементами.
Например:
>( cons ' a (cons ' b ' ( c d ) ) )
( a b c d )

или

>( cons ' train (cons ' truck ' (bus car boat ) ) )
( train truck bus car boat )

Используем объявленную ранее функцию:
>( cons-two ' a ' b ' ( c d ) )
( a b c d )
>( cons-two ' train ' truck ' ( bus car boat ) )
( train truck bus car boat )


Слайд 64
Текст слайда:

Вызов функции

( < имя-функции > < значения аргументов >)

>( cons-two ' a ' b ' ( c d ) )
( a b c d )


Слайд 65
Текст слайда:

Значение функции

Значение тела функции при заданных аргументах.

Примеры:
>( defun double ( num ) ( * 2 num ) )
( double 7 )
14

Определенную функцию можно использовать как встроенную:
>( setq z ( double ( + 5 10 ) ) )
30
>( double z )
60


Слайд 66
Текст слайда:

Примеры

Необходимо элемент new поместить на второе место в списке: ( a c d ), в результате должно получиться ( a new c d )

Назовем функцию insert-second. Она зависит от двух аргументов: item и oldlist.

Тело функции:
( cons ( car oldlist ) ( cons item ( cdr oldlist ) ) )

Таким образом, определим функцию:
>( defun insert-second ( item oldlist )
( cons ( car oldlist ) ( cons item ( cdr oldlist ) ) )
>( insert-second 'b '( a c d ) )
( a b c d )


Слайд 67
Текст слайда:

Передача параметров

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


Слайд 68
Текст слайда:

Локальные и глобальны переменные. Пример

Например:
>( defun f ( x ) ( setq x ' new ) ) ; меняет значение x
f
>( setq x ' old )
old
>x
old
>( f x )
New


Еще пример:
>( defun double ( num ) ( > num 2 )
double
>( setq num 5 )
5
>( double 2 )
4
>num
5


Слайд 69
Текст слайда:

Свободные переменные

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

Например:
>( defun f1 ( y ) (setq x 3 ) )
f1
>( f1 5 )
3
>x
3


Слайд 70
Текст слайда:

Расчет сопротивления цепи

Задача:
Написать программу расчета сопротивления цепи.
r1=r2=r3=10

Последовательное соединение (serial)
R = R1 + R2
Функция (s_r R1 R2)
Определение: ( defun s_r ( R1 R2 ) (+ R1 R2 ) )


Параллельное соединение (parallel)
R = ( R1 > R2 ) / ( R1 + R2 )
Функция ( p_r R1 R2 )
Определение: ( defun p_r ( R1 R2 ) ( / ( > R1 R2 ) ( + R1 R2 ) ) )


Слайд 71
Текст слайда:

(Продолжение)

Расчет:
>(s_r 10 ( p_r 10 10 ) )
15
Усложним цепь:
r1=r2=r3=r4=10
Расчет:
> ( p_r 10 ( s_r 10 ( p_r 10 10 ) ) )
и т.д.


Слайд 72
Текст слайда:

УПРАВЛЕНИЕ ВЫЧИСЛЕНИЕМ



Слайд 73
Текст слайда:

Программа состоит из форм и функций
Управляющие структуры Лиспа являются формами LET создает локальную связь
Последовательные вычисления: PROG1, PROG2 и PROGN
Разветвление вычислений: условное предложение COND
Другие условные предложения: IF, WHEN, UNLESS и CASE
Циклические вычисления: предложение DO
Предложения PROG, GO и RETURN
Другие циклические структуры
Повторение через итерацию или рекурсию
Формы динамического прекращения вычислений: CATCH и THROW


Слайд 74
Текст слайда:

Программа состоит из форм и функций

Под формой (form) понимается такое символьное выражение, значение которого может быть найдено, интерпретатором. Ранее мы уже использовали наиболее простые формы языка: константы, переменные, вызовы функций и их сочетания. Кроме них были рассмотрены некоторые специальные формы, такие как QUOTE и SETQ, трактующие свои аргументы иначе, чем обычные функции. Лямбда-выражение без фактических параметров не является формой.


Слайд 75
Текст слайда:

Вычислимые выражения можно разделить на три группы:
Самоопределенные (аксиоматические) формы. Эти формы, подобно константам, являются лисповскими объектами, представляющими лишь самих себя. Это такие формы, как числа и специальные конста­нты Т и NIL, а также знаки, строки и битовые векторы.
Символы, которые используются в качестве переменных.


Слайд 76
Текст слайда:

3. Формы в виде списочной структуры, которыми являются:
Вызовы функций и лямбда-вызовы.
Специальные формы, в число которых входят SETQ, QUOTE и многие описанные в этой главе формы, предназначенные для управления вычислением и контекстом.
Макровызовы
У каждой формы свой синтаксис и семантика, основанные на едином способе записи и интерпретации.


Слайд 77
Текст слайда:

Управляющие структуры Лиспа являются формами

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


Слайд 78
Текст слайда:

Наиболее важные с точки зрения программирования синтаксические формы можно на основе их использования разделить на следующие группы:
Работа с контекстом:
QUOTE или блокировка вычисления;
вызов функции и лямбда-вызов;
предложения LET и LET*.
Последовательное исполнение:
предложения PROG1, PROG2 и PROGN.


Слайд 79
Текст слайда:

Разветвление вычислений:
условные предложения COND, IF, WHEN, UNLESS;
выбирающее предложение CASE.
Итерации:
циклические предложения DO, DO*, LOOP, DOTIMES, DOUNTIL
Передачи управления:
предложения PROG, GO и RETURN.
Динамическое управление вычислением:
THROW и CATCH, а также BLOCK.


Слайд 80
Текст слайда:

LET создает локальную связь

Вычисление вызова функции создает на время вычисления новые связи для формальных параметров функции. Новые связи внутри формы можно создать и с помощью предложения LET. Эта структура выглядит так:

(LET ((ml знач1) (т2 знач2) ...) форма1 форма2...)


Слайд 81
Текст слайда:

Предложение LET вычисляется так, что сначала статические переменные
m1, m2, ... из первого "аргумента" формы связываются с соответствующими значениями знач1, знач2, … Затем слева направо вычисляются значения форм форма1, форма2,… В качестве значения всей формы возвращается значение последней формы. Как и у функций, после окончания вычисления связи статических переменных m1, m2, ... ликвидируются и любые изменения их значений (SETQ) не будут видны извне.


Слайд 82
Текст слайда:

Например:
_(setq х 2)
2
_(let ((x 0)) (setq x 1))
1

2


Слайд 83
Текст слайда:

Форма LET является на самом деле синтаксическим видоизменением лямбда-вызова, в которой формальные и фактические параметры помещены совместно в начале формы:
(LET ((ml at) (m2 a2) ... (mn an)) форма1 форма2 ...)
((LAMBDA
(ml m2 ... mn) ; формальные параметры форма1 форма2 ...) ; тело функции
a1 а2 ... an) ; фактические параметры


Слайд 84
Текст слайда:

Значения переменным формы LET присваиваются одновременно. Это означает, что значения всех переменных mi вычисляются до того, как осуществляется связывание с формальными параметрами. Новые связи этих переменных еще не действуют в момент вычисления начальных значений переменных, которые перечислены в форме позднее. Например:
_(let ((х 2) (у (* 3 х)))
(list х у)) ; при вычислении Y
Error: Unbound atom X ; у X нет связи


Слайд 85
Текст слайда:

Побочный эффект можно наблюдать при работе с формой LET* подобной LET, но вычисляющей значения переменных последовательно:
_(let* ((x 2) (у (* 3 x)))
(list x у)) (2 6)


Слайд 86
Текст слайда:

Последовательные вычисления: PROG1, PROG2 и PROGN

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


Слайд 87
Текст слайда:

_(progn (setq x 2) (setq y (* 3 x)))
6
_x
2


Слайд 88
Текст слайда:

Разветвление вычислений: условное предложение COND

Предложение COND является основным средством разветвления вычислений. Это синтаксическая форма, позволяющая управлять вычислениями на основе определяемых предикатами условий. Структура услов­ного предложения такова:
(COND (p1 a1) (р2 а2) … (pN aN))


Слайд 89
Текст слайда:

Предикатами pi и результирующими выражениями ai могут быть произвольные формы. Значение предложения COND определяется следующим образом:
1. Выражения pi, выполняющие роль предикатов, вычисляются последовательно слева направо (сверху вниз) до тех пор, пока не встретится выражение, значением которого не является NIL, т.е. логическим значением которого является истина.
Вычисляется результирующее выражение, соответствующее этому предикату, и полученное значение возвращается в качестве значения всего предложения COND.
Если истинного предиката нет, то значением COND будет NIL.


Слайд 90
Текст слайда:

Рекомендуется в качестве последнего предиката использовать символ Т, и соответствующее ему результирующее выражение будет вычисляться всегда в тех случаях, когда ни одно другое условие не выполняется. В следующем примере с помощью предложения COND определена функция, устанавливающая тип выражения:
_(defun тип(l) (cond ((null l) ‘пусто) ((atom l) ‘атом) (t ‘список)))
ТИП


Слайд 91
Текст слайда:

_(тип ‘(a b c))
СПИСОК
_(тип (atom ‘(a t o m)))
ПУСТО
В условном предложении может отсутствовать результирующее выражение ai или на его месте часто может быть последовательность форм:
(COND (p1 a1)
…..
(pi) ; результирующее
…. ; выражение отсутствует
(pk akl ak2... akN) ; последовательность форм
...) ; в качестве результата


Слайд 92
Текст слайда:

Если условию не ставится в соответствие результирующее выражение, то в качестве результата предложения COND при истинности предиката выдается само значение предиката. Если же условию соответствует несколько форм, то при его истинности формы вычисляются последовательно слева направо и результатом предложения COND будет значение последней формы последовательности (неявный PROGN).


Слайд 93
Текст слайда:

_(defun и (х у) (cond (x у) (t nil)))
И
_(и t nil)
NIL
_(defun или (х у) (cond (x t) (t y)))
ИЛИ
_(или t nil)
T
_(defun не (х) (not x))
HE
_(не t)
NIL
_(defun => (x y) (cond (x y) (t t)))
=>
_(=> nil t)
T


Слайд 94
Текст слайда:

_(defun => (x y) (или x (не y)))
=>
_(defun ⬄ (x y) (и (=> x y) (=> y x)))



Слайд 95
Текст слайда:

Предикаты "и" и "или" входят в состав встроенных функций Лиспа и называются AND и OR. Число их аргументов может быть произвольным.
_(and (atom nil) (null nil) (eq nil nil))
T
Предикат AND в случае истинности возвращает в качестве значения значение своего последнего аргумента. Его иногда используют как упрощение условного предложения по следующему образцу:
(AND условие1 условие2 ... условиеN)

(COND ((AND условие1 условие2 ...условиеN)
(Т NIL))


Слайд 96
Текст слайда:

Предложения COND можно комбинировать таким же образом, как и вызовы функций. Например, предикат "исключающее или" (exclusive or или хоr), который ложен, когда оба аргумента одновременно либо истинны, либо нет, можно определить следующим образом:
_(defun xor(x y)
(cond (x (cond (y nil)
(t t)))
(t y)))
XOR


Слайд 97
Текст слайда:

Другие условные предложения: IF, WHEN, UNLESS и CASE

(IF условие то-форма иначе-форма)

(COND (условие то-форма)
(Т иначе-форма))

(if (atom t) 'атом 'список)
АТОМ


Слайд 98
Текст слайда:

(WHEN условие форма1 форма2 ...)

(UNLESS (NOT условие) форма1 форма2 ...)

(COND (условие форма1 форма2 ...))

(IF условие (PROGN форма1 форма2 ...) NIL)


Слайд 99
Текст слайда:

(CASE ключ
(список-ключей1 m11 m12 ...)
(список-ключей2 m21 m22 ...))
Сначала в форме CASE вычисляется значение ключевой формы ключ. Затем его сравнивают с элементами списков ключей список-ключей, с которого начинаются альтернативы. Когда в списке найдено значение ключевой формы, начинают вычисляться соответствующие формы mil, mi2, ..., значение последней из которых и возвращается в качестве значения всего предложения CASE (неявный PROGN).


Слайд 100
Текст слайда:

Повторение через итерацию или рекурсию

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


Слайд 101

Слайд 102
Текст слайда:

ЗАДАЧИ

Реализовать на языке Lisp и Haskell:
Функции генерации числовых последовательности из прошлой лекции
Известные вам алгоритмы сортировки (в том числе, прямой выбор и qsort)
Генерирование всех вариантов перестановок символов входной строки


Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика