Transcript Functions

Concepts from Functional Programming Languages
Peter Gorm Larsen
TIVDM2
Functional Programming
Language Concepts
1
Agenda
 Introduction to the Functional Programming Paradigm
• The notion of higher order functions
• Polymorphic examples of standard higher order
functions
TIVDM2
Functional Programming
Language Concepts
2
Introduction to FP
• The design of the imperative languages is based
directly on the von Neumann architecture
• Efficiency is the primary concern, rather than the
suitability of the language for software development
• The design of the functional languages is based on
mathematical functions
• A solid theoretical basis that is also closer to the
user, but relatively unconcerned with the architecture
of the machines on which programs will run
TIVDM2
Functional Programming
Language Concepts
3
Principles of FP
• Treats computation as evaluation of mathematical
functions (and avoids state)
• Data and programs are represented in the same way
• Functions as first-class values
– Higher-order functions: functions that operate on, or
create, other functions
– Functions as components of data structures
• Lambda calculus provides a theoretical framework for
describing functions and their evaluation
• It is a mathematical abstraction rather than an imperative
programming language
TIVDM2
Functional Programming
Language Concepts
4
History
• lambda calculus (Church, 1932)
• simply typed lambda calculus (Church, 1940)
• lambda calculus as prog. lang. (McCarthy(?), 1960,
Landin 1965)
• polymorphic types (Girard, Reynolds, early 70s)
• algebraic types ( Burstall & Landin, 1969)
• type inference (Hindley, 1969, Milner, mid 70s)
• lazy evaluation (Wadsworth, early 70s)
• Equational definitions Miranda 80s
• Type classes Haskell 1990s
• Microsoft F# etc 2000s
TIVDM2
Functional Programming
Language Concepts
5
Varieties of FP languages
• Typed (ML, Haskell) vs untyped (Scheme, Erlang)
• Pure vs Impure
• impure have state and imperative features
• pure have no side effects, “referential transparency”
• Strict vs Lazy evaluation
TIVDM2
Functional Programming
Language Concepts
6
Declarative style of programming
• Declarative Style of programming - emphasis is placed
on describing what a program should do rather than
prescribing how it should do it.
• Functional programming - good illustration of the
declarative style of programming.
• A program is viewed as a function from input to output.
• Logic programming – another paradigm
• A program is viewed as a collection of logical rules and
facts (a knowledge-based system). Using logical
reasoning, the computer system can derive new facts
from existing ones.
TIVDM2
Functional Programming
Language Concepts
7
Functional style of programming
• A computing system is viewed as a function which
takes input and delivers output.
• The function transforms the input into output .
• Functions are the basic building blocks from which
programs are constructed.
• The definition of each function specifies what the
function does.
• It describes the relationship between the input and the
output of the function.
TIVDM2
Functional Programming
Language Concepts
8
Agenda
 Introduction to the Functional Programming Paradigm
 The notion of higher order functions
• Polymorphic examples of standard higher order
functions
TIVDM2
Functional Programming
Language Concepts
9
First-Class Functions
Data values are first-class if they can
• be assigned to local variables
• be components of data structures
• be passed as arguments to functions
• be returned from functions
• be created at run-time
TIVDM2
Functional Programming
Language Concepts
10
Higher-order Functions
•
•
•
TIVDM2
Every function has an order:
• A function that does not take any functions as parameters, and
does not return a function value, has order 1
• A function that takes a function as a parameter or returns a function
value has order n+1, where n is the order of its highest-order
parameter or returned value
A small example:
Twice: (int -> int) * int -> int
Twice(f,x) ==
f( f (x))
Or
TwiceCur: (int -> int)-> int -> int
TwiceCur(f)(x) ==
f( f (x))
Functional Programming
Language Concepts
11
Functions in Programming
Languages
• How functions are treated by programming languages?
Language
passed as
arguments
returned from
functions
nested scope
Java
No
No
No
C
Yes
Yes
No
C++
Yes
Yes
No
Pascal
Yes
No
Yes
Modula-3
Yes
No
Yes
Scheme
Yes
Yes
Yes
ML
Yes
Yes
Yes
TIVDM2
Functional Programming
Language Concepts
12
Nested Functions and Closures
• Return a function from function call
function f(x) {
var y = x;
return function (z){y += z; return y;}
}
var h = f(5);
h(3);
• In order to handle this one needs to introduce closures
• A closure is a function that captures the bindings of free variables in
its lexical context.
TIVDM2
Functional Programming
Language Concepts
13
Agenda
 Introduction to the Functional Programming Paradigm
 The notion of higher order functions
 Polymorphic examples of standard higher order
functions
TIVDM2
Functional Programming
Language Concepts
14
Predefined Higher-Order
Functions in Functional Languages
• We will use three important predefined higher-order
functions:
•
•
•
•
map
filter
foldr
foldl
• Actually, foldr and foldl are very similar, as you might
guess from the names
TIVDM2
Functional Programming
Language Concepts
15
The Map Function
• Map applies a function to every element of a list:
Map[@A,@B]: (@A -> @B) -> seq of @A -> seq of @B
Map(f)(list) ==
[f(list(i)) | i in set inds list]
TIVDM2
Functional Programming
Language Concepts
16
The Filter Function
• Filter selects every element that satisfies a predicate:
Filter[@A]: (@A -> bool) -> seq of @A -> seq of @A
Filter(pred)(list) ==
[list(i) | i in set inds list & pred(list(i))]
TIVDM2
Functional Programming
Language Concepts
17
The FoldR Function
• Folds all elements in a list from the right into one
value (a simple pattern of recursion):
FoldR[@A,@B]: (@A * @B -> @B) -> @B -> seq of @A -> @B
FoldR(f)(neutral)(list) ==
if list = []
then neutral
else f(hd list,FoldR(f)(neutral)(tl list))
Example usage:
Sum = FoldR(+)(0)
Product = FoldR(*)(1)
Or = FoldR(or)(false)
And = FoldR(and)(true)
TIVDM2
Functional Programming
Language Concepts
18
Summary
• What have I presented today?
• Introduction to the Functional Programming Paradigm
• The notion of higher order functions
• Polymorphic examples of standard higher order functions
• What do you need to do now?
• Complete your distributed real time model for your project
TIVDM2
Functional Programming
Language Concepts
19
Quote of the day
Program designers have a tendency to think of the users
as idiots who need to be controlled. They should
rather think of their program as a servant, whose
master, the user, should be able to control it. If
designers and programmers think about the apparent
mental qualities that their programs will have, they'll
create programs that are easier and pleasanter —
more humane — to deal with.
John McCarthy
TIVDM2
Functional Programming
Language Concepts
20