The Language Bella

1 Introduction

Bella is a simple programming language with interesting features that make it a great fit for learning (1) compiler and interpreter writing, and (2) formal language semantics.

The language features numeric literals, assignments, basic arithmetic, conditionals, loops, and simple functions. Function bodies are limited to simple expressions and may be recursive, but not mutually recursive. The typing system is static (types are determined at compile time), strong (type mismatches are errors), and inferential (type annotations are ever explicitly given). Bella is a friendly, simple language that is relatively easy to implement.

This document defines the language Bella.

2 Language Description

2.1 Programs

A program is a sequence of one or more statements, of which there are five kinds. Comments begin with // and extend to the end of the line.

let dozen = 12;                                   // let declaration
print dozen % 3 ** 1;                             // print statement
function gcd(x, y) = y == 0 ? x : gcd(y, x % y);  // function declaration
while dozen >= 3 || (gcd(1, 10) != 5) {           // while statement
  dozen = dozen - 2.75E+19 ** 1 ** 3;             // assignment statement
}

Apologies for the old-fashioned semicolons, but they do make the language somewhat easier to parse.

2.2 Values

All values in Bella are either:

• IEEE-754 binary64 values. All operations on these values are as specified in the IEEE-754 standard.
• Functions from zero or more binary64 values to a single binary64 value.

2.3 Types

All values in Bella have a type. Numeric values belong to the type $\textsf{Num}$. Functions of $n$ parameters belong to the type $\textsf{Fun}\,n$.

2.4 Literals

Numeric values in Bella are denoted with literals as in JavaScript:

2
2.0
55.9
819.999e-15
2E+10
5.89999e2

There are no function literals.

2.5 Variables

A variable is a named container for a value. Variables get their name via a declaration, as described in the next section. It is possible for multiple variables to have the same name at the same time.

Variables can be mutable or immutable. All variables bound in the standard library are immutable, as are all variables bound to function values in a function declaration. All other variables are mutable.

let x = 3;
print x;
x = 2;                      // OK, mutable
print π;                    // π is from the standard library
// π = 3;                   // ERROR: immutable

A variable may only contain values of a single type throughout its lifetime.

2.6 Declarations

A declaration binds an identifier to a variable. There are three kinds of declarations:

• function declarations
• let declarations
• parameter declarations

Here is a short example showing all three kinds:

let sister = 5 + 1;          // let declaration of sister (Ⅴ + Ⅰ = Ⅵ)
function triple(x) = x * 3;  // function declaration of triple
                             // ...and parameter declaration of x

Each occurrence of an identifier is either a defining occurrence or a using occurrence. Using occurrences are legal only in the visible region of the declaration that binds the identifier. In Bella, shadowing of identifiers is permitted, so the visible region of a declaration is the scope minus any “inner” scopes of declarations with the same name; therefore the visible region may be discontinuous.

• The scope of an identifier bound in a parameter declaration is the body of the innermost function in which the declaration appears.
• The scope of an identifier bound in a variable declaration begins immediately after its initializer and extends to the end of the block in which the declaration appears.
• The scope of an identifier bound in a function declaration begins immediately after its parameter list and extends to the end of the block in which the declaration appears.

Here a block is code enclosed within a matching pair of curly braces { ... }, or the entire program itself.

Shadowing can occur from declarations that (1) appear later in a block or (2) appear in an inner scope:

let x = 3;
function f() = x;           // Body always refers to the x above
let x = 5;                  // A new, distinct variable (shadows x above)
print f();                  // prints 3
function x() = 0;           // Also shadows the x above
let x = 8;                  // Yet another shadowing of x
function h(x) = 0;          // OK! parameter x shadows global x
while x != 0 {
  print h(1);               // refers to outer h
  let h = 2;                // shadows outer h
  print h;                  // refers to the new h
  let y = 1;                // new variable y in inner scope
  x = 0;                    // Can read and write outer x
}                           // inner h and y go out of scope
// print y;                 // ERROR: y not visible here
print h(3);                 // refers to outer h (inner one is gone now)
function j(k) = π - x;      // OK
// print k;                 // ERROR: k not in scope
let k = 2;                  // OK, brand new k
x = π;
print j(100);               // prints 0
function f(f) = f * k;      // parameter f shadows function f
let k = k + 1;              // creates new k initialized using previous k

Parameter declarations may not be repeated within the same function.

// function g(a, a) = 0;    // ERROR: a already declared

An identifier bound to a variable containing a function value can only be used in a call position. It can never stand alone:

function successor(n) = n + 1;
print successor(2);              // Function call of successor, fine
// let s = successor;            // ERROR: successor cannot stand alone
// print successor;              // ERROR: successor cannot stand alone
// let plusTwo = successor + 1;  // ERROR: successor cannot stand alone
let successor = 5;               // OK, this is a shadowing of the function successor

2.7 Statements

A statement is code that is executed solely for its side effect; it produces no value. The kinds of statements are:

• let $i$ = $e$ ;

  (Let declaration) Declares a new variable with name $i$. Evaluates $e$, which must have numeric type, and assigns this value to the new variable. The new variable is mutable.

• function $f$ ( $x_1, \ldots, x_n$ ) = $e$ ;

  (Function declaration) Defines a new variable named $f$ containing a function with $n$ parameters, that is, its type is $\textsf{Fun}\,n$. The parameters $x_1, \ldots, x_n$ must be distinct. The expression $e$ is not evaluated at this time, but must be determined to have a numeric type.

• $i$ = $e$ ;

  (Assignment statement) Evaluates $e$, which must have numeric type, then copies the value of $e$ into $i$. $i$ must name a visible mutable variable in this scope.

• print $e$ ;

  (Print statement) Evaluates $e$, which must have numeric type, then prints its value to standard output.

• while $e$ $b$

  (While statement) First, evaluates $e$, which must have numeric type. If $e$ produces 0, the execution of the while statement terminates. Otherwise, body $b$ is executed then the entire while statement is executed again.

2.8 Expressions

An expression produces a numeric value. For numeric literals $n$, identifiers $i$ and $f$, and expressions $e$, $e_1$, and $e_2$, the Bella expressions are:

• $n$

  A numeric literal produces the value of the number it denotes.

• true

  Produces 1.

• false

  Produces 0.

• $i$

  Here $i$ must be an identifier bound in a let or parameter declaration (not a function declaration) that is visible in scope. Produces the value of the variable it names.

• - $e$

  Evaluates $e$ and produces the negation of $e$.

• ! $e$

  If $e$ evaluates to 0, produces 1, otherwise produces 0.

• $e_1$ * $e_2$

  The subexpressions are evaluated in any order and their product is produced.

• $e_1$ ** $e_2$

  The subexpressions are evaluated in any order and the result of raising $e_1$ to the power of $e_2$ is produced.

• $e_1$ / $e_2$

  The subexpressions are evaluated in any order and their quotient is produced.

• $e_1$ % $e_2$

  The subexpressions are evaluated in any order and the remainder of $e_1$ divided by $e_2$ is produced.

• $e_1$ + $e_2$

  The subexpressions are evaluated in any order and their sum is produced.

• $e_1$ - $e_2$

  The subexpressions are evaluated in any order and their difference is produced.

• $e$ ? $e_1$ : $e_2$

  Evaluates $e$ and if non-zero, evaluates and produces $e_1$. Otherwise evaluates and produces $e_2$.

• $e_1$ < $e_2$

  Evaluates the subexpressions in any order, then produces 1 or 0, respectively, as to whether the value of $e_1$ is less than the value of $e_2$.

• $e_1$ <= $e_2$

  Evaluates the subexpressions in any order, then produces 1 or 0, respectively, as to whether the value of $e_1$ is less or equal to the value of $e_2$.

• $e_1$ == $e_2$

  Evaluates the subexpressions in any order, then produces 1 or 0, respectively, as to whether the value of $e_1$ is equal to the value of $e_2$.

• $e_1$ != $e_2$

  Evaluates the subexpressions in any order, then produces 1 or 0, respectively, as to whether the value of $e_1$ is not equal to the value of $e_2$.

• $e_1$ >= $e_2$

  Evaluates the subexpressions in any order, then produces 1 or 0, respectively, as to whether the value of $e_1$ is greater or equal to the value of $e_2$.

• $e_1$ > $e_2$

  Evaluates the subexpressions in any order, then produces 1 or 0, respectively, as to whether the value of $e_1$ is greater than the value of $e_2$.

• $e_1$ && $e_2$

  First $e_1$ is evaluated. If it evaluates to 0, the entire expression immediately produces 0 (without evaluating $e_2$). Otherwise $e_2$ is evaluated and the entire expression produces the value of $e_2$.

• $e_1$ || $e_2$

  First $e_1$ is evaluated. If it evaluates to a non-zero value, the entire expression immediately produces this value (without evaluating $e_2$). Otherwise $e_2$ is evaluated and the entire expression produces the value of $e_2$.

3 Standard Library

The following identifiers are pre-defined in a scope that surrounds the program. All are bound to immutable variables, though declarations within a program may shadow them.

• π

  The IEEE-754 binary64 approximation of $\pi$.

• function sqrt(x)

  Returns the square root of $x$.

• function sin(x)

  Returns the sine of $x$ radians.

• function cos(x)

  Returns the cosine of $x$ radians.

• function exp(x)

  Returns $e^x$.

• function ln(x)

  Returns the natural log of $x$.

• function hypot(x, y)

  Returns the hypotenuse of a right triangle with sides $|x|$ and $|y|$.

4 Formal Syntax

The source of a Bella program is a Unicode string. Here is the syntax given as an Ohm grammar:

Bella {
  Program   = Statement+
  Statement = let id "=" Exp ";"                        -- vardec
            | function id Params "=" Exp ";"            -- fundec
            | Exp7_id "=" Exp ";"                       -- assign
            | print Exp ";"                             -- print
            | while Exp Block                           -- while
  Params    = "(" ListOf<id, ","> ")"
  Block     = "{" Statement* "}"

  Exp       = ("-" | "!") Exp7                          -- unary
            | Exp1 "?" Exp1 ":" Exp                     -- ternary
            | Exp1
  Exp1      = Exp1 "||" Exp2                            -- binary
            | Exp2
  Exp2      = Exp2 "&&" Exp3                            -- binary
            | Exp3
  Exp3      = Exp4 ("<="|"<"|"=="|"!="|">="|">") Exp4   -- binary
            | Exp4
  Exp4      = Exp4 ("+" | "-") Exp5                     -- binary
            | Exp5
  Exp5      = Exp5 ("*" | "/" | "%") Exp6               -- binary
            | Exp6
  Exp6      = Exp7 "**" Exp6                            -- binary
            | Exp7
  Exp7      = num
            | true
            | false
            | id "(" ListOf<Exp, ","> ")"               -- call
            | id                                        -- id
            | "(" Exp ")"                               -- parens

  let       = "let" ~idchar
  function  = "function" ~idchar
  while     = "while" ~idchar
  true      = "true" ~idchar
  false     = "false" ~idchar
  print     = "print" ~idchar
  keyword   = let | function | while | true | false
  num       = digit+ ("." digit+)? (("E" | "e") ("+" | "-")? digit+)?
  id        = ~keyword letter idchar*
  idchar    = letter | digit | "_"
  space    += "//" (~"\n" any)*                         -- comment
}

5 Formal Semantics

The meaning of a Bella program is defined in this section via transition rules in the style of Natural Semantics. It is defined from the following abstract syntax:

5.1 Static Semantics

Constructs are statically analyzed relative to a context that keeps track of the type and mutability status of each identifier.

Statically analyzing an expression computes its type; statically analyzing a statement or block computes the resulting context; Statically analyzing a program simply determines whether it satisfies all contextual rules.

Notes

Shadowing rules lead to a simpler semantics than in languages that forbid it, since no checks are needed to prohibit redeclaration within a scope.

Since the visible region of a declaration begins after the declaration is complete, the statement let x = x + 1; in a while-body reads the enclosing x and declares a fresh local one (similar to Lua but different from JavaScript, where the corresponding region is a temporal dead zone and the reference is an error).

The while statement rule specifically produces its input context. Local declarations in the loop body therefore stay in the loop body.

The function rule places $f$ into the context before checking the body, so a function may call itself recursively. But because the parameters are added after $f$, a parameter named $f$ shadows the function itself, making recursion unavailable within such a body.

5.2 Dynamic Semantics

Dynamic meanings are computed relative to both an environment, mapping identifiers to variables, and a store, mapping variables to values. Both are required since multiple variables with the same name can live simultaneously, and captured variables in a closure must not be lost by a subsequent shadowing.

Notes

Environments are required because a single map from identifiers to values cannot properly handle the scenario of simultaneous active bindings of one name: let x = 1; function f() = x; while c { let x = 2; print f(); }, must print $1$. Similarly, let x = 1; function f() = x; x = 2; print f(); must print $2$ .

Declarations always allocate fresh variables (allowing shadowing to work), while assignments update values of variables (allowing mutations to become visible to a closure that captured an environment mapping an identifier to that same variable).

Since function bodies are expressions, they can neither assign nor print, so there is no need to model recursion with an explicit stack of environments.