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.
- A function is pure if is deterministic and do not have side effects;
- A function that is pure can be optimized by the compiler using internal cache and tail recursion;
- A function that use or modify a state variable or receive parameters by reference is not pure;
- A function that call another function that is not pure it is also not pure;
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.
|1||When in doubt, parameterize||When you are not sure make a new parameter instead of shared state variable.|
|2||Local is better then global||We use let to define local scope to avoid global scope declarations.|
|3||Group globals into records||Avoid using global variables. If you have them group several into a global record.|
|4||Favor loops over recursion||Recursive functions are hard to debug. Loops are more efficient and safe to use.|
|5||Avoid side-effects||Side-effects are difficult to comprehend. Pure functions are more safe.|
|6||Do not stay astray from left side||Deep code indentation makes code unreadable.|
|7||Do not be afraid of long programs||Do not create functions and libraries if not necessary. Level has support for very large program files.|
|7||Initialize early rather then later||Avoid differed initialization. Working with uninitialized references can be a source of run-time errors.|
In this chapter we will explain several additional features that makes Level a versatile language.
|01||dynamic functions||define functions using dynamic expressions|
|02||recursive functions||functions that can call themselves|
|03||dispatch||create multiple functions using same name and different signatures|
|04||closures||function that encapsulate another function|
|05||generators||function that can be interrupted and resumed to generate result on demand|
|06||type methods||bound methods to types using single dispatch|
|07||dynamic collections||list, map, set|
|08||set operators||union, intersection …|
|09||slicing technique||extract a subset from a set|
|10||new types||text, json, complex, rational|
|11||type casting||convert one type into other|
|12||type inference||use deduction to infer variable type|
|13||introspection||program know about himself (description, trace, type inquery)|
|14||regular expressions||for parsing a text or string|
|15||text templates||insert variable values into text|
|16||system storage||to create and open files|
|17||web services||application servers and back-end programming|
|18||internet services||internet and cloud based applications|
New data types
For Level2 we create new data types. One additional numeric type is “complex” number.
|Type Name||Short description|
|Unicode||This type is double quoted Unicode string|
|Text||This is double quoted string, that can contain Unicode strings|
|Complex||This is a new kind of number: complex number (a+i*b)|
|List||This is a new collection type that is a dynamic list.|
|Map||This is known a collection of pairs: (key,value) like a dictionary.|
|Set||This is a collection of elements. Each element is unique in the collection.|
In following table A, B are two sets and x is a member type: numeric or string
|x in A||logical||verify if x is a member|
|x not in A||logical||verify if x is not a member|
|C = A||modifier||initialize and clone A to C (deep copy)|
|A == B||logical||verify is all A is the same as B (A=B and B=A)|
|A <= B||logical||verify is A is subset of B|
|A >= B||logical||verify if B is subset of A|
|A ~= B||logical||verify if set A is not equal to set B|
|A += B||logical||modify set A is by adding new elements found in B|
|A -= B||logical||modify set A is by removing elements found also in B|
|A || B||set||Union of A with B, use like: C = A || B (return a new set)|
|A && B||set||Intersect A with B, use like: C = A && B (return a new set)|
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.
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 <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.
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.
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;
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.
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;
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 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.
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.
- 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;
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;
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.
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
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 );
Level2 add support for recursive functions:
--------------------------------------------------- -- 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.
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.
-- 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;
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.
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.
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;
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);
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.
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.
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” 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.
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.
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.
-- function signatures function sum(p1, p2: Real) => Real; !sum-real-real=>real function sum(p1, p2: Integer) => Integer; !sum-integer-integer=>integer
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.
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.
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