Transcript Functional Programing

Functional Programing
Referencing material from
Programming Language Pragmatics – Third Edition – by Michael L. Scott
Andy Balaam (Youtube.com/user/ajbalaam)
Historical Origins
How did we get here
History
• From the work of Alan Turing, Alonzo Church, Stephen Kleene, Emil Post,
and others
• Each worked on their own
• Each made a formalized notion of an algorithm
• Church’s Thesis:
Any intuitively appealing model of computing would be equally powerfull
Two Paradigms
•
•
•
•
•
•
Turing Machine
Lambda Calculus
(Imperative Languages)
(Functional Languages)
Based on pushdown automaton
•
A pushdown automata uses a stack
Uses an unbounded storage “tape”
•
Computation is done by reading and writing
values from cells on the tape
Example: Google Doodle for Alan Turing’s 100th
Birthday
All of the languages you have learned in 201 and
202
•
•
Based on parameterized expressions, each
parameter is introduced with a 𝜆
One substitutes parameters into expression to
compute each expression
Example: Scheme (later)
Lisp (scheme, rocket), Haskell, Miranda, pH,
Sisal, Single Assignment C, Erlang
Functional Programming Concepts
A completely new paradigm
No side effects
• Based on function
• A function takes parameters and returns something
• Functions can not modify values
First Class values
• Everything is a first class value, including functions
• This allows for higher order functions, which operate on functions.
Polymorphism
• Most functional languages are polymorphic
• Lisp (Scheme, Rocket, etc.) is dynamically typed
•
Functions can take many different types and conditionally deal with them based on
type
Lists
• A list is an item followed by a list
• This leads to natural recursion
• Provides the only way to repeatedly do something
• Operate on the first element, do the same with the rest (hint: recursion)
Scheme
A language with only one feature
Scheme is a dialect of Lisp
• Lisp stands for LISt Processing
• It is usually interpreted, although can be compiled
• Scheme uses prefix (Caimbrige Polish Notation) – although this makes sense
Scheme Interpreters
•
•
Dr. Scheme – deprecated
•
Rocket – for the Rocket dialect
MIT Scheme – its own implementation
My Chosen best:
SISC - Second Interpreter of Scheme Code
• In java – portable
• Uses standard Scheme in a simple command-line environment
You can do one thing
(item item item item item item item)
A Scheme program
(operation operation operation operation)
Operation: (operator operand operand operand)
How to do things
•
•
•
Addition, subtraction, multiplication, and division are predefined and referred to
with +,-,*,/.
Other operations, like modulus are referred to with words
In order to trigger evaluation you must wrap an operation in parenthasys
•
•
•
•
(+ 1 2) evaluates to 3
7 is already evaluated, it results in 7
(7) tries to run the function 7. 7 is not a function
Similarly ((+ 1 2)) tries to run the function 3
How to not do things
• A single quote defines a list
• Because an operation is a list, this means that we can use the single quote to
do operations on a operation or return the operation
‘(+ 1 2) results in the list (+ 1 2)
Booleans
• #t for true
• #f for false
Control flow
If
If [Boolean] [expr if true] [expr if false]
Cond
Cond
([boolean] [expr])
([boolean] [expr])
(else [expr if else])
Dynamic typing
(if (> a 0) (+ 2 3) (+ 2 “foo”))
This will execute fine? Why?
Defining items – lambda expressions
• From lambda calculus
• Lambda takes two arguments, a list of identifiers, and an expression to
compute using them
• Lambda (x) (* x x) is a function that takes a value and returns its square
Defining – function ‘Define’
As the Book does it
• Define takes two parameters, an identifier, and a function
• (Define pow (lambda (x) (* x x)) allows us to use the function pow that takes
a parameter and returns its square
Defining – function ‘Define’
Another way
• Define takes two parameters, a list matching how it should be called, and an
expression using the identifiers given in the first part
• This merges lambda expressions and definition
• (define (pow x) (* x x)) defines the same thing as before
Defining – local bindings
• Defining is just global binding
• You can create local bindings using let
• Let takes a list of defines parameters and an expression, and runs the
expression using that set of defines
Lists
•
•
•
•
•
•
Everything is a list
Recall: a single quote makes a set of parenthesis not evaluate and stay as a list
‘(1 2 3) is a list
Recall: a list is an item followed by a list
What about the last item?
Null? [list]
List operations
• Car [list]
• Cdr [list]
• Cons [item] [list]
Higher-Order Functions
I heard you like functions, so we made your functions return functions, so you can
compute what you compute.
Metaprogramming is just programming
• Metaprogramming is writing code about code
• Lisp doesn’t care
• Lisp is homoiconic – a lisp program is a list.
• A function can be an argument to a function, or it can be returned from a
function
Common Higher order functions
•
•
•
•
•
•
•
Define
Load
Lambda
For-each
Call
apply
compose
Example – Folding
(define fold (lambda (f I l)
(if (null? L) I
(f (car l) (fold f I (cdr l))))))
This takes a function f to fold the list l using the identity i
Evaluation Order
Putting functional programming in order
Evaluation order
Applicative-order
•
You evaluate each argument before you pass it
to a function
Normal-order
•
You pass each argument as an unevaluated
expression
Example (Right from the book)
(Define double (lambda (x) (+ x x)))
(double (* 3 4))
Applicative-order
Normal-order
(double (* 3 4))
(double (* 3 4))
(double 12)
(+ (* 3 4) (* 3 4))
(+ 12 12)
(+ 12 (* 3 4))
24
(+ 12 12)
24
What kind of cases could applicative order be
wasteful?
This is much longer
We calculate the same value twice
Scheme
The book claims that scheme evaluates in applicative-order.
But what about this line? (We just saw this in dynamic typing)
(if (> a 0) (+ 2 3) (+ 2 “foo”))
In reality: Lazy evaluation
• We evaluate any evaluable expressions and store their value for later use
• We can forget about this, it is behind the scenes
Functional Programming in Perspective
Functional and comparative, when and why
Side-effect free
•
•
•
•
•
Its simple
Not much advanced computer science needed
Perfect for math
No required evaluation order (other than
common sense)
Parallelism doesn’t matter (the only way to
“talk” is to pass variables)
•
•
•
Some general programming ideas require
assignment (we can’t do that)
I/O is difficult (technically impossible without
side effects)
Any small update requires an entire new copy
of the data
In conclusion
• Fun
• Easy to use
• You can make a computational program easily
• Not a tool for every job, but every tool has a job.