Expressions and Operators

Because it is a functional language without side effects, all useful computation in Melodeon produces a value. Something that evaluates to a value is an expression: so, everything is an expression in Melodeon.

Operators

Literals representing values are the simplest Melodeon expressions. The following built-in operators provide building-blocks for more complex expressions. As explained below, the operators are grouped by input. In the Precedence field, a larger value signifies a higher order of precedence (“tighter” binding).

Also, try out the operators in the REPL as you read along!

Nat operators

Nat operators take natural numbers. For example, the compiler throws a type error if you try to compare two vectors with <=:

melorun> [1] <= [1, 2]
Melodeon compilation failed
~/.melorun.melo.tmp:3: error: expected a subtype of Nat, got [{1}] instead
    [1] <= [1, 2]
^~~~~~~~~~~~~

Logical operators

Logical operators take any value as input, interpreting their inputs as booleans. As mentioned in the section on values, 0 is “falsy” and every other value is “truthy”.

Examples:

melorun> 0 || 1
1

melorun> 0 && 1
0

melorun> 1 && 2
2

melorun> !3
0

As you might have noticed from the examples, && and || are implemented with short-circuit evaluation.

x && y is equivalent to

if x then y else x

and x || y is

if x then x else y

Short-circuiting logical operators enable neat JavaScript-style idioms in Melodeon. For instance, suppose we want to multiply x by 2 if it’s a Nat, but x’s most specific type is Nat | %[8] (in other words, we only know x is either a Nat or a byte string of length 8). We can express this logic with

x is Nat && x * 2

In this expression, x is Nat is a boolean expression that evaluates to true if x is a member of type Nat (you can read about the is operator in Advanced Types). Because && has short-circuit logic, if x is Nat, then we’ll get the result of x * 2. If x is Nat is false, then x * 2 will never be evaluated, so we won’t ever get a type error.

Exercise 4.1. What does 0 || ([1] && "hello") evaluate to?

Bitwise operators

Bitwise operators take Nat’s as input, interpreting them as bit strings. Here are a few examples:

melorun> 1 << 2
4

melorun> 8 >> 2
2

melorun> 1 ^ 3
2

melorun> 6 & 4
4

melorun> 2 | 4
6

Try them out in the REPL!

Vector operators

Vector operators take vector inputs. All vectors are 0-indexed. Also, all vector operators return newly created vectors or elements: nothing is ever mutated.

Slice

The slice operator v[i..j] returns a new vector that contains the elements of v between indices i and j, including i but not including j. For example:

melorun> let v = [1, 2, 3] in v[0..1]
[1]

melorun> let v = [1, 2, 3] in v[1..3]
[2, 3]

melorun> let v = [1, 2, 3] in v[0..3]
[1, 2, 3]

(note that let v = expr in body binds the variable v to the expression expr and evaluates body; we will discuss this further later)

Update

Here are a few examples of update. They emphasizes that update does not mutate the vector:

melorun> ([1, 2, 3] :: [Nat; 3])[1 => 3]
[1, 3, 3]

melorun> ([1, 2, 3] :: [Nat; 3])[2 => 5]
[1, 2, 5]

melorun> let v = [1, 2, 3] in (v :: [Nat; 3])[1 => 10] ++ v
[1, 10, 3, 1, 2, 3]

Exercise 4.2. Define vec as follows:

vec = ["melo", "deon"]

What does this expression evaluate to?

vec[1 => "haha"] ++ vec[1..2]

Structure operators

This operator is analogous to vector reference. It’s included here for completeness; learn about structures and field access in Advanced Types and let expressions below.

For example, given a file containing this definition:

struct Point {
    x: Nat,
    y: Nat
}

we have:

melorun> let p = Point{ x: 1, y: 2 } in p.x
1

melorun> let p = Point{ x: 1, y: 2 } in p.y
2

Byte string operators

In Melodeon, ++ is an overloaded operator (that means it’s multiple functions with the same name). It also works for byte strings:

Exercise 4.3. Is "1" ++ [2] a valid Melodeon expression?

If expressions

Melodeon has an ML-like branching expression:

if x then y else z

This returns y if x is “truthy” (i.e. not 0), otherwise z. The inferred type of an if expression is the inferred type of y union the type of z. For instance,

melorun> if 35 then 1 else [10]
- : {1} | [{10}]
1

Exercise 4.4. What is the type of if 35 then 35 else "melodeon"?

Let expressions

Variable bindings in Melodeon are also expressions. They’re similar to variable bindings in ML languages:

let x = expression_1 in
expression_2

binds variable x to expression_1 in the scope of expression_2. Variable names must begin with a lower-case letter and contain only alphanumeric characters. Idiomatically, variables are written in snake_case. Here is an example:

melorun> let x = 1 in x + 2
3

Because let bindings are themselves expressions, they can be chained. For instance,

melorun> let x = 1 in let y = 2 in let z = 3 in x * y + z
5

You can also define multiple variables in one let expression, using this syntax:

let var_1 = expr_1,
    var_2 = expr_2,
    ...,
    var_n = expr_n
in
    expression

A concrete example:

melorun> let x = 1, y = 2 in x + y
3

Iteration expressions

Melodeon has three bounded iteration constructs: for, fold, and loop. Each has a stopping value that determines how many iterations are executed. This is the vector length in for and fold and the iteration number in loop. To prevent unbounded computation (whose fees cannot be pre-determined!), this stopping value must be known at compile time—that is, it must be a constant expression.

A constant expression is either a number whose value is known at compile time, or such numbers combined with + and * (other operators cannot be used in constant expressions). Numeric constants like 1 and 5 are constant expressions; so are 3 + 5 and 1 * 4. Constant generics are the final kind of constant expressions: learn about them in Advanced Types!

Melodeon does not currently support any form of recursion. We are considering adding provably bounded recursion similar to Fixpoint in Coq in the future.

for

for applies an expression to every member of a vector. It’s the equivalent of map in other functional languages. for has two equivalent forms:

for <variable> in <vector> collect <expression>

and also

[<expression> for <x> in <vector>]

which may be familiar from Python.

The collect keyword in the first syntax and the square brackets in the second indicate that the output of for is always a vector.

Examples:

melorun> for x in [1, 2, 3] collect x + 1
[2, 3, 4]

melorun> x && 0 for x in ["melo", "deon"]
[0, 0]

melorun> for n in [1, 2, 3] collect "4"
["4", "4", "4"]

for only works on fixed-length vectors, as we explained above. For example, if we cast the type of [1, 2, 3] in the first example above to a dynamic-length vector, then it will fail to compile.

melorun> for x in ([1, 2, 3] :: [Nat;]) collect x + 1
Melodeon compilation failed
~/.melorun.melo.tmp:15: error: list comprehension needs a list with a definite length, got [Nat;] instead
	for x in ([1, 2, 3] :: [Nat;]) collect x+1
	^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Exercise 4.5. Write a for expression, in either syntax, that squares each element of the vector [1, 10, 100].

fold: WIP

Fold takes a vector, a base value, and a “collector” expression. It applies the expression to each element of the vector with the base value, updating the base value as it proceeds. Its syntax is

for x in vec fold accum = base with expr

where for every element of vec, fold computes expr and sets accum to be the new expr, and base is the starting value of accum. It’s typically used to combine the elements of a vector.

Examples:

melorun> for n in [1,2,3] fold y = 0 :: Nat with y + x
6

melorun> for x in [1,2,3] fold accum = 0 :: Nat with 5
5

melorun> for v in [[1], [2], [3]] fold accum = [] with accum ++ v
TODO!

WIP: casting rules for fold

Exercise 4.6. on casting: WIP

loop: pseudo-imperative loops

loop n do
    body
return ret

executes body n times and returns ret, where body is a chain of 0 or more pseudo-mutations of the form variable_name <- expression separated by semicolons, and n is a constant expression.

A pseudo-mutation is variable mutation restricted to the scope of the loop:

x <- new_value

sets a special copy of a previously defined variable x to new_value. This copy is in scope only in the loop body. So under the hood, this expression

let x = 0 in
loop 5 do
    x <- x+1
return x

is really

let x = 0 in
let y = 0 in
loop 5 do
    y <- y + 1
return y

Pseudo-mutations are only valid inside loop bodies.

Examples:

melorun> let x = 0 :: Nat in
            loop 5 do
            x <- x+1
            return x
5

melorun> let x = 0 :: Nat in
            loop 5 do
                x <- x + 1;
                x <- x + 1
                return x
10

Note: :: Nat here casts x to type Nat. Upcasting is necessary in these examples because the compiler automatically assigns type {0} to x in both cases (read about Melodeon’s type inference in Simple Types), but clearly the new values assigned to x do not belong to {0}. In general, mutated variables often need to be upcasted before mutation to avoid a type error.

To reiterate, the iteration number following the keyword loop must be a constant expression. An example of a non-constant expression is the argument to a function. To see this fail in action, try running the REPL with a .melo file containing this function:

def f(n: Nat) =
    let x = 0 in
    loop n do
        x <- x + 1
    return x

Here’s what we got:

❯ melorun -i loop.melo
Error: Melodeon compilation failed
~/loop.melo:4: error: expected const_mult_expr
	    loop n do
	         ^

Exercise 4.7. Using a loop, write an expression that produces 4 appended copies of the vector [1, 2] (evaluating to [1, 2, 1, 2, 1, 2, 1, 2]).

Assert and Fail

fail! crashes the program.

Examples:

melorun> fail!
MelVM exection failed

melorun> let x = 1 in (if x is %[] then "great!" else fail!)
MelVM execution failed

assert! expr1 in expr2

returns expr2 if expr1 evaluates to true, otherwise fail!. It’s equivalent to

if expr1 then expr2 else fail!

Examples:

melorun> assert! 1==1 in 3
3

melorun> assert! 1 == 2 in 3
MelVM execution failed