The Kvasir Programming Language

UNMAINTAINED

Kvasir is no longer maintained, in favour of a remake in Haskell called Carth. See https://git.sr.ht/~jojo/Carth.

About

Kvasir is a toy programming language, much inspired by Haskell, LISP/Scheme/Racket, and Rust. Kvasir is intended to in the future maybe be used for interactive and type-safe game programming. Who knows.

Example

;; Exercise 1.16 in SICP
;;
;; A logarithmic implementation of exponentiation.
;; Uses iterative recursion to accumulate the answer.
(define (expt b n)
  (let [[(iter acc b i)
         (cond ((= i 0)
                acc)
               ((even? i)
                (iter acc (square b) (/ i 2)))
               (else
                (iter (* acc b) b (- i 1))))]]
    (iter 1 b n)))

;; The algebraic data type of a singly linked list
(data (List a)
  Empty              ; Either the list is empty
  (Node a (List a))) ; or it's an element followed by the rest of the list
  
;; Mapping a function over each element of a list
(define (map f xs)
  (match xs
    [Empty        (new Empty)]
    [(Node x xs') (new Node (f x) (map f xs'))]))

Features

• Lisp style, parenthesis based syntax. Looks quite Scheme-y.
• Static typing
• (TODO: Bounded) parametric polymorphism
• Global type inference
• Reference count garbage collection (unimplemented)
• Efficient C bindings/ffi
• LLVM backend

Building from source

The following tools and packages are required to build:

• Nightly rustc and cargo, suggested to get via rustup.
• LLVM 5.0 library (6.0 seems to work fine as well) and related llc
• clang (can easily be modded to use gcc, might make that a feature…)
• git

Nightly rust

A few nice, but not critical, unstable features are used, which implies the requirement of nightly rust. Hopefully these features will be stabilized soon, otherwise, I could probably remove them if there exists a demand for it.

llvm-sys

The rust crate llvm-sys is used for interfacing with the LLVM C-interface. Depending on your distribution and such, getting llvm-sys and LLVM to play nicely together and in general can be troublesome.

A common problem seems to be that the command llvm-cfg incorrectly reports which libraries are necessary to link with for applications using LLVM. I’ve had problems with libtinfo and libffi not being included correctly myself.

The symptoms of this is that you get errors like

error: linking with `cc` failed: exit code: 1
  |
  = note: "cc" "-Wl,--as-needed" "-Wl,-z,noexecstack" ...  "-l" "pthread" "-l" "util" "-l" "util"
  = note: /home/.../libllvm_sys-b4b9c2e4bce947fe.rlib(ExternalFunctions.cpp.o): In
function `llvm::Interpreter::callExternalFunction(llvm::Function*, llvm::ArrayRef<llvm::GenericValue>)':
          ExternalFunctions.cpp:(.text._ZN4llvm11Interpreter20callExternalFunctionEPNS_8FunctionENS_8ArrayRefINS_12GenericValueEEE+
0x3f3): undefined reference to `ffi_type_float'
...
          ExternalFunctions.cpp:(.text._ZN4llvm11Interpreter20callExternalFunctionEPNS_8FunctionENS_8ArrayRefINS_12GenericValueEEE+
0x2408): undefined reference to `ffi_type_sint32'
          collect2: error: ld returned 1 exit status


error: aborting due to previous error

error: Could not compile `kvasir-lang`.

To fix for libffi not linking, compile with environment variable LLVM_SYS_50_FFI_WORKAROUND=1.

LLVM_SYS_50_FFI_WORKAROUND=1 cargo build --release

To fix in general, for other libs than ffi, make sure that you have the newest compatible version of LLVM (maybe try building from source?), and pray.

Building

Clone the repo:

git clone https://github.com/bryal/kvasir
cs kvasir

Build:

cargo build --release

When the build is finished, the actual executable for the compiler can be found in target/release/kvasir. To install, place the executable somewhere in your PATH.

Core library

By itself, the compiler can’t create very interesting programs. To actually get some functionality you would have to call code from some external library that you link into your program.

You can compile a rudimentary core library by executing the script build_core.sh, which will compile the C file src/core.c and the LLVM IR file src/core.ll into a new library libcore.a, which can then be linked with your program with the -l flag.

Usage

$ kvasir -l core examples/test.kvs
$ ./examples/test.bin
1337

Roadmap

• [_] Comprehensive standard library (Ongoing WIP)
• [_] Modules (Basic import system exists, but does not solve name collisions)
• [x] Algebraic data types
• [x] Pattern matching
• [x] Unbounded parametric polymorphism (I.e. Hindley-Milner)
• [_] Bounded parametric polymorphism (à la typeclasses/traits/interfaces)
• [_] Higher kinded types (to allow for stuff like Functor, Applicative, Monad)
• [x] Macros
• [_] Build system / package manager
• [_] Working refcount garbage collection (broken/partly unimplemented atm)

Contributing

As this is a project for education and fun, I’m not much interested in outside help with implementation. However, bug reports, feature suggestions, and comments in general are welcome!

License

Copyright (C) 2018 Johan Johansson

GPLv3

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

See LICENSE