TL;DR We want to add "function traits" that track an expression's capabilities and "computation modes" that indicate the mechanism of evaluation.
# pure, transform, linear
func inc(x: Int64):
return x + 1
end
Goal
Beyond type information, there are certain function characteristics that are vital for the compiler to know. For example, we may wish to know that an expression is to be evaluated at compile time, or that an expression represents a streaming computation.
Function traits and computation modes are a proposed solution. By explicitly listing a function's capabilities, we have a way of allowing new mechanisms of evaluation.
The traits proposed here are an inversion of effect systems. (If types describe the kind of data, then effects describe the kind of computation.) Effects generally describe "bad" things that can happen, like IO, state changes, and exceptions. A compound expression's effect is the set-wise union of all subexpressions' effects.
The function traits proposed here describe something "good" that can happen, and compound expression traits are the intersection of subexpression traits. The resulting computation mode is then determined from the traits.
Traits and Modes
Traits describe the qualities of a computation:
pure: no side effects
transform: does not change an array's size (can be used in a grouped transformation)
linear: computes in linear a fashion (ie., no random or forward-looking access)
autostream: defaults to streaming computation
Modes indicate how a computation is performed:
stream: to be evaluated in pieces
comptime: to be evaluated at compile time
async (TODO): to be evaluated concurrently
A function can have any number of traits, but only one mode. The resulting traits of a function call are simply the set-wise intersection of the the function and all parameters. The mode is determined by specific rules:
stream: function is autostream, or function is linear and at least one parameter is stream
comptime: function is pure and all parameters are comptime
aync: TODO
Most VVM ops will be pure, transform, and linear with the following exceptions:
IO is not pure (eg., load(), store(), print(), etc.)
unique() and filter() are not transform
sort() and index ([]) are not linear
load() and range() include autostream
Regarding mode, literals are comptime. Constant assignment (let) can be comptime, but variables (var) are not.
Implementation
The traits will be stored as an integer bitmap; subexpressions need only be &'ed and |'ed together.
The traits and mode will exists for all expressions and declarations. As mentioned in the final remarks of issue #23, we need to know when a value is available at compile time:
# both of these values are comptime:
let x = 7
let y = add(3, 4)
A function's traits and mode are inferred at compile time based on the function body's return statements, similar to how the function's return type is inferred.
Thinking Ahead
It is conceivable that users could define their own traits as part of a metaprogramming regimen. I don't yet know what this would look like, so I am putting that on hold for now.
Users might need to explicitly list the traits for a recursive function. (Users already have to explicitly list the return type for recursive functions.) That implies some sort of syntax like
func foo(x: Int64) pure, transform, linear -> Int64:
The primary purpose for creating function traits is to support both compile-time function evaluation and streaming computation. We may want to distinguish chunked from continuous, but we will punt that for now.
TL;DR We want to add "function traits" that track an expression's capabilities and "computation modes" that indicate the mechanism of evaluation.
Goal
Beyond type information, there are certain function characteristics that are vital for the compiler to know. For example, we may wish to know that an expression is to be evaluated at compile time, or that an expression represents a streaming computation.
Function traits and computation modes are a proposed solution. By explicitly listing a function's capabilities, we have a way of allowing new mechanisms of evaluation.
The traits proposed here are an inversion of effect systems. (If types describe the kind of data, then effects describe the kind of computation.) Effects generally describe "bad" things that can happen, like IO, state changes, and exceptions. A compound expression's effect is the set-wise union of all subexpressions' effects.
The function traits proposed here describe something "good" that can happen, and compound expression traits are the intersection of subexpression traits. The resulting computation mode is then determined from the traits.
Traits and Modes
Traits describe the qualities of a computation:
pure: no side effectstransform: does not change an array's size (can be used in a grouped transformation)linear: computes in linear a fashion (ie., no random or forward-looking access)autostream: defaults to streaming computationModes indicate how a computation is performed:
stream: to be evaluated in piecescomptime: to be evaluated at compile timeasync(TODO): to be evaluated concurrentlyA function can have any number of traits, but only one mode. The resulting traits of a function call are simply the set-wise intersection of the the function and all parameters. The mode is determined by specific rules:
stream: function isautostream, or function islinearand at least one parameter isstreamcomptime: function ispureand all parameters arecomptimeaync: TODOMost VVM ops will be
pure,transform, andlinearwith the following exceptions:pure(eg.,load(),store(),print(), etc.)unique()andfilter()are nottransformsort()and index ([]) are notlinearload()andrange()includeautostreamRegarding mode, literals are
comptime. Constant assignment (let) can becomptime, but variables (var) are not.Implementation
The traits will be stored as an integer bitmap; subexpressions need only be
&'ed and|'ed together.The traits and mode will exists for all expressions and declarations. As mentioned in the final remarks of issue #23, we need to know when a value is available at compile time:
A function's traits and mode are inferred at compile time based on the function body's
returnstatements, similar to how the function's return type is inferred.Thinking Ahead
It is conceivable that users could define their own traits as part of a metaprogramming regimen. I don't yet know what this would look like, so I am putting that on hold for now.
Users might need to explicitly list the traits for a recursive function. (Users already have to explicitly list the return type for recursive functions.) That implies some sort of syntax like
The primary purpose for creating function traits is to support both compile-time function evaluation and streaming computation. We may want to distinguish chunked from continuous, but we will punt that for now.