Фэндом

Smalltalk по-русски

Путеводитель хич-хайкера по компилятору в Smalltalk-е

239статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Путеводитель хич-хайкера 1 по компилятору в Smalltalk-е 2Править

Автор Vassili Bykov, 2000
Перевод Андрея Собчука, 2003
Не паникуйте

Это статья о блеске и нищете компиляторов в VisualWorks и Squeak. Вполне возможно, что компилятор находится в конце списка вещей, с которыми вы захотите иметь проблемы. Если же вы часто сталкиваетесь с ними, то ваше имя должно быть Дэн или Элиот 3 или же вы работаете с кем-то из них. Если это так, то много вы тут не почерпнёте, пожалуй даже ничего.

Что особенно приятно в VW и Squeak-е, так это то, что вы имеете такой же полный доступ к компилятору, как и разработчики. Если вы похожи на меня, то вы любите разбираться, как же всё устроено. Эта статья расскажет вам о нескольких хаках, которые я делал с компиляторами раньше. Так же, эта статья должна познакомить вас с компилятором. Она задумывалась как обзор компилятора в VisualWorks, но потом добавились вкрапления информации о Squeak-е. У VW и Squeak одни и те же прародители. И увидеть, что есть между ними общего и в чем появилось различие за эти годы, очень интересно.

Статья не о теории компиляторов и не о том, как создавать компиляторы. Мы не будем рассматривать грамматику, чем отличается разбор сверху-вниз от разбора снизу-вверх или конфликты сдвига-свёртки. Естественно, что вы не станете супер-знатоком компиляторов, если вы не являетесь им сейчас. Какая же тогда цель статьи? Ну, я полагаю, что можно провести аналогию с хич-хайкингом по дорогам, когда без особых усилий можно ознакомиться с множеством мест.

Вавилонское столпотворениеПравить

Сперва давайте пройдёмся по терминологии и рассмотрим, о чем мы собираемся говорить.

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

foo := self bar

Выражение передаётся либо как строка, либо как поток, значит с точки зрения компилятора это буква f, затем две буквы o, потом пробел, двоеточие... Так можно за деревьями не увидеть леса, вдобавок тут слишком много ненужной информации. К примеру, нас не интересует один там пробел, несколько или foo и := разделены символом табуляции.

Первая фаза, сканирование или лексический анализ, убирает подобную избыточную информацию и собирает в кучу отдельные символы. Эти большие куски называются лексемы или токены. После сканирования наш пример будет выглядеть как слово "foo", затем оператор ":=", затем слово "self" и, наконец, слово "bar".

Теперь компилятор видит поток токенов, но всё еще нет никакой структуры. Процес нахождения структуры называется синтаксический анализ. Его результат — это дерево грамматического разбора, представляющее разделение исходного текста на синтаксические элементы. После разбора примера компилятор будет знать, что то, что ввели это "присваивание со ссылкой на переменную foo с левой стороны и результатом, полученным после посылки сообщения bar к self, справа".

Дерево грамматического разбора представляет смысл исходной программы. Последняя стадия, генерация кода, переписывает этот смысл в целевой машинный код. Мы забежим немного вперёд (понимание байткода интерпретатором обсудим позже), но вот во что будет оттранслирован наш пример:

push self
 send #bar
 store local 0

В остальной части главы, мы посмотрим как эти этапы реализованы. В Squeak-е классы, относящиеся к компилятору, сгруппированы в категории System-Compiler. В VW, они расположены под категориями System-Compiler-*.

Лексический анализПравить

И в VW и в Squeak-е лексический анализатор (сканер) представлен классом Scanner. Только что мы представили лексический анализ, как отдельную стадию, хотя это не так. Обычно Сканер представляет потоковый доступ к исходному тексту, поставляя грамматическому анализатору токены по его запросу один за другим. Токены не представляют из себя настоящие объекты. В процессе сканирования обычно устанавливаются две переменные экземпляра в Сканере: типТокена (tokenType) и токен (token). типТокена — это экземпляр класса Symbol. Он указывает, какого типа токен был просканирован. Например, #ключевоеСлово (#keyword) или #число (#number). Переменная токен содержит объект, обычно класса Строка (String), Число (Number) или Символ (Character), который представляет значение токена. Например, после сканирования первого слова из нашего примера в переменной типТокена будет находиться #слово (#word), а в токен — строка "foo".

Даже если сканер в действительности не превращает исходные тексты в последовательность токенов за один шаг, то увидеть, какой набор токенов соотвествует определённому исходному тексту, может быть удобным для изучения механизмов работы компилятора. Нижеприведённый метод (он работает в VW и Squeak-е — у них общие корни!) превращает строку Smalltalk-ового кода в массив из пар типТокена-токен.

Scanner>>scanAll: aString
   | tokenStream |
   tokenStream := WriteStream on: (Array new: 10).
   self scan: (ReadStream on: aString).
   [tokenStream nextPut: (Array with: tokenType with: token).
   tokenTyp == #doIt]
     whileFalse: [self scanToken].
   ^tokenStream contents

В качестве упражнения, пользуясь этим методом, посканируйте разные куски кода. Это не обязательно должен быть правильный Smalltalk-овый код. Как мы отметили, сканер не анализирует структуру текста. Всё, что похоже на слова, сканер преобразует в токен с типом #слово, не важно — это ссылка на локальную переменную foo, глобальную Foo, селектор сообщения self foo или литерал как nil, true, false. Только на следующих стадиях компиляции определяется действительное значение этих слов.

Синтаксический анализ Править

Синтаксический анализатор (анализатор) реализован классом Parser в VW и Squeak-е. Это вручную закодированный рекурсивный спускающийся анализатор (что это значит, мы узнаем позже на нашем примере). Его легко понять и модифицировать. Он использует сканер, чтобы читать токены из компилируемой программы, один за другим по мере надобности. Необычно то, что Parser — это подкласс класса Scaner. Какова бы ни была причина подобного дизайнерского решения, оно явно идёт из Smalltalk-80, так как применяется и в VW и в Squeak. Точка входа в анализатор, по крайней мере в тот, который в VW и в Squeak-е, это сообщение parse:class:noPattern:context:notifying:ifFail:, которое понимают экземпляры класса Parser. В случае безошибочной компиляции, результатом будет дерево разбора. Следующий пример работает в VW и в Squeak

Parser new
   parse: (ReadStream on: '(Point new x: 10; y: 16r20) r')
   class: UndefinedObject
   noPattern: true
   context: nil
   notifying: nil
   ifFail: [^nil]

и возвращает получившееся дерево грамматического разбора. Особенно удобно его смотреть при помощи ObjectExplorer из Squeak-а.

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

Если исходный текст — это метод, то второй аргумент задаёт класс, в котором метод будет проинсталлирован. Класс представляет информацию о переменных, которые доступны из метода. Третий (noPattern:) аргумент установлен в false, если анализатор должен найти заголовок метода в начале исходного текста.

Если это "отдельный" код, то третий аргумент установленный в true говорит, что в начале текста нет заголовка метода. Параметр class: зависит от того, какой из инструментов используется для выполнения кода. Примеры мы увидим позже. Параметр context: используется, если метод должен иметь возможность обращаться к переменным из существующего блока или контекста метода (этим может пользоваться отладчик).

Последние два аргумента используются при обработке ошибок. Параметр notifier: — это обработчик ошибок. В VW обычно это подкласс CompilerErrorHandler. Если в тексте обнаружена ошибка, то этот объект должен каким-либо способом сообщить об этом пользователю. Один вариант может вставлять текст сообщения об ошибке в текст в месте ошибки, другой может просто печатать сообщение в Transcript.

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

Вместе notifier и блок ifFail представляют из себя инструмент для обработки ошибок. Компилятор и его протокол был создан более чем на десятилетие раньше, чем в любом из существующих диалектов Smalltalk-а появились исключения. Если ошибок не обнаружено, то результатом сообщения является корень дерева разбора исходного кода. Это дерево построено из экземпляров подклассов ProgramNode (VW) или ParseNode (Squeak). В VW, все эти классы принадлежат категории System-Compiler-Program Objects.

Виртуальная машина Править

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

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

Альфа и омега интерпретатора — это контекст вызова. Как минимум в теории, это объекты, размещаемые в куче — экземпляры классов КонтекстМетода (MethodContext) и КонтекстБлока (BlockContext). Контекст хранит информацию, относящуюся к выполнению текущего метода, СкомпилированныйМетод (CompiledMethod) хранит выполняемый сейчас байткод, объект-получатель сообщения, значения временных переменных (аргументы тоже считаются временными переменными), и указатель на текущий выполняемый байткод. Так же там хранится отправитель (sender) — контекст, из которого было отправлено сообщение, обрабатываемое в текущем контексте. Цепочка контекстов, связанная через отправителя, соответствует стеку вызовов в "традиционных" языках программирования.

Интерпретатор изменяет значения в контексте при выполнении программы. Однако, это только теоретически. В реальной системе, интерпретатор (или динамический компилятор, как в VW) врядли будет использовать объекты из кучи для выполнения кода. Тем не менее, иллюзия подобного устройства создаётся при использовании псевдопеременной текущийКонтекст (thisContext) 4. Выполняя код, интерпретатор использует значения счетчика команд, получателя, литералы и временные переменные (литералы расположены в СкомпилированномМетоде, временные переменные в текущем контексте). Аргументы сообщения так же являются временными переменными (в терминах VW — locals). Для работы с вышеперечисленными значениями есть специальные байткоды. Другая важная структура, к которой работают многие байткоды, это стек. Опять же, это не тот тип стека, который большинство языков используют для хранения адресов возврата из функций. Стек, который использует интерпретатор — это часть контекста. Значит, каждый вызов метода имеет свой собственный маленький стек. Он похож на стек данных в Форте и используется вместо регистров для хранения временных данных. Каждая ячейка стека может хранить один объект (это может быть и объектная ссылка и непосредственный объект (immediate), как экземпляры класса SmallInteger). Нас не интересует полная спецификация на байткоды, но ниже дан обзор самых основных инструкций, чтобы вы получили представление, какие возможности доступны. Тут даны не "официальные" названия инструкций, частично, чтобы избежать ненужного усложнения и детализации материала, а частично, чтобы не привязываться к конкретной реализации, так как мы рассматриваем две разные системы с подобными, но различающимися наборами байткодов.

Работа с данными:

  • push self - положить получателя текущего сообщения в стек;
  • push instance N - положить переменную с индексом N в текущем получателе в стек;
  • push temp N (push local N в VW) - положить в стек объект из временной переменной N текущего контекста. Как уже отмечалось, аргументы — это тоже временные переменные. Например, у метода могут быть два аргумента во временных слотах 0 и 1, а начиная с 2 и далее лежать временные переменные метода;
  • push literal N - положить в стек объект по индексу N в кадре литералов текущего метода (в своё время мы обсудим кадры литералов);
  • pop instance N - извлечь объект с вершины стека в переменную по индексу N в получателе;
  • pop temp N - извлечь объект с вершины стека во временную переменную N текущего контекста.

По понятным причинам, не существует команд pop self и pop literal N. Две дополнительные команды, относящиеся к стеку:

  • dup - как и в Форте, положить в содержимое текущей вершины стека. Как мы увидим, команда используется при реализации каскадов.
  • pop - отбросить содержимое вершины стека.

Программа может содержать комбинацию этих инструкция, чтобы реализовать присваивание. foo := self может быть оттранслировано в

push self
 pop temp 0

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

  • send N

ссылается на посылаемый селектор по индексу в кадре литералов. Имейте это ввиду, потому что далее мы будем игнорировать индекс и записывать эту инструкцию как send #foo. Получатель сообщения и аргументы запихиваются в стек до исполнения инструкции send (первым идёт получатель, затем аргументы в порядке с первого по последний). После возвращения из отправки сообщения всё это заменяется на единственный объект — возвращаемое значение. Например, часть кода foo := self bar: 1 with: #one может оттранслироваться в:

push self
 push literal 0 "SmallInteger - 1"
 push literal 1 "Symbol - #one"
 send #bar:with:
 pop temp 1

Многие реализации виртуальной машины для оптимизации предоставляют специальные инструкции, чтобы помещать в стек часто используемые объекты, как то true, false, nil, 0, 1, без сохранения их в кадре литералов. Как результат, реальный код может отличаться от того, что приведён выше.

Ну и наконец операторы управления потоком выполнения программы или перехода... Нужны ли они вообще? Они не были бы нужны, если бы сообщения наподобие ifTrue: были реальными сообщениями. Но, в целях оптимизации, они инлайнятся, и операторы условного и безусловного перехода нужны, чтобы закодировать управление потоком выполнения, как и в любой ассемблерной программе. Операторы безусловного перехода передают управление в другую точку байткодов метода. Переход задаётся при помощи смещения. Есть несколько видов одних и тех же операторов перехода, в зависимости от размеров смещения. Так как мы решили работать с упрощённым набором инструкций, то различия в форматах нас не интересует.

Операторы условного перехода ожидают, что на вершине стека будет булево значение. Переход либо осуществляется, либо нет, в зависимости от этого значения. Также, этот оператор удаляет булево значение из стека в независимости от результатов проверки. Вот пример использования условия:

foo := self foo ifTrue: [self bar] ifFalse: [nil]

и возможная трансляция:

push self
 send #foo
 jump ifFalse L1
 push self
 send #bar
 jump L2
L1:
 push nil
L2:
 pop temp 0

Ну и наконец, по завершению метода, он должен оставить возвращаемое значение на стеке и выполнить инструкцию возврата return. Опять же, некоторые реализации могут иметь специальные инструкции, используемые, чтобы вернуть такие значения, как self, за одну команду.

Как увидеть деталиПравить

Чтобы убедиться, что примеры из статьи работают, нам нужен удобный доступ к байткодам метода и к декомпилированному коду. И в Squeak и в VW, если выбрать метод в броузере с нажатым Shift-ом, то броузер покажет декомпилированный а не исходный код. В Squeak есть пункт меню "Show bytecodes" ("Показать байткод"). Выбрав его, вы увидите байткод вместо исходного кода.

В VW с загруженным модулем ProgrammingHacks, есть пункт inspect в меню utilities. При его выборе откроется инспектор на выбранном СкомпилированномМетоде. Инспектор для скомпилированного метода умеет показывать байткоды 5.

Понятно, что это тяжело назвать "прямым доступом". Можем ли мы добавить в систему возможность показывать байткоды при выборе метода с нажатой клавишей Control, так же как декомпилированный код показывается при нажатой клавише Shift? Да, можем. Удивительно, но проверка на нажатие клавиши Shift находится в классе CompiledMethod (на самом деле CompiledCode) в методе getSourceForUserIfNone:, а не в броузере. Первая строка метода вызывает декомпиляцию при нажатом Shift-е. Добавим еще одну строку:

InputState default ctrlDown ifTrue: [^self symbolic]

Она сделает то, что нам нужно.

Ну и наконец то, перейдём к примерам.

Приватные селекторы (VW)Править

Squeak имеет поддержку "приватных методов". Приватность гарантируется во время компиляции. Идея простая: сообщения с селектором, который начинается с "pvt", может быть отправлено только самому себе. Любая попытка отправить такое сообщение к любому получателю кроме самого себя, приводит к ошибке компиляции. В не зависимости от пользы, от такого нововведения, реализация подобной возможности в VW это хороший пример простой модификации компилятора. Чтобы это мычание превратилось в незаурядную работу, мы начнём с того, что добавим метод в класс Symbol, который проверит, является ли этот селектор приватным:

Symbol>>isPrivateSelector
   self size > 3 ifFalse: [^false].
   1 to: 3 do: [ :index |
     (self at: index) = ('pvt' at: index) ifFalse: [^false]].
   ^true

Теперь рассмотрим компилятор. Начнём с того, что исследуем, как отправка сообщения представлена в дереве грамматического разбора. Чуть раньше мы узнали, как получить дерево разбора со строк кода, используя синтаксический анализатор (Parser). Если построить дерево для:

self new: 10 withAll: Character space

то соответствующая часть результата (удобнее всего смотреть через Squeak-овый ObjectExplorer) будет выглядеть так:

УзелСообщения
   селектор: #new:withAll:
   получатель: УзелПеременной {self}
   аргументы:
     аргумент 1: УзелЛитерала {10}
     аргумент 2: УзелСообщения
   селектор: #space
   получатель: УзелПеременной {Character}
   аргументы: #()

Весь результат — это экземпляр класса УзелМетода (MessageNode). Анализатор всегда создаёт УзелМетода, даже если компилирует кусок кода для немедленного выполнения.

Очевидно, что то, что нас интересует, это УзелСообщения. Экземпляры класса УзелСообщения представляют из себя отправку сообщения в разобранном коде. Сообщения, которые мы собрались отбрасывать, будут представленны УзламиСообщений, у которых селектор будет отвечать true на наш тест на приватность, а получатель — это что угодно, кроме self. Проверить селектор легко благодаря методу, который мы добавили к классу Symbol. Но как проверить второе условие? Как видно в вышеприведённом дереве разбора, ссылка на self представленна УзломПеременной, равно как и ссылка на "настоящую" глобальную переменную Character. Возможно, что мы можем добавить метод к УзлуПеременной для проверки того, не представляет ли он ссылку на self. Посмотрев на УзелПеременной (класс VariableNode) в броузере, мы видим, что такой метод уже существует (#isSelf).

Остаётся последний вопрос, когда делать проверку? Очевидно, проверка должна выполняться, когда компилятор обходит дерево разбора. Это происходит в момент генерации кода, вызовом метода кодогенерации у каждого узла. Но есть и альтернатива. Дерево разбора обходится и в момент своего создания. При инициализации УзлаСообщения происходит вызов метода MessageNode>>receiver:selector:arguments: для каждой новой отправки сообщения, которая включается в дерево разбора.

Squeak выполняет проверку во время синтаксического анализа, и мы поступим также, просто потому, что мы еще не изучали процес кодогенерации. Изменять мы должны класс SimpleMessageNode, это абстрактный суперкласс УзлаСообщения (MessageNode). Именно в нём определены и управляются те атрибуты процесса отправки сообщения, в которых мы заинтересованы. Метод гарантироватьПриватность (ensurePrivacy) должен быть определён до того, как мы изменим любой другой метод! Метод receiver:selector:arguments: вызывается каждый раз, при нахождении отправки сообщения в компилируемом коде. Если вы не создадите метод ensurePrivacy заранее, то компилятор не сможет скомпилировать никакой код с отправкой сообщений, включая сам метод ensurePrivacy! Добро пожаловать в хакинг компилятора. Если компилятор не работает, то часто вы не можете исправить это, только потому, что... ну... компилятор не работает...

SimpleMessageNode>>ensurePrivacy
   (selector isPrivateSelector and: [receiver isSelf not])
     ifTrue: [self error: 'can only send this to self']
 SimpleMessageNode>>receiver: rcvr selector: sel arguments: ars
   receiver := rcvr.
   selector := sel.
   arguments := args.
   precendence := nil.
   self ensurePrivacy

В данном случае, если мы в начале изменим метод receiver:selector:arguments:, то мы всё еще можем восстановить исходное определение метода, так как начальный вариант не содержит посылок сообщения. Затем мы сможем определить метод ensurePrivacy и опять изменить метод receiver:selector:arguments:. Хотя подобная возможность откатить изменения — это скорее исключение, чем правило.

После внесения изменений, можно проверить работоспособность кода. Вы заметите один момент относящийся к сообщениям об ошибках. Что делает УзелСообщения, когда блокирует посылку сообщений? Мы использовали self error: ..., которое открывает отладчик. Но об ошибках компиляции обычно сообщается по-другому. Чаще всего, сообщение об ошибке вставляется в отображение исходного кода.

Это делается посылкой сообщений к объекту-уведомителю (припоминаете аргумент notifying: который передаётся парсеру?). В VW, это обычно экземпляр одного из подклассов ОбработчикаОшибокКомпиляции (CompilerErrorHandler). Генерация сообщений об ошибках осуществляется при помощи методов, расположенных в протоколе "обработка ошибок" (error handling). Проблема в том, что в VW УзелСообщения не знает о парсере в момент своей инициализации. Это отличается от реализации в Squeak. Там один из аргументов метода инициализации УзлаСообщения, это — Кодировщик (Encoder). Кодировщик знает, как правильно сообщать об ошибках, используя исходный объект-уведомитель. Именно по этой причине, проверка на приватность в VW должна быть реализована при кодогенерации.

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

Вычисление во время компиляции (VW)Править

Следующая остановка в нашем путешествии, это кое что из Dolphin Smalltalk и IBM Smalltalk — вычисление во время компиляции. Многие не одобряют подобную возможность, так как видят слишком мало возможностей для правильного применения. Тем не менее, это всё еще интересное упражнение с компилятором. Было бы неплохо реализовать это для Squeak, так как моя реализация для VW доступна из архива UIUC 6. К сожалению, как станет ясно позже, реализация этой возможности для Squeak требует значительных изменений и в классе Scanner и в классе Parser. Вычисление во время компиляции — это возможность создания произвольных литералов в методе. В классическом Smalltalk-е, вы можете создать некоторые объекты, например, строки, прямо в исходном коде. Вот как это работает. Например, если компилятор видит

'привет' размер

то он создаёт экземпляр Строки с соответствующим содержимым. Затем, этот экземпляр сохраняется в одной из индексированных переменных в СкомпилированномМетоде. Виртуальная машина может ссылаться на объекты в индексированных переменных СкомпилированныхМетодов. Байткоды метода будут содержать инструкции для извлечения объекта из определённой индексированной переменной и отправки ему сообщения #размер. Эти проиндексированные переменные используются компилятором для различных целей, включая хранение литералов и селекторов сообщений, посылаемых из метода, и известны, как кадр литералов метода.

В кадр литералов можно положить любой объект, но синтаксис Smalltalk-а имеет конструкции только для таких литералов: Числа (Number), Буквы (Character), Строки (Strings), Символы (Symbol) и Массивы (Array). Вычисление во время выполнения позволяет создавать литералы других типов. Выражение, создающее литерал, используется вместо литерала, внутри конструкции ##(). Это выражение вычисляется во время компиляции (отсюда и название) и результат используется, как литерал вместо всей ##() конструкции. Например, следующие две строки эквивалентны друг другу:

'abc' size
 ##(String with $a with: $b with: $c) size

Вычисление во время выполнения может использоваться, чтобы создать литерал класса Dictionary в методе:

errorStringFor: anInteger
   ^##(Dictionary new
     at: 1 put: 'File not found';
     at: 2 put: 'Not enough memory';
     yourself)
   at: anInteger ifAbsent: [^'Unknown error'].

Что нужно сделать для того, чтобы реализовать что-то подобное в VW или Squeak? Возможно, что получится использовать уже существующий механизм, обеспечивающий создание "классических" литералов, таких как Строки. Как видно в дереве разбора строки "self new: 10 withAll: Character space" из предыдущего раздела, литерал 10 представлен экземпляром УзлаЛитералов (LiteralNode). Эксперименты с другими типами литералов показывают, что любой литерал превращается УзелЛитералов, а реальный объект сохраняется в переменной значение (value) этого узла. Это подсказывает простой план атаки. Всё, что нам нужно сделать, это изменить синтаксический анализатор таким образом, чтобы конструкции ##(...) распознавались, и код между скобками вычислялся, производя УзелЛитерала, где значение — результат вычисления кода. Всё остальное сделает генератор кода.

Звучит очень просто, но прежде чем начать, давайте проверим, что сделает с ##(...) лексический анализатор. Воспользуемся методом scanAll:, который мы добавили в класс Scanner, что бы просканировать простое выражение, например:

##(Time now)

отсканируется в VW в

<literalQuote>
 <literalQuote>
 <leftParenthesis>
 <word 'Time'>
 <word 'now'>
 <rightParenthesis>.

Хотя сканер в Squeak сосканирует это, как один токен

<literal #(#Time #now)>.

Очевидно, что это существенное различие между Squeak и VW в том, как они работают с текстом, начинающимся с #. В общем, Сканер устроен одинаково в обоих диалектах: он читает буквы и ищет их в таблице диспетчеризации по ASCII коду. Эта таблица хранится в переменной класса, названой TypeTable. Она содержит селекторы методов Сканера, которые используются для обработки разных типов. Таблица инициализируется в методе initialize на стороне класса. Метод, который отвечает за всё, что начинается с буквы #, это #xLitQuote.

В Squeak этот метод полностью обрабатывает литералы Массивов (Array) и Символов (Symbol). Парсер получает токен типа #литерал с Массивом или Символом, в качестве значения токена. В отличии от Squeak-а, сканер в VW гораздо проще. Он разбивает ввод на примитивные цепочки, такие как слова, буквы # (это токены типа #literalQuote), а это уже забота синтаксического анализатора выделить литералы Массива или Символа. Например:

#(foo)

сосканируется в VW в

<literalQuote>
 <leftParenthesis>
 <word 'foo'>
 <rightParenthesis>.

А уже анализатор превратит это в УзелЛитерала со значением #(#foo). Хотя в Squeak сканер вернёт, как токен <literal #(foo)>.

Теперь понятно почему реализация вычисления во время выполнения будет очень различаться в Sueak и VW. Мы остановимся только на VW. Когда мы всё сделаем, станет ясно, почему баланс между Сканером и Парсером выбранный в VW делает реализацию намного проще.

Как уже было отмечено, синтаксический анализатор использует рекурсивный спуск. Подробности и теорию можно найти в любой книге по компиляторам. Для нас же сейчас достаточно понимания идеи в целом. Существенно важно, что анализатор представляет из себя группу методов "параллельных" к правилам грамматики языка. То есть, существует метод, соответствующий каждому правилу грамматики языка. Метод проверяет следующий токен в потоке, чтобы увидеть, каким вариантом правила воспользоваться. Методы так же включают набор действий по созданию дерева грамматического разбора.

Лучше всего это видно на примере. Вот фрагмент несколько упрощенной грамматики Smalltalk-а:

метод ::= заголовок временные тело
 временные ::= '|' имя-переменной* '|' ИЛИ <пустая строка>
 имя-переменной ::= слово
 тело ::= выражение*
 заголовок ::= ...

Рекурсивный спускающийся анализатор будет выглядеть (не включая действий по созданию дерева разбора) так:

анализироватьМетод
   сам заголовок; временные; тело
   временные
   сам типСледующегоТокена == #вертикальнаяЧерта еслиИстина: 
     [сам сканировать.
     [сам типСледующегоТокена == #слово]
       покаИстина: [сам имяПеременной].
     сам типСледующегоТокена == #ВертикальнаяЧерта еслиЛожь:
       [сам синтаксическаяОшибка: 'Ожидается имя переменной']. 
     сам сканировать].
 имяПеременной
   сам добавитьВременнуюПеременнуюМетода: сам значениеСледующегоТокена.
   сам сканировать.

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

Короче говоря, анализатор предсказывает, что ему ожидать дальше, основываясь на текущем и следующем токенах. У этого способа есть ограничения, но его легко понять и реализовать вручную. В VW методы, вызываемые в рекурсивном спуске, расположены в протоколах типы выражений-* (expression types-*), а точка входа это метод method:context:. Метод, который отвечает за разбор массивов, символов и строк — #constant. Что бы внести наши изменения, мы должны изменить этот метод так, что бы он начал понимать конструкцию ##(). Этот метод — очень длинный набор выражений выбора. Ближе к концу есть несколько проверок, на разные типы того, что начинается с диеза. (Кстати, в VW 3.x присутствует проверка на #левуюФигурнуюСкобку — литерал квалифицированного имени, часть поддержки пространств имён, введённой в VW 5i. Эта возможность разрабатывалась до VW 3.x). Для наших целей, добавим выражение, которое определит наличие второго диеза. В листинге оно выделено жирным. Эти изменения можно внести сейчас же, без прекращения работоспособности компилятора. Даже если метода #compileTimeEval еще нет в системе, это сообщение будет послано только, если встретится конструкция ##().

Parser>>constant
   tokenType == #leftBrace
     ifTrue: 
       [self scanToken.
       self qualifiedNameLiteral.
       ^true].
   tokenType == #literalQuote 
   "must be ##(expr)"
     ifTrue:
       [self scanToken.
       tokenType == #leftParenthesis.
         ifTrue:
           [self compileTimeEval.
           ^true].
       ^self expected: 'parenthesized eval-when-compile expression'].
   self expected: 'word, binary, keyword, #, (, or ['

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

А теперь сердце нашей реализации — метод #compileTimeEval. При входе в метод оба диеза уже сосканированы и следующим токеном должны быть открывающие скобки. Вот список того, что метод должен сделать для того, чтобы заработало вычисление во время выполнения:

  • прочитать поток токенов до соответствующей закрывающей скобки;
  • разобрать и вычислить токены;
  • создать УзелЛитерала со значением - результатом вычисления.

Будем создавать код шаг за шагом, постепенно заполняя пробелы.

Начнём с последней задачи, создания УзлаЛитерала, потому что она самая лёгкая. Вообще ничего не нужно делать. Согласно комментарию к методу #constant, метод ожидает получить константный объект в переменной parseNode (узел дерева разбора). Очевидно, что УзелЛитерала будет создан позже, тем кто вызвал метод constant, так что наш метод просто присвоит значение соответствующей переменной:

compileTimeEval
   ... считывание, разбор, вычисление...
   parseNode := ...результат вычисления...

Считывание токенов вплоть до закрывающей скобки выглядит достаточно просто — читаем токены один за другим. Но здесь есть ловушка. Во-первых, это должна быть соответствующая парная скобка. А ведь могут существовать и другие, вложенные пары скобок до ней. Во-вторых, токены, даже если мы правильно считали их до закрывающей скобки, для нас бесполезны. Мы должны разобрать и вычислить их, но синтаксический анализатор не имеет интерфейса для разбора уже сосканированной последовательности токенов! И добавить такой интерфейс не просто! (Если вы уже собрались создавать объекты, которые хранятся в последовательности токенов, и имитировать сканер, возвращая их один за другим, то похлопайте себя по плечу, за то, что у вас хорошая ОО-интуиция). Проблема в том, что в Squeak и VW Parser — это подкласс Scanner-а. То есть, сканер и парсер — это один объект! Благодаря этой дизайнерской особенности мы не можем подключить другой сканер и не можем отделаться от анализатора, который умеет читать только поток из букв. Мы можем легко обойти это. Подумайте, что останется после того, как мы отбросим оба диеза. Если исходный код был ##(Time now), то анализатор/сканер теперь видит (Time now). Естественно, это простое выражение в скобках или основноеВыражение (primaryExpression) в терминах грамматики, понимаемой анализатором! Если мы попросим анализатор разобрать основноеВыражение, он с радостью слопает всё вплоть до скобок и отдаст нам назад дерево грамматического разбора.

Вот второй дополненный вариант нашего метода:

compileTimeEval
   self primaryExpression.
   parseNode := ...

Это основная причина, почему наш пример легче реализовать в VW, чем в Squeak. В Squeak мы должны были бы дополнить сканер возможностью считывать поток до соответствующей закрывающей скобки, правильно обрабатывать вложенные скобки, и затем попытаться разобрать эту последовательность токенов. Это не невозможно (в Smalltalk нет ничего невозможного), но не настолько просто, как мы сделали сейчас.

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

Первое — генерация кода. Исполняемый объект в Smalltalk — это СкомпилированныйМетод, и это то, что мы должны сгенерировать. Скомпилированный метод всегда создаётся из полного дерева метода (то есть такого, где в корне лежит УзелМетода (MethodNode)). в #compileTimeEval, сразу после вызова #primaryExpression, мы имеем дерево грамматического разбора для выражения в скобках. Мы должны построить полное дерево из частичного нашего. Дерево грамматического разбора обычно создаётся специальным объектом, экземпляром класса ProgramNodeBuilder, который хранится в анализаторе в переменной экземпляра builder. Осматривая систему, в попытке найти способ его использования, мы прийдём к следующему варианту нашего метода:

compileTimeEval
   | methodTree |
   self primaryExpression.
   methodTree := builder
     newMethodSelector: #DoIt
     primitive: nil
     block: (builder newBlockBody: (builder newReturnValue: parseNode)).
   parseNode := ...

Итак, мы имеем полное дерево разбора. Теперь мы должны из него получить СкомпилированныйМетод. Этот метод будет "свободным", то есть не расположенным в словаре методов ни в одном классе в системе. Его не возможно выполнить по стандартным Smalltalk-вым правилам, но VW позволяет выполнять подобные свободные методы.

Так же важно отметить один момент. При создании СкомпилированногоМетода используется область видимости (scope). Любой метод скомпилированный внутри области видимости определённого класса должен выполняться, как отправка сообщения тому же классу. Область видимости определяет, какие переменные доступны из кода. Код, выполняемый из Workspace, компилируется в области видимости класса UndefinedObject. Он выполняется, как сообщение отправленное к nil. (Если вы никогда не думали, что это так устроено, то вычислите self в Workspace и посмотрите на результат. Более интересно будет понять, что произойдёт при вычислении выражения self DoIt в Squeak workspace и почему). Также код вычисляемый в броузере, компилируется в области видимости класса, выбранного в броузере. А значит код может ссылаться на переменные класса. Код вычисляемый в инспекторе, компилируется в области видимости инспектируемого класса и выполняется, как отправка сообщения к инспектируемому объекту. Следовательно код может использовать self и любые переменные экземпляра.

Вполне разумная область видимости для кода, вычисляемого во время компиляции, это класс, в котором метод, содержащий код, определён. Например, ##(self name) в методе со стороны экземпляра класса Foo будет преобразован в литерал, который ссылается на символ #Foo.

Чтобы произвести вычисление выражения в нужной области видимости, анализатор должен знать в каком классе будет установлен метод, который сейчас разбирается. В VW до версии 3.0 эта информация не была доступна. Моя старая реализация из UIUC архива добавляла переменную экземпляра к классу Parser названную targetClass. В версии 3.0, разработчики VW добавили целевойКласс (targetClass) к синтаксическому анализатору самостоятельно, и такая модификация больше не требуется. Финальная (почти) версия нашего метода:

compileTimeEval
   | methodTree |
   self primaryExpression.
   methodTree := builder
     newMethodSelector: #DoIt
     primitive: nil
     block: (builder newBlockBody: (builder newReturnValue: parseNode)).
   parseNode := targetClass performMethod: 
     (Compiler new
       compile: methodTree in: targetClass class).

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

compileTimeEval
   | exprStart methodTree |
   exprStart := mark.
   self primaryExpression.
   methodTree := builder
     newMethodSelector: #DoIt
     primitive: nil
     block: (builder newBlockBody: (builder newReturnValue: parseNode)).
   [parseNode := targetClass performMethod: 
     (Compiler new compile: methodTree in: targetClass class)]
   on: Error
   do: [:ex | self notify: 'evaluation error: ', ex errorString at: exprStart]

Заинлайненный (почти) ifNil: (VW)Править

Только что мы использовали метод компилятора compile:in:, чтобы получитьСкомпилированныйМетод из дерева разбора. Сейчас же мы детально рассмотрим, что происходит в это время. Первое, что происходит в VW, это макроподстановки.

Макросы это не стандартная часть Smalltalk-а, но VW имеет внутренние возможности макроподстановок. Эти макроподстановки используются для замены определённых отправок сообщений другими узлами. Обычно замена осуществляется на специальные узлы, например, УзелУсловногоВетвления и УзелЦикла, которые генерируют код особым образом. Например, УзелСообщения, представляющий посылку сообщения #to:do: заменяется другим типом узла — УзломАрифметическогоЦикла (ArithmeticLoopNode). Заменяющий узел генерирует оптимизированный заинлайненный код для конструкции, определяющей цикл, чтобы избежать накладных расходов на создание блока и посылку ему сообщения на каждой итерации. Подобная возможность позволяет добавлять в дерево разбора такие узлы, которые иначе не возможно было бы добавить. Другой вариант использования макроподстановок — замена отправки сообщения группой других узлов, которые не создаваемы вручную. Именно так макросы используются в некоторых других языках.

Хорошим примером применения подобной возможности будет реализация метода ifNil:. Очевидно, что реализовать нужно два метода в Object и UndefinedObject 7:

Object>>ifNil: aBlock
   ^self
 UndefinedObject>>ifNil: aBlock
   ^aBlock value.

Альтернативная реализация может развернуть ifNil: в форму эквивалентную, но содержащую явную проверку на nil:

^foo ifNil: ['default']

будет заменено на

^nil == foo ifTrue: ['default'] ifFalse: [foo]

Хотя тут есть подводный камень. Может оказаться, что после макроподстановки на подобии этой, получатель ifNil: вычисляется дважды. Это важно, если получатель — выражение с побочными эффектами, а не переменная. Мы можем использовать другую схему подстановок. Те, кто предпочитает использовать замыкания, сразу предложат подобную схему:

([:tmp | nil == value
   ifTrue: ['default']
   ifFalse: [tmp]]
     value: self stafWithSideEffects)

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

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

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

Подстановка происходит, если селектор УзлаСообщения найден в словаре МакроСелекторов (MacroSelectors) в УзлеСообщения (класс MessageNode). Словарь задаёт соответствие между селекторами, которые будут заменены, и методами УзлаСообщения, которые произведут подстановку. В нашем случае, мы хотим преобразовать такое выражение:

<получатель> ifNil: <блок>.

в

nil == <получатель> ifTrue: <блок>

А это значит, что трансформирующий метод должен построить такое дерево (напомню, что в VW нет броузера способного показать дерево именно так):

УзелУсловия
   условие: УзелСообщения
     получатель: nil
     селектор: #==
     аргументы: <исходный получатель>
   блокИстина: <блок-аргумент ifNil:>
   блокЛожь: <блок с исходныи получателем>.

Производить замену мы должны только в случае, если получатель не имеет побочных эффектов и, если блок-аргумент является литералом. Оказывается, что проверка на побочные эффекты очень проста (именно по этой причине я взял этот пример). В протоколе Проверки (Testing) УзлаПрограммы (ProgramNode) имеется сообщение имеетЭффекты (hasEffects). В УзлеСообщения есть метод, который может удостовериться, что определённый аргумент — это блок литерал с данным числом аргументов. Это всё, что нам нужно, чтобы написать трансформирующий метод:

transformIfNil
   "MacroSelectors at: #ifNil: put: #transformIfNil:"
   ^((self testLiteralBlock: 0 at: 1)
     and: [self receiver hasEffect not])
       ifTrue:
         [ConditionalNode new
           sourcePosition: self sourcePosition;
           condition: (MessageNode new
             receiver: (LiteralNode new value: nil)
             selector: #==
             arguments: (Array with: self receiver))
             trueBlock: arguments first
             falseBlock: (BlockNode new body: self receiver)
             from: self]
           ifFalse: [nil].

Код для регистрации трансформирующего метода в комментарии. Если мы положим наш код в парсел, то регистрацию можно сделать, послезагрузочным действием (post-load), с "зеркальным" действием перед выгрузкой (pre-unload) парсела, чтобы отменить регистрацию. Естественно, "обычные" методы ifNil: в классах Object и UndefinedObject тоже должны быть размещены в парселе, что бы обеспечить работу случаев, когда макроподстановки не происходят.

Чтобы проверить работоспособность нашего кода, добавим следующий метод к любому классу:

foo: anObject
   ^anObject ifNil: [3 + 4].

Теперь посмотрите на декомпилированный код. Должно быть что-то похожее на:

foo: t1
   nil == t1 ifrue: [^3+4].
   ^t1.

Измените метод так, что бы получателем ifNil: стало выражение с побочными эффектами (имело отправку сообщения). Декомпилированный код должен быть похожим на исходный текст.

Ассерты (Squeak)Править

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

  • Использование не должно иметь накладных расходом. Если ассерты отключены, то скомпилированные методы не должны содержать никакого дополнительного кода.
  • Когда ассерты включены, то код ассерта инлайнится в проверяемый метод.
  • При включении/выключении ассертов все методы, содержащие ассерты, автоматически перекомпилируются.
  • При не прохождении ассерта выбрасывается исключение AssertionFailedError.

Несколько лет назад я реализовал подобные возможности для VW 2.0. Там использовался менее понятный синтаксис '(self assert: [...])', и код должен быть обновлён для работы с VW 3.0 и более поздними версиями. Тот механизм подставлял особый тип узла, УзелАссерта, вместо исходной отправки сообщения #assert:. УзелАссерта создавал (или не создавал) инлайненый код проверки.

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

Во-первых, посмотрим как УзелСообщения работает в Squeak. Вместо знакомого нам словаря МакроСелекторов из VW, в Squeak мы видим пять переменных класса: MacroEmmiters, MacroPrinters, MacroSelectors, MacroSizers, MacroTransformers. Во всех них лежат массивы. Как вы помните, в VW Макроселектор из УзлаСообщения содержит словарь селекторов сообщений, которые должны, или могут, быть обработаны особым образом, и селекторов методов выполняющих трансформацию.

В Squeak-е используется похожая, но другая идея. В переменной MacroSelectors лежит массив селекторов, которые могут потребовать дополнительной обработки. Во время инициализации, УзелСообщения ищет свой селектор в этом массиве. Если находит, то запоминает его индекс в переменной экземпляра названной special. Если не находит, то значение переменной выставляется в ноль, что обозначает, что никакой дополнительной обработки не требуется.

При кодогенерации, УзелСообщения должен сделать всё. В отличии от VW, он не строит дополнительные узлы, чтобы делегировать им генерацию кода. Кодогенерации управляется значение переменной special. Если она равна нулю, то создаётся обычная отправка сообщения. Иначе, значение переменной используется как индекс в других четырёх Macro* массивах, для того, чтобы найти селекторы методов, которые отвечают за различные этапы кодогенерации. Например, #ifFalse: — это специальный селектор. Он найден по индексу 2 в переменной MacroSelectors. Метод УзлаСообщения, который отвечает за подготовку узла к кодогенерации это transformIfFalse:. Селектор расположен по индексу 2 в переменной MacroTransformers. Метод, отвечающий за создание байткода — #emitIf:on:value:, хранится по индексу 2 в переменной MacroEmitters.

Кодогенерация в Squeak происходит в три этапа: трансформация, определение размера, генерация.

На этапе трансформации (он начинается при входе в метод #transform:) УзелСообщения определяет действительно ли данная отправка сообщения имеет особое значение и выполняет подготовку. Например, если сообщением является #ifTrue:, но аргумент — это переменная, а не блок-литерал, то узел создаст обычную отправку сообщения. При этом, трансформирующий метод должен вернуть false. Если это происходит, то переменная special сбрасывается в ноль и остальные этапы проходят? как для обычной кодогенерации.

Предположим, что отправка сообщения имеет особый смысл. Метод трансформации при этом возвращает true. До, возврата метод обычно подготавливает и сохраняет вспомогательные объекты, которые участвуют в кодогенерации. Например, сообщение #transformToDo: создаёт УзелПрисваивания для создания кода, который проинициализирует и будет увеличивать переменную, управляющую циклом. Для сохранения этих объектов в УзлеСообщения используется ad-hoc подход. Большинство трансформирующих методов собирают вспомогательные объекты в массив и запихивают их переменную экземпляра аргументы (arguments). Массив либо заменяет либо добавляется к аргументам. На этапе определения размера и создании кода массив должен быть там.

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

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

<условный переход>
 jump ifFalse to L1
 <блок для истины>
 jump to L2
L1:
 <блок для лжи>
L2:

Чтобы создать операторы в вышеприведённом коде, узел должен знать размер блока для истины, чтобы создать первый оператор jump ifFalse, и блока для лжи для безусловного перехода с конца блока для истины в конец выражения. Метод определения размера для ifTrue:ifFalse: в УзлеСообщения вычисляет размер кода проверки условия, блока для истины, блока для лжи. Размеры блоков запоминаются в переменной размеры (sizes), так как они понадобятся нам позже. Из метода возвращается размер всего выражения — сумма размеров проверок условий, обеих условных блоков, и всех задействованных операторов. В УзлеПрограммы есть два метода для определения размера: #sizeForEffect: и #sizeForValue:. Разница очень важна. Любое выражение в Smalltalk-е имеет значение, хотя иногда это значение игнорируется. По этому, каждый узел программы может создавать два типа кода: один — для значения — байткод, выполняющий выражение и оставляющий значение на вершине стека; и другой — для эффекта — приводит стек к тому состоянию, которое было до выполнения выражения. Часто, в конце кода для значения так же как и вконце кода для эффекта ставится инструкция pop. Два разных метода отвечают за определение размера кода в каждом случае.

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

Наконец, когда приходит время генерировать код, сообщение #emitForEffect:on: или #emitForValue:on: посылается узлу. Разница та же, что указано выше. Например, обычная отправка сообщения self foo: 1 "для значения" скомпилируется в:

pushSelf
 push 1
 send #foo:

а "для эффекта" в:

pushSelf
 push 1
 send #foo:
 pop.

Как обычно, чтобы выбрать метод для создания кода в особом случае, используется таблица диспетчеризации MacroEmitters. Аргументами являются два объекта: стек и поток байткодов. Поток байткодов — поток, в который мы будем писать инструкции. Стек — это экземпляр класса СтекРазбора (ParseStack), который вычисляет максимальную глубину стека, которую может затребовать метод. (Максимальная глубина нужна для правильного создания СкомпилированногоМетода).Не вдаваясь в подробности, когда вы создаёте инструкцию pop, нужно послать стеку сообщение pop: 1, когда вы пишете инструкцию pushpush: 1.

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

[<выражение1>.
 <выражение2>] assert

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

<выражение1>.
 <выражение2> ifFalse: [AssertionFailedError signal].

Мы добавим переменную класса ВключатьАссерты (IncludeAssert) в класс УзелСообщения (MessageNode), чтобы запомнить, должны мы инлайнить ассерты или пропускать.

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

transfromAssert: encoder
   (receiver isMemberO: BlockNode) ifFalse: [^false].
   receiver numberOfArguments = 0 ifFalse:
     [^encoder notify: 'Receiver must be a 0-argument literal block'].
   arguments := Array with:
     (MessageNode new
       receiver: (encoder encodeVariable: 'AssertionFailedError')
         selector: #signal
         arguments: #()
         precedence: 3
         from: encoder).
   ^true

Мы создали и сохранили УзелСообщения, соответствующий отправке сообщения AssertionFailedError signal. Позже мы воспользуемся им для кодогенерации. Применяя уже отмеченный ad-hoc стиль, мы запихнули УзелСообщения в переменную arguments, как единственный элемент массива. (Возможно, что не будет ничего плохого, если сохранить узел сам по себе, но само название переменной подразумевает коллекцию.) Затем пишем кодогенератор. (Метод, вычисляющий размер, легче написать потом, когда мы узнаем где именно эти размеры используются).

emitAssert: stack on: stream value: forValue
   IncludeAsserts == false ifTrue: [^self].
   receiver emitForEvaluateValue: stack on: stream.
   self emitBranchOn: true dist: sizes first pop: stack on: stream.
   arguments first emmitForEffect: stack on: stream

Первая строчка простая. Если мы собрались отключить ассерты, то мы сразу выходим прекращая кодогенерацию. Условие вида IncludeAssert == false позволяет любой объект воспринимать, как истина. Что особенно важно, это условие работает, если там будет nil, значение неинициализированной переменной. Это спасает от проблем при изменении инициализатора класса.

Если мы решили, что код нужно инлайнить, мы начнём с генерации кода вычисляющего условие. Нам нужно условие (получатель), чтобы создать код "для значения". Послать emitForValue:on: к условию (блоку) будет не правильно, потому как результат будет равносилен такому коду:

[...] ifFalse: [...].

Вместо этого, мы должны "развернуть" блок и создать код для его содержимого. Для этого, мы пошлем #emitForEvaluatedValue:on: к УзлуБлока (потому что "сообщения", как ifTrue: тоже должны разворачивать блоки, то УзелБлока любезно предоставил этот метод).

Следующее, что мы хотим, это сгенерировать код для выбрасывания исключения AssertionFailedError, и предваряющего это оператора, который перепрыгнет через код выбрасывающий исключения, если значение на вершине стека (значение условия) это истина.

Чтобы создать управляющий оператор, нам нужно знать размер кода выбрасывающего исключение. Мы возьмём воображаемый узел, что бы создать и сохранить этот размер в массиве размеры (sizes) в методе вычисляющем размеры, и сгенерируем условный оператор используя мысленно вычисленный размер. Оператор умирает, если значение на вершине стека, это истина и перепрыгивает sizes first байт вперёд, вероятно как раз в конец выбрасывающего исключение кода. В конце концов, в третей строке мы передаём узлу для кода AssertionFailedError signal, построенному во время трансформации, генерацию байткода выбрасывающего исключение.

Теперь вернёмся к кодогенераторы. Мы ничего не забыли?

В принципе, мы всегда должны генерировать код того типа, который затребован параметром дляЗначения (forValue:). А код, который мы генерируем всегда "для эффекта". Первая часть условного кода оставляет на вершине стека одно булево значение. Оператор перехода поедает это значение в не зависимости от того в дляЗначения истина или ложь. После того, как пыль осядет, в стеке не останется ничего.

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

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

foo := [self check] assert

должно быть обнаружено компилятором и выведено сообщение об ошибке. Насколько тяжело будет реализовать такую проверку?

Всё что нужно, это сообщить об ошибке, если дляЗначения равно истине. Единственная проблема, это то, что узел не знает о том, через какой объект выводить сообщение об ошибке в момент кодогенерации. Предполагается, что все ошибки замечены раннее и выведены через кодировщик (encoder). А кодировщик доступен только на этапах трансформации и вычисления размера, как один из аргументов.

На этапе трансформации мы еще не знаем будет это код "для эффекта" или "для значения". Наилучшее (и единственное) место для подобной проверки, это метод вычисляющий размер кода.

Этот метод имеет еще одну обязанность. Вспомните перекрёсные ссылки. Если мы просто сгенерируем код, как мы сделали выше, то метод, который использует ассерт, будет не определён как отправитель сообщения #assert потому, что не зависимо от того, ассерт инлайнится или игнорируется, сообщение #assert никогда не посылается.

Это легко исправить: отправители определяются по тем экземплярам класса Symbol, которых они имеют в кадре литералов. Если мы сами добавим символ #assert в кадр литералов метода, то метод будет найден, как отправитель сообщения #assert, даже если он на самом деле и не посылает такое сообщение. Так же в кадр литералов мы положим и другой символ — #inlinedAssertionMarker. При изменении свойств ассертов, мы будем искать методы, которые ссылаются на этот символ, чтобы найти и перекомпилировать все методы имеющие ассерты. Поиск ссылок на #assert найдёт больше методов, чем нам нужно, так как сообщение #assert используется в некоторых частях системы.

Ну, и, наконец, метод вычисления размеров:

sizeAssert: encoder value: forValue
   forValue ifTrue:
     [^encoder notify: 'Assertions can be used for effect only'].
   encoder
     litIndex: #assert;
     litIndex: #inlinedAssertionMarker.
   IncludeAsserts == false ifTrue: [^0].
   sizes := Array with: (arguments first sizeForEffect: encoder).
   ^(receiver sizeForEvaluatedValue: encoder)
     + (self sizeBranchOn: true dist: sizes first)
     + sizes first.

Кодировщик (Encoder) отвечает и за отслеживание литералов, так что мы его используем, чтобы добавить литералы к методу. Сообщение #litIndex: возвращает индекс объекта в кадре литералов. Нам он не нужен, так как мы кладём туда символы только как маркеры. В вычислении размеров нет ничего сложного. Метод возвращает общий размер байткода, который мы создаём, включая условие, генератор исключения, и операторы перехода (для вычисления размера оператора перехода используется отдельное сообщение, так как его размер зависит от условного оператора и расстояния к цели). Всё почти готово. Если мы сейчас в метод MessegeNode class>>initialize добавим код, который положит символ #assert в конец массива MacroSelectors, и селекторы методов, которых мы перечислили выше, в конец соответствующих таблиц диспетчеризации, то специальная обработка ассертов должна умереть. Конечно же, мы еще должны создать класс AssertionFailedError. Метод

foo: n
   [n > 0] assert.
   ^3 + 4

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

foo: n
   n > 0 ifFalse: [AssertionFailedError signal].
   ^3 + 4

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

foo: n
   ^3 + 4

Поищем отправителей сообщения #assert — метод есть. Победа? Почти. Попробуйте написать метод, который посылает сообщение #assert к переменной. Такая отправка компилируется, как обычная отправка сообщения. Попробуйте декомпилировать ... ба-бах! Даже если до сих пор мы говорили только о компиляторе, то пришло время сказать пару слов о декомпиляторе.

Декомпилятор (класс Decompiler) сканирует байткоды СкомпилированногоМетода в поисках ряда образцов и восстанавливает дерево грамматического разбора, которое возможно использовалось для создания байткода. Оно не обязательно идентично тому, которое использовалось на самом деле, но оно имеет тот же смысл. Затем дерево разбора печатает себя, выдавая читаемый декомпилированный Smalltalk-овый код.

Это то, для чего используются методы в массиве MacroPrinters. Это метод для красивого форматирования управляющих структур. Интересно, что в действительности нам не нужен метод для инлайненых ассертов как таковых. Когда ассерты инлайнятся, то декомпилятор не создаёт узел для посылки сообщения #assert вообще. Только когда сообщение #assert действительно посылается, то декомпилятор создаёт дерево с УзломСообщения для #assert. Для ассерта вызывается сообщение из MacroPrinters и наша почти поджарившаяся версия прерывается, так как мы не создали нужный метод. Так давайте его сделаем. В нашем случае, достаточно просто выводить отправку сообщения без какого-либо специального форматирования. К моменту вызова метода, получатель уже выведен.

printAssertOn: aStream indent: level
   self
     printKeywords: selector key
     arguments: arguments
     on: aStream
     indent: level

Дальше — дело техники. Добавить методы доступа к переменной IncludeAsserts класса MessageNode, чтобы можно было менять значение флага и перекомпилировать все методы, которые используют ассерты. Ничего особенного — загляните в полную реализацию.

Инлайненный (полностью) ifNil: (VW)Править

Мы только что вышли сухими из воды работая с простой кодогенерацией. Хотя, то, что мы делали через кодогенерацию, может быть сделано, и было сделано в VW на уровне макрорасширений. Достаточно заменить код:

[<...>] assert

на

<...> ifFalse: [AssertionFailedError signal].

Это чисто синтаксическая замена. Даже в Squeak, с его менее "формальными" возможностями чем в VW, мы можем сконструировать дерево разбора для всего выражения ... ifFalse: [AssertionFailedError signal], сохранить его в УзлеСообщения для #assert и делегировать туда кодогенерацию. Мы пошли по другому пути просто для иллюстрации основных моментов относящихся к кодогенерации в Squeak.

Последний пример — это переделка инлайненного ifNil:. Мы последуем другому подходу, будем всегда инлайнить сообщение #ifNil:, независимо от того, есть там побочные эффекты или нет. Реализация будет создавать специальный байткод, такой который мы не сможем произвести через макрорасширения.

В начале, я планировал, что это будет пример для Squeak (что бы соблюдалась пропорция между примерами для VW/Squeak). Во время написания, Эндрю Гринберг (Andrew C.Greenberg) независимо начал работать над инлайненым ifNil: для Squeak-а. Ко времени, когда статья будет готова, его реализация возможно тоже будет готова. Чтобы не дублировать усилия, это будет еще один пример для VW. Еще один плюс — это возможность заглянуть в интересные различия между кодогенерацией в Squeak и VW.

Причиной определения наличия побочных эффектов в начальной реализации #ifNil: была вероятность двойного вычисления кода после расширения. Мы использовали возможности УзлаПрограммы (ProgramNodes) для определения наличия побочных эффектов, и осуществляли трансформацию, только если это было возможно. К сожалению, проверка на наличие побочных эффектов не очень хороша (и не может быть хорошей). Выражения-литералы и ссылки на переменные не имеют побочных эффектов, всё остальное — в первую очередь отправки сообщений — предположительно имеет. Это очень пессимистический, но единственно возможный подход. Что-то вроде:

self name ifNil: [self defaultName]

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

| tmp |
 tmp := <.выражение1>
 tmp == nil ifTrue: [<выражение2>] ifFalse: [tmp].

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

<для значения выражения1>
 dup
 push nil
 send #==
 jump ifFalse to L1
 pop
 <для значения выражения2>
L1:
 ...

В этой реализации ifNil: мы будем придерживаться подобного подхода. Как обычно, в VW мы начинаем с определения класса, который будет представлять узел специального селектора, IfNilNode, и добавляем метод трансформации к УзлуСообщения:

transformIfNil
   "MacroSelectors at: #ifNil: put: #transformIfNil"
   ^(self testLiteralBlock: 0 at: 1)
     ifTrue:
       [IfNilNode new
         baseNode: receiver
         alternativeNode: arguments first]
     ifFalse: [nil].

Пока ничего особенного. IfNilNode запоминает дерево разбора для получателя и аргумент исходного сообщения #ifNil:.

Кодогенерация в VW похожа на кодогенерацию в Squeak — код генерируется узлами дерева разбора. Каждый узел понимает два сообщения #emitValue: и #emitEffect:. Инфраструктура поддержки кодогенерации, тем не менее, в VW лучше. Одна сразу заметная особенность это то, что узлы не заботятся о вычислении размера для создания управляющих операторов. Методы кодогенерации принимают единственный аргумент — поток кода, экземпляр класса ПотокКода (CodeStream). Поток кода — это умный кодогенератор. Он хранит поток байткодов и знает, как кодируются различные инструкции виртуальной машины. Он отслеживает использование стека методом (так что тут не нужен отдельный стековый объект, как в Squeak). Он также отслеживает позиции внутри байткода, чтобы помочь созданию управляющих операторов. Он использует специальный объект, названный МеткаКода (CodeLabel), который отслеживает логические позиции в коде. Адреса перехода управляющих инструкций задаются через метки, а не с использованием явных смещений. Метки создаются ПотокомКода. Сообщение #метка (labelHere), посылаемое к ПотокуКода, возвращает метку, которая помечает текущую позицию в коде. Эту метку, можно использовать позже для создания оператора перехода назад к текущей позиции. Сообщение #новаяМетка (newLabel) возвращает "будущую метку", представляющую еще не определённую позицию для ссылки на перёд. Эта метка может использоваться так же, как и у же определённая метка. Она даёт возможность создавать переходы вперёд. Когда позиция метки достигнута, то к потоку кода посылается сообщение #определить: (define) с этой меткой, как аргументом.

потокКода define: метка.

Поток кода определяет значение метки, чтобы она представляла текущую позицию в коде и исправляет уже сгенерированные инструкции, которые используют только что определённую метку. Иначе говоря, МеткаКода играет роль ассемблерной таблицы символов. Использовать этот механизм намного проще, чем явное вычисление кода в Squeak.

Вот реализация метода IfNilNode>>emitValue:

emitValue: codeStream
   | exit |
   exit := codeStream newLabel.
   baseNode emitValue: codeStream.
   codeStream
     dupFirst; "теперь в стеке два значения"
     pushConstant: nil;
     send: #== numArgs: 1;
     putBranchTo: exit if: false; "оставляем одну копию в стеке"
     pop.
   alternativeNode emitValue: codeStream.
   codeStream define: exit.

Набросок кодогенератора выше простой и понятный. Он использует метку exit для перехода вперёд мимо альтернативного кода. Я не предоставляю отдельного метода emitEffect:. По умолчанию emitEffect: использует метод emitValue:, чтобы создать код "для значения" и затем добавляет к нему инструкцию pop. Довольно неплохо.

В качестве дополнения, в VW есть три инструкции с ``dup в имени. Это dupFirst, dupNext и dupLast. В терминах ``чистых стековых операций dupFirst работает как ``dup, dupNext — ``pop, dup, dupLast, несколько необычно, работает как просто ``pop. Они используются, чтобы закодировать Smalltalk-овые каскады. Так, каскад:

выражение
   метод1;
   метод2;
   метод3.

будет закодирован как (комментарий справа показывает содержимое стека после выполнения каждой инструкции; вершина стека справа):

<выражение ``для значения> ; <знач.выр>
 dupFirst                     ; <знач.выр> <знач.выр>
 send #метод1                 ; <знач.выр> <знач.метода1>
 dupNext                      ; <знач.выр> <знач.выр>
 send #метод2                 ; <знач.выр> <знач.метода2>
 dupLast                      ; <знач.выр>
 send #метод3                 ; <знач.метода3>.

Возможная причина, по которой, вместо комбинации dup и pop используются эти инструкции, это облегчение декомпилятору задачи нахождения каскадов. Кстати, о декомпиляции. Наш заинлайненный ifNil: уже должен работать. Предложенный класс IfNilNode содержит рядовые вещи такие, как переменная экземпляра для хранения основногоУзла (baseNode) и альтернативногоУзла (alternativeNode), и регистрацию метода #transformIfNil: в МакроСелекторах, как трансформатора для #ifNil:. Мы можем посмотреть на байткоды СкомпилированногоМетода с заинлайненным #ifNil:, чтобы удостовериться, что всё правильно. Проблема в том, что мы не можем использовать Декомпилятор на таких методах. Он распознаёт определённые последовательности байткодов. Последовательность, сгенерированная классом IfNilNode не похожа ни на что, и это смущает Декомпилятор. (Похоже, он думает, что это начало каскадирования из-за инструкции dupFirst).

Идеальная реализация должна также включать в себя исправления Декомпилятора, чтобы он корректно распознавал новую последовательность байткодов и правильно создавал дерево разбора. Так как это просто пример, то мы проигнорируем все проблемы с декомпилятором. (Те, кто заинтересуются особенностями работы декомпилятора, могут прочитать комментарии к классу Decompiler и описание переменной экземпляра mustBeSimple в комментариях к классу ByteCodeStream).

Оригинальная статья была опубликована на сайте "Smalltalk Cronicles" в марте 2000 года. Перевод Андрея Собчука, 2003

СноскиПравить

1)...

Хич-хайкер — человек, путешествующий автостопом. Название появилось благодаря книге Путеводитель хитч-хайкера по Галактике — Перев.

2)...

Речь идёт о компиляторе в байт-код, а не машинный код. — Перев.

3)...

Думаю, речь идёт о Дэне Инголсе (Dan Ingalls), который работал с Аланом Кеем над ST, и сейчас активно участвует в разработке Squeak, и Элиоте Миранде (Eliot Miranda), который сейчас работает над VW. — Перев. 4)...

Более подробно об устройстве контекста в VW можно прочитать в статье Элиота Миранды "Context Management in VisualWorks 5i". — Перев.

5)...

В VW7 ничего загружать не нужно. Выберите пункт меню броузера Method->Inspect... 6)... UIUC

The UIUC Smalltalk Archive — http://st-www.cs.uiuc.edu. В настоящее не поддерживается и содержит код только для старых (до 1998г.) диалектов ST. - Перев.

7)...UndefinedObject

В VW7 метод ifNil: уже включен в базовый образ (image). — Перев.

8)...Ассерты

Буду рад более правильному переводу этого и других терминов. Пишите мне. — Перев.

Обнаружено использование расширения AdBlock.


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

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

Также на Фэндоме

Случайная вики