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.

Introduction

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

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.

Effects in Fuzion

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.

Type Features

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.

Mapping Java to Fuzion

The talk will present code examples of how this will be done:

Packages, Classes, Interfaces, instance methods

These are all represented by (nested) Fuzion features.

static methods

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!

Variables updates

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.

I/O operations

TBD: Will give an example how I/O is performed via an effect

Exception handling

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

static fields

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

Status of Fuzion

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.

Conclusion and Future Work

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!

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!

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.

This talk will present the advances in the Fuzion languages since its first public announcement at FOSDEM 2021. This includes a simplified and cleaned-up syntax, improved type inference, its safety features, foreign language interface to Java and an overview of the existing and planned toolchain.

Fuzion is not only about the language itself, but just as well about the intermediate representation that is the basis for static analysis, optimization and back-ends. The talk will give an overview of the format of intermediate code.

Introduction

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 language 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.

Fuzion Feature Declarations

A Fuzion feature has a name, similar to the name of a class or a function. The main operation that can be performed on a feature is a feature call. The constituents of a feature declaration are as follows:

Formal Arguments

Features may have a list of formal arguments, which are themselves features implemented as fields. On a call to a feature with formal arguments, actual arguments have to be provided to the call, unless the list of formal arguments is empty.

Feature Result

The result of a feature call is an instance of the feature. Alternatively, a feature may declare a different result type, then it must return a value of that type on a call.

Closures

Features are nested, i.e., every feature is declared within the context of an outer feature. The only exception is the universe, which is the outermost feature in Fuzion. A feature can access features declared in its outer feature or, recursively, any outer feature of these outer features. This means, a feature declaration also defines a closure of the feature and its context.

When calling a feature f1 declared as an inner feature of f2, the call must include a target value which is the result of a call to f2, e.g., f2.f1.

Generics

Features may have generic type parameters. E.g. a feature declaration may leave the actual type used within that feature open and to be defined by the user of the feature.

The list of generic type parameters may be open, i.e., the number of actual generic type parameters is not fixed at feature declaration. This turns out to be useful in the declaration of choice types and functions as explained below.

Inheritance

Fuzion features can inherit from one or several other features. When inheriting from an existing features, all inner features of the parent automatically become inner features of the heir feature. It is possible to redefine inherited features. In particular, when inheriting from a feature with abstract inner features, one can implement the inherited abstract features.

A redefinition of an inherited feature may implement an inherited feature as a routine or as a field. An inherited feature that is implemented as a field, however, cannot be redefined as something else since fields might be mutable.

Inheritance may result in conflicts. An example would be two features with the same name that are inherited from two different parents. In this case, the heir must resolve the conflict either by redefining the inherited features and providing a new implementation or by renaming the inherited features resulting in two inner features in the heir feature.

Inheritance and redefinition in Fuzion does not require dynamic binding. By default, the types defined by features are value types and no run-time overhead for dynamic binding is imposed by inheritance.

A Contract

A feature may declare a contract that specifies what the features does and under which conditions the feature may be called.

An implementation

Features must have one of the following implementations

• a routine is a feature implementation with code that is executed on a call

• a field is a memory slot that stores a value and whose contents are returned on a call

• an abstract feature has no implementation and cannot be called directly, but can be implemented by heir features

• an intrinsic feature is a low-level feature implemented by the compiler or run-time system, e.g., the infix + operator to add two 32-bit integer values may be an intrinsic operation.

A feature implemented as a routine can contain inner feature declarations.

Feature examples

Here is an example that declares a feature point that functions similar to a struct or record in other languages:

point(x, y i32) is # empty
p1 := point 3 4
say "p1.x is {p1.x}"    # will print "p1.x is 3"
say "p1.y is {p1.y}"    # will print "p1.y is 4"

The next example shows a feature base that provides an inner feature plus that adds its argument to the value passed to the enclosing base:

base(v i32) is
  plus(w i32) => v + w

b1 := base 30
b2 := base 100
say (b1.plus 23)    # will print "53"
say (b2.plus 23)    # will print "123"

Fuzion Syntax Evolution

Fuzion provides two main syntax alternatives, a classic once using semicolons, braces and parentheses and a modern one using white-space and indentation. Both are equivalent, there should be tools between these two representations of source code. The following explains the main ideas how white-space is used instead of special symbols

Separating Statements

Flat line feeds instead of semicolons

The classic way to separate statements is by using a semicolon as in

stmt1; stmt2; stmt3

or

stmt1;
stmt2;
stmt3;

The Fuzion grammar knows a symbol called 'flat line feed', which is a line feed with the next line starting with white space up to the previous line's indentation level. A 'flat line feed' is considered equivalent to a semicolon, so the sequence of three statements above can be written without semicolons as follows:

stmt1
stmt2
stmt3

Indenting line feeds to form blocks

Code blocks in Fuzion can be build using braces similar to many other languages

if cond { stmnt1 } else { stmnt2 }

if cond {
  stmnt1
} else {
  stmnt2
}

if cond
  {
    stmnt1
  }
else
  {
    stmnt2
  }

An 'indenting line feed' in Fuzion is a line feed with the next line starting at a higher indentation level. The parser treats an 'indenting line feed' like a left brace '{'. Correspondingly, a linefeed that reduces the indentation level back to the original level is treated like a right brace '}'. The example above is hence equivalent to

if cond
  stmnt1
else
  stmnt2

Finally, an optional keyword 'then' may as well be used to separate an expression like the condition in an 'if' from a following expression without the need of braces:

if cond then stmnt1 else stmnt2

Separating calls, arguments and operator expressions

calls without parentheses

Fuzion calls do not need parentheses or commas to separate the called feature and its arguments, i.e., a call

f(a, b, c)

can be written as

f a b c

Parameters are then separated by white space. Line breaks, either flat or indenting as explained above, end the argument list.

Parentheses may be needed for nesting calls with arguments, e.g., the code

f (g x y) (h z)

is equivalent to

f(g(x, y), h(z))

If placed in parentheses, operator expressions may extend over several lines using an indenting line feed followed by additional flat line feeds, e.g.,

f (1 + 2 + 3 + 4 +
   5 + 6 + 7 + 8 +
   9 + 10 + 11 + 12)

Tuples of values such as '(a, b)' syntactically look like argument lists. A list of expressions enclosed in parentheses is treated as an argument list only if it immediately follows the name of a called feature. The code

f(a, b)

hence calls 'f' with two arguments 'a' and 'b'. In case there is white space after the name of the called feature as in

f (a, b)

the expression in parentheses is passed as an argument, so, in this case 'f' will be called with a single argument: the tuple '(a, b)'.

Array indexing vs. array creation

The square brackets '[' and ’]’ are used in Fuzion for two purposes: A pre-initialized array of fixed size can be created using an expression like '[x, y, z]', while an array can be indexed using 'a[i]'. Again, white space can be used to distinguish these two cases:

a[i]

read an element from an array while

f [x, y, z]

create array with elements x, y and z and passes it as an argument in a call to 'f'.

Operator expressions

Operators are parsed as prefix- or postfix operators if the are not separated by white space from their target operand, but they are separated by white space on the other side. This means that the call

f -x

is equivalent to

f (-x)

while

f - x
f-x

both subtract 'x' from 'f'. Furthermore,

f- x

is parsed as

(f-) x

i.e., it calls 'postfix -' on 'f' and, assuming the result is a function, calls this result with one argument 'x'.

The precedence of operators that are not separated by white space is stronger than that of a call, so

f a-b

is equivalent to

f (a-b)

while the precedence of calls is higher than that of operators separated by white space, i.e,

f a -b
f a - b

are equivalent to

f (a) (-b)
(f a) - b

respectively.

White space vs. explicit tokens

Attaching semantics to white space might appear dangerous and error-prone to those not used to it. However, more and more languages (Python, Scala-3, Nim, Raku, ...) make use of white-space and the experience is generally very positive, the code is cleaner, easier to read an even easier to maintain. Compiler errors complaining about unbalanced parentheses or braces are gone and mismatch between indentation and semantics may no longer occur.

Furthermore, even languages like Java allow code to have hugely different semantics if just a single white space is added, e.g., the Java code

if (cc) x(); elsey();
if (cc) x(); else y();

changes completely by insertion of a single space character.

Fuzion Type Inference

Fuzion is statically typed, every expression, every field, every routine result has a static type known at compile time. Type inference is used to avoid the need to specify these types explicitly in many situations, reducing the boilerplate code while keeping the safety of a statically types language.

Type inference in Fuzion occurs at explicit or implicit assignments. An explicit assignment is a field declaration with an initial value such as

v := expr

while an implicit assignment occurs, e.g., when a routine returns the value of its last expression as its result

sum (x, y u32) =>
  x + y

or when an argument is passed to a function

sum 1.234e6 567890

Type inference occurs in two directions: From the value to the field that the value is assigned to and from the type of the assigned field to the value. Field declarations using ':=' without an explicit type use the type inferred from the value, the same holds for routines defined using '=>'.

On the other hand, the type of expressions such as lambdas or numeric literals are inferred from what they are assigned to.

Type inference from expressions to feature result type

When declaring either a field using ':=' or a routine using '=>', the result type is inferred from the expression that is assigned or returned, respectively:

v := 123                    # type i32, default type for integer literal
v := "hello"                # type string
highNibble(b u8) => b >> 4  # type u8
origin => point 0 0         # type point

Type inference from expressions to type arguments

Type arguments are inferred from actual arguments as shown by the following example: Imagine a generic routine square as follows

square<T: integer<T>> (a T) => a * a

This could be called using explicit type arguments as in

say (square<i32> 23)

or the type can be inferred from the argument type

say (square 23)

As a consequence, type arguments can be omitted in many cases.

Type inference for lambdas

In Fuzion, inline functions (lambdas) are defined using '->' with the input variables on the left and the expression on the right. Types for a lambda are implicitly taken from the target the lambda is assigned to. E.g., the following example takes a function argument

print(s string, f (string, i32) -> string) =>
  say (f s 3)

print(f (i32, i32) -> i32) =>
  say (f 10 3)

print "Alice" (s,i -> s * i)   # lambda type is (string, i32) -> string
print "Bob"   (s,i -> s + i)
print (s,i -> s * i)           # lambda type is (i32, i32) -> i32
print (s,i -> s + i)

Type inference for numeric constants

Numeric constants that are assigned to a given type inherit that type. There is no immediate distinction between plain numeric literals like '123' or ones using a fractional parts and exponents such as '-0.1234E4'. The target type determines the type of the constant.

v1 u32 := 123456
v2 i8 := -128
v3 i16 := 32000
v4 u64 := 1000000000000000000
v5 i64 := -1000000000000000000
v6 u16 := 4711
v7 f32 := 123456
v8 f64 := 123.456E6
v9 f64 := 1.0E3

In case the constant is too large for the target type, or it has a fractional part not representable by the type, a compile-time error occurs:

v1 u32 := -123456       # error: negative value assigned to unsigned
v2 i32 := 3000000000    # error: value too large
v3 i8  := 128           # error: value too large
v4 u16 := 65536         # error: value too large
v5 f32 := 123.456E39    # error: overflow
v7 f64 := 123.456E309   # error: overflow
v8 f32 := 7E-46         # error: underflow

Fuzion Intermediate Files

Fuzion uses intermediate files during different stages of compilation: module files that contain library code, application files for whole applications and Fuzion intermediate representation files that serve as input to the back ends.

Fuzion uses a simple intermediate code to represent pre-compiled modules and whole applications. This intermediate code serves as the input for static analysis tools, optimizers and for different back-ends that produce executable applications. The goal in the design of the intermediate file format was high performance and simplicity for tools using this code.

The intermediate code is a binary format containing features and types in a way that may be mapped to memory and used directly, so overhead of parsing this format into an in-memory representation is avoided. In particular, if only parts of a pre-compiled module are used by an application, there is no need to read and unpack parts of the module intermediate representation that are not used.

For features containing code, a very simple stack-based format is used. There are currently only ten different instructions:

• Unit -- produce a value of unit type
• Current -- produce the current instance as a value
• Constant -- produce a constant value
• Assign -- perform an assignment to a field
• Call -- perform a call to a given feature
• Tag -- convert a value into a tagged value of a choice type
• Match -- match a choice type
• Box -- convert a value type to a ref type
• Unbox -- extract the value from a ref type
• Pop -- drop the top element from the stack

The intermediate code uses indices to refer to features and types within intermediate files. This means that lookup is very efficient, but it also means that a change in a library module requires recompilation of all dependent modules. Any incompatibilities would be found at compile time instead of resulting in something like Java's 'IncompatibleClassChangeError' at run-time.

Foreign language interface

Fuzion provides a tool 'fzjava' that takes a Java module file and converts it into Fuzion features. In the spirit of Fuzion, Java's packages, classes, interfaces, methods, constructors, static methods and fields are all converted into Fuzion features. Java methods that may throw an exception are converted into features resulting in a choice type that is either the exception type or the result type of that method.

A few intrinsic functions in the Java interpreter back-end use Java's reflection API to access the corresponding Java code.

Here is a example how Java code can be used from Fuzion:

javaString := java.lang.String.new "Hello Java 🌍!"                          # create Java string, type Java.java.lang.String
javaBytes  := javaString.getBytes "UTF8"                                     # get its UTF8 bytes, type is fuzion.java.Array<i8>
match javaBytes
  err error => say "got an error: $err"
  bytes fuzion.java.Array =>
    say "string has {bytes.count} bytes: $bytes"
    javaString2 := java.lang.String.new bytes 6 bytes.count-6                # create Java string from bytes subset,
    say "Hello "+javaString2                                                 # append Java string to Fuzion string and print it

C back-end

Fuzion now has a back-end that produces C source code to be compiled to machine code using clang and LLVM.

Fuzion safety

A main goal of Fuzion is to provide a development tool for safety-critical applications. Fuzion brings a number of features that address safety issues at different levels:

• Language features

  • static typing
  • language simplicity
  • pre- and post-conditions for design by contract
  • no wrap-around for standard operations +, -, *, /, etc.
  • mutability restricted to local contexts

• Run-time features

  • dynamic checks where static checks are not sufficient
  • (real-time) garbage collection

• Environment features

  • static linking to specific library versions
  • static analysis tools
  • no dynamic code loading
  • simple intermediate representation, simpler tools

Conclusion and Next Steps

The Fuzion language definition and implementation are far from stable, but are getting closer to become useful. Big improvements come from the ability to pre-compile modules and from the foreign language interface for Java, which makes a giant code base accessible for Fuzion applications to build on.

Additionally, new projects such as the language server implementation for Fuzion by Michael Lill help by integrating Fuzion support in popular IDEs and editors.

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
• 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!

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.

This talk will explain how Java's concepts such as classes, interfaces, methods, constructors, packages, etc. are mapped to the single concept of a Fuzion feature. The fzjava tool will be explained that provides Fuzion interfaces to Java libraries. Finally, the Fuzion interpreter and a (planned) Java byte-code back-end are presented.

Introduction

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 language 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.

Fuzion Feature Declarations

A Fuzion feature has a name, similar to the name of a class or a function. The main operation that can be performed on a feature is a feature call. The constituents of a feature declaration are as follows:

Formal Arguments

Features may have a list of formal arguments, which are themselves features implemented as fields. On a call to a feature with formal arguments, actual arguments have to be provided to the call, unless the list of formal arguments is empty.

Feature Result

The result of a feature call is an instance of the feature. Alternatively, a feature may declare a different result type, then it must return a value of that type on a call.

Closures

Features are nested, i.e., every feature is declared within the context of an outer feature. The only exception is the universe, which is the outermost feature in Fuzion. A feature can access features declared in its outer feature or, recursively, any outer feature of these outer features. This means, a feature declaration also defines a closure of the feature and its context.

When calling a feature f1 declared as an inner feature of f2, the call must include a target value which is the result of a call to f2, e.g., f2.f1.

Generics

Features may have generic type parameters. E.g. a feature declaration may leave the actual type used within that feature open and to be defined by the user of the feature.

The list of generic type parameters may be open, i.e., the number of actual generic type parameters is not fixed at feature declaration. This turns out to be useful in the declaration of choice types and functions as explained below.

Inheritance

Fuzion features can inherit from one or several other features. When inheriting from an existing features, all inner features of the parent automatically become inner features of the heir feature. It is possible to redefine inherited features. In particular, when inheriting from a feature with abstract inner features, one can implement the inherited abstract features.

A redefinition of an inherited feature may implement an inherited feature as a routine or as a field. An inherited feature that is implemented as a field, however, cannot be redefined as something else since fields might be mutable.

Inheritance may result in conflicts. An example would be two features with the same name that are inherited from two different parents. In this case, the heir must resolve the conflict either by redefining the inherited features and providing a new implementation or by renaming the inherited features resulting in two inner features in the heir feature.

Inheritance and redefinition in Fuzion does not require dynamic binding. By default, the types defined by features are value types and no run-time overhead for dynamic binding is imposed by inheritance.

A Contract

A feature may declare a contract that specifies what the features does and under which conditions the feature may be called.

An implementation

Features must have one of the following implementations

• a routine is a feature implementation with code that is executed on a call

• a field is a memory slot that stores a value and whose contents are returned on a call

• an abstract feature has no implementation and cannot be called directly, but can be implemented by heir features

• an intrinsic feature is a low-level feature implemented by the compiler or run-time system, e.g., the infix + operator to add two 32-bit integer values may be an intrinsic operation.

A feature implemented as a routine can contain inner feature declarations.

Feature examples

Here is an example that declares a feature point that functions similar to a struct or record in other languages:

point(x, y i32) is # empty
p1 := point 3 4
say "p1.x is {p1.x}"    # will print "p1.x is 3"
say "p1.y is {p1.y}"    # will print "p1.y is 4"

The next example shows a feature base that provides an inner feature plus that adds its argument to the value passed to the enclosing base:

base(v i32) is
  plus(w i32) => v + w

b1 := base 30
b2 := base 100
say (b1.plus 23)    # will print "53"
say (b2.plus 23)    # will print "123"

Fuzion FZJava Tool

Fuzion provides a tool fzjava that takes a Java module file and converts it into Fuzion features. In the spirit of Fuzion, Java's packages, classes, interfaces, methods, constructors, static methods and fields are all converted into Fuzion features. Java methods that may throw an exception are converted into features resulting in a choice type that is either the exception type or the result type of that method.

A few intrinsic functions in the Java interpreter back-end use Java's reflection API to access the corresponding Java code.

Basic approach

The FZJava tool converts each Java class into three Fuzion Features. Say you have a Java class as follows

package x.y;
class MyClass
{
  MyClass(String arg)
  {
   ...
  }
  void myMethod()
  {
  }
  void myStaticMethod()
  {
  }
}

This will be converted into a Fuzion feature x.y.MyClass that may not be instantiated directly:

Java.x.y.MyClass(redef forbidden void) ref : Java.java.lang.Object(forbidden), fuzion.java.JavaObject(forbidden) is

  unit myMethod is
    ...

This feature defines a Fuzion type x.y.MyClass and contains wrappers for the instance methods. It is, however, not permitted to directly create instances of this feature, which is ensured the forbidden parameter of type void (which makes this feature 'absurd', it cannot be called directly since void values cannot be created).

Additionally, a Fuzion feature containing features for static methods and constructors is generated as follows:

Java.x.y.MyClass_static is

  new(arg string) is
    ...

  myStaticMethod is
    ...

This Feature defines a unit type. Finally, a Fuzion feature returning an instance of this unit type is generated for convenience

Java.x.y.MyClass => x.y.MayClass_static

With this, the following code can be used to create an instance of MyClass within Fuzion and call myMethod and myStaticMethod of this class:

o := Java.x.y.MyClass.new "test"
o.myMethod
Java.x.y.MyClass.myStaticMethod

The counterpart to import a Java class in Fuzion would be to declare a field and assign the class' unit type value to it, i.e., the code above could be simplified as

MyClass := Java.x.y.MyClass
o := MyClass.new "test"
o.myMethod
MyClass.myStaticMethod

or even

mc := Java.x.y.MyClass
o := mc.new "test"
o.myMethod
mc.myStaticMethod

using mc as an alias of Java.x.y.MyClass. Note that since the value of field mc is a unit type, this assignment or any accesses of mc will not execute any code at runtime.

Small Example

Here is a example how Java code can be used from Fuzion:

javaString := java.lang.String.new "Hello Java 🌍!"                          # create Java string, type Java.java.lang.String
javaBytes  := javaString.getBytes "UTF8"                                     # get its UTF8 bytes, type is fuzion.java.Array<i8>
match javaBytes
  err error => say "got an error: $err"
  bytes fuzion.java.Array =>
    say "string has {bytes.count} bytes: $bytes"
    javaString2 := java.lang.String.new bytes 6 bytes.count-6                # create Java string from bytes subset,
    say "Hello "+javaString2                                                 # append Java string to Fuzion string and print it

Web Server Example

The following code shows how Java APIs can be used to create a minimalistic web server in Fuzion.

webserver is

   # declare short hands to access Java net and io packages
   net := Java.java.net
   io  := Java.java.io

   # open socket
   port := 8080
   serversocket := net.ServerSocket.new port
   match serversocket
     err error => say "#### $err ####"
     ss Java.java.net.ServerSocket =>

       for n in 1.. do
         say "accepting connections to localhost:$port"

         match accept
           unit      => say "ok."
           err error => say "#### $err ####"

         accept outcome<unit> is
           # accept and handle connection
           s := serversocket.accept?
           input  := io.BufferedReader.new (io.InputStreamReader.new s.getInputStream?)
           output := io.DataOutputStream.new s.getOutputStream?

           req := read?
           say "got request ({req.byteLength} bytes): $req"
           if req.startsWith "GET "
             (send200 "<html>Hello Fuzion $n!</html>")?

           # close streams
           input.close?
           output.close

           # helper to read request
           #
           read outcome<string> is
             for
               r := "", "$r$s\n"
               s := input.readLine?
               ready := input.ready?
             until s = "" || !ready
               r

           # helper to send data in HTTP response with status 200
           #
           send200(data string) outcome<unit> is
             output.writeBytes ( "HTTP/1.1 200 OK\n"
                               + "Connection: close\n"
                               + "Server: Fuzion demo WebServer v0.01\n"
                               + "Content-Length: " + data.byteLength + "\n"
                               + "Content-Type: text/html\n"
                               + "\n"
                               + data)?

Java methods that may result in an exceptions are represented by Fuzion features that result in the type outcome<T> where T is the Fuzion type corresponding to the Java result type of the method. outcome is a union type that may be either error, which wraps the Java exception, or the actual result type T.

Java methods that result in void are mapped to Fuzion features that result in unit, or, outcome<unit> in case the method has any declared exception.f

Fuzion Interpreter

Fuzion currently supports two back-ends: An interpreter implemented in Java and running on top of OpenJDK and a C code generator implemented in Java using clang to create machine code.

The goal of the interpreter was to quickly obtain a way to execute Fuzion applications. Performance was not the main concern. The interpreter operates directly on Fuzion's abstract syntax tree.

For better performance, a byte-code back-end is planned that will operate on Fuzion's intermediate code instead.

Fuzion Byte-Code Back-End

Similar to Fuzion's C back-end, the byte-code back-end is planned to work on top of Fuzion's intermediate code.

Fuzion intermediate code

Fuzion uses intermediate files during different stages of compilation: module files that contain library code, application files for whole applications and Fuzion intermediate representation files that serve as input to the back ends.

Fuzion uses a simple intermediate code to represent pre-compiled modules and whole applications. This intermediate code serves as the input for static analysis tools, optimizers and for different back-ends that produce executable applications. The goal in the design of the intermediate file format was high performance and simplicity for tools using this code.

The intermediate code is a binary format containing features and types in a way that may be mapped to memory and used directly, so overhead of parsing this format into an in-memory representation is avoided. In particular, if only parts of a pre-compiled module are used by an application, there is no need to read and unpack parts of the module intermediate representation that are not used.

For features containing code, a very simple stack-based format is used. There are currently only ten different instructions:

* Unit -- produce a value of unit type
* Current -- produce the current instance as a value
* Constant -- produce a constant value
* Assign -- perform an assignment to a field
* Call -- perform a call to a given feature
* Tag -- convert a value into a tagged value of a choice type
* Match -- match a choice type
* Box -- convert a value type to a ref type
* Unbox -- extract the value from a ref type
* Pop -- drop the top element from the stack

The intermediate code uses indices to refer to features and types within intermediate files. This means that lookup is very efficient, but it also means that a change in a library module requires recompilation of all dependent modules. Any incompatibilities would be found at compile time instead of resulting in something like Java's IncompatibleClassChangeError at run-time.

Instance Implementation

Fuzion instances should be mapped directly to instances of Java classes generated for the corresponding features. Fuzion fields should be mapped to Java fields and Fuzion routines to Java methods.

Fuzion instances that are accessed only locally by their defining features code, i.e., they do not live longer than their code is executed and they are not passed to any other features, might be optimized and implemented as Java methods using local variables instead of fields.

Call Implementation

Fuzion's support multiple inheritance similar to Eiffel. Java support multiple inheritance only for interfaces, so one way to implement dynamic binding in calls would be to define interfaces for every Fuzion feature and use the JVM's invokeinterface byte-code for calls.

A more flexible alternative might be to use invokedynamic to implement dynamic dispatch, but this will likely result in higher overhead compared to highly optimized invokeinterface implementations.

Conclusion and Next Steps

The Fuzion language definition and implementation are far from stable, but are getting closer to become useful. Big improvements come from the ability to pre-compile modules and from the foreign language interface for Java, which makes a giant code base accessible for Fuzion applications to build on.

Additionally, new projects such as the language server implementation for Fuzion by Michael Lill help by integrating Fuzion support in popular IDEs and editors.

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
• 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!

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.

This talk will focus on Fuzion's aspects related to safety-critical software development. A fundamental idea of Fuzion is to provide a simple language at a high level of abstraction and move implementation decisions from the developer to the compiler. To enable this, the language defines a simple but powerful intermediate representation for static analysis tools to operate on.

Furthermore, pre- and post-conditions for design-by-contract are provided in a way that enables different levels of verification: static analysis as well as dynamic checks at different levels from safety to debugging.

Fuzion does not support exceptions, a run-time error has to be part of the result of a call and must be checked explicitly. Fuzion does not support dynamic loading of code. Numeric operations such as 'infix +' check for overflow.

Fuzion applications consist of a set of library modules and a main modules. Modules are verified for correctness individually as well as whole applications. This is possible since dynamic loading of code is not supported.

Introduction

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 language 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.

Fuzion Feature Declarations

A Fuzion feature has a name, similar to the name of a class or a function. The main operation that can be performed on a feature is a feature call. The constituents of a feature declaration are as follows:

Formal Arguments

Features may have a list of formal arguments, which are themselves features implemented as fields. On a call to a feature with formal arguments, actual arguments have to be provided to the call, unless the list of formal arguments is empty.

Feature Result

The result of a feature call is an instance of the feature. Alternatively, a feature may declare a different result type, then it must return a value of that type on a call.

Closures

Features are nested, i.e., every feature is declared within the context of an outer feature. The only exception is the universe, which is the outermost feature in Fuzion. A feature can access features declared in its outer feature or, recursively, any outer feature of these outer features. This means, a feature declaration also defines a closure of the feature and its context.

When calling a feature f1 declared as an inner feature of f2, the call must include a target value which is the result of a call to f2, e.g., f2.f1.

Generics

Features may have generic type parameters. E.g. a feature declaration may leave the actual type used within that feature open and to be defined by the user of the feature.

The list of generic type parameters may be open, i.e., the number of actual generic type parameters is not fixed at feature declaration. This turns out to be useful in the declaration of choice types and functions as explained below.

Inheritance

Fuzion features can inherit from one or several other features. When inheriting from an existing features, all inner features of the parent automatically become inner features of the heir feature. It is possible to redefine inherited features. In particular, when inheriting from a feature with abstract inner features, one can implement the inherited abstract features.

A redefinition of an inherited feature may implement an inherited feature as a routine or as a field. An inherited feature that is implemented as a field, however, cannot be redefined as something else since fields might be mutable.

Inheritance may result in conflicts. An example would be two features with the same name that are inherited from two different parents. In this case, the heir must resolve the conflict either by redefining the inherited features and providing a new implementation or by renaming the inherited features resulting in two inner features in the heir feature.

Inheritance and redefinition in Fuzion does not require dynamic binding. By default, the types defined by features are value types and no run-time overhead for dynamic binding is imposed by inheritance.

A Contract

A feature may declare a contract that specifies what the features does and under which conditions the feature may be called.

An implementation

Features must have one of the following implementations

• a routine is a feature implementation with code that is executed on a call

• a field is a memory slot that stores a value and whose contents are returned on a call

• an abstract feature has no implementation and cannot be called directly, but can be implemented by heir features

• an intrinsic feature is a low-level feature implemented by the compiler or run-time system, e.g., the infix + operator to add two 32-bit integer values may be an intrinsic operation.

A feature implemented as a routine can contain inner feature declarations.

Feature examples

Here is an example that declares a feature point that functions similar to a struct or record in other languages:

point(x, y i32) is # empty
p1 := point 3 4
say "p1.x is {p1.x}"    # will print "p1.x is 3"
say "p1.y is {p1.y}"    # will print "p1.y is 4"

The next example shows a feature base that provides an inner feature plus that adds its argument to the value passed to the enclosing base:

base(v i32) is
  plus(w i32) => v + w

b1 := base 30
b2 := base 100
say (b1.plus 23)    # will print "53"
say (b2.plus 23)    # will print "123"

Design-by-Contract

Fuzion features can be equipped with pre- and post-conditions to formally document the requirements that must be met when a feature is called and the guarantees given by a feature. An example is a feature that implements a square root function for 32-bit integers:

sqrt(a i32) i32

pre
  safety: a >= 0
post
  debug: result * result <= a,
  debug: (result + 1) > a / (result + 1),
  debug: result >= 0

is

if a == 0
  0
else
  for
    last := 0, r
    r    := 1, (last +^ a / last) / 2         # +^ performs saturating addition
  until r == last

In this case, the function defines the pre-condition that its argument 'a' is non-negative. A call of this function with a negative value will result in a run-time error. On the other hand, its post-conditions make a clear statement about the result: The result will be the largest value that, when squared, is less than or equal to 'a'.

Checking Pre- and Post-conditions

Pre- and post-conditions can be classified for different purposes. Default qualifiers provided in the standard library are

safety

This qualifier protects pre-conditions that are required for the safety of an operation.

An example is the index check pre-condition of the intrinsic operation to access an element of an array: Not performing the index check would allow arbitrary memory accesses and break the application's safety.

This qualifier should therefore never be disabled unless you are running code in an environment where performance is essential and safety is irrelevant.

debug, debug(n)

This qualifier is generally for debugging, it is set iff debugging is enabled or enabled at the given level, respectively..

pedantic

This qualifier is for conditions that a pedantic purist would require, that otherwise a more relaxed hacker would prefer to do without.

analysis

Qualifier for conditions that are generally not reasonable as run-time checks, either because they are prohibitively expensive or even not at all computable in this finite universe. These conditions may, however, be useful for formal analysis tools that do not execute the code but perform techniques such as abstract interpretation or formal deduction to reason about the it.

Additional user defined qualifiers may be added, any expression resulting in a 'bool' can be used.

Run-time checks for pre- and post-conditions can be enabled or disabled for each of these qualifiers (except for 'analysis', which is always disabled). This gives a fine-grain control over the kind of checks that are desired at run-time. Usually, one would always want to keep safety checks enabled in a system that processes data provided from the outside to avoid vulnerabilities such as buffer overflows. However, in a closed system like a rocket controller, it might make sense to disable checks since a run-time error would mean definite loss of the mission, while an unexpected intermediate value may still result in a useful final result of a calculation.

Explicit results instead of Exceptions

Instead of exceptions that provide an alternative path for a function to return, Fuzion requires all functions to return a result. To indicate failure, the generic result type 'outcome' is provided.

outcome is a choice type that represents the result of a routine that may either produce something useful or fail producing an error condition.

Here is a small example of using an outcome result

getData (u User, t Type) outcome<data> is

if u.allowedToAcces T
  (readFile t.fileName)?
else
  error "user $u not allowed to access $t"

readFile (n string) outcome<data> is

if dataExists n
  readData n
else
  error "data $t not available"

A user of this code when would have to explicitly unwrap the read data as follows

o := getData user type match o

d data  => say "success: $d"
e error => say "*** error $e"

Fuzion Modules

Modules in Fuzion are collections of Fuzion features that form a library to be used by other modules. Modules may define a main entry point, such that they can be used to build applications.

The Fuzion front end performs static code analysis at the module level. This means that any features exported by a module are save to be used in different contexts by other modules. This includes static checking of the following aspects:

Field Initialization

In Fuzion, the front end ensures that all fields are assigned an initial value. There is no default initial value for uninitialized fields and there is no means to access an uninitialized fields, as there is, e.g., for final fields in Java.

Instead, it is checked that whenever an instance containing a field becomes accessible outside of the feature declaring that field, the call chain is analyzed to ensure it may not contain any accesses to the field. In particular, if an instance may become visible outside of the module, no uninitialized field may be accessible by any exported features of that module.

Function Purity

The result of any feature visible to the outside must be independent of state modifiable by other exported features and must not itself modify state that may affect the result of other exported features. This purity will allow optimizations such as memoization or lazy evaluation common in functional languages.

Nevertheless, a pure function may use mutable fields, e.g., to store intermediate results during its calculations. If the mutable field's life span is limited to the call of the exported feature and the field is not accessed by any other exported feature, mutation does not make a function impure.

Race Freedom

Closely related to function purity is race freedom: Any exported feature is checked to be safe to be called in a threaded environment without causing data races. There are no explicit locks in Fuzion, so there is no danger of deadlocks due to nested locking.

Immutability

Fuzion encourages the use of immutable data by simple syntax for the declaration of immutable fields. Also, the use of tail calls for loops automatically converts iterator variables used in that loop into immutable variables with a life span of a single loop iteration.

Since immutability is essential to ensure correctness of parallel execution within threads that do not rely on locks or similar synchronization mechanisms, Fuzion's analyzer will verify that data shared between threads is immutable.

The standard library has been designed to provide immutable data types. Nevertheless, there are mutable types such as 'marray', which provides a mutable array. These, however, should be used for local calculations only, escape analysis will ensure that no accesses to mutable types occur from outside the code manipulating the state.

Memory Management

Fuzion to a large extend relies on static analysis to reduce memory management overhead. Instances are by default value instances that do not require heap allocation. Furthermore, immutability in many cases avoids the need to keep a shared copy on the heap. For dynamic calls, heap allocation and dynamic binding overhead is avoided by specialization of calls.

Only for those instances for which all of these optimizations would fail, in particular instances shared between threads or long-lived instances with mutable fields, heap allocation will be required. Memory allocated on the heap will be reclaimed by a real-time garbage collector.

Fuzion Thread Safety

Static analysis at module and application level ensure that mutable data is not shared between threads in Fuzion. However, there must be means for threads to communicate, e.g., for the result of a thread to become available to other threads. How this will be done in Fuzion is still open, thread safe libraries such as thread-safe queues between might be provided here.

Conclusion and Next Steps

I hope Fuzion shows some interesting ideas how to approach the development of safety-critical software.

The Fuzion language definition and implementation are far from stable, but are getting closer to become useful. Currently, two execution options for Fuzion are available: An interpreter implemented in Java and a back-end that compiles to C code. A tool to interface Java code is available for the interpreter.

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
• 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!

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 implementation 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 runtime checks.

The talk will explain Fuzion's motivation and present its main concepts, feature declarations and feature calls. It will not go into details of the syntax, but present Fuzion's approach to immutability, memory management and type inference.

Introduction

Many current programming language 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 for nesting of 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 for all the rest.

Fuzion Feature Declarations

A Fuzion feature is has a name, similar to the name of a class or a function. The main operation that can be performed on a feature is a feature call. The constituents of a feature declaration are as follows:

Formal Arguments

Features may have a list of formal arguments, which are themselves features implemented as fields. On a call to a feature with formal arguments, actual arguments have to be provided to the call, unless the list of formal arguments is empty.

Feature Result

The result of a feature call is an instance of the feature. Alternatively, a feature may declare a different result type, then it must return a value of that type on a call.

Closures

Features are nested, i.e., every feature is declared within the context of an outer feature. The only exception is the universe, which is the outermost feature in any Fuzion system. A feature can access features declared in its outer feature or, recursively, any outer feature of these outer features. This means, a feature declaration also declares a closure of the feature and its context.

When calling a feature f1 declared as an inner feature of f2, the call must include a target value which is the result of a call to f2, e.g., f2.f1.

Generics

Features may have generic type parameters. E.g. a feature declaration may leave the actual type used within that feature open and to be defined by the user of the feature.

The list of generic type parameters may be open, i.e., the number of actual generic type parameters is not fixed at feature declaration. This turns out to be useful in he declaration of choice types or functions explained below.

Inheritance

Fuzion features can inherit from one or several other features. When inheriting from an existing features, all inner features of the parent automatically become inner features of the heir feature. It is possible to redefine inherited features. In particular, when inheriting from a feature with abstract inner features, one can implement the inherited abstract features.

A redefinition of an inherited feature may implement an inherited feature as a routine or as a field. An inherited feature that is implemented as a field, however, cannot be redefined.

Inheritance may result in conflicts, e.g. if two features with the same name are inherited from two different parents. In this case, the heir must resolve the conflict either by redefining the inherited features and providing a new implementation or by renaming the inherited features resulting in two inner features in the heir feature.

Inheritance and redefinition in Fuzion does not require dynamic binding. By default, the types defined by features are value types and no run-time overhead for dynamic binding is imposed by inheritance.

Contract

A feature may declare a contract that specifies what the features does and under which conditions the feature may be called. This will be handled in more detail below in the section Design by Contract.

An implementaton

Features must have one of the following implementations

• a routine is a feature implementation with code that is executed on a call

• a field is a memory slot that stores a value and whose contents are returned on a call

• an abstract feature has no implementation and cannot be called directly, but can be implemented by heir features

• an intrinsic feature is a low-level feature implemented by the compiler or run-time system, e.g., the infix + operator to add two 32-bit integer values may be an intrinsic operation.

A feature implemented as a routine can contain inner feature declarations.

Feature examples

Here is an example that declares a feature point that functions similar to s struct or record in other languages:

point(x, y i32) is # empty
p1 := point(3, 4)
stdout.println("p1.x is " + p1.x)    # will print "p1.x is 3"
stdout.println("p1.y is " + p1.y)    # will print "p1.y is 4"

The next example show a feature base that provides an innver feature plus that adds its argument to the value passed to the enclosing base:

base(v i32) is
  plus(w i32) => v + w

b1 := base(30)
b2 := base(100)
stdout.println(b1.plus(23))    # will print "53"
stdout.println(b2.plus(23))    # will print "123"

Features and Types

A feature declaration implicitly declares a type of its instances. In the example above, the feature declaration

point(x, y i32) is

declares the type point that can be used to declare a feature of field type, so we could, e.g., declare a new feature that takes an argument of type point:

draw(p point) is
  drawPixel(p.x, p.y)

Syntactic Sugar

Fuzion's grammar adds syntactic sugar that simplifies the developers work by making code more readable and easier to write. However, internally, this syntactic sugar is converted into feature declarations and feature calls. Consequently, only the front-end of the language implementation is affected, the later phases that optimize, analyse, compiler, interpret, etc. the code are not affected by this.

Loops

Fuzion has a very powerful syntax for loops, an overview is given at flang.dev. However, loops are purely syntactic sugar and get translated into feature declarations and calls. This has important impact for the immutability of variables as will be explained below. Since the compiler performs optimizations for tail recursive calls, the resulting performance will be equal to inline loops.

Choice Types

Fuzion provides choice types (also called union types, sum types, tagged types, co-product types in other languages). A choice type is a feature declared in the standard library that has an open list of generic parameters for a number of actual types a field of this choice type may hold.

The simplest example of a choice type is the type bool, which is a choice between types TRUE and FALSE. TRUE and FALSE are themselves declared as features with no state, i.e., no fields containing any data.

Another example for a choice type from the standard library is Option<T>, which is a generic choice type that either holds a value of type T or nil, while nil is a feature with no state declared in the standard library.

A match statement can be used to distinguish the different options in a choice type, e.g.,

mayBeString Option<string> = someCall()
match mayBeString
  s String => stdout.println(s)
  _ nil    => stdout.println("no string")

The ? operator allows for more compact syntax, the following code is equivalent

stdout.println(mayBeString ? s | "no string")

while a single ? may be used to return immediately from the current feature in case of an error

stdout.println(mayBeString?)    # return nil immediately if mayBeString is nil

which works only within a feature that may return the unhandled types as a result.

First-class Function

Another open generic type in the standard library is Function. This is a feature that declares an abstract inner feature call. Syntactic sugar in the Fuzion front-end enables inline declaration of functions as shown in this example:

fun_example is

  eval(msg string, f fun (i32) i32) is
    for
      x in 0..3
      m := msg, ", "
    do
      y := f(x)
      stdout.print("" + m + "f(" + x + ") = " + y)
    stdout.println

  eval("f(x) = 2*x:   ", fun (x i32) => 2*x)
  eval("f(x) = x*x:   ", fun (x i32) => x*x)
  eval("f(x) = x*x*x: ", fun (x i32) => x*x*x)

which results in

f(x) = 2*x:   f(0) = 0, f(1) = 2, f(2) = 4, f(3) = 6
f(x) = x*x:   f(0) = 0, f(1) = 1, f(2) = 4, f(3) = 9
f(x) = x*x*x: f(0) = 0, f(1) = 1, f(2) = 8, f(3) = 27

Internally, function declarations are implemented as inner features. Since a feature declaration defines a closure, a function declarations also defines the function closure.

Tuples

Tuples in Fuzion are provided by a generic standard library feature Tuple. The open list of generic parameters specifies the types of each element and their number.

Here is an examples of a feature that splits a 32-bit unsigned integer v into four bytes returned as a tuple:

bytes(v u32) => ((v >> 24) ,
                 (v >> 16) & 255,
                 (v >>  8) & 255,
                 (v      ) & 255)

A caller might directly decompose this tuple when calling bytes:

(b0, b1, b2, b3) := bytes(1234567890)

stdout.println("Bytes: " + b0 + " " + b1 + " " + b2 + " " + b3 + " ")

References

By default, Fusion types have value semantics. This means that a value cannot be assigned to a field whose type is a parent type of the value's type. However, a value can be marked as a reference by adding the keyword ref. Then, any value of a heir type can be assigned to this field.

An example is the argument of the println feature, which is a ref to an Object. Its implementation is shown here:

public println(s ref Object) void is
  for c in s.asString.asBytes do
    write(c)
  println

Object is the implicit parent feature of all features that do not explicitly declare a parent. Consequently, any value can be assigned to the argument s of println.

Object declares some basic features such as asString, which creates a string representation of the Object. Redefinitions of these functions in heir features such as integer provide useful string representations of the objects.

Note that the ref keyword does not require that the implementation would allocate the value passed as a ref on the heap and it also does not imply that we will have dynamic type information and dynamic binding at run-time. Instead, these overheads can be avoided by stack allocation and specialization.

Design by Contract

Fuzion features can be equipped with pre- and post-conditions to formally document the requirements that must be met when a feature is called and the guarantees given by a feature. An example is a feature that implements a square root function:

sqrt(a i32) i32
  pre
    a >= 0
  post
    result * result <= a,
    (result + 1) > a / (result + 1),
    result >= 0
is
  if a == 0
    0
  else
    for
      last := 0, r
      r    := 1, (last +^ a / last) / 2
    until r == last

In this case, the function defines the pre-condition that its argument a is non-negative. A call of this function with a negative value will result in a run-time error. On the other hand, its post-conditions make a clear statement about the result: The result will be the largest value that, when squared, is <= a.

Checking Pre- and Post-conditions

Pre- and post-conditions can be classified for different purposes. Default qualifiers provided in the standard library are

• safety

  This qualifier protects pre-conditions that are required for the safety of an operation.

  An example is the index check pre-condition of the intrinsic operation to access an element of an array: Not performing the index check would allow arbitrary memory accesses and typically would break the applications safety.

  This qualifier should therefore never be disabled unless you are running code in an environment where performance is essential and safety is irrelevant.

• debug

  This qualifier is generally for debugging, it is set iff debugging is enabled.

• debug(n)

  this qualifier is specific for enabling checks at a given debug level, where higher levels include more and more expensive checks.

• pedantic

  This qualifier is for conditions that a pedantic purist would require, that otherwise a more relaxed hacker would prefer to do without.

• analysis

  This is a qualifier for conditions that are generally not reasonable as run-time checks, either because they are prohibitively expensive or even not at all computable in this finite universe. These conditions may, however, be very useful for formal analysis tools that do not execute the code but perform techniques such as abstract interpretation or formal deduction to reason about the code.

Run-time checks for pre- and post-conditions can be enabled or disabled for each of these qualifiers. This gives a fine-grain control over the kind of checks that are desired at run-time. Usually, one would always want to keep safety checks enabled in a system that processed data provided from the outside to avoid vulnerabilities such as buffer overflows. However, in a closed system like a rocket controller, it might make sense to disable checks since a run-time error would mean definite loss of the mission, while an unexpected intermediate value may still result in a useful final result of a calculation.

Immutability in Fuzion

Fuzion encourages the use of immutable data by simple syntax for the declaration of immutable fields. Also, the use of tail recursion for loops automatically converts index variables used in that loop into immutable variables with a life span of a single loop iteration.

Since immutability is essential to ensure correctness of parallel execution within threads that do not rely on locks or similar synchronization mechanisms, Fuzion's analyser will require data that is shared between threads to be immutable.

Memory Management in Fuzion

Fuzion to a large extend relies on static analysis to reduce memory management overhead. Instances are by default value instances that do not require heap allocation. Furthermore, immutability in many cases avoids the need to keep a shared copy on the heap.

For dynamic calls, heap allocation and dynamic binding overhead is avoided by specialization of calls.

Only for those instances for which all of these optimizations would fail, in particular instances shared between threads or long-lived instances with mutable fields, heap allocation will be required.

Memory allocated on the heap will be reclaimed by a real-time garbage collector, an example means to provide this is the real-time GC presented at ISMM'10: Concurrent, parallel, real-time garbage-collection.

Type Inference

Fuzion is a statically types language. However, type inference is used to avoid the need to explicitly provide types for fields, for function results and for actual generic parameters. Furthermore, the type of constant numeric expression is propagated from target the expression's value is assigned to.

For the type inference for fields and function results, a dedicated phase in Fuzion's front-end lazily determines the types of expressions. This phase also detects possible cycles in the type inferencing and flags these as errors if encountered.

For interference of actual generic parameters, the types of actual arguments passed the the generic feature are used. This, however, works only for generic features that use the generic types within their formal argument lists.

Fuzion Implementation

The Fuzion implementation consists of several, independent parts from a front-end performing parsing and syntax-related tasks and creates the intermediate representation (IR), via a middle-end that collects the part of a Fuzion application, to the optimizer and several back-ends.

Fuzion IR

Fuzion has very simple intermediate representation. The dominant instruction is a feature call. The only control structure is a conditional (if) operation. Loops are replaced by tail recursive feature calls, so there is no need in the compiler or analysis tools to handle loops as long as (tail-) recursion is provided.

The largest part of a compiler back-end consists of providing target-platform specific implementations for all intrinsic features declared in the Fuzion standard library.

Fuzion Optimizer

The Fuzion Optimizer modifies the intermediate representation of a Fuzion application. In particular, it determines the life spans of values to decide if they can be stack allocated or need to be heap allocated and it specializes feature implementations for the actual argument types and the actual generic arguments provided at each call.

This means that run-time overhead for heap allocation and garbage collection will be avoided as much as possible, most values can be allocated on the run-time stack. Additionally, run-time type information such as vtables will be required only in very few cases where dynamic binding cannot be avoided. An example is a data structure like a list of some reference type with elements of different actual types that are stored in this list.

Fuzion Back-Ends

Fuzion currently has two back-ends: An interpreter written in Java running on OpenJDK and a back-end creating C source code processed by gcc or clang. It is planned to add further back-ends, in particular for LLVM and Java bytecode.

Next Steps

The Fuzion language definition and implementation is still in an early stage. It is planned to publish a first version of the language and its implementation at FOSDEM 2021. But a lot of work remains to be done, in particular, for Fuzion to be successful, it will need

• a powerful standard library
• additional library modules for all sorts of application needs
• powerful interfaces to other languages such as Java, C, Python, etc.
• highly optimizing back-ends
• IDE integration
• documentation, tutorials
• much more

Also, professional services around Fuzion will be required for acceptance outside the open-source community. The Tokiwa SW GmbH currently leads the development of Fuzion and plans to provide professional services as well.