📜 ⬆️ ⬇️

Terra Language - Low Level Partner Lua

Terra is a low-level system programming language that is embedded and can be metaprogrammed using 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 }) 

Like C / C ++, Terra is a statically typed, compiled language with “manual” memory management. Unlike C / C ++, it was originally designed for metaprogramming using Lua.

Terra is designed based on the fact that C / C ++ actually consists of many “languages.” There is a core language, consisting of operators, controlling the flow of execution and calling functions, but the surrounding language is a metalanguage made up of a mixture of different things, such as preprocessor, templates, structure declarations. The templates themselves form a Turing-complete language and are used to generate optimized libraries, such as Eigen , but are terrible in terms of practical use.
')
In the Terra language, we abandoned the idea of ​​making the metal language C / C ++ more powerful and replaced it with a real programming language, Lua.

The combination of a low-level language that can be meta-programmed by a high-level scripting language makes many behaviors impossible in other systems possible. Unlike C / C ++, the code on Terra can be JIT-compiled and run in conjunction with the Lua interpreter, which makes it easy to write libraries that depend on runtime code generation.

The capabilities of other languages, such as conditional compilation and patterns, simply lose compared to using Lua for Terra metaprogramming:

 -- 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) 

You can use Terra and Lua as ...

Embedded JIT compiler for constructing languages. We use multi-stage programming techniques [2] to enable Terra metaprogramming using Lua. Expressions, types and functions of the Terra language are first-class values ​​in the Lua language, which makes it possible to generate arbitrary programs in runtime. This allows you to compile domain-specific languages ​​(DSL) written in Lua into high-performance Terra code. Moreover, since Terra is built on the Lua ecosystem, it is easy to embed a program on Terra-Lua into another program as a library. This design allows you to add a JIT compiler to your existing software. You can use it to add JIT-compiled DSL languages ​​to your application, or automatically and dynamically configure high-performance code.

A scripting language with high-performance extensions. Although the performance of Lua and other dynamic languages ​​is continuously improving, a low level of abstraction gives you predictable performance control when you need it. The Terra programs use the same LLVM backend that Apple uses in its C compilers. This means that the performance of the Terra code is similar to the C code. For example, our translations of the nbody and fannhakunen programs from the benchmark [1] programming languages ​​have a performance that is no more than 5% of their equivalents on C compiled to Clang, frontend LLVM. Terra also includes built-in support for SIMD operations and other low-level features, such as recording and prefetching non-temporary memory . You can use Lua to organize and configure your application, and then, when you need managed performance, make a call to the Terra code.

Independent low-level language. Terra is designed to work independently of Lua. In fact, your final program does not require Lua, you can save the Terra code to a .o file or to an executable file. In addition to a clear separation between high-level and low-level code, this design allows you to use Terra as an independent low-level language. In such a use case, Lua acts as a powerful metaprogramming language. Lua serves as a substitute for C ++ templates [3] and C preprocessor macros (X-Macro) [4], with the best syntax and best hygiene properties [5]. Since Terra exists only as code embedded in a Lua metaprogram, those features that are usually built into a low-level language can be implemented as Lua libraries. Such a design keeps the Terra core simple, making it possible to perform complex behaviors such as conditional compilation, namespaces, patterns, and even a class system implemented as libraries.

For more information on using Terra, see the beginner ’s guide and API reference . Our publications provide a deeper insight into language design.

[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

Generating programming


Terra entities such as functions, types, variables, and expressions are first-class values ​​in Lua, they can be stored as variables, and also passed to Lua functions and returned from Lua functions. Using constructs from multi-stage programming, you can write Lua code that generates arbitrary Terra code.

Multistep Operators


In the Terra code, you can use the escape ([]) operator, which places the result of the Lua expression in the Terra code:

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

The escape value is calculated when the Terra function is compiled, and the result is placed in the Terra code. In this example, this means that the expression math.sin (5) will be evaluated once, and the code implementing the Terra function will return a constant. This can be verified by displaying the compiled version of the function sin5.

 --  ,    sin5:printpretty() > output: > sin50 = terra() : {double} > return -0.95892427466314 > end 

Escape statements can also return other Terra entities, such as functions:

 add4 = terra(a : int) return a + 4 end terra example() return [add4](3) -- 7 end 

In this case, the Terra code will be inserted into the Terra function stored in the variable add4:

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

In fact, any name used in Terra code, such as add4 or foo.bar, is treated by default as if it were an escape statement.

Inside the escape statement, you can refer to variables defined in 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 

Since the escape operators are evaluated before the Terra functions are compiled, the variables a and b will not have specific integer values ​​inside the escape operator. Instead, inside the Lua code, the variables a and b are Terra symbols representing references to Terra values. Since choosesecond returns the character b, the function in the example will return the value b of the Terra code variable when it is called.

The quotation operator, the reverse apostrophe, allows you to generate Terra operators and expressions in Lua. They can be inserted into the Terra code using the escape statement.

 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 

To generate statements instead of expressions, use the quote clause:

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

Compiling language


With these two statements, you can generate arbitrary code on Terra at compile time. This makes the Lua / Terra combination well suited for writing a high-performance, object-oriented language compiler. For example, we can implement a BF compiler, a minimal language that emulates a Turing machine. The compile function in Lua takes a string of BF code and a maximum tape size N. It then generates a Terra function that implements the BF code. This is the “skeleton” that prepares the BF program:

 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 

The body function is responsible for generating the body of the BF program with a line of code:

 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 

The loop goes through the line of code, generates the corresponding code on Terra for each BF character (for example, ">" shifts the tape by one character and is implemented on Terra with the code ptr = ptr + 1). Now we can compile the BF function:

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

The result, add3, is the Terra function, which adds 3 to the input symbol and displays the result:

 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 

We can also use the goto operator ( goto labelname ) and labels ( :: labelname ::) to implement the loop construction in 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 

We use generative programming constructs to implement domain-specific languages ​​and auto-tuning. Our PLDI article describes our implementation of Orion, the language for image processing cores, and we are in the process of porting the Liszt language ( mesh- based solution of partial differential equations) to the Terra language.

Embedding and interaction


Programming languages ​​do not exist in a vacuum, and the possibilities of generating programming in Terra can be useful even in projects that were originally implemented in other programming languages. We make possible the integration of Terra with other projects, so that you can use the generation of low-level code, and at the same time most of your project will be implemented in any traditional language.

First we make it possible to transfer values ​​between Lua and Terra. Our implementation is based on the interface of foreign functions (LuaJIT foreign function). You can call Terra functions directly from Lua (and vice versa) and access objects directly from Lua (described in more detail in the API reference).

Moreover, Lua-Terra is backward compatible with pure Lua and C, which facilitates the use of existing code. In Lua-Terra, you can use require or loadfile and treat the file as a Lua program (use terralib.loadfile to load the combined Lua-Terra file). You can use terralib.includec to import C functions from existing header files.

Finally, Lua-Terra can also be embedded in an existing application by linking the application with libterra.a and using Terra's C API. The interface is very similar to the Lua interpreter interface. A simple example initializes Terra and runs the code from the file defined in each argument:

 #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; } 

Simplicity


The combination of a simple low-level language with a simple dynamic programming language means that many of the built-in capabilities of statically typed low-level languages ​​can be implemented as libraries in a dynamic language. Here are a few examples:

Conditional compilation


As a rule, conditional compilation is done using preprocessor directives (for example, #ifdef), or some kind of build system. When using Lua-Terra, we can write Lua code that defines how to construct the Terra function. Since Lua is a complete programming language, it can do things that most preprocessors cannot do, for example, call external programs. In this example, we use conditional compilation to compile the Terra function differently for OSX and Linux by calling uname to determine the operating system, and using the if statement to instantiate different versions of the Terra function depending on the result:

 -- 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() 

Namespaces


Statically typed languages ​​usually need constructs that solve the namespace problem (for example, the namespace keyword in C ++, or the import construct in Java). For Terra, we simply use Lua's first-class tables as a way to organize functions. When you use any name, for example, myfunctions.add, inside the Terra function, Terra will resolve it at compile time to its associated value Terra. Here is an example of placing the Terra function inside a Lua table, followed by a call from another Terra function:

 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)) 

In fact, you have already seen this behavior when we imported C functions:

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

The includec function simply returns a Lua (C) table containing C functions. Since C is a Lua table, you can iterate over it:

 for k,v in pairs(C) do print(k,v) end > seek <terra function> > asprintf <terra function> > gets <terra function> > size_t uint64 > ... 

Templates


Since the types and functions of Terra are first-class values, you can get functionality close to C ++ templates by simply creating the Terra type and defining the Terra function inside the Lua function. Below is an example in which we define the Lua function MakeArray (T), which takes the type T of the Terra language and generates an Array object that can store many objects of type T (that is, a simple version of std :: vector from 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 

As shown in the example, Terra allows you to define methods in struct types. Unlike other statically typed languages ​​with classes, there are no built-in inheritance mechanisms or run-time polymorphisms. The method declarations are simply syntactic sugar, which associates Lua method tables with each type. Here, the get method is equivalent to the following:

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

The ArrayT.methods object in the Lua table stores methods for the ArrayT type.

Similarly, a call, for example, ia: get (0) is equivalent to T.methods.get (& ia, 0).

Specialization


By placing the Terra function inside the Lua function, you can compile different versions of the function. Here we generate different versions of the degree function (i.e. 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 

Class system


As shown in the example for templates, Terra allows you to define methods for struct types, but does not provide a built-in mechanism for inheritance or polymorphism. Instead, the usual class system can be written as a library. For example, a user might write:

 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 

The J.extends and J.implements functions are Lua functions that generate the corresponding Terra code for the implementation of the class system. More information is available in our PLDI article . The file lib / javalike.t contains one possible implementation of a class system similar to Java, and the file lib / golike.t is more similar to the language Go.

Source: https://habr.com/ru/post/336406/


All Articles