What is Sane ?

Sane is a code generator, designed to speed up the development of programs optimized for execution speed and memory usage.

In itself, the language is not going to provide any abstraction that would drive the programmers away from the hardware, nor any stubborn dogmatic rule that would perpetually force them to spend time on workarounds. In place of that, Sane allows and promotes the use and development of active libraries (libraries that take part in the process of compilation). Teams and developers can therefore choose the right level of abstraction, depending on the context, to meet the needs in terms of programming speed, security and execution performance.

Sane is basically very close to C++, except for the streamlined syntax, the compilation processes, and last but not least, the dramatically improved compile-time abilities which notably drives the tools for generative programming and compiler aided decisions.

Sane is the acronym of Software engineers Are Not Evil.

Organization of this document

This documentation starts with the base syntax. The main differences with the base C++ are then emphasized, to drive thereafter to applications on generative programming. It is then followed by examples of commonly used optional abstractions (asynchronous execution, security enforcements, ...), illustrating the principle of active library.

Base syntax

Simplifications

For calls, functions definitions, ifs, ... the parentheses become optional. Semicolon, braces and returns have undergone the same treatment.

# 'foo' is a function with two (unconstrained) parameters 'a' and 'b'
def foo a, b
    info a + b

# equivalent to foo( 5, min( 10, 15 ) )
# (Auto-calls are handled right to left)
foo 5, min 10, 15

Line continuations are automatic (thanks notably to operators and block structures).

# b is the rhs of the '+'
foo 10, a +
    b

# argument list can be specified in block lines.
# In this case, the comma become optionnal
foo
    10
    a + b

But frantic one-liners, are still welcome to play the game :)

# ';' acts as a carriage return
def foo a, b; info a + b

# '()' allows for block definitions
def bar a, b; ( c := a + b; 2 * c )

As a rule of thumb, if the compiler can take care of an obvious simplification, this simplification is enabled for the greater goods.

# Std def of a lambda functions without parameter
l0 := () => 17 # std def of a lambda func without parameter
# in the following line, as ':=' can't be an argument spec.
# we safely assume that '=> 17' is a no parm lambda
l1 := => 17

# works of course with all the kinds of operators
foo
    => 17 # unnamed arg
    arg: => 17 # named arg

Parameters

Parameters of callable objects (defs, classess, lambdas, ...) can have default values, constraints (with free parameters) and can be selected using their names.

# a must be a SI32 (32 bits signed integer)
# b and c have default values 'a + 1' and 'b + 1'
def foo a: SI32, b? a + 1, c? b + 1
    a + b + c

# argument may be named. Default values are computed on the go
foo 15, c: 18

By default, arguments is passed as immutable references.

"Deconstification" is possible, using the mut keyword.

# modification of b is possible inside this function
def foo a, mut b
    b += a

# => 25
b := 10
foo 15, b
info b

Qualifiers

Qualifiers like private, protected, static, global... may be associated with one or several declarations at the same time if written in sub-blocks.

class Mesh[ ElemTypes ]
    # A public method
    def area
        elems.sum e => e.with_coords( e.nodes.map n => nodes[ n ] ).area

    # A private section (with two attributes)
    private
        nodes: Vec[ Node ]
        elems: HetVec[ ...ElemTypes ]

Templates

The word "template" refers to that of C++. Template in Sane works roughly in the same way as in C++: functions code are actually generated according to the input types and needed compile-time known values. It enables a first-level of compile-time or static polymorphism.

The main differences with C++ are that:

  • By default, every callable (def, class, lambda, ...) is a template. There's no special syntax for templates.
  • The compiler acts like a server, enabling aggressive per function caching and hashing, for the compilation speed and the binary sizes.
  • Template parameters can be of any type,
  • Selection of surdefinitions work with programmable criteria than can work at compile-time (preferred) or run-time (if needed).

Priorities and conditions

An arbitrary number or surdefinitions may lie on the same scope. Selection may depend on programmable priorities (pertinence) and programmable conditions (when).

# computed priority
def pow mat: Matrix, n: PositiveInteger 
            pertinence - cost_mult( mat, mat ) * log n
    n & 1 ? mat * pow( mat, n - 1 )
          : pow( mat * mat, n / 2 )

# + computed condition (handled at compile time in this case)
def pow mat: Matrix, n: Number
            when mat.sub_types.some( T => T.is_approximate )
            pertinence - cost_eigen( mat )
    e := eigen mat
    e.P.trans * pow( e.D, n ) * e.P

Multidimensionnal vtables

The virtual keyword can work on any kind of argument, indifferently on methods or functions.

# run-time selection using bidimensionnal vtables
def intersection_area virtual a: Square, virtual b: Triangle
    ...

# a (dynamic) polymorphic function
def weight a: GeometricObject, b: GeometricObject, density? 7800
    density * intersection_area a, b

(Remark: there are different kinds of vtables in Sane. Adding a pointer at the beginning (for the simple mono-inheritance case) is the default solution -- very good on a general purpose -- but other choices exist)

Template classes

Classes parameters can be of any type, as long as copy and equality can be Compile-Time handled, in a symbolic way (comparison of graphs) or not (comparison of known values).

This notably does not exclude the types that may imply memory allocation as String, Vec[...], ... In this case, the comparison are symbolic and can be handled at Compile-Time.

# `sizes` can be defined using any kind of array
class PoolBySize[ sizes: ArrayLike, mt? true, name? "anon" ]
    class Item
        free_ptr: NullableAT # nullable address
        page_vec: Vec[ AT ]  # contiguous array of addresses
    # StaticMap constructs a Compile-Time tree
    map: StaticMap[ sizes, Item ] 
    ...

# instantiation for a given set of sizes (handled at CT)
pool := PoolBySize[ [ 16, 24, 32 ] ]()

Variadic arguments

Callable parameters (for def, class, =>, ...) can be variadic, with optional constraints. It construct a compile-time known Varargs object, containing the optional names and the argument references.

def foo a, ...b: SI32, c: StringLike
    info a, b, c         # -> 4, [5,arg_name:6], "bar"
    info b[ 0 ]          # -> 5
    info b[ "arg_name" ] # -> 6
    info b.values        # -> [5, 6]
    info b.names         # -> [arg_name]

foo 4, 5, arg_name: 6, "bar"

Spread operator

The ... operator can also be used to expand stuff, notably for calls and list definitions.

... works with every kinds of lists containing a compile-time runnable spread method.

# ex. 1: call with an expanded Varargs 
def foo a, ...b
    bar ...b, 654

# ex. 2: expansion in a list
u := 2 .. 10 # range( 2, 10 )
v := [ 1, ...u, 10 ]

Objects

Constructors

As with C++, constructors allow a pre-construction phase, to initialize attributes only once and directly with the right arguments.

Unlike with C++, pre-construction may occur in a block, with arbitrary interleaved instructions.

This block can be delimited explicitly (wpc) or implicitly (the last visible init_of call). init_of attr_name, [ ctor_args ] allows to initialize an argument. init_of self, [ ctor_args ] enables to call another constructor of the same class.

class MyClass
    def construct
        # explicit pre-construction block (with interleaved instructions)
        wpc
            init_of a, 564 
            z := 12
            init_of b, 654, z
        # -> "normal" construction (*all* arg are now pre-initialized)
        print a + b

    # equivalent ctor with automatic wpc block
    def construct
        # implicit pre-construction block
        init_of a, 564 
        z := 12
        init_of b, 654, z
        # -> "normal" construction (*all* arg are now pre-initialized)
        print a + b

    # wpc allows for the use of arbitrarily complex interleaved instructions
    def construct
        wpc
            u := 7 + 5 
            for n in "ab"
                init_of $n, 654, u
            my_c_init()

    def my_c_init
        init_of c, 564 # (this instruction forces the inlining of my_c_init)

    a: Foo
    b: Bar
    c: Baz

Getsetters

Symbolic attributes can be added using get_..., set_..., mod_... and typeof_... method names.

# an example with getters and setters
class Complex[ T? FP32 ]
    def get_mag
        sqrt real * real + imag * imag

    def get_arg
        atan2 imag, real

    def set_mag new_mag
        old_arg := arg
        real = new_mag * cos old_arg
        imag = new_mag * sin old_arg
        
    real: T
    imag: T

c := Complex 1, 2
info c.mag # => 2.24
c.mag = 4  # => calls set_mod( 4 )

typeof_... allows to get type information without the need for a getter (can be useful for pure setters or moders).

class Smurf
    def typeof_break_dance
        SI32

    def set_break_dance value
        info value

def foo v: SI32
    v = 654

s := Smurf()
foo s.break_dance # will work (typeof is known without a getter)

mod_... can be seen as a generalized setter. It is called with a modifying function as parameter (instead of a value).

# an example with getters and setters
class NodeList
    def mod_x func
        for p in points
            func p.x
    points: Vec[ Point ]

node_list.x += 10 # 'operator+=' is a register "mod function"

Types for literals

Literals (12, "smurf", [1,2], ...) must be of given types, but it's impossible to find types that would directly fit all the needs (one day you need fast coding, on another day you will have to focus on execution speed, security, etc...).

Sane tries then to provide types to fit the most common needs, with maximum flexibility and able to execute the most common operations at good mean speeds and memory occupancy, while fully ensuring that the conversion costs will be zero.

# generates a mutable 'String'
s := "les { 2 * 4 } scarole"

# supporting common operations
# (with potential memory allocation)
s += "s"

# operations can nevertheless be handled by the compiler,
# enabling to remove intermediate memory allocation. t
# will be stored in the .text or .data section with a
# zero-cost execution
t := StaticCString s

# and now, we have a pointer on a zero-ended string
strlen t + 2 # returns s.length - 2

For maximum flexibility, arrays are fully generic

# heterogeneous arrays (no forced conversion)
for a in [ "f", 1 ]; print a + 1 # -> f1 2 
# costlesss conversions (using a std lib function)
for a in vec [ "f", 1 ]; print a + 1 # -> f1 11 
# choice of the target type
for a in Vec[ String ] [ "f", 1 ]; print a + 1 # -> f1 11

Maps have followed the same path.

# works the same way for maps
import HashTable

v := 17
a := { 1: 2, "f": "g", v } # <=> "v": v for the last item
# can be converted with compile time support
info HashTable[ String, String ] a # -> { "1": "2", "f": "g", "v": "17" }

(Remark: {} may allow to define JS-like objects, using the function obj. In Sane, keys are computed value, whence the need for double quotes as in JSON.)

Memory

Rvalues

rvalue allows to know if a value is owned on a given scope.

def foo a, b
    info rvalue a # -> true (s + 2 has been created for the call and will be destroyed just after)
    info rvalue b # -> false (b is a reference on a variable referenced elsewhere)

s := "..."
foo s + 2, s

move x create a new object, with the resources of x (y := move x moves the resources of x to a new object y of the same type).

Besides, forward x is equivalent to move x if x is an rvalue. In the other case, it returns the reference on x.

def foo v
    info rvalue v
    w := Vec[ SI32 ] forward v # content of v will be transfered (not copied) to w if v is a rvalue

v := vec [ 1, 2, 3 ]
foo v      # rvalue: false. Content of v will be copied (with a potential mem alloc)
foo move v # rvalue: true.  No copy, no mem alloc

Heap

Variables can of course be created on the heap, with the (heap or mixed) allocator of your choice. new and delete are regular standard functions (not operators) that use a slub allocator (modifiable globally if wanted) but that can be surdefined, locally or globally.

Besides, it is common to use different allocators in different parts of the programs (e.g. with calls like my_allocator.new Type[, ctor_args]. That's one on the reason why new and delete are regular functions.

Stack(s)

If not specified, variables are of course created on a stack. By default, variables are created on the current stack. Nevertheless, as an optimization, if they are intended to be returned or used elsewhere, they can be created directly on a parent stack.

def foo
    vec 0 .. 1e6
# the vector 'vec 0 .. 1e6' is directly created 
# in the stack of a, not in the stack of foo
a := foo()

Notations for references and pointers

For faster reading (and conformance with the base syntax), pointers and references have the specific signs.

# new is a regular function (explaining the ',' after the type)
p := new String, "123" # -> type = Ptr[ String ]
# '@' allows to get the references
info @p
# '->' works as usual
info p->size
# '\' allows to get a pointer
a := "456"
q := \a # -> a Ptr[ String ] pointing to a

Generative programming

Of course, Sane can profitably be used to generate code formatted in strings, to be included in a second compilation phase...

Nevertheless, as we will see below, the Sane compiler is able to execute and cache the result of any Sane code during the compilation. It opens up an important set of new possibilities, providing access to more flexibility, clarity and efficiency.

Compile-time execution

The Sane compiler executes code during the compilation

  • if explicitly required (via for instance kv function),
  • if mandatory (notably for template parameters, computed names, ...),
  • or if trivial (simplifications that do not penalize the compilation time)

Of course, compile-time execution is not allowed to work on data intended to be handled at run-time (e.g. files, unless explicitly stated).

# a good portion of the CT simplifications are automatic 
a := [ 1, 2, 3 ].size
if a != 3
    never_compiled() # because size is trivially known at CT

# they can also be triggered explicitly (`kv` function)
b := 0
for i in 0 .. 10
    b += i
if kv b != 45 # at CT, b is symbolic, but kv( b ) is known
    never_compiled()

# if explicitly stated, it can work with files
c := load( "fs" ).read_file_sync "my_file", kv: true
s := c.split().filter( x => x.size == 3 ).size
info kv s # computed entirely at CT

# triggering can be implicitly 
i := MyClass[ s ] # we store the symbolic repr (no need at this stage to get the value)
j := MyClass[ 17 ] # here, the equality operator (s==?17) forces the computation

Computed names

All variable names (whether it's for look up or for creation) may be computed (using $s).

# creation and use of a variable named 'i18'
a := 9
i$( 2 * a )n := 43
info $( "hij"[1] )18 # => 43

Creation in parent scopes

A \ in a variable declaration enables to declare it in a parent scope (\ for the first parent, \\ for the second one, ...). It works also in class block (notably to define methods and attributes, static or dynamic) which can actually be a place where any kind of code is executed (Sane use the variables in the scope to determine attributes and methods).

# This is (an extract of) the class used for enums is the std libraries
class Enum[ id, item_names ]
    # class blocks are executed only once (for a set of template parameters)
    static __nb_items := 0
    for name in item_names 
        num := post_inc __nb_items
        static # (works also with non-static defs and attrs)
        def \get_$name
            Enum[ id, name, item_names ] __value: num

    def write_to_stream os 
        os << item_names[ __value ]

    __value ~= SI32
      
T := Enum[ 0, [ "A", "B" ] ]
info T::A # => A (thanks to the generated `static def get_A` in the class scope)

Compile-time Symbolic computations

Sane enables to handle SSA (Single Static Assignment) trees at compile-time.

It is for instance possible to get a representation of what a function or a block does. Trees can be filtered (transformations) or created ab anitio. They can then be passed back to the compiler which will be able to generate tuned and optimized code from this representation.

Here is a (simplified) example of automatic optimized differentiation.

# extract of a function to differentiate at a graph level
def ssa_diff node: SsaGraph
    switch node
        Symbolic::mul ==> node.children[ 0 ] * ssa_diff node.children[ 1 ] +
                          node.children[ 1 ] * ssa_diff node.children[ 0 ] 
        ... 

# a simple function
def foo n, x
    res := typeof( x ) 0
    for i in 1 .. n
        res += pow x, i
    res

# graph representation + differentiation of foo
x := ct_symbol FP64
n := ct_symbol SI32
sym_diff := ssa_diff ct_graph( foo( x, n ) ), x

# compile time optimized differentiation of foo
foo_diff := sym_diff.subs [ x, n ], [ xv, nv ]

These symbolic representations can be seen as the level above the AST representation (also accessible via std introspection as shown later). They enable what one can call "code introspection and filtering".

It is for instance used in the module vectorize (providing ways to simplify the writing of loops with SIMD instructions). In all the cases, transformations are triggered by standard calls and are a library concern (meaning that you have the choice to select them, to modify or create new ones for full control and extensibility).

Compile-time evaluation

For the extreme cases, it is possible to pass an arbitrary string to the compiler (as long of course as it can be CT computed).

a := 5
ct_eval "def foo; ${ 1 + a }"
info foo() # => 6

This construction is probably the closest to the one we can find in "code generation", with a reduction of problems coming from information scattering and tangled build configuration. Nevertheless, computed names with CT branching usually offer superior clarity and debugging support.

Ab initio primitives

In the same vein, it is possible to handle structures instead of text (as e.g. handling a DOM vs the html text).

Almost every objects handled by the compiler is actually accessible and modifiable within the language. It's valid for types, scopes, definition of methods, classes, and so on.

Compilation objects can for instance be created ab initio, to be consecutively handled by the compiler.

# creation
T := Type()
T.name = "MyType"
T.attributes << Type::Attribute off:0, name: "a", type: SI32

# the created type is stored and handled exactly like the others
i := T a: 100
info i # => T( a: 100 )

Active libraries

Selection

In Sane, functions implementations can be selected according to their a posteriori usage, notably to allow global optimizations.

When functions (or methods) that are qualified switchable are called, Sane marks them in the generated graph (which includes the captured variables). Before code emission, these marks are sent to the registered "switch procedures", allowing to choose the best implementations depdending on the global context.

# a standard matrix class (with a `switchable` procedure)
class Matrix
    switchable
    def operator* that
        # -> normal multiplication procedure
    ...

# standard multiplications (left to right)
a := p * q * r * v

# addition of a "switcher" (a different implementation, providing the same result)
# to call a procedure able to find the best ways to do the multiplications
globals.switchers.add
    oper: Matrix::operator*
    func: inps, outs =>
        # (simplified code)
        mults := get_mults_rec inps
        best_split := ...
        return mul( mults[ 0 .. best_split ] ) * mul( mults[ best_split.... ] )

These possibilities are used in a lot of essential optimizations. For instance, the concatenation operator works only with two variables (because it is an operator). If we want to concatenate more than two variables using this operator, we may end up with a lot of intermediate allocations and copies. A posteriori selection enable to gather the concatenations to avoid the waste.

Examples of active libraries

Auto-tuning

AutoTune is an experimental module that helps to find sets of compile-time variables that minimize a given set of functions.

It uses the fact that Sane is able to compile and execute code in the middle of another compilation (+ use of graphs and caches).

import AutoTune

# a function with internal tunable parameters
# (contains only a subset of the optimizations
# to be made on a dot function)
def dot a, b
    ule := AutoTune.parameter [ 2, 4, 8 ]
    res := Vec[ typeof( a ), ule ] 0
    for c in by_chunks 0 .. a.size, ule
        for j in unrolled 0 .. c.size
            res[ j ] += a[ c[ j ] ] * b[ c[ j ] ]
    res.sum

# make a tuned version of 'dot' for a given set of representative parameters.
# 'va' is a function that constructs a Varargs from its arguments
t_dot := AutoTune.tuned dot, [ {
    "pond": 1, "args": va vec( 1 .. 1000 ), vec( 1 .. 1000 )
} ]

# 't_dot' is the same thing as 'dot' with an optimized set of parameters
info t_dot vec( 1 .. 1000 ), vec( 1 .. 1000 )

Compact representations

Memory representation or potentially mutable variables are rarely compact. For instance, a String will take at least 24 bytes (on a 64 bits machine) even of the string is very small, a lot of small numbers are stored in too wide integers, etc...

But one can use introspection and generative programming to generate and handle compact representations.

In the following example, we use operator mem_size, which is an optional static method. Its mission is to compute the memory footprint of an instance (in bits), given a pointer to its start.

# generates a class to handle compact representation of T
# For the sake of simplicity, this class works with bytes
# and there's no ctor nor setters.
# This is the generic version
class CompactRepr[ T ]
    # method to compute offset of a given attribute
    static
    def offset_of base_ptr: AT, name: StringLike
        ptr := orp
        for attr in T.attributes
            if attr.name == name
                break
            ptr += ( 7 + CompactRepr[ attr.type ]::operator mem_size ptr ) // 8
        ptr - this.val

    # method to compute memory footprint
    static
    def operator mem_size base_ptr: AT
        offset_of base_ptr, "-"

    # make the getters
    for attr in T.attributes
        def \get_$( attr.name )
            @reinterpret_cast Ptr[ CompactRepr[ attr.type ] ], this.val + kv offset_of this.val, attr.name

# surdefinition for positive integers (VLQ)
class CompactRepr[ T ] when T.inherits( Number ) && T::is_integer && T::is_signed == false
    # method to compute memory footprint
    static
    def operator mem_size base_ptr: AT
        ptr := reinterpret_cast Ptr[ PI8 ], base_ptr
        while @ptr >= 128
            ++ptr
        ptr - base_ptr

    # conversion 
    def convert x: PrimitiveNumber
        ptr := reinterpret_cast Ptr[ PI8 ], this
        x.construct 0
        shift := 0
        while @ptr >= 128
            x += typeof( x )( @ptr - 128 ) << shift
            shift += 7
            ++ptr
        x += typeof( x )( @ptr ) << shift
            
    # display
    def write_to_stream mut os
        os << T self

# usage example
class MyClass
    a: PI32
    b: PT

C := CompactRepr[ MyClass ]

i := reinterpret_cast Ptr[ C ], my_ptr
info sizeof i # something between 2 and 15 bytes
info i->a
info i->b

Asynchronous code

Sane allows functions to pause when they do not have the data needed to progress. It can be seen as a kind of data-driven coroutine ability. It can also be seen as a Reactive Extension with a deep support from the language. It allows to transparently work with fors, ifs, ... and to generate highly optimized code (with less copies, indirections, ...).

Nevertheless, it is purely optional (activated only if RX function are used). Remark: the current event loop is simple and does not give the full control to the developers (for the scheduling, message passing, thread pinning, etc...). There's work to do on this topic.

A simple example:

import fs

# reads are launched in parallel
a := read( "a.txt" )
b := read( "b.txt" )
t := a.find b

# this sum is computed immediatly even if the read
# have not finished (the content of t is not needed)
info sum vec 

# here we say that 'stdout' depends on the sum of the
# two reads, but we don't make any operation (we're 
# just filling a graph handled at compile-time)
info t

# ...but at the end of the program, we have to make the output
# => execution of the graph

It generate something like (simplified)

struct T0 {
     String a0;
     String a1;
     int    a2;
};
void f1( T0 *R0 ) {
    write( find( R0->a0, R0->a1 ) );
}
void f0( T0 *R0 ) {
    if ( ++R0->a2 == 3 )
        f1( R0 );
}
int main() {
    T0 *R0 = Allocator::New( T0 );
    R0->a2 = 0;
    EventLoop::reg_read( "a.txt", f0, &R0->a0, R0 );
    EventLoop::reg_read( "b.txt", f1, &R0->a1, R0 );
    ... // computation of the sum
    f0( R0 );
}

Code generation

Sane currently mainly targets C++ and Javascript (WebAsm), but other languages are welcome :)

In all the cases, Sane provides the tool to generate whole programs (binaries and so on), but also code for functions, classes, modules... thanks notably to the deep introspection and (again) the compile-time execution abilities.

For instance, one can output the contents of a class made by generative programming:

class Foo
    def bar
        a + kv sum 0 .. 10

    def baz a: SI32, c
        a + c

    for name in "ab"
        \$name: SI32

# by default, Codegen generate code for methods returning something
# if not specified, arg_types are found using the type constraints
print Codegen.generate_code_for Foo, target: "C++", arg_types: { "baz": [ { "b": SI32 } ] }

It generates something like 

class Foo {
public:
    SI32 bar();
    SI32 baz( SI32 a, SI32 b );

    SI32 a;
    SI32 b;
}

SI32 Foo::bar() {
    return a + 45;
}
SI32 Foo::baz( SI32 a, SI32 b ) {
    return a + b;
}

Current status

All the features in the documents have been tested in intermediate prototypes. Since there's stable interpreter, the compiler is currently rewritten in Sane... so it's totally a good time for comments and potentially deep modifications !