I designed Khepri with function inlining in mind, but inlining support was only recently added to the compiler. This post overviews the Khepri compiler’s inlining support. A later post will cover some of the specific challenges of inlining Javascript and how Khepri implements inlining.

# The Need For Inlining

The functional programer solves a complex problem by composing the solutions of its independent subproblems. With the function as the base unit of computation, this approach produces lots of tiny functions, each of which does a simple computation or composes other computations.

Given the importance of functions and function application, it is very important that the overhead of calling a function be minimized. While modern Javascript runtimes can perform many millions of function calls per-second, each call still adds noticeable overhead, overhead that can far outweigh the cost of evaluating the body of a small function.

// These tiny functions from Nu are called hundreds of thousands of times
// during even simple Bennu parsing.
stream := \val f -> ({ first: val, rest: f });
first := (.first);
rest := \s -> s.rest();
isEmpty := (===, NIL);

Inlining a function call replaces the call with the function body. Even if the Javascript runtime supports inlining, there is often a benefit to inlining in the source. While not always appropriate, inlining enables the functional-style Javascript that Khepri targets to perform nearly as well as hand optimized imperative Javascript code.

## Use With Khepri Builtins

Khepri also relies heavily on inlining to generate efficient code for its builtins.

var compose := \a b -> \x -> b(a(x));

var f = compose((+, 10), compose((_/, 2), (_>, 5)));

Without inlining, calling f calls a total of five functions:

1. Call the function from outer compose.
2. Call (+, 10)
3. Call the function from the inner compose.
4. Call (_/, 2)
5. Call (_>, 5)

Khepri uses the exact same compose function definition for its composition \> operator, but the output after inlining is:

var f = (+, 10) \> (_/, 2) \> (_>, 5);

// Output With Inlining -----
var f = (function(z) {
var z0 = (10 + z),
y = (z0 / 2);
return (y > 5);
});

For a total of one function call per call to f (the example with compose will optimize to the exact same optimized output). Even when the a and b functions cannot be inlined at compile time, the inner compose calls always can be. The Khepri output has far less definition overhead too.

# Khepri Inlining

The Khepri compiler can inline small function calls to eliminated call overhead. This section details when a function can or cannot be inlined, and how code may be effected by inlining.

The compiler attempts to optimize code without effecting its visible behavior, but does make a few important exceptions for inlining. Khepri’s inlining documentation has more comprehensive inlining documentation.

## Lambda Functions

Any call to a lambda function may be inlined. Lambda functions are functions that:

• Have an expression body. Functions with block bodies cannot be inlined at this time.
• Does not use a fat arrow unpack.
// These are lambda functions
\ -> 1;
\x -> x;
\a#[{x}, y, ...xs] -> ...'
\args(x ...) -> args;

// and these are not
\x -> { return x; };
\=self-> self.x;
\={x}-> x;

## Callees

Individual function calls may be inlined only when the compiler can safely resolve the callee to a lambda function. In general, a callee bound immutably to a lambda function can always be inlined.

// Immutable bindings inlining ----
// This can always be inlined
var sqr := \x -> x * x;

// As can this
var callWith2 := \f -> f(2);

// This inlines both `calleWith2` and the inner `f` for `sqr`
callWith2(sqr);

But calls with mutable callees can sometimes be inlined too, if the compiler can unambiguously resolve the callee to a lambda at that point of execution.

// Mutable bindings inlining ----
var sqr = \x -> x * x;
sqr 2; // here we can inline because we know what `sqr` is

// This too can be fully inlined at this point
// because we can inline `cube` and we know what `sqr` is
var cube := \x -> sqr(x) * x;
cube 3;

// But if we do some evil mutation
sqr = null;

// We can't inline `sqr` inside `cube` anymore
cube 3; // outputs: sqr(3) * 3;

#### No Methods

This brings up a major limitation of Khepri’s inlining; only calls to functions, and not methods, can be inlined. There is simply no way for the compiler to safely determine the value of the method at compile time.

// Inlining would be nice here
var math = {
sqr: \x -> x * x
};

math.sqr(2);

// But we safely can't because of mutation
math.sqr = \x -> 4;

// This is the correct behavior of the program.
// Inlining would result in `math.sqr(3)` being 9 instead.
math.sqr(2); // 4
math.sqr(3); // 4

## Function Call to Let Expression Expansion

Khepri inlines a function call by expanding it to let expression. Let expressions have very little overhead and can be further optimized by later compiler stages.

var add := \x y -> x + y;

// inline expansion ----
let x = 2, y = 2 in x + y;

The expanded let expression binds the inlined function’s parameters to the function call arguments. Inlined function call arguments are evaluated left-to-right, before the body of the function. Scoping remains the same, with arguments evaluated in the callee scope, and the function body evaluated in the function’s scope.

#### Unused Binding Removal

Once a call is rewritten to a let expression, unused argument bindings may be pruned at compile time.

var mid = \_ ...mid _ -> mid;
mid(a(), b(), c(), d());

// inline expansion ----

// Ends are never evaluated
let mid = [b(), c()] in mid;

Regular function calls evaluate all arguments, even those that are never used, before evaulating the body. This difference is intentional and, I believe, justified. There are far more cases where it is highly beneficial to remove such unnecessary calculations then there are cases where code depends on evaluation of unused arguments.

# Other Differences and Limitations

## Arguments Object

Khepri can inline functions that use the arguments object, but inlining replaces the arguments object with a Javascript array of values. Code should only perform lookups on the arguments object, so usually this should not cause problems.

var f := \args(x y) ->  (x + y) * args.length;

f(1, 2);
// inlines to
let x = 1, y = 2, args = [x, y] in (x + y) * args.length;

But this behavior can allow an inlined function call to work correctly, while a regular call would crash.

var list := \args(...) -> args;

// This always works correctly, regardless of inlining
var a := list(1, 2, 3);
[].prototype.forEach.call(a, console.log);

// While this crashes if `list` is not inlined
// because `a` would be an arguments object and
// have no method `forEach`.
var a := list(1, 2, 3);
a.forEach(console.log);

A slice unpack however will always return a list:

var list := \...args -> args;

## Lazy Function Body Evaluation

Some functions rely on lazy evaluation of the function body:

// Here we are using a function to delay resolution of `s` to
// create a circular list.
var s = \ -> s;
s = stream(1, s);

Inlining s in the call to stream would resolve the s in the body of s early to undefined.

Functions that require this sort of lazy evaluation cannot be converted to expressions with inlining. A block function body may be used to explicitly disable unwanted inlining.

var s = \ -> { return s; };
s = stream(1, s);