Transcript ppt
Programs as Functions
• Some programs act like mathematical functions
– Associate a set of input values from the function’s domain
with a set of output values from the function’s range
– E.g., written as y = f(x) or f : X → Y …
… where X is the domain, Y is the range, xX is the
independent variable, and yY is the dependent variable
• No assignment, so no loops in purely functional code
– Instead, rely on recursion to perform iteration
• Referential transparency
– Function’s value depends only on arguments (+ global
state)
• Value semantics
– No local state
CSE 425: Functional Programming I
Intro to Lambda Calculus
• Syntax
expression →
constant | variable
| ‘(‘ expression expression ‘)’
| ‘(‘ ‘λ’ variable ‘.’ expression ‘)’
• Lambda expressions: function, parameters, arguments
– E.g., (λx. + 1 x), written (lambda (x) (+ 1 x)) in Scheme
• Can apply a lambda expression (“beta reduction”)
– E.g., (λx. + 1 x) 2 replaces x with 2, evaluates to 3
• Can parameterize an expression (“beta astraction”)
– E.g., can parameterize expression (+ 1 2) as (λx. + 1 x) 2
• Can also rename variables (“alpha conversion”) and
remove redundant expressions (“eta conversion”)
CSE 425: Functional Programming I
Intro to Scheme (a Dialect of Lisp)
• General syntactic structure of Scheme is very simple
expression → atom | ‘(‘ {expression} ‘)’
atom → literal | symbol
literal → number | string | character | boolean
• Atomic literals evaluate to themselves
– 100, “world”, #\z, #T, #f,
• Symbols are treated as identifiers
– Which are then looked up in a symbol table for the current
environment, replaced by the values that are found there
– If a symbol names a function, it is applied to other values
CSE 425: Functional Programming I
Expressions in Scheme
• All are either special forms or function applications
– Special forms begin with a Scheme keyword (e.g., car, cdr,
cond, cons, define, display, if, lambda, let, letrec, quote, etc.)
– Function application (call) is prefix: name then arguments
• Predefined operators for many basic functions
– Such as + (addition), * (multiplication), / (division), etc.
• Selection expressions for if, if-else, and if-elseif logic
– Use if form for single selection, vs. cond form for multiple
• Binding lists (using the let or letrec keywords)
– Associate values with variables before applying a function
• Lambda expressions (using the lambda keyword)
– Define formal parameter lists for (anonymous) functions
CSE 425: Functional Programming I
Data Structures in Scheme
L
car L
cdr L
“hello, ”
car cdr L
cdr cdr L
“world!”
• Basic construct is a list node (box and arrow notation)
– Lists are concatenations of list (or list of list …) nodes
– Functions car and cdr select the head vs. the rest of a list
• The cons function constructs a list from two others
– Concatenates them with the first in front of the second
• The null? primitive tests whether or not a list is empty
– Useful for recursive operations on lists (“cdr down, cons
up”)
CSE 425: Functional Programming I
Evaluation, Type Checking, and Scopes
• Scheme uses applicative order evaluation
– Arguments evaluated first, then function is applied to them
– Recursively, expression tree is evaluated leaves-to-root
• Special forms use delayed evaluation
– E.g., else part of a cond expression may not evaluate at all
• Can prevent evaluation using the quote keyword
– Identifies a list as being a literal rather than an expression
• Scheme type checks only when absolutely necessary
– E.g., just before a primitive function is applied
• Scoping is static in Scheme, with hiding with nesting
– E.g., an inner let hides an outer let for same symbol name
CSE 425: Functional Programming I
Today’s Studio Exercises
• We’ll explore ideas from Scott Chapter 10.1-3
– Looking at basic functional programming features in C++
– Using them in ways similar to Scheme/Lisp features
• Today’s required exercises are again in C++
– Please take advantage of the on-line tutorial and reference
manual pages that are linked in the lab machines
– As always, please ask us for help as needed
• When done, email your answers to the course account
with subject line “Functional Programming Studio I”
– Send to [email protected]
CSE 425: Functional Programming I