Отправляет 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 за неделю
←   Все выпуски   →

Программирование с нуля - это совсем просто! 178) Функциональное программирование и Лисп : Рекурсия-2


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

178) Функциональное программирование и Лисп : Рекурсия и последовательные вычисления

Последний выпуск по Лиспу, был N 175.

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

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

(PROG (переменные) операторы )

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

В современных реализациях Лиспа, и в частности в newLisp, нету явного разделения между механизмом лямбда-вычислений и последовательным выполнением "обычных" операторов.

В качестве примера рассмотрим программу, суммирующую первые 100 целых чисел. Оператор присваивания в Лиспе выглядит так:

(setq переменная выражение)

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

(setq x 1)
(setq x (+ 2 2))

Существует расширенный вариант этого оператора - set. В нем в левой части ставится не атом (имя переменной), а выражение, которое сначала вычисляется, и лишь потом атому, получившемуся в ходе такого вычисления, присваивается значение правой части:

   (set (first '(x)) (+ 2 2))

Здесь сначала вычисляется выражение (first '(x)) , равное атому x, и затем этому атому присваивается значение 4. В простейшем случае:

   (set 'x 4)

Условный оператор цикла записывается следующим образом:
(while выражение тело)
Тело вычисляется, пока значение выражения не равно nil.

Оператор цикла со счетчиком выглядит так:
(for (счетчик начальное-значение конечное-значение шаг условие-прекращения-цикла) тело)
Шаг и условие прекращения цикла можно опускать.

Тело цикла, как правило, заключают в логические скобки (блок). Для этого используют функцию begin:
(begin тело)

Вывод строки на консоль newLisp выполняет функция print:
(print последовательность-выражений)
Перевод на новую строчку обозначается строкой "\n".

Тогда всю программу суммирования целиком запишем так:

   (define (summ)
    (set 'SUM 0)
    (for (N 1 100)
     (begin
       (set 'SUM (+ SUM N))
  )))
  (summ) ; это сам вызов функции summ

Этот текст прозрачен - в цикле происходит суммирование значений счетчика N, от 1 до 100. Вызов этой функции напечатает на консоли ее результирующее значение - 5050. Это значение - значение последнего вычисленного выражения, коим будет оператор присваивания

    (set 'SUM (+ SUM N))

Когда он вызовется в сотый раз, в переменную SUM занесется число 5050, которое и станет значением всей функции.

А вот в истинно "лисповском", рекурсивном духе, данный код запишется примерно так:

  (define (SUM100 N CURSUM)
   (cond
    ((<= N 100) (SUM100 (+ N 1) (+ CURSUM N)))
    ((> N 100) (print "Sum= " CURSUM)))
  )
  (SUM100 1 0)

С точки зрения классического программиста, данный код конечно менее нагляден и понятен. Но для Лисп-программиста главное, что он рекурсивен. Функция SUM100 имеет два параметра - N (счетчик - цикла в линейном варианте, или глубины рекурсии в данном коде), и CURSUM - текущее значение рассчитанной суммы. Пока мы не опустились рекурсивно вглубь на 100 вызовов - это проверяет условная функция cond, функция SUM100 вызывает собственную копию с новыми параметрами: увеличенным на единичку значением счетчика и увеличенным на N значением общей суммы. Когда нужная глубина достигнута, печатается результат. Исходный вызов - SUM100 с параметрами: счетчик = 1 (текущая глубина вызова), а текущая сумма = 0.

Вот на тему схожести языков программирования письмо от Максима:

Решил попробовать задачу Л2 написать на Лиспе.
Краткий алгоритм функции find_gen:
0) Если список, переданный функции совпадает с нужным атомом, то выход.
1) Ищем нужный атом.
2) Если не нашли, то ищем “(* Atom *)”. Т.е. ищем вложенный список с нужным атомом.
3) Если снова не нашли, то ищем “(* (* Atom *) *)”. Повышаем степень вложенности списка, пока не найдем нужный список с нашим атомом.
4) Генерируем код, для выбора найденного списка из изначального.
5) Исполняем код и передаем результат функции find_gen (рекурсия)
Вот код на Лиспе:

  (define (find_gen str atom)
   (begin
      (if (!= str atom)
       (begin
       (set ' fstr atom)
       (set ' depht 1)
       (set ' N 1)
       (while (= nil
         (if (= depht 1)
          (set ' N (find fstr str))
          (set ' N (find fstr str match))))
        (begin
         (set ' fstr (list ' * fstr ' *))
         (inc ' depht)))
       (set ' gs "(first ")
       (dotimes (i N)
        (begin
         (set ' gs (append gs "(rest "))))
       (set ' result (append gs result))
       (set ' gs (append gs " ' " (string str)))
       (dotimes (i (+ N 1))
        (begin
         (set ' gs (append gs ")"))
         (set ' result (append result ")"))))
       (find_gen (eval-string gs) atom)))))

Функция запускающая find_gen:

  (define (gen str atom)
   (begin
   (set ' result (append "'" (string str)))
   (find_gen str atom) result))

Язык Лисп оказался не таким сложным, как показалось при первом взгляде на него. Все те же 5 основных элементов языка программирования:
1) Переменные
2) Массивы
3) Оператор ветвления if
4) Оператор цикла
5) Подпрограммы

Причем понятие массива в Лиспе сливается с понятием переменной.
Еще Лисп очень похож на язык Forth.
Например запись в Лиспе:

  (set 'x (+ a b))

И запись в Форте:

  a @ b @ + x !
  @ - прочитать значение переменной
  ! - записать в переменную последний результат (вершину стека)

После изучения 3-4 языков программирования все следующие изучаются за несколько дней. Похоже что это случилось и со мной. :) Когда уже неважно на чем писать только «дайте пример программы и скажите что писать». :)

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

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

Изучать разные языки программирования имеет смысл с двумя целями:
а) получить навыки быстрого и эффективного создания программ на языках, которые массово востребованы (С++, Delphi, C#, Java, PHP), хотя, быть может, эти языки отнюдь не самые лучшие;
б) как следует познакомиться с оригинальными механизмами управления (например, рекурсией) и приемами реализации алгоритмов из лучших в своем классе языков, чтобы затем перенести такой опыт в свою практику на конкретном языке. Ведь и Си, и Паскаль рекурсию тоже поддерживают, однако в полной мере мощь и красоту этого механизма можно понять прежде всего на примере Лиспа.

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

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

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

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

Мои книги (учебные курсы) "Технологии Delphi / C++ / C#".
http://shop.piter.com/publish/authors/17681/191180213/

Все эти учебные курсы рассчитаны не только на разработчиков, но и на всех тех, кто хочет стать ИТ-менеджером. Для этого как минимум нужно иметь общее представление о современных технологиях разработки и их истории и владеть соответствующей терминологией. Именно это мои книги и дают.
В учебных курсах описаны десятки технологий, каждой из которых посвящены отдельные книги. Таким образом, купив один учебный курс, вы существенно сэкономите :) В книгах полностью описаны:
- 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-программирование
В избранное