WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 7 | 8 ||

Синтаксис Лиспа изысканно прост. Разделитель - пробел, ограничители - круглые скобки. В скобки заключается представление функции с ее аргументами. Все остальное - вариации в зависимости от категории функций, определенности атомов и вычислимости выражений, типов значений и структур данных. Функционалы - это одна из категорий функций, используемая при организации управления вычислениями.

Лисп - язык символьной обработки информации. Методы программирования на Лиспе часто наывают “функциональное программирование”. Лисп прочно утвердился как эсперанто для задач искусственного интеллекта. К середине семидесятых годов XX века на Лиспе решались наиболее сложные в практике программирования задачи из области дискретной и вычислительной математики, экспериментального программирования, лингвистики, химии, биологии, медицины и инженерного проектирования. На Лиспе реализована AutoCAD - система автоматизации инженерных расчетов, дизайна и комплектации изделий из доступного конструктива, и Emacs – весьма популярный текстовый редактор в мире UNIX/Linux. Многие созревшие на базе Лиспа системные решения постепенно обрели самостоятельность и выделились в отдельные направления и технологии.

Реализационные находки Лиспа, такие как ссылочная организация памяти, “сборка мусора” - автоматизация повторного использования памяти, частичная компиляция программ с интерпретацией промежуточного кода, длительное хранение атрибутов объектов в период их использования и др., перекочевали из области исследований и экспериментов на базе Лиспа в практику реализации операционных систем и систем программирования.

Приверженцы Лиспа ценят его не только за элегантность, гибкость, но и за способность к точному представлению программистских идей и удобной отладке. В стандартных языках программирования принята императивная организация вычислений по принципу немедленного выполнения каждой очередной команды. Это не всегда обосновано и эффективно. Неимперативные модели управления процессами позволяют прерывать и откладывать процессы, а потом их восстанавливать и запускать или отменять, что обеспечено в Лиспе средствами конструирования функций, блокировки вычислений и их явного выполнения.

История и выводы (вместо заключения) История Лиспа пронизана жаркими спорами, притиворечивыми суждениями, яркими достижениями и смелыми изобретениями:

1958 - Первые публикации Джона Мак-Карти о замысле языка символьной обработки.

1962-1964 - Авторские проекты первых Лисп-систем.

1964 - Демонстрация принципиальной решаемости проблем искусственного интеллекта.

(Написанная Дж.Вейценбаумом на Лиспе программа-собеседник “Элиза”, имитирующая речевое поведение психоаналитика, дала положительный ответ на вопрос о возможности искусственного разума.) 1972-1974 - Разрешение теоретических парадоксов, связанных с бестиповым лямбдаисчислением.

1972-1980 - Стандартизация языка Лисп.

1978 – Появление Лисп-компьютеров.

1965-1990 - Построение специализированных диалектов Лиспа и создание практичных реализаций для широкого спектра весьма различных применений, включая инженерное проектирование и системы математической обработки информации 1992-2002 - Разработка визуальных и сверхэффективных Лисп-систем, таких как CMUCL.

В нашей стране программирование знакомство с языком Лисп состоялось из первых рук. В конце 1968 года Джон Мак-Карти лично познакомил программистов Москвы и Новосибирска с Лиспом, что побудило к реализации отечественных версий языка.

Литература и сайты 1. McCarthy J. LISP 1.5 Programming Mannual.- The MIT Press., Cambridge, 1963, 106p.

2. Хендерсон П. Функциональное программирование.- М.: Мир, 3. Хьювенен Э., Сеппанен Й. Мир Лиспа., т.1,2, М.: Наука, 4. Сергеев Л.О. Удивительный мир языка Лисп. Введение в язык и задачи, задачи, задачи. // Информатика – 2000, N 29.

5. Лавров С.С. Функциональное программирование. // Компьютерные инструменты в образовании. – 2002, N 2-4.

6. Городняя Л.В., Лавров С.С. Функциональное программирование. Принципы реализации языка Лисп. // Компьютерные инструменты в образовании. – 2002, N5, с. 49-7. http://www-formal.stanford.edu/jmc/ - Личный сайт Дж. МакКарти с текстами его публикаций 8. http://www.marstu.mari.ru/mmlab/home/lisp/title.htm – Дистанционный учебник М.Н.Морозова 9. http://grimpeur.tamu.edu/~colin/lp/ - Небольшой учебник для начального знакомства с Лиспом 10. http://www.paulgraham.com/onlisptext.html - Интересные материалы по Clisp Паула Грэхема, автора книги по стандарту ANSI Clisp 11. Городняя Л.В. Основы функционального программирования. Курс лекций. Учебное пособие. Серия «Основы информационных технологий» /М.: ИНТУИТ.РУ «Интернетуниверситет Информационных Технологий», 2004. – 280 с.

Термины Термин Term Определение Алгоритм algorithm Абстрактное представление процесса, который может быть механизирован, т.к. ему предстоит быть запрограммированным для выполнения машиной.

А-список a-list Ассоциативный список Ассоциативный список Association list Список пар, эквивалентный таблице с двумя столбцами.

Используется для связывания переменных с их значениями и функций с их опрелениями.

Например, ((VAR1. VAR2) (B. (U V (W)))(C. Z)) Атом Atom Атомный символ Атомный символ Atomic symbol Минимальный элемент S-выражений. Допустимые атомные символы – это определенные последовательности букв, цифр и специальных литер. Примеры: AI ИИ NIL База_2-Базисные функции Basic functions: Эти функции называются базисными, потому что их CAR, CDR, CONS, достаточно для построения полного класса вычислимых EQ, ATOM функций от S-выражений использованием композиции, условных выражений и рекурсии.

Всюду- total Функция, которая возвращает результат на определенные functio любом аргументе - тотальная функция функции n Destruc Деструктивны tive Функции, изменяющие структуру входных е функции functio данных. Например, nconc ns Модель вычислений, при которой задерживается вычисление всех фактических Lazy Замедленные аргументов всех функций, а также evaluati вычисления задерживается вычисление самих функций.

on Для получения результата необходимо возобновлять вычисления.

Определение функции + контекст в момент определения этой функции. В Лиспе замыкание строится с помощью функции Замыкание Lexical FUNCTION. Построение замыканий функции closure позволяет более надежно оперировать с функциями, у которых есть свободные переменные Pure Идеальная Чистая функция, без побочных эффектов с functio функция однозначным результатом n Индикатор свойства Indicator Имя свойства атома (атрибут), расположенное непосредственно перед значением этого свойства в списке свойств атома.

Интерпретатор Interpreter Интерпретатор выполняет программу, используя ее исходный язык и формально исполняя представленные программой алгоритмы. В этом отличие от компилятора, который переводит программу с исходного языка на язык машины для многократного исполнения алгоритмов потом.

Истинностные True Истина и Ложь. В Лиспе этим понятиям значения values соответствуют атомы T и NIL.

Компилятор compiler Программа, переводящая с исходного языка на машинный (объектный) язык. В отличие от большинства компиляторов, LISP – компилятор не пытается компилировать полную программу до ее исполнения.

Более эффективна компиляция отдельных функций, описанных как S-выражения, на машинный язык во время вычисления, по мере их отладки.

Композиция composition Композиция функций – это использование значения одной функции в качестве аргумента другой. Обычно композиция записывается с помощью вложенных скобок.

Пример: (CONS (CAR Y) X) Константа Constant Символ, значение которого не меняется в течение вычислений.

Примеры: T NIL 1 2 3 «строка» … Состояние среды, в которой происходит Контекст context вычисление Универсальный язык программирования, Лисп Lisp созданный Джоном Маккарти в конце 60-е годов.

Аппаратные реализации подмножеств языка Lisp Лисп, концептуально близких SECD и языку Лиспprocess Scheme - активно используется статический процессоры or контекст. Были выпущены рядом ведущих фирм в конце 70-х годов XX века.

Логическая форма Logical form Специальная форма, включающая AND, OR или NOT, которая может использоваться для построения значений истинности и конструирования предикатов.

Лямбда-выражение Lambda notation Обозначение, впервые предложеное Черчем для обобщения выражений (форм) и функций, использующее греческую букву «лямбда» для четкого выделения в формулах аргументов функций.

Memo- Функция, которая накапливает ранее Мемоfunctio вычисленные соответствия между аргументом функция n и результатом Подмножество декартового произведения области Отображение Imaging, map определения и области значения Переменная - символ, значение которого Переменная variable может меняться в процессе выполнения программы.

Предикат Predicate Функция со значениями истина (true) или ложь (false) PseudoПсевдоfunctio Функция с побочным эффектом функция n Empty Список, в котором нет элементов. В Лиспе Пустой список list обозначается как NIL Определение является рекурсивным, если оно ссылается Рекурсия Recursion на себя. Это может быть явная ссылка из определения или косвенная, через серию определений Сборка «мусора» Garbage collector, Проверка доступных структур с пометкой, чтобы reclaimer выделить ненужные, недоступные слова – «мусор». Затем весь «мусор» собирается в список свободной памяти, с тем чтобы эти слова использовать повторно.

Атом, обладающий списком свойств для хранения Символ Symbol имени, значения, определения функции, идентификации принадлежности пакету и пр.

Набор индикаторов и значений свойств, объединенных в Список свойств Property list, p-list одноуровневый список и связанный с некоторым атомом в таблице атомов.

Встроенные функции, которые сами вычисляют свои аргументы. Такая техника обеспечивает связывание Специальная форма Special form переменных, блочную структуру, циклы и другие процессы управления вычислениями.

Свободная переменная Free variable Переменная, не объявленная ни как рабочая в блоке, ни как связанная в функции. Переменная может рассматриваться как связанная или свободная только внутри контекста, в котором она появляется. Для вычисления интерпретатором переменная должна быть связана на некотором уровне или иметь постоянное значение (константа).

Данное, размещенное в списке свойств Свойство Propert атома непосредственно вслед за индикатором атома y этого свойства.

Связанные переменные Bound variable Переменная, входящая в список связанных переменных, расположенный за LAMBDA.

Значением связанной переменной является аргумент, расположенный в позиции, соответствующей вхождению переменной в LAMBDA-список. Например, в выражении вида:

(( LAMBDA (X Y ) E )(QUOTE (A B)) (QUOTE C)) Y имеет значение C, для любых его вхождений в E, а X – (A B).

Список свободной памяти Free-storage list Список доступных слов памяти, используемых при вычислении. Каждое обращение к CONS преобразует первое слово списка свободной памяти, которое из этого списка исключается. Когда список свободной памяти исчерпан, тогда проводится сборка мусора и строится новый список свободной памяти.

Список List S-выражение, для которого движение вправо ограничено символом NIL.

Предикат LISTP(x) = NULL(x) OR (NOT (ATOM (x)) AND LISTP (CDR (x))) Списочная запись List notation Метод изображения S-выражений в виде ( m1 m2 … mn) вместо вида (m1. (m2. ( …. (mn. NIL))) Таблица Atom Форма хранения информации об атомах в атомов table реализациях Лиспа.

Код типа значения в структуре данных.

Тег Tag Сопровождает адрес в указателе.

Total Тотальная functio Всюду определенная функция функция n Точечная нотация Dot notation Метод записи S-выражений составлением заключенных в скобки пар S-выражений, разделенных точкой. Точечная нотация – базовая структура данных в Lisp-е. Списочная запись определяется с помощью точечной нотации.

Примеры: (А. В) (А. NIL) Обычно - адрес, по которому, можно найти продолжение информации. В Лиспе такой Указатель Pointer адрес сопровождается тегом, задающим тип значения, расположенного по адресу.

Функция, аргументы которой – Sвыражения, представляющие любую Univers вычислимую форму или функцию и ее Универсальна al аргументы. Значение универсальной функции я функция functio – это значение формы или результат n вычислимой функции, примененной к ее аргументам.

Примеры: EVAL, APPLY Условное выражение Conditional Запись ветвления в виде выражения, состоящего из expression списка предикатов и соответствующих им форм.

Значением условного выражения является значение формы, соответствующей первому истинному предикату.

Пример: ( COND (( < A 0) B) (T C)) Форма Form Выражение, которое может быть вычислено, если установлено некоторое соответствие между входящими в него переменными и набором фактических аргументов.

Функции в отличие от формы следует явно задать аргументы.

Фуннкциональный Functional argument Функция, являющаяся аргументом функционала. В аргумент Лиспе функциональные аргументы обозначают формой “#” (FUNCTION).

Функция преобразует входные данные в выходные.

Функции в Лиспе описываются с помощью специальной Функция Function функции DEFUN. Программа на Лиспе - это коллекция функций.

Абстрактный язык программирования на Pure базе минимального набора функций: CAR, Чистый Лисп lisp CDR, CONS, EQ, ATOM, COND, LAMBDA,QUOTE.

Метод применения функции к списку ее аргументов.

EVAL и APPLY - функции с помощью которых можно APPLY APPLY сконструировать интерпретатор Лиспа. Все функции высших порядков в той или иной степени используют APPLY или FUNCALL Голова неатомарного S-выражения. Имя образовано от CAR CAR Contents of Addres of Register. Голова списка или точечной пары. Левая часть Хвост неатомарного S-выражения. Имя образовано от CDR CDR Contents of Decrement of Register Функция, которая вычисляет вражения в Лиспе в EVAL EVAL соответсвии со списком фактических параметров и семантикой вычисляемого выржения NIL NIL Пустой список. Ложь.

Универсальная структура данных для символьных вычислений – символьное выражение.

S - выражение S - expression

Pages:     | 1 |   ...   | 7 | 8 ||










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.