Skip HHVM Interop Internals

August 15, 2018

Overview

The first step with interop is getting Skip and HHVM to talk to each other. Interop between HHVM and Skip is done through the HHVM extensions mechanism. We register an extension which adds a Skip::init() function to Hack. When Hack calls Skip::init() we load or reload the skip shared object (DLL), ask it what functions it provides and register them with the current HHVM request as native functions.

Skip normally generates executables. How do we generate this DLL for HHVM to load?

Normally our compiler generates llvm assembly, we compile that with clang and then link that against our runtime and a stub called sk_standalone.cpp which contains some simple initialization code.

This is problematic for HHVM use for several reasons:

HHVM owns main
We want to be able to reload the skip code and if our runtime is linked against it then we won't be able to share data (such as memoization data).
We want our runtime to use the same libraries as HHVM (such as folly). If we link our runtime against our compiled code then we would either have to discover and export the entire folly ABI from HHVM or have two separate copies of folly loaded in one process.
The runtime does a lot of low-level hooks to handle memory and singleton initialization. Those are really hard to make sure they unload cleanly in a DLL.

To handle these issues we statically link the Skip runtime directly against HHVM. This way all loaded Skip binaries share a single runtime and we only have to expose a small ABI for Skip binaries to use. To compute the ABI to expose, we link a small stub DLL and look at the symbols that were exported. The skip code is then linked against a small stub called sk_hhvm.cpp which provides initialization and routing helper code (instead of linking against sk_standalone.cpp).

The next issue we have is when the runtime wants to call into SKIPC functions. SKIPC functions are helper functions generated by skip_to_llvm and intended to be called by the Skip runtime (such as functions for creating specialized types of objects like Array<Int>) as opposed to Skip code written by the user and exported so it can be called from Hack.

Although you can only load a single Skip DLL for a given request, in sandbox mode you could have several DLLs loaded each being used by different ongoing requests (imagine starting a long-running request, changing some Skip code and running a new request - you'll have the old Skip code loaded in the old request until it finishes and the new Skip code loaded in the new request until it finishes). The runtime needs to know to which binary to route its calls.

To handle routing calls each SKIPC function has a stub compiled into the extension which looks up the current binary in a thread-local variable and forwards the call through a big interface which calls the underlying SKIPC function. Both the stubs and the interface are generated during buck builds.

Skip Runtime API

Functions which are defined in the Skip runtime and expected to be called from the Skip generated code are prefixed with 'SKIP_' or are in the 'skip::' namespace.

SKIPC functions are so named because they're prefixed with 'SKIPC_'. (Note that for historical reasons there are a number of functions which should be prefixed with 'SKIPC_' but are prefixed with 'SKIP_'. These are listed in the variable HACK_REMOVE_LIST).

Calling Hack from Skip

In Skip you can import a Hack function by declaring a prototype and annotating it with @hhvm_import:

@hhvm_import
untracked native fun my_php_function(x: Int, y: Int): String;

This prototype allows you to call the named Hack function as if it were a Skip function.

How it works under the covers

Calling a Hack function is relatively easy - The user Skip code calls into the extension and passes it the function name, parameters, and a description of what types those parameters are. The extension converts those parameter values from Skip representations to HHVM representations and asks HHVM to call the function. When the Hack function returns we convert the HHVM return value to a Skip value and return it.

Calling Skip from Hack

You can export a Skip function so it can be called from Hack by annotating it with @hhvm_export:

@hhvm_export
fun add_two(a: Int, b: Int): Int {
  a + b
}

Calling Skip from Hack is a little harder because we have to generate a stub for each Skip function we want to call from Hack. So for every @hhvm_export function the Skip compiler generates a wrapper function which expects the HHVM types, converts those types to Skip, calls the original Skip function, converts the return value back to HHVM and returns it.

During compilation skip_to_llvm collects a list of all the @hhvm_export functions and signatures and the extension fetches that data when the Skip DLL is loaded. This allows the extension to tell HHVM what native functions are available.

Portable Types

This document refers to “portable types” as the types which can be passed between Skip and HHVM (whether by copying or proxying). The following table enumerates these portable types.

Skip Type	HHVM Type	Mode	Notes
Bool	bool	copy
Int	int	copy
Float	float	copy
String	string	copy
@hhvm_import("T")	T	proxy
@hhvm_shape("T")	shape	proxy
@hhvm_copy("T")	T	copy
@hhvm_shape_copy("T")	shape	copy
Vector.HH_varray2	varray	proxy	Tv must be a portable type.
Map.HH_darray2<Tk, Tv>	darray	proxy	Tk must be Int, String or a subtype of HH.Arraykey. Tv must be a portable type.
Set.HH_keyset2	keyset	proxy	Tk must be Int, String or a subtype of HH.Arraykey.
HH.Mixed	mixed	copy	Excludes HH.Object and HH.Resource.
Array	varray	copy	Tv must be a portable type.
Vector	varray	copy	Tv must be a portable type.
Map<Tk, Tv>	darray	copy	Tk must be Int, String or a subtype of HH.Arraykey. Tv must be a portable type.
UnorderedMap<Tk, Tv>	darray	copy	Tk must be Int, String or a subtype of HH.Arraykey. Tv must be a portable type.
Set	keyset	copy	Tk must be Int, String or a subtype of HH.Arraykey.
UnorderedSet	keyset	copy	Tk must be Int, String or a subtype of HH.Arraykey.
Tuple<T0...>	array	copy	The types of each tuple element must be portable types.
?T	?T	copy	T must be a portable type.
??T	?T	copy	Special case for optional fields in shapes - see below

An example of a non-portable type would be a normal Skip class without any @hhvm annotation.

??T - Optional fields in shapes

In Hack a shape can be defined to have an optional field:

type Point = shape('x' => int, 'y' => int, ?'z' => ?int);

In this case the Skip class could be defined as either:

@hhvm_shape_copy
class Point {
  x: Int,
  y: Int,
  z: ?Int
}

or:

@hhvm_shape_copy
class Point {
  x: Int,
  y: Int,
  z: ??Int
}

Values are copied as follows:

Hack Value	Skip Value for ?T	Skip Value for ??T
undefined	None()	None()
null	None()	Some(None())
value	Some(value)	Some(Some(value))

Type Table

When the Skip DLL is loaded the extension discovers the set of HHVM classes and the fields and types expected on each by calling the SKIPC function SKIPC_hhvmTypeTable(). The format for this table is defined as the class TypeTable in github:src/runtime/prelude/native/Svmi.sk.

During discovery the extension iterates through all the classes and ensures that their definition in Skip matches the definitions from Hack. It also iterates through all the fields and caches the HHVM slot offset for each field.

Talking About Objects

Objects are converted from HHVM to Skip or from Skip to HHVM in a few places. When Skip code calls a @hhvm_import function the parameters need to be converted from Skip to HHVM and the return value needs to be converted from HHVM to Skip. When Hack code calls a Skip @hhvm_export function the parameters need to be converted from HHVM to Skip and the return value needs to be converted from Skip to HHVM. Reading fields from an @hhvm_import object needs to convert the result from HHVM to Skip and writing fields to an @hhvm_import object needs to convert the value from Skip to HHVM.

Copying OBJECTS

To mark classes as copying you annotate them with either @hhvm_copy or @hhvm_shape_copy.

Copying objects from HHVM to Skip is done via a "gather" operation. When skip_to_llvm realizes it needs to copy an object from HHVM to Skip it generates code to call SKIP_HhvmInterop_Gather_gatherCollect(), passing it the object and type table classId it wants to collect. The extension will recursively visit each field in the class as specified in the type table, check that it's the correct type and then serialize it to a buffer in the form that Skip expects. Finally it returns a pointer to a filled buffer and a cleanup handle. When the code is finished building the Skip objects it calls SKIP_HhvmInterop_Gather_gatherCleanup() to free the buffer.

Copying objects from Skip to HHVM is done via a “push” operation. When skip_to_llvm realizes it needs to copy an object from Skip to HHVM it generates code to call SKIP_HhvmInterop_DataTypeCons_create() (where DataType is either “Object” or “Shape”) telling it the type table classId it wants to construct. The generated code then calls SKIP_HhvmInterop_DataTypeCons_setFieldType() once for each field (where Type is the field type such as 'Int' or 'Mixed'). Finally the generated code calls SKIP_HhvmInterop_DataTypeCons_finish() to note that construction is done.

Proxying OBJECTS

When proxying objects skip_to_llvm replaces the Skip fields with a single “proxyPointer” field.

Field gets are turned into calls to HhvmInterop.propertyGetHelper() which in turn is lowered into calls to SKIP_HHVM_DataTypegetFieldType() (where DataType is either “Object” or “Shape” and Type represents a specialized type like 'Int' or a generic type like 'Mixed').

Field sets are turned into calls to HhvmInterop.propertySetHelper() which in turn is lowered into calls to SKIP_HHVM_DataTypesetFieldType().

FAQ

Q. How does the extension know what DLL to load?

A. The path to the shared object is given to HHVM as a config variable called Skip.Binary.

Q. How does the extension know when it's safe to unload a DLL?

A. It uses the HHVM treadmill to defer unloading until after the last HHVM request which could still be using the DLL has completed.

Q. What if I want to have my exported or imported function named differently in Hack and Skip?

A. Both @hhvm_import and @hhvm_export annotations accept a parameter which is the Hack name to use. For example

@hhvm_import(“my_hack_function”)
native fun my_skip_function(x: Int): Int;

will call the Hack function my_hack_function when a Skip program calls my_skip_function().

Q. How does Hack/Skip interop handle copy-on-write HHVM arrays?

A. It doesn't. For now, HHVM arrays are read-only.

Q: Does the gather operation really serialize everything? For example - do string contents get serialized into the temporary buffer?

A: It stores all the copied values with some special cases. So for primitive types (Int, Float, Bool) it stores the value. For Strings it copies the string into Skip's memory and format and stores the pointer to the string (technically the StringRep). For proxied objects it stores the HhvmHandle pointer. For copied objects it recursively stores all the fields. The details of the format can be found at the top of src/native/hhvm/gather.sk.

as expression and @ patterns

August 6, 2018

Aditya Durvasula

as does runtime casting from a base class to any of its children by attempting to match an object (lhs) with a pattern (rhs). If it succeeds, as returns the object casted to the type of the pattern. Otherwise, it throws an exception. as is really similar to the is expression which returns true or false instead of performing a cast.

Here's a quick overview:

base class Animal
class Dog(int: Int) extends Animal
class Cat(string: String) extends Animal

fun main(): void {
  x: Animal = Dog(0);
  ex1 = x as Dog(0); // type of ex1 is Dog!
  ex1Bool = x is Dog(0); // true
  ex2 = x as Dog(1); // will throw an exception, but ex2 : Dog
  ex2Bool = x is Dog(1); // false
  ex3 = x as Cat("foo"); // will throw an exception, but ex3 : Cat
  ex3Bool = x is Cat("foo") // false
}

How do as expressions work?

The expression

x as <pattern>

is desugared to

x match {
| tmp @ <pattern> ->
  // 'tmp @' is an "at pattern" that introduces the local 'tmp' in that branch,
  // bound to the value matched at that position in the pattern
  tmp
| _ -> throw InvalidCast()
}

Why have as expressions?

Consider the following Abstract Datatype.

`base class Animal
class Dog() extends Animal
class Cat() extends Animal
...
class Zebra() extends Animal

Before the as expression, we would define helper methods to cast to each child class of the ADT.

fun asDog(data: Animal): Dog {
  data match {
  | tmp @ A _ -> tmp
  | _ -> throw InvalidCast()
  }
}

fun asCat(data: Animal): Cat {
  data match {
  | tmp @ B _ -> tmp
  | _ -> throw InvalidCast()
  }
}

Now, with as, we don't need any of these functions because as effectively desugars to these functions.

fun bar(): void {
  x: Foo = A();
  a = x as A _; // no need to define asA and do (a = asA(x))
}

Why use patterns instead of types?

Patterns let us leverage existing machinery already in place match to perform “cast”-like behavior. Additionally, this let's us perform more restrictive casts than a basic typecast. Deep introspection would not be possible with a simple instanceof like typecast. For example:

base class B
class C1(int: Int) extends B
class C2(string: String) extends B

fun foo(): void {
  x: ?B = Some(C1(4));
  y: ?C1 = x as Some(C1 _) // no way to express nested patterns with a typecast
}

as patterns become @ patterns

While the two pieces of syntax exist in different namespaces, to avoid potential conflicts with the as pattern and have less confusing future syntax for irrefutable patterns/bindings, Todd Nowacki suggested removing the as pattern and using @ instead. Now, code like

x match {
| Some _ as y -> y
...
}

instead looks like

x match {
| y @ Some _ -> y
...
}

Macros

July 24, 2018

Peter Hallam

Skip now has a limited form of macros. They are particularly handy for default implementations of common traits.

For example:

trait .Hashable {
  overridable macro fun hash(): Int {
    h = #thisClassName.hash();
    #forEachField (#field) !h = combine(h, this.#field);
    h
  }
}

class Person{name: String, age: Int} uses Hashable {
  // NOTE: No hash() implementation required.
}

In the above example the implementation of Person.hash() is:

  fun hash(): Int {
    h = "Person".hash();
    {
      !h = combine(h, this.name);
      !h = combine(h, this.age);
    };
    h
  }

Also note that the "Person".hash() expression is constant folded at compile time and initializes h to an integer literal.

macro Methods

All macros start with # to visually distinguish them from normal, non-macro code.
Macros may only be used within methods with the macro modifier.
macro methods may be defined on traits as well as on classes.
macro methods are expanded in leaf classes.
macro methods are expanded after parsing and before type checking.
The restrictions on the use of macros ensure that macros are expanded into valid parse trees.
You will see type errors in the expanded bodies of macro methods. These errors use the same reporting techniques we use for deferred methods, so the error reporting should be easy to follow.

Macros

The macros currently implemented are:

#thisClassName

Expands to a string literal containing the fully qualified name of the leaf class the method is being expanded into. It may be used as an expression.

#ThisClass

Expands to the class type of the class being expanded into. It may be used as a type annotation as well as in pattern matching.

#forEachField(#fieldIdentifier [, #fieldNameLiteral]) body

#forEachField expands to an expression sequence where the body expression is expanded once for each field in the containing class. The expansion includes all fields in the class including those inherited from base classes.

Within body the #fieldIdentifier macro expands to an identifier equal to the name of the field being expanded. It may be used as an expression, or more commonly on the right hand side of the . member access operator.

If present, the #fieldNameLiteral macro is also available in the body expression and expands to a string literal containing the name of the field being expanded.

Current Uses of Macros

Macros currently provide default implementations for the following traits:

Hashable
Equality
Orderable

You should rarely need to provide manual implementations of these traits.

Equality Example

The Equality implementation shows the use of the #ThisClass macro used in a pattern match:

trait Equality {
  overridable macro readonly fun ==(other: inst): Bool {
    other match {
    | #ThisClass _ as otherTyped ->
      // silence unused variable warning in classes
      // with no fields.
      _ = otherTyped;

      #forEachField (#field) {
        if (this.#field != otherTyped.#field) {
          return false;
        }
      };
      true

    | _ -> false
    }
  }
}

JSON Example

Here's an example using the field literal version of #forEachField to implement JSON serialization:

trait Jsonable {
  overridable macro fun toJson(): JSON.Value {
    fields = mutable Map<String, JSON.Value>[];
    #forEachField (#field, #fieldName) {
      this.#field.toJson() match {
      | JSON.Null() -> void
      | value -> fields.set(#fieldName, value)
      }
    };

    JSON.Object(freeze(fields))
  }
}

Integral Types

July 20, 2018

Aditya Durvasula

Skip now supports UInt8, UInt16, UInt32, Int8, Int16, Int32 along with the original Int (64 bit) type.

The new integer types can be used to efficiently store a value in a specific range, while all operations always work by first converting to 64 bit Ints. Conversion back to a smaller integer type is explicit and the user can choose to truncate the value or fail if it is outside the representable range.

// Int literals are 64 bit
x = 20;    
y = 100;
// All operations return Int
z: Int = x + y;

// Other integer types are created with a method call:
x8 = UInt8::create(20);
y32 = Int32::create(100);
// Operations convert to Int first and return an Int:
z: Int = x8 + y32;

z8: UInt8 = UInt8::truncate(z); // ignore overflow
z8: UInt8 = UInt8::create(z);   // fail if overflow

How does it work?

The original Int class is the workhorse that provides the implementations for all the useful math and comparison methods by compiling down to LLVM or JS. Each operation is specialized on the types of the arguments so that operations between two Ints incurs no additional overhead. Operations between other integer types will inline the conversion and operation together.

What next?

Now that we have the UInt8 type we plan to add more features for working with binary data. Aaron Orenstein is already adding support for converting between String encodings and converting a String from utf8 bytes. We're also planning to add support for binary IO as well as serialization of Skip objects to/from binary formats such as Thrift.

Async/Await

July 18, 2018

Mat Hostetter

Skip now has async/await, which should look familiar to Hack and Javascript programmers:

async fun myFun(name1: String, name2: String): ^Int {
  value1 = await lookup(name1);
  value2 = await lookup(name2);
  value1 + value2
}

Implementation details

Skip implements await in much the same way as generators, using heap-allocated coroutines. If you’re not familiar with coroutines, it’s an interesting exercise to work out how the compiler might transform your function containing await or yield into one that can return early (like when an await isn’t ready) and later resume where it left off.

Coroutines were challenging to add to the compiler, but that was only one piece of the puzzle. In addition to async/await, Skip also supports parallel execution, memoization and reactivity. Supporting two of those features at the same time isn't so bad, but when you mix all four together the implementation starts to get tricky.

Processes

In order to make Skip's various forms of parallelism and concurrency mesh together, I extended Skip's C++ runtime with a concept that I grudgingly called Process. A Process consists of a private GC heap, an event queue and some reactive graph construction state.

At any given time a Process may or may not be “animated” by a thread; in particular, a Process which is stalled waiting for I/O will not consume a thread until it's ready to run again. This is analogous to OS processes that may or may not be running on a CPU core at any given moment.

A Skip program consists of multiple communicating Processes, but they are hidden from users. That said, you could imagine tasteful ways to expose them in the future or even distribute them across machines (Erlang, anyone?)

Async + memoized, together at last

Before Skip had async/await, if two Processes tried to compute the same memoized value at the same time, the second Process would block and wait for the first to finish. Avoiding redundant computation is good, but we never want threads to block, and we’ve seen this be a problem in practice. Observe the parallelism dips in Skip's type checker (written in Skip) where many parallelMap Processes all try to compute the same commonly-used memoized values, such as the Int type:

Skip compiler parallelism over time

Finally we can fix this! A function can now be both async and memoized:

async memoized fun getSomething(name: String): ^Int

In the "contention" case described above, the second Process will immediately get back an Awaitable that will be ready when the first Process finishes. Because await is inherently non-blocking, this lets it do useful parallel work rather than getting stuck.

A memoized async function may of course do an await that needs to suspend, perhaps waiting for a network result. To implement this, I gave each memoized function invocation its own Process, which can be suspended during await and put on a shelf until it's ready to run again. Creating a Process is cheap, but not free, and it's possible we'll need to optimize this later.

When a suspended Process is ready to run again, it can resume running in any background thread. This means async computation can automatically proceed in parallel with other work being done in the main thread.

Optimizations

HHVM's experience has been that the size of Awaitables is important, so I implemented a few compiler optimizations:

When an await suspends, we only save exactly those local variables ("SSA nodes" to you compiler hackers) which are "live" at that point in the function. Variables which are never live across an await do not consume any space in the Awaitable.

The compiler uses graph coloring to minimize how much storage it needs for suspended variables. If two local variables never need to be "suspended" by the same "await", they can share the same storage in the Awaitable's suspend state. This is not dissimilar to register allocation, a classic use of graph coloring. The end result is that the size of each Awaitable is determined by the maximum storage needed by any single "await".

Future Work

Language changes

To preserve determinism, an async function can only take frozen (deeply immutable) parameters or Awaitables (which, although their physical representation changes over time, are “logically frozen”). This rule is necessary because if two async functions were able to take the same mutable object as an argument, the program could perceive the order in which those async functions finished, which could vary randomly from run to run. Additionally, we wouldn’t be able to run async computation in background threads.

Determinism has many advantages, such as easier debugging and making the reactive cache’s "false positive" detection more efficient. But unfortunately the async parameter rule turns out to be too restrictive, preventing us from writing useful features like async iterators. Julien Verlaguet, Basil Hosmer and Todd Nowacki are looking into adding a dash of Rust-style unique references to the language to solve this problem.

HHVM integration

A Skip program can already be statically compiled and loaded into HHVM as a shared library, where Skip code can interoperate with Hack code. That said, the interop is incomplete. We have not yet tied together Skip and HHVM’s async/await implementations, so a Skip program cannot await an HHVM object or vice versa. To fix this, we need to integrate Skip Awaitables with HHVM’s event loop by implementing one of their interfaces. Fortunately Jan Oravec has given us some handy tips on how to proceed.

Loops as Expressions

May 15, 2018

Todd Nowacki

Recently, loops were added to Skip!

In the past, we avoided adding loops under the assumption that higher-order functions could be used to write any code you would want in a nice, declarative manner. And if you really needed a loop, you could use a standard library function that provided mostly what you needed. Overtime, we found that it is very difficult to write certain performance critical algorithms without break, return, or yield from inside the loop.

Making Loops Feel at Home with Expressions

If we had taken loops and implemented them exactly how you would expect in a statement-based language, they would not feel very cohesive with the rest of the language. To address this, Mat and I looked for someway that let's you use the loop directly, as you might with some of our other statement-like expressions such as if-else or try-catch.

The solution we arrived at was as follows:

Break and Else

Loops in Skip are different than you might be used to in two key ways:

Break takes an expression Instead of just break; we write break e; And if the break is hit, the value e is the resulting value of the entire loop.
Every Loop Has an Else If the loop condition is not met, the else branch is taken as the resulting value of the loop. In other words, if a break (or some other divergent expression) the loop will either loop forever, or the else branch is the value. Like if expressions, if there is no explicitly written else, it has an implicit else void.

For clarity, two small examples:

while (true) break 100 else 0; // == 100
while (false) void else 42; // == 42

What's the motivation behind this design? Why not make loops more expression friendly in a different way?

Most iteration can be written with higher-order functions such as map, filter, and fold. The biggest weakness in the language without native loops was that there was no easy way to break early from "looping". Commonly, especially in the standard library, this was when some value had been found and looping wanted we wanted. For example

v : Vector<X>;
p : X -> Bool;
size = v.size();
i = 0;
result = None();
while_loop(
  () -> i < size && result matches None(),
  () -> {
    x = v[i];
    if (p(x)) !result = Some(x);
    !i = i + 1;
  },
);
result

can now be rewritten with native loops as:

v : Vector<X>;
p : X -> Bool;
result = None();
foreach (x in v) {
  if (p(x)) {
    !result = Some(x);
    break void;
  }
};
result

and then with a value-based break and else as:

v : Vector<X>;
p : X -> Bool;
foreach (x in v) {
  if (p(x)) break Some(x)
} else
  None()

while it might not be a huge difference in lines of code, with the expression-based loop you maintain this puzzle-piece-like feeling with your code. That is, this last version of the foreach loop can be moved around without having to preserve the context for these local side effects (the assignment).

To summarize

A lot of patterns will continue to use standard library higher-order functions
If you want to write code using a more iterative, statement-like style, you still can (you might just have to write break void; instead of break;
The pattern that higher-order functions are bad at is supported by this style of expression-based loops

Why the `else` keyword?

else might seems like an odd choice of keywords for this behavior. Here is a quick overview of why I went with this keyword over some other, new keyword

Python has a similar behavior to this, but with no expression/value in break. Having a successful programming language as an existing data point is super helpful.
else is already a keyword in a similar pattern with if. In particular, it shares similar behavior with if-else with having an implicit else void when the else branch is missing in the user's code.
else fits logically with while and do while, and if you stretch it a bit for foreach, with "else is taken when the loop condition is false". Then break bypasses both the loop and the else branch.

That being said, this keyword isn't set in stone. We are in a bit of uncharted territory with this style of loops (at least among popular programming languages). With that in mind, we will try out the keyword, and if it doesn't feel like it is working, we will change it.

The Three Loops

We added the three loops you might expect:

while
do while
foreach

Each of these loops behaves as you might expect

The condition of while and do while is of type Bool
The body of each loop is of type void
break and continue can only be used inside the loop body. Much like throw and return, break and continue have any type.
foreach is desugared into a do-while. Examples in the sections below
As described above, break takes an expression which if taken is the value of the loop. else is taken when the loop finishes without breaking.

foreach Syntax

The syntax for the foreach is as follows:

foreach (<foreach_value> in <expression>) <expression> else <expression>

we currently support three "patterns" for the value bindings of the foreach.

Identifier: Just a simple variable binding, e.g. x
Tuple of Identifiers: A "tuple" of variable bindings, e.g. (x, y, z). Currently these tuples cannot be nested.
Key-value: A key value binding is two variable bindings separated by a fat arrow, e.g. k => v

In the future, we will support a more-general, irrefutable-pattern structure for these bindings, which will help bring them inline with any other lvalue.

foreach Semantics

foreach uses the standard library's Iterator framework.

Identifier or Tuple of Identifiers loops call values() on the collection
Key-value loops call items() on the collection. It assumes that each element in iteration is a pair of the key and the value
next() is called, looping while Some and stopping when None()
The value of next is then matched against inside a do while

Here are two examples of

foreach ((x, y, z) in collection) <body> else <else_expr>

becomes

flag = true;
values = collection.values();
do
  values.next() match {
  | None() ->
    !flag = false;
    // A continue is added to prevent type errors with the other branch
    continue
  | Some((x, y, z)) ->
    <body>
  }
while (flag) else <else_expr>

and

foreach (k => v in collection) <body>

becomes

flag = true;
items = collection.items();
do
  items.next() match {
  | None() ->
    !flag = false;
    continue
  | Some((x, y, z)) ->
    <body>
  }
while (flag) else <else_expr>

Summary

Skip now has loops! They are while, do while, and foreach
To make them feel more like expressions, break takes an expression and is the resulting value of the loop. If no break is reached, it takes the else branch.
Our approach to loops as expressions fits nicely into the weak spot of higher-order functions, while not interfering with traditional "statement" usages of loops.
foreach desugars into a do while, calling either values() or items() on the given collection. next() is called until a None() is reached.

And thanks to Mat for coming up with the break/else design and helping work out the kinks of the final implementation!

Generator Support

May 3, 2018

Mat Hostetter

TL;DR: Skip now has generators!

If you've ever used the yield keyword in Python, Hack, Javascript, C#, etc., you know how handy generators can be. And now Skip has them!

While implementing async/await, I noticed that the coroutine support I was adding to the compiler would make generators easy to implement. So I took a brief detour and added them to the language too.

A few examples

Suppose you want to write a function that produces a stream of square numbers, but without actually allocating a container to hold them all. You can now write:

fun squares(count: Int): mutable Iterator<Int> {
  foreach (i in range(0, count)) {
    yield i * i
  }
}

// Enabling users to write something like this:
foreach (n in squares(100)) { ... }

That’s a bit contrived, so let's look at a real example of how generators can improve Skip's standard library. Skip Iterators support chaining into pipelines, such as:

    x.values()
      .filter(a -> a.isValid())
      .map(b -> b.name)

Previously, Iterator's filter() method created an instance of a custom FilterIterator class that wraps its own value stream:

  overridable mutable fun filter(p: T -> Bool): mutable Iterator<T> {
    mutable FilterIterator(this, p)
  }

By itself that looks fine, but of course it requires writing a separate FilterIterator class, and that class does a bunch of messy stuff (don’t worry about the details):

  mutable fun next(): Option<T> {
    found: Option<T> = None();
    while_loop(() ->
      this.base.next() match {
      | Some(x) ->
        !this.p(x) ||
          {
            !found = Some(x);
            false
          }
      | None() -> false
      }
    );
    found
  }

That code was written before Skip supported early return, so it could be made more concise. But with generators, we can go much farther than incremental tweaking; in fact, the FilterIterator class is now completely gone, leaving us with only this method on Iterator:

  overridable mutable fun filter(p: T -> Bool): mutable Iterator<T> {
    foreach (v in this) {
      if (p(v)) yield v
    }
  }

I think you'll agree that's much easier to read!

Implementation details

Skip's generators are implemented in basically the same way that other languages do.

For each function containing a yield, the compiler creates a custom Iterator subclass whose next() method holds a transformed version of the the user’s function. The original function is replaced with a stub that simply returns a new instance of that subclass.

The transformed next() method weaves a simple state machine into the user's code, with states corresponding to "initial call", "done", or which specific yield was executed most recently. On entry, next() does a switch on the state number field, resuming execution where it last left off.

Each yield x saves that yield's state number and any live local variables into fields, so they can be restored on the next call to next(), then returns Some(x). When next() is completely finished, it returns None().

The Skip compiler primarily targets LLVM, although there is also Peter Hallam’s Javascript back end, which transpiles to native Javascript generators. I looked into leveraging LLVM's coroutine support, but I couldn't use it because I need to control the coroutine suspend state in order to describe it to Skip's garbage collector. But even if I could solve that, the strategy of desugaring generators into normal Skip objects allows us to apply our standard mid-level optimizations to that code before handing it to LLVM, including potentially inlining all of the generator code and removing the heap allocation.

Next up, async/await!

Conditional Trait Usage

April 19, 2018

Todd Nowacki

A long requested feature of conditional usage has finally landed!

Quick Overview of Traits

In Skip, traits cannot be used in normal types, but can be used as constraints on generics. This limitation let's code to be easily shared between value classes and normal, reference classes. Additionally, it let's us capture behavior that cannot normally be expressed by traditional interfaces in other OO languages, for example, we can definite the equality operator == in the Equality trait.

Concretely we have

// inst get's substituted for the class that uses the trait
trait Equality {
  // A user of the trait must define this method
  readonly fun ==(other: inst): Bool;
  // They get this method for free
  overridable readonly fun !=(other: inst): Bool {
    !(this == other)
  }
}

fun selfEq<T: Equality>(x: T): Bool {
  // inst is substituted with T
  x == x
}

Conditional Methods

Often when defining methods like == or toString for collections, the collection needs some handle to the function for it's underlying values. In OO languages, this is often done by defining a static method, that either adds an interface constraint to a generic, or has a lambda that is used to perform the operation.

For example

mutable class Vector<+T>(...) {
  static fun toString<V: Show>(v: readonly Vector<V>): String { ... }
  static fun eqBy<V>(v: readonly Vector<V>, eq: (V, V) -> Bool): Bool { ... }
}

But, with conditional methods, we can do better!

This feature adds a set of constraints written as [T1: C1, T2: C2 & C3], where the method can be called only when the constraints are met. (This is similar to where types in other languages, for example in Hack)

We can then modify these examples to normal ==, toString instance methods.

For example

mutable class Vector<+T>(...) {
  readonly fun toString[T: Show](): String { ... }
  readonly fun ==[T: Equality](): Bool { ... }
}

Even though Vector now has == and toString, it cannot use Equality nor Show, since it has these additional constraints. This brings us too...

Conditional Trait Usage

Combining traits and conditional usage, we get conditional trait usage. The syntax is as follows

class MyClass<T>() uses MyTrait<T>[T: X]

And can be read as "MyClass uses MyTrait of T, when T is a subtype of X"

We can then modify our example before

mutable class Vector<+T>(...) uses Show[T: Show], Equality[T: Equality] {
  readonly fun toString[T: Show](): String { ... }
  readonly fun ==[T: Equality](): Bool { ... }
}

Inheriting Methods

When inheriting method implementations, any conditions on the trait usage are added to the method. For example:

class MyClass<T>(x: T) uses Equality[T: Equality] {
  // Explicit declaration
  fun == [T: Equality](other: MyClass<T>): Bool {
    this.x == other.x
  }

 /* Implicit, inherited declaration
  * fun != [T: Equality](other: MyClass<T>): Bool {
  *   not(this == other)
  * }
  */
}

Inheriting Parent Traits

When inheriting trait usage from another trait, any conditions on the trait usage are added to the method. For example:

trait Orderable extends Equality {
  ...
}

class MyClass<T>(x: T)
  uses Orderable[T: Orderable] /* (implicit) Equality[T: Orderable] */ {
}

This can lead to some nasty "gotchas", as you might not realize that it is NOT the case that MyClass<T> uses Equality[T: Equality]

For example:

class HasOrd() uses Orderable { ... }
class HasEq(): uses Equality { ... }
...
selfEq(MyClass(HasOrd())); // Valid!
// ERROR MyClass does not have Equality since HasEq does not have Orderable
// selfEq(MyClass(HasEq()));

Limitations

I'll try to explain this very quickly, but I will be glossing over a lot of detail.

The TL;DR

The implementation of conditional trait usage leverages on the fact that the Skip type checker only looks at class hierarchies lazily AND that trait constraints tend to be solved only once type inference is complete.

If the type system yells and says this object doesn't use a given trait, but you think the conditions are met, try annotating your type

In the Skip type checker, we implement subtyping by expanding any object type into it's full hierarchy. Then we can implement various subtyping relations by using a combination of set operations. This system is very powerful, and deserves it's own post, but the important thing to know is that to do these set operations, we have to fully expand a type into it's hierarchy.

In some cases, we can be lazy and delay the expansion of the hierarchy until we need to. It was much easier to implement conditional uses via this lazy expansion, since no new information had to be added to these sets of types.

But, there are some situations where this expansion is forced, most commonly is when combining the branches of if-expressions with two children of the same hierarchy.

In cases like that, the type system might fail to see a conditional trait usage is valid.

Example:

base class P<T>(value: T) uses Equality[T: Equality] {
  children = L | R
}
...
// f : () -> alpha
f = () -> 0;
// p : P<alpha>, the trait was dropped since alpha wasn't known
p = if (true) L(f()) else R(f());
// ERROR P<Int> does not use Equality
selfEq(p)

In this example, the type system expands up the hierarchy to find the type of p. But since we do not know the type of alpha yet, the type system is forced to drop the conditional trait. And thus we get this weird error.

Note though, that the code will work if you annotate p : P<Int>

Future Work

There are two major areas that need to be improved.

Error Messages: Currently the error message sucks. In the example above, it will just say that P<Int> doesn't have Equality. Which is very confusing. The error message needs to indicate that the conditional check was likely failed to be inferred correctly due to some usage at the type. And the type should be annotated

Conditions Don't Affect Constraints: If you do something like [Vector<T>: Show] It will not infer [T: Show] even though Vector<T> uses Show[T: Show]. It will require some reworking of parts of typing to keep track of these constraints (we need to not throw out certain bits of information)

Summary

Conditional Traits are a great tool for Collection-like objects
Conditional Trait usage adds the conditions to any inherited method
Conditional Trait usage adds the conditions to any inherited traits
If the type system freaks at you and thinks the trait isn't there, annotate the type
The conditions do not yet propagate for generic's constraints.

Understanding Mutability

April 10, 2018

Todd Nowacki

Unlike many other languages, Skip favors immutability by default, with the ability to make things mutable explicitly. And as such, we've added a good bit of syntax and terminology that you would not normally find in an Object Oriented language. That being said, I think our system is remarkably simple given the amount of expressive power, and hopefully, it will be easy to understand!

This post will cover the principles of the mutability model in Skip

Overview

Skip is designed first and foremost as a language to support reactivity (memoization with computation-dependent invalidation). In order to do this soundly, objects need to be immutable. As such, objects are immutable by default in Skip. However, when objects are immutable, it is often difficult to build up collections or partial results without a lot of copying, which can be slow. Additionally, some designs or ideas just aren't expressible with immutability, e.g. references. To support this, we have the ability to explicitly declare instances of objects as mutable.

A quick overview of these rules:

Object types have a mutability "mode"
Objects types have the immutable mode by default
There is no immutable modifier in the syntax
Objects can be explicitly instantiated as mutable
readonly is a mode that lets code work both for mutable and immutable objects
There are no global mutable values. All mutability is locally scoped, or explicitly declared at function boundaries.
Objects are considered frozen if they are immutable and all of their type parameters are frozen
Arguments to inputs and outputs to memoized functions must be frozen

Basics of Mutable Objects

Classes that can have mutable instances must be declared as mutable.
The type of mutable instances of a class is the class name, preceded by the mutable type modifier. The class name by itself denotes the type of immutable instances of the class.
Mutable instances are created by prefacing an object construction expression with mutable. An object construction expression without mutable in front creates an immutable instance.
Fields are made assignable by prefacing their declaration with mutable.
Assignable fields on mutable objects are modified by using a ! on the left-hand side of an assignment.
Mutable instances can be made immutable with freeze().
While a class's type parameters can be declared to be covariant or contravariant instead of the invariant default, those variances only apply to immutable and readonly instances. The type of a mutable instance is considered to have invariant type parameters.

Examples:

// Ref can have mutable instances
mutable class Ref<+T>(mutable value: T)

// Pet has no mutable modifier, so no mutable instances
base class Pet { children = Dog() | Cat() }

...
// mutable keyword before type and construction expression
ref : mutable Ref<Int> = mutable Ref(0);
ref.!value = 1; // assigns 1 to the vector
assert(ref.value == 1);
frozen_ref : Ref<Int> = freeze(ref); // create a fully immutable copy
// Immutable instances cannot have fields assigned
// ERROR frozen_ref.!value = 1

// ! can be placed anywhere in an lvalue, denoting the in-place update
// of the field immediately to the right of the !
nested : mutable Ref<mutable Ref<Int>> = mutable Ref(mutable Ref(0))
nested.value.!value = 100;

// Immutable instances are covariant as declared
_ : Ref<Pet> = Ref(Dog())
// Mutable instances are made invariant
// ERROR _ : mutable Ref<Pet> = mutable Ref(Dog())

The Three Modes

Every object type has a mode: immutable, mutable, or readonly

immutable is the "default" mode, meaning that there is no modifier in the language for this mode. For example:

_ : Vector<Int> = Vector[]; // immutable Vector of Ints
_ : mutable Vector<Int> = mutable Vector[1, 2, 3]; // mutable Vector of Ints
// No direct way to create a readonly object
_ : readonly Vector<Int> = Vector[1, 2, 3]; // unmodifiable Vector of Ints
_ : readonly Vector<Int> = mutable Vector[1, 2, 3]; // unmodifiable Vector of Ints

Subtyping

As seen above, readonly is the "parent" mode.

This gives us the following subtyping relations. Let X and Y be two object types:

        X <: Y
----------------------
mutable X <: mutable Y

        X <: Y
-----------------------
mutable X <: readonly Y

X <: Y
---------------
X <: readonly Y

         X <: Y
------------------------
readonly X <: readonly Y

(these rules become more complicated with generics, see Mode Preservation for details)

Mode Semantics

The mode of a type can be thought of as modifying its declaration, as follows:

Immutable: None of the object's fields can be modified. Any mutable or readonly field types become immutable (before type instantiation), and methods marked mutable (meaning they require a mutable instance of this to operate) become unavailable. (More on method modifiers below.) This property is recursive for any type in the object's fields.
Mutable: Any of the object's fields can be modified if they are marked mutable. All field types keep their declared mode. Methods marked immutable (unmarked) or frozen become unavailable.
Readonly: None of the object's fields can be modified, but the actual instance might be mutable (there could be a mutable reference to this object). Any mutable types become readonly (before type instantiation). Methods marked mutable, immutable (unmarked), or frozen become unavailable.

"Before type instantiation" means that this rule only applies to types that are not type parameters/generics. For example readonly Vector<mutable Ref<Int>> is a readonly object that points to mutable data.

Reading all of this as formal rules would make your eyes bleed. Instead, here are a few concrete examples:

// updatable ref to a mutable vector of some type T
// (we don't know anything about the mutability of T, yet)
mutable class VectorRef<T>(mutable value: mutable Vector<T>)

// note that the field here is not updatable, and the Vector type is immutable
// ...but we still don't know about the mutability of T
mutable class NestVector<T>(value: Vector<T>)

...

// Immutable cases

v1 : VectorRef<Int> = VectorRef(Vector[1, 2, 3]);
// note the 'mutable' mode has been "frozen" off
_ : Vector<Int> = v1.value;
// And the argument MUST be immutable
// ERROR _ = VectorRef(mutable Vector[1, 2, 3]);
// And fields cannot be modified
// ERROR v1.!value = Vector[4, 5, 6]

// An immutable value that contains a mutable value!
v2: VectorRef<mutable Ref<Int>> = VectorRef(Vector[mutable Ref(42)]);
// The field's written mutability is gone, but the generic's mutability
// is still around
_ : Vector<mutable Ref<Int>> = v2.value;
_ : mutable Ref<Int> = v2.value[0];

// Mutable cases

mv1 : mutable VectorRef<Int> = mutable VectorRef(mutable Vector[1, 2, 3]);
// The field retains its defined mode
_ : mutable Vector<Int> = mv1.value;
// And the argument MUST be mutable  
// ERROR _ = mutable VectorRef(Vector[1, 2, 3]

// The field retains its defined mode
mv2 : mutable NestVector<Int> = mutable NestVector(Vector[1, 2, 3]);
_ : Vector<Int> = mv2.value;

// Readonly cases

rv1 : readonly VectorRef<Int> = mutable VectorRef(mutable Vector[1, 2, 3]);
// The field's declared 'mutable' mode becomes 'readonly'
_ : readonly Vector<Int> = rv1.value;
// And fields cannot be modified
// ERROR rv1.!value = mutable Vector[4, 5, 6]

// mutable inside readonly value
rv2: readonly VectorRef<mutable Ref<Int>> = VectorRef(Vector[mutable Ref(42)]);
// The field's written mutability is gone, and replaced with 'readonly',
// but the generic's mutability remains
_ : readonly Vector<mutable Ref<int>> = rv2.value;
_ : mutable Ref<Int> = rv2.value[0];

// Immutable types retain their defined mode
rv3 : readonly NestVector<Int> = mutable NestVector(Vector[1, 2, 3])
_ : Vector<Int> = rv3.value

The `frozen` Constraint

In several spots, such as with memoization, we need to know if a an object is "fully" immutable. Meaning that the object has to be mutable itself AND cannot contain any mutable values. For example Vector<mutable Ref<Int>> is immutable but not frozen.

The rule is as follows, given a class C:

C<t0, ..., tn> : frozen iff t0 : frozen .... tn : frozen

The constraint comes into play in two key places. The first, any generic can be marked as frozen

mutable class C<T1: frozen, T2>(x : T, y : T2) {
  fun test<V: frozen>(): void { ... }
  fun test2[T2: frozen](): void { ... }
}

Additionally, for memoized functions, all inputs and outputs must be frozen.

The `freeze()` operator

Skip provides a native operator freeze(e). That given any expression, it will give a deeply frozen copy such that freeze(e) : frozen. Note that not all types can be frozen (namely -> and ^ more on this later)

Method Modifiers

There are 3 method modifiers related to mutability, all of them modify the mutability of this inside the method (note they cannot be used on static methods)

no modifier this is immutable. The method can be called only on immutable instances.
mutable this is mutable. The method can be called only on mutable instances.
readonly this is readonly. The method can be called on any instance.
frozen this is frozen. The method can be called only on instances that satisfy the frozen constraint. For example:

mutable class C<T1, T2> {
  frozen fun ex(): void { ... }
  // is equivalent to  
  fun equivalent_ex[T1: frozen, T2: frozen](): void { this.ex() }
}

Relaxed Override Rules

As you might imagine based on the subtyping rules.

no modifier Can be overridden in the child by immutable or readonly
mutable Can be overridden in the child by mutable or readonly
readonly Can be overridden in the child by readonly
frozen Can be overridden in the child by frozen, immutable, or readonly

But there is a further relaxing that you can be achieved. If a class isn't marked as mutable, it means that that class, and any of it's children, cannot have mutable fields nor can they refer to any objects statically that have mutable fields. So from a typing perspective, all three modes are equivalent! Thus we get this new set of rules

If the child is NOT marked as mutable

no modifier, mutable and readonly Can be overridden in the child by mutable, immutable, or readonly
frozen Can be overridden in the child by frozen, immutable, or readonly

Note that as with the previous set of rules, a frozen child method must be frozen in the parent. Even though the three modes are equivalent, immutable is not the same as frozen.

Two Types of Lambdas

While lambda types are not objects in our type system, similar to objects they have a mutable and immutable mode.

-> This type of lambda can capture any type of value.
- If a field contains a -> in it's type, it can only be accessed from a mutable. There is no immutable or readonly view of ->
~> This type of lambda is considered "pure".
- It cannot capture any mutable values, additionally it cannot capture any local variable that was modified (past it's initial declaration).
- ~> is a subtype of ->, much like immutable is a subtype of readonly
- A ~> type is frozen, regardless of it's parameter or return types.

The Awaitable Type

The awaitable type ^t behaves very similarly to ->

For any t, ^t is not frozen
If a field contains the type ^t, it can only be accessed from a mutable. There is no immutable or readonly view of ->

Restrictions on Mutable Values

As mentioned, to provide certain guarantees for reactivity, we cannot allow mutability values in all locations.

Here are the restrictions

You cannot have mutable const declarations. All global (and class) constant must be frozen
As previously mentioned, ~> cannot capture mutable values
the if clause of a pattern match cannot modify any mutable value.
All parameters to a memoized function must be frozen
The return type of a memoized function must be ^t or t where t: frozen
memoized methods must have a this: frozen. This is easily done by marking the method as frozen
async { } blocks cannot capture mutable values, additionally it cannot capture any local variable that was modified (past it's initial declaration)
All parameters to a async function (and this for an async method) must be frozen
- However, just for these async contexts, we consider ^t : frozen if t : frozen. This is safe due to the awaitable type is "logically frozen", meaning you cannot modify any of it's state

Inferring `frozen` on certain functions

With the rules memoized and async functions/methods, it would be annoying to have to write : frozen on all of your type parameters.

Anywhere a type parameter appears in a memo/async function/method, where it would need to be frozen, we will infer the frozen constraint.

For example:

memoized fun ex<T>(Vector<T>): Map<Int, T> { ... }
// equivalent to
memoized fun ex<T: frozen>(Vector<T>): Map<Int, T> { ... }

async fun ex2<T, U>(Vector<T>, T ~> U): ^Vector<U>
// equivalent to
async fun ex2<T: frozen, U>(Vector<T>, T ~> U): ^Vector<U>
// note no need for U to be frozen

class Tester<T, U>(...)
  memoized fun ex(Vector<T>): U { ... }
  // equivalent to   
  memoized fun ex[T: frozen, U: frozen](Vector<T>): U { ... }

  async fun ex2(Vector<T>): ^U { ... }
  // equivalent to   
  async fun ex2[T: frozen](Vector<T>): ^U { ... }
}

Mode Preservation

Recall from above that when doing subtyping checks, there certain rules around the "subtyping" of modes.

If we make immutable mode (even though it is implicit in the concrete syntax), we can generalize with a submode judgement <|

 X <: Y    m1 <| m2
--------------------
   m1 X <: m2 Y

----------------------
immutable <| immutable      

------------------
mutable <| mutable  

--------------------
readonly <| readonly  

---------------------
immutable <| readonly  

-------------------
mutable <| readonly

Recall also that

 t1 : frozen ... tn : frozen
-----------------------------
   C<t1, ..., tn> : frozen

The new immutable mode, and the combination of these rules gives rise to a few properties that we need for these sub-typing relations to be sound.

Namely we need to know that for any type t1, t2 where mode(t1) = mode(t2) = immutable

If not(t2 : frozen) and t1 <: t2, not(t1: frozen)
If t1 : frozen and t1 <: t2, t2 : frozen

We refer to these properties as Mutability Preservation and Frozen Preservation respectively. These rules are so critical that without them, we would not be able to allow mutable instantiations of type parameters for immutable objects.

In other words, without Mode Preservation, we would have to require that immutable objects are instantiated only with frozen type arguments.

Mutability Preservation

Since the frozen constraint is critical to the safety around mutability, we need to ensure that the rule cannot be bypassed by upcasting. For example:

base class Parent
class Boxy<T>(value: T) extends Parent

It would be very dangerous if Boxy<mutable Vector<Int>> <: Parent since Parent: frozen but not(Boxy<mutable Vector<Int>>: frozen)! So you could break any of our immutability guarantees just by upcasting; this would be very, very bad.

This is why we have the mutability preservation rule.

In the implementation, when we are performing the subtyping relation in the type checker, if the new parent type is frozen, find all of the type parameters in the subtype that are NOT visible in the super type. Then verify that those types are frozen. If it contains a type variable, we just add a constraint that the type variable must be frozen.

For example: To check Boxy<mutable Vector<Int>> <: Parent

Parent: frozen so check the missing type parameter of the child
T for Boxy isn't visible
T is instantiated with mutable Vector<Int>
mutable Vector<Int> isn't mutable so ERROR

In another example, where a is a type variable, to check Boxy<Vector<a>> <: Parent

Parent: frozen so check the missing type parameter of the child
T for Boxy isn't visible
T is instantiated with Vector<a>
Vector<a> is frozen iff a is frozen so add a constraint to the environment that a : frozen

Frozen Preservation

In the reverse case, we need to be concerned with casting changing the mode of any type. This might seem counterintuitive that it would matter that you lose frozen when upcasting, since we do allow upcasting from immutable into readonly. BUT this is important when upcasting from one immutable type to another.

For example:

base class Parent<+T: mutable Ref<Int>>(v: T)
class Child extends Parent<mutable Ref<Int>>

fun no1(ref: Ref<Int>): void {
  c = Child(ref);
  p: Parent<mutable Ref<Int>> = c;
  p.v.set(42) // modifying an immutable object!
}

fun no2(p: Parent<mutable Ref<Int>>): Ref<Int> {
  p match {
  | Foo(ref) ->
    _: Ref<Int> = ref // mutable cast to frozen!
  }
}

This rule is very easy to implement in practice since it works exactly as described: When upcasting to a type, if it's immutable and not frozen, check the original type is not frozen

Summary

A quick wrap-up

Three modes for objects immutable, mutable, and readonly
Objects are immutable by default and can be explicitly instantiated as mutable
readonly acts as a "supertype" between mutable and immutable instances
frozen is a constraint that guarantees deep, full immutability.
In certain spots, only frozen objects can be used
The mode of the object can change the mode of the types in the field
Unless they are marked as frozen, type parameters can be instantiated with mutable types
Mutability and Frozen Preservation allow for mutable type arguments to immutable objects

Faster Option

February 20, 2018

Mat Hostetter

TL;DR: Skip's Option type is now implemented as a value class, reducing speed and space overhead.

Problem: "Option is too slow"

The Skip programming language (formerly “Reflex”) does not have conventional null pointers (avoiding Tony Hoare's "billion dollar mistake". Instead, as with several other languages, possibly-absent values are represented using a simple Option<T> class that has subclasses None() and Some(value: T).

The problem with this implementation is that calling Some(myValue) allocates a heap instance to "box" myValue. This can be expensive, especially given that the Iterator API is defined to return an Option each time through a loop. We were considering changing the Iterator API to avoid this overhead, but that idea was pretty unsatisfying.

Solution: Avoid heap allocation

Rather than compromise standard library APIs, over the weekend I fixed the performance problem. The back end now compiles Option to a value class, a pass-by-value object that never allocates heap memory.

The user-visible API is unchanged. The front end compiles Option normally, as if it were a reference type, but the back end changes the representation to a value class and converts internal operations like TypeSwitch (normally a vtable-examining operation allowed only on reference types) to analogous operations on the value class form.

The Skip compiler uses two strategies to compile Option<T> as a value class, depending on T: Flag and Sentinel.

Flag

The most general strategy is Flag. This compiles Option<T> as (effectively) a pair of (Bool, Unsafe.RawStorage<T>). If the Bool is true, the Option is really Some(), and the RawStorage holds the value. If the Bool is false, the Option is None() and the RawStorage is unused (but filled with all zero bits to make the GC and interner happy).

Flag is efficient, but it adds an extra Bool field that must be passed around and stored. This is almost always better than heap allocating, but it can make an object containing an Option field larger than it was previously, when that Option was just a pointer.

Sentinel

We can represent Option<T> using the same number of bits as T, if there is some "illegal" bit pattern for T that we can reserve for None(). The most obvious use case for this is Option<SomeReferenceType>. Here we just use a null pointer for None(), and the SomeReferenceType object pointer for Some. This is better in every way than the old Option implementation.

Sentinel is the preferred strategy, but can't always be used. Some types, like Int, have no "reserved" value, so Option<Int> must use Flag.

We can use Sentinel in some surprising cases. The tuple (Int, Int, String) is a value class, so we can’t use the null pointer trick for Option<(Int, Int, String)> in the usual way, but even so we don’t need to fall back to Flag. Instead, we use Sentinel, where the tuple (*, *, null) indicates None(). More generally, any value class that has a Sentinel-compatible field can use the Sentinel strategy by using the nullness of that field to indicate None() for the entire Option. Of course, for something like Option<(Int, Int, Int)> we still need to use Flag.

Nested Options

What about Option<Option<Option<String>>>? We'd like to use Sentinel, but we can't just use a null pointer, because that would leave ambiguous None() vs. Some(None()) vs. Some(Some(None())). We could just give up and use Sentinel for the "inner" Option and Flag for the outer ones, but where’s the fun in that?

Null isn't the only reserved pointer value -- the Skip garbage collector ignores any pointer <= 0. The compiler exploits this by detecting the nested Option case and using null (0) for the innermost Option (that's always the strategy for Option<String>), and then -1 as the sentinel pointer value for Option<Option<String>>, -2 as the sentinel for Option<Option<Option<String>>>, and so on.

Examples

Let's look at the assembly code produced for some simple functions. First, the Sentinel case:

fun stringSome(s: String): Option<String> {
  Some(s)
}

fun stringNone(): Option<String> {
  None()
}

compiles to:

sk.stringSome:
        movq    %rdi, %rax
        retq

sk.stringNone:
        xorl    %eax, %eax
        retq

And the Flag case:

fun intSome(n: Int): Option<Int> {
  Some(n)
}

fun intNone(): Option<Int> {
  None()
}

also compiles to some simple register manipulation:

sk.intSome:
        movb    $1, %al
        movq    %rdi, %rdx
        retq

sk.intNone:
        xorl    %eax, %eax
        xorl    %edx, %edx
        retq

As you can see, no heap allocations remain!

Now let’s try doing a pattern match:

fun stringDefault(s: Option<String>): String {
  s match {
  | Some(x) -> x
  | None() -> "[none]"
  }
}

This yields:

sk.stringDefault:
    testq   %rdi, %rdi
    movabsq $-1152818814380970405, %rax # imm = 0xF0005D656E6F6E5B
    cmovneq %rdi, %rax
    retq

Not only does this code have no memory loads, it doesn’t even have any conditional branches.

Conclusion

Skip Options are now fast enough that we can feel free to use them routinely, even in performance-sensitive code. Next up, I’d like to see us add some syntactic shorthand that makes them even easier to use.

Overview

Skip normally generates executables. How do we generate this DLL for HHVM to load?

Skip Runtime API

Calling Hack from Skip

How it works under the covers

Calling Skip from Hack

Portable Types

??T - Optional fields in shapes

Type Table

Talking About Objects

Copying OBJECTS

Proxying OBJECTS

FAQ

How do as expressions work?

Why have as expressions?

Why use patterns instead of types?

as patterns become @ patterns

macro Methods

Macros

Current Uses of Macros

Equality Example

JSON Example

How does it work?

What next?

Implementation details

Processes

Async + memoized, together at last

Skip compiler parallelism over time

Optimizations

Future Work

Language changes

HHVM integration

Making Loops Feel at Home with Expressions

Break and Else

Why the else keyword?

The Three Loops

foreach Syntax

foreach Semantics

Summary

A few examples

Implementation details

Quick Overview of Traits

Conditional Methods

Conditional Trait Usage

Inheriting Methods

Inheriting Parent Traits

Limitations

Future Work

Summary

Overview

Basics of Mutable Objects

The Three Modes

Subtyping

Mode Semantics

The frozen Constraint

The freeze() operator

Method Modifiers

Relaxed Override Rules

Two Types of Lambdas

The Awaitable Type

Restrictions on Mutable Values

Inferring frozen on certain functions

Mode Preservation

Mutability Preservation

Frozen Preservation

Summary

Problem: "Option is too slow"

Solution: Avoid heap allocation

Flag

Sentinel

Nested Options

Examples

Conclusion

Why the `else` keyword?

The `frozen` Constraint

The `freeze()` operator

Inferring `frozen` on certain functions