3 Programming With Functions

3.1 Strict Type Checking

Wafl is a strongly typed programming language. This means that Wafl requires a detailed and very strict type checking before program evaluation. Each function application must fully comply with the function type.

Strong type checking is usually paired with explicit declarations of name types. In Wafl, however, no explicit type declarations are required as the types are automatically inferred during the code analysis.

Due to the strict type checking, no implicit type conversions are allowed.

In the following example, we have a program with incorrect type usage. The addition operator is defined for various types, but it is not defined for operands of different types. An error is therefore reported:

1 + '2.0'

--- Loading: C:\Users\smalkov\AppData\Local\Temp\wafltmpfile_488229_0.tmp
Typechecking failed!
- Program   [Line: 2]
    The argument (2) type is not suitable for the context : 
        1+'2.0'   [Line: 2]
    The expression type is not suitable for the context: 
        '2.0'
        Exp.type not compatible with : Int
--- End loading: C:\Users\smalkov\AppData\Local\Temp\wafltmpfile_488229_0.tmp

The correct way to deal with such problems is to use explicit type conversions. This will be covered later in this tutorial.

3.2 Automatic Type Inference

Wafl is a strongly typed programming language. However, the Wafl syntax does not contain explicit type specification. All types are inferred implicitly. Normally, the inferred types are not displayed to user during program evaluation, but if a type error is detected during type checking, the related inferred types are reported.

In the following example, three local functions are defined:

• The function g is recognized to be of type (Float -> Float) (maps a single float argument to a float result);
• The function h is recognized to be of type (Int -> Int)(maps an integer argument to an integer result).
• The function f is not well defined because there is an addition operator a first operand of type Float and a second operand of type Int, but the implemented addition operator does not allow the different operand types.

f(7.0)
where{
    f(x) = g(x) + h(x); //  Type checking error!
    g(x) = sin(x);
    h(x) = x + 5;   
}

--- Loading: C:\Users\smalkov\AppData\Local\Temp\wafltmpfile_362105_0.tmp
Typechecking failed!
- f ( x ) : '2   [Line: 4]
    The argument (2) type is not suitable for the context : 
        g(x)+h(x)   [Line: 4]
    The result type is not suitable for the context: 
        h(x)   [Line: 4]
        Exp.type not compatible with : Float
--- End loading: C:\Users\smalkov\AppData\Local\Temp\wafltmpfile_362105_0.tmp

The error report contains some redundant data, as all branches of the type checking process are reported to allow a better understanding of the reported problems. If we read the report from the beginning, we can see all the actions that the type checker has performed:

• the attempt to check only type of the function f failed because f uses the names g and h whose types have not yet been inferred;
• the attempt to check the type of the function g inferred its type : (Float -> Float);
• the type of the function h is inferred also: (Int -> Int);
• it tried again to check the type of the function f and failed again because h(x) is not a valid usage in the context, which means that x is already assumed to have a non-float type;
• it tried again to check the type of the function f, but now in a wider context and failed for the same reason.

In most cases, it is better to read the report from the bottom. The last block of reported unrecognized types is the most important. Any line in the report beginning with OK: indicates that the given definition type is well inferred.

Reading from the bottom up, the error report shows that the type checking for Program and f fails and the problem is in the subexpression h(x). Further analysis shows that this is h(x) from the definition body of f.

3.3 Polymorphism

Polymorphism is the property of a function to be well defined for arguments of different data types. Implicit polymorphism is a very important feature of the Wafl programming language.

Type inference starts with the most general assumption that each of the local definitions is completely polymorphic, i.e. that any argument of any function can be of any data type. Step by step, the assumed polymorphic types are reduced to types for which expressions and definitions are applicable.

In the following example, two polymorphic functions add and sub are defined and used with arguments of different types:

{#
    add(1,2),
    add(1.3,2.3),
    add('a','b'),
    sub(5,1),
    sub(5.4,1.2),
    f(5,4,3),
    f(1.2, 3.4, 1.3),
    add( asFloat(add(1,2)), 3.1 )
#}
where{
    add(x,y) = x + y;
    sub(x,y) = x - y;
    f(x,y,z) = sub( add(x,y), z);
}

{# 3, 3.6, 'ab', 4, 4.2, 6, 3.3, 6.1 #}

The function add has the type (Value['1] * Value['1] -> Value['1]). This means:

1. it can be applied to arguments of any value type (Integer, Float or String);
2. both arguments must be of the same value type and
3. the result is of the same value type.

Similarly, the type of the function sub is inferred to be (Numeric['1] * Numeric['1] -> Numeric['1]). Thus:

1. it is applicable to arguments of any numeric type (Integer or Float);
2. both arguments must be of the same type and
3. the result is of the same type.

Both Numeric['1] and Value['1] are so-called combined data types. They can be further reduced to different primitive data types. The type '1 stands for a polymorphic type name, like a type variable. Identical polymorphic type names in a type must be reduced to identical specific types in each specific function application.

In each particular function application, the function type must be reduced to a non-polymorphic data type. However, different applications of the same polymorphic function can be reduced to different types in a program. When used in function definitions, polymorphic functions can be used in a polymorphic way, without further reduction of the data types, or with reduction to a more specific but still different polymorphic type. Their types are further reduced if the application of the defining function makes this necessary.

The function f in our example is defined as:

f(x,y,z) = sub( add(x,y), z);

and its type is inferred as (Numeric['1] * Numeric['1] * Numeric['1] -> Numeric['1]). Thus:

1. it is applicable to three arguments of any numeric type (Integer or Float);
2. all arguments must be of the same type and
3. the result is of the same type.

The function f uses both add and sub. In the specific application, the type of the function add is reduced from Value['1] to Numeric['1], while the type of the function sub is not reduced any further.

It is important to note that each specific application is reduced independently of the other applications. Therefore, in the same example, our function add is successfully applied to a pair of integers, a pair of floats and a pair of strings, and the functions sub and f are successfully applied to integers and floats. Also, in the last expression, the function add is applied to both integers and floats.

3.4 Higher Order Functions

One of the essential features of functional programming languages is that functions are treated as first-order citizens. Functions can be used as arguments and results of other functions, in a much simpler way than in the most imperative languages.

The functions that take functions as arguments or return a function as a result are called higher order functions. They are essential for functional programming.

In the following simple example, the function double is used as an argument to the function apply:

apply(double,2)
where{
    apply(f,x) = f(x);
    double(x) = x + x;    
}

4

The function double has the type (Value['1] -> Value['1]). It is similar to the add function from one of the previous examples.

The function apply has the type (('1 -> '1) * '1 -> '1). This means:

• its first argument must be a unary function of type ('1 -> '1);
• its second argument must be of type '1,
• its result is of type '1 and
• the type variable '1 can be replaced by any type, but in the same time in all previous assertions.

In the given example, the function apply applies the function double to 2. In this particular application, the type variable '1 is replaced by Int.

More complex examples follow later.

3.5 Partial Application

A partial application is any function application where not all expected arguments are specified.

For example, if we were to specify only the first argument of the add function (from the previous examples), the result would be a unary function that returns its argument incremented by one.

One way to do this is to define a new function:

f(x) = add( 1, x );

Another possibility is to use a partial application:

f = add(1,_);

In Wafl, the syntax of the partial application is similar to a regular function call, but the underscore ‘_’ is used instead of unspecified arguments. You must always use as many arguments as the function expects, but some of the arguments can be specified and others can be left unspecified.

The result of a partial application is a function. Its arguments correspond to the unspecified arguments of the partial function application, in the preserved order.

It is possible to leave all arguments unspecified. However, this is not very useful as the result is the function itself.

In the following example, several partial applications are used:

{#
    strGetFirst5a( "1234567890" ),
    strGetFirst5b( "1234567890" ),
    charAt( "123456", 1 ),
    charAt( "123456", 2 ),
    add2( 5 ),
    // The following expressions give the same result
    subStr( "1234567890", 5, 3 ),
    subStr( _, 5, _ )( _, 3 )( "1234567890" )
#}
where{
    // The following definitions are identical.
    // Both functions return
    // the first 5 characters of a string.
    strGetFirst5a( s ) = strLeft( s, 5 );
    strGetFirst5b = strLeft( _, 5 );

    // charAt(n) returns the nth character of a string.
    charAt = subStr( _, _, 1 );

    // twice(f,x) applies f twice to x
    twice( f, x ) = f( f(x) );
    // inc(x) returns x incremented by 1
    inc(x) = x + 1;
    // add2 returns its argument incremented by 2
    add2 = twice( inc, _ );
}

{# '12345', '12345', '2', '3', 7, '678', '678' #}

In many functional programming languages, a partial application is implemented by specifying only the first argument of a function (or, more generally, some of the arguments from the beginning of the argument list, in the appropriate order). This approach is called curried functions. The result of a curried partial application is a function that maps the remaining arguments to the result.

The partial application, as implemented in Wafl, is more general than curried functions.

3.6 Lambda Functions

In functional programming languages, the term lambda function refers to various concepts for defining unnamed functions at the place where they are used.

When we use higher-order functions, we often have to specify a function as an argument that is not needed elsewhere. If we use a function only once in a program, it is easier and often more readable to define it inline than to introduce a regular function definition.

In the Wafl programming languagewe define lambda functions in the following form:

A lambda function can appear at any point where we can use a regular function name. Sometimes it is necessary to put the lambda function in parenthesis to clarify the syntax.

In our first lambda example, we define and use an unnamed function that returns its argument incremented by 1:

(\x:x+1)(41)

42

This function is the same as the inc function from the previous examples, but now it is defined as a lambda and used in the place of the definition. This is much shorter than using a full definition syntax, as in the following example:

inc(41)
where {
    inc(x) = x+1;
}

42

For the first time, let us define a function that takes only functions as arguments and returns a new function as a result. The function combine takes two functions as arguments. It returns a unary function that applies the combined functions to its argument. The following expression should therefore always evaluate to true:

combine(f,g)(x) == f(g(x))

One way to write combine is to first define an auxiliary function c that takes three arguments f, g and x and returns their partial application:

combine = c(f,g,_)
where {
    c(f,g,x) = f(g(x));
}

A simpler way is to use lambda instead of the definition of the function c, but the solution is equivalent:

{#
    add2(1),
    add3(1),
    combine( inc, inc )(10),
    combine(\x:x+1,\x:x+1)(10)
#}
where{
    combine( f, g ) = ( \f,g,x : f(g(x)) )( f, g, _ );
    add3 = combine( add2, inc );
    add2 = combine( inc, inc );
    inc(x) = x + 1;
}

{# 3, 4, 12, 12 #}

In the following example, we use combine to define the function repeat that generalizes twice from the previous examples. For a given function f and a given integer n, repeat returns a function that applies f to its argument n times. In repeat we use the lambdas to write the identity function, and in the main expression we use a lambda equivalent of the function inc:

{#
    repeat( \x:x+1, 0 )( 100 ),  
    repeat( \x:x+1, 1 )( 100 ),
    repeat( \x:x+1, 10 )( 100 )   
#}
where{
    repeat( f, n ) =
        if n=0 
            then \x:x 
            else combine( f, repeat(f,n-1) );
    combine( f, g ) = ( \f,g,x : f(g(x)) )( f, g, _ );
}

{# 100, 101, 110 #}

Note that this implementation of repeat is not very efficient. However, it shows how higher-order functions can be combined with lambdas to achieve very interesting goals.

3.7 Lambda Closures

In functional programming languages, a closure is a function that binds some elements of its outer scope. We can say that partial applications are a kind of closures.

Let us go back to the definition of the function combine. We can say that combine binds the given functions f and g in a closure:

combine( f, g ) = ( \f,g,x : f(g(x)) )( f, g, _ );

Definitions like this are very common: first we need to define a function with multiple arguments and then create a closure by partially applying this function. It seems like we write the same things twice.

Fortunately, we can use lambda closures (or lambdas with bindings), to create closures more easily. To define a lambda closure, we need not only the lambda arguments, but also the list of names from the definition space that we need to bind. These names are listed in square brackets, after the lambda arguments:

There is an alternative, older syntax for the same thing, where a hash symbol ‘#’ is used to separate the list of lambda arguments from the list of bound names:

Now we can define the function combine even more easily than before with the help of a lambda closure:

{#
    combine(\x:x+1,\x:x+1)(10),
    combine(operator+(2,_), operator*(8,_))(5)
#}
where{
    combine( f, g ) = \x [f,g]: f(g(x));
}

{# 12, 42 #}

3.8 Operators as Functions

The syntax for partial application is not applicable to operators. Furthermore, operators cannot be used as arguments for function application. For this reason, Wafl introduces the functional syntax of operators. Each operator has a corresponding equivalent function. If there is an operator <op>, then there is also the corresponding function operator<op>, with the same number of arguments and the same type.

The following example shows how we can use the functional syntax of operators to partially apply the operator ‘+’:

{#
    operator+( _, 'b' )( 'a' ),
    operator+( 'a', _ )( 'b' ),
    apply( operator+( _, 5 ), 10 ),
    apply( operator+( _, 5 ), _ )( 10 ),
    apply2( operator+, _, _ )( 5, 10 ),
    apply2( _, 5 ,10 )( operator+ )
#}
where{
    apply( f, x ) = f( x );
    apply2( f, x, y ) = f( x, y );
}

{# 'ab', 'ab', 15, 15, 15, 15 #}

3.9 Dot Operator

Due to the functional semantics of subroutines, the source code of programs written in functional programming languages is very often quite unreadable.

For example, consider the following definition of the function g. For a given string s, it extracts a substring starting at position 5 of length 8, then replaces each ‘a’ with ‘B’, then replaces each ‘b’ with ‘A’, and finally converts the string to lowercase. Basically, it is a very simple function, but it is very unreadable, no matter how carefully we indent the code:

g(s) = 
    strLowerCase(
        strReplaceAll(
            strReplaceAll(
                subStr(s,5,8),
                'a','B'
            ),
            'b','A'
        )
    );

Wafl tries to solve the problem by introducing a dot operator ., which is very similar to the object-oriented dot syntax. In short, any function that is defined for at least one argument can be used with more than just the usual syntax:

but also using the dot syntax, where the function application is written as an OO method of the first argument:

These two syntaxes have the same semantics. Programmers are free to use both and choose the best one for each case.

Using the dot syntax usually leads to better readable source code. In the following example, we define two equivalent functions. For f we use the dot syntax and for g we use the usual syntax of the function application.

{#
    f( 'abcdABCDabcdABCD' ),
    g( 'abcdABCDabcdABCD' )
#}
where{
    f(s) = 
        s.subStr(5,8)
        .strReplaceAll('a','B')
        .strReplaceAll('b','A')
        .strLowerCase();

    g(s) = 
        strLowerCase(
            strReplaceAll(
                strReplaceAll(
                    subStr(s,5,8),
                    'a','B'
                ),
                'b','A'
            )
        );
}

{# 'bcdbacda', 'bcdbacda' #}

Transformational Semantics

A consecutive use of dot syntax can represent an application of transofrmational semantics. Each application of the dot syntax represents a single transformation step that transforms its first argument into the result of the applied function. The entire sequence applications of the dot operator represents a series of such transformation steps.

In the last example, the function f is defined as a series of transformations of the input string x. Four successive transformations are applied to calculate the result of the function.

To enable such applications, in view of the dot syntax, any function that has a main argument and can be regarded as a kind of transformation of this argument, should be defined so that the main argument is the first one.

Continuation Operator

The dot operator has the highest priority. The only operators with higher precedence are the library referencing operator ‘::’, the record/tuple element selector ‘$’ and the record/tuple element update operator ‘^’. In the following example, the abs function is used via the dot operator before the multiplication:

-3 * 2 .abs()

-6

The high precedence of the dot operator often requires the use of parentheses around the preceding expression. To avoid annoying parentheses, Wafl supports the arrow operator ‘=>’, which behaves very similarly to the dot operator, with the only difference that it has the lowest precedence.

If we replace ‘.’ with ‘=>’ in the previous example, then the application of the function abs has the lowest priority and is only evaluated after the entire previous expression has been evaluated:

-3 * 2 => abs()

6

The lowest precedence means that there is no other operator or syntax construction with a higher priority. For example, the function echoLn in the next example is not only applied to the preceding else expression, but to the entire if-then-else expression:

if 3>2
  then 3
  else 2
=> echoLn() 
+ 1

3
4

Alternative Syntax - Arrow Operator

In the first Wafl versions, this technique was called arrow syntax and the operator ‘->’ was used instead of ‘.’. In the current version, the operators ‘->’ and ‘.’ are equivalent. However, we recommend using the dot syntax. The arrow operator may no longer be supported in some of the future versions. This old arrow operator ‘->’ should not be confused with the new arrow operator ‘=>’.

3.10 Explicit Computation State

A few sections earlier, there was an example of Fibonacci numbers:

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

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

This is an interesting example of recursive programming. However, even a simple analysis shows that this approach is very inefficient. The problem is that the function is evaluated over and over again for the same numbers. Let us analyze the case of fib(6):

fib(6)
 -> fib(5) + fib(4)
     |        -> fib(3) + fib(2)
     |            |        -> 1
     |            -> fib(2) + fib(1)
     |                -> 1     -> 1
     -> fib(4) + fib(3)
         |        -> fib(2) + fib(1)
         |         -> 1     -> 1
         -> fib(3) + fib(2)
             |        -> 1
             -> fib(2) + fib(1)
                 -> 1     -> 1

As we can see: fib(6) is evaluated once, fib(5) once, fib(4) twice, fib(3) three times, fib(2) 5 times and fib(1) 3 times. We see that this sequence corresponds to the Fibonacci number sequence, except for the last step: 1, 1, 2, 3, 5, 3. Since only calls to the lowest level return the exact value, it is easy to conclude that for any n the total number of evaluations of fib(2) and fib(1) is equal to fib(n). And this grows rapidly, approximately with ϕⁿ, where ϕ is the golden ratio (1.61803…).

So our function fib becomes very slow for large numbers. How can we improve this? The formula shows that we should keep the last two results during the computation. This is relatively easy to do in imperative programming. In C/C++, for example, we can do something like the following:

unsigned fib( unsigned n ) {
    unsigned prev2=1, prev1=1, result=1;
    //  for n=0 and n=1 result is already ok
    //  result == 1 == fib(0) == fib(1)
    //  prev1 == 1 == fib(1)
    //  prev2 == 1 == fib(0)
    for( int i=2; i<=n; i++ ) {
        result = prev1 + prev2; // result = fib(i)
        prev2 = prev1;          // prev2 = fib(i-2)
        prev1 = result;         // prev1 = fib(i-1)
    }
    return result;  
}

But in Wafl we do not have variables, so it’s not as simple as in C++. There is no implicit computation state, and the only way to pass the computation state is to do it explicitly. One solution could be to pass the same state as in the C++ example with every recursive call:

{# fib(1), fib(2), fib(3), fib(4), fib(5), fib(6), fib(7) #}
where {
    fib(n) = if n <= 2 then 1 
             else fib_s(1,1,2,n);
    fib_s(p1,p2,i,n) = if i=n then p2
                       else fib_s(p2,p1+p2,i+1,n);
}

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

If we check this carefully, we can remove the constant factor n from fib_s and get a better solution:

{# fib(1), fib(2), fib(3), fib(4), fib(5), fib(6), fib(7) #}
where {
    fib(n) = if n <= 2 then 1 
             else fib_s(1,1,n-2);
    fib_s(p1,p2,i) = if i=0 then p2
                     else fib_s(p2,p1+p2,i-1);
}

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

However, it is not hard to see that this approach to the problem is not so nice.

3.11 Cached Functions

Another approach to exponentially growing recursion is to memorize the previous results. Cached functions can help here.

Cached functions is a Wafl technique to memorize the previous results of a function. If we have a fast growing recursion tree, as in the case of fib, or if we have a function that is computed very often for the same arguments, then we can suggest that this function should have its results cached.

The syntax is simple:

<name>(<args>) = cached <exp>;

If we try to use it with fib, then it becomes:

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

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

When we test this solution with larger numbers, we see that it is much faster than the original solution, but that the previous solution with explicit state transfer is still more efficient. This is no surprise - the problem is that the cached solution has to store the computed results and search for the previously stored result. However, if we apply fib over and over again to the same range of numbers, the cached solution becomes much more efficient than any other.

And it is easy to use, which is a big advantage.