Внутреннее устройство llst, часть 1. Введение в Smalltalk

Доброго времени суток. Предлагаю вашему вниманию вторую статью из цикла о Low Level Smalltalk (LLST). Кто не в курсе о чем идет речь, тем рекомендую прочитать предыдущую, обзорную статью, где рассказывается о том, что такое llst и зачем он был создан.

В этой части мы сконцентрируемся на самом языке Smalltalk, его синтаксисе и «правилах игры».

В последующих частях мы плавно перейдем к особенностям реализации виртуальной машины и внутреннему представлению объектов в памяти. Затронем вопросы организации менеджера памяти и сборщика мусора. Поговорим мы и о байткодах виртуальной машины. Узнаем, как текст метода Smalltalk превращается в последовательность команд. Наконец, мы проследим путь от загрузки образа в память машины до процессов, происходящих при посылке сообщений между объектами, а так же узнаем как реализуются замыкания в блоках.

Введение

Языки программирования бывают разные. Некоторые имеют довольно низкий порог вхождения. Иные же, отпугивают потенциального адепта еще на дальних подступах, ужасая его причудливостью и чуждостью синтаксиса, чрезмерной многословностью повествования, либо сложностью концепций. Есть языки, которые требуют от программиста буквально вывернуть мозг наизнанку, чтобы научиться думать так, как нужно для успешного программирования на таком языке. Некоторые языки только выглядят простыми, реально же требуя от кандидата неслабого багажа знаний из области математики, лямбда исчисления и теории категорий…

Так вот, Smalltalk — простой язык. Простой язык не только в плане синтаксиса, но и в плане понимания его неподготовленным человеком. Неудивительно, что изначально автор позиционировал Smalltalk как язык для обучения детей программированию. Не срослось, к сожалению. Дети предпочитают PHP и бейсик (или что там нынче модно?). Ну да не будем об этом.

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

Мир объектов

Забудьте о Java, забудьте о C++. Забудьте все, чему вас учили.

Фраза «в языке X все есть объект» настолько изъезженная, что я не хотел ее применять здесь. Тем не менее, сложно описать всю глубину этой мысли в отношении Smalltalk-а, не прибегая к подобным штампам.

Действительно, в Smalltalk все — объекты. Строки, числа (впрочем тут есть одно полезное исключение), массивы — это понятно. Но у каждого объекта есть свой класс. Который (сюрприз!) тоже является объектом. И да, у него тоже есть свой класс, который тоже является объектом, и т.д. Методы класса — это тоже объекты. Байткоды методов — ну вы поняли. Даже кусочки кода, представленные в языке т.н. блоками, тоже являются объектами, с каждым из которых можно дружески побеседовать, и он расскажет вам все, что знает.

В описании базового образа LittleSmalltalk есть такое чудесное психоделическое место:

name         subclassOf    instanceOf
Object       MetaObject    nil
Class        MetaClass     Object
MetaObject   Class         Class
MetaClass    Class         MetaObject

Оно говорит нам о том, что:

• класс Object является подклассом MetaObject и инстанцией nil (из небытия явились объекты)
• класс Class является подклассом MetaClass и инстанцией Object (все классы — это тоже объекты)
• класс MetaObject является подклассом Class и его же инстанцией (э…)
• класс MetaClass является подклассом Class инстанцией класса MetaObject (метаклассы — это тоже классы)
• Примечание знатокам: В Little Smalltalk нет класса Behavior.

Взрыв мозга? Ага. Но это единственное место во всей иерархии классов, которое выглядит противоречивым. Оно и есть противоречивое. Но ценой этого маленького маразма достигаются большие возможности.

Это место я привел не для того, чтобы испугать читателя, а чтобы продемонстрировать, что классы и объекты в Smalltalk, подобно даосскому символу «Инь и Ян» представляют собой взаимопроникающие сущности.

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

Образ

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

К примеру: пользователь закрыл текстовый редактор, а затем вернулся к нему спустя некоторое время. Загрузившись из образа он обнаружит, что получил в свое распоряжение систему ровно в том состоянии, в котором он ее оставил. Положение курсора, выделенные области текста, содержимое буфера обмена восстановится в первоначальном виде. Это в корне отличается от модели запуска обычных программ. Данная концепция находит свое продолжение и в современных окружениях рабочего стола, однако, с мой точки зрения, это бледное подобие того, что могло бы быть.

Понятие сообщения

Программирование на языке Smalltalk целиком и полностью сводится к общению с объектами, находящимися в образе. Традиционного редактирования простыни исходных кодов здесь нет. Вернее, оно с успехом заменяется работой во встроенной IDE. Но в основе по прежнему лежит взаимодействие одних объектов с другими.

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

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

Впрочем, проще всего это увидеть на примерах (как запускать можно узнать в первой статье):

->2 + 3
5

Здесь мы взяли объект 2 и отправили ему сообщение + с параметром 3. Результатом сообщения является объект суммы, который был возвращен наружу и отображен командной оболочкой. Это пример бинарного сообщения, в котором задействованы два объекта.

А вот пример унарного сообщения. Давайте спросим у объекта 2, какой класс ему соответствует. Это делается посылкой сообщения class:

->2 class
SmallInt

Отлично. Двойка оказалась объектом класса SmallInt.

А что еще умеют экземпляры класса SmallInt? Давайте спросим:

->SmallInt listMethods
*
+
-
/
<
=
asInteger
asSmallInt
bitAnd:
bitOr:
bitShift:
hash
quo:
rem:
truncSmallInt
SmallInt

Ага. Известный нам оператор + и еще кучка арифметических действий. Чтобы получить эту информацию, мы послали сообщение listMethods классу SmallInt. Это стало возможным потому что класс SmallInt тоже является объектом, которому тоже можно посылать сообщения. А все благодаря вышеописанной «психоделической» хитрости с наследованием. Важно отметить, что посылка сообщений классам и объектам реализуется одним и тем же образом, то есть это один и тот же механизм (без костылей). Классы и объекты действительно сосуществуют рядом и нисколько не мешаются друг другу.

Какие вообще бывают объекты?

Бывают: обычные объекты (являющиеся инстанцией некоторого класса), собственно классы, метаклассы. Метаклассы это такие объекты, что обычные классы являются их инстанциями. Заковыристо, но поначалу можно на это не обращать никакого внимания.

А еще есть true, false и nil. Первые два являются единственными инстанциями классов True и False соответственно. То есть, во всем образе есть только один объект true. Все места, где предполагается возврат или хранение булевого значения, явно или неявно используют эти объекты.

Теперь поговорим о nil. Как вы уже могли догадаться, этот объект представляет собой пустое, не инициализированное (или ошибочное) значение. Вот только, в отличие от нулевого указателя C++ и null из мира Java, nil является полноценным объектом.

Давайте проверим:

-> 1 isNil
false
-> nil isNil
true
-> nil class
Undefined

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

Символы

Еще одним важным видом объектов являются символы. Символ в Smalltalk это объект, похожий по своим свойствам на строку, но, подобно nil, true и false, присутствующий в образе в единственном экземпляре.

Вот так ведут себя обычные строки:

->'hello' = 'hello'
true
->'hello' == 'hello'
false
-> 'hello' + 'World' = 'helloWorld'
true
-> 'hello' + 'World' == 'helloWorld'
false

Здесь оператор = используется для формального сравнения значений двух строк, тогда как оператор == проверяет объекты на идентичность. Оператор == вернет true только в том случае, если объект и переданный параметр — это один и тот же объект. В вышеописанном случае это не так, так как проверяются на идентичность две инстанции класса String, которые создаются одна за другой, но не являются одним и тем же объектом.

А вот что произойдет в случае с символами:

-> #helloWorld = #helloWorld
true
-> #helloWorld == #helloWorld
true
-> ('hello' + 'World') asSymbol == #helloWorld
true

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

Каскадирование сообщений

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

Пробуем:

-> Array parent
Collection
-> Object parent
nil
-> Array parent isNil
false
-> Object parent isNil
true

В этом примере мы сначала выводим предков классов Array и Object, а затем посылаем результату сообщение isNil, для проверки на наличие значения. Класс Object является вершиной иерархии обычных классов, поэтому в ответ на сообщение parent он возвращает nil. Как мы видим, для объединения нескольких сообщений достаточно записать их через пробел. И такие очереди могут быть любой длины:

-> 12
12
-> 12 class
SmallInt
-> 12 class methods
Dictionary (* -> Method, + -> Method, - -> Method, / -> Method, < -> Method, = -> Method, asInteger -> Method, asSmallInt -> Method, bitAnd: -> Method, bitOr: -> Method, bitShift: -> Method, hash -> Method, quo: -> Method, rem: -> Method, truncSmallInt -> Method)
-> 12 class methods keys
OrderedArray (* + - / < = asInteger asSmallInt bitAnd: bitOr: bitShift: hash quo: rem: truncSmallInt)
-> 12 class methods keys size
15

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

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

Ключевые сообщения

На данный момент мы знаем уже два вида сообщений: унарные и бинарные. Еще есть ключевые сообщения, которые могут принимать один или несколько параметров. Возьмем из прошлого примера словарь методов класса SmallInt и спросим, какой ключ лежит под индексом 7:

-> SmallInt methods keys at: 7
asInteger

Здесь мы посылаем объекту keys сообщение #at: с параметром 7. Индексы в Smalltalk отсчитываются с 1, поэтому первый элемент имеет индекс 1 а последний равен размеру контейнера.

Вот еще один пример ключевого сообщения:

-> (Array new: 5) at: 1 put: 42
Array (42 nil nil nil nil)

Сначала мы создали массив, послав сообщение #new: объекту Array с параметром 5, означающим количество элементов. Затем мы поместили в только что созданный массив значение 42 по индексу 1. Получившийся массив был отображен на экране. Обратите внимание, что оставшиеся 4 ячейки заполнены значениями nil.

Замечательной особенностью ключевых сообщений является то, что строка at: 1 put: 42 представляет собой одно параметризованное сообщение #at:put:, а не два, как можно было подумать. В стиле C-подобных языков это можно было записать навроде keys->atPut(1, 42), однако в такой записи теряется соответствие переданных параметров и их назначения.

Допустим, у нас есть некий класс Rectangle, представляющий прямоугольник на некоторой плоскости. В C++ коде мы встретили такие строки:

Rectangle* rect1 = new Rectangle(200, 100);
Rectangle* rect2 = new Rectangle(200, 100, 115, 120, 45);

Как понять, какие числа чему соответствуют? Скажем, в первом случае наш опыт подскажет нам, что скорее всего, речь идет о размерах прямоугольника, и что первый параметр соответствует размеру по X, а второй по Y. Но чтобы это узнать точно, нам необходимо заглянуть в прототип конструктора класса Rectangle. Второй вариант выглядит еще менее читаемым. Разумеется, хороший программист бы и добавил комментариев в код, и изменил бы прототип функции так, чтобы он принимал «говорящие» типы, вроде Point, но речь сейчас не об этом.

Давайте посмотрим, как могла бы выглядеть подобная конструкция на языке Smalltalk:

rect1 <- Rectangle width: 200 height: 100.
rect2 <- Rectangle new
             width: 200;
             height: 100;
             positionX: 115;
             positionY: 120;
             rotationDegrees: 45.

В первом случае мы послали сообщение #width:height: классу Rectangle, который создал инстанцию себя и установил значение соответствующих полей из своих параметров. Во втором случае мы создали инстанцию обычным образом, послав сообщение #new, а затем применили каскадирование сообщений для поочередного задания значений. Обратите внимание, каким наглядным становится код. Нам даже не нужно добавлять комментарии, чтобы читатель понял что происходит.

В принципе, этот код мог бы быть записан и «в лоб», однако выглядит это менее красиво:

"создаем инстанции"
rect1 <- Rectangle width: 200 height: 100.
rect2 <- Rectangle new.

"устанавливаем значения"
rect2 width: 200.
rect2 height: 100.
rect2 positionX: 115.
rect2 positionY: 120.
rect2 rotationDegrees: 45.

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

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

keysAsArray | index result |
    result <- Array new: keys size.
    1 to: keys size do: [ :index | result at: index put: (keys at: index) ].
    ^ result

В теле этого метода мы сначала создаем массив возвращаемых значений, а затем наполняем его содержимым поля keys. Здесь единице передается сообщение #to:do: с двумя параметрами. Первый это keys size, а второй — кусок кода, который надо выполнить (выражение в квадратных скобках). В Smalltalk такие кусочки кода называются блоками. Разумеется, они являются объектами и могут храниться в переменной. Здесь переменной для блока не создается, а он передается сразу по месту использования. Для того чтобы выполнить блок, ему нужно послать сообщение #value, либо #value: если он принимает параметр. Именно это будет делать класс SmallInt в реализации своего метода #to:do:.

В нашем случае блок будет вызван size раз, каждый раз ему будет передаваться номер итерации, который будет интерпретироваться как индекс для выборки значений из keys и их добавления в result.

Синтаксис

На данный момент мы внезапно осознаем, что знаем уже 90% всего синтаксиса Smalltalk. Осталось только прокомментировать отдельные моменты и объяснить назначение тех или иных частей. Чтобы не было совсем скучно, проделаем это на реальном примере кода. Его я нагло позаимствовал из исходников первичного образа. Сначала приведу весь текст целиком, а потом пройдемся по частям и прокомментируем назначение отдельных строк.

METHOD Collection
sort
    ^ self sort: [ :x :y | x < y ]
!

METHOD Collection
sort: criteria | left right mediane |
    (self isEmpty) ifTrue: [^self].

    mediane <- self popFirst.

    left  <- List new.
    right <- List new.
    self do: [ :x |
        (criteria value: x value: mediane)
            ifTrue:  [ left  add: x ]
            ifFalse: [ right add: x ] ].

    left  <- left  sort: criteria.
    right <- right sort: criteria.

    right add: mediane.
    ^ left appendList: right
!

Класс Collection представляет некоторую абстрактную коллекцию элементов. Collection не знает как хранить данные, он лишь предоставляет общие алгоритмы для оперирования ими. Одним из таких алгоритмов является сортировка.

Итак, по проядку:

METHOD Collection
sort
    ^ self sort: [ :x :y | x < y ]
!

Здесь мы объявляем метод сортировки по умолчанию, не принимающий параметров и вызывающий своего напарника — метод #sort: который в качестве параметра принимает блок, сравнивающий два элемента коллекции на основании некоторого критерия. У нас предоставляется критерий по умолчанию: отношение больше-меньше. Хотя, для сложных элементов коллекции никто не запрещает вызывать дополнительные сообщения, навроде x someField < y someField.

Запись [ :x :y | описывает формальные параметры блока, символ ^ — эквивалент return из мира Си. Ключевое слово self используется для посылки сообщения самому себе, super — для посылки своему предку.

Идем дальше:

sort: criteria | left right mediane |
    (self isEmpty) ifTrue: [^self].

    mediane <- self popFirst.

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

sort: criteria
    | left right mediane |

    (self isEmpty) ifTrue: [^self].

    mediane <- self popFirst.

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

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

Конструкция (self isEmpty) ifTrue: [^self] принципиально ничем не отличается от любой другой ей подобной. Круглые скобки здесь не обязательны и вставлены исключительно в декоративных целях. Сначала мы отправляем самому себе сообщение #isEmpty, а затем результату этого действия (одной из инстанций класса Boolean) посылаем сообщение #ifTrue: с параметром блока, который надо выполнить в случае истины.

Последней строкой мы связываем локальную переменную mediane с объектом, который возвращает текущий объект в ответ на сообщение #popFirst. Я намеренно употребил глагол «связываем» вместо «присваиваем», дабы подчеркнуть, что никакого копирования тут не происходит. Все переменные хранят только ссылки на объекты, а не значения. Коллекции тоже хранят ссылки, поэтому мы не должны заботиться о проблемах копирования больших объемов данных. Для явного создания копии объекта предусмотрены отдельные сообщения для полного или поверхностного (нерекурсивного) копирования.

Следующая часть кода, собственно сортировка:

    left  <- List new.
    right <- List new.
    self do: [ :x |
        (criteria value: x value: mediane)
            ifTrue:  [ left  add: x ]
            ifFalse: [ right add: x ] ].

Мы создаем пару списков для хранения элементов, удовлетворяющих и не удовлетворяющих критерию сортировки. Условно мы называем их «левой» и «правой» половинами. Затем мы проходимся по содержимому текущей коллекции (метод #do:), для каждого элемента (x) мы вызываем блок сравнения с медианой и раскладываем элементы по спискам, на основании результата сравнения.

Обратите внимание на то, что блоки, будучи на самом деле отдельными объектами, спокойно обращаются к вышеобъявленным переменным. Так, блок внутри #do: использует переменную mediane, тогда как блок при #ifTrue: ссылается как на переменную x, так и на left, объявленную еще выше по иерархии. Это становится возможным благодаря тому, что блоки в Smalltalk являются замыканиями и завязаны на лексический контекст своего использования.

Наконец, остаток метода:

    left  <- left  sort: criteria.
    right <- right sort: criteria.

    right add: mediane.
    ^ left appendList: right

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

Посмотрим теперь, как можно использовать сортировку:

"простая сортировка"
-> #(13 0 -6 221 64 7 -273 42 1024) sort
Array (-273 -6 0 7 13 42 64 221 1024)

"сортировка по убыванию"
-> #(13 0 -6 221 64 7 -273 42 1024) sort: [ :x :y | x > y ]
Array (1024 221 64 42 13 7 0 -6 -273)

"лексикографическая сортировка"
-> #(13 0 -6 221 64 7 -273 42 1024) sort: [ :x :y | x asString < y asString ]
Array (-273 -6 0 1024 13 221 42 64 7)

"сортировка по длине строчного представления"
-> #(13 0 -6 221 64 7 -273 42 1024) sort: [ :x :y | x asString size < y asString size ]
Array (7 0 13 -6 42 64 221 1024 -273)

"разбиение строки на слова"
->'а вообще, мне очень нравится этот язык!' words
List (а вообще, мне очень нравится этот язык!)

"разбиение строки на слова и сортировка по длине слова"
->'а вообще, мне очень нравится этот язык!' words sort: [ :x :y | x size < y size ]
List (а мне этот язык! очень вообще, нравится)

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

Списки

Пару слов необходимо сказать и о контейнере List, который на самом деле является потомком Collection и хранит данные в виде однонаправленного списка, представленного цепочкой объектов. При этом голова списка хранится у него в поле, а дальше каждый следующий элемент (инстанция класса Link) ссылается на хранимый объект и на следующий элемент списка.

Поэтому, наиболее быстро добавлять данные в голову списка:

METHOD List
add: anElement
    elements <- Link value: anElement next: elements.
    ^ anElement
!

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

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

METHOD List
addLast: anElement
    elements isNil
        ifTrue:  [ self add: anElement ]
        ifFalse: [ elements addLast: anElement ].
    ^ anElement
!

METHOD Link
addLast: anElement
    next notNil
        ifTrue:  [ ^ next addLast: anElement ]
        ifFalse: [ next <- Link value: anElement ]
!

В этом смысле списки Smalltalk напоминают соответствующие структуры в языке Haskell (разумеется за вычетом требования гомогенности списка в Haskell). При этом оператор : соответствует #add:, а оператор ++ соответствует #addLast:.

Наконец, метод #appendList: быстро связывает два списка в один. Он находит конец первого списка и приклеивает к нему второй:

METHOD List
appendList: aList | element |
    (elements isNil)
        ifTrue: [ elements <- aList firstLink. ^self ].

    element <- elements.
    [element next isNil]
        whileFalse: [element <- element next].
    element next: aList firstLink.

    ^self
!

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

Заключение

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

Продолжение следует :)

P.S.: Хабрачеловек sheknitrtch сделал патч, позволяющий компилировать llst на MSVC10, за что ему большое спасибо. Если кто-либо желает сделать билд для размещения в downloads — просьба стучаться в личку.