fble-0.5 (2025-07-13,fble-0.4-212-ga8f8ad0f)
Fble is a general purpose functional programming language with support for polymorphism and modularity.
The primary design goals of fble are:
Fble should be as simple a language as possible while still being useful. A simple language will hopefully be simple to specify, simple to learn, simple to understand, simple to program, powerful, and low cost to develop high quality tools for.
Fble should support high performance, low overhead computing. This is achieved by using a static type system and having a very clear performance model that a developer can optimize for.
Fble should be a joy to program in. It should be easy to describe the majority of programs we want to describe, not tediously difficult. To accomplish this, fble allows functions to be declared locally with access to variables in the context where they are declared, and fble supports polymorphic types and functions.
Fble should support programming at scale. That is, namespace control and composition of modules developed by different individual developers or organizations.
Fble is based around the primitive data types of structs, unions, and functions. It is a strongly and statically typed language supporting polymorphic types and values. Recursive types and values are supported through a recursive let construct. Types are treated as another kind of value in fble, which allows us to reuse the constructs of variables, lets, polymorphism, and structs for types in addition to normal values. Additional syntax is provided to make structs suitable for describing and manipulating namespaces.
Data values and the expressions that describe them are strongly typed. A value's type describes the kinds of operations that can legally be performed on that value. Types are used to check that an fble program is well formed statically. Types do not take meaningful part in the dynamic execution of an fble program after it has been statically checked.
Types are themselves treated as data values in fble, which allows us to reuse variables, lets, polymorphism, and structs for types in addition to normal values. This means an expression can be used to describe either a normal value or a type and that types themselves have types.
To ensure all type information is available at compile time, there is a one-to-one mapping between a type and the type of that type. As a consequence, you can determine the value of a type if you know the type of that type.
For example, the boolean value True is a normal value. The type of
True is the type Bool@, which is a union type. Bool@ is a type
value. The type of Bool@ is known only as the type of Bool@,
expressed using the syntax: @<Bool@>. @<Bool@> is also a type
value, and the type of that value is @<@<Bool@>>. If you have an
expression of type @<Bool@>, you know statically that the value of that
expression must be Bool@, so the expression need not be evaluated at
runtime.
Type information is stripped away at runtime. The value of a type at runtime is a special unit value. Without the type information, there is no way to distinguish between the special unit value for different types. For this reason we say types do not take meaningful part in the dynamic execution of an fble program after it has been statically checked, though the special unit value for types may exist at runtime when using an fble native interface.
Kind: basic_normal_kind Kind: basic_type_kind
kind = '%' (* normal_kind *) kind = '@' (* type_kind *)
% @
Kinds are used to classify whether a value is a normal value, a type value, or something else. Using the example in the previous section:
True is a normal value. It is of normal kind.Bool@ is a type value. It is of type kind.@<Bool@> is a type of a type value. It is of higher kind.@<@<Bool@>> is also of higher kind.Kinds are analogous to types in that they describe what operations are supported by a particular value, but they are much more restricted in the operations they allow. A value of normal kind cannot be used where a type is expected, for example. Unlike types, kinds do not act as values and cannot be described using expressions.
The kind of a value is uniquely determined by the type of the value.
It is useful to be able to recognize immediately whether a variable refers
to a normal value, a type value, or something else. For that reason, we
require different namespaces be used for different kinds of values. In the
concrete syntax, names of normal variables are unadorned, while names of
type variables must be followed with the character @. So, for example,
True is a normal value, and Bool@ is a type value.
The @ character is not considered part of the variable, but rather is
an indicator of the namespace of the variable. So, for example 'Foo'@
is a type variable named Foo, and 'Foo@' is a normal variable named
Foo@.
You are not allowed to use a variable to refer to a higher kinded value,
because then using @ in variable names to distinguish between normal
variables and type variables would be insufficient. In practice this should
not be a significant limitation because you should be able to use a type
variable for the value of the type and use the typeof operator to get the
type of the type as needed. For this reason, there is no syntax for
describing a higher kind, though it is possible to describe types and
expressions of higher kind.
Type: typeof (expr : Expr)
type = '@', '<', expr, '>'
@<x>
Evaluates to the type of the expression, without evaluating the expression itself. This is primarily useful for explicitly describing the type of a struct that has type fields.
Runtime is O(1).
Expr: var (name : Name)
expr = name
x
Variables allow data values to be reused multiple times within a program. In conjunction with let expressions, variables allow data values to be used recursively.
Expressions are evaluated in a context that maps variable names to values, along with their types and kinds. The value, type, and kind of the variable expression is the value, type, and kind associated with the variable name in the context.
In general it is legal to declare a new variable with the same name as an existing variable in scope. In this case, the new variable shadows the existing variable for as long as the new variable is in scope. The existing variable is not visible or accessible as long as the new variable is in scope.
The rationale for allowing variables to shadow other variables is for modularity: it allows you to re-use a self-contained block of code in any context. Otherwise self-contained blocks of code could not be reused in contexts that happen to declare a variable with the same name as some variable in the self-contained block.
Runtime is O(log(N)), where N is the number of variables in scope. In the case of delayed evaluation of functions, the number of variables in scope is limited by the number of variables captured by the function when it is created.
Spec: kind_spec (kind : Kind) Spec: type_spec (type : Type) Expr: let (bindings : [(Spec, Name, Expr)]) (body : Expr)
spec = kind spec = type stmt = spec, name, '=', expr, {',', spec, name, '=', expr}, ';', stmt
Int@ x = mul(3, 3); mul(x, x) @ Bool@ = +(Unit@ true, Unit@ false); ...
Let expressions can be used to define local variables that allow values to be reused in multiple places in a program. Let expressions support recursive definitions of variables, which makes it possible to define recursive values.
The let expression is used to define variables. For each binding, a new variable is defined. The value of the variable is the result of evaluating the expression for the variable's binding.
The defined variables are visible in the body of the let expression. To support self and mutually recursive values, the defined variables are also visible in all of the bindings expressions.
While a variable can be referenced in the bindings where the variable is defined, the value of the variable is undefined until after the binding expressions have completed evaluation.
The value of the let expression is the value of its body. The type of the let expression is the type of its body.
When defining a variable, ether a kind or a type can be used to specify the operations supported by the value of the variable.
If a kind is used, the type of the variable is abstract in the bindings expressions. The actual type of the variable will be inferred from its definition for use in the body of the let expression. It is a type error if the kind of the value of the variable is not equal to the kind specified for the variable. As a restriction to ensure type checking is possible, the kind of the variable is treated as a basic kind in the bindings expressions. This restricts the set of recursive types that can be described to ones that the type checker can handle without difficulty. The rationale for requiring the full kind of the variable instead of just whether it is a type or a value, and for requiring the kind of the value be equal to the kind specified for the variable instead of compatible with, is that it helps to document the kinds of values being defined in a machine checkable way.
If a type is used when defining a variable, that type is used for the type of the variable in the binding expressions. It must match the type of the variable inferred from the variable's definition.
It is recommended that a type specifications be preferred over kind specifications for normal values whose types are relatively easy to describe, to better document types for readers of the code.
Recursively defined values must not be vacuously recursive. For example, the following definition is not allowed:
@ T@ = T@; ...
But it is okay to define recursive types and values that involve a constructor somewhere, such as:
@ T@ = +(T@ x);
Vacuously defined types are reported as compile time errors. Vacuously defined values are reported as runtime errors.
Bindings are allowed to define variables with the same name as variables already in scope, thus shadowing the variable already in scope. Except that the variables defined in a single let expression must have distinct names.
Implementations are encouraged to emit warnings for unused variables, with
the convention that no warnings should be produced for variables starting
with _ in their name. This allows the programmer to annotate a variable
as intentionally unused, which is occasionally useful in practice.
Runtime is O(N log(M)) plus the runtimes of the bindings and the runtime of the body, where N is the number of bindings and M is the number of variables in scope.
A variable's value takes up memory for as long as the variable is in scope. Variables are in scope until the body of the let expression has finished evaluation or, as a special case, until the body of the let expression makes a tail recursive call.
Expr: undef (name: Name) (type: Type) (body: Expr)
stmt = type, name, ';', stmt
Bool@ True; @(Bool@, True);
The undef expression evaluates an expression in a context with an undefined value. It allows you to assign a type to a value that will never be used.
The primary intent of the undef expression is to facilitate writing header files for modular compilation of fble programs. In that case, the undef expression allows you to declare a variable or function without a corresponding implementation. See the section on modular compilation for more details.
The type of the expression is the type of the body of the expression. The defined variable is visible in the body of the undef expression. It may be referenced in the body of the expression, but the value of the variable is undefined.
As with let expressions, implementations are encouraged to emit warnings
for unused variables, with the convention that no warnings should be
produced for variables starting with _ in their name.
Runtime is the runtime of evaluating the body of the expression.
A struct value is a grouping of other values. The items of a struct are organized into a finite number of fields. Each field has a name, used to identify the field, and a type, specifying the type of value for that field.
Struct values are constructed by supplying values for all fields of the struct. Individual components of a struct can be accessed by field name.
Struct values can be used for namespaces, by grouping together a collection of types and normal values. Syntax is provided for creating struct values with implicit types to facilitate this use case.
Expr: struct_type (fields : [(Type, Name)])
expr = '*(', [type, name, {',', type, name}], ')'
*() # The Unit type. *(Int@ x, Int@ y) # The type of a pair of ints x, y.
Struct types are considered equal if their fields are equal, including field types, field names, and the order of the fields.
Runtime is O(1).
Expr: struct_value_explicit_type (type : Type) (args : [Expr])
expr = type, '(', [expr, {',', expr}], ')'
Coord@(3, 5)
The type of the struct value is the explicit type provided, which must be a struct type. The number of arguments provided must match the number of fields in the provided type, and the type of each argument must match the type of the field of the struct type in the same position.
The expression is evaluated by evaluating all arguments and creating a struct value with the results. The arguments may be evaluated in any order, sequentially or in parallel.
Runtime is O(N) plus the runtimes of the arguments, where N is the number of arguments.
Expr: struct_value_implicit_type (args : [(Name, Expr)])
expr = '@(', [field_arg, {',', field_arg}] ')'
@(x: 3, y: 5) @(Bool@, True, False, Not: NotInternal)
Allows you to construct a struct value with an implicit type. When defining structs used as namespaces, it is tedious to have to repeat the types of the entities being defined and to worry about what order they are defined in. The anonymous struct value makes it more convenient to define structs used as namespaces.
As a syntactic sugar, if no value for a field is provided, its value is assumed to be the variable with same name as the field. For example, the above example is equivalent to:
@(Bool@: Bool@, True: True, False: False, Not: NotInternal)
The type of the struct value is a struct type with fields defined in the same order as the implicit value struct: the name of the field is the name provided and the type of the field is the type of the argument provided.
The expression is evaluated by evaluating all arguments and creating a struct value with the results. The arguments may be evaluated in any order, sequentially or in parallel.
Runtime is O(N) plus the runtimes of the arguments, where N is the number of arguments.
Expr: struct_access (object : Expr) (field : Name)
expr = expr, '.', name
x.first
Returns the value passed to the struct at the corresponding field position when the struct was constructed.
The object must be a struct value. The field must refer to a field of that struct value. The type of the expression is the type of the field being accessed.
The expression is evaluated by evaluating the object, then accessing its field value.
Runtime is O(log(N)) plus the runtime of the struct object, where N is the number of fields in the struct.
Expr: struct_copy (src : Expr) (args : [(Name, Expr)])
expr = expr, '.@(', field_arg, {',', field_arg}, ')'
Vector@ v = @(x: 1, y: 2, z: 3); Vector@ w = v.@(x: 3); Vector@ a = v.@(x: 3, z: 4);
Allows you to construct a new struct value by copying from an existing struct value. The resulting value has the same type as the source expression. The contents of the new struct value come from the provided arguments as in a struct value implicit type expression; any fields not included in arguments take their values from the source struct value.
In the above example, the definition of w is equivalent to:
Vector@ w = @(x: 3, y: v.y, z: v.z);
The source value must be a struct value. At least one argument must be provided. Arguments must be provided in the same order as the fields in the struct type.
As with implicit type struct values, if no value for a field is provided, its value is assumed to be the variable with same name as the field.
The expression is evaluated by evaluating the source and all arguments and creating a struct value with the results. The arguments may be evaluated in any order, sequentially or in parallel.
For consistency, src is still evaluated even if all fields are provided explicitly.
Runtime is O(N) plus the runtimes of the arguments, where N is the number of fields of the struct.
A union value is a particular value chosen from a group of possible values. The possible choices are organized into a finite number of fields. Each field has a name, used to identify the field, and a type, specifying the type of value for that field.
Union values are constructed by supplying a value for a particular field of the union. The particular value for the union can be accessed by field name, and the union can be used to select among other values and expressions based on the field present in the union value.
Type: union_type (fields : [(Type, Name)])
type = '+(', type, name, {',', type, name}, ')'
+(Unit@ true, Unit@ false)
Union types are considered equal if their fields are equal, including field types, field names, and the order of the fields.
Runtime is O(1).
Expr: union_value (type : Type) (field : Name) (arg : Expr)
expr = type, '(', name, ':', expr, ')'
Maybe@(Just: 3)
The type of the union value is the type provided, which must be a union type. The supplied argument name must be of a field in the union type, and the type of the argument must match the type of that field.
The expression is evaluated by evaluating the argument and creating a union value with the result.
Runtime is O(log(N)) plus the runtime of the arg, where N is the number of fields in the union.
Expr: union_access (object : Expr) (field : Name)
expr = expr, '.', name
x.just
Returns the value passed to the union at the corresponding field position when the union was constructed. Behavior is undefined if the union tag does not match the field being accessed; implementations are encouraged to provide meaningful error messages in this case.
The object must be a union value. The field must refer to a field of that union value. The type of the expression is the type of the field being accessed.
The expression is evaluated by evaluating the object, then accessing its field value.
Runtime is O(log(N)) plus the runtime of the object, where N is the number of fields in the union.
Expr: union_select (condition : Expr) (choices : [(Name, Expr)]) (default : Expr)
expr = expr, '.?(', name, ':', expr, {',', name, ':', expr}, [',', ':', expr], ')' stmt = expr, '.?(', name, ':', expr, {',', name, ':', expr} ')', ';', stmt
mfoo.?(Just: mfoo.Just, Nothing: 3) char.?(a: True, b: True, : False) { char.?(a: True, b: True); False; }
The condition must be a union value. Returns the value of the choice selected by the tag of the condition, without causing any other choices to be evaluated. The type of all choices must be the same.
If no default is provided, a choice must be present for each field of the condition's union type. If a default is provided, the default value will be used for any fields not explicitly listed. The fields must be listed in the same order as they are declared in the union type, regardless of whether or not a default value is provided. At least one non-default choice must be provided.
A default branch may be specified even if all fields have explicit branches. This allows new fields to be added to the union type, defaulting to the default branch instead of having to update all union select expressions on that type. Any errors in compilation of the default branch are considered errors in the program, even if the default branch is unused.
The expression is evaluated by evaluating the condition, then evaluating the choice selected by the condition. No other choices are evaluated.
Runtime is O(log(N)) plus the runtimes of the condition and selected argument, where N is the number of fields in the union.
The stmt form of syntax is an alternate syntax to reduce syntactic overhead of nested union select expressions. In this syntax the body of the default branch is specified in the statement following the union select.
For example, the following union select expression:
x.?( true: y.?( true: A, : B), false: y.?( true: C, : D));
Is equivalent to the following statement based form:
{
x.?(true: { y.?(true: A); B; });
y.?(true: C);
D;
}
A function is a mapping from an argument value to a result value. The argument has a name, used to identify the argument in the body of the function, and a type, specifying the type of value that can be supplied for the argument. A function has a return type, specifying the type of value that will result when applying the function.
Functions are described using the fble expression language. A function can be applied to an argument of appropriate type to produce a value with the return type of the function. Syntactic sugar is provided to make it easier to describe multi-argument functions.
Type: func_type (arg : Type) (return : Type)
block = '(', type, {',', type}, ')', block
(Int@) { Bool@; } (Int@) { (Int@) { Bool@; }; } (Int@)(Int@) { Bool@; } (Int@, Int@) { Bool@; }
The function type describes the type of a function value by specifying the function's argument and return types.
Function arguments can be any kind of value, including types, structs, unions, or functions.
Two function types are equal if their argument and return types are equal.
The concrete syntax allows you to specify multiple arguments in a function type. This is syntactic sugar for nested single argument function types. For example, the following two expressions describe the same type:
(a, b) { c; }
(a) { (b) { c; }; }
Runtime is O(1).
Expr: func_value (arg : (Type, Name)) (body : Expr)
block = '(', type, name, {',', type, name}, ')', block
(Bool@ a) { a.?(true: 1, false: 0); } (Bool@ a)(Bool@ b) { a.?(true: b, false: False); } (Bool@ a, Bool@ b) { a.?(true: b, false: False); }
The function value expression is used to describe a function value given the argument and the body of the function. The return type of the function is inferred to be the type of the body of the function. The argument name chosen when defining a function has no effect on the type of the function.
Implementations are encouraged to emit warnings for unused arguments, with
the convention that no warnings should be produced for arguments starting
with _ in their name. This allows the programmer to annotate an
argument as intentionally unused, which is occasionally useful in practice.
The concrete syntax allows you to specify multiple arguments in a function value. This is syntactic sugar for nested single argument function values. For example, the following two expressions describe the same function:
(Bool@ a, Bool@ b) { a.?(true: b, false: False); } (Bool@ a) { (Bool@ b) { a.?(true: b, false: False); }; }
Runtime is O(N log(M)), where N is the number of variables in scope that are captured by the function and M is the number of variables in scope. Only variables referenced in the body of the function are captured by the function.
Expr: func_apply (func : Expr) (arg : Expr)
expr = expr, '(', expr, {',', expr}, ')'
foo(x) foo(x)(y) foo(x, y)
The application expression is used to apply a function to an argument. The supplied argument must match the type specified for the function. The application expression evaluates to the value of the body of the function in the context of the supplied argument.
The concrete syntax allows you to specify multiple arguments in a function application. This is syntactic sugar for nested single argument function application. For example, the following two expressions describe the same function application:
foo(x)(y) foo(x, y)
Runtime is O(log(M)) plus the runtime of func, the runtime of the argument, and the runtime of the body, where M is the number of variables captured by the function.
A deep chain of tail recursive calls takes O(1) stack space. Local variables not passed as arguments in a tail recursive call are not retained across the tail call.
A deep chain of non-tail recursive calls takes O(N) stack space, where N is the depth of the call chain. The implementation must provide the same order of magnitude stack space as there is heap space available. Programmers should not need to convert non-tail recursive functions to use heap space instead of stack space.
Polymorphism allows expressions to be parameterized by types.
Kind: poly_kind (arg : Kind) (return : Kind)
kind = '<', kind, {',', kind}, '>', kind
<@>@ <@,@>%
A poly kind describes the kind of a polymorphic value. It describes what kinds of values can be used as arguments to polymorphic values.
Two poly kinds are equal if they have the same argument and return kinds.
A kind is compatible with another kind if it is at least as polymorphic as
the other kind. For example, something of kind <@>@ is compatible for
use when something of kind @ is expected, but not the other way around.
A poly kind is compatible with another poly kind if both its argument and
return kinds are compatible with the other argument and return.
A poly kind is considered a normal kind if its result kind is a normal kind, and a type kind of its result kind is a type kind.
The argument kind of a poly kind must be a type kind.
The concrete syntax allows you to specify multiple arguments in a poly kind. This is syntactic sugar for nested single argument poly kinds. For example, the following two expressions describe the same kind:
<@,@,@>@ <@><@><@>@
Expr: poly_value (arg : (Kind, TypeName)) (body : Expr)
block = '<', kind, name, {',', kind, name}, '>', block
<@ T@> { +(T@ just, Unit@ nothing); } <@ T@>(T@ x){ Maybe@<T@>(just: x); }
A polymorphic value is a value that is parameterized by one or more abstract types. Poly arguments must be of type kind, not normal kind. The type of a polymorphic value depends on the value of the poly arguments, but the runtime value does not. Use a function instead of a poly if you want a runtime value that changes depending on the value of its arguments.
The type of a poly value is a poly type value with the same arguments as the poly value whose body describes the type of the poly body. For example, the type of the poly value:
<@ T@> { Maybe@<T@>(nothing: Unit@); }
Is the poly type:
<@ T@> { Maybe@<T@>; }
The body of a poly is evaluated as part of evaluation of the poly value. The runtime is the runtime of the body.
Expr: poly_apply (poly : Expr) (arg : Type)
expr = expr, '<', type, {',', type}, '>'
Maybe@<Int@> fromJust<Int@>(3)
Poly application is used to specialize a poly value for a specific type.
The type of a poly application is the type of the body of the poly value, with the abstract type variables substituted for the corresponding concrete type values provided as argument to the poly application.
It is a type error if the kind of the type argument is not compatible with the kind of the argument expected by the poly.
The runtime of a poly application is linear in the number of arguments plus the runtime of the poly. Unlike function application, poly application does not cause the body of the poly to be re-evaluated.
Type inference allows you to use poly values in place of struct types, union types, and function values in struct_value_explicit_type, union_value, and func_apply respectively. The type arguments of the poly are inferred and automatically applied by the compiler based on the types of the arguments to the struct_value_explicit_type, union_value, or func_apply.
For example, assume you have a polymorphic function fromJust of type:
<@ T@>(T@) { Maybe@<T@>; }
Assuming the type of 3 is Int@, the func_apply expression
fromJust(3) is rewritten by the compiler to fromJust<Int@>(3).
The motivation for supporting type inference is to prevent cluttering the code with types that are otherwise straight forward to infer. This is particularly important when used in combination with function bind (described later), where the common use case requires specifying the return type repeatedly for each call in a function bind chain. It is a type error if the compiler is unable to unambiguously infer all the type parameters to the poly based on the arguments. For example, it would be impossible to infer type arguments to a poly with either of the following types:
<@ T@>(Unit@) { T@; } <@ T@, @ M@>(M@<T@>) { M@<T@>; }
The type and runtime behavior of a poly inference expression is the same as the type and runtime behavior of the target combined poly application and struct_value_explicit_type/union_value/func_apply expression.
We introduce syntax for describing lists and literals to make it less tedious to write code involving sequences of elements of the same type and raw sequences of data without the overhead of punctuation between data elements.
We introduce bind syntax to facilitate calling a function with an anonymous function as its only argument. This is useful for using reusable glue logic to compose operations in a monadic style.
Expr: list (func : Expr) (args : [Expr])
expr = expr, '[', [expr, {',', expr}], ']'
List<Int@>[] List<Int@>[x] List<Int@>[x, f(y), z]
A list expression describes a sequence of zero or more values of the same type that are combined together according to a user supplied function. It is syntactic sugar for constructing a list value and passing it as a single argument to a function.
The list expression can be used with any function that has an argument of
list type. A list type is any type matching the structure of the following
type L@:
@ L@ = +(*(E@ head, L@ tail) cons, *() nil);
The fields can be named anything, but the order of the fields must match
that shown above. Any type E@ of list elements may be used.
The list expression f[a, b, c], assuming the type of f is
(L@) { V@; } for some type V@, is desugared to:
f(L@(cons: @(head: a, tail: L@(cons: @(head: b, tail: L@(cons: @(head: c, tail: L@(nil: *()()))))))));
Each argument to the list expression must have a type E@ matching the
element type of the list type L@ expected by the function f.
The function provided in the list expression may be a polymorphic function value, in which case type inference is performed as with func_apply expressions.
Struct types and package types cannot be used for the function in list syntax, even though they share a similar concrete syntax to function application.
The motivation for requiring a function to be supplied as part of the list
expression, instead of having stand alone list expressions like
[a, b, c], is:
It allows the user to specify what type of list to build instead of assuming a single builtin list type.
It make it possible to specify the type for empty lists.
It is consistent with literal expressions, which require a user defined letter type to be supplied.
Expr: literal (func : Expr) (letters : word)
expr = expr, '|', word
Octal|177 Str|'hello there!'
The literal expression is syntax that allows you to express a raw sequence of data without the overhead of punctuation between data elements. It is syntactic sugar for a list expression with a separate list element for each individual letter of the literal expression's word.
As with the list expression, the literal expression is used with a function
that has an argument of list type. The element type of the list must be a
union type with fields of type *() for each letter in the word.
For example, the element type for an octal literal might look like:
@Octal = +(*() 0, *() 1, *() 2, *() 3, *() 4, *() 5, *() 6, *() 7);
The literal expression f|077, assuming the element type for the list
argument to f is Octal@, is desugared to:
f[Octal@(0: *()()), Octal@(7: *()()), Octal@(7: *()())];
In the example above, each letter corresponds to a single character. You can define letters to be longer field names too. In that case, the literal word is split up into letters by reading from left to right and selecting the longest field name to match at each position.
It is a type error if the word cannot be decoded into a sequence of letters
based on the field names of the element type E@.
Struct types and package types cannot be used for the function in literal syntax, even though they share a similar concrete syntax to function application. Type inference is not supported with literals because the word provides no information about what type the function should be.
To better illustrate the intended use of list and literal expressions, imagine we want to define a binary integer literal.
The type of letter is a bit:
@ Unit@ = *(); @ Bit@ = +(Unit@ 0, Unit@ 1);
The literal will be formed of lists of bits:
@ Bits@ = +(*(Bit@ head, Bits@ tail) cons, Unit@ nil);
The function specifies how to transform a list of bits into an integer,
assuming some int type Int@:
(Int@, Bits@) { Int@; } Helper = (Int@ n, Bits@ bits) { bits.?(nil: n); Int@ m = Add(Mul(2, n), bits.cons.head.?(0: 0, 1: 1)) Helper(m, bit.cons.tail); }; (Bits@) { Int@; } Binary = (Bits@ bits) { Helper(0, bits); };
Now we can form binary literals using list or literal expressions. For example:
Int@ 6 = Binary|110; Int@ x = Binary[first_bit, second_bit, third_bit];
Expr: bind (args : [(Type, Name)]) (func : Expr) (body : Expr)
stmt = type, name, {',', type, name}, '<-', expr, ';', stmt
Int@ x <- Map(l); f(x, y)
Bind is syntactic sugar for calling a function with an anonymous function as its argument. It is equivalent to:
func_apply func (func_value args [body])
For example, the expression:
Int@ x <- Map(l);
f(x, y)
Desugars to:
Map(l)((Int@ x) { f(x, y); });
Multiple arguments can be provided in the bind syntax to form a multi argument function. For exmaple:
Int@ x, Bool@ y <- Map(l); f(x, y)
Desugars to:
Map(l)((Int@ x, Bool@ y) { f(x, y); });
Bind is particularly suited for abstracting glue logic that manipulates how
program statements are combined. For example, it can be used to hide error
propagation based on a Maybe@ monad.
Instead of:
Maybe@ a = f(x); a.?( just: { Maybe@ b = g(a.just); b.?(just: h(b.just), nothing: Nothing); }, nothing: Nothing);
And instead of the slightly better:
(Maybe@, (X@) { Maybe@; }) { Maybe@; } Maybe = (Maybe@ m, (X@) { Maybe@; } f) { m.?(just: f(x.just), nothing: Nothing); }; Maybe(f(x), (X@ a) { Maybe(g(a), (X@ b) { h(b); }; };
You can write:
(Maybe@)((X@) { Maybe@; }) { Maybe@; } Maybe = (Maybe@ m)((X@) { Maybe@; } f) { m.?(just: f(x.just), nothing: Nothing); }; X@ a <- Maybe(f(x)); X@ b <- Maybe(g(x)); h(b);
Which more clearly separates the glue logic from the meat of the program.
The function provided in the bind expression may be a polymorphic function value, in which case type inference is performed as with func_apply expressions.
Struct types and package types cannot be used for the function in bind syntax, even though they share a similar concrete syntax to function application.
Fble code is organized into a hierarchy of reusable modules. Each module describes a value that may depend on the value of other modules. A program is formed by combining a module with all of its direct and indirect dependencies.
Modules are organized into a tree structure. The purpose of the tree structure is to group modules together that are developed by the same organization to help avoid name conflicts.
The module hierarchy is described in a platform dependant manner. On a platform with standard file system, the following is suggested:
The hierarchy of modules is expressed using a directory hierarchy. The
value of a module Foo is described in the file Foo.fble as an fble
expression using the stmt concrete syntactic term. The child modules of
Foo are placed in a directory Foo/.
For example, you might have the following directory structure:
root/
StdLib/
Unit.fble
List.fble
List/
Tests.fble
Md5.fble
Md5/
Tests.fble
Modules may depend on other modules independent of the tree hierarchy of modules. A program can include a module without having to depend on any descendants of that module. The only restriction on module dependencies is that there must not be any cyclic dependencies. A module may not reference itself, as that is considered a form of cyclic dependency.
A module is referred to using an absolute path, which describes a path of named children from the root of the module hierarchy.
Path: abs_path (name : [Name]) Expr: module_path (ref : Path)
path = '/', name, {'/', name}, '%' expr = path
/StdLib/List% /Unit% /Md5/ImplA%
A program is an fble expression that creates a value that is used however is deemed suitable by whoever is executing the program.
In practice, the value could be a polymorphic function value of abstract monadic type. The function is applied to a builtin instance of the monadic type that can have side effects. For example, the type of the value might be:
<<@>@ M@>(Monad@<M@>, Stdio@<M@>)(List@<String@>) { M@<Bool@>; };
The function is provided with instances of the Monad@ and Stdio@
interface and a list of command line arguments. The function is executed,
resulting in input and output operations over the Stdio@ interface, and
the final result is converted to a standard exit code.
Other examples of ways to execute an fble program:
Evaluate the value to ensure there are no runtime errors, for testing purposes.
The value is a polymorphic function of abstract monadic type that takes an interface to a graphical display. The function is executed, resulting in updates to the display of an application window.
A program is formed of a module and all of its direct and indirect dependencies. For example, consider the following module hierarchy:
StdLib/
Unit
List/
Tests
Md5/
Tests
With the following dependency graph:
/StdLib/List% -> /StdLib/Unit% /StdLib/List/Tests% -> /StdLib/List%, /StdLib/Unit% /Md5% -> /StdLib/Unit%, /StdLib/List% /Md5/Tests% -> /StdLib/Unit%, /Md5%
The module /Md5/Tests% can be turned into a program to run Md5 tests
conceptually by forming a let expression in topological sort dependency
order:
StdLib_Unit = </StdLib/Unit%>; StdLib_List = </StdLib/List%>; Md5 = </Md5%>; </Md5/Tests%>;
Where </Foo%> is the fble expression describing the value of module
/Foo% and we assume references to a module /Foo/Bar% in the
expression are replaced with variables named Foo_Bar.
Notice in this case that the value of /StdLib/List/Tests% is not used.
The modules may be combined in any order that satisfies their dependencies.
The same module hierarchy can be used for a program to run List tests:
StdLib_Unit = </Stdlib/Unit%>; StdLib_List = </StdLib/List%>; </StdLib/List/Tests%>;
On a platform with standard file system, the following is suggested:
To support modular compilation and platforms that allow distributing
pre-compiled modules in binary form, the type of a module can optionally
be described in the file Foo.fble.@ as an fble expression using the
stmt concrete syntactic term whose type is the same as the type of the
module Foo. The Foo.fble.@ file will never be executed, which means
it may contain undefined values for implementations of functions. In this
way, Foo.fble.@ can be considered as a header file for the module
Foo.
If both Foo.fble and Foo.fble.@ are provided for a module, the
Foo.fble.@ file is considered the source of truth for the type of
Foo. It is a compile error if the type of Foo.fble does not match
the type of Foo.fble.@.
If Foo.fble.@ is provided, then compilation of a module that depends on
Foo should read the type of Foo from the Foo.fble.@ file,
ignoring any Foo.fble file that may or may not be present at the time
of compilation.
The Foo.fble.@ file is optional. If it is not provided, the type of a
module should be determined from the Foo.fble file for the module.
The undef expression is particularly useful for writing header files. For example, a header file for a module defining a boolean type might look like:
@ Bool@ = +(Unit@ true, Unit@ false); Bool@ True; Bool@ False; (Bool@) { Bool@; } Not; (Bool@, Bool@) { Bool@; } And; (Bool@, Bool@) { Bool@; } Or; @(Bool@, True, False, Not, And, Or)
Private types provide a mechanism to define types of values that can only be accessed by modules under the same location in the module hierarchy. This makes it possible to hide implementation details from users and enforce invariants on how values are constructed.
By default, anyone can use any operation supported by the type of a value, including construction, field access, conditional access, function application, and so on. A private type is a type whose access is restricted based on module path. Modules that have not been granted access to the type can only interact with it using publicly available functions.
Expr: package_type (path : Path)
expr = '@', path
@ FooBar@ = @/Foo/Bar%;
The package type describes a set of modules under the same location in the
module hierarchy by using what is called a package path. A module belongs
to the package if the package path is a prefix of the module path.
For example, the package type @/Foo/Bar% includes modules
/Foo/Bar%, /Foo/Bar/Sludge%, and /Foo/Bar/A/B%, but not
/Foo% or /Bar%.
The package path for a package type need not refer to an existing module. There need not be any modules that satisfy the package path. A module need not be a member of whatever package type it constructs.
A package type has kind @. Two package types are considered equal if
they have the same path.
Specifying the module path for a private type via a package type instead of directly as a module path allows fble language abstactions like variables and structs to be used for describing package types.
Type: private_type (type : Type, package : Type)
type = type, '.%(', type, ')'
@ PrivateBool@ = +(Unit@ true, Unit@ false).%(@/Foo/Bar%);
The private type behaves exactly like the given underlying type for modules with access, and as an abstract non-polymorphic type otherwise. The package type argument to the private type is used to determine which modules are granted access to the type.
It is a type error if the package argument is not of package type.
Two private types are considered equal if their underlying types are equal and either their package types are equal or the module where the equality check is being performed is granted access to both types.
For example, the following assignments are well typed in the module
/Foo/Bar/Sludge%:
@ Bool@ = +(Unit@ true, Unit@ false); @ PrivateBool@ = Bool@.%(@/Foo/Bar%); Bool@ true = Bool@(true: Unit); PrivateBool@ private_true = true; Bool@ true2 = private_true;
The same code would fail to type check in the module /Bar% because
/Bar% doesn't have access to PrivateBool@, and so
PrivateBool@ and Bool@ are considered unequal types.
If the underlying type of a private type is itself a private type, the module will need to have access to both layers of private type to access the underlying value.
Expr: private_value (expr : Expr, package : Type)
expr = expr, '.%(', path, ')'
PrivateBool@ private_true = True.%(@/Foo/Bar%);
The private value expression can be used to cast the type of a value to a
private type. In the example here, if the type of True is Bool@,
then True.%(@/Foo/Bar%) has the same value as True, but is of
private type Bool@.%(@/Foo/Bar%).
This is mostly useful for constructing values where the type of the value is not mentioned expicitly during construction, such as implicit struct values and function values.
It is a type error if you don't have access to the type of value you are casting to.
Private values can be nested the same way as private types.
The following example shows how to define a three element enum type that can only be accessed externally using the provided methods.
@ Enum@ = +(Unit@ a, Unit@ b, Unit@ c).%(@/MyPackage%); Enum@ A = Enum@(a: Unit)); Enum@ B = Enum@(b: Unit)); Enum@ C = Enum@(c: Unit)); (Enum@) { Bool@; } IsA = (Enum@ e) { e.?(a: True, : False); }; (Enum@) { Bool@; } IsB = (Enum@ e) { e.?(b: True, : False); }; (Enum@) { Bool@; } IsC = (Enum@ e) { e.?(c: True, : False); }; @(Enum@, A, B, C, IsA, IsB, IsC);
The Enum@ type restricts access to internals of the type to modules
starting with /MyPackage in their path. Other users are unable to
construct or access fields of the Enum@ type directly; they can only
use the provided values A, B, C and functions IsA, IsB,
and IsC.
Private types can be used to mark exported functions from a module as
proviate, and private values can be used to effectively mark a module as
private. For example, consider a module /Foo/Internal%:
@ X@ = ...; @ Y@ = ...; X@ X = ...; Y@.%(@/Foo/Internal%) Y = ...; @(X@, Y@, X, Y).%(@/Foo%);
Any attempt to use the value of Y from a module not starting with
/Foo/Internal% will result in a type error. That way Y can be
exported and used from submodules like /Foo/Internal/A%, but not by
anyone else.
Any attempt to use the value of /Foo/Internal% from a module not
starting with /Foo% will result in a type error.
NormalName: A string of characters.
TypeName: A string of characters.
Name:
normal_name (name : NormalName)
| type_name (name : TypeName)
;
Path:
abs_path (name : [Name])
;
Kind:
basic_normal_kind
| basic_type_kind
| poly_kind (arg : Kind) (result : Kind)
;
Type: Synonym for Expr where a type is expected.
Spec:
kind_spec (kind : Kind)
| type_spec (type : Type)
;
Expr:
typeof (expr : Expr)
| var (name : Name)
| let (bindings : [(Spec, Name, Expr)]) (body : Expr)
| undef (name: Name) (type: Type) (body: Expr)
| module_path (path : Path)
| struct_type (fields : [(Type, Name)])
| struct_value_explicit_type (type : Type) (args : [Expr])
| struct_value_implicit_type (args : [(Name, Expr)])
| struct_access (object : Expr) (field : Name)
| struct_copy (src : Expr) (args : [(Name, Expr)])
| union_type (fields : [(Type, Name)])
| union_value (type : Type) (field : Name) (arg : Expr)
| union_access (object : Expr) (field : Name)
| union_select (condition : Expr) (choices : [(Name, Expr)]) (default : Expr)
| func_type (arg : Type) (result : Type)
| func_value (arg : (Type, Name)) (body : Expr)
| func_apply (func : Expr) (arg : Expr)
| poly_value (arg : (Kind, Name)) (body : Expr)
| poly_apply (poly : Expr) (arg : Expr)
| list (func : Expr) (args : [Expr])
| literal (func : Expr) (letters : word)
| bind (args : [(Type, Name)]) (func : Expr) (body : Expr)
| package_type (path : Path)
| private_type (type : Type) (package : Type)
| private_value (value : Expr) (package : Type)
;
Module: (value : Expr) (modules : [Module])
We have the following categories of characters:
#.(){|};,:?=.<>+*-!$@~'\[]%/^.The lexical syntax is used to interpret a string of arbitrary characters as a sequence of punctuation characters and words.
Whitespace is treated as a delimiter of words. The comment character and any following characters on the same line are treated as a delimiter of words. Whitespace and comments are otherwise ignored.
A sequence of continuous word characters is grouped together into a word.
A sequence of characters surrounded by single quotes is treated as a
sequence of word characters, regardless of what class the characters come
from. This makes it possible to specify words containing whitespace,
comment, and punctuation characters. For example, 'Foo,Bar' is treated
as a single word where the fourth character of the word is a comma.
Within a single quoted word, a single quote character can be expressed by
using two adjacent single quote characters. For example, 'Foo''Bar' is
treated as a single word where the fourth character of the word is a single
quote.
Single quotes act as word delimiters. For example,
Foo'.'Bar
is treated as three separate words: 'Foo', '.', and 'Bar', not
as a single word 'Foo.Bar'. The only exception is when consecutive
single quote characters are used to embed a single quote character in a
word.
word = ? word as described in the section on lexical syntax ? normal_name = word type_name = word, '@' name = normal_name | type_name ; path = '/', name, {'/', name}, '%' ; kind = '%' (* normal_kind *) | '@' (* type_kind *) | '<', kind, {',', kind}, '>', kind (* poly_kind *) ; type = expr ; spec = kind (* kind_spec *) | type (* type_spec *) ; field_arg = name, [':', expr] ; (* implicit tagged expr *) expr = '@', '<', expr, '>' (* typeof *) | name (* var *) | path (* module_path *) | '*(', [type, name, {',', type, name}], ')' (* struct_type *) | type, '(', [expr, {',', expr}], ')' (* struct_value_explicit_type *) | '@(', [field_arg, {',', field_arg}] ')' (* struct_value_implicit_type *) | expr, '.', name (* struct_access *) | expr, '.@(', field_arg, {',', field_arg}, ')' (* struct_copy *) | '+(', type, name, {',', type, name}, ')' (* union_type *) | type, '(', name, ':', expr, ')' (* union_value *) | expr, '.', name (* union_access *) | expr, '.?(', name, ':', expr, (* union_select *) {',', name, ':', expr}, [',', ':', expr], ')' | expr, '(', expr, {',', expr}, ')' (* func_apply *) | expr, '<', type, {',', type}, '>' (* poly_apply *) | expr, '[', [expr, {',', expr}], ']' (* list *) | expr, '|', word (* literal *) | '@', path (* package_type *) | type, '.%', '(', path, ')' (* private_type *) | expr, '.%', '(', path, ')' (* private_value *) | block ; block = '{', stmt, '}' | '(', type, {',', type}, ')', block (* func_type *) | '(', type, name, {',', type, name}, ')', block (* func_value *) | '<', kind, name, {',', kind, name}, '>', block (* poly_value *) ; stmt = expr, ';' | spec, name, '=', expr, (* let *) {',', spec, name, '=', expr}, ';', stmt | stmt = type, name, ';', stmt (* undef *) | expr, '.?(', name, ':', expr, (* union_select *) {',', name, ':', expr} ')', ';', stmt | type, name, (* bind *) {',', type, name}, '<-', expr, ';', stmt ; module = stmt (* module_value *) ;
Notes:
Struct and union access share the same form. The type of the object is used to distinguish between the two kinds of expressions.
Explicit type struct value, and function apply share the same form. The type of the expr is used to distinguish between these kinds of expressions.
The concrete syntax for private type and private value are identical. The type of the argument is used to distinguish between the two cases.
The module value for module /Foo/Bar% is stored in Foo/Bar.fble.