newLISP для программистов

Эта статья адресована программистам на "традиционных" процедурных и объектно-ориентированных языках. Ее цель - показать некоторые удобные приемы программирования, обычные для функционального языка LISP, но редко используемые в других языках.

ЛИСП - это целое семейство диалектов, наиболее известным и признанным среди которых является Common LISP. Однако, основой для этой статьи послужил упрощенный диалект newLISP, интрепретатор которого работает в любой операционной системе и который можно использовать для "повседневных задач" на уровне языка Perl. Различия между newLISP и Common LISP в рамках излагаемого материала абсолютно не существенны.

О том, где взять дистрибутив newLISP написано в последней главе.

Итак... попробуем!

Для чего нужен ЛИСП?

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

(1 2 "abc" var (34 "w"))

Ассоциативный список - это "список списков", в которых первый элемент используется как ключ для поиска:

((ключ1 значение1_1 значение1_2) (ключ2 значение2_1 значение2_2) .....)

(Как?
  (читать лисп-программу))

f1(x, y)

(f1 x y)

f1(x, f2(y, z))

(f1 x (f2 y z))

1 + 2 -> 3

(+ 1 2) -> 3

Скажете "Неудобно!"? - Тогда посмотрите на это:

(+ 1 2 3 4 5) -> 15

Как вычисляется ЛИСП-выражение?

(+ 10 (sqrt 25)) -> 15

Несколько полезных примеров:

(setq a "test") -> "test"

a -> "test"

(setq b (sqrt 25)) -> 5

(setq b '(sqrt 25)) -> (sqrt 25)

(setq b (quote (sqrt 25))) -> (sqrt 25)

(setq b '(("first" 1) ("second" 2) ("third" 3)))
  -> (("first" 1) ("second" 2) ("third" 3))

(b 1) -> ("second" 2)

(1 b) -> (("second" 2) ("third" 3))

(0 2 b) -> (("first" 1) ("second" 2))

(assoc "second" b) -> ("second" 2)
(lookup "second" b) -> 2
(lookup "second" b 0) -> "second"
(lookup "second" b 1) -> 2

(К-чему?
  (все
    (эти скобки)))

Ответ лежит на поверхности: Вы, вероятно, уже обратили внимание на внешнее сходство ЛИСП-списков и ЛИСП-выражений. Действительно, ЛИСП-выражение синтаксически является ЛИСП-списком. Более того, оно может обрабатываться как обычный список - храниться в переменных, подвергаться преобразованиям, передаваться параметром функции в виде списка, и, конечно же - выполнятся!

Это - одно из основополагающих свойств ЛИСПа - использование кода, как данных.

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

(setq x 0 y 0) ; инициализация позиции

(define (up moves) (dec 'y moves))
; определение функции с именем "up", параметром "moves", которая уменьшает
; значение символа "y" на величину "moves"

(define (down moves) (inc 'y moves)) ; аналогично
(define (left moves) (dec 'x moves))
(define (right moves) (inc 'x moves))

(setq doings (list up down left right))
; всего лишь список символов - только что определенных функций ;-)
; функция list - создает список

(seed (date-value)) ; инициализируем датчик случайных чисел

; непосредственно выржение перемещения
(dotimes (i 100)
 ((doings (rand 4)) (rand 5))
 (println x ":" y))

(dotimes (i 100) выражение1 выражение2 ...) - вычисляет "выражения" 100 раз, при этом символ "i" принимает значения от 0 до 99.

(rand 4) - генерирует случайное целое в диапазоне от 0 до 3.

(doings (rand 4)) - эта форма была описана в предыдущей главе, как "получение элемента списка по индексу". Соответственно: "doings" - список, а "(rand 4)" служит индексом.

Здесь стоит посмотреть на список doings более внимательно:

doings ->
  ((lambda (moves) (dec 'y moves))
   (lambda (moves) (inc 'y moves))
   (lambda (moves) (dec 'x moves))
   (lambda (moves) (inc 'x moves)))

Возможно, у вас возник вопрос: а как же имена - "up", "down", "left" и "right"? На самом деле, эти имена всего лишь символы-переменные, которым присвоены в качестве значений соответствующие лямбда-списки:

up -> (lambda (moves) (dec 'y moves))
(up 1) -> -1            ; происходит вызов функции с параметром 1
(nth 0 up) -> (moves)   ; поскольку implicit indexing здесь не работает,
                        ; используем функцию nth для получения 0-го элемента
(setq up-new up)
up-new -> (lambda (moves) (dec 'y moves))
(up-new 1) -> -2        ; было -1, уменьшаем еще на единицу...

(define (up moves) (dec 'y moves))
(setq up '(lambda (moves) (dec 'y moves)))

((doings (rand4)) (rand 5)) - поскольку элемент списка "doings" - это функция, мы можем использовать ее как обычный вызов функции - т.е., подставить в ЛИСП-выражение вместо имени функции. Соответственно, случайное число (rand 5) будет аргументом функции.

(println выражение1 выражение2 ...) - печатает на экран результаты вычисления выражений-аргументов, завершая их переводом строки. Кроме того, функция "println" возвращает в качестве результата значение вычисления последнего выражения-аргумента.

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

.....
(setq doings '(up down left right))
.....
(dotimes (i 100)
 (apply (doings (rand 4)) (list (rand 5)))
 (println x ":" y))

Возможности, подобные описанным частично и рудиментарно присутствуют в процедурных языках, однако они используются, в основном, Очень Крутыми Программистами в минуты отчаяния. Чтобы сделать их более дружественными, в процедурные языки пришлось добавить ООП, которое, в свою очередь, потребовало раздутых объектных декомпозиций и внесло порядочную неразбериху в освоение программирования.

Однако в ЛИСПе использование кода как данных является "повседневной" практикой, применяемой при любой необходимости (а также и вовсе без оной ;-).

В завершение главы - пару слов об ООП в ЛИСП:
В языке Common LISP система объектно-ориентированного программирования (CLOS) реализована как обычная библиотека, написанная на том же Common LISP - без каких-либо изменений самого языка.
В языке newLISP для программирования с объектами предлагается встроенная система "контекстов" ("context") - изолированных пространств имен, реализующих основные принципы ООП в форме, максимально приспособленной для быстрого "скриптинга".

Исключения, подтверждающие правила.

(define (test1 arg) (println arg))
; определим обычную функцию
(tes1 (+ 1 2)) -> 3
; и испробуем...

(define-macro (test2 arg) (println arg))
; теперь определим "необычную" макро-функцию
(test2 (+ 1 2)) -> (+ 1 2)
; и испробуем...

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

Функция "quote" является простейшей макро-функцией. Если бы она отсутствовала в языке, ее можно было бы определить так:

(define-macro (quote a) a)
; функция принимает один аргумент
; и возвращает его в неизменном виде (без вычисления) в качестве результата.

Если вы передаете аргументом макро-функции ЛИСП-выражение, то это выражение само по себе и будет доступно в качестве переменной при вычислении вызываемоой макро-функции. Если вы захотите его вычислить, вам понадобится функция "eval":

(define-macro (test3 arg) (println (eval arg)))
(test3 (+ 1 2) -> 3

(define-macro (my-if condition result-true result-false)
  (let (_c (eval condition))
    (and _c (eval result-true))
    (or _c (eval result-false))))

(my-if (= 1 1) (println "ture") (println "false")) -> "true"
(my-if (= 1 2) (println "ture") (println "false")) -> "false"

(let (символ1 выражение-значение1 символ2 выражение-значение2 ...)
  выражение-действие
  выражение-действие
  ....)

Функции "and" и "or" - логические и действуют по очевидной схеме:
Для "or" - если первое выражение ложь, вычисляется второе и т.д., возвращается результат первго истинного выражения.
Для "and" - соответственно.

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

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

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

Немного об условных вычислениях.

Основа логических вычислений, двоичная логика, построена на значениях "истина" и "ложь". В newLISP в качестве значения "ложь" используется символ "nil". Второе назначение этого символа - "пустое" значение, которое имеют не инициализированные символы.

Все остальные значения в newLISP трактуются как "истина" (в т.ч., 0, пустая строка и пустой список). Для удобства написания программ в newLISP имеется также специальный символ "true" - его могут возвращать некоторые логические функции.

(if условие выражение
    условие выражение
    ....
    иначе-выражение)

Обратите внимание, что "выражением" может быть только одиночное выражение:

(if вправо (+ x 1))

(if вправо-вниз (begin
                  (+ x 1)
                  (+ y 1)))

Обратите внимание, что в примере использованы "кириллические" имена символов "вправо" и "вправо-вниз" - в ЛИСПе это допустимо.

Альтернативный вариант функции "if" - функция "cond":

(cond (условие выражения)
      (условие выражения)
      ...)

И, наконец, венец функций условного ветвления - функция "case":

(case символ
  (тестовая-константа выражения)
  (тестовая-константа выражения)
  ...
  (true выражения))

(define (translate n)
  (case n
    (1 "one")
    (2 "two")          
    (3 "three")
    (4 "four")
    (true "Can't translate this")))

(translate 3)  -> "three"
(translate 10) -> "Can't translate this"

Теперь, с помощью функции "translate" численное значение может быть преобразовано в слово-числительное.

Следует отметить, что у функции "case" есть особеннось: "тестовые константы" - это именно константы, они не могут быть вычисляемыми выражениями. Т.е., данная запись синтаксически допустима, но не принесет желемого результата:

(case n
  (a "n равно знчению a")
  ((+ a 1) "n на единицу больше значения a"))

Но как быть, если удобство важнее? Очень просто - написать свой макрос:

(define-macro (ecase _v)
  (eval (append
          (list 'case _v)
          (map (fn (_i) (set-nth 0 _i (eval (_i 0))))
               (args)))))

(setq a 1 n 2)
; присваиваем a=1, n=2

(ecase n
  (a "n равно знчению a")
  ((+ a 1) "n на единицу больше значения a"))

  -> "n на единицу больше значения a"

Текст данного макроса пока что немного сложен - он станет понятен после глав "Преобразование списков" и "Анонимные функции".

Такая "неудобная" функцональная запись.

a = 1 + 2;

(setq a (+ 1 2)) -> 3

(setq a (+ 1 2 3 4 5)) -> 15

(setq l '(1 2 3 4 5)) -> (1 2 3 4 5)

l -> (1 2 3 4 5)

(define-macro (my-apply fun lst)
  (eval (cons fun (eval lst))))

(my-apply + l) -> 15

(setq a (apply + l)) -> 15

(define (average) (div (apply add (args)) (length (args))))
  -> (lambda () (div (apply add (args)) (length (args))))

(apply average l) -> 3

(define (f x y) (println "x=" x " y=" y " args=" (args)))
  -> (lambda (x y) (println "x=" x " y=" y " args=" (args)))

(f 1 2 3 4) -> x=1 y=2 args=(3 4)

Анонимные функции.

Одним из наиболее замечательных встроенных экземпляров является функция "map".

(map pow '(1 2 3 4)) -> (1 4 9 16)
; pow - возведение в квадрат

(map first '((1 2 3) (4 5 6) (7 8 9))) -> '(1 4 7)
; first - возвращает первый элемент списка

(define (third lst) (lst 2))
; функции "third" в языке нет

(map third '((1 2 3) (4 5 6) (7 8 9))) -> '(3 6 9)

(map (fn (lst) (lst 2))
     '((1 2 3) (4 5 6) (7 8 9))) -> '(3 6 9)

(define (third lst) (lst 2)) -> (lambda (lst) (lst 2))
; кроме того, символ "third" получил значение - этот же лямбда-список

(fn (lst) (lst 2)) -> (lambda (lst) (lst 2))
; только лямбда список в результате; никакого дополнительного эффекта

Мы уже видели подобную технику в главе "(К-чему? (все (эти скобки)))", только в ее примерах использовалась не функция-конструктор "fn", а непосредственно готовый лямбда-список, защищенный символом апострофа:

(fn (lst) (lst 2)) -> (lambda (lst) (lst 2))
'(lambda (lst) (lst 2)) -> (lambda (lst) (lst 2))

Преобразование списков.

(setq a 25)
(list 1 2 3 a) -> (1 2 3 25)

(append '(1 2 3) '(4 5 6)) -> (1 2 3 4 5 6)

(cons 1 '(2 3 4)) -> (1 2 3 4)
(cons '(1 2) '(3 4)) -> ((1 2) 3 4)

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

; (filter тестовая_функция список)

(filter (fn (x) (not (empty? x))) '("abc" "" "def" "jhi" ""))
  -> ("abc" "def" "jhi")

Обратной по действию является функция "clean":

(clean empty? '("abc" "" "def" "jhi" "")) -> ("abc" "def" "jhi")

(join '("abc" "" "def" "jhi") ":") -> "abc::def:jhi"
(join '("abc" 123 "def" "jhi") ":") -> Ошибка! - 123 не является строкой
(join (map string '("abc" 123 "def" "jhi")) ":") -> "abc:123:def:jhi"

И, конечно, самой "чудесной" является рассмотренная в предыдущей главе функция "map". В дополнение скажем, что она может обрабатывать несколько списков.

(map (fn (x y) (+ x y)) '(1 2 3 4) '(5 6 7 8)) -> (6 8 10 12)

(map + '(1 2 3 4) '(5 6 7 8)) -> (6 8 10 12)

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

Самодостаточные функции.

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

Функциональная запись.

Разработка снизу - вверх.

В ЛИСПе, благодаря его свойствам мета-языка, все делается наоборот. Для решения задачи исследуется предметная область и на основе возможностей ЛИСПа создается новый язык. Затем на этом языке записывается решение требуемой задачи. Если "вдруг" выясняется, что первоначальный план претерпел существенные изменения, не беда - на уже готовом языке несложно записать и что-то новое. Этот способ называется разработкой "снизу-вверх".

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

Самодокументирование.

Не лишайте себя возможности писать так:

(do-select ((CustomerName CustomerEmail)
            :from Customers
            :where (> CustomerAge 100))
  (send-email CustomerEmail
              :subject "Congratulations!"
              :body (format nil
                            "Dear ~A, you won a prize! Call ~A."
                            CustomerName company-phone)))

Обработка списков.

Форматирование кода.

Отступы.

Отступ для вложенных списков данных - один пробел (поскольку открывающие скобки на предыдущей строчке могут следовать одна за другой).

Если у функции много аргументов и первый находится на одной строке с именем функции, остальные аргументы удобно писать под первым "в столбик" (как в предидущем примере).

Для специальных функций, вроде "let" или "if", у которых первый параметр имеет особое значение, первый параметр обычно начинают на одной строке с именем функции, а остальные - на других строках со стандартным отступом в два пробела:

(if (= a b)
  (println "равенство")
  (println "неравенство"))

Закрывающие скобки.

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

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

Практический скриптинг.

Для тех же задач неплохо подходит и newLISP. Этот язык также поддерживает Perl-совместимые регулярные выражения PCRE и позволяет производить разбор текстовых документов. Особенностью применения newLisp является его ориентация на обработку списков (в то время, как стиль Perl тяготеет к потоковой обработке). Это означает, что используя newLisp, обычно выгоднее не обрабатывать отчет строчка - за строчкой, а прочитать его весь, разделить на список, состоящий из его частей (строк, слов в строках) и затем обработать, используя всю мощь ЛИСПа.

Для примера, рассмотрим простую задачу: Предположим, в файле "report.txt" вы имеете отчет вида:

+----------------------------+
|  Пример текстового отчета  |
+----------------------------+
| uid     | balance | volume |
+----------------------------+
| user1   | 100000  | 1000   |
| user2   | 200000  | 1234   |
........

(apply +
  (map (fn (x) (int (x 3) 10))
       (filter (fn (x) (and (> (length x) 3) (regex "^[0-9]+$" (x 3))))
               (map (fn (x) (parse x " *\\| *" 0))
                    (parse (read-file "report.txt") "\n")))))

Чтобы разобраться, как это работает, запишем то же, но более аккуратно:

(define (split-report-line str)
  (map (fn (x) (parse x " *\\| *" 0))
       str))

(define (line-has-data? lst)
  (and (> (length lst) 3) (regex "^[0-9]+$" (lst 3))))

(apply +
  (map (fn (x) (int (x 3) 10))
       (filter line-has-data?
               (map split-report-line
                    (parse (read-file "report.txt") "\n")))))

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

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

В завершение - несколько слов о возможностях языка newLISP.

Не смотря на свой миниатюрный размер - один бинарный файл размером менее 200к, в newLISP встроены такие возможности, как:

• TCP/IP, возможость работы сетевым демоном и поддержка HTTP
• Порождение процессов, семафоры, сигналы, таймеры
• Вызов функций из динамических библиотек (.so, .dll и т.д.)
• Регулярные выражения PCRE
• XML-парсер
• Интерфейс к TCL/Tk (Windows-дистрибутив включает графическую библиотеку Tk)
• Система унификации (unify), позволяющая реализовать Пролог-подобную логику
• Байесовские классификаторы (с применением доп. библиотеки из дистрибутива)
• Поддержка Unicode
• Множество математических функций

Среди документации следует особо выделить чрезвычайно полезные "официальные" документы:
"newLISP Manual and Reference" - справочник по языку и
"newLISP Design Patterns" - описание приемов программирования задач из всех основных областей применения языка.

Сайт автора данного опуса располагается по адресу http://en.feautec.pp.ru. На нем можно найти несколько полезных библиотек и неофициальный репозитарий пакетов Debian (для дистрибутивов sarge и etch).

БЛАГОДАРНОСТИ

Alex-у с форума newLISP Fan Club за комментарии по стилистике.

ЛИЦЕНЗИЯ

Допускается любая модификация текста при выполнении условий:
- отражения факта модификации в строке с номером версии в начале документа,
- извещения автора по e-mail, указанному в Copyright документа,
- безусловного согласия на включение любых фрагментов произведенных изменений в оригинальную версию документа (с отражением авторства в разделе "Благодарности").

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