Since last year's FOSDEM, the Fuzion language has seen two major enhancements: algebraic effects and type features. Algebraic effects provide a means to manage non-functional side-effects of calls, while type features provide means to attach logic to type parameters providing more power to generic types.
This talk will explain algebraic effects and type features in Fuzion and show how they can be used. Algebraic effects provide means to manage non-functional aspects like I/O, global and local state, exceptions and much more. This can be used to automatically detect security issues due to side-effects. Many examples will be given that show how typical code patterns in Java can be realized in a purely functional way using effects and type features.
Fuzion is a modern general purpose programming language that unifies concepts found in structured, functional and object-oriented programming languages into the concept of a Fuzion feature. It combines a powerful syntax and safety features based on the design-by-contract principle with a simple intermediate representation that enables powerful optimizing compilers and static analysis tools to verify correctness aspects.
Algebraic effects are a relatively new mechanism currently in use in some research programming languages to make side-effects explicit. The motivation for this is to make any side-effects explicit and use this information either for security analysis or to permit optimizations, e.g. to automatically detect redundant calls or potential for parallelism. An analysis of side-effects of library code could have made it clear early on that code contains the log4shell vulnerability by exposing the side effects of network access and possible loading of code.
Algebraic Effects are sets of operations that encapsulate a side-effect in a way that is orthogonal to otherwise purely functional code. Algebraic effects represent values that are additional implicit arguments and results of functions that depend on an operation provided by an effect.
Such functions must be called with an instance of the effect available in the environment they are called from. Effects can be installed for a certain region of code. Regions using given effects can be nested and inner regions may replace the effects installed in surrounding regions.
When an operations of an effect is performed, say read on a file-I/O effect,
that effect typically returns with a result, in this case the byte read. Is is
said that the caller resumes operation with the result value. However, an
operation may as well abort a calculation, which means that it will not return a
result but continue execution at the end of the region for which the effect was
installed. In the general case, the operation of an effect may resume with 0,
1, or more results, while the effect is responsible of joining the resulting 0,
1, or more execution paths.
In a sense, Java's exception mechanism has a lot in common with effects: The
try-block defines the region, while throw corresponds to aborting an
operation and the catch or finally clauses perform the required code to
produce a result from a resumed or aborted operation.
In Fuzion, effects are Fuzion features that inherit from base library feature
effect and define their operations as inner features. Effects are identified
by their type. Imagine we define an effect x that provides an operation y,
then we would do
x : effect is
y(arg some_type) => ...some operation...
A feature f using effect x to perform operation y given value v would then write
f =>
...
x.env.y v
...
This means that effect x is taken from the current environment to call
operation y v.
Before f can be called, we must install an instance of x. This can be done as follows:
x.use ()->f
Where x creates this instance and use installs it while executing the
provided lambda ()->f, which in this case does nothing but call f.
Fuzion provides a static analysis tool to determine for each feature the set of effects a call to that feature may require. There is currently no syntax to include in a feature declaration the set of effects that feature requires. However, it is planned that for library code, such syntax will be added to document the effects directly required. It is this analysis that permits the detection of the safety of code.
In Fuzion, features may have type parameters and value parameters, similar to Java's method that may have generic arguments and 'normal' arguments. In Fuzion, however, type parameters are treated much the same way as value parameters, but they can additionally be used as types.
It is possible to call a feature on a type argument. A simple example is the following
f(A type, v A) is
say "f called with type $A and value $v"
f u16 123
f 123 # using type inference for A
f 3.14
resulting in
f called with type u16 and value 123
f called with type i32 and value 123
f called with type f64 and value 3.14
In Fuzion, every feature defines a type, which is the type of its local instance. Type features are features declared implicitly for every feature. Type features duplicate the inheritance tree of their underlying features, such that type features can be inherited and redefined.
The values of type parameters are instances of these type features and the inner
features that can be called are the features defined for the type feature. We
can, e.g., redefine asString in a type feature as follows
point(x, y i32) is
redef asString => "point $x $y"
redef type.asString => "!!!my point type!!!"
f (point 3 4)
resulting in
f called with type !!!my point type!!! and value point 3 4
This mechanism is more powerful than generics as used in Java since we can define additional functionality, e.g., each type could provide an operation to compare values of that type.
The talk will present code examples of how this will be done:
These are all represented by (nested) Fuzion features.
Fuzion does not have static features, every feature is declared as an inner feature of some outer feature and called on an instance of that outer feature. However, type features provide a natural place for what is a static method is Java. But there is more: these can be inherited and redefined!
In Fuzion, all fields are immutable, i.e., it is not possible to change a value. In code like
x := 123
say x
x := 2*x
say x
x := x+1
say x
there are actually three fields x declared, only the later ones masks the
earlier ones. It is not possible to write a setter as follows
x := 123
setX(v i32) =>
x := v
since this would just define a new local field x within the feature setX.
Mutable fields must be declared explicitly:
x := mut 123
say x
x <- 2*x
say x
x <- x+1
say x
works. But the fact that this code performs a mutation is recorded by the side-effect 'mutate'.
In many cases, mutable variables are not needed, e.g., in a loop
for
i := 0, i + 1
while i < 10 do
say i
new instances of i are created for each loop iteration, so i is never
modified.
TBD: Will give an example how I/O is performed via an effect
A simple example using an untyped try-raise:
divide (a, b i32) =>
if b = 0
try.env.raise (error "division by zero!")
a / b
show_div(a, b i32) =>
r := try i32 (() -> divide a b)
match r
v i32 => say "ok, result is $v"
e error => say "not ok: $e)
show_div 100 12
show_div 100 0
show_div 10 100
Immutable static fields in Java are often used for constants. In Fuzion, these can be just type features resulting in a constant.
Mutable static fields, however, are used for side-effects like caching of intermediate results. Fuzion effects can be used here as well,
A cache effect does this for us:
expensive =>
say "sleeping 3sec..."
time.nano.sleep (time.durations.seconds 3)
4711
my_cache(val i32) is
expensive_with_cache => (cache my_cache (() -> my_cache expensive)).val
say expensive_with_cache
say expensive_with_cache
Fuzion is still in an early prototype stage, but the language is reaching a more stable state. Some of the syntax shown here is still subject to change. We are developing sample code to compare different options and choose a clear syntax.
A large number of examples is shown on the Fuzion website flang.dev, in particular the tutorial, idioms and design pages.
Fuzion currently has two back-ends, a Java interpreter and static compiler using C as intermediate language. A tool called fzjava creates Fuzion interfaces for Java modules such that interaction with arbitrary Java code is possible.
The addition of algebraic effects and powerful type parameters bring Fuzion a big step ahead as a general purpose language. The use of algebraic effects brings a simple and powerful mechanism to provide many features known from imperative programming languages to functional world while enabling static analysis to ensure that unwanted side-effects do not occur.
With the language specification becoming more stable, it is now time to develop a modern standard library and improve the performance of the back-ends. We are currently a small team of three developers at Tokiwa Software bringing this ahead, but we are happy get feedback or other active contributors!
Speakers: Fridtjof Siebert