Статический анализ (продолжение)

Оригинал: Static Analysis
Автор: Leah Hanson
Дата публикации: 22 сентября 2015
Перевод: Н.Ромоданов
Дата перевода: июль 2016 г.

Это продолжение статьи. Начало смотрите здесь

Интроспекция в языке Julia

Язык Julia облегчает выполнение интроспекции. Есть четыре встроенные функции, которые позволят увидеть нам то, о чем думает компилятор: code_lowered, code_typed, code_llvm и code_native. Они перечислены в том порядке, в каком следуют стадии процесса компиляции; первая ближе к тому коду, который мы вводим, а последняя ближе к тому коду, который работает в процессоре компьютера. В данной главе мы сосредоточимся на использовании функции code_typed, которая даст нам оптимизированное абстрактное синтаксическое дерево (AST - abstract syntax tree), выведенное из имеющихся типов.

Функция code_typed использует два аргумента: функцию, которой мы интересуемся, и кортеж типов аргументов. Например, если мы хотим, чтобы увидеть дерево AST для функции foo, когда она вызывается с двумя аргументами Int64, то нам нужно будет вызвать code_typed(foo, (Int64,Int64)).

function foo(x,y)
  z = x + y
  return 2 * z
end

code_typed(foo,(Int64,Int64))

Ниже показана структура, которую возвратит функция code_typed:

1-element Array{Any,1}: :($(Expr(:lambda, {:x,:y}, {{:z},{{:x,Int64,0},{:y,Int64,0},{:z,Int64,18}},{}}, :(begin # none, line 2: z = (top(box))(Int64,(top(add_int))(x::Int64,y::Int64))::Int64 # line 3: return (top(box))(Int64,(top(mul_int))(2,z::Int64))::Int64 end::Int64))))

Это массив Array; функция code_typed может вернуть несколько подходящих методов. Некоторые комбинации функций и типов аргументов могут не полностью определять, какой метод должен быть вызван. Например, вы могли бы в качестве типа передать тип Any (а не тип Int64). Тип Any является типом, который находится в самом верху иерархии типов; все типы являются подтипами типа Any (в том числе и сам тип Any). Если мы включили тип Any в наш кортеж типов аргументов и есть несколько соответствующих методов, соответствующих, то в типе /code>Array из code_typed должно быть более одного элемента; должно быть по одному элементу для каждого подходящего метода.

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

julia> e = code_typed(foo,(Int64,Int64))[1] :($(Expr(:lambda, {:x,:y}, {{:z},{{:x,Int64,0},{:y,Int64,0},{:z,Int64,18}},{}}, :(begin # none, line 2: z = (top(box))(Int64,(top(add_int))(x::Int64,y::Int64))::Int64 # line 3: return (top(box))(Int64,(top(mul_int))(2,z::Int64))::Int64 end::Int64))))

Структура, которой мы интересуемся, находится внутри массива Array: это структура Expr. В языке Julia структура Expr (сокращение от expression - выражение) используется для представления дерева AST. (AST или абстрактное синтаксическое дерево – это то, как компилятор представляет себе организацию кода, это вроде того, как если бы вы пользовались диаграммой структуры предложений в начальной школе). Expr, которое мы получили, представляет собой один метод. В нем есть некоторые метаданные (описывающие переменные, которые есть в методе) и выражения, которые составляют тело метода.

Теперь мы можем задать несколько вопросов, касающихся e.

Мы можем спросить, какие свойства из Expr используются функцией names. Функция names, который работает для любого значения иои типа языка Julia, возвращает массив Array имен, определенных для указанного типа (или типа значения).

julia> names(e)
3-element Array{Symbol,1}:
 :head
 :args
 :typ

Мы просто спросили о том, какие в e есть имена, и теперь мы можем спросить, какое значение соответствует каждому имени. В Expr указываются три свойства: head, typ и args.

julia> e.head :lambda julia> e.typ Any julia> e.args 3-element Array{Any,1}: {:x,:y} {{:z},{{:x,Int64,0},{:y,Int64,0},{:z,Int64,18}},{}} :(begin # none, line 2: z = (top(box))(Int64,(top(add_int))(x::Int64,y::Int64))::Int64 # line 3: return (top(box))(Int64,(top(mul_int))(2,z::Int64))::Int64 end::Int64)

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

• Свойство head указывает на то, какого вида выражение; обычно, вы для этого должны использовать в языке Julia отдельные типы данных, но тип Expr является типом данных, с помощью которого моделируется структура, используемая в синтаксическом анализаторе. Синтаксический анализатор написан на диалекте языка Scheme, в котором все структуры представлены как вложенные списки. Свойство head рассказывает нам о том, как организована остальная часть Expr и какие выражения там представлены.
• Свойство typ является выведенным типом значения, которое возвращается выражением; когда мы выполняем оценку какого-либо выражения, то результат возвращается в виде некоторого значения. typ является типом значения, которое является оценкой выражения. Почти для всех выражений Expr это значение будет иметь тип Any (что всегда будет корректно, поскольку любой возможный тип является подтипом типа Any). Только значение body для методов с выводимыми типами и большинство выражений внутри них будут иметь значение typ, указывающее на что-нибудь более конкретное. (Потому что type это ключевое слово, и для данного поля нельзя в качестве имени поля использовать это слово).
• Свойство args является наиболее сложной частью Expr; его структура варьируется в зависимости от значения свойства head. Это всегда массив типа Array{Any} (нетипизированный массив), но за пределами, что изменения структуры.

В выражении Expr, представляющем метод, в e.args имеются три элемента:

julia> e.args[1] # names of arguments as symbols
2-element Array{Any,1}:
 :x
 :y

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

julia> e.args[2] # three lists of variable metadata 3-element Array{Any,1}: {:z} {{:x,Int64,0},{:y,Int64,0},{:z,Int64,18}} {}

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

julia> e.args[3] # the body of the method :(begin # none, line 2: z = (top(box))(Int64,(top(add_int))(x::Int64,y::Int64))::Int64 # line 3: return (top(box))(Int64,(top(mul_int))(2,z::Int64))::Int64 end::Int64)

Первые два элемента args являются метаданными третьего элемента. Хотя метаданные очень интересны, они сейчас нам непосредственно не нужны. Важной частью является тело метода, которое является третьим элементом. Это еще одно выражение Expr.

julia> body = e.args[3] :(begin # none, line 2: z = (top(box))(Int64,(top(add_int))(x::Int64,y::Int64))::Int64 # line 3: return (top(box))(Int64,(top(mul_int))(2,z::Int64))::Int64 end::Int64) julia> body.head :body

Тип typ является выведенным типом, возвращаемым методом.

julia> body.args 4-element Array{Any,1}: :( # none, line 2:) :(z = (top(box))(Int64,(top(add_int))(x::Int64,y::Int64))::Int64) :( # line 3:) :(return (top(box))(Int64,(top(mul_int))(2,z::Int64))::Int64)

В args содержится список выражений: список выражений тела метода. Есть несколько аннотаций с номерами строк (то есть, :( # line 3:)), но большая часть тела представляет собой задание значения z (z = x + y) и возврат значения 2 * z. Обратите внимание, что эти операции были заменены внутренними инструкциями, специальными для типа Int64. Выражение top(function-name) указывает внутреннюю функцию; это то, что реализуется на этапе генерации кода языка Julia, а не в самом языке Julia.

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

julia> function lloop(x)
         for x = 1:100
           x *= 2
         end
       end
lloop (generic-функция с 1 методом)

julia> code_typed(lloop, (Int,))[1].args[3] :(begin # none, line 2: #s120 = $(Expr(:new, UnitRange{Int64}, 1, :(((top(getfield))(Intrinsics, :select_value))((top(sle_int))(1,100)::Bool,100,(top(box))(Int64,(top( sub_int))(1,1))::Int64)::Int64)))::UnitRange{Int64} #s119 = (top(getfield))(#s120::UnitRange{Int64},:start)::Int64 unless (top(box))(Bool,(top(not_int))(#s119::Int64 === (top(box))(Int64,(top( add_int))((top(getfield)) (#s120::UnitRange{Int64},:stop)::Int64,1))::Int64::Bool))::Bool goto 1 2: _var0 = #s119::Int64 _var1 = (top(box))(Int64,(top(add_int))(#s119::Int64,1))::Int64 x = _var0::Int64 #s119 = _var1::Int64 # line 3: x = (top(box))(Int64,(top(mul_int))(x::Int64,2))::Int64 3: unless (top(box))(Bool,(top(not_int))((top(box))(Bool,(top(not_int)) (#s119::Int64 === (top(box))(Int64,(top(add_int))((top(getfield))( #s120::UnitRange{Int64},:stop)::Int64,1))::Int64::Bool))::Bool))::Bool goto 2 1: 0: return end::Nothing)

Вы заметите, что в теле нет циклов for или while. Поскольку компилятор преобразует код из того, что мы написали в двоичные инструкции, которые понимает процессор, удаляется все, что пригодилось бы человеку, но что непонятно процессором (например, циклы). Цикл будет переписан в виде выражений label и goto. В goto имеется номер; каждая метка label также имеет номер. goto осуществляет переход на метку label с тем же самым номером.

Продолжение статьи смотрите здесь

---

---