WWW.DISSERS.RU

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

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


Pages:     || 2 | 3 | 4 | 5 |   ...   | 9 |
Введение в программирование на языке Лисп Учебное пособие для начинающих Лидия Городняя Gorod@iis.nsk.su Новсибирск, 2005 1 Содержание Предисловие................................. 3 1. Рекурсивные функции и структуры........... 5 2. Идеальный Лисп.......................... 10 3. Запись программ........................... 20 4. Определение языка......................... 32 5. Интерпретатор............................. 43 6. Отображения и функционалы................ 51 7. Имена и контексты........................ 64 8. Управление процессами..................... 76 9. Традиционное программирование............ 80 10. Парадигмы программирования.............. 89 История и выводы............................. 93 Литература.................................. 94 Термины.................................... 95 Учебное пособие разработано при поддержке Российского фонда переподготовки кадров и сдано в печать в 2004 году.

Курс разработан на базе Высшего колледжа информатики Новосибирского госуниверситета.

Содержание курса соответствует PF4, PL7, PL5 классификатора CC2001CS.

2 Предисловие Целью курса является изучение идей языка Лисп и методов функционального программирования. В курсе будут рассмотрены:

- История языка Лиспа.

- Идеи символьной обработки информации.

- Принципы функционального программирования.

- Методы программирования на Лиспе.

Автор языка Лисп – профессор математики и философии Джон Мак-Карти, выдающийся ученый в области искусственного интеллекта. Он предложил проект языка Лисп, идеи которого возбудили не утихающие до наших дней дискуссии о сущности программирования. Сформулированная Джоном МакКаpти (1958) концепция символьной обработки информации восходит к идеям Чёрча (лямбда-исчисление) и других видных математиков конца 20-ых годов предыдущего века. Джон Мак-Карти предложил функции рассматривать как общее понятие, к которому могут быть сведены все другие понятия программирования.

Особый интерес представляют рекурсивные функции и методы их реализации в системах программирования. Понятие функции отчасти содержит концепцию времени: сначала вычисляются аргументы в порядке перечисления, затем в соответствии с заданным алгоритмом строится значение функции - ее результат.

Лаконизм рекурсии может скрывать нелегкий путь к элегантному решению задачи. А. П. Ершов в предисловии к русскому переводу книги П.Хендерсона привел поучительный пример задачи о рекурсивной формуле, сводящей вычитание единицы из натурального числа к прибавлению единицы:

{1 –1 = 0 ; ( n +1 ) -1 = n }, не поддавшейся А.Чёрчу и решенной С.Клини лишь в 1932 году:

{ F (x, y, z) = если (x = 1) то иначе если ((y +1) = x) то z иначе F (x, y +1, z +1) ;

n –1 = F (n, 0, 0) } алг F ( цел x, y, z) арг x, y, z нач если (x = 1) то знач := инес (y +1) /= x то знач := F (x, y +1, z +1) кон алг N-1 (цел N) арг N нач знач := F (N, 0, 0) кон Решение получилось через введение формально усложненной вспомогательной функции с накопительными парметрами, что противоречит интуитивному стремлению к монотонности движения от простого к сложному.

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

В этом курсе мы сконцентрируемся на ключевой идее Лиспа - сведении понятия “программа” к взаимодействию разных категорий функций, а также на основах и методах функционального программирования. Курс может быть адресован студентам, любителям экспериментального программирования, преподавателям информатики и старшеклассникам. Подробно познакомимся с базисом Лиспа, проанализируем конструктивность методов программирования на Лиспе, изучим построение Лисп-системы и узнаем ее архитектурные особенности, рассмотрим методы эффективного и прикладного программирования в функциональном стиле. С математическими основами Лиспа можно ознакомиться подробнее на страницах журнала “Компьютерные инструменты в образовании” [5,6].

Примечание [D1]: Примечан ие. Этот парагарф адресован читателям, не знакомым с 1. Рекурсивные функции и структуры математическими оснвоами программирования и мтеодами реализации рекурсивных функций в системах “Вот дом, который построил Джек …” программирования.

Этот парагарф адресован новичкам, не знакомым с математическими основами программирования и методами реализации систем программирования. На игровых, почти шуточных, моделях рассмотрим понятия:

- Рекурсия.

- Иерархия.

- Список.

- Функция.

Модель 1. "Матрешки" Представим, что перед нами сувенир “матрешки”, вкладывающиеся друг в друга.

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

Задача 1. Как узнать, сколько матрешек внутри Предварительный анализ и описание процесса решения:

1) Глядя на большую матрешку трудно сказать, сколько в ней спрятано ее меньших подруг. Но можно ее потрясти и по звуку понять, есть ли что-то внутри или она пуста.

2) Если матрешка не пуста, то ее можно разнять и вынуть внутреннюю матрешку, а части внешней матрешки соединить и поставить в сторонку, чтобы не мешали дальнейшему эксперименту.



3) Возвращаемся к исходной задаче, но с меньшей матрешкой, что гарантирует завершение процесса. (Реальные вещи не могут уменьшаться до бесконечности.) 4) Если матрешка пуста, то имеющиеся матрешки можно пересчитать – они все на виду.

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

- Разбираем внешнюю матрешку и убираем ее.

- Вынимаем внутренний комплект матрешек.

- Трясем матрешку, чтобы узнать, есть ли что-то внутри.

Задача 2. Пусть все матрешки разобраны. Надо их собрать в одну.

Предварительный анализ и описание процесса решения:

Для решения такой задачи понадобится еще две функции:

- Прячем меньшую матрешку в большую - Сравниваем матрешки 1) Выбираем самую маленькую матрешку.

2) Сравниваем матрешки, ищем ближайшую к выбранной по размеру.

3) Прячем меньшую матрешку в большую.

4) Если еще остались матрешки, то возвращаемся к исходной задаче с уменьшенным числом матрешек.

5) Если матрешка всего одна, то процесс сборки завершен.

Здесь рекурсивная функция решения задачи включает в себя поиск подходящего элемента из набора, уменьшающегося на каждом витке процесса.

Задача будет решена, когда обнаружится, что не из чего выбирать очередной элемент.

Задача 3. Надо выяснить сколько матрешек, а потом снова собрать их в одну.

Предварительный анализ и описание процесса решения:

При описании решения сразу учитываем, что понадобится не только разбирать матрешек, но и собрать их обратно.

1) Решаем задачу 1, но с небольшой поправкой в пункте 2:

- Если матрешка не пуста, то ее можно разнять и вынуть внутреннюю матрешку, а части внешней матрешки ставить рядом по очереди, чтобы потом их было удобно брать для сборки.

2) Решаем задачу 2, но с учетом, что части разобранных матрешек стоят по порядку. Значит, пункт 2 можно уточнить:

- Берем части очередной матрешки.

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

Модель 2. “Конверты и карточки”.

Другой ряд иллюстраций дает модель из конвертов, вкладываемых друг в друга.

Конверты можно надписывать. Пустой конверт можно заменить карточкой с той же надписью – это атом. Внутрь коверта можно, как в матрешки, вкладывать конверты или карточки. Подобным образом устроены иерархические структуры данных - символьные выражения (S-выражения). Вкладывание объекта в конверт - простейшая модель консолидации двух данных, сцепления их в одно более сложное данное.

Примеры:

Пусть в конверт с надписью «ГОЛОВА» вложен пустой конверт с написью «ХВОСТ». Такую структуру данных можно изобразить в виде S-выражения:

( ГОЛОВА. ХВОСТ) Заключение в скобки символизирует целостность структуры. Если конверт с написью «ХВОСТ» заранее вложить в конверт с написью «СЕРЕДИНА», а его вложить в конверт с надписью «ГОЛОВА», то соотвествующую структуру данных можно записать в виде S-выражения:

( ГОЛОВА. (СЕРЕДИНА. ХВОСТ)) Пустой конверт или карточку без написи можно изображать парой скобок.

( ) Модель 3. “Кошелек”.

Наклеим на лицевую сторону конверта большой карман. Получится нечто вроде кошелька. Вместо надписи на конверте можно в карман кошелька вкладывать надписанную карточку.

Возьмем карточку с написью «ЭЛЕМЕНТ» и вложим ее в карман пустого кошелька без написи – получится модель одноэлементного списка:

(ЭЛЕМЕНТ) Многократным применением такого процесса можно строить списки произвольной длины.

(ЧЕМОДАН ПОРТФЕЛЬ РЮКЗАК ПОРТМОНЕ) Если разрешить в карман кошелька вместо карточек вкладывать другие кошельки, то элементы списка можно конструировать и получать многоуровневые списки вида:

((ЭЛ1-1 ЭЛ1-2) ЭЛ 2 (ЭЛ3-1 ЭЛ3-2 ЭЛ3-3) ЭЛ4) По традиции в Лиспе пустой список изображается атомом NIL. Атомарность пустого списка вполне естественна в мире вещей – это прямой аналог упаковки.

Пустой конверт - обычная вещь, которую можно наполнить, тогда она становится сложной, или опустошить, тогда она становится простой.

Модель 4. “Форма, вид и пометки”.

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

Примеры:

(fn arg1 arg2... argN) (Собрать портфель рюкзак) (+ 1 2 3 4 5 ) (fn (gn arg1) arg2... argN) (Сложить (Найти портфель) (Подготовить Список_предметов)) (+ 5 (* 2 3.14 R) X) При таком подходе список, представляющий вызов функции, внешне мало отличается от списка, представляющего данные, не требующие особой обработки.

В таких случаях конверт можно заклеить, а в карман вставить карточку с надписью “QUOTE”, что соотвествует блокировке вычислений. Увидев, что конверт заклеен, можно так его и оставить или расклеить. В последнем случае его содержимое становится доступным для обработки в будущем. В записи это можно изобразить символом апострофа "'".





Примеры:

(СОБРАТЬ ‘(ШКАТУЛКА КОЛЬЦО СЕРЬГИ) СУМКА) (fn 'arg1 arg2... argN) (cons '(+ 1 2 3 4 5) arg2... argN) При такой записи первые аргументы функций вычисляться не будут.

(Расположены вторыми в списках.) Обычно подразумевают, что функция применяется к заранее вычисленным значениям ее аргументов. Но если в качестве данных допускать не только значения, но и символьные формы - записи программ для вычисления разных значений, то можно рассматривать и реализовывать специальные функции, способные обрабатывать аргументы нестандартно по любой схеме. Такие варинаты нужны для реализации приcвоений и управления процессами.

Конверты, кошельки и карточки могут быть разного цвета, они могут быть помечены перфорацией, марками, текстами и рисунками. Такие пометки можно понимать как указания на схему обработки конвертов и их содержимого ("Перед прочтением - сжечь!"), что и позволяет моделировать функции и функциональные программы, характерные для программирования на Лиспе. Подобным образом организуют отображения – нечто вроде переноса рисунка вышивки с бумаги на ткань.

2. Идеальный Лисп - Основы символьной обработки.

- Cписочная запись - Точечная нотация - Элементарные функции 1. Основы символьной обработки.

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

1) Природа данных Все данные представляются в форме символьных выражений. В Лиспе Дж.

Мак-Карти назвал их S-выражениями. Система программирования над такими структурами обычно использует для их хранения всю доступную память, поэтому программист может быть освобожден от распределения памяти под отдельные блоки данных.

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

3) Подобие машинным языкам Система программирования на Лиспе допускает, что программа может интерпретировать и/или компилировать программы, представленные в виде Sвыражений. Это сближает программирование на Лиспе с методами низкоуровневого программирования и отличает от традиционной методики применения языков высокого уровня.

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

A Nil ATOM LISP ЗанятиеНовый_год ВотДлинныйАтомНуОченьДлинныйНоЕслиНадоАтомМожетБытьЕщеДлинннее Ф4длш139к131б Одинаково выглядящие атомы не различимы по своим свойствам. Термин “атом” выбран по аналогии с химическими атомами, строение которых – предмет другой науки. Согласно этой аналогии атом может иметь достаточно сложное строение, но атом не предназначен для разбора на части базовыми средствами языка.

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

Функция Аргументы Результат Cons Атом ( Атом. X ) X Car Атом ( Атом. X ) Cdr X ( Атом. X ) По соглашению атом Nil выполняет роль пустого списка. Бинарный узел, содержащий пару атомов ATOM и Nil, рассматривается как одноэлементный список (ATOM ) :

АТОМ NIL или для наглядности:

АТОМ Если вместо атома “ATOM” подставлять произвольные атомы, а вместо “Nil” - произвольные списки, затем вместо атомов - построенные списки и так далее, то мы получим множество всех возможных списков. Можно сказать, что список - это заключенная в скобки последовательность из разделенных пробелами атомов или списков.

Примеры:

(C ) С (B C ) В С (C (A B)) С А В Такая форма записи S-выражений называется списочной записью (list-notation).

Список – это перечень произвольного числа элементов, разделенных пробелами, заключенный в круглые скобки.

Элементы списка могут быть любой природы.

Упражнения: Нарисуйте диаграммы для списков вида:

((A B) C) ((A B) (D C)) ((A B)(D(C E))) Любой список может быть построен из пустого списка и атомов с помощью CONS и любая его часть может быть выделена с помощью подходящей композиции CAR-CDR.

CONS - Функция, которая строит списки из бинарных узлов, заполняя их парами объектов, являющихся значениями пары ее аргументов. Первый аргумент произвольного вида размещается в левой части бинарного узла, а второй, являющийся списком, - в правой.

CAR – Функция, обеспечивающая доступ к первому элементу списка - его “голове”.

Pages:     || 2 | 3 | 4 | 5 |   ...   | 9 |










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

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