PowerPoint Presentation
CS 345
Lecture 3
Last Session
Imperative vs. functional paradigms
Programming with statements vs. programming with expressions
Defining simple functions in Racket
“Sugared” functions vs. functions using “lambda”
Imperative vs. Functional
Imperative programs solve problems, such as sorting a list, by “mutating state”
assigning and re-assigning values, such as the index of a for loop or the items in an array
Functional programs avoid the mutation of state and instead exclusively use expressions.
Expressions always apply a built-in operator or a function that you define to argument(s), and they always return a value.
In Racket, expressions are always surrounded by parentheses. They are as simple as (+ 2 3) or as complex as an entire program.
Defining Functions in Racket
Define your own functions using the define keyword:
(define (double x)
(* x 2))
“To double something, multiply it by two.”
This is equivalent to:
(define double (lambda (x) (* x 2))
“To double something, make a function that takes an
argument and returns that argument multiplied by 2.”
Write a function that squares its argument:
with and without “syntactic sugar”
Today’s Topics
Let’s learn how two design decisions are handled by Racket:
Control Flow
Conditional Branching
Evaluation Strategy
Eager (vs. Lazy)
Control Flow
“Control flow” is the way that a language lets the programmer manage the order of a program’s execution
What should be done first, second, etc.?
Examples of control structures in Java, Python:
if / else if / else
for loops
while loops
class WhileIfDemo {
public static void main(String[] args){
int count = 1;
while (count < 11) {
System.out.print("Count: " + count);
if (count % 2 == 0) {
System.out.println(“ is even.”);
} else {
System.out.println(“ is odd.”);
}
count++; }
}
}
class WhileIfDemo {
public static void main(String[] args){
int count = 1;
while (count < 11) {
System.out.print("Count: " + count);
if (count % 2 == 0) {
System.out.println(“ is even.”);
} else {
System.out.println(“ is odd.”);
}
count++; }
}
}
The previous example was Imperative.
What about Functional Programming?
Consider what you now know about expressions and functional programming.
Is conditional branching (control flow with if/else) compatible with functional programming?
Absolutely! Functional languages offer “conditional expressions.”
Already familiar as the Java ternary expression:
x = a < b? a : b;
Conditional branching in Racket
Use if when branching between two options:
(if (< a b)
a
b)
Use cond for more than two options:
(cond ((< a b) a)
((= a b) b)
(else 0))
(if (and (> b a) (< b (* a b)))
b
a)
Re-write is-even to use if
(define (is-even x)
(= 0 (modulo x 2)))
(define (is-even x)
(if (= 0 (modulo x 2))
#t
#f))
(abs x)
(define (func x)
(cond ((> x 0) x)
((= x 0) 0)
(else (- x))))
“Participation Quiz”:
Write a function that takes a score as an argument and returns a letter grade.
A if score >= 80
B if score >= 70
C if score >= 60
D if score >= 50
Otherwise, F
Answer
Today’s Topics
Let’s learn how two design decisions are handled by Racket:
Control Flow
Conditional Branching
Evaluation Strategy
Eager (vs. Lazy)
“Substitution Model of Evaluation”
In between your calling the function and getting the result, your language must evaluate the expression.
(define (square x) (* x x))
(define (sum-of-squares x y) (+ (square x) (square y))
(define (f a) (sum-of-squares (+ a 1) (* a 2)))
> (f 5) Answer is 136. But what are the evaluation steps?
Every programming language that has functions must also have an evaluation strategy for functions.
An evaluation strategy must answer:
If the arguments to a function are themselves expressions, when do you evaluate them?
Only two possibilities: “now, or later”!
Now: when called, i.e. before argument is passed into the function body; or, Later: after being passed into the function body, when built-in operations have been reached.
(double (average 2 4))
Eager/Strict/Applicative Order Evaluation
(define (double x) (+ x x))
(define (average x y) (/ (+ x y) 2))
> (double (average 2 4))
(double (/ (+ 2 4) 2))
(double 3)
(+ 3 3)
6
Racket uses applicative order evaluation.
Lazy/Non-strict/Normal Order Evaluation
(define (double x) (+ x x))
(define (average x y) (/ (+ x y) 2))
> (double (average 2 4))
(+ (average 2 4) (average 2 4))
(+ ((/ (+ 2 4) 2) (/ (+ 2 4) 2)))
(+ 3 3)
6
Racket does not use normal order evaluation. The evaluation order above is for demonstration purposes only.
Use the concept of “eager evaluation” to explain this result:
One argument to test is an expression, (p).
Because Racket evaluates eagerly, the argument must be evaluated before being passed into test.
But (p) is just a function that calls itself, infinitely!
So, even though x is indeed 0, and 0 “should” be returned, the arguments are never even passed to the function body.
Given eager evaluation, what will be the result?
One of the arguments is an expression, (/ 1 0). Because Racket is eager, this argument must be evaluated before being passed to my-if. Evaluating this expression produces a “division by zero” error.
Is Python eager?
Yes. If Python instead had normal order evaluation, we would expect “I got called” to be printed three times, not twice.
Lab #1
Wait, but what about boolean operators?
“Short-circuiting” is a specific way that all eager languages do actually delay the evaluation of arguments.
What about lazy/normal order evaluation?
Almost all programming languages are eager by default. Lazy evaluation is almost never the default evaluation strategy.
So why do we even talk about lazy evaluation?
History: normal order evaluation was used in Algol 60 and Simula
To understand what is done most frequently, it is helpful to contrast it with the alternative
Most importantly, “lazy evaluation” is indeed the default strategy in Haskell, and it is enabled as an option in many languages, like Scala and Swift.
Lazy Evaluation
Haskell is “lazy,” and we’ll focus on laziness more when we get to it. But to preview:
With Haskell’s laziness, a value is only evaluated when it is needed, and after one evaluation, all other copies of that expression can be updated with the cached value. That is, we remember the locations where we a certain argument will be used, and when we evaluate a function, we replace the argument with the “memoized” value.
Allows for infinite lists, “DRY” or modular code, and saves on computation!
What we did today
Conditional Branching
Racket handles conditional branching with if (for two cases) and cond (two or more cases)
Evaluation Strategy: Eager or Lazy?
When the argument to a function call is an expression, will the expression be passed to the function body evaluated (eager) or unevaluated (lazy)?
Racket is eager. (Haskell, we shall see, is lazy!)
/docProps/thumbnail.jpeg