1 Символьные вычисления и функциональное программирование Вывод знаний 3. - презентация

1 1 Символьные вычисления и функциональное программирование Вывод знаний 3

2 © Муромцев Д.И. Лекция 9 2 Язык LISP (List Processing) Создан в конце 1950-х. Основные уникальные особенности LISP: Основной структурой данных является список символов, Программы на этом языке также имеют списочную структуру, Базовыми операциями являются операции над списками. Вычисление, управляемое данными.

3 © Муромцев Д.И. Лекция 9 3 Физическая символическая система (1) В основе символьных вычислений лежит понятие символа. Можно определить символ как «нечто, заменяющее другое нечто», «Другое нечто» в данном случае является значением (designation) символа – то на что ссылается и что представляет символ. Мы можем понимать под символами, с которыми выполняются какие-либо действия, все, что угодно. Программа, обрабатывающая эти символы, создает структуры символов. Операции изменяют семантику символов, имитируя тем самым деятельность человека. Символьные вычисления подразумевают единообразное представление как данных, так и правил манипуляции с символами в виде некого физического устройства. Впервые эта идея была сформулирована Ньюэллом и Саймоном в гипотезе о физической символической системе (The Physical Symbol System Hypothesis)

4 © Муромцев Д.И. Лекция 9 4 Физическая символическая система (2) Физическая символическая система «состоит из множества сущностей (entities), называемых символами (symbols), являющихся физическими шаблонами (physical patterns), которые могут быть компонентами сущностей другого типа, называемых выражениями (expression) или символическими структурами (symbol structure)». Важнейшими понятиями, связанными с символическими структурами являются обозначение (designation) и интерпретация (interpretation). Выражение может ссылаться (refer) на какой-либо другой объект, в том числи и на другую символическую структуру

5 © Муромцев Д.И. Лекция 9 5 Структура символической системы Память, содержащая символические структуры, число и содержание которых может меняться во времени; Набор операторов для манипулирования символическими структурами, например, чтение, запись, копирование; Средства управления, предназначенного для непрерывной интерпретации текущей активной символической структуры, к которой выполняется обращение; Средства ввода/вывода для взаимодействия с окружающей средой, посредством рецепторов и эффекторов.

6 © Муромцев Д.И. Лекция 9 6 Символические вычисления в LISP Синтаксическими элементами языка LISP являются символьные выражения (symbolic expression), которые называются s-выражениями. В виде s-выражений представляются и данные, и программы. S-выражение может быть либо атомом (atom), либо списком (list). Ниже приведены несколько примеров атомов: 3,1415 x 100 good *слово_на_русском_языке* nil

7 © Муромцев Д.И. Лекция 9 7 Списки в LISP Списки в LISP формируются из атомов или других (вложенных) списков, разделенных пробелами и ограниченных круглыми скобками. Пустой – nil – список можно обозначить (). Благодаря этим скобкам LISP получил неформальное название «язык скобок». Ниже следуют несколько примеров списков: ( ) (tom mary john joyce) (a (b c) (d (e f))) (on block-1 table) (likes bill X) (and (likes george kate) (likes bill merry))

8 © Муромцев Д.И. Лекция 9 8 Вычисления в LISP Запись выражений: (* 7 9) (- (+ 3 4) 7) Оценивание выражений: (eval (+ 2 3)) (quote (+ 2 3)) Определение функций: (defun sqr (x) (* x x)) (funcall #(lambda (x) (* x x)) 4) (defun sqr (x) (lambda (x) (* x x)))

9 © Муромцев Д.И. Лекция 9 9 Условные операторы (cond ( ) ( ) … ( ) )

10 © Муромцев Д.И. Лекция 9 10 Обработка s-выражений Основными способами доступа к элементам списка являются функции car – возвращающая голову или первый элемент списка и cdr – возвращающая хвост или тот же список после удаления из него первого элемента. Обе функции принимают в качестве аргумента список. Используя функций car и cdr можно реализовать так называемую рекурсию по дереву или car-cdr рекурсию. Отличие этой рекурсии от обычного рекурсивного вызова заключается в том, что при сканировании списка, если текущий элемент является не атомарным (вложенный список), то выполняется также перебор элементов вложенного списка.

11 © Муромцев Д.И. Лекция 9 11 Функциональное программирование в Python Базовыми функциональными элементами являются map(), reduce(), filter() и оператор lambda. Этих функций и нескольких базовых операторов достаточно для написания любой программы на Python; в частности, все управляющие утверждения ('if', 'elif', 'else', 'assert', 'try', 'except', 'finally', 'for', 'break', 'continue', 'while', 'def') можно представить в функциональном стиле, используя исключительно функции и операторы.

12 © Муромцев Д.И. Лекция 9 12 Пример if/elif/else Ообычные условные операторы if/elif/else могут быть представлены в виде «замкнутых накоротко» ("short circuits") логических выражений, вычисление которых заканчивается сразу, как только становится известен их логический результат: # Традиционное выражение для условного оператора if : func1() elif : func2() else: func3() # Эквивалентное "накоротко замкнутое" выражение ( and func1()) or ( and func2()) or (func3()) # Пример "накоротко замкнутого" выражения >>> x = 3 >>> def pr(s): return s >>> (x==1 and pr('one')) or (x==2 and pr('two')) or (pr('other')) 'other >>> x = 2 >>> (x==1 and pr('one')) or (x==2 and pr('two')) or (pr('other')) 'two' >> x = 3 >>> def pr(s): return s >>> (x==1 and pr('one')) or (x==2 and pr('two')) or (pr('other')) 'other >>> x = 2 >>> (x==1 and pr('one')) or (x==2 and pr('two')) or (pr('other')) 'two'">

13 © Муромцев Д.И. Лекция 9 13 Пример lambda Условных вызовы с помощью выражений дают максимальную выгоду при совместно использовании с другими функциональным конструкциями, например оператором lambda, который может содержать только выражения. Выражение lambda позволяет в общей форме представить условные возвращаемые значения. Изменим определение функции pr(s) из предыдущего примера и добавим namenum() используя выражение lambda: >>> pr = lambda s:s >>> namenum = lambda x: (x==1 and pr("one")) \... or (x==2 and pr("two")) \... or (pr("other")) >>> namenum(1) 'one' >>> namenum(2) 'two' >>> namenum(3) 'other' >> namenum(1) 'one' >>> namenum(2) 'two' >>> namenum(3) 'other'">

14 © Муромцев Д.И. Лекция 9 14 Пример reduce Функция reduce() применяет переданную функцию к каждому значению в списке и к внутреннему накопителю результата. Например, вычисление факториала числа 10 с помощью утверждения for выглядит так: def factorial10(): factor = 1 for i in range(2, 10): factor = factor * i return factor на основании функции reduce значительно короче: reduce(lambda n,m:n*m, range(1,10))

15 © Муромцев Д.И. Лекция 9 15 Пример map Функция map() применяет переданную функцию к каждому элементу в переданном списке (списках) и возвращает список результатов. for e in lst: func(e) # цикл, основанный на утверждении 'for' map(func, lst) # тот же цикл, основанный на вызове функции map() Этот же подход можно применить для введения в функциона- льные вызовы элементов императивного программирования, то есть состоящего из последовательности утверждений, требу- ющих «сделать это, затем сделать то, затем - что-то еще»: # создаем вспомогательную функцию для выполнения действий do_it = lambda f: f() # пусть f1, f2, f3 (etc) выполняют требуемые действия # тогда последовательное выполнение будет таким map(do_it, [f1,f2,f3])

16 © Муромцев Д.И. Лекция 9 16 Сравнение характеристик языков LISP и Python Ключевые возможностиLISPPython Все является объектамиДа Переменные не типизированыДа Поддержка гетерогенных списков Да (linked list и array)Да (array) Мультипарадигмное программирование Да: функциональное, императивное, ООП, обощенное Да: функциональное, императивное, ООП Управление памятьюАвтоматическая сборка мусора МодулиСложны в использованииПросты в использовании Интроспекция объектов и классов Строгая Макросы метапрограммированияРазвитые макросыНет Интерактивный ввод и вычисления Да: > (string-append "hello" " " "world") "hello world" Да: >>> ' '.join(['hello', 'world']) 'hello world' Кросс-платформеная реализацияДа: Windows, Mac, Unix, Linux Да: Windows, Mac, Unix, Linux Количество реализацийМногоОдна ЛицензированиеЛицензированный и open source Open source GUI, Web и др. библиотекиНет в стандартеЕсть стандартные GUI, Web и др. библиотеки >> ' '.join(['hello', 'world']) 'hello world' Кросс-платформеная реализацияДа: Windows, Mac, Unix, Linux Да: Windows, Mac, Unix, Linux Количество реализацийМногоОдна ЛицензированиеЛицензированный и open source Open source GUI, Web и др. библиотекиНет в стандартеЕсть стандартные GUI, Web и др. библиотеки">