Introduction

Welcome to the Hark guide.

The purpose of this guide is to get you happily productive with Hark as fast as possible.

The guide is version controlled in the Hark repository, and should be kept in sync with Hark releases.

The version you’re reading was published for Hark v0.5.0.

Quick links:

Onwards!

(Tip: use your keyboard ⇦ & ⇨ to navigate)

Why Hark?

Hark is not a replacement for your favourite mainstream language. It does something new: eliminates the need to write infrastructure.

Serverless applications are inherently distributed, and building distributed systems by hand is hard. It’s much easier to think about them as monolithic applications which are then compiled into distributed applications.

Hark lets you do that. Some benefits:

Local testing. Full local testing of the application logic (you still have to mock out third party services).
Advanced metrics. Automatic log aggregation (like structured logging), making for much easier contextual debugging. Deep insight into application performance and cost (way better than the context-free AWS reporting).
Deployment. Trivial deployment or rollback of entire applications, not just single functions.
Portability. Hark is naturally cloud-agnostic. Only the AWS runtime has been implemented so far, but in principle, Hark programs are fully portable across execution environments.

Soft infrastructure

Don’t write infrastructure when you want to write software.

No one writes assembly code anymore. Infrastructure is a bit like assembly.

Most infrastructure patterns are repeatable, and can be described in simple terms—”send outputs from here to there”, or, “this function needs to respond within 30ms to millions of messages concurrently”.

Most of those patterns correspond to familiar software concepts—value assignment, function calls and concurrency.

Instead of writing infrastructure, write software that gets compiled and uses serverless infrastructure to get all the benefits, but doesn’t expose the complexity.

Using Hark means you get a solid, infrequently changing, and well-understood infrastructure platform, rather than manually wiring together complicated flow-charts yourself.

Other approaches

Hark was originally created for building serverless data pipelines, and this is its primary use-case. There are a couple of common ways to process data in AWS.

Here’s how Hark stacks up.

Method	Fully Serverless?	Familiar programming model?	Local testing possible?	Setup time
Large EC2 instance	No	Yes	Yes
Workflow managers (Apache Airflow etc)	No	No (usually a “DAG” model)	Yes (docker image)
Task runners (Celery, CI tools)	No	Yes (usually a simple API)	Yes
AWS Step Functions	Yes	No (flow-chart model)	Yes (docker image)
DIY: Lambda + SQS + custom logic	Yes	Yes, but lots of AWS to learn	Tricky (localstack...)	Hours to days

Hark	Yes	Yes (new language, but familiar concepts)	Yes (built-in)	60s

Hark is like AWS Step Functions, but is cheaper (pay only for the Lambda invocations and process data), and way easier to program and test. The tradeoff is you don’t get tight integration with the AWS ecosystem (e.g. Hark doesn’t natively support timed triggers).

Hark is like Azure Durable Functions -- it lets you pause and resume workflows, but it’s (subjectively) nicer to write. The syntax feels natural. Also it’s not bound to Azure.

Hark is like a task runner (Celery, Apache Airflow, etc), but you don’t have to manage any infrastructure.

Hark is not Kubernetes, because it’s not trying to let you easily scale Dockerised services.

Hark is not a general-purpose programming language, because that would be needlessly reinventing the wheel.

FAQ

Why is this not a library/DSL in Python?

When Hark threads wait on a Future, they stop completely. The Lambda function saves the machine state and then terminates. When the Future resolves, the resolving thread restarts any waiting threads by invoking new Lambdas to pick up execution.

To achieve the same thing in Python, the framework would need to dump the entire Python VM state to disk, and then reload it at a later point -- this may be possible, but would certainly be non-trivial. An alternative approach would be to build a langauge on top of Python that looked similar to Python, but hark wrong because it was really faking things under the hood.

How is Hark like Go?

Goroutines are very lightweight, while Hark async functions are pretty heavy -- they involve creating a new Lambda (or process, when running locally).

Hark’s concurrency model is similar to Go’s, but channels are not fully implemented so data can only be sent to/from a thread at call/return points.

Is this an infrastructure-as-code tool?

No, Hark does not do general-purpose infrastructure management. There are already great tools to do that (Terraform, Pulumi, Serverless Framework, etc).

Instead, Hark reduces the amount of infrastructure you need. Instead of a distinct Lambda function for every piece of application logic, you only need the core Hark interpreter (purely serverless) infrastructure.

Hark will happily manage that infrastructure for you (through hark deploy and hark destroy), or you can set it up with your in-house custom system.

Cases for Hark

Data pipelines (workflows)

Hark was originally created for building serverless data pipelines, and this is its primary use-case.

Here’s an example of a task which

is triggered on S3 upload
solves an embarassingly parallel problem

import(split_file, src, 2);
import(process_chunk, src, 1);
import(save_all, src, 1);

// bucket and key filter configured elsewhere (hark.toml)
fn on_upload(bucket, key) {
  chunks = split_file(bucket, key);
  results = map_async(process_chunk, chunks);
  save_all(results);
  print("Finished ᵔᴥᵔ");
}

Key points:

Every chunk of the file will be processed by process_chunk in parallel (map_async defined elsewhere).
While that happens, the Lambda running on_upload is completely stopped. So you don’t waste computation time.
You can run this program locally before deployment to test the logic. For example, what happens if process_chunk passes a bad value to save_all? It’ll be much easier to debug that kind of situation locally than in the cloud!

Background web tasks

Hark has basic support for API Gateway endpoints, which means you can trigger long-running background tasks from your website frontend, and easily keep track of when they complete.

fn on_http(method, path, body, lambda_event) {
  if path == "/dump_data" {
    async dump_user_data(lambda_event);
    {"session_id": sid()};  // use the ID to check the dump status later
  }
  else if ...
}

Getting Started

You can install hark through pip or otherwise

pip install hark-lang

Like any modern language or framework, a hello-world should be instant. So let us do that...

Hello Worlds!

Hello world in hark looks like this. Type or paste this in your favourite editor.

// service.hk

fn hello_world() {
  "Hello from hark!"
}

Which we can run locally:

hark service.hk -f hello_world

Explanation

Hark files contain imports and Hark functions. The command line program allows us to specify which Hark function to invoke with the -f argument. The age old main function convention also applies in Hark.

Our service.hk when run without an explicit function will tell us that we dont have a main function.

hark service.hk

Can't run function `main'.
Does it exist in service.hk?

We can solve that easily by adding a main.

// service.hk

fn hello_world() {
  "Hello from hark!"
}

fn main() {
  hello_world()
}

Deploy something!

We’ll now build a slightly bigger program and run it on AWS. This time, there is Hark and Python, and multiple threads.

In a fresh directory, create the bare minimum files for a new project:

$ hark init

Source code

Add some complicated Python:

# src/__init__.py

def complicated_stuff(x):
    print(f"Complicated! {x}")
    return x * 10

And some Hark:

// service.hk
import(complicated_stuff, src, 1);

fn map(func, items, acc) {
  if nullp(items) {
    acc
  }
  else {
    map(func, rest(items), append(acc, func(first(items))))
  }
}

fn wait(item) {
  await item;
}

fn complicated(x) {
  async complicated_stuff(x);
}

fn main() {
  results = map(complicated, [1, 2, 3, 4, 5], []);
  map(wait, results, []);
}

This:

imports the Python function
creates a map function and helpers
runs complicated_stuff on every element of an array, at the same time (with async)
waits for all results to come back

There are several new concepts here, particularly in the implementation of map. Briefly, map works by calling itself recursively (which the compiler optimises) until the list of inputs runs out, at which point it returns the accumulated results. This will eventually be in the Hark “standard library” - coming soon!

Test first!

$ hark service.hk
Complicated! 1
Complicated! 2
Complicated! 3
Complicated! 4
Complicated! 5
[10, 20, 30, 40, 50]

-- 0s

Looks right enough.

Deploy

Ensure your AWS credentials are correctly configured, and that AWS_DEFAULT_REGION is set.

$ hark deploy

Reply Create a new self-hosted instance (using local AWS credentials) to the question -- this will create a new Hark instance in your account.

Expected output:

Target: Self-hosted instance xxx.......

✔ Deploying infrastructure Build data: ....../.hark/
✔ Checking API Hark 0....
✔ Deploying service.hk

Done. `hark invoke` to run main().

-- 56s

You could also deploy with the verbose flag, -v, to see details of what is changed.

Run!

This will take a little while, because the Lambda function is being spun up for the first time.

$ hark invoke
Target: Self-hosted instance xxx.......

✔ main(...) 3e50fbf3-5e3e-47bf-b949-a93b1cdf08b0
✔ Getting stdout...

Thread   Time
=========================================
     1   +0:00:00          Complicated! 1
     2   +0:00:01.280391   Complicated! 2
     4   +0:00:02.358765   Complicated! 4
     3   +0:00:02.652161   Complicated! 3
     5   +0:00:03.700506   Complicated! 5


=>
[10, 20, 30, 40, 50]

-- 17s

Success! Lambda was invoked 6 times here -- once for each thread (including the top-level thread 0).

Developing with Hark

Good practices and approaches to developing Hark-powered serverless applications.

Creating a new project

Hark does not enforce a particular project structure on you. For a good starting point, you can clone https://github.com/condense9/starter-project. In this tutorial, we will start from scratch to take away some of the mystery.

The plan

Implement a pipeline that counts the number of words occuring in a randomly generated essay from https://metaphorpsum.com.

Returns the run-length encoded (rle) contents of the essay along with the word frequency count.

Project skeleton

Create a new python project, we will use poetry in this case.

poetry new --src hark-rle
cd hark-rle
poetry add hark-lang
poetry install
hark init

We want our Hark code to parallelise the processing of a (potentially) large essay. To start, we can implement the word counter and rle encoding code in python. Here is an implementation you can copy. Alternatively feel free to write (and unit test) your own.

# hark-rle/src/hark_rle/__init__.py

from functools import reduce
from typing import Dict, List, Tuple
from collections import Counter


def _make_encoding(encoding: List[Tuple[int, str]], c: str) -> List[Tuple[int, str]]:
    if not encoding:
        return [(1, c)]

    *init, (count, character) = encoding
    if character == c:
        return [*init , (count + 1, c)]
    else:
        return encoding + [(1, c)]


def cleanup(paragraph: str, *, remove_spaces: bool = False):
    clean = paragraph.lower().strip()
    if remove_spaces:
        return clean.replace(' ', '')
    else:
        return clean


def rle_encode(paragraph: str) -> str:
    characters = cleanup(paragraph, remove_spaces=True)
    encoding = reduce(_make_encoding, characters, [])
    return ''.join(f'{count}{character}' for count, character in encoding)


def word_counts(paragraph: str) -> Dict[str, int]:
    words = cleanup(paragraph).split()
    return dict(Counter(words))


__version__ = '0.1.0'

Next we can modify the hark file to do our processing. Here is an example of what we might want:

// service.hk

import(rle_encode, hark_rle, 1);
import(word_counts, hark_rle, 1);


fn main(contents) {
    encoding = async rle_encode(contents);
    frequencies = async word_counts(contents);
    {
        "encoding": await encoding,
        "frequencies": await frequencies
    }
}

We can now run the hark code locally for example:

poetry run hark service.hk "the quick brown fox jumps over the lazy dog"

If we are happy with that, we can get our essay from metaphorpsum.com instead of passing command line arguments. Lets add a nice library to make these requests with.

poetry add httpx

We can add the following to our hark_rle python code to grab a paragraph to be processed. Add the following function to the python code:

# hark-rle/src/hark_rle/__init__.py
...
import httpx
...

def paragraph() -> str:
    url = "http://metaphorpsum.com/sentences/50"
    resp = httpx.get(url)
    resp.raise_for_status()
    return resp.text


__version__ = '0.1.0'

And update service.hk:

// service.hk

import(rle_encode, hark_rle, 1);
import(word_counts, hark_rle, 1);
import(paragraph, hark_rle, 0);


fn main() {
    contents = paragraph();
    encoding = async rle_encode(contents);
    frequencies = async word_counts(contents);
    {
        "encoding": await encoding,
        "frequencies": await frequencies
    }
}

And test:

poetry run hark service.hk

Configuration with hark.toml

Hark is configured with a file called hark.toml, usually located in the directory where the hark CLI is invoked (pass --config to use a different file).

When you run hark init, hark.toml is created with the following default content (values uncommented here):

## hark.toml
##
## This is where all Hark configuration takes place. Default values are
## indicated where it's appropriate to do so.
##
## Hark will work just fine without any modifications to this file, but you'll
## probably want to tweak things!

[project]

## File containing Hark code to be deployed
hark_file = "service.hk"

## Location of Python source
python_src = "src"

## Location of Hark build data
data_dir = ".hark"

## Location of Python dependencies
python_requirements = "requirements.txt"

## Path to the Python source lambda layer package (zip). If not defined, Hark
## will use pip to install requirements from python_requirements and copy source
## from python_src
package = "package.zip"

## The command to build project.package, if you have a build script
build_cmd = "./build.sh"


[instance]

## Additional AWS IAM policy statements to attach to the instance role
policy_file = <file.json>

## Extra source layers to use (maximum of 4)
## e.g., from: https://github.com/keithrozario/Klayers
extra_layers = [ ]

## Lambda function timeout (s)
lambda_timeout = 240

## Lambda function memory (MB)
lambda_memory = 128

## File with lambda environment variables
env = "hark_env.txt"

## Names of S3 buckets that `hark deploy/destroy` manages
managed_buckets = [ ]

## Names of S3 buckets to enable read/write
s3_access = [ ]

## List of S3 upload triggers. Format: [[bucket, prefix, suffix], ... ]
## Example: [["my-bucket", "images/", ".jpg"], ...]
upload_triggers = [ ]

## Enable the API Gateway trigger
enable_api = false

[project]

These are project-specific configuration parameters.

Most of these don’t need to be changed, except for build_cmd and package. Hark can build Python projects that use a requirements.txt file to list Python dependencies. If you use a different method, use package and build_cmd to hook into hark deploy.

package: If defined, this will be used to locate the Lambda layer package - be sure to follow the AWS docs for packaging this.

build_cmd: If defined, will be run before every hark deploy. Note: package must also be defined in this case.

[instance]

These are instance-specific configuration options. At the moment, Hark only supports a single instance per project, but in the future it may support multiple (e.g [instance.dev], [instance.prod]).

In particular:

env: Set run-time environment variables here (will be copied into the Lambda environment) in the usual (dotenv style) VARIABLE=value format.

lambda_timeout and lambda_memory: Control the function timeout and memory allocation.

Hark will handle some infrastructure changes for you:

s3_access: Your program will be given full read/write access to S3 buckets listed here. Note: must also be added to managed_buckets.

upload_triggers: Configure S3 triggering here. Usually you’ll want to filter the trigger by key prefix and suffix, which this supports. See File uploads.

managed_buckets: Hark will only modify buckets listed here.

enable_api: If true, an API gateway will be configured for the project. See HTTP APIs.

Testing

Deployment

hark deploy

Monitoring

Sharing

Debugging and troubleshooting

Hark on AWS

HTTP APIs

When instance.enable_api in hark.toml is true, Hark configures a single API gateway endpoint for all routes and methods.

It expects a function called on_http in the executable with the following function signature:

fn on_http(method, path, event) {
  // ...
}

method: string (e.g. “GET”, “POST”)
path: string (e.g. “/compute”)
event: dictionary (full AWS Lambda event, in version 1.0 format)

Source (HttpHandler)

File uploads

When instance.upload_triggers in hark.toml is configured, Hark enables file upload triggering.

It expects a function called on_upload in the executable with the following function signature:

fn on_upload(bucket, key) {
  // ...
}

bucket: string
key: string

Source (S3Handler)

The Hark Programming Language

Hark is a functional, compiled language which aims to support first-class concurrency and mainstream language inter-op. It compiles into byte-code which runs on The Hark VM .

Hark has:

Named variables.
Threads, and async & await primitives to manage them.
Python 3.8 interoperability ([Foreign Function Interface][1]).
JSON-compatible types (strings, numbers, lists, dictionaries).
First-class functions (proper closures coming soon).

The compiler is basic at the moment, but does feature tail-call optimisation for recursive functions. Compile-time correctness checks (e.g. bound names, types, etc) are planned.

Functions

Variables

Types

Comments

Threads

Python inter-op

NOTE: this syntax is unstable and very likely to change before Hark v1.0, in particular, to permit qualified imports.

Python functions (or callables) are imported into a Hark program with import, with the following signature:

import(name, module, num_args);

name: identifier, the name of the function to import
module: identifier, module to import from
num_args: int, number of arguments the function takes

For example:

import(foo, my_package.bar, 1);

Error handling

Keywords

The VM

This section is aimed at developers who want to improve Hark, or port it to a new (cloud) platform, or at anyone who’s interested in how Hark works.

The Hark VM is the main “interesting” and novel contribution in this project. Hark, the language, does not present anything new -- it’s simple an alternative skin on familiar concepts.

From Source to Success

We’ll begin by exploring the process of going from Hark source code to successfully running a multi-thread process in AWS.

Here’s our source:

// service.hk
import(foo, pysrc, 1);

fn bar(x) {
  x + 1
}

fn compute(x) {
  a = async foo(x);
  b = bar(x);
  await a + b;
}

fn main() {
  compute(1)
}

Features:

one imported Python function, foo
two Hark functions, bar and compute
each function takes 1 argument (assumed to be an int)
foo(x) is called asynchronously (new thread)
bar(x) is evaluated in the current thread
a is waited for
the sum foo(x) + bar(x) is returned

Here’s the Python source:

# pysrc/__init__.py

def foo(x):
    return x * 2

Running the program:

$ hark service.hk
4

Absolutely breathtaking.

Lots of things happened in the milliseconds it took to make that fantastic number four appear in our console. Before anything particularly interesting however, the Hark CLI tries to interpret our request.

The CLI

The CLI, in hark_lang/cli, does what you’d expect. Some neat libraries are used to make things pretty.

So what happens when we run hark service.hk? First, the command line is interpreted, then further configuration is read, and finally the command handler (in this case “run”) is dispatched.

graph LR;
 cmd{{"Command"}} --> load[Load configuration] --> run["Dispatch: Run"]
 click cmd "https://github.com/condense9/hark-lang/blob/master/src/hark_lang/cli/main.py"
 click load "https://github.com/condense9/hark-lang/blob/master/src/hark_lang/load.py"
 click run "https://github.com/condense9/hark-lang/blob/master/src/hark_lang/cli/main.py"

Command

Next: Configuration

Relevant functions & classes:

__docstring__ & dispatch -- hark_lang/cli/main.py
UserResolvableError -- hark_lang/exceptions.py

The command line hark FILE is the “default” command -- just run the Hark file locally.

Hark uses docopt. It’s simple and doesn’t impose many structural constraints -- you get a dictionary that describes the command-line options. It could be swapped out one day if really needed.

graph LR;
  doc{{cli/main.py docstring}} --> opt[docopt] --> args
  args{{args dict}} --> h[command handler]

To add a CLI command or option:

modify the cli/main.py module docstring
add a branch to dispatch if necessary
modify handlers as necessary

Note: the CLI also handles user-facing errors (exceptions of UserResolvableError) and attempts to print them nicely.

Some command line arguments are particularly interesting:

the -c flag, which sets the concurrency mode (Python threads by default)
the -s flag, which sets the storage mode (in-memory by default)
the -f flag, which sets the function to run (main by default)

In this case, there are no arguments, but it is possible to pass arguments on the command line.

Configuration

Prev: Command
Next: Handler

Relevant functions & classes:

load -- [hark_lang/config.py][config]
Config -- [hark_lang/config.py][config]
ProjectConfig -- [hark_lang/config_classes.py][config_classes]
InstanceConfig -- [hark_lang/config_classes.py][config_classes]

If a handler requires configuration (like run does -- the program timeout), it looks for hark.toml and loads it into a set of dataclasses.

Other configuration data is stored in the hark_data directory (usually .hark, but configurable).

graph LR;
  ic{{InstanceConfig}}
  pc{{ProjectConfig}}
  dir(".hark/...")
  f1("hark.toml [instance_config]") --> ic
  f2("hark.toml [project_config]") --> pc
  config{{Config}}
  pc --> config
  ic --> config
  dir --> config
  config --> h[handler]

Handler

Prev: Configuration
Next: Compilation

Relevant functions & classes:

run_local -- hark_lang/run/local.py
run_ddb_* -- hark_lang/run/dynamodb.py

In this case, the _run handler is called. To run Hark, a few things are needed:

graph LR;
 exe{{"Executable"}}
 dc{{"Data Controller (in-memory)"}}
 inv{{"Invoker (threading)"}}
 fn{{"Run arguments"}}
 run[Run and wait for finish]
 
 fn --> dc
 exe --> dc
 dc --> run
 inv --> run

Explanation:

Data Controller: this is the “memory” of the Hark VM
Invoker: determines how threads are run
Executable: the Hark program executable

In this case, we’re running the program locally, without using DynamoDB, so the run_local function is used to instantiate the controller and invoker. Note that the data controller holds all VM state, and so needs to know the entrypoing function. The invoker can then run the VM, given that state.

But first, we need to compile the Executable.

Compilation

graph LR;
 A{{ Source }} --> B[Lexer] --> C[Parser] --> D[Compiler] --> E{{ Executable }}
 click B "/vm/source-to-success-compilation.html#lex"
 click C "/vm/source-to-success-compilation.html#parse"
 click D "/vm/source-to-success-compilation.html#compile"

We’ll look at each step in more detail now.

Lex

Next: Parse

In this step, the Hark source code is transformed into a stream of “tokens” representing valid pieces of syntax (e.g. numbers, identifiers, keywords).

graph LR;
  A{{"Source code (.hk file)"}} --> B{{Token stream}}

Relevant functions & classes:

compile_file -- hark_lang/load.py
tl_parse -- hark_lang/hark_parser/parser.py
HarkLexer -- hark_lang/hark_parser/parser.py

To see what the token stream looks like, load the file with the DEBUG_LEX environment variable set:

$ DEBUG_LEX=1 hark service.hk

ID         : import
(          :
ID         : foo
,          :
ID         : pysrc
,          :
NUMBER     : 1
)          :
TERM       : ;
FN         : fn
ID         : bar
(          :
ID         : x
... etc

Note:

each token has a “type” (e.g. ID -- Identifier, or FN -- the “define function” keyword)
some tokens have a “value” (e.g. foo)
punctuation is syntax (e.g. ()
some literals have their own tokens (e.g. "true" -> TRUE)

The lexing is done by Sly.

Parse

Prev: Lex
Next: Compile

Here, the token stream is converted into a tree-like data-structure representing valid Hark program structure.

graph LR;
  A{{Token stream}} --> C --> B{{"Abstract syntax tree (AST)"}}
  C("(nested) expressions")

Relevant functions & classes:

tl_parse -- hark_lang/hark_parser/parser.py
HarkParser -- hark_lang/hark_parser/parser.py
Node -- hark_lang/hark_parser/nodes.py

What does valid program structure mean? Hark programs are sequences of “expressions”. Everything is an expression, and expressions may contain other expressions.

The AST is made up of Node instances, which represent expressions.

For example, the token TRUE is parsed as an expression (expr) into a Node subclass called N_Literal, which holds a literal value (Python True in this case).

@_("TRUE")
def expr(self, p):
    return N(self, p, n.N_Literal, True)

Note: N is a factory function to construct a Node with debug symbols taken from the parser.

Another example. The sequence of tokens representing an if-expression (yup, if is also an expr) are parsed into a Node to represent it.

@_("IF expr block_expr TERM rest_if")
def expr(self, p):
    return N(self, p, n.N_If, p.expr, p.block_expr, p.rest_if)

Here, block_expr and rest_if are parser items with rules expressed elsewhere.

This is how a function call, e.g. foo(x), is parsed:

@_("ID '(' arglist ')'")
def expr(self, p):
    identifier = N(self, p, n.N_Id, p.ID)
    return N(self, p, n.N_Call, identifier, p.arglist)

ID: foo
'(': a literal opening bracket
arglist: a parser rule to parse a list of arguments (defined elsewhere)
')': a literal closing bracket

Check the Sly docs for more details.

Error handling: The parser is currently fragile - any error causes immediate failure. A more conventional approach would be to attempt to continue and present all errors at the end.

Compile

Prev: Parse

The AST is now compiled into an Executable -- a multi-step process.

graph TB;
  A{{"AST containing Nodes"}}
  F{{Executable}}

   A --> B[Register imports] --> B2[Wrap Python functions] --> F

   A --> 1A
   1C --> F
  
  subgraph Compile Function
   1A[Optimise AST] --> 1B[Compile expressions] --> 1C[Change symbolic Gotos to Jumps]
  end

Relevant functions & classes:

Node -- hark_lang/hark_parser/nodes.py
CompileToplevel -- hark_lang/hark_compiler/compiler.py
optimise_block -- hark_lang/hark_compiler/compiler.py
replace_gotos -- hark_lang/hark_compiler/compiler.py
Executable -- hark_lang/machine/executable.py
Instruction -- hark_lang/machine/instructionset.py and hark_lang/machine/instruction.py
TlType -- hark_lang/machine/types.py

First, let’s briefly look at the (simplified) Executable class to know where we’re going.

@dataclass
class Executable:
    code: List[Instruction]
    bindings: Dict[str, TlType]
    locations: Dict[str, int]
    attributes: dict

code: All of the executable machine instructions.

bindings: A map of string names (identifiers) to either hark functions or imported Python functions.

locations: Lookup-table of Hark function locations in code.

attributes: (not used yet) Attributes of Hark functions for compiler/runtime behaviour configuration.

Here’s the result of compiling service.hk.

$ hark asm service.hk

BYTECODE:
 /
 | ;; #F:foo:
 |    0 | PUSHB    foo
 |    1 | CALL     1
 |    2 | RETURN
 | ;; #1:bar:
 |    3 | BIND     x
 |    4 | POP
 |    5 | PUSHV    1
 |    6 | PUSHB    x
 |    7 | PUSHB    +
 |    8 | CALL     2
 |    9 | RETURN
 | ;; #2:compute:
 |   10 | BIND     x
 |   11 | POP
 |   12 | PUSHB    x
 |   13 | PUSHB    foo
 |   14 | ACALL    1
 |   15 | BIND     a
 |   16 | POP
 |   17 | PUSHB    x
 |   18 | PUSHB    bar
 |   19 | CALL     1
 |   20 | BIND     b
 |   21 | POP
 |   22 | PUSHB    b
 |   23 | PUSHB    a
 |   24 | WAIT     0
 |   25 | PUSHB    +
 |   26 | CALL     2
 |   27 | RETURN
 | ;; #3:main:
 |   28 | PUSHV    1
 |   29 | PUSHB    compute
 |   30 | CALL     1
 |   31 | RETURN
 \

BINDINGS:

 NAME        VALUE
 foo ....... <TlForeignPtr pysrc.foo>
 bar ....... <TlFunctionPtr #1:bar>
 compute ... <TlFunctionPtr #2:compute>
 main ...... <TlFunctionPtr #3:main>

This shows how each Hark function has an associated block of bytecode, and the one imported Python function has been wrapped (using a #F: prefix to indicate that it is different from the other functions that are just #n:).

Register imports

Any import expressions at file top-level are saved as named bindings in the final executable. They’re also wrapped in Hark functions so that they can be called just like Hark functions (#F:foo above). Currently this wrapped version is only needed when calling a Python function asychronously -- usually, the Python function is called directly.

Compile Functions

Each top-level definition is compiled into a “body” of instructions and a named binding. The final executable code is created by simply concatenating all of the bodies together and saving the locations by name (e.g. bar -> #1:bar -> code[3] above).

Optimise AST

Currently tail-recursion optimisation is implemented, which makes recursive functions significantly faster because no activation record (stack frame) is created in the recursive call.

There’s lots of scope for develoment here! e.g. Issue #15

Compile Expressions

Each node (representing an expression) in the tree must be converted into a sequence of VM instructions (bytecode).

Examples of compiling expressions:

convert literal Python types to Hark types
convert N_If (the if-expression Node) into linear instructions and conditional Jumps

For example, a literal value is simply pushed onto the data stack:

@compile_expr.register
def _(self, n: nodes.N_Literal):
    val = mt.to_hark_type(n.value)
    return [mi.PushV.from_node(n, val)]

mi is the machine instruction module, and mt is machine types.

The from_node constructor copies node debug data into the instruction so that tracebacks can be created.

A function call is more interesting as the arguments have to be evaluated first.

def _compile_call(self, n: nodes.N_Call, is_async: bool) -> List[Instruction]:
    arg_code = flatten(self.compile_expr(arg) for arg in n.args)
    instr = mi.ACall if is_async else mi.Call
    return (
        arg_code
        + self.compile_expr(n.fn)
        + [instr.from_node(n, mt.TlInt(len(n.args)))]
    )

arg_code contains a list of instructions to evaluate each of the function arguments, which is simply prefixed to the function call instruction.

Note that n.fn, the function identifier, is also compiled -- the Call (or ACall) instruction requires the identifier to be on the stack.

Run

The (static) executable is run by the “TlMachine” class, using the previously loaded configuration to create the VM.

graph LR;
 exe{{"Executable"}}
 dc{{"Data Controller"}}
 inv{{"Invoker"}}
 fn{{"Run arguments"}}
 machine{{TlMachine}}
 
 fn --> machine
 exe --> dc
 dc --> machine
 inv --> machine --> top[Run from top]

Overview

Next: Start Top Level Thread

Relevant functions & classes:

TlMachine -- hark_lang/machine/machine.py
Executable -- hark_lang/machine/executable.py
Controller -- hark_lang/machine/controller.py
Invoker -- hark_lang/executor/thread.py
Instruction -- hark_lang/machine/instructionset.py and hark_lang/machine/instruction.py

Vaguely speaking, “running” a program follows this logic:

stateDiagram

Eval : Eval
Eval : Run instruction at current Instruction Pointer (IP)

Step : Inc
Step : Increment IP

 [*] --> Eval
 Eval --> Step
 Step --> Eval : Not stopped
 Step --> [*] : Stopped

To run the executable, the VM simply executes instructions until it cannot anymore. Reasons it may stop:

returning from the entrypoint function
waiting for another thread to finish

Machine instructions can do several things:

change the instruction pointer (control flow -- branches, jumps)
push/pop the data stack
halt the machine (e.g. to wait for a thread)
perform actions with external side effects (new thread, write to stdout)

Note: Next we will go through some bytecode. Each instruction is defined in instructionset.py and implemented in machine.py.

Start Top Level Thread

Prev: Overview
Next:

The Invoker instance calls TlMachine.run is to begin execution at main:

 | ;; #3:main:
 |   28 | PUSHV    1
 |   29 | PUSHB    compute
 |   30 | CALL     1
 |   31 | RETURN

Instructions:

PUSHV 1 -- push the literal value 1 (integer 1) onto the data stack.
PUSHB compute -- push the value bound to compute onto the stack (in this case, the compute function).
CALL 1 -- call a function with one argument. The top value on the stack is the function, and subsequent values are arguments.
RETURN -- (after compute returns) return from the function, ending the program in this case.

The CALL instruction creates a new Activation Record (like a stack frame) and sets the IP to the location of compute.

Compute

Prev: Top Level
Next: New Thread

Now we evaluate compute(1):

 | ;; #2:compute:
 |   10 | BIND     x
 |   11 | POP
 |   12 | PUSHB    x
 |   13 | PUSHB    foo
 |   14 | ACALL    1
 |   15 | BIND     a
 |   16 | POP
 |   17 | PUSHB    x
 |   18 | PUSHB    bar
 |   19 | CALL     1
 |   20 | BIND     b
 |   21 | POP
 |   22 | PUSHB    b
 |   23 | PUSHB    a
 |   24 | WAIT     0
 |   25 | PUSHB    +
 |   26 | CALL     2
 |   27 | RETURN

Interesting steps:

BIND x -- bind the value on the top of the stack (without popping it) to x.
ACALL 1 -- call a function asynchronously with one argument. Again, the top value on the stack is the function (foo), and subsequent values are arguments. This uses the Invoker to start a new thread with the given function and arguments.
BIND a -- bind the ACALL result to a (it will be a Future object).
WAIT 0 -- wait for the top object on the stack to resolve (assuming it is a Future).

graph LR;
 wait["WAIT for foo(x)"] --> check{Resolved?}
 check -->|No| stop[Save continuation and stop]
 check -->|Yes| cont[Get the value and continue]

The simple “Yes” case can be visualised:

gantt
 title foo(x) completes before Wait
 dateFormat  YYYY-MM-DD
 axisFormat  
 section main()
 Run to end :a1, 2020-01-01, 30d
 section foo(x)
 Run foo(x)      :f1, 2020-01-10, 5d

In this case, foo(x) finishes in the time it takes Thread 0 to run the 10 instructions between ACALL and WAIT.

Alternatively:

gantt
 title foo(x) takes longer
 dateFormat  YYYY-MM-DD
 axisFormat  
 section main()
 Run until Wait  :a1, 2020-01-01, 18d
 Resume          :after f1, 5d
 section foo(x)
 Run foo(x)      :f1, 2020-01-10, 15d

In this case, foo(x) takes longer and Thread 0 waits for it to continue. While waiting, the underlying Python thread is killed.

Each Future has a list of “continuations”, which are records of threads which can be picked up and resumed at a later time. When the Future does resolve, it can then use the Invoker to resume each thread.

New Thread

Prev: Compute
Next: Finish

ACALL creates a thread context for foo(x) - data stack, future and IP - and uses the Invoker to start the thread.

 | ;; #F:foo:
 |    0 | PUSHB    foo
 |    1 | CALL     1
 |    2 | RETURN

CALL 1 pops foo and one argument from the stack, and then calls foo directly (after converting the argument to a Python type). The result is converted to a Hark time and pushed onto the stack as the return value.

The Future associated with this thread is then resolved to that value, and any waiting threads are resumed.

Finish

Prev: New Thread

Once foo(x) has finished, and compute(1) is ready to RETURN, it retrieves the caller IP from its activation record, and simply jumps there. The activation record is deleted.

Finally, we return from main() -- all threads have “finished”, and the result is returned to the CLI to be printed.

The end. Here’s a spaceship.

                     `. ___
                    __,' __`.                _..----....____
        __...--.'``;.   ,.   ;``--..__     .'    ,-._    _.-'
  _..-''-------'   `'   `'   `'     O ``-''._   (,;') _,'
,'________________                          \`-._`-','
 `._              ```````````------...___   '-.._'-:
    ```--.._      ,.                     ````--...__\-.
            `.--. `-`                       ____    |  |`
              `. `.                       ,'`````.  ;  ;`
                `._`.        __________   `.      \'__/`
                   `-:._____/______/___/____`.     \  `
                               |       `._    `.    \
                               `._________`-.   `.   `.___
                                             SSt  `------'`

Machine Design

Recommended: Read From Source to Success first!

Introduction

Hark (the language) compiles into bytecode that runs on a virtual machine designed for concurrency and portability.

Concurrency: When you do y = async f(x), f(x) is started in a new thread (Lambda instance, on AWS). And then when you do await y, the current thread halts, and automatically continues when y is finished being computed.

Portability: Two implementations of this VM exist so far—local and AWS Lambda, but there’s no reason Hark couldn’t run on top of (for example) Kubernetes (See Issue #8).

Abstractions

At its core, the VM has two abstractions:

Storage: what does it mean to store/retrieve a value? For example, this is done with DynamoDB in AWS.
Invocation: what does it mean to “invoke” a function? In AWS, this is currently done with Lambda.

These are both run-time abstractions, but which could be guided by compile-time source-code annotations. For example, if some functions have very high memory requirements, the VM can happily invoke them on an appropriate instance, while invoking other functions in a smaller instance.

Implement both of these, and you can run Hark.

Here’s the current implementation landscape.

Storage	Invocation	Platform	Notes
In-memory	threading	Local	Python threads are not actually concurrent!
DynamoDB	threading	Local	Only useful for testing the DynamoDB storage.
DynamoDB	multiprocessing	Local	Concurrent. Use DynamoDB Local.
DynamoDB	Lambda	AWS	Concurrent. Limitations on DynamoDB item size!

Requirements and concepts

The Hark VM is designed to meet these requirements.

1. More than one thread

It must be possible to do more than one thing at a time. It must support concurrency.

Corrolaries:

There must be a way to pass data between threads.
There must be a way to synchronise threads.

2. “Pause-able”

It must be possible to “pause” threads, and “continue” them when the data they need is ready. While paused, it must be possible to easily and efficiently save the state of a thread, and restore it upon continuation.

3. Symbolic data

It must be possible to define named values, and operate on them (functions and variables).

4. Inter-op with other languages (FFI)

It must be possible to call Python functions (and possibly later - other languages).

5. Portable

It must be a relatively simple job to port the VM to a new (cloud) platform. Programs written in Hark should run the same on any implementation (ignoring the effect of any Python calls).

What are the core components?

These are the core components that make up the design. Understand these, and how they interact, and you’ll understand Hark.

Threads

A Hark program starts off as a single thread, and can create other threads to execute in parallel. Each thread begins executing from a specific function (called its entrypoint).

Each thread executes instructions in series until it cannot return anymore (ie it returns from its entrypoint). All threads share the same executable -- the currently-implemented synchronisation method depend on it!

Each thread has:

(one) private data stack
(one) private instruction pointer
(one) shared Future
(many) shared Activation Records

Executable

The executable is a static (does not change at run-time) data structure containing:

a set of function names
a list of VM instructions and operands for each function
debug data

Note: At the moment, the executable does not contain a “data” section, or any globally named (non-function) values.

Data Stack and Instruction Pointer

Within the context of a single thread, the Hark VM is a simple stack-based machine (similar, in a distant way, to Java’s JVM).

The instruction pointer is an index into the executable code, determining the next instruction to be executed (it is pre-incremented).

The data stack supports basic push/pop semantics and can store any Hark data-type, although this might change before Hark v1.0 to support proper heap storage of data.

Instructions

The VM operates like a traditional CPU -- by iterating over a list of “instructions”, and executing each one in the context of the current data stack. Each instruction may pop or push data onto or from the stack.

Some special instructions exist in order to, for example:

call foreign functions
enable program control flow (ie, jumps)
control the VM (pause a thread, write to standard output, etc)

Instructions can take (fixed) operands.

Activation Record

Activation records store the context of a function call (arguments, caller activation record, return instruction address, etc). A bit like stack frames. Stack frames are just activation records that maintain strict LIFO semantics, hence the “stack” name.

The C2 Wiki explains it well.

Hark activation records do not have to maintain strict LIFO semantics, and so they are not called stack frames. This makes it easier to support:

closures
cross-thread stack-traces.

Futures

Each thread is associated with a single Future object. Futures can be resolved or not. If they are resolved, they have an associated value. If they are not resolved, they have a (possibly empty) list of continuations, each of which represent the state of a paused thread.

When a thread returns from its entrypoint function, the associated Future is resolved to the function’s return value (top item on the data stack).

Calling convention

The “calling convention” dictates how parameters are passed to functions and results are returned. Normally (e.g. on Intel x86 processors), this would involve registers. There are no data registers in the Hark VM, so the calling convention here is very simple:

push parameters onto the stack (reverse order)
call function
top item on the stack is the function’s return value

Key Abstraction 1: Storage

This is the “long-term” storage that any processor needs. The Hark VM abstracts this so that storage backends are portable.

Key Abstraction 2: Invocation

The Hark VM abstracts the creation of threads so that execution backends are portable.

Thread States

Futures

Activation Records

Overview

Styling hints:

Nouns in Italics (and capitalised).
Adjectives/verbs in bold.
Code in `monospace**.

Terms

Session: 1 or more Threads.

Top Level Thread: the thread that initiated the Session.

A TlMachine instance runs a single thread.

The Entrypoint is the function that kicks-off a Session. This might be main(), or it might be some other specific handler.

Standard Output

Standard output in Hark is a bit different from the usual.

Instead of modelling the output as a stream, each Session has a list of items collectively called Standard Output. The items are tuples containing:

a timestamp
the originating thread
a string

e.g.

[
#  timestamp, thread, message
  (123523432, 0, "thread 0 says hi\n"),
  (123523438, 1, "thread 1 says hi\n"),
]

You write to standard output using the print() builtin function.

Probes

Each Thread gets assigned a Probe, which records interesting events during execution, and is useful for tracing/debugging.

Stopping

A Thread is stopped if:

it has run out of Instructions to execute (i.e. run out of call stack)
an error occurs

It is called finished in the first case, and broken in the second.

A Session is stopped if all Threads in it are stopped.

Similarly, a Session can be finished or broken.

Futures

Each Thread gets assigned a Future and an Error.

If the Thread finishes, then it resolves the Future with its result.

If it breaks, then the Future will never resolve, and Error will contain information about the error, and a stack trace.

Either way, the Thread is stopped.

Stack Traces

A Stack Trace is created when one or more fatal errors occur in a Session.

Stack Traces are directed acyclic graphs with a single “entry” node, and an “exit” node for every error in the session. “Stack Trace” is a misnomer, since they’re not really stacks, but it’s kept because people are familiar with the concept.

The nodes in the graph are called Activation Records. Activation Records are like “Stack Frames”, but more general - stack frames are usually items in a strictly last-in-first-out data structure (the stack), activation records just represent a function call context. See Activation Records.

An Activation Record is created when a Function is called. They contain:

The function parameters
The call-site (pointer to return address in the exe code)
A “pointer” to parent AR

If more than one Thread breaks in the same Session, their Stack Traces will share at least one common node (the Entrypoint). But they might share more than one! Graphically, the Stack Traces could be represented together, where the shared nodes are drawn only once.

For example:

    C-D-!
   /
A-B-E-F-G-!

In this case, the letters represent activation records (function calls). There are two threads, and errors ocurring in AR D and G. Logically, the functions do share stack traces, and it makes sense to display this.

Results & Return Values

TODO

Storage

Invocation

Adding new instructions

Developing Hark

Read on if you’re keen to find out how Hark works and how to develop it.

Local development environment

Cloud-Native Development With Hark