University of Guadalajara DR Raquet Programming Language Worksheet

Dr. Raquet language program

Implement the following functions. Functions should return values which will can then be printed by racket (as a result of the function call).Include display/printf statements as necessary to label the results (of the function calls) in order to demonstrate that your code works properly.Functions should not internally contain display or printf statements within other than when you are tracing/debugging the code. Email your racket file to me when done (normally a .rkt extension).

Write two functions to convert between miles and kilometers: kilometres(miles) → kilometres and miles(km) → miles. To get from miles to kilometers, multiply by 1.609. To convert the other way, multiply by 0.6215.To demonstrate that each function works, you might have something like the following:; using display(display “(miles-to-km 10) = “)(miles-to-km 10)(newline)(newline)

; Or, using printf(printf “(miles-to-km 10) = ~a\n” (miles-to-km 10))

Give the values returned by each of the following function calls in Dr. Racket.You can mainly just label the output, and look at each to understand what they do.(define (foo x y)(+ x y (- x)))Expression:

(foo (- 2) 4)(define (a b c d)(e b c d))

(define f +)

(define e f)Expression:

(a (+ 3 2) (* 4 5) 3)(define (a1 b c d)((e1 (f1 b)) c d))

(define (e1 a)a)

(define (f1 a)(if (positive? a)+-))Expression:

(a1 1 (+ 2 3) 4)Rewrite the following functions so that the definitions are nested lexically within each other.Only the entry procedure baz should be visible in the global environment. Take advantage of lexical scoping to remove redundant parameters.(define (foo a)(* a (+ a 2)))

(define (bar a b)(if (= a 14)b(bar (+ a 1) (+ (foo a) b))))

(define (baz n)(bar 3 n))Write a function sum-range (from-to) for finding the sum of integers in the range from to, inclusive.Make sure that (sum-range 4 18), (sum-range 18 4), and (sum-range 7 7) all give the expected result.Note that this function should be able to count up or count down depending on the order of the paramaters.So, (sum-range 4 18) and (sum-range 18 4) should give the same result. (sum-range 7 7) should return 7.

Functional Programming
with Scheme
Procedural Abstraction (1)
Programs
In Scheme programs are sequences of any number of forms
– in pure FP the order of forms does not matter
– however, the result of a program is the value of its last form
– in ’impure’ FP with assignments the order of forms does matter
Forms are either expressions or definitions
〈program〉 ::= 〈form〉*
〈form〉 ::= 〈expression〉 | 〈definition〉
Expressions are either simple or compound
slide 2
Simple (Primitive) Expressions
Self‐evaluating expressions
– the result of evaluating an expression is the expression itself
〈expression〉 ::= 〈number〉 | 〈character〉 | 〈string〉 | …
Non‐self‐evaluating expressions
– the result of evaluating an expression is an object not necessarily
identical to the expression (though it mightbe)
〈expression〉 ::= … | 〈variable〉 | …
slide 3
Compound Expressions
Compound expressions (combinations)
– applications
– special syntactic forms
Sequences of (possibly nested) expressions enclosed in
parentheses
The general pattern is the prefix (Polish) notation
– the leftmost is an operator followed by a sequence of operands
(〈operator〉 〈operand〉*)
Applications apply the operator (procedure) to the operands
(arguments)
(〈procedure〉 〈argument〉*)
slide 4
Definitions
Definitions are special syntactic forms
– they do not follow the general evaluation pattern of (compound)
expressions
– all special forms have their own evaluation rules
A definition defines a variable (a procedure)
The definition binds a symbol – the name of a variable
(procedure) – to an object – the variable’s (procedure’s)
value (body)
(define 〈variable〉 〈expression〉?)
(define ( 〈procedure〉 〈parameter〉*) 〈expression〉+)
slide 5
Compound Procedures
Procedure definitions are a means of abstraction
Use interfaces instead of implementations
– (cube x) instead of (* x x x) or (* (* x x) x)
Remember: functional programming!
(define (sum-of-squares x y)
(+ (square x) (square y))
(define (sum-of-squares x y)
(square x)
(square y)
(+ x y))
slide 6
Evaluation
Expressions are evaluated according to a substitution model of
evaluation (SME)
SME is a way to think about procedure application, but not
necessarily the manner in which the interpreter evaluates
expressions
Possible SMEs
– applicative‐order evaluation (AOE)
– normal‐order evaluation (NOE)
– evaluation rules for special forms (SFE)
slide 7
Evaluation (contd)
OE is implementation‐dependent; AOE is standard for
Scheme (and CL) expressions
NOE is used in stream processing and in macro expansions
(define‐syntax constructs)
Subexpressions are evaluated either in parallel, in left‐to‐right
or in right‐to‐left order (as in MIT Scheme)
In pure FP the result of a computation depends neither on
the OE nor on the order of evaluation of subexpressions
slide 8
Applicative OE
Applies a procedure to evaluated arguments
–
’evaluate, then apply’ order
To evaluate a (compound) expression
1. recursively evaluate all subexpressions
2. apply the (procedure that is the value of the) operator to the
(values of the) operands
(e0 e1 e2 … en) → (p a1 a2 … an) → apply
This scheme is an example of tree accumulation
–
nodes: compound expressions
–
leaves: primitive expressions
slide 9
Applicative OE (contd)
Application of a primitive procedure (RL order)
(+ (* 1 2) (/ 3 (+ 4 5)))
(+ (* 1 2) (/ 3 9))
(+ (* 1 2) 1/3)
(+ 2 1/3)
7/3
slide 10
Applicative OE (contd)
Application of a compound procedure (RL order)
(define (square x) (* x x))
(define (double x) (+ x x))
(define (double-square x) (double (square x)))
(double-square 10)
(double (square 10))
(double (* 10 10))
(double 100)
(+ 100 100)
200
slide 11
Normal OE
Applies a procedure to non‐evaluated arguments
–
’expand, then reduce’ order
To evaluate a (compound) expression
1. evaluate the operator
2. if the value is a primitive procedure, evaluate all operands and
apply the procedure
(e0 e1 e2 … en) → (pp e1 e2 … en) → (pp a1 a2 … an) → apply
3. else apply the (compound) procedure to the unevaluated
operands
(e0 e1 e2 … en) → (cp e1 e2 … en) → apply
slide 12
Normal OE
Application of a primitive procedure (RL order, except for
the operator)
(+ (* 1 2) (/ 3 (+ 4 5)))
(+ (* 1 2) (/ 3 9))
(+ (* 1 2) 1/3)
(+ 2 1/3)
7/3 ;; as in AOE
slide 13
Normal OE (contd)
Application of a compound procedure (RL order, except for the operator)
(define (square x) (* x x))
(define (double x) (+ x x))
(define (double-square x) (double (square x)))
(double-square 10)
(double (square 10))
(+ (square 10) (square 10)) ;; here comes the difference
(+ (square 10) (* 10 10))
(+ (square 10) 100)
(+ (* 10 10) 100)
(+ 100 100)
200
slide 14
Evaluation – Special Cases
Parameterless procedures and procedures with primitive
expressions in their bodies – are subject to the usual
evaluation rules
(define (compute-zero) (- 5 5))
(compute-zero) ;; apply a procedure to no arguments
(- 5 5)
;; the same for both AOE and NOE
0
(define (zero-anyway x) 0)
(zero-anyway (+ 1 2))
(zero-anyway 3) ;; skipped by NOE
0
slide 15
Evaluation – Special Cases (contd)
Define the following…
(define (zero) 0)
(define one 1)
…and try these expressions
(zero)
zero
one
(one)
slide 16
AOE vs. NOE
Define the following…
(define (double x) (+ x x))
… and compare
(double (* 123456789 987654321))
;; in AOE 🙂
(double 121932631112635269)
(+ 121932631112635269 121932631112635269)
243865262225270538
;; in NOE 🙁
(+ (* 123456789 987654321) (* 123456789 987654321))
(+ (* 123456789 987654321) 121932631112635269)
(+ 121932631112635269 121932631112635269)
243865262225270538
slide 17
AOE vs. NOE (contd)
Define the following…
(define (make-fun x y) ”just kiddin’!”)
… and compare
(make-fun (* 1234 4321) (* 1234 4321))
;; in AOE 🙁
(make-fun (* 1234 4321) 5332114)
(make-fun 5332114 5332114)
”just kiddin’!”
;; in NOE 🙂
”just kiddin’!”
slide 18
AOE vs. NOE (contd)
Who wins?
– NOE is smart, because it is lazy and evaluates a procedure’s
arguments only if they are needed (on‐demand)
– NOE is dumb if any argument is used more than once in the
procedure – it has to be recomputed each time
– AOE is smart, because it computes the arguments just once
– AOE is dumb because it has to compute all arguments even if
some of them are never used by the procedure
If procedures will use all their arguments and often use
them several times – AOE is the best.
We will use NOE in stream processing
slide 19
Conditional Expressions
Truth
– truth values for true and false are #t and #f
– an expression is false if it (its value) equals #f
– it is true otherwise (#t or any other non‐ #f)
Predicates
– examine expressions and return a truth value
– =, , not etc. (usual AOE)
– special forms or, and (SFE: LR with pre‐termination)
Conditionals perform tests and choose alternative actions
– special syntactic forms (SFE)
(cond (〈p1〉 〈e1〉) (〈p2〉 〈e2〉) … (〈pn〉 〈en〉))
(if 〈condition〉 〈consequent〉 〈alternative〉)
slide 20
AOE or NOE?
Modified exercise 1.5 in SICP – determine the OE of your interpreter
(define (compute-me) (compute-me))
(define (test x y) (and x y))
(test #f (compute-me))
;; NOE 🙂
(and #f (compute-me))
#f
;; AOE 🙁
(test #f (compute-me))
(test #f (compute-me))
…
slide 21
AOE or NOE? (contd)
Another test: use trace
(define (square x) (* x x))
(define (double x) (+ x x))
(define (skip x) 0)
(trace square)
;; see when square is used
(double (square 2)) ;; was square used once or twice?
(skip (square 2))
;; was square used?
slide 22
AOE or NOE? (contd)
Yet another test: use side effects
(define (test) (display ”test”) 0)
(define (double x) (+ x x))
(define (skip x) 0)
(double (test)) ;; was test evaluated once or twice?
(skip (test))
;; was test evaluated?
slide 23
Recursive Procedures
recursion: n. See recursion
A recursive procedure is a procedure that calls itself in its
definition (is defined in terms of itsef)
(define (even? n)
(or (= n 0)
(not (even? (- n 1)))))
(define (odd? n)
(or (= n 1)
(not (odd? (- n 1)))))
slide 24
Recursive Procedures (contd)
Procedures that are defined in terms of each other are
mutually recursive
(define (even? n)
(or (= n 0)
(not (odd? n))))
(define (odd? n)
(or (= n 1)
(even? (- n 1))))
slide 25
Conflicting Definitions
A global definition (the binding it creates) is visible
throughout the whole program
Any other global definition of the same variable (procedure)
evaluated afterwards destructively reassigns an object to
the variable (a side‐effect, in fact)
Any code dependent on this variable (procedure) may
change its behaviour (bad), fail to perform its task (worse)
or even keep doing it (worst)
Different procedures may need supporting procedures with
colliding names
slide 26
Conflicting Definitions (contd)
Problem: redefined variable (variables and procedures share
the namespace)
(define pi 3.14)
(define (area r)
(* pi r r))
(define (pi) (* 4 (atan 1))
(define (circumference r)
(* 2 (pi) r))
(area 10)
;; causes trouble
slide 27
Conflicting Definitions (contd)
Solution: internalize helpers
(define (area r)
(define pi 3.14)
(* pi r r))
(define (circumference r)
(define (pi) (* 4 (atan 1))
(* 2 (pi) r))
(area 10)
;; works!
slide 28
References and Declarations
A variable reference is a use of the variable
A variable declaration is an introduction of the variable as a
definition or as a procedure’s parameter
A variable denotation is the value of the variable
(define (p x)
(define (q y)
y)
(q (+ x 1)))
;; p and x are declarations
;; q and y are declarations
;; y is a reference
;; q and x are references
slide 29
Free and Bound Variables
A variable v occurs free in an expression E iff there is some
use of v in E that is not bound by any declaration of v in E
A variable v occurs bound in an expression E iff there is some
use of v in E that is bound by a declaration of v in E
(define (p x)
(define (q y)
y)
(q (+ x y)))
;; y is bound
;; q and x are bound, y is free
;; x occurs bound, y occurs both bound and free
;; q occurs bound
;; p is only declared (but may occur bound globally)
slide 30
Lexical Scoping
The scope of a variable declaration is the part of the code
within which references to the variable refer to the
declaration
For a top‐level definition it is the whole program (global
variable)
For a procedure’s argument it is the body of the procedure
Nested regions (blocks) in a block‐structured program may
cause shadowing of variable declarations
A declaration of a variable in a nested block creates a hole in
the scope of the variable if declared in any outer block
slide 31
Lexical Scoping (contd)
The declaration of a variable v has a scope s that includes all
references to v that occur free in the region r associated
with the declaration; those references to v that occur
bound in r are shadowed by inner declarations and are
not included in s
(define (p x)
;; the scope of x and p starts here
(define (q y)
(define (p x) ;; is shadowed here
x)
(p x))
(q x))
;; x reappears here
;; p reappears here
slide 32
Lexical Scoping (contd)
Define…
(define (p1 x)
(define (q y)
y)
(q 1))
(define (p2 x)
(define (q y)
x)
(q 1))
(define (p3 x)
(define (q x)
x
(q 1))
… and compare
(p1 2)
(p2 2)
(p3 2)
slide 33