Versions Compared

Old Version 41

changes.mady.by.user Robert Cartwright

Saved on

compared with

New Version 42

changes.mady.by.user Robert Cartwright

Saved on

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

...

Comp

...

211

...

Laboratory

...

2

...

Natural

...

Numbers

...

&

...

List

...

Abbreviations

...

Students

...

should

...

feel

...

free

...

to

...

skip

...

the

...

challenge

...

exercises.

...

Scheme's

...

Built-in

...

Naturals

...

We

...

already

...

know

...

Scheme

...

has

...

lots

...

of

...

numbers

...

built-in,

...

like

...

3,

...

17.83,

...

and

...

-14/3.

...

It

...

is

...

often

...

convenient

...

to

...

limit

...

our

...

attention

...

to

...

a

...

subset

...

of

...

these

...

such

...

as

...

the

...

naturals:

...

0,

...

1,

...

2,

...

3,

...

...

...

.

...

We

...

can

...

define

...

the

...

naturals

...

and

...

its

...

template

...

as

...

follows:

{
Code Block
}
; A natural (N) is either:
; - 0
; - (add1 n)
; where n is a natural

; Template
; nat-f : natural -> ...
;(define (f ... n ... ) 
;  (cond [(zero? n) ...] 
;        [(positive? n)
;         ... (f ... (sub1 n) ... ) ...]))
{code}

Of

...

course,

...

we

...

already

...

know

...

what

...

the

...

example

...

data

...

looks

...

like:

...

0,

...

1,

...

2,

...

3,

...

...

...

.

...

Unlike

...

most

...

data

...

definitions,

...

we

...

are

...

not

...

defining

...

new

...

Scheme

...

values

...

here

...

(

...

i.e.

...

,

...

there's

...

no

...

define-struct

...

),

...

but

...

we

...

are

...

defining

...

(identifying)

...

a

...

subset

...

of

...

Scheme

...

numbers.

...

The

...

definition

...

and

...

template

...

use

...

some

...

built-in

...

Scheme

...

functions

...

(

...

add1

...

,

...

sub1

...

,

...

zero?

...

) that

...

may

...

be

...

unfamiliar,

...

but

...

which

...

mean

...

just

...

what

...

their

...

names

...

suggest.

...

Exercises

Write each of the following functions on N.

  1. The factorial function !, which is defined by the equations:
    Code Block
    
(! 0) = 1
(! (add1 n)) = (* (add1 n) (! n))

...

  2. The function down that takes an input n in N and returns the list of N (n ... 1 0).
  3. The function up that takes an input n in N and returns the list of N (0 1 ... n). Hint: define an auxiliary function upfrom: N N -> list of N such that (upfrom m n) returns (m (add1 m) ... n). Assume that m is less than or equal to n.
List Abbreviations
Chapter 13 of the book introduces some new, compact methods for representing lists, which have already been mentioned in lecture. The following exercises simply let you explore how this notation behaves.
Finger Exercises on List Abbreviations
  1. Evaluate he following in the DrScheme interactions pane. You can cut and paste to save time if you want. 
     Code Block
    
(list 1 2 3)
(cons 1 (cons 2 (cons 3 empty)))
(list 1 2 3 empty)
(cons 1 (cons 2 (cons 3 (cons empty empty)))

...
  1. Rewrite the following using list. 
     Code Block
    
(cons (cons 1 empty) empty) (cons 1 (cons (cons 2 (cons 3 empty)) (cons 4 (cons (cons 5 empty) empty))))
(cons (cons (cons 'bozo empty) empty) empty)

List Constants
Using ' notation we can abbreviate constant lists even more concisely.
Finger Exercises on list constants
  1. Evaluate he following in the DrScheme interactions pane. You can cut and paste to save time if you want. Note that ' produces strange results for embedded references to true, false, (), and empty.
 Code Block
{code}

h3. List Constants

Using {{'}} notation we can abbreviate _constant_ lists even more concisely.

h4. Finger Exercises on list constants

# Evaluate he following in the DrScheme interactions pane.  You can cut and paste to save time if you want.  Note that {{'}} produces strange results for embedded references to {{true}}, {{false}}, {{()}}, and {{empty}}.

{code}
'(1 2 3 4)
(list 1 2 3 4)
'(rabbit bunny)
(list 'rabbit 'bunny)
'(rabbit (2) (3 4 5))
(list 'rabbit (list 2) (list 3 4 5))
'(true)
'(empty)
'(())
(list empty)
(list ())
(list 'empty)
(list '())
'((cons x y) (1 (+ 1 1) (+ 1 1 1)))
{code}

Notice 
...
 that 
...
 no 
...
 expressions 
...
 within 
...
 the 
...
 scope 
...
 of 
...
 the 
...
'
...
 operator 
...
 are 
...
evaluated
...
.
...
We 
...
 can 
...
 think 
...
 of 
...
 the 
...
'
...
 operator 
...
 as 
...
 distributing 
...
 over 
...
 the 
...
 elements. 
...
 We 
...
 apply 
...
 this 
...
 rule 
...
 recursively 
...
 until 
...
 there 
...
 are 
...
 no 
...
 more 
...
'
...
 operators 
...
 left. 
...
 This 
...
 simple 
...
 rule 
...
 makes 
...
 embedded 
...
 references 
...
 to 
...
true
...
, 
...
false
...
, 
...
 and 
...
empty
...
 behave 
...
 strangely 
...
 because 
...
'true
...
, 
...
'false
...
, 
...
 and 
...
'empty
...
 reduce 
...
 to 
...
themselves
...
 as 
...
symbols
...
, 
...
 not 
...
 to 
...
true
...
, 
...
false
...
, 
...
 and 
...
empty
...
. 
...
 In 
...
 contrast, 
...
'n
...
 for 
...
 some 
...
 number 
...
n
...
 reduces 
...
 to 
...
 n.
Trees and Mutually Recursive Data Definitions
Students should feel free to skip the challenge exercises.
Trees
In class, we used ancestor family trees as an example of inductively defined tree data. In ancestor family trees, each person (a make-child structure) has two ancestors (also make-child structures) which may be empty. In this lab, we'll use a similar, but slightly different, form of tree as an example.
In mathematics, we can formalized arithmetic expressions as trees. For example,
 Code Block
}}.

h2. Trees and Mutually Recursive Data Definitions

Students should feel free to skip the challenge exercises.

h3. Trees

In class, we used ancestor family trees as an example of inductively defined tree data. In ancestor family trees, each person (a {{make-child}} structure) has two ancestors (also {{make-child}} structures) which may be {{empty}}. In this lab, we'll use a similar, but slightly different, form of tree as an example.

In mathematics, we can formalized arithmetic expressions as trees. For example,
{code}
5+(1-8)×(7+1)
{code}

or 
...
 equivalently, 
...
 the 
...
 Scheme 
...
 code

{
 Code Block
}
(+ 5 (* (- 1 8) (+ 7 1)))
{code}

which 
...
 encodes 
...
 expressions 
...
 as 
...
 lists 
...
 revealing 
...
 their 
...
 nesting 
...
 structure. 
...
The 
...
 string 
...
 representation 
...
 for 
...
 expressions 
...
 is 
...
 particularly 
...
 unattractive 
...
 for 
...
 computational 
...
 purposes 
...
 because 
...
 we 
...
 have 
...
 to 
...
 parse 
...
 the 
...
 string 
...
 to 
...
 understand 
...
 its 
...
 structure. 
...
 The 
...
 parsing 
...
 process 
...
 must 
...
 understand 
...
 which 
...
 symbols 
...
 are 
...
 variables, 
...
 operators 
...
 incorporate 
...
 the 
...
 precedence 
...
 of 
...
 infix 
...
 operators.
...
We 
...
 can 
...
 define 
...
 a 
...
 tree 
...
 formulation 
...
 of 
...
 simple 
...
 Scheme 
...
 expressions 
...
 which 
...
 avoids 
...
 representing 
...
 them 
...
 as 
...
 list 
...
 and 
...
 encodes 
...
 far 
...
 more 
...
 information 
...
 about 
...
 their 
...
 structure. 
...
 Parsers 
...
 build 
...
 tree 
...
 representations 
...
 for 
...
 programs.
...
To 
...
 simplify 
...
 the 
...
 formulation 
...
 of 
...
 Scheme 
...
 expressions 
...
 as 
...
 trees, 
...
 we 
...
 will 
...
 limit 
...
 each 
...
 addition, 
...
 subtraction, 
...
 multiplication, 
...
 anddivision 
...
 operation 
...
 to 
...
 exactly 
...
 two 
...
 subexpressions. 
...
 We 
...
 will 
...
 limit 
...
 the 
...
 atomic 
...
 elements 
...
 of 
...
 expressions 
...
 to 
...
 numbers.

{
 Code Block
}
;; Given

(define-struct add (m n)) 
(define-struct sub (m n)) 
(define-struct mul (m n)) 
(define-struct div (m n)) 

;; an Arithmetic-Expression (AExp) is either:
;; - a number ;
;; - (make-add m n) where m,n are AExps;
;; - (make-sub m n where m,n are AExps; 
;; - (make-mul m n where m,n are AExps; or
;; - (make-div m n where m,n are AExps,
{code}


Using 
...
 this 
...
 data 
...
 definition, 
...
 the 
...
 arithmetic 
...
 expression 
...
 above 
...
 corresponds 
...
 to 
...
 the 
...
 structure ae1 defined by
 Code Block
 {{ae1}} defined by
{code}
(define ae1 (make-add 5 (make-mul (make-sub 1 8) (make-add 7 1))))
{code}

A 
...
 trival 
...
AExp
...
 is 
...
ae2
...
 defined 
...
 by

{
 Code Block
}
(define ae2 16)
{code}

h4. Exercises on Arithmetic Expressions

# Develop the function {{eval: AExp -> N}} where {{(eval ae)}} returns the number denoted by the expression {{ae}}.  For example, {{(eval ae1)}} should return {{\-51}}, and {{(eval ae2)}} should return {{16}}.

# 
Exercises on Arithmetic Expressions
  1. Develop the function eval: AExp -> N where (eval ae) returns the number denoted by the expression ae. For example, (eval ae1) should return -51, and (eval ae2) should return 16.
  1.  Wiki Markup
    \[Challenge\] Assume that our expression language includes many basic operations, not just the four supported by {{AExp}}.  We would want a single representation for the application of a binary operator to arguments and use a separate data definition enumerating all of our operations. Rewrite the preceding data definitions, examples,
and the function {{eval}} using for this.  As a further challenge, extend your data definition to accommodate unary operations including negation and absolute value as unary operators.
...
Files and Directories
The following are data definitions are idealized (for the sake of simplicity) representations of files and directories (folders). 
...
 These 
...
 definitions 
...
 follow 
...
 the 
...
 Windows 
...
 convention 
...
 of 
...
 attaching 
...
 a 
...
 name 
...
 to 
...
 a 
...
 file. 
...
 They 
...
 also 
...
 collapse 
...
 the 
...
 definition 
...
 of 
...
 the 
...
 directory 
...
 type 
...
 into 
...
 a 
...
 clause 
...
 in 
...
 the 
...
 definition 
...
 of 
...
 a 
...
 file, 
...
 which 
...
 makes 
...
 the 
...
 set 
...
 f 
...
 definitions 
...
 more 
...
 compact 
...
 but 
...
 obfuscates 
...
 how 
...
 to 
...
 write 
...
 functions 
...
 that 
...
 process 
...
 directories 
...
 (instead 
...
 of 
...
 files). 
...
 For 
...
 this 
...
 reason, 
...
 none 
...
 of 
...
 the 
...
 following 
...
 exercises 
...
 uses 
...
 a 
...
 directory 
...
 as 
...
 the 
...
 primary 
...
 input 
...
 to 
...
 a 
...
 function.
...
Observe 
...
 the 
...
 mutual 
...
 recursion 
...
 between 
...
 files 
...
 and 
...
 list-of-files.
 Code Block


{code}
(define-struct dir (name contents))

; A file is either:
; - a symbol (representing a "simple" file's name) or
; - a directory (make-dir name contents) where name is a symbol, and contents is a lof.


; A list-of-files (lof) is one of
; - empty or
; - (cons f lofd) where f is a file and lofd is a lof
{code}

This 
...
 set 
...
 of 
...
 definitions 
...
 is 
...
 very 
...
 similar 
...
 to 
...
 the 
...
 descendant 
...
 trees 
...
 data 
...
 structure 
...
 discussed 
...
 in 
...
 class. 
...
Tree-based 
...
 data 
...
 structures 
...
 are 
...
 very 
...
 common!
...
Directory exercises
  1. Create some sample data for the above types.
  2. Write the templates for the above types.
  3. Develop a function 
     Code Block
    
; find? : symbol file -> boolean
; Returns whether the filename is anywhere in the
; tree of files represented by the file. This includes both
; simple file names and directory names.

...
  1.  (empty 
...
  1.  line)
...

  1.  Note 
...
  1.  that 
...
  1.  this 
...
  1.  function 
...
  1.  is 
...
  1.  a 
...
  1.  vast 
...
  1.  simplification 
...
  1.  of{{find}}, 
...
  1.  the 
...
  1.  mother-of-all 
...
  1.  everything-but-the-kitchen-sink 
...
  1.  UNIX 
...
  1.  directory 
...
  1.  traversing 
...
  1.  command. 
...
  1.  If 
...
  1.  open 
...
  1.  a 
...
  1.  terminal 
...
  1.  window 
...
  1.  and 
...
  1.  enter 
...
  1.  Code Block
...
  1. 
man find

...
  1.  to 
...
  1.  see 
...
  1.  what 
...
  1.  it 
...
  1.  can 
...
  1.  do.
...

  1.  (empty 
...
  1.  line)
...

  1.  Use 
...
  1.  DrScheme's 
...
  1.  stepper 
...
  1.  to 
...
  1.  step 
...
  1.  through 
...
  1.  an 
...
  1.  example 
...
  1.  use 
...
  1.  of 
...
  1. find?
...
  1. . 
...
  1.  Following 
...
  1.  the 
...
  1.  templates 
...
  1.  leads 
...
  1.  to 
...
  1.  an 
...
  1.  overall 
...
  1.  strategy 
...
  1.  known 
...
  1.  as 
...
  1. depth-first 
...
  1.  search
...
  1. , 
...
  1. i.e.
...
  1. , 
...
  1.  it 
...
  1.  explores 
...
  1.  each 
...
  1.  tree 
...
  1.  branch 
...
  1.  to 
...
  1.  the 
...
  1.  end 
...
  1.  before 
...
  1.  moving 
...
  1.  on 
...
  1.  to 
...
  1.  the 
...
  1.  next 
...
  1.  branch.
...
  2. Develop 
...
  1.  the 
...
  1.  following 
...
  1.  function: 
...
  1.  Code Block
...
  1. 
; any-duplicate-names? : file -> boolean
; Returns whether any (sub)directory directly or indirectly contains
; another directory or file of the same name. It does NOT check
; for duplicated names in separate branches of the tree.

...
  1.  (empty 
...
  1.  line)
...

  1.  There 
...
  1.  is 
...
  1.  a 
...
  1.  straightforward 
...
  1.  way 
...
  1.  to 
...
  1.  write 
...
  1.  this 
...
  1.  function 
...
  1.  that 
...
  1.  just 
...
  1.  follows 
...
  1.  the 
...
  1.  template.
...

  1.  (empty 
...
  1.  line)
...
  2. Challenge: 
...
  1.  develop 
...
  1.  a 
...
  1.  program 
...
  1.  to 
...
  1.  check 
...
  1.  for 
...
  1.  duplicated 
...
  1.  names 
...
  1.  among
...

  1.  all 
...
  1.  directories 
...
  1.  and 
...
  1.  files 
...
  1.  in 
...
  1.  the 
...
  1.  given 
...
  1.  tree, 
...
  1.  not 
...
  1.  just 
...
  1.  subdirectories.
...

  1.  Here's 
...
  1.  a 
...
  1.  hint. 
...
  1. Develop the 
...
  1.  following 
...
  1.  function: 
...
  1.  Code Block
...
  1.  ; 
...
  1.  flatten-dir-once 
...
  1.  : 
...
  1.  symbol 
...
  1.  file 
...
  1.  -> 
...
  1.  (file 
...
  1.  or 
...
  1.  lof)
...

  1.  ; 
...
  1.  Purpose: 
...
  1.  returns 
...
  1.  a 
...
  1.  structure 
...
  1.  like 
...
  1.  the 
...
  1.  original 
...
  1.  file, 
...
  1.  except 
...
  1.  that 
...
  1.  any 
...
  1.  (sub)directory 
...
  1.  with 
...
  1.  that 
...
  1.  name 
...
  1.  is 
...
  1.  removed 
...
  1.  and 
...
  1.  its 
...
  1.  contents 
...
  1.  are 
...
  1.  promoted 
...
  1.  up 
...
  1.  one 
...
  1.  level 
...
  1.  in 
...
  1.  the 
...
  1.  tree.
...

  1.  (empty 
...
  1.  line)
...

  1.  Here 
...
  1.  are 
...
  1.  two 
...
  1.  pictorial 
...
  1.  examples, 
...
  1.  in 
...
  1.  both 
...
  1.  cases 
...
  1.  removing 
...
  1.  the 
...
  1.  directory
...

  1.  namedto-remove. 
...
  1.  These 
...
  1.  illustrate 
...
  1.  why 
...
  1.  this 
...
  1.  function 
...
  1.  can
...

  1.  return 
...
  1.  either 
...
  1.  a 
...
  1.  file 
...
  1.  or 
...
  1.  a 
...
  1.  list 
...
  1.  of 
...
  1.  files.
...
Example 
...
 1: 
...
 foo
 / \ \
 bar baz to-remove
 / \
 one two
becomes
 foo
 / / \ \
 bar baz one two
...
Example 2:
...
 to-remove
 / \ \
 foo bar baz
becomes
foo bar baz
Follow the templates and think about a single
 case at a time. If you do that, this exercise is not too difficult. If you don't follow the templates, you
 are likely to run into difficulty.