Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

13.3. ЯЗЫКИ РАЗМЕТКИ

785

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

фрагмент

HTML

, показывающий данные о редакторе.

Однако

XSL

может действовать как функция текстового процессора

merge-

. Определенный как часть пространства имен

XSL

, элемент

xsl:for-each

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

лы в исходном файле

XML

. Атрибут

xsl:value-of

вставляет значение узла

XML

в элемент

HTML

. Таким образом, если придется вернуться к

EDITORS.XML

вставить десятки или сотни контактных адресов, то они без каких-либо изме-

нений будут отображаться в соответствии с таблицей стилей. Благодаря тому,

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

XML

XSL

экономят пропускную способность.

Таблицы стилей

XSL

имитируют функцию

merge-print

еще и в том, что

они позволяют избирательно опускать поля данных при отображении. Кроме

того, вывод может быть отсортирован по любому конкретному полю данных.

Для сортировки базы данных контактных адресов по фамилии редактора в

прямом алфавитном порядке элемент

xsl:for-each

следует изменить следую-

щим образом:

<xsl:for-each select="editor_contacts/editor" order-by="last_name">

XSL

способен осуществлять условную трансформацию вывода в зависимо-

сти от значений различных элементов или атрибутов. Более того, он позво-

ляет запрашивать данные с использованием множества разнообразных опе-

раторов шаблонов, символов подстановки, фильтров, булевых операторов и

выражений.

XML

XSL

никоим образом не предназначены для замены систем рабо-

ты с базами данных, например,

SQL

Однако

XSL

открывает возможность

разнообразного поиска по данным после их загрузки в браузер.

Из перечня возможностей

XSL

видно, что

XML

снабжен выразительными

средствами оперирования с древовидно структурированными текстами, но

что особенно важно, здесь четко прослеживается поддержка принципа раз-

деления распознавания структуры и работы с ней. Мы уже имели возмож-

ность убедиться в преимуществах такого подхода, когда обсуждали стиль

программирования от событий. Эти преимущества существенно возрастают

за счет стандартизации

XML

. В частности, ведется разработка стандартных

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

Да, наверно, вряд ли найдется много желающих хранить свои базы данных непосред-

ственно в формате

XML

786

ГЛАВА 13. СЕНТЕНЦИАЛЬНЫЕ МЕТОДЫ

достижений в этой области является так называемая объектная модель до-

кумента (

Document Object Model

DOM

), версия 1.0 которого была принята в

качестве рекомендации

W3C

в октябре 1998 года.

DOM

возникла как специ-

фикация для обеспечения переносимости сценариев

JavaScript

и программ

на

Java

между браузерами

Web

и позднее эволюционировала в

API

для до-

кументов

HTML

XML

. Она определяет логическую структуру документов,

способы доступа и манипулирования ими. Программисты могут создавать

документы, управлять их структурой и добавлять, модифицировать или уда-

лять элементы и содержимое.

Таким образом, возникнув в функциональных рамках языков разметки и

достаточно хорошо соответствуя этому назначению,

XML

XSL

нашли свое

место в качестве инструментария технологии программирования Интернет

приложений.Этот инструментарий стремится быть адекватным задачам про-

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

если ограничиться рассмотрением

XML/XSL

как средства оперирования с дре-

вовидными структурами, нельзя не заметить один существенный недостаток

подхода: деревья и перекрестные ссылки между элементами деревьев зада-

ются в текстовом представлении. Это удобно для унификации предъявления

данных для браузеров, но для эффективного оперирования разумнее было

бы пользоваться каким-либо стандартизованным бинарным представлением,

связывая именно с ним все, что относится к просмотрам, поискам и преобра-

зованиям данных. В таком случае вся специфика языка разметки, предназна-

ченного для Интернет и, возможно, для других нужд, могла бы быть задана

как специализированная стандартная надстройка над бинарным представле-

нием.

Применительно к оперированию с таблицами, которое послужило пово-

дом для обсуждения

XML/XSL

подхода, нужно именно бинарное представле-

ние. Приведенное в § 10.5.3 решение этой задачи на

XML

в основном обусло-

влено его стандартностью, а не реальными достоинствами. Оно заодно слу-

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

стилем программирования для их обработки не является однозначной. Даже

если в большинстве случаев хорошо работает некоторый стиль (в частности,

сентенциальный стиль для языков разметки), конкретная задача может про-

диктовать другой. Но в любом случае нужно выбирать стиль, концептуально

согласующийся с представлением данных.

13.4. ПРИМЕНЕНИЯ СЕНТЕНЦИАЛЬНОГО ПРОГРАММИРОВАНИЯ

787

§ 13.4. ПРИМЕНЕНИЯ СЕНТЕНЦИАЛЬНОГО ПРОГРАММИРОВАНИЯ

13.4.1. Аналитические преобразования

Символическое вычисление — это выполнение действий над специально

представленными обозначениями (в данном случае — множеств и их элемен-

тов), а не над конкретными значениями, которые, быть может, и существуют-

то только в идеальном математическом смысле (π,

√

2 и др.). Это абстрактно-

синтаксическое представление конкретно-синтаксического представления язы-

ка изображения предикатов. Иногда такой путь даже очень облегчает жизнь:

повышает точность, сокращает время выполнения

Пример 13.4.1. Символическое разложение многочленов (высоких поряд-

ков) на множители с целью получения аналитических решений уравнений.

Это стоит делать везде, где можно. Пусть требуется найти корни уравнения

− 5X

− 9X

+ 37X

+ 40X

+ 72X

− 360X

− 2X

+ 10X

+ 18X

− 74X

− 80X

− 144X + 720 = 0 (13.14)

Это совершенно неподъемная задача, если пытаться ее решить численными

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

их множителей, то получится все прозрачно (конечно, если известен алго-

ритм преобразования):

(X − 5)(X

− 9)(X

− 8)(X

− 2) = 0.

Конец примера 13.4.1.

Этот пример показывает необходимость владения методами нечисленной ма-

тематики, в данном случае, методами аналитических вычислений.

Что здесь существенно с точки зрения программиста?

Данные — символьные строки определенной структуры (есть правила

задания выражений). Операции — богатый арсенал преобразований одних

Причем, если это удается (что происходит реже, чем хотелось бы, но чаще, чем может по-

казаться неквалифицированному в математике программисту), то сокращение времени явля-

ется принципиальным и радикальным, на порядки превосходящим все, что можно получить

прямой оптимизацией программы. Заодно улучшаются при этом (как всегда происходит при

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

Расплатой же является необходимость применения интеллектуальных ресурсов программи-

ста и (или) аналитика.

788

ГЛАВА 13. СЕНТЕНЦИАЛЬНЫЕ МЕТОДЫ

выражений в другие. Эти операции целенаправленно применяются програм-

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

(в примере — для решения уравнения, но это совсем не обязательно!). Обыч-

ные операции пополняются специальными, часто выражающими сущности

более высоких порядков (например, дифференцированием).

Существенный момент систем аналитических преобразований — вну-

треннее представление выражений. Текстовое представление явно не похо-

дит.Немногим лучше и абстрактно-синтаксическое представление,если иметь

ввиду семантику, которая вкладывается в соответствующие операции тради-

ционных языков программирования.

Конечно, реализовывать аналитические вычисления можно самыми раз-

нообразными способами. Можно упрятать реализацию всех нужных преобра-

зований в каком-либо прикладном пакете (как это сделано,например в

Maple

)

и даже не заметить, что мы имеем дело с сентенциальными по сути своей

задачами. Однако этот путь ведет лишь к таким решениям, которые нужны

«здесь и сейчас»: программист, к примеру, не сможет подсказать программе

символического дифференцирования, что она имеет дело в неким частным

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

буется проводить подобные преобразования систематически, удобнее снаб-

дить перерабатываемые данные дополнительными атрибутами, направляю-

щими вычисления в нужное русло. Иными словами, полезно делать струк-

турные единицы данных активными. А это — привнесение в программу, об-

рабатывающую такие данные, элементов сентенциального стиля, пусть даже

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

рые при этом появляются, непосредственно следуют из того, что данный вид

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

средств реализации.

13.4.2. Сентенциальные методы в традиционных языках

Что касается программирования в сентенциальном стиле на операцион-

ном языке, то прежде всего здесь нужно очертить границы применения. Мы

упоминали условия, при которых применение данного стиля оправдано. Из

них следует, что нет никаких оснований говорить об ‘универсальном’ сен-

тенциальном стиле, пригодном для обработки любых данных. Для специа-

лизированного применения, когда перерабатываемые данные естественным

образом структурированы,правильное программирование в сентенциальном

стиле предполагает отражение в составляемой программы этой структуры.

13.4. ПРИМЕНЕНИЯ СЕНТЕНЦИАЛЬНОГО ПРОГРАММИРОВАНИЯ

789

Здесь есть альтернатива: можно структурировать описание данных или дей-

ствий.

Первый подход ведет к описаниям структур, подобных тем, которые мы

использовали для определения абстрактного синтаксиса языковых конструк-

ций (см. § 2.3). Для соответствующих шаблонов этих структур пишутся об-

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

Надо еще позаботиться о том, как будет происходить просмотр перерабаты-

ваемых данных (порядок обхода структурных единиц, рекурсивный вызов

обработчиков и др.). Этот путь поддерживается во многих языках, связанных

с разметкой текстов и (или) программированием для Интернет (например, в

Pearl

Второй подход — отражение структуры перерабатываемых данных в дей-

ствиях программы. Это один из типовых методов программирования, полу-

чивший название рекурсивного спуска. В простейшем случае, когда для рас-

познавания структурной единицы данных достаточно узнать, с чего они на-

чинаются, детерминирование процесса просмотра структуры, заложенной в

действиях, достигается в самом начале обращения к структурной единице

(все расхождения между структурами квалифицируются как ошибки ввода).

Обработка данных в этом случае локализована достаточно хорошо и, как пра-

вило, трудностей не представляет. Если же быстрое условие распознавания

структурной единицы нарушается, то этот прием существенно усложняется:

приходится планировать заглядывания вперед, возвраты и другие способы

преодоления недетерминизма.Иными словами,адекватность моделирования

сентенциального стиля падает: программист вынужден одновременно забо-

титься и о процессе разбора структуры, и об обработке.

Задания для самопроверки

1. Если в программе 13.2.1 переставить местами факты

unknown(a)

unknown(b)

изменится ли что-нибудь?

2. Что произойдет, если в программе 13.2.1 заменить определение преди-

ката

greater

на

greater(X,Y):-greater(X,Z),greater(Z,Y).

greater(X,f(X)).

790

ГЛАВА 13. СЕНТЕНЦИАЛЬНЫЕ МЕТОДЫ

3. Совпадают ли выражения

(a-b)-c

a-b-c

? А выражения

a+b+c

(a+b)+c

a+(b+c)

4. Проверьте, как работает программа 13.2.3. Она имеет недостаток, вы-

являющийся в случае отсутствия пути. Как, изменив лишь одно пред-

ложение в данной программе, избавиться от недостатка?

5. Придумать несколько вариантов представления полиномов, ориенти-

рованных на сложение, умножение и деление с остатком.

Глава 14

Функциональное

программирование

Этот стиль программирования объясняется на примере языка

LISP

в его

наиболее распространенной форме (имеющей официальный стандарт)

Common

Lisp

LISP

— вероятно, первый из практически реализованных языков

, ко-

торый основывался на серьезном теоретическом фундаменте и пытался под-

нять практику программирования до уровня концепций, а не опустить кон-

цепции до уровня сегодняшней (на момент создания языка) практики.

§ 14.1. СТРУКТУРА ДАННЫХ

Lisp

, так же, как в сентенциальных языках, структура данных програм-

мы и поля памяти, обрабатываемого программой, совпадают. После столь-

ких примеров такое совпадение уже не кажется случайностью, видимо, это

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

коуровневых систем.

Основной единицей данных для

Lisp

-системы является список. Списки

Lisp

изоморфны тем,которые определены в Приложении (определение A.6.1).

Атомами являются истина

, числа и имена, ложью служит пустой список

NIL

Если не применены специальные операции блокирования вычислений,

первый аргумент списка интерпретируется как функция, аргументами кото-

рой являются оставшиеся элементы списка. Это позволяет и программу за-

давать списком.

И уж точно первый из выживших, поскольку

Plankalk

Цузе умер вместе с его машинами.

791

792

ГЛАВА 14. ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ

Основная операция для задания списков

(listab... z)

.Она вычисляет свои

аргументы и собирает их в список. Для этой операции без вычисления аргу-

ментов есть скоропись

’(a b ... z)

. Она является частным случаем функции

quote

(сокращенно обозначаемой

’

), которая запрещает всякие вычисления в

своем аргументе и копирует его в результат так, как он есть.

По традиции элементарные операции разбора списков обозначаются име-

нами, которые начинаются с

, кончаются на

, а в середине иден некоторая

последовательность букв

(car s)

выделяет голову (первый член) спис-

ка,

(cdr s)

— его хвост (подсписок всех членов, начиная со второго). Буквы

применяются, начиная с конца. Рассмотрим маленький пример диалога,

иллюстрирующий эти операции.

[13]>(setq a ’(b c (d e) f g))

(B C (D E) F G)

[14]> (cddr a)

((D E) F G)

[15]> (cddar a)

*** - CDDAR: B is not a list

1. Break [16]> ^Z

[17]> (caaddr a)

[18]> (cdaddr a)

(E)

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

ны атрибуты. Стандартный атрибут — значение атома. Для установки это-

го атрибута есть функция

(setq atom value)

, аналогичная присваиванию. Эта

функция не вычисляет свой первый аргумент, она рассматривает его как имя,

коотрому нужно приписать значение.

Значение может является локальным, если мы изменили значение ато-

ма внутри некоторого блока, то такое ‘присваивание’ действует лишь вну-

три минимальных объемлющих его скобок, и исчезает снаружи блока. Кро-

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

атрибуты глобальны. Они принадлежат самому имени, а не блоку. Способ

установки значений этих атрибутов несколько искусственный. Имеется еще

одна функция

setf

, которая вначале вычисляет свой первый аргумент, кото-

рый должен дать ссылку на место, которому можно приписать значение (на-

14.2. МОДЕЛЬ ВЫЧИСЛЕНИЙ

793

пример, на атрибут). Функция получения значения атрибута

get

, даже если

атрибута еще нет, указывает на его место.

[38]> (setf (get ’b ’weight) ’(125 kg))

(125 KG)

[39]> (get ’b ’weight)

(125 KG)

Таким образом, получаем общую структуру данных языка

LISP

, изобра-

женную на рис. 14.1.

§ 14.2. МОДЕЛЬ ВЫЧИСЛЕНИЙ

Программа на языке

LISP

задается как список применений функций,часть

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

правило, заданные в программе списки интерпретируются как применения

функций и вычисляются, если другое не определяют ранее активированные

функции (вы видели, что функция

quote

запрещает вычисление своего аргу-

мента, функция

setq

запрещает вычисление лишь первого из двух аргумен-

тов, а функция

setf

заставляет вычислить первый аргумент лишь до стадии,

когда получена ссылка на его значение). Любое выражение выдает значение

(это используется, в частности, при диалоговой работе с

LISP

, на примере

которой иллюстрируются понятия).

Основные управляющие функции соответствуют тому. что необходимо

для вычисления условных термов. Функция

(block name e1 ... en)

(14.1)

вычисляет свои аргументы, начиная со второго, один за другим, тем самым

задавая последовательность команд. Первый ее аргумент, name, служит име-

нем блока. В любой момент из любого объемлющего блока можно выйти и

выдать значение с помощью функции

(return-from name value)

(14.2)

Этим

LISP

выгодно отличается от большинства языков.

Далее, блоком считается любое описание функции. Описание функции

производится при помощи функции

defun

, которая, в свою очередь, опреде-

ляется через примитивы

function

lambda

. Первый из них задает, что имя,

794

ГЛАВА 14. ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ

Block 1

( A ( A ) )

Block 2

Атрибуты

Attr1

Attr2

Val1

Val2

Значение

Тип

Значение

Тип

Function

Рис. 14.1. Структура данных языка LISP