Создание расширенной версии оператора case с помощью макросов Lisp

Доброго времени суток, случайные и не случайные читатели.

Сегодня хочу рассказать о модификации конструкции case в Scheme для того, чтобы она использовала переданный пользователем предикат для сравнения. Решение основано на макросах... но обо всём по-порядку.

Описание работы case

Во-первых, как работает case ? Несложно догадаться, case является одной из управляющих конструкций, которые выполняют работу по принятию решений (англ. case analysis), выбирая "путь", по которому должна пойти программа, в зависимости от переданного им выражения.

В общем виде, синтаксис case выглядит так:

case ключевое-выражение условие-1 условие-2 ...

Каждое из условий должно содержать список из одного или нескольких элементов данных, за которым должно быть одно или несколько выражений для исполнения:

(case ключевое-выражение
  ((элемент-данных ...) выражение-1 выражение-2 ...)
  ...)

Используя специальный оператор =>, можно вызвать выражение (процедуру) в условии со значением ключевого выражения:

(case ключевое-выражение
  ((элемент-данных ...) => выражение))

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

((lambda (параметр)
   ...)
 значение-ключевого-выражения)

Так же case позволяет использовать else в конце списка условий, для случаев, когда ни одно из условий не было удовлетворено:

(else выражение-1 выражение-2 ...)

Конструкция с => также допустима:

(else => выражение)

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

(case (+ 2 3)
  ((5)
   (display "Привет мир!")
   (newline))
  (else
   (display "С миром что-то пошло не так.")
   (newline)))

Как всё это работает? Сначала case вычисляет первый аргумент (выражение; в данном случае, (+ 2 3)), после этого сравнивает полученный результат с каждым условием. Условие состоит из списка значений для сравнения и выражения (последовательности выражений) к выполнению при совпадении результата с одним из элементов данных. Сравнение производится через предикат eqv?.

Попробуем выполнить выражение выше (-| показывает побочный эффект от вычисления выражения, в данном случае, печать строки):

(case (+ 2 3)
  ((5)
   (display "Привет мир!")
   (newline))
  (else
   (display "С миром что-то пошло не так.")
   (newline)))
-| Привет мир!

Как и ожидалось, выводится строка "Привет мир!". Но что делать, если нам нужно сравнить результат вычисления ключевого выражения со, скажем, списоком строк? Попробуем это сделать обычным case.

Использование case для перебора строк

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

(case *цвет*
  (("оранжевый")
   (display "апельсин")
   (newline))
  (("красный" "зелёный")
   (display "яблоко")
   (newline))
  (else
   (display "банан")
   (newline)))

Разумеется, компьютеры (пока) не умеют удивляться, когда им подсовывают для исполнения подобный код, однако в остальном мы уловили суть. Переменная *цвет* может быть задана до выполнения case следующим образом:

(define *цвет* "оранжевый")

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

(eqv? "яблоко" "яблоко")
=> #f

Что же это? Результатом булева выражения оказалась "ложь" (#f), несмотря на то, что с нашей точки зрения строки идентичны! Посмотрим, в чём дело.

С точки зрения реального мира подобный ответ корректен, так как переданные eqv? яблоки (то есть, строки) являются разными объектами (хранятся в разных областях памяти), хотя и выглядят одинаково. В реальном мире два яблока, как бы они не были внешне похожи, являются разными объектами.

Если же мы объявим переменную, в которую сохраним яблоко (то есть, строку "яблоко", конечно же), и объявим ещё одну переменную, присвоив ей значение первой переменной, то при сравнении этих переменных мы получим истину (#t):

(define *фрукт1* "яблоко")
(define *фрукт2* *фрукт1*)
(eqv? *фрукт1* *фрукт2*)
=> #t

Та-да! Эти переменные равны, так как ссылаются на один и тот же фрукт (одну и ту же область памяти, которая хранит строку "яблоко").

Поиск правильного инструмента сравнения

Очевидно, что eqv? не подходит в данном случае для сравнения строк, поскольку по мнению eqv? две строки различаются, если являются разными объектами, даже если они состоят из одинакового набора символов. Мы должны использовать правильный способ сравнения объектов, чтобы получить желаемый результат. В данном случае, строки должны сравниваться лексикографическим способом, тогда две строки одинаковой длины, с одинаковым набором символов, расположенных в одинаковом порядке, будут идентичны. Это может сделать предикат string=?:

(string=? "яблоко" "яблоко")
=> #t

Как раз то, что нужно. Осталось научить case использовать string=? для сравнения. Это можно сделать, добавив в язык программирования новую конструкцию -- назовём её case-pred. Сложно, разве нет? Оказывается, что не так уж и сложно, когда знаешь лисповые макросы.

Пишем код, который пишет код, который пишет код, который ...

Для реализации case-pred можно использовать другую управляющую конструкцию, cond. То есть, мы объявим наш case-pred таким образом, что после развёртки макроса он будет превращаться в корректную конструкцию cond, которая и будет выполнять всю работу.

Конструкция cond, так же, как и case, состоит из набора условий, но не привязана к конкретному ключевому выражению. В общем виде синтаксис выглядит так:

cond условие-1 условие-2 ...

где каждое из условий представляет собой:

(тест выражение-1 выражение-2 ...)

Выражения вычисляются тогда, когда тест возвращает не-ложь (не #f). Наш "фруктовый" пример кода, переписанный вручную с использованием cond:

(cond
  ((string=? *цвет* "оранжевый")
   (display "апельсин")
   (newline))
  ((or (string=? *цвет* "красный")
       (string=? *цвет* "зелёный"))
   (display "яблоко")
   (newline))
  (else
   (display "банан")
   (newline)))

Теперь осталось написать код, который будет писать код, который будет делать то, что нам нужно.

Что мы хотим получить в итоге, так это макрос case-pred, который принимает первым аргументом предикат, который используется для сравнения результата ключевого выражения со списком условий. В остальном, макрос должен работать так же, как и обычный case.

Макросы во всей красе

Наш первый вариант макроса case-pred использует классический лисповый макрос, объявляемый через define-macro:

(define-macro (case-pred pred key . clauses)
  `(cond
    ,@(map
       (lambda (clause)
         (let ((datum (car clause))
               (exp   (cadr clause)))
           (cond
            ((and (not (list? datum)) (not (eq? datum 'else)))
             (error "Syntax error: expected a list" datum))
            ((eq? datum 'else)
             `(else ,exp))
            ((= (length datum) 1)
             `((,pred ,key ,(car datum)) ,exp))
            (else
             `((or ,@(map (lambda (o) `(,pred ,key ,o))
                          datum)) ,exp)))))
       clauses)))

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

`(cond ,@(map ...)) как раз возвращает нужный список. Как можно прочитать в документации, оператор quasiquote, в краткой форме обозначаемый знаком грависа ("`"), позволяет создать цитированный (англ. quoted) список, части которого могут быть вычислены. Те части, которые должны быть вычислены, помечаются с помощью операторов unquote (в краткой форме -- ",") и unquote-splicing (в краткой форме -- ",@"). unquote вычисляет выражение и вставляет результат в список. unquote-splicing также вычисляет выражение, но подставляет в список элементы того списка, который был получен в результате вычисления "разкавыченного" выражения. Таким образом, ,@(map ...) возвращает список, элементы которого подставляются в другой список -- как тело cond.

Данный макрос не лишён недостатков -- к примеру, не описан оператор =>. Однако в остальном данная версия case-pred работает неплохо.

Но можем ли мы сделать эту запись короче и яснее? Ответ -- можем, используя define-syntax:

(define-syntax case-pred
  (syntax-rules (else)
    ((_ pred key ((datum ...) exp) ...)
     (cond
      ((or (pred key datum) ...) exp) ...))
    ((_ pred key ((datum ...) exp) ... (else else-exp))
     (cond
      ((or (pred key datum) ...) exp) ...
      (else else-exp)))))

В этой версии используется стиль макросов, предоставляемый GNU Guile. syntax-rules создаёт преобразователь синтаксиса, основанный на сопоставлении выражения с шаблоном, и переписывании данного выражения согласно шаблону преобразования.

К примеру, шаблон

    ((_ pred key ((datum ...) exp) ...)
     (cond
      ((or (pred key datum) ...) exp) ...))

совпадает с выражением следующего вида:

(case-pred string=? *цвет*
  (("оранжевый")
   (display "апельсин")
   (newline)))  

А шаблон

    ((_ pred key ((datum ...) exp) ... (else else-exp))
     (cond
      ((or (pred key datum) ...) exp) ...
      (else else-exp)))))

совпадает с

(case-pred string=? *цвет*
  (("оранжевый")
   (display "апельсин")
   (newline))
  (else
   (display "банан")
   (newline)))

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

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

(case-pred string=? *цвет*
  (("оранжевый")
   (display "апельсин")
   (newline))
  (("красный" "зелёный")
   (display "яблоко")
   (newline))
  (else
   (display "банан")
   (newline)))

После развёртки макроса мы получим примерно следующий код (который мы уже видели ранее):

(cond
  ((string=? *цвет* "оранжевый")
   (display "апельсин")
   (newline))
  ((or (string=? *цвет* "красный")
       (string=? *цвет* "зелёный"))
   (display "яблоко")
   (newline))
  (else
   (display "банан")
   (newline)))

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

- Артём

Макрос define-method* для использования ключевых слов совместно с GOOPS

Сегодня загрузил в репозиторий LazyCat коммит, который добавляет макрос, расширяющий стандартный набор функций GOOPS для создания методов. Макрос используется для реализации метода host-list-add-host в классе <host-list> и позволяет использовать ключевые слова (англ. keywords) для задания аргументов, передаваемых в метод. То есть, вместо создания методов с большим количеством параметров, или выдёргивания аргументов из списка по индексу, можно просто указывать каждый из аргументов по ключевому слову.

Текущая версия макроса выглядит так:

;; Needed modules
(use-modules (ice-9 optargs)
             (ice-9 syncase)
             (oop goops))

;; Macro definition
(define-syntax define-method*
  (syntax-rules ()
    ((_ (m (o <class>) (var defval) ...) body ...)
     (define-method (m (o <class>) . args)
       (let-keywords args #t ((var defval) ...)
                     body ...)))))

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

(define-class <talking-machine> ())

(define-method* (hey (obj <talking-machine>)
                     (say  "Hello, ") 
                     (name "J. Random Programmer"))
  (display (string-append say name "!\n")))

(define talking-machine (make <talking-machine>))

Результат вызова метода hey с разными аргументами:

(hey talking-machine)
=> Hello, J. Random Programmer!

(hey talking-machine #:say "Goodbye, ")
=> Goodbye, J. Random Programmer!

(hey talking-machine #:name "John Doe")
=> Hello, John Doe!

Данный макрос написан в процессе изучения макросов в GNU Guile -- может быть, данную задачу можно решить гораздо более простым и элегантным способом?

- Артём

Препроцессор C

Доброго времени суток, случайные и не случайные читатели.

На прошлой неделе, изучая код ядра Linux, я наткнулся на довольно занятный заголовочный файл. В файле объявлено два макроса и одна inline-функция. Заинтересовало же меня следующее: название одного из макросов совпадает с именем функции, равно как и набор их параметров. Я подумал -- как будет работать этот код? И решил провести эксперимент, как только появится свободное время.

На следующий день я вспомнил про этот файл -- и понял, что результат компиляции очевиден и без проведения эксперимента: достаточно вспомнить, как работает компилятор gcc.

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

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

После этого происходит компиляция, потом -- преобразование ассемблерного кода в машинный код и, наконец, линковка.

На этапе линковки можно увидеть (конечно же) ошибки линковки. Эти ошибки обычно сводятся к тому, что линковщику не удаётся найти в данных ему файлах функцию, на которую есть ссылка где-то в коде (undefined reference).

Если же всё прошло нормально, то в конце-концов мы получаем исполняемый файл.

Из этого алгоритма видно, что препроцессору, в общем-то, совершенно безразличны проблемы компилятора и, тем более, линковщика.

Посмотрим на примере.

Итак, допустим, у нас есть заголовочный файл и файл с исходным кодом -- назовём их test.h и test.c соответственно. Вот содержимое test.h:

 
#ifndef __TEST_H__ 
#define __TEST_H__

inline int function1(int param) 
{
 return param; 
}

#define function1(param) function1(param)

#endif /* ifndef __TEST_H__ */

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

А вот содержимое test.c:

 
#include <stdio.h> 
#include "macros.h"

int main(int argc, char *argv[])
{ 
 printf("Result of calling function1: %d\n", 
  function1(100));

 return 0;
}

Результат работы препроцессора можно увидеть, передав gcc ключ -E, вот так:

$ gcc -E test.c -o test.i

Не буду приводить здесь этот файл test.i полностью (он достаточно объёмен) -- посмотрим лишь на последние 15 строк:

 
$ tail -15 test.i 


inline int function1(int param)
{
 return param;
}
# 3 "test.c" 2

int main(int argc, char *argv[])
{
 printf("Result of calling function1: %d\n",
  function1(100));

 return 0;
}

Здесь мы видим, что в main() всё так же вызывается function1(), однако этот вызов был получен в результате работы препроцессора: он нашёл макрос function1, потом встретил имя function1 в main(), и подменил его результатом обработки макроса.

Попробуем сделать следующее: поменяем макрос function1() в test.h таким образом, чтобы он разворачивался в вызов несуществующей функции function2():

 
#define function1(param) function2(param)

Теперь, после работы препроцессора мы увидим следующую картину:

 
$ tail -15 test.i        


inline int function1(int param)
{
 return param;
}
# 3 "test.c" 2

int main(int argc, char *argv[])
{
 printf("Result of calling function1: %d\n",
  function2(100));

 return 0;
}

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

 
$ gcc test.c 
/tmp/ccUBRByP.o: In function `main':
test.c:(.text+0x19): undefined reference to `function2' collect2:
выполнение ld завершилось с кодом возврата 1

Из этого можно сделать интересный вывод: если у нас существует функция и макрос с одинаковым именем и набором параметров, то нам не удастся вызвать функцию напрямую -- её вызов прежде будет обработан препроцессором, который подставит в место вызова результат обработки макроса. Таким образом, функция может быть "скрыта" от компилятора, или подменена. Например, поменяв макрос следующим образом:

 
#define function1(param) 0

И скомпилировав программу, мы увидим следующее:

$ gcc test.c 
$ ./a.out 
Result of calling function1: 0

Мы получили ноль, несмотря на то, что передавали в функцию число 100, так как вызов функции был принят препроцессором за вызов макроса, и заменён на тело макроса -- то есть, на ноль.

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