Functional Programming Part 1

Functional Programming Language

It has simpler semantics and a simpler model of computation than an imperative language.

Effects of the Advantages of a Functional Language

Popular for rapid prototyping, artificial intelligence, mathematical proof systems, and logic applications.

Semantics

A major drawback to functional languages was inefficient execution. Because of their ____, such languages at first were interpreted rather than compiled, resulting substantial loss in execution speed.

Program

A description of a specific computation.

“How”

The ____ of the computation that focus on the result being computed.

“What”

The _____ of the computation which a program becomes a virtual black box that transforms input to output.

Program

From this point of view, a ____ is essential equivalent to a mathematical function.

Function

A rule that associated to each x from some set X of values a unique y from a set Y of values. In mathematical terminology, if f is the name of the ___, we write:
y = f(x) or f: X → Y

Domain

The set X is called the ____ of f.

Range

The set Y is called the ____ of f.

Independent Variable

The x in f(x), which represents any value from X.

Dependent Variable

The y from the set Y, defined by the equation y = f(x).

Partial Function

Sometimes f is not defined for all x in X, in which case it is called a _____.

Total

A function that is defined for all x in X.

Programs, procedures, and functions

____, ____, ____ in a programming language can all be represented by the mathematical concept of a function.

Program

In the case of a ____, x represents the input and y represents the output.

Procedure or Function

In the case of a ______, x represents the parameters and y represents the returned values.

“Input”

We can refer to x as ___.

“Output”

We can refer to y as ___.

Function Definition

It describes how a value is to be computed using formal parameters.

Function Application

It is a call to a defined function using actual parameters, or the values that the formal parameters assume for a particular computation.

Imperative Programming Languages

In ____, variables refer to memory locations that store values.

Functional Programming Languages

It takes a mathematical approach to the concept of a variable. In ___, variables are bound to values, not to memory locations. Once a variable is bound to a value, that variable’s value cannot change.

True

TRUE OR FALSE. Functional programming languages retain some notion of assignment, thus, it is possible to create a pure functional program — that is, one takes a strictly mathematical approach to variables.

True

TRUE OR FALSE. The lack of assignment in functional programming makes loops impossible, because a loop requires a control variable whose values is reset as the loop executes.

Composition

It is a function that takes two functions as parameters and procedures another function as its returned value.

Higher-order Functions

Functions that have parameters that are themselves functions or that produce a result that is a function, or both are called ___.

“o”

Mathematically, the composition operator ____ is defined as follows:
If f: X → Y and g: Y → Z, then g o f: X → Z is given by (g o f)(x) = g(f(x)).

Qualities of Functional Programming Languages and Functional Programs

1. All procedures are functions and clearly distinguish incoming values (parameters) from

   outgoing values (results).

2. In pure functional programming, there are no assignments. Once a variable is bound to a

   value, it behaves like a constant.

3. In pure functional programming, there are no loops. Instead, loops are replaced by

   recursive calls.

4. The value of a function depends only on the value of its parameters and not on the order of

   evaluation or the execution path that led to the call.

5. Functions are first-class data values.

True

TRUE OR FALSE. In a language with an applicative order evaluation rule, all parameters to user-defined functions are evaluated at the time of a call, even though it may not be necessary to do so — or even wrong to do so.

Boolean Special Forms (and, or, if)

They do not use applicative order evaluation.

Short-Circuit Evaluation of Boolean Expressions

The Scheme expression (and a b) need not evaluate parameter b if an evaluates to false. It is an example of the usefulness of delayed evaluation.

Non-strict Functions

They can produce results even in the presence of incomplete or malformed input — as long as there is enough information to make the result reasonable.

Pass by Name Evaluation

A parameter is evaluated only when it is actually used in the code of the called procedure. Thus, the function:

function p(x: boolean, y: integer): integer;
begin
if x then p := 1
else p := y;
end;

Using ____, return the value 1 when called as p(true, 1 div 0), since y is never reached in the code of p, and so the value of y — the undefined expression 1 div 0 — will never be computed.

____ is helpful in that it allows parameters to remain un-computed if not needed and permits special forms similar to if and cond to be defined as ordinary functions.

Lazy Evaluation

This mechanism of evaluating expressions can be achieved in a functional language without

explicit calls to delay and force by requiring the run-time environment to adhere to the following

rules:

1. All arguments to user-defined functions are delayed.

2. All bindings of local names in let and letrec expressions are delayed.

3. All arguments to constructor functions (such as cons ) are delayed.

4. All arguments to other predefined functions, such as the arithmetic functions “1,” “*,” and so on, are forced.

5. All function-valued arguments are forced.

6. All conditions in selection forms such as if and cond are forced.

Lazy Evaluation

Makes it possible to include potentially infinite lists in languages, because only a part of the list would ever be computed at any one time.

Streams

• Lists that obey lazy evaluation rules are often called ____.

• They can be thought of as a partially computed list whose remaining elements can continue to be computed up to any desired number.

• They are an important mechanism in functional programming.

• To eliminate side effects completely, input and output must be introduced into functional languages as _____.

Lambda Calculus

It was invented by the mathematician Alonzo Church (1903 - 1995).

Alonzo Church

• He is interested in the notion of a function from computational perspective.

• He is the PhD supervisor of Alan Turing (who invented the Turing Machine).

• For him, a function is a black box, but you are not allowed to look inside. What it does it takes some input and it’s going to process it someway and it’s going to produce an output.

Alan Turing

He invented the Turing Machine.

Lambda Calculus

• A function that takes a single input called x, process it in some way and produces the output, the number x + 1 that refers to as increment of x.

• Another example is that a function that takes two inputs and produces an output.

• It is purely mathematical function and there’s no internal state that we can look inside a function.

For example, let’s have the increment function in ____. We will

define a function using a lower-case lambda symbol then you write down the

input x and then you have a dot. To calculate the output in terms of input, x+1.

λx. x + 1

We can also do the same with addition, a function that receives two inputs x

and y delivers an output, x + y.

λx. λy. x + y

Let’s have another example. Here, we will do the basic process of substitution.

We will substitute x with 5.

(λx. + x 1) 5

= + 5 1

= 6

Basically, in ____ it only got three things: the variables; the

lambda notation build functions and a way of applying functions. It does not

have any built-in data types, logical values, recursion and things alike. So, if

you need to do these things in _____, you need to encode them.

Lambda Calculus

Here’s an example of encoding logical values TRUE and FALSE. The key to this is to think

what do you do in logical values in a programming language? The basic observation is that

you use them to make a choice between doing two things. Like saying if something is TRUE

do one thing, if something is FALSE do another thing. Let’s say:

TRUE = λx. λy. x

FALSE = λx. λy. y

What it does it takes two things x and y then choose the first if it’s TRUE. In FALSE it does the

opposite, it takes two things x and y then chooses the second.

So, we’ve got two Lambda expressions here, both of which takes two inputs x and y, one

chooses the first the other one chooses the second.

Lambda Calculus

Here’s another example for negation, we can do encoding by

expanding the definition. Let’s say NOT TRUE:

NOT TRUE

= (λb. b FALSE TRUE) TRUE

= TRUE FALSE TRUE

= (λx. λy. x) FALSE TRUE

= FALSE

Lambda Calculus

To apply loops or recursion in ____, we have so-called self

application— a function that is applied to itself.

LOOP

= (λx. x x ) (λx. x x )

= (λx. x x ) (λx. x x )

…

…

Lambda Calculus

1. It can encode any computation.

2. A basis for functional programming.

3. Present in most programming languages.