MENTAL
 Main Menu
 Applications
 Computer Science
 Functional Programming

Functional Programming
 FUNCTIONAL
PROGRAMMING

Is it possible to free von Neumann programming style?(John Backus).

"What was new and essential to all mathematics was the entirely general conception of function" (Dedekind).


The Functional Paradigm

The functional paradigm of programming is based on using a single concept (or conceptual primitive): the function, in the mathematical sense of the term. It was born as a reaction to the imperative paradigm. John Backus has been one of the prime movers of functional programming semantics, criticizing the concept of variables and the concept of assignment statements, claiming that they are the root of many evils and a "curse" transmitted by the von Neumann model [Backus, 1978].


Features of the functional paradigm
Limitations of the functional paradigm

The exclusive application of the functional paradigm leads to serious expressive difficulties:
Specification in MENTAL

Function definition

A function f is an expression dependent on one or more parameters that, when evaluated with the same arguments always produces the same result.
Ways to specify and evaluate functions

There are many ways to specify and evaluate functions: directly (unnamed), named, with and without formal parameters, with or without deferred evaluation, with absolute or relative substitutions, with partial or total evaluation, etc.
Examples of functions with parameters

In the following examples, for clarity, we are going to use parameterized generic expressions to define functions.
  1. Fibonacci series.
    Produces a sequence with the n first numbers of the Fibonacci series.

    ⟨( fibo(n) = ( (n=1 → ¡1 )
    (n=2 → ¡(1 1)))
    (s = fibo(n−1)))
    ¡(s↓ (s\(s#) + s\(s#−1))))
    )!
    )⟩

    fibo(1) // ev. 1
    fibo(2) // ev. (1 1)
    fibo(3) // ev. (1 1 2)
    fibo(8) // ev. (1 1 2 3 5 8 13 21)

  2. Conversion of a sequence x of binary digits to a decimal number.
    The procedure consists of multiplying the first digit by 2 and adding the second, multiplying the result by 2 and adding the third, etc., until the last digit is added. For example, 1011 = ((1*2 + 0)*2 + 1)*2 + 1.

    ⟨( bindec(x) = ( (r = 0)
    [(r = (r*2 + x\[1...x#]))]
    ¡r )! )⟩

    bindec(1011) // ev. 11

  3. Conversion of a positive integer n to a sequence of binary digits.
    The procedure consists of dividing the number n by 2, the quotient is divided again by 2, etc. until the quotient is 1. Then the last quotient is taken and all remainders are taken in reverse order. Example for the number 19:

    Oper.QuotientRestResult
    19÷291←10011
    9÷241←
    4÷220←
    2÷21←0←

    ⟨( decbin(n) = ( (s = ()) // initial result sequence

    (m = n)

    ( (c = m÷2)) // quotient

    (c=1 → ¡(c s↓))

    (r = remainder(m 2)) // remainder

    // include remainder at the beginning of the sequence

    (s = (r s↓))

    (m = (m = c) )★ )! )⟩

    decbin(19) // ev. (1 0 0 0 1 1 1)

  4. Function that returns "S" if n is prime and "N" otherwise.

    ⟨( prime(n) = ( n≤3 → ¡"S")
    ((remainder(n 2) = 0) → ¡"N")
    [ (i = [(3 ... nv2)])
    ((remainder(n i) = 0) → ¡"N") ]
    ¡"S" )! )⟩

    Being

    ⟨( remainder(n1 n2) = n1 - (n1÷n2)*n2 )⟩

    the remainder of the division between two integers. The expression nv2 is the integer part of √n

Recursive functions

These are functions that call themselves. The use of recursion greatly simplifies the definition of functions.

A representative example is the breadth and depth paths of a tree. If we have the tree


ie,

( tree = ( (a b) (a c) (a d)
(b e) (b f) (c g) (d h) (d i) ) )

or, alternatively, using the distribution,

( tree = ( [(a [b c d])]
[(b [e f])] (c g) [(d [h i])] ) )

where (x y) represents the branch of the tree from node x to node y

Extent tree path (node is the root node):

⟨( amplitude(tree node) = (
(s = (⟨ (x ← (node x)∈tree ⟩) // sequence of child nodes.
(¡( node ) ← s=() →'
¡( node s↓ [amplitude(tree [s↓])↓] )
)! )⟩

amplitude(tree a) // ev. (a b c d e f f g h i).
amplitude(tree b) // ev. (b e f)
amplitude(tree e) // ev. ( e )

Tree traversal in depth (node is the root node):

⟨( depth(tree node) = (
(s = (⟨ (x ← (node x)∈tree ⟩) // sequence of child nodes.
(¡( node ) ← s=() →'
¡( node s\1 [depth(tree ([s ∪' s\1])↓] )
)! )⟩

depth(tree a) // ev. (a b e f c g d h i).
depth(tree b) // ev. (b e f)
depth(tree e) // ev. ( e )


Tables

A table is a particular case of a function in which there is an explicit and direct correspondence between each argument and its result.

Examples:
  1. A function and defined on an argument x:

    xy
    12
    27
    35
    rest8

    '⟨( y(x) = (2 ← (x=1) →'
    (7 ← (x=2) →'
    (5 ← (x=3) →' 8)))) )⟩
    y(2) // ev. 7
    y(4) // ev. 8
    y("abc") // ev. 8

  2. Function z of two arguments (x, y) where α indicates "any expression":

    xyz
    00a
    01b
    α0c
    1αd

    ⟨( z(x y) = ((a ← (x=0 → y=0) →'
    ((b ← (x=0 → y=1) →'
    ((c ← y=0) →'
    (d ← x=1)))) )⟩
    z(3 0) // ev. c
    z(1 3) // ev. d
    z(3 3 3) // ev. θ (function not defined for arguments)

  3. Function f of two arguments (x, y) that produces a sequence of two variables (u, v) with their values:

    xyuv
    aa27
    ba34
    cb16
    db59

    ⟨( f(x y) = ((x=a → y=a → ¡((u = 2) (v = 7)))))
    (x=b → y=a → ¡((u = 3) (v = 4))))
    (x=c → y=b → ¡((u = 1) (v = 6))))
    (x=d → y=b → ¡(((u = 5) (v = 9))))) )⟩

    f(c b) // ev. (u=1 v=6)
    f(0 0) // ev. θ (undefined function for arguments)

Functions that return functions

These are functions that return another function as a result. Examples:
  1. ⟨( f(n1 n2) = ⟨( g(n) = (n1 n2 … n) )& ⟩ )⟩
    f(3 7) // ev. ⟨( g(n) = (3 7 … n) )⟩

  2. ⟨( f(n1 n2) = ( ⟨( g(n) = (n1−n2 … n) )⟩ )⟩ ← n1>n2 →'
    ⟨( g(n) = (n1+n2 … n) )⟩ ) )⟩
    f(3 7) // ev. ⟨( g(n) = (10 … n) )⟩
    f(7 3) // ev. ⟨( g(n) = (4 … n) )⟩

Functions as function arguments

A function can be passed as an argument to another function. Example:

⟨( f(g n1 n2) = ⟨( ( [g([[(n1…n2)!])] )/g ) )⟩ )⟩
f(⟨( g(n) = 2*n+1 )⟩ 1 4)
// ev. (g(1) g(2) g(3) g(4))/ ⟨( g(n) = 2*n+1 )⟩
// ev. (3 5 7 9)


Higher order functions

These are functions that have as functions as arguments and return another function as a result. In general, a parametric expression can be passed as an argument to a function. Examples:
  1. ⟨( f(u v) = ⟨( h(x y) = (u + v + 7) )⟩ )⟩
    f(x*x y*y) // ev. ⟨( h(x y) = (x*x + y*y*y + 7) )⟩

  2. ⟨( f(g n) = ⟨( h(x) = (n★g(x))/g )⟩ )⟩
    f(⟨( g(x) = 2*x+1 )⟩ 4)
    // ev. (⟨( h(x) = (4★g(x))/⟨( g(x) = 2*x+1 )⟩ )⟩ )⟩
    // ev. (⟨( h(x) = (4★(2*x+1) )⟩

Application of a function to a sequence of arguments

In MENTAL it is easy to do this using the "Distribution" primitive.

Example with one parameter:

⟨( triple(x) = 3×x )⟩
( [triple([1 2 3 4])] ) // ev. ( 3 6 9 12 )
( [triple[(( 2...5 )])] ) // ev. ( 6 9 12 15 )

Example with two parameters:

⟨( f(x y) = (x+y x*y) )⟩
( [f[(1 2) (3 4) (3 4) (5 6)]] ) // eq. ( f(1 2) f(3 4) f(5 6) )
// ev. ( (3 2) (7 12) (11 30) )

It can also be done by relative substitution. For the above two examples:

(1 2 3 4)/⟨( triple(n) = 3*n )⟩ // ev. ( 3 6 9 12 )

((1 2) (3 4) (5 6))/⟨( f(n1 n2) = (n1+n2 n1*n2) )⟩ // ev. ( (3 2) (7 12) (11 30) )

Note that the function parameters have to indicate the type of elements to which they apply (integers, in this case).


Recursive application of a function

The recursive application (n times) of a function f(x), with argument a, that is, for example, with n=4: f(f(f(f(f(a)))) can be specified by (f★n a)Δ being Δ the hierarchical binary grouping operator, in this case to the right. Recall that, for example,

(f f f f a)Δ = f(f(f(f a))

If the function name is fixed and the argument a as well, you could define the one-parameter function:

⟨( z(n) = (f★n a)Δ )⟩

Example:

⟨( f(x y) = (x+y x*y) )⟩
⟨( z(n) = (f★n (a b))Δ )⟩
z(1) // ev. (f (a b)) eq. f(a b) ev. (a+b a*b)
z(2) // ev. (f (f (f (a b)))) eq. f(f(f(a b)) // ev. ((a+b)+(a*b) (a+b)*(a*b))

If the x argument were variable, we could also define the two-parameter function:

⟨( z(x n) = (f★n x)Δ )⟩

Example:

⟨( f(x y) = (x+y x*y) )⟩
z((a b) 1) // ev. (f (a b)) eq. f(a b) ev. (a+b a*b)
z((a b) 2) // ev. (f (f (f (a b))) eq. f(f(f(a b))) // ev. ((a+b)+(a*b) (a+b)*(a*b))

Maximum generality is achieved when the function itself is also a parameter:

⟨( z(f x n) = ((f★n x)Δ)/f )⟩

Example:

z(⟨( f(x y) = (x+y x*y) )⟩ (a b) 1) // ev. (f (a b))/⟨( f(x y) = (x+y x*y) )⟩ ev. (a+b a*b)

z(⟨( f(x y) = (x+y x*y) )⟩ (a b) 2) // ev. (f (f (f (a b))))/⟨( f(x y) = (x+y x*y) )⟩ ev. f(f(f(a b))) ev. ((a+b)+(a*b) (a+b)*(a*b)))


Partial evaluation of functions

This is to supply fewer arguments than parameters the function has defined. This allows you to define particular functions, instantiated from more general functions. Example:

⟨( f(x y) = (x+y x*y) )⟩
f(5y) // ev. (5+y 5*y)
⟨( g(y) = f(5 y) )⟩ // ev. ⟨( g(y) = (5+y 5*y) )⟩
g(7) // ev. (12 35)

In MENTAL, the partial evaluation mechanism is generic, i.e., it is applicable to all types of expressions [see MENTAL Language - Techniques - Partial Evaluation].


Bibliography