The Quik programming language

Quik is a high concurrency, strongly typed, high level, general purpose programming language. You may ask why Quik exists when we already struggle to remember all the programming languages that are widely used. Well, here are the main three reasons:

1. Most traditional high level programming languages haven't been built for the programmer. Instead they were built for the compiler/parser. This means that generally these programming languages don't have an elegant syntax, and even worse, as time changes and requirements change, programs written in these languages become harder and harder to reason about.

2. You may say that you already know a programming language that works well for you. Like, everyone has is favorite. Well, odds are low that it is a pain to use for writing and testing concurrent programs. We are in the 21st century, aren't we? Quik solves this with a mixture of functional programming paradigms and Software Transactional Memory for mutable objects.

3. And, quite frankly, creating a programming language from scratch is fun 🚀.

What you'll find in this document:

• In a nutshell
• In more detail
• Status
• Installation
• Usage
• Development
• Release

For everything else visit https://quik-lang.github.io.

In a nutshell

Here are the main features of Quik, just to give you an idea of what it's like:

• Expression oriented - In Quik everything you write in a program is or is part of an expression. This makes Quik's syntax powerful, elegant and easy to learn.
• Refinement types - Refinement types make Quik safer, by allowing for domain specific checks at compile time, and easier to reason about, by allowing for a more mathematical notation and drastically reducing the need for error handling. Additionally, types in Quik are first-class citizens. Quik is strongly and statically typed. It's type system is completely "sound", meaning that type mismatches are caught before running your code. Quik infers types so that you only ever have to define them in function declarations. Quik supports encapsulation, generic types, polymorphism through interfaces, and a form of inheritance, but is not object oriented as it does not support subtyping.
• High concurrency - Quik makes it incredibly easy to write concurrent programs. It uses Software Transactional Memory for mutable objects, so that all mutations are atomic, consistent, isolated and durable. Side effects can also be handled safely. Channels can be used to transfer information between multiple threads.
• Easy to reason about - By removing common ways in which programs tend to become harder to maintain and understand, Quik becomes easier to reason about. It also supports multiple dispatch, operator overloading, list comprehensions, and destructuring assignments.
• Sophisticated package system - Quik has a package system much like ES6 modules. This makes it highly modular, but still keeps intentions explicit. It uses Yarn as a package manager.

In more detail

Expression oriented

In Quik everything you write in a program is or is part of an expression. While in a traditional statement oriented language you will see something like this:

public int func(boolean arg) {
  String str = null;
  if (arg)
    str = "abc";
  else
    str = "xyz";
  return doSomething(str);
}

In an expression oriented language like Quik, you'd simply do this:

func = (arg: Boolean): String =>
  if arg
    do_something('abc')
  else
    do_something('xyz')

In fact, as Quik only has expressions, declarations return values too. This plays nicely with the first-class citizen paradigm Quik follows. Whenever you declare a struct, for example, a new instance of Struct is returned.

type = struct Type
  # ...

IO.print type.name

EOP has another benefit. You don't have to think about whether some language construct needs a statement, expression, or even a condition as everything is and everything takes a condition. This makes Quik's syntax easy to learn, and more powerful.

Type system

Refinement types

Refinement types are a way of extending the reach of compile-time checks from type-only to domain-specific. Among the benefits are:

• a drastically reduced need for error handling, making code easier to reason about.
• a syntax that resembles mathematical formulas more closely.

The most common example for refinement types might be the (integer) division operator which is defined as a mapping of two integers where the latter must not be 0 to a decimal. Here is how you'd implement that in Quik:

/ = (left: Integer, right: Integer): Decimal
  | right != 0 => # left / right

This means that when using the division operator, you have to provide a proof that the divisor is not 0. So the following would result in a compile error:

1 / 0

Using a constant, providing a proof is trivial. When using references you might have to wrap them into an if expression:

/* trivial proof */
1 / 2

/* explicit proof */
if b != 0
  a / b

This has the benefit of making the user of an interface handle invalid states, instead of relying on error handling that gets confusing real fast, makes public interfaces more complicated, and simply is the wrong approach to these problems. Look at mathematic formulas and operations. We don't have error handling there. They are just defined for specific set of inputs. When you use them with an input the formula is not defined for, you are to blame, not the one who defined the formula.

Using refinement types with the multiple dispatch paradigm makes things even more fun. Look at this beautiful, concise and explicit definition of the Fibonacci sequence in Quik:

fib = (0): Integer => 0
fib = (1): Integer => 1
fib = (n: Integer): Integer | n > 1 => fib(n-2) + fib(n-1)

And just to contrast this, here is the Fibonacci sequence in Java:

public int fib(int n) {
  if (n == 0 || n == 1) {
    return n;
  } else if (n > 1) {
    return fib(n-2) + fib(n-1);
  } else {
   /* Ahhhhhhhrgh, I need HEEEEEEEEEELP!!
      Probably should throw something here.
      Let's define an exception.
      How did you do this again.
      Oh wait, what should I call it.
      Let's see what's still available
      Hmmm. our interface already defines [...] exceptions.
      Adding one doesn't matter, right?
      Or should I use an existing one instead?
      Yeah, just passing a descriptive error message should suffice.
      We can expand the interface later, if need be.
      (Good job: At least I thought of this edge case.) */
 }
}

Decide for yourself which implementation signals intent way, way more clearly.

On top of that: In Quik the dereferencing operator . expects a proof that its binding is not nil. This means that you won't get those nasty null pointer exceptions in Quik!

This will not compile:

object.attribute

This, however, will:

object?.attribute

if object != nil
  object.attribute

First-class citizens

In Quik everything has a type. These types can be defined by the programmer using Structs and Modules, or they can be provided by the standard library. The standard library provides type like Integer, Decimal, String, Boolean, Map, Tuple, and List, but also Struct, Module, Interface, Function, and Type. This means that all constructs of the Quik language are first-class citizens, meaning they are handled just like integers, decimals, strings, booleans and all other types. In fact the only way in which types provided by the standard library are different from custom types, is that they offer an implicit way of instantiating a new object. For integers that may be just writing a number, for structs that may be declaring it.

Every instantiable type implicitly includes the abstract struct _Object which provides instance functions like to_str: (_Object) -> String.

For some of these types provided by the standard library, Quik's parser accepts a specific syntax for type annotations:

{String -> String} == Map[String, String]
(String, Integer, Boolean) == Tuple[String, Integer, Boolean]
[Integer] == List[Integer]
(Integer, Integer) -> String == Function[Integer, Integer, String]

Encapsulation

You may have guessed it by now with all the talk about structs and modules: Yes, Quik supports encapsulation. In fact, encapsulation in Quik is at simple as it gets.

There are two methods of encapsulation available with Quik. Structs and modules. Structs are instantiable types that may provide a constructor, functions, and have attributes. Modules are singletons. They implicitly instantiate one instance upon first reference. This instance may provide functions, and have attributes. Lets have a look at them:

struct Object
  attribute = 'var'

  new = (...args: Array[String]): Void =>
    self.args = args

  get_arg = (index: Integer): String =>
    self.args[index]

module Singleton
  hello = 'Hello'

  hello_you = (name: String): String =>
    '{self.hello} {name}'

  plus_one = (int: Integer): Integer =>
    int + 1

There are a couple of notable things about this:

• The type Struct provides the module-level function new that calls the instance-level function new whenever a new instance of a struct is instantiated. A module is instantiated by calling its own block/body, thus modules essentially are namespaces.
• A self is implicitly set as the first parameter of every function you declare inside a Struct or Module. When you call a function on an instance of a struct or module, the instance is passed as the first argument to the called function.

  obj = Object.new()
  obj.func() == Object.func(obj)
  
  Singleton.func() # calls `func(Singleton)` inside the `Singleton` module.

By default, structs and modules are immutable (their state/attributes can only change when they are instantiated). You can, however, declare mutable structs and modules using the mutable keyword:

mutable struct State
  pass

This leaves you with four options for encapsulation:

1. immutable module - a namespace or an enumerable.
2. mutable module - a stateful singleton.
3. immutable struct - an instantiable type.
4. mutable struct - the closest thing to a class as in OOP.

So, as we've seen, objects and their attributes may be mutable. Quik does not have top-level variables. Constants in Quik are always immutable references. Once you assign to a constant, you can be sure that it will always encompass the same reference and be of the same type. You cannot be sure, however, that the value of the referenced object does not change unless it in of itself is immutable.

Generic types

Quik supports parametric polymorphism:

id = (x: X): X => x

struct CustomList[X]
  new = (list: [X]): Void =>
    self.list = list

  first = (): X =>
    self.list.get(0)

Polymorphism

Through interfaces, Quik also supports polymorphism. Much like in Go, interfaces in Quik aren't implemented. Instead, to determine if a type matches an interface, it has to define the same methods as the interface. An interface consists of a block of abstract functions. Abstract functions are functions that don't take a block. Here is an example:

interface Iterable[X]
  join = (sep: String): String

This interface then can be used like this:

func = (iterable: Iterable[String]) =>
  iterable.join(', ')

An empty interface matches every instance:

func = (object: interface Anything) =>
  # ...

Inheritance

Quik also has a way of doing something similar to inheritance:

• Structs can include other structs and modules.
• Modules can only include other modules.

This way you can add static context to structs:

struct User
  include module Static
    find = (id: Number): User =>
      # SQL query

  destroy = (): Void =>
    # SQL query

Quik does not support subtypes, and as such is not object oriented.

Access modifiers

Abstract structs and modules can only be included in other structs/modules. Abstract types are identified by a leading _. Private bindings are also denoted by a leading _ and can only be referenced from the same block or a child-block.

Quik does not have any modifier keywords like static, final, or private and protected.

Functions

In Quik, functions are first-class citizens. You have previously seen the use of . in Quik and probably thought it behaves like a the dereferencing operator as in a typical object oriented programming language. Actually in Quik . behaves more like a pipelining/composition operator:

object.attribute # calls `attribute(object)` in the context of `object.type`
Type.constant # calls `constant(Type)` in the context of `Type`

So . can be used to pipe arguments into functions:

fact = (0): Integer => 1
fact = (n: Integer): Integer
  | n > 0 => n * fact(n-1)

9.fact == fact(9)

You can also pipe arguments into specific positions:

9./(3)./(6, ?) == 2.0

Partial function application

Quik supports partial application of functions. So the following is possible:

Integer./.type == (Integer, Integer) -> Decimal
Integer./(?, 2).type == (Integer) -> Decimal

Multiple dispatch

Quik uses multiple dispatch as a paradigm eliminating the need to define multiple functions with distinct names for implementing similar behavior for different types. This simplifies program interfaces. In languages like Python or Ruby you would do this:

def collide_asteroid_asteroid(x, y):
  # collision of asteroid with asteroid

def collide_asteroid_spaceship(x, y):
  # collision of asteroid with spaceship

def collide_spaceship_asteroid(x, y):
  # collision of spaceship with asteroid

def collide_spaceship_spaceship(x, y):
  # collision of spaceship with spaceship

Whereas in Quik, you'd do:

collide_with = (x: Asteroid, y: Asteroid): Void =>
  # collision of asteroid with asteroid

collide_with = (x: Asteroid, y: Spaceship): Void =>
  # collision of asteroid with spaceship

collide_with = (x: Spaceship, y: Asteroid): Void =>
  # collision of spaceship with asteroid

collide_with = (x: Spaceship, y: Spaceship): Void =>
  # collision of spaceship with spaceship

Operator overloading

In Quik every operator internally calls a function. This means that the behavior of an operator depends on the type it is used on. The most common example for operator overloading is probably using the + operator for numeric values and strings. When used with numeric values it represents an addition, when used with strings it represents a concatenation.

An operation in Quik is in fact a function. You can use the symbols of operations just like regular identifiers:

struct CustomInteger
  new = (value: Integer): Void =>
    self.value = value

  + = (right: CustomInteger): CustomInteger =>
    self.value + right.value

CustomInteger.new(2) + CustomInteger.new(-1) == CustomInteger.new(1)

The multiple dispatch paradigm proves very useful in these cases. You can just define an operation multiple times with varying parameter or return types:

+ = (right: CustomDecimal): CustomDecimal =>
  self.value + right.value

A "sound" type system

Quik is strongly and statically typed. It's type system is completely "sound", meaning that type mismatches are caught before running your code. Quik infers types so that you only ever have to define them in function declarations.

Concurrency

Quik has quite a unique take on concurrency that sets it apart from most other (object based/oriented) languages. In some ways it is similar to what Haskell and Clojure do. Making concurrent programs easy(ier) to reason about and fun to write is the main focus of Quik. Most programming languages that introduced threading use a lock-based system that comes with quite a few disadvantages:

• you have to think about overlapping operations that may come form very distant areas of your code
• you have to adopt locking policies to prevent entering invalid states (deadlock, ...)
• when issues arise, they are very hard to reproduce & debug

This makes lock-based systems very, very hard to reason about, and very error-prone.

Quik uses two notions to fix this problem.

Communication

Quik supports the mantra "Do not communicate by sharing memory; instead, share memory by communicating." popularized by Go. Admittedly, Quik's take on thread communication is very similar to Go. Now, that's not a bad thing as Go's system of communicating through channels is nice.

In Quik any expression can be safely executed concurrently using the do keyword:

do IO.print(1 + 1)
do func('hello', (): Void => IO.print('callback called'))

Channels represent a way of communicating/passing data between threads. This method should always be preferred as sharing memory, while safe in Quik, can lead to unnecessary transactions that are bound to failure and reduce the performance of your code.

[Section on channels, threads and select expressions]

Immutability and Software Transactional Memory

In some cases you have to share memory between threads, and some other cases you do it without intent. After all, concurrency is hard, right?

No. In Quik sharing memory is safe. Here are the reasons why:

• Quik encourages the use of immutable variables (constants) and objects that are always thread safe.
• For mutable objects Quik automatically uses transactions to make sharing memory, and producing side effects safe.

The use of Software Transactional Memory in Quik makes every update of mutable attributes atomic and safe. Whenever you make an assignment to a mutable attribute (outside of a transaction), Quik initiates a transaction. Here is how a transaction works in Quik:

1. It saves the current state of the mutable attribute and adds it to an assignment queue.
2. Perform the operation/expression the transaction is wrapped around:
   • It adds side effects to a side effects queue.
   • If it reads (or assigns to) a mutable variable (attribute) that is dirty, the transaction enters a waiting state. When this change in state results in a deadlock the transaction is aborted.
   • If there are nested assignments it adds them to the assignments queue with their current state. It then branches the attribute and uses the update version for all further occurrences of it within the transaction.
3. It then starts the commit:
   • It goes through the assignment queue and saves it unless the state in memory is different from the state stored at the begin of a transaction or the current state is dirty.
   • A log is kept of all performed changes in memory.
   • Each assignment also locks the mutable variable (attribute) by setting the dirty bit.
   • It then calls is_valid(): Boolean on all affected objects.
4. If the commit fails:
   • The transaction aborts and all changes are reverted.
   • The side effects queue is emptied.
   • The transaction is safely retried.
5. If the commit succeeds:
   • The locks are lifted and the waiting queue is cleared.
   • The side effects queue is processed.

Note: If a transaction produces an error, an uncaught exception, or runs infinitely (all of this may happen because it reads values from memory as another transaction commits and thus ends up in an invalid state), it is aborted and retried

Side effects are denoted using the hold keyword:

hold IO.print 'This is a side effect!'

That's not everything. You can do some really fancy stuff, using Quik's atomic and retry keywords.

atomic opens a new transaction and retry aborts it and, well, retries:

atomic
  if queueSize > 0
    # remove item from queue and use it
  else
    retry

Easy to reason about

Quik promotes programming patterns that do not make programs hard to reason about once they grow and requirements change without limiting its expressiveness. Here are some of the things you will not find in Quik:

• for or while - promoting ways of iterating that more clearly signal intent.
• Inheritance - promoting other means of polymorphism.

Fail fast, be productive

Core to Quik is the mantra of "fail-fast". Quik tries to fail as soon as it notices something that is prone to failure at runtime. Part of that is Quik's "sound" type system. When Quik fails it gives you descriptive error messages with hints as to how you might be able to fix the problem making it very productive and good for prototyping.

Sophisticated package system

Quik has package system much like ES6 modules. Thus you can import and export from a file much like with ES6:

import IO
import Type from 'package'
import Type as A from 'file'

struct CustomType
  pass

export default CustomType

Destructuring assignments

Quik supports destructuring assignments of lists, tuples, maps, objects, and types:

[a, b] = [1, 2]
# a == 1
# b == 2

(a, b, c) = [1, 2, 3]
# a == 1
# b == 2
# c == 3

{'key' => a} = {'key' => 1}
# a == 1

struct A
  new = (attribute: Integer): Void =>
    self.attribute = attribute

{'attribute' => a} = Struct.new(2)
# a == 2

module B
  const = 0

{'const' => b} = Module
# b == 0

Low memory footprint

Most built-in data structures like lists, tuples and maps are implemented as Persistent Data Structures and use a combination of path copying and fat nodes to keep memory footprint low and access speeds high.

General purpose

Quik aims to be a general purpose language and as such is supposed to provide a wide variety of packages for networking, io, numerical computing, and more.

Small standard library

One of the major design decision for Quik is to keep its standard library as small as possible. As Quik is highly modular, most functionality can be added through Quik's package system. Keeping the standard library small, means that all separate packages and Quik itself are highly agile and can make important design decisions at a much faster pace.

Status

✔ Lexer

✔ Parser

✖ Analyzer

✖ Compiler

✖ Standard library

✖ Interpreter

✖ Shell

✖ Syntax highlighting (Tree Sitter, Pygments)

✖ Linter

Installation

Follow these steps to install Quik:

1. Clone this repository

   $ git clone [email protected]:quik-lang/quik.git

2. Install Node either by running asdf install or by installing the version of Node as listed in .tool-versions with your favorite version manager.

3. Install Quik

   $ yarn install
   $ yarn build
   $ yarn link

Usage

Start the interactive shell:

$ quik

Setup a new Quik project in the working directory:

$ quik init

To parse a test.qk:

$ quik parse test.qk

To compile the project in the current directory:

$ quik compile

To run the project in the current directory:

$ quik run

To get a list of all available commands and options:

$ quik --help

Development

Listen to changes and make them accessible through quik from the command line:

$ yarn start

Run ESLint:

$ yarn eslint

Run TypeScript compiler checks:

$ yarn tsc

Run tests:

$ yarn test

Release

1. Review breaking changes and deprecations in CHANGELOG.md.
2. Change the version in package.json and src/version.ts.
3. Reset CHANGELOG.md.
4. Create a pull request to merge the changes into master.
5. After the pull request was merged, create a new release listing the breaking changes and commits on master since the last release.
6. The release workflow will publish the package to NPM and GPR.