LISP Шестаков А.П.. LISP2 Лисп (LISP, от англ. LISt Processing language «язык обработки списков»; современное написание: Lisp) семейство языков программирования, - презентация

1 LISP Шестаков А.П.

2 LISP2 Лисп (LISP, от англ. LISt Processing language «язык обработки списков»; современное написание: Lisp) семейство языков программирования, программы и данные в которых представляются системами линейных списков символов. Лисп является вторым в истории (после Фортрана) используемым в настоящее время высокоуровневым языком программирования. Создатель Лиспа Джон Маккарти (1960) занимался исследованиями в области искусственного интеллекта

3 LISP3 Традиционный Лисп имеет динамическую систему типов. Язык является функциональным, но многие поздние версии обладают также чертами императивности, к тому же, имея полноценные средства символьной обработки, становится возможным реализовать объектно-ориентированность. Функциональное программирование раздел дискретной математики и парадигма программирования, в которой процесс вычисления трактуется как вычисление значений функций в математическом понимании (в отличие от функций как подпрограмм в процедурном программировании) Функциональное программирование раздел дискретной математики и парадигма программирования, в которой процесс вычисления трактуется как вычисление значений функций в математическом понимании (в отличие от функций как подпрограмм в процедурном программировании)

4 LISP4 Функциональное программирование предполагает обходиться вычислением результатов функций от исходных данных и результатов других функций, и не предполагает явного хранения состояния программы. Соответственно, не предполагает оно и изменяемость этого состояния (в отличие от императивного, где одной из базовых концепций является переменная, хранящая своё значение и позволяющая менять его по мере выполнения алгоритма).

5 LISP5 Достоинства Повышение надёжности кода Повышение надёжности кода Привлекательная сторона вычислений без состояний повышение надёжности кода за счёт чёткой структуризации и отсутствия необходимости отслеживания побочных эффектов. Любая функция работает только с локальными данными и работает с ними всегда одинаково, независимо от того, где, как и при каких обстоятельствах она вызывается. Невозможность мутации данных при пользовании ими в разных местах программы исключает появление трудно обнаруживаемых ошибок (таких, например, как случайное присваивание неверного значения глобальной переменной в императивной программе).

6 LISP6 Удобство организации модульного тестирования Удобство организации модульного тестирования Поскольку функция в функциональном программировании не может порождать побочные эффекты, менять объекты нельзя как внутри области видимости, так и снаружи (в отличие от императивных программ, где одна функция может установить какую-нибудь внешнюю переменную, считываемую второй функцией). Единственным эффектом от вычисления функции является возвращаемый ей результат, и единственный фактор, оказывающий влияние на результат это значения аргументов. Таким образом имеется возможность протестировать каждую функцию в программе, просто вычислив её от различных наборов значений аргументов. При этом можно не беспокоиться ни о вызове функций в правильном порядке, ни о правильном формировании внешнего состояния. Если любая функция в программе проходит модульные тесты, то можно быть уверенным в качестве всей программы. В императивных программах проверка возвращаемого значения функции недостаточна: функция может модифицировать внешнее состояние, которое тоже нужно проверять, чего не нужно делать в функциональных программах

7 LISP7 Возможности оптимизации при компиляции Возможности оптимизации при компиляции Традиционно упоминаемой положительной особенностью функционального программирования является то, что оно позволяет описывать программу в так называемом «декларативном» виде, когда жесткая последовательность выполнения многих операций, необходимых для вычисления результата, в явном виде не задаётся, а формируется автоматически в процессе вычисления функций. Это обстоятельство, а также отсутствие состояний даёт возможность применять к функциональным программам достаточно сложные методы автоматической оптимизации.

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

9 LISP9 Недостатки Отсутствие присваиваний и замена их на порождение новых данных приводят к необходимости постоянного выделения и автоматического освобождения памяти, поэтому в системе исполнения функциональной программы обязательным компонентом становится высокоэффективный сборщик мусора.

10 LISP10 Язык программирования Лисп предназначен в первую очередь для обработки символьной информации. Поэтому естественно, что в мире Лиспа числа играют далеко не главную роль. Основные типы данных в Лиспе называются атом и точечная пара. Элементарные данные языка Лисп называются атомами. Атомы могут иметь вид имен, чисел или других объектов, неделимых базовыми средствами языка. Атомы, выглядящие как имена, могут обладать свойствами, задаваемыми системой или программой. Значения переменных и определения функций – примеры свойств. Особый интерес представляют рекурсивные функции.

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

12 LISP12 Таким образом, п рограмма на LISP – это последовательность вычисляемых форм. Рекурсия – сведение к себе – позволяет такие правила записывать достаточно лаконично и ясно. Стек обеспечивает работу с рекурсивными функциями.

13 LISP13 Принципы функционального программирования 1.Унификация понятий «функция» и «значение». При символьном представлении информации нет принципиальной разницы в природе изображения значений и функций. Следовательно, нет и препятствий для обработки представлений функций теми же средствами, какими обрабатываются значения, т.е. представления функций можно строить из их частей и даже вычислять по мере поступления и обработки информации. Именно так конструируют программы - компиляторы. 2.Кроме функций-констант вполне допустимы функции-переменные.

14 LISP14 3. Самоприменимость. Первые реализации Лиспа были выполнены методом раскрутки, причем в составе системы сразу были предусмотрены и интерпретатор и компилятор. Оба эти инструмента были весьма точно описаны на самом Лиспе, причем основной объем описаний не превосходил пару страниц. 4. Интегральность ограничений на пространственно-временные характеристики. Если не хватает памяти, принципиально на всю задачу, а не на отдельные блоки данных, возможно мало существенных возможностей для ее решения. При недостатке памяти специальная программа "мусорщик" пытается найти свободную память. Новые реализации этого механизма рационально учитывают преимущества восходящих процессов на больших объемах памяти.

15 LISP15 5. Уточняемость решений. Реализация Лиспа обычно содержит списки свойств объектов, приспособленные к внешнему доопределению отдельных элементов поведения программируемой системы. 6. Динамическое управление вычислениями и конструированием программ В стандартных языках программирования принята императивная организация вычислений по принципу немедленного и обязательного выполнения каждой очередной команды. Это не всегда оправдано и эффективно. Существует много неимперативных моделей управления процессами, позволяющих прерывать и откладывать процессы, а потом их восстанавливать и запускать или отменять, что обеспечено в Лиспе средствами конструирования функций, блокировки вычислений и их явного выполнения.

16 LISP16 Одинаково выглядящие атомы не различимы по своим свойствам. Термин "атом" выбран по аналогии с химическими атомами, строение которых – предмет другой науки. Согласно этой аналогии атом может иметь достаточно сложное строение, но атом не предназначен для разбора на части базовыми средствами языка. Более сложные данные в Лиспе выстраиваются из одинаково устроенных бинарных узлов, содержащих пары объектов произвольного вида. Каждый бинарный узел соответствует минимальному блоку памяти, выделяемому системой программирования при организации и обработке структур данных. Выделение блока памяти и размещение в нем пары данных выполняет функция CONS (от слова consolidation), а извлечение левой и правой частей из блока выполняют функции CAR и CDR соответственно ("content of address part of register", "content of decrement part of register").

17 LISP17 ФункцияАргументыРезультат ConsАтомX ( Атом. X ) Car Атом Cdr X

18 LISP18 Списки Любой список может быть построен из пустого списка и атомов с помощью CONS и любая его часть может быть выделена с помощью подходящей композиции CAR-CDR. CONS - Функция, которая строит списки из бинарных узлов, заполняя их парами объектов, являющихся значениями пары ее аргументов. Первый аргумент произвольного вида размещается в левой части бинарного узла, а второй, являющийся списком, - в правой. CONS - Функция, которая строит списки из бинарных узлов, заполняя их парами объектов, являющихся значениями пары ее аргументов. Первый аргумент произвольного вида размещается в левой части бинарного узла, а второй, являющийся списком, - в правой. CAR – Функция, обеспечивающая доступ к первому элементу списка - его "голове". CAR – Функция, обеспечивающая доступ к первому элементу списка - его "голове". CDR – Функция, укорачивающая список на один элемент. Обеспечивает доступ к "хвосту" списка, т.е. к остатку списка после удаления его головы. CDR – Функция, укорачивающая список на один элемент. Обеспечивает доступ к "хвосту" списка, т.е. к остатку списка после удаления его головы. ATOM - Функция, различающая составные и атомарные объекты. На атомах ее значение "истина", а на более сложных структурах данных – "ложь". ATOM - Функция, различающая составные и атомарные объекты. На атомах ее значение "истина", а на более сложных структурах данных – "ложь". EQ – Функция, которая проверяет атомарные объекты на равенство. EQ – Функция, которая проверяет атомарные объекты на равенство.

19 LISP19 Различие истинностных значений в Лиспе принято отождествлять с разницей между пустым списком и остальными объектами, которым программист может придать в программе некоторый другой смысл. Таким образом, значение "ложь" – это всегда Nil. Если требуется явно изобразить значение "истина", то используется стандартная константа – атом T (true), но роль значения "истина" может выполнить любой, отличный от пустого списка, объект.

20 LISP20S-выражение S-выражение - это или атом или заключенная в скобки пара из двух S-выражений, разделенных точкой. Все сложные данные создаются из одинаково устроенных блоков - бинарных узлов, содержащих пары объектов произвольного вида. Каждый бинарный узел соответствует минимальному блоку памяти. Списки – это подмножество S-выражений, движение вправо по которым завершается атомом Nil. Любое S-выражение может быть построено из атомов с помощью CONS и любая его часть может быть выделена с помощью CAR-CDR.

21 LISP21 Пример. Факториал (DEFUN Факториал (N) (COND ((= N 0 ) 1 ) (COND ((= N 0 ) 1 ) (T ( * N (Факториал (- N 1 ))) ) ))