Отправляет email-рассылки с помощью сервиса Sendsay

Программирование с нуля - это совсем просто!

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "Как создать свой сайт и заработать?" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Апрель 2007   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Автор
sheldon

Статистика

4.990 подписчиков
0 за неделю
←   Все выпуски   →

Программирование с нуля - это совсем просто! 166) Лисп: атомы, списки, функции и СуперУм


Школа программирования

166) Функциональное программирование и Лисп: атомы, списки и функции + развиваем СуперУм

Продолжаем тему про Лисп из выпуска 162.

Данные в Лиспе

В Лиспе вся работа ведется с так называемыми АТОМАМИ.

Атом - это последовательность букв, цифр и других символов, кроме пробелов и скобок.

Примеры атомов Лиспа:

   abcde
   Это_Атом_Лиспа
   12345
   1A2B3C4D
   0+0.110число
   xy=yz

Атомы организуются в СПИСКИ - последовательности атомов, взятые в круглые скобки.

Примеры списков Лиспа:

   (1 2 3 4 5)
   (ab cd ef 200)

В список можно включать другие списки:

   (1 (2 3) 4)

Список может состоять из одного элемента:

   (а)

или быть пустым:

   ()

Пустой список также обозначается как NIL. Записи () и NIL эквивалентны.

Могут быть и такие списки:

   (;)
   ( :- )
   ( (:-) ())
   (() a () () (b))
   ((((()))))

Главное, чтобы число закрывающих скобок ( ( ( в точности равнялось числу открывающих скобок :) :) :)

Пока ничего сложного, правда?

Выражения и функции

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

То есть вызов функции синуса Sin(X) в Лиспе запишется так: (Sin X)

А функция F10 с параметрами a, b и с - F10(a,b,c) - в Лиспе записывается как (F10 a b c) .

Если первым атомом следует неизвестная Лиспу функция, то возникнет ошибка вычислений.

Изучаем первую функцию Лиспа

Как разделить список-функцию от списка данного? В этом поможет функция QUOTE. Она возвращает в качестве своего значения значение параметра (аргумента). У QUOTE может быть только один параметр!

Если параметр QUOTE - атом, то она возвращает этот атом. Если ее параметр - список, то она возвращает этот список (не вычисляя его!).

Например, если в программе встречается запись (Sin X) , то она считается вызовом функции Sin и сразу вычисляется. А вот если встречается запись (QUOTE (Sin X)), то результатом такого выражения будет список (Sin X) , который уже больше не вычисляется, а временно представляется как данное - передается далее для обработки следующей функцией.

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

Функция QUOTE используется часто, поэтому для нее существует сокращение в виде одинарной кавычки:

' (a b c) - результатом будет список (a b c)

Применять QUOTE к нескольким аргументам нельзя: (QUOTE A B C) выдаст ошибку.

Запустите NewLISP, он сразу предложит строку подсказки. В ней можно вводить выражения Лиспа и получать их результат. Если ввести

   > (a b c)

и нажать ENTER, то NewLISP напишет invalid function (ошибочная функция). Лисп считает, что это вызов функции a с параметрами b и c.

А вот если записать

  > ' (a b c)

то результатом станет список (a b c).

   > (quote 123)
   123

Доступ к элементам списка

В Лиспе есть две важные функции FIRST (ранее называлась CAR) и REST (ранее называлась CDR), которые возвращают, соответственно, самый первый элемент списка-аргумента (этим элементом может быть и атом, и список), и список, у которого первый элемент отброшен.

Например:

  > (first ' (a))
   a

Не забываем, что в Лиспе любой список по умолчанию считается функцией, поэтому выражение (first (a)) трактовалось бы как 1) вызов функции a без аргументов; 2) вызов функции first с параметром - результатом работы функции a.

Мы же хотим, чтобы список (а) трактовался как данные для обработки функцией FIRST, поэтому перед ним ставится кавычка (вызов функции QUOTE).

   > (first ' (a b))
   a

   > (first ' ((c d) a b))
   (c d)

В последнем случае первым элементом списка ((c d) a b) выступает не атом, а список (c d). Он и возвращается как результат.

Примеры использования REST:

   > (rest ' (a))
   ()

Отбрасываем элемент a из списка (а) - остается пустой список ().

   > (rest ' (a b))
   (b)

   > (rest ' ((c d) a b))
   (a b)

Путем комбинирования этих двух функций мы можем получить доступ к любому элементу списка. Например, доступ к третьему элементу списка (1 2 3 4 5) может быть записан так:

   > (first (rest (rest ' (1 2 3 4 5))))
   3

Это уже достаточно типичное выражение Лиспа, которое обычно заканчивается кучей скобок :) Вычисление начинается из глубины (обратите внимание, что QUOTE используется только перед обрабатываемым списком, а другие списки работают как вызовы функций). Сначала считается

  (rest ' (1 2 3 4 5)) = (2 3 4 5)

Далее этот результат (уже автоматически считающийся как данное) поступает на вход следующей функции:

   (rest ' (2 3 4 5)) = (3 4 5)

Наконец, из этого промежуточного списка выбирается первый элемент:

   (first ' (3 4 5)) = 3

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

Продолжение следует.

Задание Л1.

С помощью только двух функций first и rest организуйте доступ к каждому АТОМУ (не элементу) следующего списка:
(1 (2 3) (4 (5 6) 7) (8 (9 10) ) )

Некоторые элементы - списки, поэтому их надо "раскручивать" отдельно :)

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

Подсказка :) Добираемся до атома 9 :

   (first (first (rest (first (rest (rest (rest ' (1 (2 3) (4 (5 6) 7) (8 (9 10) ) ) )))))))

Удивительно наглядно, правда? (( : )) Но не волнуйтесь, это классический Лисп, а в прикладной среде есть множество вспомогательных функций, упрощающих подобные манипуляции. Но изучить НА ПРАКТИКЕ базовые принципы использования CAR/CDR необходимо!

СуперУм

Задание Л2.

Кстати, мощное и еще более полезное упражнение для развития мышления (не будем пока касаться вопросов когнитивной психологии :) - написать на Паскале/Си (впрочем, можно и на Лиспе :) программу, которая автоматически генерирует на выходе текст подобный тексту из подсказки. На входе - список и номер атома, на выходе - разбирающий его текст на Лиспе.

Но есть и еще, более мощное :) упражнение. Его под силу выполнить, наверное, одному человеку из миллиона (я не могу :). Если предыдущее упражнение может сделать 0,1% людей, то следующее - 0,1% от этого 0,1%. Это уже будет объективный признак гениальности.

Надо написать программу, которая получает на вход настройки универсальных функций CAR/CDR. CAR выделяет не первый, а в общем случае N-й элемент, а CDR соответственно выдает список без N-го элемента. Это N и задается в качестве параметра.

Программа, получая на входе значение N, автоматически генерирует исходный текст (например, на Паскале), соответствующий заданию Л2 - на входе список и номер M. Этот сгенерированный исходный текст выдает на своем выходе исходный текст на Лиспе доступа к M-у элементу списка по правилам универсальных CAR/CDR (с доступом к N-му элементу, N уже задано).

Кстати, необязательно код на конкретном языке. Достаточно словесный пошаговый алгоритм.

Задача ясна? :)

У кого получится, присылайте ответы! При этом желательно сопроводить ответ краткими описаниями и комментариями этого процесса (рефлексией).

(c) 2004-2007 Сергей Бобровский : bo собака russianenterprisesolutions.com

Школа программирования с нуля
Все предыдущие выпуски базового курса всегда тут:
http://www.infiltration.ru/p/

Неофициальный сайт поддержки (со срочными вопросами - сюда):
www.prog-begin.net.ru.

Мои книги (учебные курсы) "Технологии Delphi / C++ / C#. Разработка приложений для бизнеса".
http://shop.piter.com/display.phtml?a_id=17681&web_ok=all

Все эти учебные курсы рассчитаны не только на разработчиков, но и на всех тех, кто хочет стать ИТ-менеджером. Для этого как минимум нужно иметь общее представление о современных технологиях разработки и их истории и владеть соответствующей терминологией.
В книгах описаны десятки технологий, каждой из которых посвящены отдельные книги. Таким образом, купив один учебный курс, вы существенно сэкономите :) В книгах полностью описаны:
- Delphi (версия 2006, полностью совместимая с Delphi 2005/2006/2007 и Turbo Delphi) для обеих платформ - Win32 и .NET;
- C# (новый язык Microsoft, на котором базируется платформа .NET и все новые версии Windows);
- C++ для платформы Win32.
Охвачены также темы работы с файлами на этих платформах, создания файл-серверных, клиент-серверных, распределенных приложений, веб-программ (Indy, ASP.NET, веб-сервисы). Описаны языки SQL и OCL. Немало глав посвящены истории программирования и различных технологий. Особое внимание уделено созданию программ с помощью технологии ECO и языка моделирования UML - программы фактически рисуются, и теперь даже для создания корпоративных приложений и их переноса в Интернет не обязательно знать программирование!
Отдельная часть отведена технологиям организации групповой работы, управления требованиями, контроля версий, локализации и тестирования.
Тут подробнее про книги.

Мои книги, которые пока доступны в продаже:

Дизайн рассылки: Алексей Голубев - Web-дизайн и web-программирование
В избранное