Без темы
<<  Высокопроизводительные вычисления в геостатистике Вычисление объема многогранников  >>
Вычисление в лиспе
Вычисление в лиспе
Программа состоит из форм и функций Управляющие структуры Лиспа
Программа состоит из форм и функций Управляющие структуры Лиспа
Программа состоит из форм и функций
Программа состоит из форм и функций
Вычислимые выражения можно разделить на три группы: Самоопределенные
Вычислимые выражения можно разделить на три группы: Самоопределенные
3. Формы в виде списочной структуры, которыми являются: Вызовы функций
3. Формы в виде списочной структуры, которыми являются: Вызовы функций
Управляющие структуры Лиспа являются формами
Управляющие структуры Лиспа являются формами
Наиболее важные с точки зрения программирования синтаксические формы
Наиболее важные с точки зрения программирования синтаксические формы
Разветвление вычислений: условные предложения COND, IF, WHEN, UNLESS;
Разветвление вычислений: условные предложения COND, IF, WHEN, UNLESS;
LET создает локальную связь
LET создает локальную связь
Предложение LET вычисляется так, что сначала статические переменные m1
Предложение LET вычисляется так, что сначала статические переменные m1
Например: _(setq х 2) 2 _(let ((x 0)) (setq x 1)) 1 _х 2
Например: _(setq х 2) 2 _(let ((x 0)) (setq x 1)) 1 _х 2
Форма LET является на самом деле синтаксическим видоизменением
Форма LET является на самом деле синтаксическим видоизменением
Значения переменным формы LET присваиваются одновременно
Значения переменным формы LET присваиваются одновременно
Побочный эффект можно наблюдать при работе с формой LET* подобной LET,
Побочный эффект можно наблюдать при работе с формой LET* подобной LET,
Последовательные вычисления: PROG1, PROG2 и PROGN
Последовательные вычисления: PROG1, PROG2 и PROGN
_(progn (setq x 2) (setq y (* 3 x))) 6 _x 2
_(progn (setq x 2) (setq y (* 3 x))) 6 _x 2
Разветвление вычислений: условное предложение COND
Разветвление вычислений: условное предложение COND
Предикатами pi и результирующими выражениями ai могут быть
Предикатами pi и результирующими выражениями ai могут быть
Рекомендуется в качестве последнего предиката использовать символ Т, и
Рекомендуется в качестве последнего предиката использовать символ Т, и
_(тип ‘(a b c)) СПИСОК _(тип (atom ‘(a t o m))) ПУСТО В условном
_(тип ‘(a b c)) СПИСОК _(тип (atom ‘(a t o m))) ПУСТО В условном
Если условию не ставится в соответствие результирующее выражение, то в
Если условию не ставится в соответствие результирующее выражение, то в
_(defun и (х у) (cond (x у) (t nil))) И _(и t nil) NIL _(defun или (х
_(defun и (х у) (cond (x у) (t nil))) И _(и t nil) NIL _(defun или (х
_(Defun => (x y) (или x (не y))) => _(defun
_(Defun => (x y) (или x (не y))) => _(defun
Предикаты "и" и "или" входят в состав встроенных функций Лиспа и
Предикаты "и" и "или" входят в состав встроенных функций Лиспа и
Предложения COND можно комбинировать таким же образом, как и вызовы
Предложения COND можно комбинировать таким же образом, как и вызовы
Другие условные предложения: IF, WHEN, UNLESS и CASE
Другие условные предложения: IF, WHEN, UNLESS и CASE
(WHEN условие форма1 форма2
(WHEN условие форма1 форма2
(CASE ключ (список-ключей1 m11 m12
(CASE ключ (список-ключей1 m11 m12
Повторение через итерацию или рекурсию
Повторение через итерацию или рекурсию
Вычисление в лиспе
Вычисление в лиспе
Упражнения 1. Запишите следующие лямбда-вызовы с использованием формы
Упражнения 1. Запишите следующие лямбда-вызовы с использованием формы
3. Предикат сравнения (> х у) истинен, если х больше, чем у. Опишите с
3. Предикат сравнения (> х у) истинен, если х больше, чем у. Опишите с
5. Определите функцию (ПРОИЗВЕДЕНИЕ n m), вычисляющую произведение
5. Определите функцию (ПРОИЗВЕДЕНИЕ n m), вычисляющую произведение
6. В математике числа Фибоначчи образуют ряд 0, 1, 1, 2, 3, 5, 8,
6. В математике числа Фибоначчи образуют ряд 0, 1, 1, 2, 3, 5, 8,
7. Определите функцию ДОБАВЬ, прибавляющую к элементам списка данное
7. Определите функцию ДОБАВЬ, прибавляющую к элементам списка данное

Презентация на тему: «Вычисление в лиспе». Автор: Irene V. Grigorieva. Файл: «Вычисление в лиспе.ppt». Размер zip-архива: 146 КБ.

Вычисление в лиспе

содержание презентации «Вычисление в лиспе.ppt»
СлайдТекст
1 Вычисление в лиспе

Вычисление в лиспе

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

2 Программа состоит из форм и функций Управляющие структуры Лиспа

Программа состоит из форм и функций Управляющие структуры Лиспа

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

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

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

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

4 Вычислимые выражения можно разделить на три группы: Самоопределенные

Вычислимые выражения можно разделить на три группы: Самоопределенные

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

5 3. Формы в виде списочной структуры, которыми являются: Вызовы функций

3. Формы в виде списочной структуры, которыми являются: Вызовы функций

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

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

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

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

7 Наиболее важные с точки зрения программирования синтаксические формы

Наиболее важные с точки зрения программирования синтаксические формы

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

8 Разветвление вычислений: условные предложения COND, IF, WHEN, UNLESS;

Разветвление вычислений: условные предложения COND, IF, WHEN, UNLESS;

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

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

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

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

10 Предложение LET вычисляется так, что сначала статические переменные m1

Предложение LET вычисляется так, что сначала статические переменные m1

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

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

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

12 Форма LET является на самом деле синтаксическим видоизменением

Форма LET является на самом деле синтаксическим видоизменением

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

13 Значения переменным формы LET присваиваются одновременно

Значения переменным формы LET присваиваются одновременно

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

14 Побочный эффект можно наблюдать при работе с формой LET* подобной LET,

Побочный эффект можно наблюдать при работе с формой LET* подобной LET,

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

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

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

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

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

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

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

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

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

18 Предикатами pi и результирующими выражениями ai могут быть

Предикатами pi и результирующими выражениями ai могут быть

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

19 Рекомендуется в качестве последнего предиката использовать символ Т, и

Рекомендуется в качестве последнего предиката использовать символ Т, и

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

20 _(тип ‘(a b c)) СПИСОК _(тип (atom ‘(a t o m))) ПУСТО В условном

_(тип ‘(a b c)) СПИСОК _(тип (atom ‘(a t o m))) ПУСТО В условном

предложении может отсутствовать результирующее выражение ai или на его месте часто может быть последовательность форм: (COND (p1 a1) ….. (pi) ; результирующее …. ; выражение отсутствует (pk akl ak2... akN) ; последовательность форм ...) ; в качестве результата

21 Если условию не ставится в соответствие результирующее выражение, то в

Если условию не ставится в соответствие результирующее выражение, то в

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

22 _(defun и (х у) (cond (x у) (t nil))) И _(и t nil) NIL _(defun или (х

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

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

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

(x y) (и (=> x y) (=> y x))) ?

24 Предикаты "и" и "или" входят в состав встроенных функций Лиспа и

Предикаты "и" и "или" входят в состав встроенных функций Лиспа и

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

25 Предложения COND можно комбинировать таким же образом, как и вызовы

Предложения COND можно комбинировать таким же образом, как и вызовы

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

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

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

(IF условие то-форма иначе-форма) ? (COND (условие то-форма) (Т иначе-форма)) (if (atom t) 'атом 'список) АТОМ

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

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

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

28 (CASE ключ (список-ключей1 m11 m12

(CASE ключ (список-ключей1 m11 m12

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

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

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

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

30 Вычисление в лиспе
31 Упражнения 1. Запишите следующие лямбда-вызовы с использованием формы

Упражнения 1. Запишите следующие лямбда-вызовы с использованием формы

LET и вычислите их значения на машине: ((lambda (x у) (list x у)) '(+ 2 3) 'с) ((lambda (x у) ((lambda (z) (list x у z)) 'с) ((lambda (x у) (list x у)) ((lambda (z) z) 'a) 'b) 2. С помощью предложений COND или CASE определите функцию, которая возвращает в качестве значения столицу заданного аргументом государства: (столица 'Финляндия) ХЕЛЬСИНКИ

32 3. Предикат сравнения (> х у) истинен, если х больше, чем у. Опишите с

3. Предикат сравнения (> х у) истинен, если х больше, чем у. Опишите с

помощью предиката > и условного предложения функцию, которая возвращает из трех числовых аргументов значение среднего по величине числа: _(среднее 4 7 6) 6 4. Можно ли с помощью предложения COND запрограммировать предложение IF как функцию?

33 5. Определите функцию (ПРОИЗВЕДЕНИЕ n m), вычисляющую произведение

5. Определите функцию (ПРОИЗВЕДЕНИЕ n m), вычисляющую произведение

двух целых положительных чисел. 6. Функция (LENGTH x) является встроенной функцией, которая возвращает в качестве значения длину списка (количество элементов на верхнем уровне). Определите функцию LENGTH рекурсивно с помощью предложения COND.

34 6. В математике числа Фибоначчи образуют ряд 0, 1, 1, 2, 3, 5, 8,

6. В математике числа Фибоначчи образуют ряд 0, 1, 1, 2, 3, 5, 8,

... Эту последовательность можно определить с помощью следующей функции FIB: fib(n) = 0 , если n=0 fib(n) = 1 , если n=1 fib(n) = fib(n-l)*fib(n-2) , если n>1 Определите лисповскую функцию fib(n), вычисляющую n-й элемент ряда Фибоначчи.

35 7. Определите функцию ДОБАВЬ, прибавляющую к элементам списка данное

7. Определите функцию ДОБАВЬ, прибавляющую к элементам списка данное

число: _(добавь '(2 7 3) 3) (5 10 6)

«Вычисление в лиспе»
http://900igr.net/prezentacija/matematika/vychislenie-v-lispe-266942.html
cсылка на страницу

Без темы

359 презентаций
Урок

Математика

71 тема
Слайды