2 Program Structure

2.1 Program Is an Expression

In Wafl, programs are expressions. Each program (or expression) defines primarily what to evaluate and not how to execute or evaluate.

If we want to write a program that computes 1+2+3, then we write just that expression and nothing else:

1+2+3

6

We can use literals, names, operators and functions in expressions. Here are just a few simple examples. First, this is an integer expression:

53 / 5 * 4 + 12 % 10 + abs(-7)

49

A float expression:

53. / 5. * 4. + 2.12 + sin(1.34)

45.49348454

A string expression:

strUpperCase( "Hello " + 'world!' )

HELLO WORLD!

A bool expression:

false or true

true

Wafl supports many of the usual operators and functions on primitive types (integer, float, string and bool). Also, there are more complex types (list, array, map, tuple, record), which we will cover in more details later.

Simple expressions are often not enough. In the following sections, we will see how to define and use functions and named expressions.

2.2 Comments

Two kinds of comments are available in Wafl. Block comments begin with /* and end with */. Line comments begin with // and end with end of line.

/* This is a block comment,
   in two lines */
1 + 2 // This is a line comment after an expression

3

2.3 Tuples

Tuple is a structured data type. It consists of a number of unnamed elements, which are referenced by position. Tuple elements may have different types.

We will discuss tuples in details in the following chapters. Now we have to present tuples just to make some of the following examples understandable. It is sometimes easier to present many simple expressions in one example than to use many examples, and tuples are a nice tool for that.

Tuples are written using curly brackets with hashes: {# ... #}, and tuple elements are separated by commas:

{# 1, 2, 3.14, "Hello world!" #}

{# 1, 2, 3.14, 'Hello world!' #}

In the following example we use a tuple to evaluate 6 integer expressions:

{#
    7 - 6,
    1 + 1,
    6 / 2,
    2 * 2,
    12 % 7, //  Integer division reminder
   -8 %% 7  //  Similar to `%`, but always positive
#}

{# 1, 2, 3, 4, 5, 6 #}

2.4 Local Definitions

A Wafl expression may define and use some local definitions. Local definitions are specified and used in where expressions. Local definitions include expression definitions and function definitions. Expression definitions are also referred as named expressions.

In short:

Named expressions are used as values, and functions are applied to some arguments.

The last sentence is a nice intuitive description, but do not take it strict. As we will see later, a named expression may have a functional type and apply to arguments, and a function may be used as a value.

In the following example we define and use both a function and a named expression:

fun( 100, 0 ) + nam
where {
    fun( a, b ) = a * 10 + b;
    nam = fun( 4, 2 );
}

1042

The function definition has name and parenthesis on the left side of the equality symbol, and named expression has only the name on the left side.

Local definitions are specified in where expressions. A where expression consists of a main expression body and a block of local definitions (in short where-block):

<main-expression-body>
where {
    <definition>;
    <definition>;
    ...
}

where each <definition> represents an expression definition or a function definition.

A function definition binds a function body to a function name and to its arguments. A function definition has the form:

<name>(<arguments>) = <expression>;

where <arguments> is a list of the function argument names. Arguments are separated by commas. The argument list may be empty.

A named expression definition binds an expression to a name and has the following form:

<name> = <expression>;

where <name> is any valid name and <expression> is (almost) any valid Wafl expression. The main restriction is that a name definition expression must not contain a where block.

The functions and the named expressions are not the same, by any means. Their semantics is very different. A named expression is something like a tool to make the expressions shorter and more readable, and it is obviously strongly bound to the context. On the other side, a function is always free of the context. In the following section we will discuss some specific details on local definitions and functions.

2.5 Function Definition

A function definition binds a function body to a function name and to its arguments:

<name>(<arguments>) = <expression>;

A function definition expression (<expression>) may use the following names:

In the following example, in the expression body of the function f we can use:

We could not use, for example:

f('*')
where {
    f(x) = x + name_main + name_f + f1(x) + g(x)
    where {
        name_f = x + x;
        f1(x) = x + x + g(x);
    };
    name_main = '---';    
    g(x) = name_g + g1(x)
    where {
        name_g = x + x;
        g1(x) = x + x;
    };
}

*---************

2.6 Named Expression Definition

A named expression definition binds an expression to a name and has the following form:

<name> = <expression>;

A named expression definition (<expression>) may use the following names:

In the following example, in the named expression name_f we can use:

It is important to note that we cannot use recursive references to name definitions (neither directly nor indirectly) within a name definition expression, but we can use the function in whose where-block the named expression is defined.

f('*')
where {
    f(x) = x + name_main + name_f + f1(x) + g(x)
    where {
        name_fa = name_main + x + x;
        name_f = name_main + name_fa + g(x) + f1(x) + x + x;
        f1(x) = x + x + g(x);
    };
    name_main = '---';    
    g(x) = name_g + g1(x)
    where {
        name_g = x + x;
        g1(x) = x + x;
    };
}

*---------************************

2.7 No Variables

It is important to emphasize that the named expressions are not variables. Wafl has no variables. If a name is defined to represent an expression, then it will represent that same expression throughout the evaluation of the scope in which the name is available. It is not possible to change the definition.

In the following example the x is defined twice, so an error is reported:

x
where {
    x = 1;
    x = 2;
}

--- Loading: C:\Users\smalkov\AppData\Local\Temp\wafltmpfile_sgk8.w.tmp
Parser error [C:\Users\smalkov\AppData\Local\Temp\wafltmpfile_sgk8.w.tmp]
    Definition name repeated! [err 1211:3]
    Line 6: }
        ___/
--- End loading: C:\Users\smalkov\AppData\Local\Temp\wafltmpfile_sgk8.w.tmp

A name can have different definitions in different scopes, even if one of the scopes is contained within another. If more than one definition of the same name is visible, the one with a narrower scope (i.e. closer to the usage point) is relevant.

In the next example name x is defined twice:

x + f( "10" )
where {
    x = "ABC";          //  the first `x`
    f( s ) = x + s + y
    where {
        x = "abc";      //  the second `x`
        y = "xyz";
    };
}

ABCabc10xyz

If a named expression is defined in a function where-block, and it uses function arguments (either directly or indirectly), then, of course, it may have different values for different function evaluation. However, that is not a problem, because it is usable only in the scope of that function evaluation.

In the following example, the function f is evaluated two times, first for argument 'a', and then for argument 'b'. During the f('a') evaluation, the name evaluates to '*a*', and during the f('b') evaluation, it evaluates to '*b*'. As expected, the named expressions values are not shared among different evaluations:

{# f('a'), f('b') #}
where {
    f(s) = s + name + s
    where {
        name = '*' + s + '*';
    };
}

{# 'a*a*a', 'b*b*b' #}

An important aspect of the named expressions implementation is efficiency. Each named expression is evaluated at most once per context. If it is never used, then it is never evaluated, but if it is used many times, it is never evaluated more than once.

In the following example the value of the named expression is never requested, so it is never evaluated. We know that for sure, because its evaluation would produce an error:

if 2 < 5
    then 5
    else error
where {
    error = 1/0;    //  Zero division!
}

5

In the following example we use the same name expression many times. However, we always get the same value, because it is evaluated at most once:

{# x, x, x, x, x, x, x, x, x, x #}
where {
    x = random(1000);
};

{# 598, 598, 598, 598, 598, 598, 598, 598, 598, 598 #}

Future Wafl versions are considered to analyze whether the definition body is deterministic or non-deterministic. If the definition is non-deterministic, then its semantics can be defined differently, so that it is re-evaluated each time. In that case, the previous example could return different results. Non-deterministic behavior would include the use of random function, but also the use of files, network and so on.

2.8 The Order of the Definitions

The order of the definitions in the same scope (i.e. in the same where-block) is not significant. However, it is good to use either top-down or bottom-up strategy, to make the program more readable. A top-down strategy suggests defining the most abstract name first, even if it uses some other names, which are defined later. In contrast, a bottom-up strategy suggests introducing the simplest definitions first, and later using them in more abstract ones. For example, we define the same simple function three times (with different names), to demonstrate different styles:

{# topDown('a'), bottomUp('a'), noOrder('a') #}
where {
    topDown(x) = a
    where {
        a = b + b + x + c;
        b = c + x + c;      
        c = "#" + x + "#";  
    };

    bottomUp(x) = a
    where {
        c = "#" + x + "#";
        b = c + x + c;
        a = b + b + x + c;
    };

    noOrder(x) = a
    where {
        c = "#" + x + "#";
        a = b + b + x + c;
        b = c + x + c;
    };
}

{# '#a#a#a##a#a#a#a#a#', '#a#a#a##a#a#a#a#a#', '#a#a#a##a#a#a#a#a#' #}

The three definitions are equivalent to each other, but the last one is harder to read.

2.9 Conditional Expression if

In imperative programming languages it is common to have conditional statements and use them to control program execution flow. Wafl is a functional language and there are no statements in it, so in Wafl we have conditional expressions, instead.

Programming language Wafl has two kinds of conditional expressions: if and switch. Expression if includes a condition and two optionally evaluated expressions:

if <condition> then <then-exp> else <else-exp> 

where <condition> has to be an expression of a logical Bool type, while expressions <then-exp> and <else-exp> may be of any type, but must have the same type.

The conditional expression is evaluated first. If its value is true, then expression <then-exp> in then branch is evaluated and the resulting value is the result of the complete if expression. In other case, if <condition> evaluates false, then expression <else-exp> in else branch is evaluated and the resulting value is the result of the complete if expression.

{#
    if 5 > 2 then 'five' else 'two',
    if 5 < 2 then 'five' else 'two'
#}

{# 'five', 'two' #}

2.10 Conditional Expression switch

Conditional expression if evaluates one of the two alternative expressions. If more alternatives are required, we can use multiple if-expressions or switch-expression.

Expression switch consists of a conditional expression, at least one case clause and a mandatory default clause:

switch <cond-exp> {
    <case-clause>;
    <case-clause>;
    ...
    <default-clause>
}

The conditional expression is evaluated first. Then, based on the resulting value, one of the case clauses is selected and evaluated, or, if none is selected, default clause is evaluated. The result of the selected and evaluated clause is the result of the switch expression.

Each case clause begins with keyword case, followed by comma separated list of values. After the value list goes an expression, ended by semicolon:

case <literal>, ... <literal> [:] <exp>;

An optional colon symbol may separate value list from clause expression. Also, keyword case may be used instead of a comma as a separator and optional colon symbol may be used before it. So, case 1,2,3 is the same as case 1: case 2: case 3:.

Default clause is mandatory. It is defined as:

default [:] <exp> [;]

The following example uses both types of conditional expressions to calculate how many days there are in a given month:

{#
    daysInMonth( 1, 2000 ),
    daysInMonth( 2, 2000 ),
    daysInMonth( 2, 2001 ),
    daysInMonth( 2, 2004 ),
    daysInMonth( 2, 2100 )
#}
where{
    daysInMonth( month, year ) =
        switch month {
            case 2:
                if isLeapYear(year)
                    then 29
                    else 28;
            case 4, 6, 9, 11:
                30;
            default:
                31
            };

    isLeapYear(year) =
        year % 4 = 0
        and ( year % 100 != 0
              or year % 400 = 0 );
}

{# 31, 29, 28, 29, 28 #}

Conditional expression <cond-exp> is evaluated first. All case clauses are checked in order, to find if there is a literal equal to the conditional value. If such case clause is found, the corresponding expression is evaluated and its value is the result of the complete switch expression. If no specified literal is equal to <cond-exp> value, then default clause expression is evaluated and its value is the result of the complete switch expression.

There are three simple rules:

It is unusual to have so flexible syntax here, but it is introduced to provide both the syntactical similarity to C-like languages.

2.11 Recursion

Being a functional programming language, Wafl does not posses variables, so iterative processing is (almost) impossible. The main method to express “repetitive” behavior of functions is to use recursion.

Recursion is very significant technique, that allows a function definition to use the function itself. It is frequently used in mathematics, as a tool for defining indefinite (but still enumerable) structures.

The usual example of recursive definition in mathematics is definition of factorial. Factorial, usually denoted using postfix operator !, is defined as follows:

       0! = 1
(n+1)! = (n+1) * n!

The definition of each recursive functions is based on two main elements:

  1. recognition of the terminal condition i.e. when the arguments a allow non-recursive, direct evaluation of the result and

  2. definition of recursive evaluation in such a way that the application of each such step brings the evaluation closer to a terminal condition.

In the case of the factorials, the terminal condition is satisfied if the argument is zero. In that case, the result can be directly evaluated. In other cases, the result is defined based on the application of the same principles for smaller argument. Following these rules, we can evaluate n! in n+1 steps.

Another example of recursive definitions are Fibonacci numbers. First and second elements of the sequence are defined to be 1, while each other element is defined as a sum of two preceding elements:

Fib0 = 1
Fib1 = 1
Fibn+2 = Fibn+1 + Fibn

Both recursion elements are of great importance. We have to consider them carefully when recursion is used. If terminal condition is not well defined, it may be possible that evaluation of a recursive function never stops (or at least not in an acceptable time window) for some arguments. On the other side, if a recursive step is not well defined, then function efficiency may suffer for some arguments.

In the following example we define and use factorial function:

{#
    factorial(0),
    factorial(1),
    factorial(2),
    factorial(3),
    factorial(4),
    factorial(5),
    factorial(16)
#}
where{
    factorial( n ) = 
        if n<=1 then 1
        else n * factorial(n-1);
}

{# 1, 1, 2, 6, 24, 120, 20922789888000 #}

And now here is fib function, which evaluates a given element of Fibonacci numbers sequence:

{#
    fib(1),
    fib(2),
    fib(3),
    fib(4),
    fib(5),
    fib(6)
#}
where{
    fib( n ) = 
        if n<=2 then 1
        else fib(n-1) + fib(n-2);
}

{# 1, 1, 2, 3, 5, 8 #}

In imperative programming languages recursion is usually taught as an exotic technique. It is usually noticed that it looks nice, but that it is not efficient and may cause other problems. For example, deep recursion can break the organization of the internal memory of imperative programming languages (where “deep” usually means close to thousand or several thousand steps).

Do not worry about that in Wafl. As a functional programming language, Wafl relies on recursion as one of the elementary techniques. Feel free to use deep recursion, but take care - there will be no memory corruption, but very deep recursion still cause some problems because of a high memory usage. But in Wafl, “deep” is not measured in hundreds and thousands, here we are talking about hundreds of millions.

Knowing all that, it now may seem strange, but there are enough advanced constructs in the programming language that programmers in most cases do not have to iterate explicitly, and recursion is in reality not often used. We will discuss lists and higher order functions in the next chapter, and learn how to program efficiently.