Доброго времени суток, случайные и не случайные читатели.
Сегодня хочу рассказать о модификации конструкции 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)))
Думаю, данная версия макроса в дальнейшем будет претерпевать
изменения -- к примеру, можно добавить поддержку =>
выражений. Но это уже другая история.
- Артём
