Функциональное программирование Язык Lisp. Введение.

Язык Лисп Лисп (LISP) был разработан в 1958 году американским ученым Джоном Маккарти (MIT) как функциональный язык, предназначенный для обработки списков ~ LISt Processing Лисп - один из наиболее распространенных базовых языков искусственного интеллекта. После его появления различными авторами был предложен ряд других алгоритмических языков.Это не помешало Лиспу остаться наиболее популярным языком для решения таких задач. Более того, предполагается, что Лисп наряду с Прологом будет одним из основных языков компьютеров пятого поколения. Наибольшую популярность Лисп получил в США. Долгое время язык использовался узким кругом исследователей. Широкое распространение язык получил в конце 70-х - начале 80-х годов с появлением необходимой мощности вычислительных машин и соответствующего круга задач. Сейчас Лисп - одно из главных инструментальных средств систем искусственного интеллекта (вытеснил в свое время язык Ада; система AutoCAD была разработана на Лиспе).

Особенности Лиспа Одинаковая форма представления данных и программ – в виде списка –Это позволяет программе обрабатывать другие программы и даже саму себя. Функциональный образ мышления Не требуется явное описание типов данных, используемых в программе Лисп как правило является интерпретирующим языком, также как BASIC и др. Это без типовой язык –это значит что символы не связываются по умолчанию с каким-либо типом. Использует макросы, что делает его эффективным языком для метапрограммирвоания Поддерживает итерационное, объектное, списковое, модульное, процедурное, рефлексивное программирование Лисп имеет необычный синтаксис. Из-за большего числа скобок LISP расшифровывают как «Lots of Idiotic Silly Parentheses». –Принято считать, что эквивалентные программы, написанные на Лиспе порой во много раз короче, чем написанные на процедурных языках. В основу языка положен серьезный математический аппарат: –лямбда-исчисление Черча –алгебра списочных структур –теория рекурсивных функций

Диалекты (версии) Лиспа Лисп имеет множество диалектов, однако многие специалисты склонны отдавать предпочтение диалекту Common Lisp в качестве будущего стандарта Common Lisp Scheme AutoLisp Xlisp 4

Атомы Атомы - это простейшие объекты Лиспа, из которых строятся остальные структуры. Символьные атомы - последовательность букв и цифр, при этом должен быть по крайней мере один символ отличающий его от числа. Примеры: ДЖОН АВ13 В54 10А Символьный атом или символ - это не идентификатор переменой в обычном языке программирования. Символ как правило обозначает некий предмет/объект/действие. –Он аналогичен переменной в традиционном языке программирования – это имя, состоящее из букв латиницы, цифр и некоторых специальных литер. Символ, как и переменная, может иметь какое-либо значение, то есть представлять какой-либо объект. Символьный атом рассматривается как неделимое целое. К символьным атомам применяется только одна операция: сравнение. В состав символа могут входить: + - * $ % ^ _ \ <> Числовые атомы - обыкновенные числа Е8 Числа это константы. Типы чисел зависят от реализации ЛИСПА

Списки В ЛИСПЕ список это последовательность элементов (list). Элементами являются или атомы или списки. Списки заключаются в скобки, элементы списка разделяются пробелами. –(банан) ;1 атом –(б а н а н) ; 5 атомов –(a b (c d) e) ; 4 элемента Список - это многоуровневая или иерархическая структура данных, в которой открывающиеся и закрывающиеся скобки находятся в строгом соответствии. –(+ 2 3) ; 3 атома –(((((первый) 2) второй) 4) 5) ; 2 элемента Список, в котором нет ни одного элемента, называется пустым списком и обозначается "()" или символом NIL (это и список и атом одновременно). Он играет такую же важную роль в работе со списками, что и ноль в арифметике. Пустой список может быть элементом других списков. –(NIL) ;список состоящий из атома NIL –(()) ;то же самое, что и (NIL) –((())) ;- " -((NIL)) –(NIL ()) ;список из двух других списков Голова списка – первый элемент списка, Хвост – все оставшиеся элементы (в свою очередь являющиеся самостоятельным списком)

Символьные выражения Все вышеперечисленные объекты (атомы и списки) называют символьными выражениями. Отношения между различными символьными выражениями можно представить следующим образом: (S)-выражение – это либо атом, либо список; атомы являются простейшими S-выражениями.

Функции в Лиспе Обращение к функции, которое в обычной нотации принято писать f(x,y,z), имеет вид (f x y z). Оно имеет вид списка, первый элемент которого атом – имя функции. Следующие элементы – аргументы функции – выражения. Каждая функция может накладывать ограничения на число и вид аргументов. Если функция G не требует аргументов, то обращение к ней имеет вид (G).

Выводы –Язык Лисп был изначально создан как язык ИИ для символьной обработки данных. Базовыми конструкциями в Лиспе являются атомы и списки, в совокупности образующие S- выражения. Основной и единственный способ вычислений – вызов функций (в осн. рекурсивный). В Лиспе существует множество базовых (встроенных/предопределенных) функций. –Есть встроенные функции для организации ветвлений и циклов, а также отладочные функции и др. Существуют различные виды рекурсий: вычисляемые по значению, по аргументу, параллельные, взаимные, высших порядков.