CMPUT 325 Schedule and Outcomes - 3. Week 1

CMPUT 325 Schedule and Outcomes

3. Week 1 - Jan 6

3.1 The Plan

This is the first time that we have taught CMPUT 325 in a combined lecture lab setting, so this is an approximate plan for how the course will evolve over the next 13 weeks. It will be updated with what actually happened.

Alan Perlis famously quipped ''Lisp programmers know the value of everything and the cost of nothing.'' (from Section 18 Performance from the Racket Language Guide).

3.2 Topics

Syllabus
1. syllabus
2. SICP ref
3. software
Syntax, Semantics, and Programming Styles
The DrRacket IDE,
An intoduction to Scheme by examples

The overall goal of the first week is to turn you into competent novice Scheme programmers, what could be called "shallow functional programming". That is, you have a working grasp of:

functions are first class entities
data structures are typically recursive compositions of lists
recursion replaces iteration
typing is dynamic
state is not exposed in an easily mutable way

Key Idea

Code in the form of a loop in an imperative language can be easily transformed into iterated composition of a state transition function. This is not necessarily the most religiously functional solution to the problem you want to solve.

3.3 Dr Racket IDE

Handy shortcuts for DrRacket

<esc> p	prev expr in interactions window. Note <esc> then p
<esc> n	next expr
Fn-F5	run
^p	prev
^n	next
^a	start of line
^e	end of line

Box Comments in DrRacket

Please do not use the box comment feature in racket (only 1 of you did), because it generates annoying GRacket marked up text. For example, this little 4 line program:

#lang racket (define (f x y) (+ x y)) ; This is a box comment, which creates ; an unreadable .rkt file

when the last two lines are made into a box comment creates a 263 line file of 8770 characters! Here is some of it. It makes you yearn for the simple concise expressivity of XML. code/Week01/badbox.rkt

|#

30 7 #"wxtext\0"

3 1 6 #"wxtab\0"

1 1 8 #"wximage\0"

2 0 8 #"wxmedia\0"

4 1 34 #"(lib \"syntax-browser.ss\" \"mrlib\")\0"

1 0 16 #"drscheme:number\0"

3 0 44 #"(lib \"number-snip.ss\" \"drscheme\" \"private\")\0"

1 0 36 #"(lib \"comment-snip.ss\" \"framework\")\0"

1 0 93

(

#"((lib \"collapsed-snipclass.ss\" \"framework\") (lib \"collapsed-sni"

#"pclass-wxme.ss\" \"framework\"))\0"

) 0 0 43 #"(lib \"collapsed-snipclass.ss\" \"framework\")\0"

0 0 19 #"drscheme:sexp-snip\0"

0 0 36 #"(lib \"cache-image-snip.ss\" \"mrlib\")\0"

1 0 68

(

... and so on painfully.

3.4 Flipped Work

Take a look at the initial sections of SICP.

Work on the following problems. They must be solved using the restricted version of Scheme introduced in class. You are permitted to create auxiliary functions as necessary.

Question 1 - List building with cons

Implement the functions list2 and list3 that construct lists of 2 and 3 elements respectively. For example (list2 2 3) is the list (2 3)
(list3 1 5 7) is the list (1 5 7) NOTE: You can use these functions in the other questions of this assignment.

Question 2 - Map and Reduce

Implement the fmap and freduce functions.

The fmap operator takes a unary function fn and a list L, and (fmap fn L) returns the list resulting from applying fn to each element of L. For example, (fmap (lambda (x) (< x 5)) '(1 7 3 5 7 9)) results in (#t #f #t #f #f #f) NOTE: Scheme has a builtin map operator (but you are not allowed to use it).

The freduce operator takes an associative binary function op, an identity element e for op, and a list L. Then (freduce op e L) computes the result of inserting op between each element of the list. The identity element is the result of reducing an empty or one element list.

For example, (freduce + 0 '(4 5 6)) results in 15

Question 3 - Deep list equality

Implement the function lequal that tests if two lists are equal. This means that they have the same structure and their atoms (leaves) match. For example:

These all return true

 (lequal 1 1) 

 (lequal '() '()) 

 (lequal '(1) '(1)) 

 (lequal '(1 (2) (3 4)) '(1 (2) (3 4)))

and these all return false

 (lequal 1 '()) 

 (lequal '() 1) 

 (lequal '() '(1)) 

 (lequal '(1) '()) 

 (lequal '(1) '(2))

NOTE: You can assume that only integers appear as atoms in the lists.

Question 4 - Constructing lists

Implement the function (genindex n) that generates a list consisting of the indexes (0 1 2 ... n-1). That is, the indexes that you would use to index into an n element array.

(genindex 0) is ()
(genindex 1) is (0)
(genindex 4) is (0 1 2 3)

Implement the function (genseq low high inc) that generates a list consisting of the integers

(low low+inc low+inc+inc ... high)

For example

(genseq 2 5 1) is (2 3 4 5)
(genseq 10 20 7) is (10 17)
(genseq 8 7) is ( )

NOTE: think about how fmap relates genindex and genseq. You can use fcompose also if you want.

Question 5 - Binary tree simplification

Lists that contain lists can be thought of as trees. Lists of length 2 or less represent binary trees.

Let's define a binary tree simplification as follows: If a vertex in the tree only has one branch, then the branch is moved up one level in the tree. Whenever the left and right branches of a tree match exactly, the right branch can be deleted, and the left moves up towards the root.

For example, this tree ( (1 2) (1 2) ) simplifies to (1 2), while this (1 (2 2)) simplifies to (1 2)

This more complicated tree ( (1 (2 2)) (1 (2) ) ) simplifies to ( (1 2) (1 (2) ) ) which then further simplifies to ( (1 2) (1 2) ) which then simplifies to (1 2)

Implement the function (simplify T) which does this.

3.5 Sample Solutions to Flipped Work

code/Week01/exercises.rkt

#lang scheme

; part 1

(define list2 (lambda (e1 e2) (cons e1 (cons e2 '()))))

(define list3 (lambda (e1 e2 e3) (cons e1 (cons e2 (cons e3 '() )))))

; part 2 - map and reduce

(define fmap (lambda (fn L)

(if (null? L)

'()

(cons (fn (first L)) (fmap fn (rest L)))

))

)

; compare the run-time stacks of these two solutions

; non-tail recursive - there is still work to do after the recursive call

(define freduce-non-tail (lambda (identity fn L)

(if (null? L)

identity

(fn (first L) (freduce identity fn (rest L)))

)))

; tail recursive solution

(define freduce (lambda (left-accumulate fn L)

(if (null? L)

identity

(freduce (fn left-accumulate (first L)) fn (rest L))

)))

; part 3 - deep list equality

(define both-are-lists? (lambda (x y)

(and (list? x) (list? y))

))

(define both-are-null? (lambda (x y)

(and (null? x) (null? y))

))

(define both-are-not-null? (lambda (x y)

(and (not (null? x)) (not (null? y)) )

))

(define both-are-numbers? (lambda (x y)

(and (number? x) (number? y))

))

(define lequal? (lambda (x y)

(if (both-are-lists? x y)

(if (both-are-not-null? x y)

(and

(lequal? (first x) (first y))

(lequal? (rest x) (rest y))

)

(both-are-null? x y)

)

(if (both-are-numbers? x y)

(= x y)

#f

)

))

; part 4 - list construction

(define genindex (lambda (n) (genindex_r 0 n)))

(define genindex_r (lambda (i n)

(if (>= i n)

'()

(cons i (genindex_r (+ 1 i) n))

)))

(define genseq (lambda (low high inc)

(fmap (lambda (i) (+ low (* i inc)))

(genindex (+ 1 (quotient (- high low) inc) ) )

)

))

; part 5 binary tree simplification

; if L and R are different return (L R) else return L

(define simplify_pair (lambda (L R)

(if (lequal? L R)

L

(list2 L R)

)

))

(define simplify

(lambda (L)

(if (not (list? L))

; non-lists are already simple

L

(if (null? L)

; empty lists are simple

L

(if (null? (rest L))

; 1 element lists are replaced by simplified first element

(simplify (first L))

(if (null? (rest (rest L)))

; 2 element lists need the pair simplified

(simplify_pair (simplify (first L))

(simplify (second L)))

; > 2 element lists have their terms simplified, but

; can't be simplified at the node since they are not

; binary trees

(fmap simplify L)

)

)))

(simplify '((1 1) (1 (1 1))))

3.6 Formative Quiz

For the purpose of this quiz, only restricted Scheme and the functions you created for the flipped exercises can be used.

Implement the function (fmap2 fn X Y) that takes a 2-argument function fn, and two lists X and Y, and produces a new list that results from applying fn to corrsponding elements of X and Y.

That is, If X = (x_0 x_1 ... x_n) and Y = (y_0 y_1 ... y_n) then (fmap fn X Y) is the list ( (fn x_0 y_0) (fn x_1 y_1) ... (fn x_n y_n) )

If the lists have different lengths, then the mapping stops when the shorter list becomes empty.

For example,

(fmap2 min '(1 2 3 4 5) '(0 3 2 4 6)) is (0 2 2 4 5) (fmap2 min '(1 2 3) '(0 3 2 4 6)) is (0 2 2)

Challenge: Write a cyclic version, fmapc which does the same as fmap, but if the lists are different lengths, then when the shorter one runs out, additional elements are taken from the beginning of the shorter list, cycling until the longer list is complete.

For example,

(fmap2c + '(1 2 3 4 5) '(0 1)) is (1 3 3 5 5)
(fmap2c + '(1 2 3 4 5 6 7) '()) is '()
(fmap2c + '(1 2 3 4 5 6 7) '(1)) is '(2 3 4 5 6 7 8)
(fmap2c + '(1 2 3 4 5 6 7) '(1 2 3 4 5 6)) is '(2 4 6 8 10 12 8)

3. Week 1 - Jan 6
CMPUT 325 Schedule / Version 2.31 2014-04-04