Функциональное программирование МарГТУ2009 г. 1 Функции. Базовые функции. Лекция 2

2 МарГТУ2009 г. Понятие функции Диалог с интерпретатором ЛИСПА. Блокировка QUOTE Функция EVAL Использование символов в качестве переменных Базовые функции Арифметические функции.

3 МарГТУ2009 г. Понятие функции

4 МарГТУ2009 г. Понятие функции В математике функция отображает одно множество в другое. Для х из множества определения X ставится в соответствие Y из множества значений функции F. y = F (x) F (x) y F: x y Виды отображения Функция (X и Y – числовые множества) Вектор-функция (X и Y – многомерны) Функционал (X – произвольной природы и Y – поле)

5 МарГТУ2009 г. Аргументы функции У функции может быть любое количество аргументов, в том числе их может не быть совсем. Функция без аргументов имеет постоянное значение. abs(-3) 3 абсолютная величина. +(2, 3) 5 сложение union((a, b),(c,b)) (a,b,c) объединение множеств количество_букв (слово) 5

6 МарГТУ2009 г. Типы аргументов и функций Функция в общем случае задает отображение из нескольких множеств в множество значений. F (x,y) z F: AxB С

7 МарГТУ2009 г. Основные понятия: программа, функции и выражения переменная (атом). X Y n Variable1 LongSong вызов функции (функция аргумент1 аргумент2... ) имена функций (атомы) композиции функций (функция1 (функция2 аргумент21 аргумент22... ) аргумент2... )

8 МарГТУ2009 г. Префиксная нотация Математика f(x) g(x,y) h(x,g(y,z)) x+y x–y x*(x+z) ЛИСП (f x) (g x y) (h x (g y z)) (+ x y) (- x y) (* x (+ x z)) Достоинства: упрощается синтаксический анализ выражений; данные (списки) и программа (списки) представляются единым образом.

9 МарГТУ2009 г. Диалог с интерпретатором ЛИСПА

10 МарГТУ2009 г. Диалог с интерпретатором ЛИСПА Read-eval-print цикл loop (read evaluate print) В Лиспе сразу читается(read), затем вычисляется (evaluate) значение функции и выдается (print) значение. * (+ 2 3) 5

11 МарГТУ2009 г. Иерархия вызовов В функцию могут входить функциональные подвыражения: * (* (+ 1 2)(- 11 4)) 21 *

12 МарГТУ2009 г. Блокировка QUOTE

13 МарГТУ2009 г. Блокировка QUOTE * (QUOTE a) константа атом A a * (QUOTE (A B C) ) константа список (A B C) (A B C) * (ATOM (QUOTE A)) аргумент предиката - атом A T * (ATOM (QUOTE (A B C))) аргумент предиката – список Nil * (ATOM A) значение не определено

14 МарГТУ2009 г. ' (QUOTE) * '(+ 2 3 ) (+ 2 3 ) * ( quote ' y ) ( QUOTE Y ) * '' y ( QUOTE Y ) Апостроф автоматически преобразуется в QUOTE. * ' * ( + ' 2 3 ) 5 * t T * ' t T Перед константами не надо ставить апостроф

15 МарГТУ2009 г. Функция EVAL

16 МарГТУ2009 г. Функция EVAL EVAL – дополнительный вызов интерпретатора Лиспа. Вызов может производиться внутри вычисляемого S-выражения. EVAL снимает блокировку QUOTE. * ( quote ( ) ) ( ) * ( eval ( quote ( ) ) ) 3 QUOTE и EVAL действуют во взаимно противоположных направлениях и аннулируют эффект друг друга.

17 МарГТУ2009 г. Использование символов в качестве переменных

18 МарГТУ2009 г. Использование символов в качестве переменных Константы имеют значения. * Изначально символы не имеют значения. Значения символов хранятся в ячейках (символ связан (bind) сo значением)

19 МарГТУ2009 г. Присвоение значения в Лиспе. Отличие: Не оговаривается, что может хранится в ячейке: целое, атом, список, массив и т.д. В ячейке может хранится что угодно. С символом может быть связана не только ячейка со значением, а многие другие ячейки, число которых не ограничено. (* ( ) ( ))

20 МарГТУ2009 г. Функция SET Функция SET cвязывает символ со значением, предварительно вычисляя значения аргументов. В качестве значения функция SET возвращает значение второго аргумента. * ( set 'd ' ( x y z ) ) ( x y z ) * ( set ' a ' b ) b * ( set d ' b ) ошибка (не определена переменная d) * ( set (car (x y z)) ' b ) b

21 МарГТУ2009 г. Функция SETQ Аналогична SET, но не вычисляет значение первого аргумента. Буква Q указывает на блокировку. * ( setq m ' k ) k * m k

22 МарГТУ2009 г. Обобщенная функция SETF Действует аналогично SETQ, но может использоваться для присвоения символу не только значения. (setf L '((b (b b(a))))) * (setq a (1 2 3)) (1 2 3) * (setf (second a) '4) 4 * a (1 4 3) (setq х у) (setf x у) (set х у) (setf (symbol-value x) у)

23 МарГТУ2009 г. Базовые функции

24 МарГТУ2009 г. Базовые функции CAR доступ к первому элементу CDR доступ к укороченному на один элемент списку CONS строит списки ATOM различает составные и атомарные объекты EQ проверка атомарных объектов на равенство

25 МарГТУ2009 г. Функция CAR Форма записи: CAR Первый элемент списка – голова. Список без головы – хвост. * ( car nil ) nil * ( car 'nil ) nil * ( car '(( head ) tail )) ( head ) * ( car (a b c)) ошибка – имя несуществующей функции.

26 МарГТУ2009 г. Функция CDR Форма записи: CDR * (cdr '( a ) ) nil * ( cdr nil ) nil Для атомов применение CDR выдает ошибку, т.к. аргумент – не список. * ( cdr 'kat ) ошибка * ( cdr '( ( a b) ( c d ) ) ) ( ( c d ) )

27 МарГТУ2009 г. Вычисление структур Исполнение идет "изнутри наружу". ( сar ( cdr '( ( a b ) c d ) ) ) В Лиспе сначала выполняются внутренние функции, а затем внешние.

28 МарГТУ2009 г. Функция CONS Форма записи: CONS Первый аргумент становится головой второго аргумента, который обязательно является списком. * ( cons 'a '( b c ) ) ( a b c ) * ( cons '( a b ) '( c d ) ) ( ( a b) c d ) * ( cons 'a nil ) ( a )

29 МарГТУ2009 г. Связь между CAR, CDR и CONS Назначение функций Разбор (селекторы) Создание (конструктор ) carcdrcons s-выражение Запись и результат функций CAR список список CDR список Cons s-выражение список список

30 МарГТУ2009 г. Точечная нотация Единая базовая структура для конструирования S- выражений (dot-nоtation) – левая и правая части бинарного узла равноправны и могут хранить данные любой природы. (a. b) (c.(a. b)) ((a. b).c) CONS строит бинарный узел и заполняет его парой объектов. Первый аргумент размещается в левой части бинарного узла, а второй – в правой. Функция CAR обеспечивает доступ к объектам, расположенным слева от точки, а функция CDR – справа. (A) идентичен (A. Nil) (A1 A2... Ak) идентичен (A1. (A2. (.... (Ak. Nil)... )))

31 МарГТУ2009 г. Комбинации функций CAR и CDR Мнемоничные обозначения композиций из многократных CAR-CDR * (cdr (cdr (car '((a b c) d)))) (a b c) (b c) (c) * (cddar '((a b c) d)) (c)

32 МарГТУ2009 г. N – элемент Функция NTH извлекает n-й элемент из списка Форма записи: NTH * (NTH 7 '( )) 7

33 МарГТУ2009 г. Функция LIST Форма записи: (list s-выражение1 s-выражение2…) * ( list 1 2 ) ( 1 2 ) * ( list ' a ' b ( ) ) ( a b 3 ) * ( list ' a ' ( b c ) ' d ) ( a ( b c ) d ) * ( list nil ) ( nil ) * (cons 1 (cons 2 NIL) (1 2)

34 МарГТУ2009 г. Функция LENGTH Форма записи: LENGTH * (length '(1 (2 3) 4)) 3

35 МарГТУ2009 г. Арифметические функции

36 МарГТУ2009 г. Арифметические функции Арифметические функции могут быть использованы с целыми или действительными аргументами. Число аргументов для большинства арифметических функций может быть разным. (+ x1 x2... xn) возвращает x1 + x2 + x xn. (- x1 x2... xn) возвращает x1 - x2 - x xn. (* y1 y2... yn) возвращает y1 * y2 * y3 *... * yn. (/ x1 x2... xn) возвращает x1/x2/... /xn. Специальные функции (1+ x) и (1- x)

37 МарГТУ2009 г. Спасибо за внимание! Вопросы?