Pull to refresh

Язык Terra — низкоуровневый партнёр Lua

Reading time 12 min
Views 17K
Original author: Zachary DeVito
Terra — низкоуровневый язык системного программмирования, встраиваемый и имеющий возможность метапрограммирования с помощью языка Lua.


-- Это обычный код на Lua
function printhello()
    -- Это обычная функция Lua
    print("Hello, Lua!")
end
printhello()

-- Terra обратно совместим с C, мы будем использовать библиотеку C в нашем примере
C = terralib.includec("stdio.h")

-- Ключевое слово 'terra' вводит новую функцию
terra hello(argc : int, argv : &rawstring)
    -- Здесь мы вызываем функцию C из Terra
    C.printf("Hello, Terra!\n")
    return 0
end

-- Вы можете вызвать функцию Terra прямо из Lua, она компилируется JIT
-- используя LLVM для создания машинного кода
hello(0,nil)

-- Функции Terra являются значениями первого класса в Lua, и могут участвовать в интроспекции
-- и использоваться в метапрограммировании
hello:disas()
--[[ output:
    assembly for function at address 0x60e6010
    0x60e6010(+0):		push	rax
    0x60e6011(+1):		movabs	rdi, 102129664
    0x60e601b(+11):		movabs	rax, 140735712154681
    0x60e6025(+21):		call	rax
    0x60e6027(+23):		xor	eax, eax
    0x60e6029(+25):		pop	rdx
    0x60e602a(+26):		ret
]]

-- Вы можете сохранить код на Terra как исполняемый, как объектный файл,или как разделяемую библиотеку
-- и слинковать его с существующими программами
terralib.saveobj("helloterra",{ main = hello })

Как и C/C++, язык Terra статически типизируемый, компилируемый язык с «ручным» управлением памятью. В отличие от C/C++, он изначально спроектирован для метапрограммирования с помощью Lua.

Terra спроектирован на основе того факта, что C/C++ на самом деле состоит из множества “языков.” Есть ядро языка, состоящее из операторов, управления потоком исполнения и вызова функций, но окружающий его язык, это метаязык, составленный из смеси разных вещей, таких, как препроцессор, шаблоны, объявления структур. Шаблоны сами по себе образуют Тьюринг-полный язык и используются для порождения оптимизированных библиотек, таких, как Eigen, но ужасны в плане практического использования.

В языке Terra мы отказались от идеи сделать метаязык C/C++ более мощным и заменили его настоящим языком программирования, Lua.

Комбинация низкоуровневого языка, который может метапрограммироваться высокоуровневым скриптовым языком делает возможными многие варианты поведения, невозможные в других системах. В отличие от C/C++, код на Terra может быть JIT-компилирован и запущен совместно с интерпретатором Lua, что делает простым написание библиотек, зависящих от рантаймовой кодогенерации.

Возможности других языков, такие, как условная компиляция и шаблоны просто проигрывают по сравнению с использованием Lua для метапрограммирования Terra:

-- C++                    |  -- Lua/Terra
int add(int a, int b) {   |  terra add(a : int,b : int) : int
    return a + b;         |      return a + b
}                         |  end
                          |  
                          |  -- Условная компиляция завершена
                          |  -- передача управления 
                          |  -- решает, какой код определён
#ifdef _WIN32             |  if iswindows() then
void waitatend() {        |      terra waitatend()
    getchar();            |          C.getchar()
}                         |      end
#else                     |  else
void waitatend() {}       |      terra waitatend() end
#endif                    |  end
                          |  
                          |  -- Шаблоны стали функциями Lua
                          |  -- принимающими тип Т из terra
                          |  -- и использующими его для генерации новых типов 
                          |  -- и кода
template<class T>         |  function Array(T)
struct Array {            |      struct Array {
    int N;                |          N : int
    T* data;              |          data : &T
                          |      }
    T get(int i) {        |      terra Array:get(i : int)
        return data[i];   |          return self.data[i]
    }                     |      end
                          |      return Array
};                        |  end
typedef                   |  
Array<float> FloatArray;  |  FloatArray = Array(float)

Вы можете использовать Terra и Lua как…

Встраиваемый JIT-компилятор для конструирования языков. Мы используем техники многоступенчатого программирования [2] для того, чтобы сделать возможным метапрограммирование Terra с использованием Lua. Выражения, типы и функции языка Terra являются значениями первого класса в языке Lua, что делает возможным генерацию произвольных программ в рантайме. Это позволяет вам компилировать предметно-ориентированные языки (DSL), написанные на Lua в высокопроизводительный код на Terra. Более того, так как Terra построен на экосистеме Lua, легко встроить программу на Terra-Lua в другую программу в виде библиотеки. Такой дизайн позволяет вам добавлять JIT-компилятор в ваше существующее программное обеспечение. Вы можете использовать его для добавления JIT-компилируемых DSL-языков в ваше приложение, либо автоматически и динамически конфигурировать высокопроизводительный код.

Скриптовой язык с высокопроизводительными расширениями. Хотя производительность Lua и других динамических языков непрерывно улучшается, низкой уровень абстракции даёт вам предсказуемое управление производительностью, когда вам это нужно. Программы Terra используют тот же бэкенд LLVM, который Apple использует в своих компиляторах C. Это значит, что производительность кода Terra близка к аналогичному коду C. Например, наши переводы программ nbody и fannhakunen из бенчмарка [1] языков программирования имеют производительность, отличающуюся не более, чем на 5% от их эквивалентов на С, скомпилированных на Clang, фронтенде LLVM. Terra также включает встроенную поддержку SIMD-операций и другие низкоуровневые возможности, такие, как запись и предвыборка не-временной памяти. Вы можете использовать Lua для организации и конфигурирования вашего приложения, а затем, когда вам нужна управляемая производительность, сделать вызов кода Terra.

Самостоятельный низкоуровневый язык. Terra спроектирован так, что может работать независимо от Lua. Фактически, ваша конечная программа не требует Lua, вы можете сохранить код Terra в файл .o или в исполняемый файл. Вдобавок к ясному разделению между высокоуровневым и низкоуровневым кодом, такой дизайн позволяет вам использовать Terra как независимый низкоуровневый язык. В таком сценарии использования, Lua выступает в роли мощного языка метапрограммирования. Lua служит заменой шаблонов C++ [3] и макросов препроцессора C (X-Macro) [4], имея при этои лучший синтаксис и лучшие свойства в плане гигиены [5]. Так как Terra существует только как код, встроенный в метапрограмму Lua, те возможности, которые обычно встроены в низкоуровневый язык, могут быть реализованы как библиотеки Lua. Такой дизайн сохраняет ядро Terra простым, делая возможным сложное поведение, такое, как условная компиляция, пространства имён, шаблоны, и даже систему классов, реализованную в виде библиотек.

Чтобы получить больше информации об использовании Terra, смотрите руководство для начинающих и справочник по API. Наши публикации дают более глубокое представление о дизайне языка.

[1] http://benchmarksgame.alioth.debian.org
[2] http://www.cs.rice.edu/~taha/MSP/
[3] http://en.wikipedia.org/wiki/Template_metaprogramming
[4] http://en.wikipedia.org/wiki/X_Macro
[5] http://en.wikipedia.org/wiki/Hygienic_macro

Порождающее программирование


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

Многоступенчатые операторы


В коде Terra вы можете использовать опрератор escape ([]), помещающий результат выражения Lua в код Terra:

local a = 5
terra sin5()
    return [ math.sin(a) ]
end

Значение escape вычисляется, когда функция Terra компилируется, и результат помещается в код Terra. В данном примере, это означает, что выражение math.sin(5) будет вычислено один раз, и код, реализующий функцию Terra, возвратит константу. Это можно проверить, если вывести скомпилированную версию функции sin5.

--вывод хорошо показывает, что делает функция
sin5:printpretty() 
> output:
> sin50 = terra() : {double}
>    return -0.95892427466314
> end

Escape-операторы также могут возвращать другие сущности Terra, например, функции:

add4 = terra(a : int) return a + 4 end

terra example()
    return [add4](3) -- 7
end

В этом случае, код Terra будет вставлен в функцию Terra, сохранённую в переменной add4:

example:printpretty()
> output:
> example4 = terra() : {int32}
>   return <extract0> #add43(3)#
> end

Фактически, любое имя, используемое в коде Terra, такое, как add4 или foo.bar рассматривается по умолчанию, как если бы оно было escape-оператором.

Внутри escape-оператора вы можете ссылаться на переменные, определённые в Terra:

--функция для вызова внутри escape
function choosesecond(a,b)
    -- выводит false, 'a' - не число:
    print(a == 1) 
    -- выводит true, 'a' - символ Terra:
    print(terralib.issymbol(a))
    return b
end

terra example(input : int)
    var a = input
    var b = input+1
    --создаёт escape со ссылками на 'a' и 'b'
    return [ choosesecond(a,b) ] --возвращает значение b
end
example(1) --возвращает 2

Так как escape-операторы вычисляются до того, как функции Terra скомпилированы, переменные a и b не будут иметь конкретных целых значений внутри escape-оператора. Вместо этого, внутри кода Lua переменные a и b являются символами Terra, представляющими ссылки на значения Terra. Так как choosesecond возвращает символ b, функция в примере возвратит значение переменной b кода Terra, когда она будет вызвана.

Оператор цитирования (quotation), обратный апостроф, позволяет вам генерировать операторы и выражения Terra в Lua. Они могут быть вставлены в код Terra с использованием escape-оператора.

function addtwo(a,b)
    return `a + b
end
terra example(input : int)
    var a = input
    var b = input+1
    return [ addtwo(a,b) ]
end
example(1) -- возвращает 3

Для генерации операторов вместо выражений исользуйте опретор quote:

local printtwice = quote
    C.printf("hello\n")
    C.printf("hello\n")
end
terra print4()
    [printtwice]
    [printtwice]
end

Компиляция языка


С помощью этих двух операторов вы можете генерировать произвольный код на Terra во время компиляции. Это делает комбинацию Lua/Terra хорошо подходящей для написания компилятора высокопроизводительного предметно-ориентированного языка. Например, мы можем реализовать компилятор BF, минимального языка, эмулирующего машину Тьюринга. Функция compile на языке Lua принимает строку кода BF и максимальный размер ленты N. Затем она генерирует функцию Terra, реализующую BF-код. Это «скелет», который подготавливает программу BF:

local function compile(code,N)
    local function body(data,ptr)
        --<<реализация body>>
    end
    return terra()
        --массив с содержимым ленты
        var data : int[N]
        --сначала очищаем ленту
        for i = 0, N do
            data[i] = 0
        end
        var ptr = 0
        --генерируем код функции body
        [ body(data,ptr) ]
    end
end

Функция body отвечает за генерацию тела программы BF по строке кода:

local function body(data,ptr)
    --список операторов Terra, исполняющих программу BF
    local stmts = terralib.newlist()

    --цикл по символам кода BF
    for i = 1,#code do
        local c = code:sub(i,i)
        local stmt
        --генерируем соответствующие операторы Terra
        --для каждого оператора BF
        if c == ">" then
            stmt = quote ptr = ptr + 1 end
        elseif c == "<" then
            stmt = quote ptr = ptr - 1 end
        elseif c == "+" then
            stmt = quote data[ptr] = data[ptr] + 1 end
        elseif c == "-" then
            stmt = quote data[ptr] = data[ptr] - 1 end
        elseif c == "." then
            stmt = quote C.putchar(data[ptr]) end
        elseif c == "," then
            stmt = quote data[ptr] = C.getchar() end
        elseif c == "[" then
            error("Implemented below")
        elseif c == "]" then
            error("Implemented below")
        else
            error("unknown character "..c)
        end
        stmts:insert(stmt)
    end
    return stmts
end

Цикл проходит по строке кода, генерирует соответствующий код на Terra для каждого символа BF (например, ">" сдвигает ленту на один символ и реализуется на Terra кодом ptr = ptr + 1). Сейчас мы можем скомпилировать функцию BF:

add3 = compile(",+++.")

Результат, add3 — функция Terra, прибавляющая 3 к входному символу и выводящая результат:

add3:printpretty()
> bf_t_46_1 = terra() : {}
> var data : int32[256]
> ...
> var ptr : int32 = 0
> data[ptr] = <extract0> #getchar()#
> data[ptr] = data[ptr] + 1
> data[ptr] = data[ptr] + 1
> data[ptr] = data[ptr] + 1
> <extract0> #putchar(data[ptr])#
> end

Также мы можем использовать оператор goto (goto labelname) и метки (::labelname::) для реализации конструкции цикла в BF:

local function body(data,ptr)
    local stmts = terralib.newlist()
    
    --добавляем стек, чтобы отслеживать начало каждого цикла
    local jumpstack = {}
    
    for i = 1,#code do
        local c = code:sub(i,i)
        local stmt
        if ...
        elseif c == "[" then
            --генерируем метки, представляющие начало
            --и конец цикла
            --функция 'symbol' генерирует глобальное уникальное
            --имя метки
            local target = { before = symbol(), after = symbol() }
            table.insert(jumpstack,target)
            stmt = quote 
                --метка начала цикла
                ::[target.before]:: 
                if data[ptr] == 0 then
                    goto [target.after] --exit the loop
                end
            end
        elseif c == "]" then
            --извлекаем метки, соответствующие циклу
            local target = table.remove(jumpstack)
            assert(target)
            stmt = quote 
                goto [target.before] --loop back edge
                :: [target.after] :: --label for end of the loop
            end
        else
            error("unknown character "..c)
        end
        stmts:insert(stmt)
    end
    return stmts
end

Мы используем конструкции порождающего программирования для реализации предметно-ориентированных языков и автонастройки. Наша статья в PLDI описывает нашу реализацию Orion, языка для ядер обработки изображений, и мы в процессе портирования языка Liszt (основанное на сетках решение дифференциальных уравнений в частных производных) на язык Terra.

Встраивание и взаимодействие


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

Сначала сделаем возможной передачу значений между Lua и Terra. Наша реализация построена на основе интерфейса «чужих» функций (foreign function) LuaJIT. Вы можете вызвать функции Terra прямо из Lua (и наоборот) и получать доступ к объектам прямо из Lua (более подробно описано в справочнике по API).

Более того, Lua-Terra обратно совместим с чистыми Lua и C, что облегчает использование существующего кода. В Lua-Terra, вы можете использовать require или loadfile и рассматривать файл как программу Lua (используйте terralib.loadfile для загрузки комбинированного файла Lua-Terra). Вы можете использовать terralib.includec для импорта функций C из существующих заголовочных файлов.

Наконец, Lua-Terra может также быть встроен в существующме приложения путём линковки приложения с libterra.a и использования Terra’s C API. Интерфейс очень похож на интерфейс интерпретатора Lua. Простой пример инициализирует Terra и запускает код из файла, определённого в каждом аргументе:

#include <stdio.h>
#include "terra.h"

int main(int argc, char ** argv) {
    lua_State * L = luaL_newstate(); //создаем состояние обычного Lua
    luaL_openlibs(L);                //инициализируем его библиотеки
    //инициализируем состояние Terra в Lua
    terra_init(L);
    for(int i = 1; i < argc; i++)
        //запускаем код Terra из каждого файла
        if(terra_dofile(L,argv[i]))  
            exit(1);
    return 0;
}

Простота


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

Условная компиляция


Как правило, условная компиляция совершается с использованием директив препроцессора (например, #ifdef), или какой-либо системы сборки. При использовании Lua-Terra, мы можем написать код Lua, определяющий, как сконструировать функцию Terra. Так как Lua является полноценным языком программирования, он может делать вещи, которые большинство препроцессоров делать не могут, например, вызывать внешние программы. В этом примере, мы применяем условную компиляцию, чтобы скомпилировать функцию Terra по-разному для OSX и Linux путём вызова uname, чтобы определить операционную систему, и заием используем оператор if для инстанцирования разных версий функции Terra в зависимости от результата:

--запускаем uname чтобы узнать, какая ОС запущена
local uname = io.popen("uname","r"):read("*a")
local C = terralib.includec("stdio.h")

if uname == "Darwin\n" then
    terra reportos()
        C.printf("this is osx\n")
    end
elseif uname == "Linux\n" then
    terra reportos()
        C.printf("this is linux\n")
    end
else
    error("OS Unknown")
end

--условная компиляция в 
--нужную версию для данной ОС
reportos()

Пространства имён


Статически типизированным языкам обычно нужны конструкции, которые решают проблему пространств имён (например, ключевое слово namespace в C++, или конструкция import в Java). Для Terra мы просто используем таблицы первого класса из Lua как способ организации функций. Когда вы используете любое имя, например, myfunctions.add, внутри функции Terra, Terra будет разрешать его во время компиляции в связанное с ним значение Terra. Вот пример размещение функции Terra внутри таблицы Lua, с последующим вызовом из другой функции Terra:

local myfunctions = {}
-- функции terra - это значения первого класса в Lua 

-- они могут быть сохранены в таблицах Lua 
terra myfunctions.add(a : int, b : int) : int
    return a + b
end

-- и вызваны из таблиц
terra myfunctions.add3(a : int)
    return myfunctions.add(a,3)
end

--объявление myfunctions.add это просто синтаксический сахар для:

myfunctions["add"] = terra(a : int, b : int) : int
    return a + b
end

print(myfunctions.add3(4))

Фактически, вы уже видели такое поведение когда мы импортировали функции С:

C = terralib.includec("stdio.h")

Функция includec просто возвращает таблицу Lua ( C ), содержащую функции C. Так как C — это таблица Lua, вы можете делать итерации по ней:

for k,v in pairs(C) do
    print(k,v)
end

> seek   <terra function>
> asprintf    <terra function>
> gets    <terra function>
> size_t  uint64
> ...

Шаблоны


Так как типы и функции Terra являются значениями первого класса, вы можете получить фунциональность, близкую к шаблонам C++, просто создав тип Terra и определив функцию Terra внутри функции Lua. Ниже приведён пример, в котором мы определяем функцию Lua MakeArray(T), приимающую тип T языка Terra и порождающую объект Array который может хранить множество объектов типа T (т.е. простую версию std::vector из C++).

C = terralib.includec("stdlib.h")
function MakeArray(T)
    --создаем новый тип Struct, содержащий указатель
    --на список объектов T и размер N
    local struct ArrayT {
        --&T i- указатель на T
        data : &T;
        N : int;
    } 
    --добавляем методы к типу
    terra ArrayT:init(N : int)
        -- синтаксис [&T](...) - преобразование типов,
        -- эквивалентно (T*)(...) в С
        self.data = [&T](C.malloc(sizeof(T)*N))
        self.N = N
    end
    terra ArrayT:get(i : int)
        return self.data[i]
    end
    terra ArrayT:set(i : int, v : T)
        self.data[i] = v
    end
    --возвращаем тип как
    return ArrayT
end

IntArray = MakeArray(int)
DoubleArray = MakeArray(double)

terra UseArrays()
    var ia : IntArray
    var da : DoubleArray
    ia:init(1) 
    da:init(1)
    ia:set(0,3)
    da:set(0,4.5)
    return ia:get(0) + da:get(0)
end

Как показано в примере, Terra позволяет вам определять методы в типах struct. В отличие от других статически типизированных языков с классами, здесь нет встроенных механизмов наследования или run-time полиморфизма. Декларации методов, это просто синтаксический сахар, который ассоциирует таблицы методов Lua с каждым типом. Здесь метод get эквивалентен следующему:

ArrayT.methods.get = terra(self : &T, i : int)
    return self.data[i]
end

Объект ArrayT.methods в таблице Lua хранит методы для типа ArrayT.

Аналогично, вызов, например, ia:get(0) эквивалентен T.methods.get(&ia,0).

Специализация


Помещая функцию Terra внутрь функции Lua, вы можете скомпилировать разные версии функции. Здесь мы генерируем разные версии функции степени (т.е. pow2, pow3):

--генерируем функцию степени для данного N (например, N = 3)
function makePowN(N)
    local function emit(a,N)
        if N == 0 then return 1
      else return `a*[emit(a,N-1)]
      end
    end
    return terra(a : double)
        return [emit(a,N)]
    end
end

--используем это для заполнения таблицы функций
local mymath = {}
for n = 1,10 do
    mymath["pow"..n] = makePowN(n)
end
print(mymath.pow3(2)) -- 8

Система классов


Как показано в примере для шаблонов, Terra позволяет определять методы для типов struct, но не предоставляет встроенного механизма для наследования или полиморфизма. Вместо этого, обычная система классов может быть написана как библиотека. Например, пользователь может написать:

J = terralib.require("lib/javalike")
Drawable = J.interface { draw = {} -> {} }
struct Square { length : int; }
J.extends(Square,Shape)
J.implements(Square,Drawable)
terra Square:draw() : {}
    --реализация draw
end

Функции J.extends и J.implements являются функциями Lua, генерирующими соответствующий код на Terra для реализации системы классов. Больше информации доступно в нашей статье в PLDI. Файл lib/javalike.t содержит одну возможную реализацию системы классов, аналогичную Java, а файл lib/golike.t — более похожую на язык Go.
Tags:
Hubs:
+57
Comments 28
Comments Comments 28

Articles