refu-lang/refu

Refu language

Refulang

This is the code repository for refu, a hybrid language with a strong type system based on algebraic data types.

For a language reference, tutorial and overall documentation visit here.

Dependencies

The required dependencies are:

• For building we need cmake
• For the backend code generation we need llvm
• For hash table generation we use gperf
• For units tests we need libcheck

The optional dependencies are:

• For generating dependency graphs, we can use graphviz
• For extra memory checks during unit testing, we can use valgrind
• For generating a json file of the AST, we can use json-c
• For regular expressions (not yet used anywhere yet), we can use pcre2
• For generating code coverage reports we can use lcov

Dependencies in Linux

Use your distribution's package manager

Dependencies in Macosx

brew install cmake
brew install pkg-config
brew install check
brew install llvm
brew install lcov

Installing llvm does not place it into the PATH and as such you will also need to put its path there manually. In recent versions this means adding the following to .profile.

export PATH="$PATH:/usr/local/opt/llvm/bin/"

Building

git clone --recursive https://github.com/refu-lang/refu
cd refu
mkdir build
cd build
cmake ..
make

Run the tests

In order to run the tests you have to also build them. This is done by providing an extra option to cmake.

cmake -DCMAKE_BUILD_TYPE=Debug .. -DTEST=1

There is a convenience test script that runs all of the tests for refu and its rfbase submodule.

./test.sh --rfbase

Usage

You can invoke refu --help in order to get all the possible arguments along with their description.

Example:

 --help                                                  display this help and exit
 --version                                               display version info and exit
 -v, --verbose-level=1-4                                 Set compiler verbosity level
 --backend=GCC|LLVM                                      The backend connection the refu compiler will user
 --backend-debug                                         If given then some debug information about the backend code will be printed
 --output-ast                                            If given then after analysis state the AST will be output in JSON format
 -o, --output=name                                       output file name. Defaults to input.exe if not given
 --rir                                                   Interpret the input file as a RIR file and parse it.
 -r, --print-rir                                         If given will output the intermediate representation in a file
 <file>                                                  input files

At the moment these are the important arguments.

• --verbose-level Will determine how verbose the output of the compiler will be.

• --backend-debug Will print out to the stdout the LLVM IR for debugging purposes.

• --output-ast Will output the Abstract Syntax Tree in a .json format

• --print-rir Will print the generated Refu Intermediate Format (RIR) for deugging purposes.

Contributing

You are more than welcome to open a Pull Request here in Github if you would like to contribute to the development of refu.

Coding Style and Best Practises

TODO

refu's Issues

Become self-hosting

Rewrite a substantial amount of the compiler in Refu itself.

Build issue on Mac

I'm not able to build refu using Unix makefiles, but it works when using Ninja as the build system (cmake -G ninja ..).

With Unix makefiles it will not scan the target directories for gperf files and will not generate them.

$ cmake --version
cmake version 3.7.2
$ make --version
GNU Make 3.81
$ ninja --version
1.7.2

Improve type_get_uid()

Sum types that are permutations of one another should have same unique key.

Make compatible with Windows OS

Nobody has ever attempted to compile refu in Windows. I believe it will require some work to make it happen. This issue is to track work towards that goal.

• Make necessary code changes to allow for compilation in Windows.
• Make appropriate entries in the readme with a guide how to compile in Windows.

Refactor functions in ast_constants.h

Refactor the functions in ast_constants.h to accept an ast_node as an argument.

Turn llvm_traversal_ctx to static thread local

This is a design decision that I am not so sure about. At the moment almost all of the backend llvm functions take the llvm_traversal_ctx as an argument. Example here.

Maybe it would be beneficial to make it into a static global thread local variable.

Using Refu in eWASM to write Ethereum contracts

With #34 in place it seems to be possible emitting WebAssembly from Refu.

In order to write contracts, the following is needed:

1. A bignumber library, perhaps optimised for 256 bit numbers.
2. A standard library specifying the foreign_imports for all the Ethereum interface methods.
3. A framework providing high level Ethereum features (built on top of 1. and 2.)

Crashes if not passing input file

$ ./refu 
Segmentation fault: 11
$ lldb ./refu
(lldb) target create "./refu"
runCurrent executable set to './refu' (x86_64).
(lldb) run
Process 95178 launched: './refu' (x86_64)
Process 95178 stopped
* thread #1: tid = 0x157bdf9, 0x00000001000d23fc refu`llvm::LLVMContext::removeModule(llvm::Module*) + 4, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=1, address=0x0)
    frame #0: 0x00000001000d23fc refu`llvm::LLVMContext::removeModule(llvm::Module*) + 4
refu`llvm::LLVMContext::removeModule:
->  0x1000d23fc <+4>:  movq   (%rdi), %rdi
    0x1000d23ff <+7>:  popq   %rbp
    0x1000d2400 <+8>:  jmp    0x1006e1d76               ; llvm::SmallPtrSetImplBase::erase_imp(void const*)
    0x1000d2405 <+13>: nop    

Determine signedness of comparisons in the RIR

At the moment we simply ignore signedness of the compared integers and just always do signed comparisons.

This is an issue to track the implementation of:

Check the signedness of the integers of a comparison during RIR stage and:

• if any of the two integers is signed then do signed comparison
• if both are unsigned then do unsigned comparison

Implement compound arithmetic operators

Compound arithmetic operators (+=, -=, *=, /=) are missing from the language at the moment.

This is an issue to track the implementation of their addition to the language.
TODO:

• Add the appropriate lexer tokens to the lexer.
• Test scanning of those tokens in the lexer.

• Add them to the parsing stage during the AST generation
• Test the parsing and AST generation of compound operators.

• Do the same typechecking their non-compound binary operator equivalent does.
• Make tests for the above.

• Generate RIR and backend code for the compound operators in the same way the arithmetic
  binary operators do.
• Add end to end backend tests

Note: This issue requires a lot of work, but is quite easy to do since the logic already exists throughout the code for the arithmetic operators. So implementation is just looking at what already exists and duplicating it with some modification.

For that reason it could be a nice deep-dive introduction to the codebase for someone who wants to learn how refu works.

Type operator associativity

Many of the type operators should have the associative property.

As an example the sum type:
string | i32 is the same as i32 | string and yet the current implementation does not view it as such.

I suppose same goes for product types:

string, i32, bool should be equal or at least convertible (with a warning since memory layout changes?) to any other permutation like: i32, bool, string.

Implement backend code generation for iterable ranges

Iterable ranges used in for expressions are accepted and typechecked but no proper backend code is yet generated.

Implement the backend code generation for constructs like the following:

for a in 1:2:10 {
}

There is a different issue tracking the variable range backend code generation: #29

Implement typeclasses for analysis and backend state

At the moment typeclasses are only parsable but not used at all from the analysis stage and forward. Utilize them and do the proper typechecking and backend code generation.

Make Compatible with macOS.

I have not tried to build refu in macOS so I can't confirm yet whether or not it is possible out of the box. Possibly requires a bit of adjustment. This issue is to track:

• Make necessary code changes to allow for compilation in macOS.
• Make appropriate entries in the readme with a guide how to compile in macOS.

Implement Type Inference

Fully implement proper type inference where possible.

Redesign logic of parser->has_syntax_error

The parser currently has this variable has_syntax_error and there are functions like parser_has_syntax_error() that use it.

Try to remove this logic and instead use the newly introduced info_ctx rollback along with a smart detection of if there was an error or not between a push and a pop.

There is a TODO for this here

Make the IR loadable from a file

Implement the ability to load the Refu Intermediate format from a file.

Write tests for type_get_uid()

Also put some other salt in the name to differentiate in the symbol tables between objects of same anonymous type in the same block.

Implement backend code generation for variable ranges

Iterable ranges used in for expressions can also have variables as the start, step or end value. That works fine until the typechecking stage but there is no code for it in the intermediate representation or the backend code generation.

Implement the intermediate format and backend code generation for constructs like the following:

fn (start_index:u32, end_index:u32) {
    for a in start_index:2:end_index {
        print("foo")
    }
}

Improve ast node headers

Some ast headers contain inline functions and need to include ast/ast.h for various reasons. This can be sort of ugly and in addition can create danger of circular dependencies.

Figure out if that can be addressed and the code organized a bit better to avoid it.

Implement variable iterable ranges

At the moment in refu we can only have a range with constant numbers such as:

for a in 1:2:10 {
}

Implement variable ranges so that the range start, step and end can also be an identifier. For example the following should also be possible:

for a in b:2:c {
}

[Experiment] Emit also WebAssembly in the backend

Think on the benefits of adding emitting web assembly from Refu.
Think if it makes sense to also emit WebAssembly code for web development.

It would be quite easy to do since LLVM can directly translate to Web Assembly

Migrate all issues and tasks from Trello to Github

Migrate all issues from Trello and also create the corresponding labels.

Move the language specification to this repository

Even though it's unfinished move it to this repository into a /docs directory and convert it to markdown.

Test lexer errors and their reported locations.

At the moment tests only exist for proper scanning of tokens, but not for the lexer unhappy cases.

Make some new tests for the lexer errors and assert also that the reported file locations are correct.

Make the IR saveable into a file

Implement the ability to save the Refu Intermediate format to a file.

Program verification

Use a prover like why3 in order to provide the ability to prove invariants about the logic of functions of the language in compile time.

Set Default Address Space in LLVM Functions

Replace the 0 in most functions that take a default address space with a #defined value. There is one located here

Allow conversion of non constant int to string

It should definitely be allowed to convert an int/float variable to string but the way to do that needs some thinking.

At the moment it can only be a conversion at compile time. A variable conversion would work only at runtime (unless we introduce some form of const variables optimization).

Should the same notation be used for compile time and runtime conversion and just leave it to the compiler to figure it out?
(my vote at the moment is yes)

a:i32 = 56 s:string = string(a)
versus
a:i32 = 56 s:string = to_string(a)

At the moment we allow explicit type conversion from almost all constant types to string. This is also tested here.

TODO:

Implement explicit conversion of elementary type variables to string.

Add postfix increment/decrement operator

At the moment we only have a syntactic prefix increment and decrement operator ++ and -- which acts like a postfix operator.
Think on whether we also want the postfix one and if yes then properly implement the different behaviour in the backend too.

Remember that the rule is:

• Postfix operator evaluates the value of the expression prior to incrementing or decrementing
• Prefix operator evaluates the value of the expression after incrementing or decrementing.

At the moment in the backend we simply increment or decrement one to the expression's value after it has been evaluated.

Make sure all bllvm_compile_XXX functions error paths are checked

Check all bllvm_compile_XXX() function's error path returns and make sure so that all errors can be handled a bit more gracefully. Example function here.

Errors here are fatal, but still it's our job to try and have a graceful exit.

Lazy Evaluation [Meta]

This is a Meta issue for the implementation of lazy evaluation in the places in the code where it needs to be done.

Make code compatible with gperf 3.1

Gperf 3.1 introduced various changes most important of which is the change of an argument type in the hash and lookup function. At the moment using that version breaks the build, so we have to make the code compatible with it.

Add a clang-sanitizers test-build in the CI.

Integrate clang-sanitizer in a special build and add it to Travis.

Even though we currently have valgrind run in Travis it would be nice to also have clang's sanitizers. Add the following sanitizers:

• address
• memory
• undefined behaviour
• memory leaks

Optionally add in the future but not needed now:

• thread sanitizer. At the moment no threads are used so this is not needed yet.
• data flow. To check conformance to an ABI we would specify. Also not needed.