Учебник по Lisp (Материалы к экзамену и коллоквиумам 2013-го года), страница 14

Вконце 1968 года Джон Мак-Карти лично познакомил программистов Москвы и Новосибирскас Лиспом, что побудило к реализации отечественных версий языка.40Литература и сайты1. McCarthy J. LISP 1.5 Programming Mannual.- The MIT Press.,Cambridge, 1963, 106p.2. Хендерсон П. Функциональное программирование.- М.: Мир, 19833. Хьювенен Э., Сеппанен Й. Мир Лиспа., т.1,2, М.: Наука, 19944. Сергеев Л.О. Удивительный мир языка Лисп. Введение в язык и задачи, задачи, задачи. //Информатика – 2000, N 29.5. Лавров С.С. Функциональное программирование. // Компьютерные инструменты вобразовании. – 2002, N 2-4.6. Городняя Л.В., Лавров С.С. Функциональное программирование.

Принципы реализацииязыка Лисп. // Компьютерные инструменты в образовании. – 2002, N5, с. 49-587. 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 Clisp11. Городняя Л.В. Основы функционального программирования. Курс лекций. Учебноепособие.

Серия «Основы информационных технологий» /М.: ИНТУИТ.РУ «Интернетуниверситет Информационных Технологий», 2004. – 280 с.41ТерминыТерминTermАлгоритмalgorithmА-списокa-listАссоциативный списокAssociation listОпределениеАбстрактное представление процесса, который можетбыть механизирован, т.к. ему предстоит бытьзапрограммированным для выполнения машиной.Ассоциативный списокСписок пар, эквивалентный таблице с двумя столбцами.Используется для связывания переменных с ихзначениями и функций с их опрелениями.Например, ((VAR1 .

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

Например, nconcМодель вычислений, при которойзадерживается вычисление всех фактическихаргументов всех функций, а такжезадерживается вычисление самих функций.Для получения результата необходимовозобновлять вычисления.Определение функции + контекст в моментопределения этой функции. В Лиспезамыкание строится с помощью функцииFUNCTION. Построение замыканийпозволяет более надежно оперировать сфункциями, у которых есть свободныепеременныеЧистая функция, без побочных эффектов соднозначным результатомИмя свойства атома (атрибут), расположенноенепосредственно перед значением этого свойства в спискесвойств атома.42ИнтерпретаторИстинностныезначенияКомпиляторКомпозицияInterpreterИнтерпретатор выполняет программу, используя ееисходный язык и формально исполняя представленныепрограммой алгоритмы.

В этом отличие от компилятора,который переводит программу с исходного языка на языкмашины для многократного исполнения алгоритмов потом.TruevaluescompilerИстина и Ложь. В Лиспе этим понятиямсоответствуют атомы T и NIL.Программа, переводящая с исходного языка намашинный (объектный) язык. В отличие от большинствакомпиляторов, LISP – компилятор не пытаетсякомпилировать полную программу до ее исполнения.Более эффективна компиляция отдельных функций,описанных как S-выражения, на машинный язык во времявычисления, по мере их отладки.compositionКомпозиция функций – это использование значенияодной функции в качестве аргумента другой.

Обычнокомпозиция записывается с помощью вложенных скобок.Пример: (CONS (CAR Y) X)КонстантаConstantСимвол, значение которого не меняется в течениевычислений.Примеры: T NIL 1 2 3 «строка» …КонтекстЛиспЛисппроцессорыcontextLispLispprocessorСостояние среды, в которой происходитвычислениеУниверсальный язык программирования,созданный Джоном Маккарти в конце 60-егодов.Аппаратные реализации подмножеств языкаЛисп, концептуально близких SECD и языкуScheme - активно используется статическийконтекст.

Были выпущены рядом ведущихфирм в конце 70-х годов XX века.Специальная форма, включающая AND, OR или NOT,которая может использоваться для построения значенийистинности и конструирования предикатов.Логическая формаLogical formЛямбда-выражениеLambda notationОбозначение, впервые предложеное Черчем дляобобщения выражений (форм) и функций, использующеегреческую букву «лямбда» для четкого выделения вформулах аргументов функций.MemofunctionФункция, которая накапливает ранеевычисленные соответствия между аргументоми результатомПодмножество декартового произведения областиопределения и области значенияМемофункцияОтображениеПеременнаяПредикатПсевдофункцияПустой списокImaging, mapvariablePredicatePseudofunctionEmptylistПеременная - символ, значение которогоможет меняться в процессе выполненияпрограммы.Функция со значениями истина (true) или ложь (false)Функция с побочным эффектомСписок, в котором нет элементов.

В Лиспеобозначается как NIL43РекурсияСборка «мусора»RecursionGarbage collector,reclaimerОпределение является рекурсивным, если оно ссылаетсяна себя. Это может быть явная ссылка из определения иликосвенная, через серию определенийПроверка доступных структур с пометкой, чтобывыделить ненужные, недоступные слова – «мусор» . Затемвесь «мусор» собирается в список свободной памяти, стем чтобы эти слова использовать повторно.SymbolАтом, обладающий списком свойств для храненияимени, значения, определения функции, идентификациипринадлежности пакету и пр.Property list, p-listНабор индикаторов и значений свойств, объединенных водноуровневый список и связанный с некоторым атомом втаблице атомов.Специальная формаSpecial formВстроенные функции, которые сами вычисляют своиаргументы.

Такая техника обеспечивает связываниепеременных, блочную структуру, циклы и другие процессыуправления вычислениями.Свободная переменнаяFree variableСвойствоатомаPropertyСимволСписок свойствСвязанные переменныеBound variableПеременная, не объявленная ни как рабочая в блоке, никак связанная в функции. Переменная можетрассматриваться как связанная или свободная тольковнутри контекста, в котором она появляется.

Длявычисления интерпретатором переменная должна бытьсвязана на некотором уровне или иметь постоянноезначение (константа).Данное, размещенное в списке свойстватома непосредственно вслед за индикаторомэтого свойства.Переменная, входящая в список связанных переменных,расположенный за LAMBDA.Значением связанной переменной является аргумент,расположенный в позиции, соответствующей вхождениюпеременной в LAMBDA-список.

Например, в выражениивида:(( LAMBDA (X Y ) E )(QUOTE (A B)) (QUOTE C))Y имеет значение C, для любых его вхождений в E, а X– (A B).Список свободной памятиСписокFree-storage listСписок доступных слов памяти, используемых привычислении.

Каждое обращение к CONS преобразуетпервое слово списка свободной памяти, которое из этогосписка исключается. Когда список свободной памятиисчерпан, тогда проводится сборка мусора и строитсяновый список свободной памяти.ListS-выражение, для которого движение вправоограничено символом NIL.Предикат LISTP(x) = NULL(x) OR (NOT (ATOM (x))AND LISTP (CDR (x)))Списочная записьList notationМетод изображения S-выражений в виде( m1 m2 … mn)вместо вида(m1 .

(m2 . ( …. (mn . NIL)))44ТаблицаатомовAtomtableTagТегТотальнаяфункцияТочечная нотацияTotalfunctionDot notationФорма хранения информации об атомах вреализациях Лиспа.Код типа значения в структуре данных.Сопровождает адрес в указателе.Всюду определенная функцияМетод записи S-выражений составлением заключенныхв скобки пар S-выражений, разделенных точкой. Точечнаянотация – базовая структура данных в Lisp-е.

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

Значение универсальной функции– это значение формы или результатвычислимой функции, примененной к ееаргументам.Примеры: EVAL, APPLYЗапись ветвления в виде выражения, состоящего изсписка предикатов и соответствующих им форм.Значением условного выражения являетсязначение формы, соответствующей первому истинномупредикату.Пример: ( COND (( < A 0) B) (T C))ФормаФуннкциональныйаргументФункцияЧистый ЛиспAPPLYFormВыражение, которое может быть вычислено, еслиустановлено некоторое соответствие между входящими внего переменными и набором фактических аргументов.Функции в отличие от формы следует явно задатьаргументы.Functional argumentФункция, являющаяся аргументом функционала. ВЛиспе функциональные аргументы обозначают формой “#”(FUNCTION).FunctionPurelispAPPLYФункция преобразует входные данные в выходные.Функции в Лиспе описываются с помощью специальнойфункции DEFUN.

Программа на Лиспе - это коллекцияфункций.Абстрактный язык программирования набазе минимального набора функций: CAR,CDR, CONS, EQ, ATOM, COND,LAMBDA,QUOTE.Метод применения функции к списку ее аргументов.EVAL и APPLY - функции с помощью которых можносконструировать интерпретатор Лиспа.

Все функциивысших порядков в той или иной степени используютAPPLY или FUNCALL45CARCARГолова неатомарного S-выражения. Имя образовано отContents of Addres of Register. Голова списка илиточечной пары. Левая частьCDRCDRХвост неатомарного S-выражения. Имя образовано отContents of Decrement of RegisterEVALФункция, которая вычисляет вражения в Лиспе всоответсвии со списком фактических параметров исемантикой вычисляемого вырженияEVALNILS - выражениеNILS - expressionПустой список. Ложь.Универсальная структура данных для символьныхвычислений – символьное выражение.46.