The Fuzion Language

==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 a single concept of a feature, the language implementation takes care for all the rest. ==Fuzion Features== 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. ===Nesting=== 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 can access the closure provided by its outer features. 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. ===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. ===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. ===Feature examples=== point(x, y i32) is 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" 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" ===Feature 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 whose contents are returned on a call an abstract feature has no implementation an cannot be called directly 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. ===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) ===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. An redefinition of an inherited feature may implement an inherited feature as a routine or as 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 is 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 class. 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. ===Generics=== Features may have generic type parameters. E.g. a feature declaration may leave the actual type used within that feature open an 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. ===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 data. Another examples 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. ===Function Types=== 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) = 2x: f(0) = 0, f(1) = 2, f(2) = 4, f(3) = 6 f(x) = xx: f(0) = 0, f(1) = 1, f(2) = 4, f(3) = 9 f(x) = xxx: f(0) = 0, f(1) = 1, f(2) = 8, f(3) = 27 Internally, function declarations are implemented as inner features. ===References=== By default, Fusion types have value semantics. This means that a value is 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, with 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. ==Design by Contract== Fuzion features can be equipped with pre- and post-conditions to formally document the requirements that must be 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. ==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.