Functional Programming
15.5 Intro to Scheme
15.5.13 Functional forms
Apply-To-All
map function applies function to each element of a given list
(map (LAMBDA (num) (* num num num)) '(3 4 2 6))
This function returns cubes of each input
Return values: (27 64 8 216)
Functional Composition
Similar to h(x) = f(g(x))
(DEFINE (g x) (* 3 x))
(DEFINE (f x) (+ 2 x))
can both be defined as:
(DEFINE (compose f g) (LAMBDA (x) (f (g x))))
(DEFINE (h x) (+ 2 (* 3 x)))
Only functional form provided by original LISP
15.5.12 Tail Recursion
Tail recursive is when last operation in a function
is a recursive call
Tail Recursive:
(DEFINE (facthelper n factpartial)
(IF (<= n 1)
factpartial
(facthelper (- n 1) (* n factpartial))
))
(DEFINE (factorial n)
(facthelper n 1)
)
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.
factpartial maintains the partial factorial
Not Tail Recursive:
(DEFINE (factorial n)
(IF (<= n 1)
1
(* n (factorial (- n 1)))
))
Last operation is multiplication
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
The two expressions below are equivalent:
(LET ((alpha 7)) (* 5 alpha))
((LAMBDA (alpha) (* 5 alpha)) 7)
15.5.9 Predicate functions
NULL function determines if empty list
(NULL? '(())) returns false because parameter is a list containing the empty list
(NULL? '()) returns true.
LIST function determines if list
Beware, (LIST? '()) returns true
(LIST? '(X Y)) returns true
Use EQV? to compare both numeric and symbolic atoms
(EQV? 3 3.0) -> returns #F (comparing int with float, which are represented differently)
(EQV? 3.4 (+ 3 0.4)) -> returns #T
EQ? function compares addresses (not values)
(EQ? 'A 'A) is true
15.5.8 List Functions
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.
Can use any combination of D's and A's up to 4
Ex: (CADDAR '((A B (C) ) D) E))
=(CAR (CDR (CDR (CAR '((A B (C) D) E)))))
=(CAR (CDR (CDR '(A B (C) D))))
=(CAR (CDR '(B (C) D)))
=(CAR '((C) D))
=(C)
CDR '(A B C) returns (B C) -- Every element except first
CDR = contents of the decrement part of a register
CAR '(A B C) returns A -- First element of list
CAR = contents of the address of a register
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
(QUOTE A) or 'A -> returns A
This is used to ignore evaluation of a parameter
Used because data and code have the same form
15.5.7 Control Flow
3 types
Recursion *More on this later*
N-way selector
COND keyword (conditional) -> COND ... [else
Ex: (cond ((> 3 3) 'greater)
((< 3 3) 'less) (else 'equal))
2-way selector: If - then- else
(if predicate then_expression else_expression)
15.5.6 Predicate Functions
Non-empty list evaluates to true
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 ())
15.5.5 Output Functions
Scheme has some output operations, but when using the interpreter, usually just displayed normally through EVAL function.
explicit input/output not a part of the functional program model: input operations change the state and output operations have side effects
15.5.4 Defining Functions
DEFINE keyword binds name to keyword or LAMBDA expression (analogous to declaring final variable in Java)
Ex: (DEFINE pi 3.14159)
Binds LAMBDA expression to a name
(DEFINE (function_name parameters) (expression))
Ex: (DEFINE (square num) (* num num))
Used to create more imperative style, but creates named values NOT variables
Naming convention:
Cannot begin with digit
Can have letters, digits, and special characters (except parentheses)
Not case sensative
Definition: Lambda Expression: a nameless function (actually includes the word LAMBDA in scheme)
Can have multiple parameters
Eg ((LAMBDA (x) (* x x)) 7) -> 49
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
15.5.3 Primitive Numeric Functions
Scheme includes +, -, *, /
(+ 5 7 8) -> 20
(-24 ( * 4 3)) -> 12
+ and * can have zero or more parameters
+ with no parameters returns 0
* with no parameters returns 1
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
15.5.2 The Scheme Interpreter
Expressions that are calls to primitive functions:
Lastly: result is displayed
Second: primitive function applied to parameter values
First: each parameter expression is evaluated (in no particular order)
Interpreted by the function EVAL
in interactive mode is a read-evaluate-print loop (REPL)
15.5.1 Origins of Scheme
Characterized by small size, static scoping, and treatment of functions as first-class objects
Is a dialect of LISP developed at MIT in the 70s
15.11 Imperative vs Functional
Pure FPL are already independent and significantly
easier to make concurrent as there is no state to
worry about, like in imperative programming
FPL offers a readability advantage
Execution speed for functional programming is twice
that of imperative programming due to language
characteristics like lazy evaluation
It is claimed that functional programming produces
only 10-25% as much code needed compared to
imperative programmed counterparts
Functional syntax is typically simpler than imperative,
as well as simpler semantics
15.4 The First FPL: LISP
15.4.2 The first LISP Interpreter
Implementation of EVAL
much of original language was forzen and provided odd features
Use of dynamic scoping
conditional expression form
() for empty set and logical false
M-notation never completed - used S-expression (or just expressions) instead
Other implementations copied EVAL and were also interpretive
functions needed to be expressed as list notation
Functions allowed to be bound to names (not just lambda functions) in order to be referenced.
EVAL: a function that could evaluate other functions served as LISP interpreter
(function_name (LAMBDA ( param1, ... paramN) expression)
Definition: Cambridge Polish notation: prefix notation
(* X Y) -> X * Y
Original intent to be similar to FORTRAN with compiler to translate programs in M-notation into machine code
15.4.1 S=Data Types / Structures
List: List elements are pairs that include an atom and a pointer (usually linked list) to an atom, other element, or special value
Atom: Symbols or numeric listerals
Developed by John McCarthy
Oldest/Most widely used
Original LIP was typeless
15.3 Fundamentals of FPLs
FPLs Provide:
structure(s) to represent data
a function application operation
set of functional forms to construct complex functions
set of primitive functions
Definition: Referential Transparency - execution of function always produces same result
Main objective is to mimic mathematical functions
Storage of intermediate values may be necessary, but details will be hidden from the programmer.
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.
15.2 Mathematical functions
High-order function/functional form takes on functions
as parameters or yields a function
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)
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
Nameless functions can be defined with lamda
λ(x) x * x * x
This is equivalent to the cube function, just nameless
Application of lambda with parameters
(λ(x) x * x * x)(2)
Lamda calculus was defined by Church. It
is a formal system for function definition,
function application, and recursion. Can be
typed or untyped
Application: cube(x)≡x*x*x
In this case, x cannot be changed. The final result is however
returned as the range
Always map an element of the domain to same element
of the range. There are no bound parameters
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
15.1 Foundation
Uses in database processing, financial modeling,
statistical analysis, and bioinformatics
John Backus formally proposed that Functional
Programming was the most efficient because of the
lack of side effects
Based on mathematical functions, while imperative
is based moreso on the Von Neumann Architecture
