Brussels / 4 & 5 February 2023

schedule

Algebraic Effects and Types as First-Class Features in the Fuzion Language

Giving a pure functional solution for non-functional aspects.


Fuzion is a modern general purpose programming language that unifies concepts found in functional and object-oriented programming languages. It combines a powerful syntax and safety features with a simple intermediate representation that enables powerful optimizing compilers and static analysis tools to verify correctness aspects.

Since FOSDEM 2022, Fuzion has seen two major improvements: The introduction of Algebraic Effects and a unification of types parameters and argument fields.

Side-effects of functions are hard to model in a purely functional way, while object-oriented languages typically allow code to have arbitrary side effects. Algebraic Effects were introduced to Fuzion to help track and control side-effects of features. But there is much more: Algebraic Effects provide a clean mechanism to provide mutable state, to share global data, to provide an exception mechanism and much more.

Also, Fuzion now treats type parameters like argument fields that receive types as their values. Types themselves may define inner features creating a hierarchy parallel to the hierarchy of Fuzion features. This permits type parameters to provide operations such as constructing instances of a parametric type. This talk will show how this can be used to provide functionality such as abstract equality in a clean an consistent way.

Introduction

Fuzion is a new functional and object-oriented language that aims at unifying different concepts to reduce the complexity of the language and tools processing code written in Fuzion. The biggest difference between functional and object-oriented languages is the handling of side-effects: In an ideal functional world, all functions are pure, i.e., free from side-effects, while in object-oriented languages like Java it is common to make frequent use of side effects, e.g. a Java method to read data would usually be a function read() that would return the read data and have the side-effect of advancing the current position in the input to the next element.

Side Effects

Side-effects may come in very different forms: I/O operations that interact with the outside world are just one example, other side effects are access or modification of global state, program termination or early abortion of some operation (e.g., via throwing an exception), logging, thread interactions, yielding data to a co-routines, etc.

Algebraic Effects

An algebraic effect is a set of operations that provide a certain functionality that may include side-effects. The idea is that any function that requires such an operations must do this explicitly, static that it depends on the corresponding effect. Any caller of a function that requires a certain algebraic effect either itself requires that same effect, or it must provide a handler that implements that effect.

As an example, say a function f performs some logging operation, so it requires a logger effect that has an operation log that adds one line of logging data. Any caller g of f therefore also depends on the logger effect, unless g itself would provide an implementation of the logger effect to be used by f. If g, e.g., provides a no-op logger implementation that does nothing in its log operation, then g could be pure and not depend on an effect, all the logging information created by f would be ignored. If, however, g would provide a logger that writes the log messages to a file, then g would no longer require the logger effect, but instead require some file-I/O related effect.

Operations of an algebraic effect usually return a result, but they may also abort the current calculation and directly return the the place the effect was installed. This makes effects somewhat similar to exception handling in some languages. But effects are more general, an operation of an effect may resume (return) an arbitrary number of times.

Type Parameters

Type parameters or generic types are common in many languages. Usually, type parameters are treated completely separately from normal 'value' parameters. In Fuzion, this distinction has been removed, type parameters are treated like value arguments only that the their actual value is a type. This permits adding functionality to types and performing operations on types such as creating an value of a given type.

Fuzion Language Overview

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.

Fuzion was influenced by many other languages including Java, Python, Eiffel, Rust, Go, Lua, Kotlin, C#, F#, Nim, Julia, Clojure, C/C++, and many more. The goal of Fuzion is to define a language that has the expressive power present in these languages and allow high-performance implementations and powerful analysis tools. Furthermore, Fuzion addresses requirements for safety-critical applications by adding support for contracts that enable formal specification and enable detailed control over run-time checks.

Many current programming languages are getting more and more overloaded with new concepts and syntax to solve particular development or performance issues. Languages like Java/C# provide classes, interfaces, methods, packages, anonymous inner classes, local variables, fields, closures, etc. And these languages are currently further extended by the introductions of records/structs, value types, etc. The possibility of nesting these different concepts results in complexity for the developer and the tools (compilers, VMs) that process and execute the code.

For example, the possibility to access a local variable as part of the closure of a lambda expression may result in the compiler allocating heap space to hold the contents of that local variable. Hence, the developer has lost control over the allocation decisions made by the compiler.

In Fuzion, the concepts of classes, interfaces, methods, packages, fields and local variables are unified in the concept of a Fuzion feature. The decision where to allocate the memory associated with a feature (on the heap, the stack or in a register) is left to the compiler just as well as the decision if dynamic type information is needed. The developer is left with the single concept of a feature, the language implementation takes care of all the rest.

Side-effects and Security

Unexpected side-effects in library calls are the cause of a number of recent security vulnerabilities such as log4shell. The talk will give some examples.

Algebraic Effects in Fuzion

In Fuzion, algebraic effects are features that inherit from a standard library feature effect. Algebraic effects are identified by their type, so different heirs of effect create different operations. So the declaration of an effect myeffect that provides an operation myoperation is a feature declaration of myeffect inheriting form effect and declaring an inner feature myoperation.

Since the caller of a feature has to provide an implementation of an effect, it is said that an effect has to be present in the environment of a given call. The syntax to access an operation myoperation of an effect of type myeffect uses the keyword env as follows: myeffect.env.myoperation, meaning that we take the implementation of myeffect from the current environment and then perform myoperation_ on it.

Algebraic Effect Examples

The talk will interactively show how effects can be declared, used and installed.

Type Parameters in Fuzion

The talk will present the syntax of type parameters and the declaration of operations associated with types. This enables a functional counterpart static methods in languages like Java without adding global state.

It will be shown how this can be used to implement an abstract equality operation that permits the definition of different implementations for different types along an inheritance hierarchy.

Conclusion and Next Steps

The addition of effects and type parameters were important steps to make the language more powerful while staying true to the spirit of Fuzion which is to simplify and unify aspects as much as possible.

A small team of developers is now working on the Fuzion implementation with a focus on the standard library, performance and interfaces with other languages.

Main points that are missing right now are

  • a powerful standard library
  • additional library modules for all sorts of application needs
  • low-level foreign language interface for C
  • actual implementations of static analyzers and optimizers
  • highly optimizing back-ends
  • garbage collection for the C back-end
  • documentation, tutorials
  • more enthusiastic contributors and users!

Please feel free to contact me in case you want to use Fuzion or want to help making it a success!

Speakers

Photo of Fridtjof Siebert Fridtjof Siebert

Links