Julia ASTs

Джулия имеет два представления кода. Сначала есть синтаксическое дерево (AST), возвращаемое парсером (например, функция Meta.parse), и манипулируемое макросами. Это структурированное представление кода, как он написан, построенное с помощью julia-parser.scm из потока символов. Затем есть пониженная форма, или IR (промежуточное представление), которая используется для вывода типов и генерации кода. В пониженной форме меньше типов узлов, все макросы развернуты, и все потоки управления преобразованы в явные ветвления и последовательности операторов. Пониженная форма строится с помощью julia-syntax.scm.

Сначала мы сосредоточимся на AST, так как он необходим для написания макросов.

Surface syntax AST

Фронтенд ASTs состоят почти полностью из Expr и атомов (например, символов, чисел). Обычно для каждой визуально отличительной синтаксической формы существует различная голова выражения. Примеры будут приведены в синтаксисе s-выражений. Каждый список в скобках соответствует Expr, где первый элемент - это голова. Например, (call f x) соответствует Expr(:call, :f, :x) в Julia.

Calls

do синтаксис:

f(x) do a,b
    body
end

разбирается как (do (call f x) (-> (tuple a b) (block body))).

Operators

Большинство использований операторов — это просто вызовы функций, поэтому они разбираются с заголовком call. Однако некоторые операторы являются специальными формами (не обязательно вызовами функций), и в этих случаях сам оператор является заголовком выражения. В julia-parser.scm они называются "синтаксическими операторами". Некоторые операторы (+ и *) используют N-арное разбор; цепочные вызовы разбираются как единый N-арный вызов. Наконец, цепочки сравнений имеют свою собственную специальную структуру выражения.

Bracketed forms

Macros

Strings

Синтаксис строк документации:

"some docs"
f(x) = x

разбирается как (macrocall (|.| Core '@doc) (line) "некоторые документы" (= (call f x) (block x))).

Imports and such

using имеет такое же представление, как import, но с заголовком выражения :using вместо :import.

Numbers

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

Block forms

Блок операторов разбирается как (block stmt1 stmt2 ...).

Если оператор:

if a
    b
elseif c
    d
else
    e
end

разбирается как:

(if a (block (line 2) b)
    (elseif (block (line 3) c) (block (line 4) d)
            (block (line 6 e))))

Цикл while разбирается как (while условие тело).

Цикл for разбирается как (for (= var iter) body). Если есть более одной спецификации итерации, они разбираются как блок: (for (block (= v1 iter1) (= v2 iter2)) body).

break и continue интерпретируются как выражения без аргументов (break) и (continue).

let разбирается как (let (= var val) body) или (let (block (= var1 val1) (= var2 val2) ...) body), как и циклы for.

Базовое определение функции разбирается как (function (call f x) body). Более сложный пример:

function f(x::T; k = 1) where T
    return x+1
end

разбирается как:

(function (where (call f (parameters (kw k 1))
                       (:: x T))
                 T)
          (block (line 2) (return (call + x 1))))

Определение типа:

mutable struct Foo{T<:S}
    x::T
end

разбирается как:

(struct true (curly Foo (<: T S))
        (block (line 2) (:: x T)))

Первый аргумент - это булево значение, указывающее, является ли тип изменяемым.

try блоки разбираются как (try try_block var catch_block finally_block). Если после catch нет переменной, то var равно #f. Если нет finally клаузулы, то последний аргумент отсутствует.

Quote expressions

Синтаксические формы исходного кода Julia для цитирования кода (quote и :( )) поддерживают интерполяцию с помощью $. В терминологии Lisp это означает, что они на самом деле являются формами "обратной кавычки" или "квазицитаты". Внутренне также существует необходимость в цитировании кода без интерполяции. В схеме кода Julia неинтерполирующая цитата представлена с помощью заголовка выражения inert.

inert выражения преобразуются в объекты QuoteNode Julia. Эти объекты оборачивают одно значение любого типа, и при оценке просто возвращают это значение.

Выражение quote, аргументом которого является атом, также преобразуется в QuoteNode.

Line numbers

Информация о местоположении источника представлена в виде (line line_num file_name), где третий компонент является необязательным (и опускается, когда изменяется только номер текущей строки, но не имя файла).

Эти выражения представлены как LineNumberNode в Julia.

Macros

Макро-гигиена представлена через выражение head pair escape и hygienic-scope. Результат расширения макроса автоматически оборачивается в (hygienic-scope block module), чтобы представить результат новой области видимости. Пользователь может вставить (escape block) внутрь, чтобы интерполировать код из вызывающего контекста.

Lowered form

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

В дополнение к Symbol и некоторым числовым типам, в пониженном виде существуют следующие типы данных:

• Expr

  Имеет тип узла, указанный полем head, и поле args, которое является Vector{Any} подвыражений. Хотя почти каждая часть поверхностного AST представлена Expr, IR использует только ограниченное количество Expr, в основном для вызовов и некоторых форм, доступных только на верхнем уровне.

• НомерСлота

  Идентифицирует аргументы и локальные переменные последовательной нумерацией. У него есть целочисленное поле id, указывающее индекс слота. Типы этих слотов можно найти в поле slottypes их объекта CodeInfo.

• Аргумент

  То же самое, что и SlotNumber, но появляется только после оптимизации. Указывает на то, что ссылающийся слот является аргументом окружающей функции.

• CodeInfo

  Оборачивает IR группы операторов. Его поле code является массивом выражений для выполнения.

• GotoNode

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

• GotoIfNot

  Условная ветвь. Если поле cond оценивается как ложное, переходит к индексу, указанному в поле dest.

• ReturnNode

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

• QuoteNode

  Оборачивает произвольное значение для ссылки в качестве данных. Например, функция f() = :a содержит QuoteNode, поле value которого является символом a, чтобы вернуть сам символ вместо его вычисления.

• GlobalRef

  Ссылается на глобальную переменную name в модуле mod.

• SSAValue

  Относится к последовательно пронумерованной (начиная с 1) статической переменной единственного присваивания (SSA), вставленной компилятором. Номер (id) SSAValue — это индекс массива кода выражения, значение которого он представляет.

• NewvarNode

  Отмечает точку, где создается переменная (слот). Это приводит к сбросу переменной в неопределенное состояние.

Expr types

Эти символы появляются в поле head Expr в нижнем регистре.

• call

  Вызов функции (динамическая диспетчеризация). args[1] — это функция для вызова, args[2:end] — это аргументы.

• invoke

  Вызов функции (статическая диспетчеризация). args[1] — это экземпляр метода, который нужно вызвать, args[2:end] — это аргументы (включая вызываемую функцию, которая находится в args[2]).

• статический_параметр

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

• =

  Задание. В IR первый аргумент всегда является SlotNumber или GlobalRef.

• метод

  Добавляет метод к обобщенной функции и при необходимости присваивает результат.

  Имеет форму с 1 аргументом и форму с 3 аргументами. Форма с 1 аргументом возникает из синтаксиса function foo end. В форме с 1 аргументом аргумент является символом. Если этот символ уже называет функцию в текущей области видимости, ничего не происходит. Если символ не определен, создается новая функция и присваивается идентификатору, указанному символом. Если символ определен, но называет не функцию, возникает ошибка. Определение "называет функцию" заключается в том, что связывание является постоянным и ссылается на объект с уникальным типом. Обоснование этого заключается в том, что экземпляр уникального типа однозначно идентифицирует тип, к которому нужно добавить метод. Когда тип имеет поля, не было бы ясно, добавляется ли метод к экземпляру или его типу.

  Форма с 3 аргументами имеет следующие аргументы:

  • args[1]

    Имя функции или nothing, если неизвестно или не нужно. Если это символ, то выражение сначала ведет себя как форма с 1 аргументом выше. Этот аргумент игнорируется с этого момента. Он может быть nothing, когда методы добавляются строго по типу, (::T)(x) = x, или когда метод добавляется к существующей функции, MyModule.f(x) = x.

  • args[2]

    SimpleVector аргумента типа данных. args[2][1] является SimpleVector типов аргументов, а args[2][2] является SimpleVector переменных типа, соответствующих статическим параметрам метода.

  • args[3]

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

• struct_type

  Выражение с 7 аргументами, которое определяет новую struct:

  • args[1]

    Имя struct

  • args[2]

    Выражение call, которое создает SimpleVector, указывая его параметры

  • args[3]

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

  • args[4]

    Symbol, GlobalRef или Expr, указывающий на суперкласс (например, :Integer, GlobalRef(Core, :Any) или :(Core.apply_type(AbstractArray, T, N)))

  • args[5]

    call выражение, которое создает SimpleVector, указывая его типы полей

  • args[6]

    Булев, истинный, если mutable

  • args[7]

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

• abstract_type

  Выражение с 3 аргументами, которое определяет новый абстрактный тип. Аргументы такие же, как аргументы 1, 2 и 4 выражений struct_type.

• примитивный_тип

  4-аргументное выражение, которое определяет новый примитивный тип. Аргументы 1, 2 и 4 такие же, как struct_type. Аргумент 3 - это количество бит.

  Julia 1.5

  struct_type, abstract_type и primitive_type были удалены в Julia 1.5 и заменены вызовами новых встроенных функций.

• глобальный

  Объявляет глобальную привязку.

• const

  Объявляет (глобальную) переменную как константу.

• новый

  Выделяет новый объект, похожий на структуру. Первый аргумент - это тип. Псевдо-функция new преобразуется в это, и тип всегда вставляется компилятором. Это в значительной степени является внутренней функцией и не выполняет проверок. Оценка произвольных выражений new может легко привести к ошибке сегментации.

• splatnew

  Похоже на new, за исключением того, что значения полей передаются в виде одного кортежа. Работает аналогично splat(new), если бы new был функцией первого класса, отсюда и название.

• isdefined

  Expr(:isdefined, :x) возвращает Bool, указывающий, было ли x уже определено в текущей области видимости.

• the_exception

  Возвращает пойманное исключение внутри блока catch, как возвращается jl_current_exception(ct).

• ввод

  Входит в обработчик исключений (setjmp). args[1] — это метка блока catch, к которому нужно перейти в случае ошибки. Возвращает токен, который будет использован pop_exception.

• leave

  Извлеките обработчики исключений. args[1] — это количество обрабатывателей, которые нужно извлечь.

• pop_exception

  Восстановите стек текущих исключений до состояния, соответствующего enter, при выходе из блока catch. args[1] содержит токен из связанного enter.

  Julia 1.1

  pop_exception новый в Julia 1.1.

• inbounds

  Управляет включением или отключением проверок границ. Поддерживается стек; если первый аргумент этого выражения истинный или ложный (true означает, что проверки границ отключены), он помещается в стек. Если первый аргумент равен :pop, стек извлекается.

• boundscheck

  Имеет значение false, если встроен в раздел кода, помеченный @inbounds, в противном случае имеет значение true.

• loopinfo

  Отмечает конец цикла. Содержит метаданные, которые передаются в LowerSimdLoop, чтобы либо отметить внутренний цикл выражения @simd, либо передать информацию в проходы циклов LLVM.

• copyast

  Часть реализации квази-цитаты. Аргумент — это AST синтаксиса поверхности, который просто копируется рекурсивно и возвращается во время выполнения.

• мета

  Метаданные. args[1] обычно является символом, указывающим на вид метаданных, а остальные аргументы являются произвольными. Следующие виды метаданных обычно используются:

  • :inline и :noinline: Подсказки для инлайнинга.

• foreigncall

  Статически вычисляемый контейнер для информации о ccall. Поля:

  • args[1] : имя

    Выражение, которое будет разобрано для внешней функции.

  • args[2]::Type : RT

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

  • args[3]::SimpleVector (типы) : AT

    Вектор (литеральный) типов аргументов, вычисляемый статически, когда был определен содержащий метод.

  • args[4]::Int : nreq

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

  • args[5]::QuoteNode{Symbol} : соглашение о вызове

    Конвенция вызова для вызова.

  • args[6:5+length(args[3])] : аргументы

    Значения для всех аргументов (с типами каждого, указанными в args[3]).

  • args[6+length(args[3])+1:end] : gc-корни

    Дополнительные объекты, которые могут потребоваться для gc-rooted на время вызова. См. Working with LLVM для информации о том, откуда они происходят и как с ними работают.

• new_opaque_closure

  Создает новое непрозрачное замыкание. Поля:

  • args[1] : подпись

    Подпись функции непрозрачного замыкания. Непрозрачные замыкания не участвуют в диспетчеризации, но типы входных данных могут быть ограничены.

  • args[2] : isva

    Указывает, принимает ли замыкание varargs.

  • args[3] : lb

    Нижняя граница на тип вывода. (По умолчанию Union{})

  • args[4] : ub

    Верхняя граница на тип вывода. (По умолчанию Any)

  • args[5] : метод

    Фактический метод в виде выражения opaque_closure_method.

  • args[6:end] : захватывает

    Значения, захваченные непрозрачным замыканием.

  Julia 1.7

  Непрозрачные замыкания были добавлены в Julia 1.7

Method

Уникальный контейнер, описывающий общие метаданные для одного метода.

• имя, модуль, файл, строка, подпись

  Метаданные для уникальной идентификации метода как для компьютера, так и для человека.

• амбиг

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

• специализации

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

• source

  Исходный код (если доступен, обычно сжатый).

• генератор

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

• корни

  Указатели на не-AST вещи, которые были интерполированы в AST, необходимые для сжатия AST, вывода типов или генерации нативного кода.

• nargs, isva, called, is_for_opaque_closure,

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

• primary_world

  Возраст мира, который "владеет" этим методом.

MethodInstance

Уникальный контейнер, описывающий единую вызываемую сигнатуру для метода. Обратите внимание на Proper maintenance and care of multi-threading locks для получения важной информации о том, как безопасно изменять эти поля.

• specTypes

  Основной ключ для этого MethodInstance. Уникальность гарантируется через поиск def.specializations.

• def

  Метод, который описывает эта функция, является специализацией. Или Модуль, если это верхнеуровневый Лямбда, расширенный в Модуле, и который не является частью Метода.

• sparam_vals

  Значения статических параметров в specTypes. Для MethodInstance в Method.unspecialized это пустой SimpleVector. Но для экземпляра MethodInstance во время выполнения из кэша MethodTable это всегда будет определено и индексируемо.

• невыведенный

  Исходный код верхнего уровня для thunk без сжатия. Кроме того, для сгенерированной функции это одно из многих мест, где может быть найден исходный код.

• обратные ребра

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

• кэш

  Кэш объектов CodeInstance, которые используют эту инстанциацию шаблона.

CodeInstance

• def

  MethodInstance, от которого происходит эта запись кэша.

• владелец

  Токен, который представляет владельца этого CodeInstance. Будет использоваться jl_egal для сопоставления.

• rettype/rettype_const

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

• выведенный

  Может содержать кэш выведенного источника для этой функции, или может быть установлен в nothing, чтобы просто указать, что rettype выведен.

• ftpr

  Универсальная точка входа jlcall.

• jlcall_api

  ABI, который следует использовать при вызове fptr. Некоторые значимые из них включают:

  • 0 - Еще не скомпилировано
  • 1 - JL_CALLABLE jl_value_t *(*)(jl_function_t *f, jl_value_t *args[nargs], uint32_t nargs)
  • 2 - Константа (значение, хранящееся в rettype_const)
  • 3 - С переданными статическими параметрами jl_value_t *(*)(jl_svec_t *sparams, jl_function_t *f, jl_value_t *args[nargs], uint32_t nargs)
  • 4 - Запустите в интерпретаторе jl_value_t *(*)(jl_method_instance_t *meth, jl_function_t *f, jl_value_t *args[nargs], uint32_t nargs)

• min_world / max_world

  Диапазон мировых возрастов, для которых этот экземпляр метода может быть вызван. Если max_world - это специальное значение токена -1, значение еще не известно. Он может продолжать использоваться, пока мы не столкнемся с обратной связью, которая требует от нас пересмотра.

CodeInfo

Временный контейнер для хранения пониженного исходного кода.

• код

  Массив утверждений Any

• slotnames

  Массив символов, дающий имена для каждого слота (аргумента или локальной переменной).

• slotflags

  Массив UInt8 свойств слотов, представленный в виде битовых флагов:

  • 0x02 - назначен (только ложь, если нет операторов присваивания с этой переменной слева)
  • 0x08 - использован (если есть чтение или запись слота)
  • 0x10 - статически назначено один раз
  • 0x20 - может быть использован до присвоения. Этот флаг действителен только после вывода типа.

• ssavaluetypes

  Либо массив, либо Int.

  Если это Int, он указывает количество временных мест, вставленных компилятором, в функции (длина массива code). Если это массив, он указывает тип для каждого места.

• ssaflags

  Флаги на уровне операторов 32 бита для каждого выражения в функции. См. определение jl_code_info_t в julia.h для получения дополнительной информации.

• linetable

  Массив объектов местоположения источника

• codelocs

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

Дополнительные поля:

• slottypes

  Массив типов для слотов.

• rettype

  Выведенный тип возвращаемого значения пониженнной формы (IR). Значение по умолчанию — Any.

• method_for_inference_limit_heuristics

  Метод method_for_inference_heuristics расширит генератор данного метода, если это необходимо во время вывода.

• родитель

  MethodInstance, который "владеет" этим объектом (если применимо).

• edges

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

• min_world/max_world

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

Булевы свойства:

• выведенный

  Будет ли это произведено с помощью вывода типов.

• inlineable

  Должно ли это быть допустимо для инлайнинга.

• propagate_inbounds

  Следует ли это распространять @inbounds, когда оно встроено с целью исключения блоков @boundscheck.

UInt8 настройки:

• constprop

  • 0 = использовать эвристику
  • 1 = агрессивный
  • 2 = none

• purity Состоит из 5 битовых флагов:

  • 0x01 << 0 = этот метод гарантированно вернет или завершится последовательно (:consistent)
  • 0x01 << 1 = этот метод свободен от внешне семантически видимых побочных эффектов (:effect_free)
  • 0x01 << 2 = этот метод гарантированно не вызовет исключение (:nothrow)
  • 0x01 << 3 = этот метод гарантированно завершится (:terminates_globally)
  • 0x01 << 4 = синтаксический контроль потока внутри этого метода гарантированно завершится (:terminates_locally)

  Смотрите документацию Base.@assume_effects для получения дополнительных сведений.