Menu Close

Articles

Level: Functional Programming

In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data. It is a declarative programming paradigm, which means programming is done with expressions and declarations instead of structured statements.

Functional programming:

By using functional programming we enable code optimization technique not available for structured programming. This is an optional feature that is implemented by alternative compilers to generate better executable code.

 function rules.

  1. A function is pure if is deterministic and do not have side effects;
  2. A function that is pure can be optimized by the compiler using internal cache and tail recursion;
  3. A function that use or modify a state variable or receive parameters by reference is not pure;
  4. A function that call another function that is not pure it is also not pure;

Design principles

Level is designed for _sage code_ programming. To use Level correctly developers must understand some basic design principles. These are part of _sage code_  good practice.

#The principleDetails
1When in doubt, parameterizeWhen you are not sure make a new parameter instead of shared state variable.
2Local is better then globalWe use let to define local scope to avoid global scope declarations.
3Group globals into recordsAvoid using global variables. If you have them group several into a global record.
4Favor loops over recursionRecursive functions are hard to debug. Loops are more efficient and safe to use.
5Avoid side-effectsSide-effects are difficult to comprehend. Pure functions are more safe.
6Do not stay astray from left sideDeep code indentation makes code unreadable.
7Do not be afraid of long programsDo not create functions and libraries if not necessary. Level has support for very large program files.
7Initialize early rather then laterAvoid differed initialization. Working with uninitialized references can be a source of run-time errors.

Language Features

In this chapter we will explain several additional features that makes Level a versatile language.

#NameDescription
01dynamic functionsdefine functions using dynamic expressions
02recursive functionsfunctions that can call themselves
03dispatchcreate multiple functions using same name and different signatures
04closuresfunction that encapsulate another function
05generatorsfunction that can be interrupted and resumed to generate result on demand
06type methodsbound methods to types using single dispatch
07dynamic collectionslist, map, set
08set operatorsunion, intersection …
09slicing techniqueextract a subset from a set
10new typestext, json, complex, rational
11type castingconvert one type into other
12type inferenceuse deduction to infer variable type
13introspectionprogram know about himself (description, trace, type inquery)
14regular expressionsfor parsing a text or string
15text templatesinsert variable values into text
16system storageto create and open files
17web servicesapplication servers and back-end programming
18internet servicesinternet and cloud based applications

New data types

For Level2 we create new data types. One additional numeric type is “complex” number.

Type NameShort description
UnicodeThis type is double quoted Unicode string
TextThis is double quoted string, that can contain Unicode strings
ComplexThis is a new kind of number: complex number (a+i*b)
ListThis is a new collection type that is a dynamic list.
MapThis is known a collection of pairs: (key,value) like a dictionary.
SetThis is a collection of elements. Each element is unique in the collection.

New operators

In following table A, B are two sets and x is a member type: numeric or string

OperatorResultDescription
x in Alogicalverify if x is a member
x not in Alogicalverify if x is not a member
C = Amodifierinitialize and clone A to C  (deep copy)
A == Blogicalverify is all A is the same as B  (A=B and B=A)
A <= Blogicalverify is A is subset of B
A >= Blogicalverify if B is subset of A
A ~= Blogicalverify if set A is not equal to set B
A += Blogicalmodify set A is by adding new elements found in B
A -= Blogicalmodify set A is by removing elements found also in B
A || BsetUnion of A with B, use like: C = A || B (return a new set)
A && BsetIntersect A with B, use like: C = A && B (return a new set)

Functions

A function is a named section that use several parameters to calculate one single result. Functions can be defined as members in other section: program, module, procedure or function. In Level-2 we can define static functions and dynamic functions.

Static Functions

Usual functions are defined in the declaration region of a section. These functions are called static functions. Static functions can have side-effects and can modify outer scope variables. These functions are legacy functions available in Level-1 and behave exactly the same.

Function syntax:

function <func_name>(<param> type[,<parame> type]...) => <result_type> is
  <declaration_region>;
begin
  <execution_region>;
  ...
  [result:<expression>]; 
  ... 
  [return result];
  ...
  [return];
[recover]
  <recover_region>;
[finalize]
  <finalization_region>;
end function;

Reference to function

We can define a reference to a function using pointer notation @Function. We can create a variable that is holding a reference to a function. With this notation we enter in functional programming. Reference to function can be stored in a map to create dynamic programs. Then we can call the function by name string instead of hard-coded name. The same effect can be achieved using a switch statement.

Dynamic functions

These are functions created during run-time in the executable region. We assign a function to a variable of type @function then we can use the variable name as a function. Dynamic functions can be created in the main program or can be result of a static function. Dynamic functions are first class objects.

Example:

program example() is
  c=0: Integer;
  p=1.5: Real;
  f: @Function;
begin
  -- dynamic function
  f: function(a:Integer, b:Integer) => Real is
  begin
    return a+b+p;  
  end function;
  c=f(12,10);   --> 23.5
end program;
Note: Reference to procedure is not possible. If we attempt to assign an existing procedure to a function reference the compiler should rise and error. This is a protection to avoid calling a procedure in an expression. Procedure do not have results.

Variable binding

Local variables are bind to functions with the current value. If the local variable change value after the function was created the function is using the previous value and disregard the current value. This is a protection of functions against the side-effects.

Dynamic functions can be executed outside of parent scope where the function was initially created. The function become an independent object. This is possible since the function have no dependency on scope variables. All variables including outer scope variables are encapsulated in the function context.

Functional Programming

Here are some functional programming design patterns.

  • A static function can create a dynamic function;
  • A procedure can create a dynamic function;
  • Functions bind all outer scope variables;
  • Functions do not have side-effects;
  • Functions can be assigned to function references;
  • Functions can be accepted as arguments to other functions;

Function call

The call for a function is using name of the function and round brackets (). The brackets are mandatory to call a function. If the brackets are missing the compiler will raise a compilation error. Inside brackets we can enumerate argument values.

Arguments

Arguments can be pass by value or by reference. We can declare parameters using pointer notation ” @type” then we can pass an arguments by reference. This may improve performance and does not make the function impure. Using this parameter type a function can be used to return multiple results.

Function result

Functions are computing one single result. A function can’t produce 2 results in the same time. We declare implicit “result” variable having the same type as the function. The result type is defined using symbol “=>”. Result variable can be used in expressions.

Result of the function is created using “result:=expression;” After this statement all other statements are executed then the result is communicated to the caller. When function is terminated local variables are removed from memory.

Note: The result of a function must be always captured into an expression or variable. If result need to be ignored then a dummy variable can be used to capture the result. If this is not convenient then we define a procedure instead.

Early termination:

  • A function normally terminates at the end of finalize region;
  • Return keyword can be used to terminate function early;
  • Exception can interrupt a function execution prematurely;

Example of function call

procedure example is
  c:Integer;
  -- static function declaration
  function sum(a, b:Integer) => Integer:
  begin
    return a+b;
  end function;
  -- reference declaration
  func @Function;   
begin
  c := sum(10,20);  -- function call
  print(c);         -- this will print 30
  func: sum;        -- assign a function reference
  c := func(10,20); -- call a function using reference
end procedure;

=> 30

Optional Parameters

Function parameters can be defined using assignment operator (=) to have “default values”. These parameters are also optional parameters and can be omitted from the function call.

Parameter values can be pass by position or by parameter name. Passing parameter by name can specify parameters in different order then initially defined in procedure. Also optional parameters may be skipped.

Example of function declaration with optional parameters

procedure main is
  c:Integer;
  sum: @function;
begin
  sum=function(a=0:Integer, b=0:Integer) => Integer is
  begin 
     return (a+b); 
  end function; 
  c=sum();      --call function using default values a=0, b=0
  print(c);     --will print 0
  c=sum(b:123); --pass only second parameter by name (using pair-up)
  print(c);     --will print 123
end procedure;

=> 0

=> 123

Recursive Method

Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other, the nested images that occur are a form of infinite recursion.

Recursive Algorithm

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration). The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science

Recursive Structure

An important application of recursion in computer science is in defining dynamic data structures such as lists and trees. Recursive data structures can dynamically grow to a theoretically infinite size in response to runtime requirements. In contrast, the size of a static array must be set at compile time.

-- example of recursive list of nodes in Level1
Type Node Record of (
  data int,     --integer data
  child @Node,  --reference to next node
  parent @Node  --reference to previous node
);

Recursive Function

Level2 add support for recursive functions:

Factorial example:

---------------------------------------------------
-- input: integer n such that n >= 0
-- output: [n × (n-1) × (n-2) × … × 1]
---------------------------------------------------
function factorial(n Integer) => Integer is
begin
  if n == 0 then
    result:=1
  else
    result:= n*factorial(n-1);
  end if;
end function;

Note: In general a recursive algorithm is slower then loops but programs looks better. Any recursve algorithm can be replaced by using a loop and a stack. A List has stack features so it can be used for this purpose.

Closure Function

A closure is a dynamic function that can created by another function. By using closures we can create stochastic functions that can return a different result for every call. This is advanced functionality that is tipical to functional languages.

Syntax:

-- define a closure factory
function <factory_name>() => @Function is
begin
  -- define a closure (named when created)
  result:=function() => <type> is
  begin
    pass;
  end function;
end function;

Context

Closure is an encapsulated object in memory. The outer scope of enclosed function must remain available and is not removed from memory as long as the inner function has active references. When all the active references are out of scope then the closure context is removed from memory.

Using closure

A closure must be initialized using “:” operator. After you declare a closure you must call it’s factory function at least one time to create the closure “instance”. A closure instance is a reference to a function and can be local or global.

Example:

program test_closure(s:String, a,b:Integer, c,d:Real) is
  -- higher order function: factory
  function factory(min, max :Integer) => @function
    m:Integer; 
  begin
    -- transfer "min" to context
    m:=min; 
    -- create and return a closure 
    result:= function() => Integer is
    begin
      if m > max then
        result:= -1; 
      else
        result:= m; --> return current m
      end if;
      m+=1; --> increment m in context
    end function;
  end function;
begin -- main
  -- first test case
  let
    test:Integer;
    closure=factory(1,10);
  loop
    when test<0 then exit;
    test=closure();
    print(test);   -- will print from 1 to 10
  end loop;
  -- second test case
  let
    test:Integer; -- function result    
    closure=factory(100,105);  -- implicit type @function
  loop
    when test<0 then exit;
    test=closure();
    print(test);   -- will print from 100 to 105
  end loop;  
end program;

Generator Function

A generator is a special kind of closure that do not terminate automatic after first call. Instead it’s instance is preserved in memory for a while until the last result is created. A generator is a “producer function” that can create results on demand.

Like all good things a producer can be exhausted and then will terminate. It’s last result can’r be established so we include several built-in methods fro generator functions:

  • next(g @generator);
  • finish(g @generator);

Example:

program generator_example() is
  #Create a generator
  generator test(p_stop:Integer) => Integer is
    counter:Integer;
  begin
    loop
      exit when counter > p_stop;
      yield counter;
      counter +=1;
    end loop;
  end generator;
begin
  -- example 1 generator:"aindex"
  print("call generator using for");
  let
    index=test(3);
  job
    for i in index() loop
      output("i=#n" <- i);
    end loop;
  end job;
    
  -- example 2 generator:"bindex"     
  print("call generator using loop");
  let
    index=test(3);
  loop
    exit when index.end;
    output("y=#n" <- next index);
  end loop;
  print("done.");
end program;

This will print:

call generator using for
i=0, i=1, i=2, i=3,
call generator using loop
i=0, i=1, i=2, i=3, 
done.

test()

This is a resume function that will stay in memory and wait for next() to be invoked. When the last element is generated the function terminate. A generator function is a “high order function” and must be instantiated with a parameter.

index generator

I have created two local generators named “index” using the same function test(). First generator is used into a for loop like an iterable collection. Not all values are generated in memory but one by one. This is very efficient.

For second generator I have used next(index) to create all values untile finish(index) return true. Every time next() is invoked a new value is created until all values are printed.

Note: The generator is persistent in current block. A generator is free from memory when it’s reference is out of scope.

Keyword yield

Keyword “yield” is specific to generators. This is like a return, except the function do not terminate. Instead the execution is suspended and resumed using next(). One single generator can use many yield statements or it can be in a loop like in previous example. When next() is invoked the program continue with first statement after yield.

Type Dispatch

Definition: dispatch = send off to a destination or for a purpose. We use dispatch to create multiple versions of the same sub-program using parameter types. This means we can create in the same program scope two procedures or functions with the same name.

Function signature

A subprogram or section that is using dispatch have an internal code that represent the procedure. This internal code is created automatically by the compiler using section name and parameter types in order.

Signature example:

-- function signatures
function sum(p1, p2: Real) => Real; !sum-real-real=>real
function sum(p1, p2: Integer) => Integer; !sum-integer-integer=>integer

Single dispatch

In single dispatch only the first parameter is used for differentiation of function signatures. This is used in object oriented programming paradigm. We use single dispatch in Level-3.

Multiple dispatch

In multiple dispatch all non optional parameters are used for differentiation of section signature. For function the result type is also included into the function signature. Multiple dispatch is an appreciated feature in functional programming.

Optional parameters can be missing from a call. In this case we can’t dispatch by argument type. Optional parameters are specified last in the list of parameters and can’t be used to dispatch the signature.

Variadic parameters

We can use suffix “*” to create variadic parameters. This is the last parameter of a procedure or function. There is a special collection we can use to retrieve the variadic arguments into a List of arguments. This argument can be used in function signature.

Multiple dispatch example:

program test_variadic_dispatch is
  -- initial function func
  function func(arguments* :Integer) => :List of Integer is
  begin
    result=[x | x in arguments];
  end function;
  -- overloaded function func 
  function func(arguments* Real)  => :List of Real
  begin
    result=[x | x in arguments]; 
  end function;    
work  
  -- use declare 2 local Lists
  let 
    c:[] List of Integer; 
    d:[] List of Real;
  job
    $c=func(10,1,2,3,4,5);       --> [10,1,2,3,4,5]
    $d=func(10,1.1,2.5,3,4,5.5); --> [10.0,1.1,2.5,3,4,5.5]
  end job;
end program;

Read next: Level: Dynamic Collections