Functional Programming

Based on mathematical functions, while imperative
is based moreso on the Von Neumann Architecture

John Backus formally proposed that Functional
Programming was the most efficient because of the
lack of side effects

Uses in database processing, financial modeling,
statistical analysis, and bioinformatics

Definition: Mapping of members of the domain set
to the range set. In other words, it maps the parameters
to a value(s) in a recursion style fashion

Domain/range sets can be defined explicit
or implicitly. The mapping is described by
expressions or tables. The domain set may
be the cross product of several sets

Always map an element of the domain to same element
of the range. There are no bound parameters

Application: cube(x)≡x*x*x
In this case, x cannot be changed. The final result is however
returned as the range

Nameless functions can be defined with lamda
λ(x) x * x * x
This is equivalent to the cube function, just nameless

Lamda calculus was defined by Church. It
is a formal system for function definition,
function application, and recursion. Can be
typed or untyped

Application of lambda with parameters
(λ(x) x * x * x)(2)

High-order function/functional form takes on functions
as parameters or yields a function

A common variant is function composition
h ≡ (f º g) f(x)≡x+2 and g(x)≡3*x
h ≡ f(g(x))
h ≡ (3*x) + 2

Apply-to-all is another higher-order function
It uses one function to take multiple parameters
α(h, (2, 3, 4)) where h(x) = x*x yields (4,9,16)

Main objective is to mimic mathematical functions

Avoids using variables and memory locations
(memory locations that need evaluated do not exist in pure mathematics)

Because variable are not used, iteration can not take place.
Must use recursive functions in order to iterate.

Storage of intermediate values may be necessary, but details will be hidden from the programmer.

Definition: Referential Transparency - execution of function always produces same result

FPLs Provide:

set of primitive functions

set of functional forms to construct complex functions

a function application operation

structure(s) to represent data

Oldest/Most widely used

Original LIP was typeless

Developed by John McCarthy

15.4.1 S=Data Types / Structures

Atom: Symbols or numeric listerals

List: List elements are pairs that include an atom and a pointer (usually linked list) to an atom, other element, or special value

15.4.2 The first LISP Interpreter

Original intent to be similar to FORTRAN with compiler to translate programs in M-notation into machine code

functions needed to be expressed as list notation

Definition: Cambridge Polish notation: prefix notation
(* X Y) -> X * Y

Functions allowed to be bound to names (not just lambda functions) in order to be referenced.

(function_name (LAMBDA ( param1, ... paramN) expression)

EVAL: a function that could evaluate other functions served as LISP interpreter

Implementation of EVAL

Other implementations copied EVAL and were also interpretive

M-notation never completed - used S-expression (or just expressions) instead

much of original language was forzen and provided odd features

() for empty set and logical false

conditional expression form

Use of dynamic scoping

Functional syntax is typically simpler than imperative,
as well as simpler semantics

It is claimed that functional programming produces
only 10-25% as much code needed compared to
imperative programmed counterparts

Execution speed for functional programming is twice
that of imperative programming due to language
characteristics like lazy evaluation

FPL offers a readability advantage

Pure FPL are already independent and significantly
easier to make concurrent as there is no state to
worry about, like in imperative programming

15.5.1 Origins of Scheme

Is a dialect of LISP developed at MIT in the 70s

Characterized by small size, static scoping, and treatment of functions as first-class objects

15.5.2 The Scheme Interpreter

in interactive mode is a read-evaluate-print loop (REPL)

Interpreted by the function EVAL

Expressions that are calls to primitive functions:

First: each parameter expression is evaluated (in no particular order)

Second: primitive function applied to parameter values

Lastly: result is displayed

15.5.3 Primitive Numeric Functions

Also includes: MODULO, ROUND, MAX, MIN, LOG, SIN, SQRT
Note: Scheme is not case sensative, but some other FPLs
are

if parameter for square root is negative, will return a complex number

Scheme includes +, -, *, /

+ and * can have zero or more parameters

* with no parameters returns 1

+ with no parameters returns 0

15.5.4 Defining Functions

Definition: Lambda Expression: a nameless function (actually includes the word LAMBDA in scheme)

Definition: Bound Variable: In this expression x is a bound variable -> x cannot change after being bound to an actual parameter value when evaluation begins

Can have multiple parameters

DEFINE keyword binds name to keyword or LAMBDA expression (analogous to declaring final variable in Java)

Used to create more imperative style, but creates named values NOT variables

Naming convention:

Not case sensative

Can have letters, digits, and special characters (except parentheses)

Cannot begin with digit

Binds LAMBDA expression to a name

(DEFINE (function_name parameters) (expression))
Ex: (DEFINE (square num) (* num num))

15.5.5 Output Functions

explicit input/output not a part of the functional program model: input operations change the state and output operations have side effects

Scheme has some output operations, but when using the interpreter, usually just displayed normally through EVAL function.

15.5.6 Predicate Functions

Included functions = (equality), <> (not equal -> now use NOT with equality operator), <, >, <=, >=, EVEN? (is even?), ODD? (is odd?), ZERO? (is zero?)

All evaluate to true (#t) or false (#f or ())

Non-empty list evaluates to true

15.5.7 Control Flow

3 types

2-way selector: If - then- else

(if predicate then_expression else_expression)

N-way selector

COND keyword (conditional) -> COND <clause1> ... <clause n> [else <expression>

Recursion *More on this later*

15.5.8 List Functions

Has to evaluate parameters first in case the parameter itself is a function. When a parameter is not a function reference,
it should not be evaluated -> use QUOTE

CAR = contents of the address of a register

CDR = contents of the decrement part of a register

Can use any combination of D's and A's up to 4

CONS function combines two lists (Atoms can be used too)
(CONS '(A B) '(C D)) = ((A B) C D)

LIST function can be used for shorthand nested CONS functions as it takes in variable number of parameters and produced a list.

15.5.9 Predicate functions

EQ? function compares addresses (not values)

(EQ? 'A 'A) is true

Use EQV? to compare both numeric and symbolic atoms

LIST function determines if list

NULL function determines if empty list

15.5.11 LET

LET is a function that creates local scope in which names are temporarily bound to values of expressions
-Actually shorthand for LAMBDA
-Cannot be overwritten once created

15.5.12 Tail Recursion

Tail recursive is when last operation in a function
is a recursive call

Not Tail Recursive:

Last operation is multiplication

Tail Recursive:

factpartial maintains the partial factorial

Because it is tail recursive, the calling activation record is no longer necessary, so this function only needs to keep track of 1 activation record.

15.5.13 Functional forms

Functional Composition

Only functional form provided by original LISP

Similar to h(x) = f(g(x))

can both be defined as:

Apply-To-All

map function applies function to each element of a given list

This function returns cubes of each input
Return values: (27 64 8 216)