Содержание


Bigloo — компилируемая модификация языка Scheme: Часть 2. Синтаксис и стандартная библиотека

Comments

Серия контента:

Этот контент является частью # из серии # статей:

Следите за выходом новых статей этой серии.

Этот контент является частью серии:

Следите за выходом новых статей этой серии.

Поскольку в основу Bigloo заложен язык программирования Scheme, в синтаксисе мы не обнаружим сколько-нибудь существенных различий. Ведь главная задача Bigloo — доводить scm-файлы до состояния объектных файлов, которые можно компоновать с другими модулями при создании программ. Тем не менее, некоторые особенности в Bigloo присутствуют, и мы их рассмотрим.

1. Обзор синтаксиса

Упомянутые выше особенности не ограничивают, а слегка расширяют функциональность компилятора Bigloo. Это касается дополнительной информации о типах и способах записи комментариев.

1.1. Информация о типе

Тип содержимого переменной определяется в тот момент, когда соответствующий ей идентификатор связывается с помощью конструкций lambda, let, define и т.п. Такие идентификаторы, содержащие информацию о типе, обозначаются, как "явно типизированные идентификаторы" (typed identifiers). Общая синтаксическая схема их определения:

<идентификатор> := <R5RS-идентификтор> | <типизированный_идентификатор>

где:

<типизированный_идентификатор> := <R5RS-идентификтор>::<R5RS-идентификтор>
<R5RS-идентификтор> — стандартный идентификатор языка Scheme

1.2. Как объявить тип в явной форме

Итак, Bigloo позволяет определять информацию о типе, которую часто называют аннотацией типа (type annotation). Такие аннотации типа могут быть записаны как в заголовке модуля (точнее: в директивах, содержащихся в заголовке модуля), так и в теле модуля, хотя в последнем случае по понятным причинам эта информация о типе является избыточной, следовательно, необязательной.

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

И ещё одно важное замечание: интерпретатор Scheme просто игнорирует все аннотации типов, то есть, проблемы "совместимости" не возникают.

Аннотации типов могут быть записаны в следующих специальных формах:

define (функция[::тип] [аргумент[::тип] ...) тело_функции
define-inline (функция[::тип] [аргумент[::тип] ...) тело_функции
let ((переменная[::тип] ...) ...) локальный_блок
let loop ((переменная[::тип] ...) ...) локальный_блок
let* ((переменная[::тип] ...) ...) локальный_блок
letrec цикл ((переменная[::тип] ...) ...) локальный_блок
labels ((переменная[::тип] (переменная[::тип] ...) b) ...) локальный_блок

Как уже было сказано ранее, в теле модуля не обязательно записывать аннотации типов, поэтому если в любой из вышеперечисленных конструкций опустить информацию о типах, то Bigloo будет по умолчанию использовать обобщённый тип obj.

Как же эти аннотации типов будут выглядеть на практике? Рассмотрим небольшой пример.

(module example1
  (export (vector-fill!::vector ::vector ::obj)))

(define (vector-fill! vec filler)
  (let loop ((i::long (- (vector-length vec) 1)))
    (if (< i 0)
      vec
      (begin
        (vector-set! vec i filler)
        (loop (- i 1))))))

(let ((vec::vector (make-vector 3 4)))
  (vector-fill! v "элемент"))

В этом примере определена экспортируемая функция vector-fill!, которая возвращает значение заданного типа vector, явно определяемого аннотацией типа в заголовке модуля. Функция эта принимает два аргумента: первый — вектор, который будет заполняться (опять же — явно указана аннотация типа ::vector), второй — элемент произвольного (обобщённого) типа ::obj, который будет применяться в качестве заполнителя заданного вектора.

В теле модуля также использована аннотация типа — для счётчика цикла i::long.

В аннотациях могут использоваться следующие типы:

  • основные типы языка Scheme: pair, null, bstring, bint
  • основные внешние (extern) типы: long, int, char, string
  • составные внешние типы
  • типы, представленные определениями классов

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

(module example2
  (export (increment::int ::int)))

(define (increment x) (+ 1 x))

Собственно говоря, большинство функций наверняка будут экспортируемыми, поэтому директиву export стоит рассмотреть подробнее.

1.3. О директиве export заголовка модуля

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

export идентификатор ...
export (идентификатор_функции идентификатор ...)
export (inline идентификатор_функции идентификатор ...)
export (generic идентификатор_функции идентификатор ...)
export (macro идентификатор идентификатор ...)
export (syntax идентификатор идентификатор ...)
export идентификатор_класса

Первая форма позволяет экспортировать переменную или несколько переменных. Вторая предназначена для экспортирования функций, которые считаются неизменяемыми при этом способе экспорта. Встраиваемые inline-процедуры также могут быть экспортированы (третья форма). С объектной подсистемой компилятора Bigloo связаны generic-форма (она позволяет экспортировать обобщённые функции классов) и экспортирование класса в целом (последняя форма).

Следует отметить, что экспортироваться из какого-либо модуля могут только объекты, определённые непосредственно в этом модуле (то есть, объекты, которые были импортированы в модуль, нельзя экспортировать из него).

1.4. Пример экспортирования объектов

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

(module mod01
  (export my-var ; экспорт изменяемой глобальной переменной
          (remap x y) ; экспорт неизменяемой функции, принимающей два аргумента
          (inline toggle y . z)))
          ; экспорт встраиваемой функции, которая принимает по меньшей мере
          ; один аргумент, представляющий собой пару (pair)

2. Описание стандартной библиотеки

Поскольку ранее я уже отмечал почти полную совместимость компилятора Bigloo со стандартом языка Scheme R5RS, нетрудно догадаться, что большинство функций стандартной библиотеки соответствуют функциям Scheme. Поэтому не буду долго задерживаться на подробных описаниях общеизвестных функций — для этого есть документация по языку Scheme, — а немного больше внимания постараюсь уделить "нестандартным" функциям.

2.1. Логические функции и проверки условий

Здесь никаких неожиданностей нет: к логическим относятся функции not и boolean?, а проверки условий хорошо знакомы пользователям Scheme — это eqv?, eq? и equal?.

2.2. Списки и пары

К обширному набору процедур обработки списков добавлены специализированные функции. Функция pair-or-null? <объект> проверяет, является ли объект парой или пустым списком, и если это так, то возвращает значение #t. В противном случае возвращается значение #f.

Процедура append! <список> является "разрушающим" вариантом стандартной функции append. У процедуры реверсирования списка также есть "разрушающий" аналог reverse! <список>.

Функция last-pair <список> возвращает самую последнюю пару списка, который, разумеется, не должен быть пустым.

Пара функций remq <объект> <список> и remq! <объект> <список> возвращает копию исходного списка, из которой удалены все элементы, эквивалентные (по условию eq?) заданному объекту. Как вы уже догадались, remq! представляет "разрушающую" версию.

Ещё одна пара функций delete <объект> <список> и delete! <объект> <список> действует почти так же, как и вышеупомянутые функции, с той лишь разницей, что для проверки условия применяется функция equal?.

cons* <объект> ... возвращает новый объект, сформированный посредством объединения всех заданных аргументов, обрабатываемых справа налево. Если задан только один объект, то этот объект возвращается без изменений.

2.2.1. Группа функций поэлементного сравнения списков:

every? <функция> <список1> <список2> ...

Применяет функцию-предикат, последовательно проходя по спискам и сравнивая соответствующие элементы. Значение "истина" возвращается только в том случае, если все сравнения элементов дали положительный результат. Например:

(every? < '(1 2 3) '(3 4 5))
#t  ; каждый элемент первого списка меньше соответствующего элемента второго списка
(every? < '(1 2 3) '(3 4 0))
#f  ; при сравнении последних элементов условие нарушено
any? <функция> <список1> <список2> ...

Сравнение выполняется точно так же, как в every?, но для получения "истины" достаточно чтобы как минимум одно сравнение элементов выдало положительный результат.

(any? < '(1 2 3) '(3 4 5))
#t  ; здесь вопросов не возникает
(any? < '(1 2 3) '(3 4 0))
#t  ; сравнение первых элементов уже даёт "истину" — этого достаточно

Имеются ещё и вариации этих функций every и any — заинтересованные читатели без труда разберутся с ними с помощью документации (оставляю это в качестве небольшого "домашнего задания").

2.2.2. Поиск в списках

Для поиска в списках применяются две функции:

find <условие> <список>

Возвращает самый первый найденный элемент списка, соответствующий заданному условию. Если ни один из элементов не соответствует условию, то возвращается значение #f. Например:

(find even? '(7 3 1 4 1 5 9))
4
(find even? '(17 13 11 3 1 5 9))
#f

Следует обратить особое внимание на неоднозначность семантического (смыслового) истолкования возвращаемого значения. Если функция find возвращает значение #f, то, вообще говоря, невозможно точно определить, является ли это значение найденным элементом списка, соответствующим заданному условию, или признаком того, что требуемый элемент не был найден. Конечно, в большинстве случаев эта неоднозначность не проявится — например, известно, что список не содержит элементов #f или в списке гарантированно содержится элемент, соответствующий условию. Тем не менее, "спорные" ситуации вполне возможны, и для их разрешения следует воспользоваться второй функцией:

find-tail <условие> <список>

Эта функция возвращает самую первую пару из списка, для которой результат выполнения функции car будет соответствовать заданному условию. Если таких пар не найдено, то функция возвращает #f. Следующие примеры помогут лучше понять, как работает find-tail.

(find-tail even? '(13 11 17 8 5 0 7))
(8 5 0 7)  ; потому что для пары 8 . (5 0 7) функция car возвращает 8 — чётное
(find-tail even? '(13 11 17 7))
#f  ; очевидно, что подходящая пара не найдена

2.2.3. Создание списков

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

Самая простая и понятная функция:

make-list n [заполнитель]

возвращает список, состоящий из n элементов. Если задан заполнитель, то он инициализирует все элементы списка. Если заполнитель не задан, то элементами списка становятся произвольные случайные значения. Неисправимым эгоистам понравится следующий пример:

(make-list 7 'я)
(я я я я я я я)

Для инициализации списка числовыми последовательностями пригодится следующая функция:

iota количество [нач_значение шаг]

Результатом является список, составленный из числовых элементов, вычисляемых по следующей схеме:

(нач_значение нач_значение+шаг ... нач_значение+(количество-1)*шаг)

Начальное значение и шаг задавать не обязательно — по умолчанию список начинается с 0, а шаг устанавливается равным 1. Несколько странное название автор Bigloo объясняет тем, что в изрядно подзабытом языке APL существовала стандартная процедура с таким названием, которая выполняла точно такую же операцию. В практическом применении это выглядит приблизительно так:

(iota 5)
(0 1 2 3 4)
(iota 5 -1 -0.1)
(-1 -1.1 -1.2 -1.3 -1.4)
list-split <список> n [заполнитель]

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

(list-split '(1 2 3 4 5 6 7) 3 0)
((1 2 3) (4 5 6) (7 0 0))
(list-split (iota 10) 3)
((0 1 2) (3 4 5) (6 7 8) (9)) ; заполнитель не задан
(list-split (iota 10) 3 '-1)
((0 1 2) (3 4 5) (6 7 8) (9 -1 -1)) ; заполнитель задан

Для копирования списков в Bigloo предусмотрены такие функции:

list-copy <список>
tree-copy <список>

Первая функция копирует только основную форму, так сказать, "скелет" списка. В отличие от неё tree-copy рекурсивно копирует все заданные аргументы, то есть, в некотором роде заглядывает внутрь элементов списка.

И ещё пара полезных функций обработки списков:

delete-duplicates <список> [eq-условие/equal?]
delete-duplicates! <список> [eq-условие/equal?]

delete-duplicates удаляет дублирующиеся элементы из заданного списка. Если в заданном списке встречается несколько эквивалентных элементов, то в результирующем списке будет сохранён только самый первый ("самый левый") из таких элементов. Порядок всех сохраняемых элементов остаётся точно таким же, как в исходном списке, и это весьма удобно для выполнения операции "очистки" ассоциативных списков.

Необязательное eq-условие задаётся для сравнения элементов в списке на эвивалентность — по умолчанию определено условие equal?. Таким образом, если, например, в списке за элементом x следует элемент y, за которым, в свою очередь, располагается элемент z, то непременно будут выполнены сравнения (= x y), (= y z) и (= x z). Другими словами, процедура сравнения применяется к каждой паре элементов списка не более одного раза, но при этом порядок вызовов процедуры сравнения является неопределённым.

delete-duplicate не изменяет исходный список, и результирующий список может содержать общий "хвост" совместно с исходным списком, в то время как delete-duplicates! является "разрушающим" вариантом функции, то есть, может изменять структуру исходного списка для формирования результирующего.

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

3. Заключение

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

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


Ресурсы для скачивания


Комментарии

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

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Open source, Linux
ArticleID=506852
ArticleTitle=Bigloo — компилируемая модификация языка Scheme: Часть 2. Синтаксис и стандартная библиотека
publish-date=08102010