Date: Thu, 28 Mar 2024 05:38:26 -0500 (CDT) Message-ID: <1959899609.924.1711622306647@wiki-n2.rice.edu> Subject: Exported From Confluence MIME-Version: 1.0 Content-Type: multipart/related; boundary="----=_Part_923_1653635319.1711622306645" ------=_Part_923_1653635319.1711622306645 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Content-Location: file:///C:/exported.html
Students should feel free to skip the challenge exercises.
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 s= uch as the naturals: 0, 1, 2, 3, ... . We can define the naturals and its t= emplate as follows:
; A nat= ural (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) ... ) ...]))
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 definin=
g (identifying) a subset of Scheme numbers. The definition and template use=
some built-in Scheme functions (add1
, sub1
,
Write each of the following functions on N.
!
, which is defined by the equation=
s:=20
(! 0) = =3D 1 (! (add1 n)) =3D (* (add1 n) (! n))
down
that takes an input n
in (n ... 1 =
0)
.up
that takes an input n
in (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.
Chapter 13 of the book introduces some new, compact methods for represen= ting lists, which have already been mentioned in lecture. The following exe= rcises simply let you explore how this notation behaves.
(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)))
list
.=20
(cons (= cons 1 empty) empty) (cons 1 (cons (cons 2 (cons 3 empty)) (cons 4 (cons (c= ons 5 empty) empty)))) (cons (cons (cons 'bozo empty) empty) empty)
Using '
notation we can abbreviate constant lists =
even more concisely.
'
produces strang=
e results for embedded references to true
, false
,=
()
, and empty
.'(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)))
Notice that no expressions within the scope of the '
operat=
or are evaluated.
We can think of the '
operator as distributing over the ele=
ments. We apply this rule recursively until there are no more '
operators left. This simple rule makes embedded references to true<=
/code>,
false
, and empty
behave strangely because=
'true
, 'false
, and 'empty
reduce to=
themselves as symbols, not to true
, f=
alse
, and empty
. In contrast, 'n
for some =
number n
reduces to n
.
Students should feel free to skip the challenge exercises.
In class, we used ancestor family trees as an example of inductively def=
ined tree data. In ancestor family trees, each person (a make-child=
code> structure) has two ancestors (also
make-child
structures=
) which may be empty
. In this lab, we'll use a similar, but sl=
ightly different, form of tree as an example.
In mathematics, we can use formalized arithmetic expressions as trees. F= or example,
5+(1-8)= =C3=97(7+1)
or equivalently, the Scheme code
(+ 5 (*= (- 1 8) (+ 7 1)))
which encodes expressions as lists revealing their nesting structure.
The string representation for expressions is particularly unattractive f= or computational purposes because we have to parse the string to understand= its structure. The parsing process must understand which symbols are varia= bles, operators incorporate the precedence of infix operators.
We can define a tree formulation of simple Scheme expressions which avoi= ds representing them as list and encodes far more information about their s= tructure. Parsers build tree representations for programs.
To simplify the formulation of Scheme expressions as trees, we will limi= t each addition, subtraction, multiplication, anddivision operation to exac= tly two subexpressions. We will limit the atomic elements of expressions to= numbers.
;; Give= n (define-struct add (left right)) (define-struct sub (left right)) (define-struct mul (left right)) (define-struct div (left right)) ;; an Arithmetic-Expression (AExp) is either: ;; - a number ; ;; - (make-add l r) where l,r are AExps; ;; - (make-sub l r) where l,r are AExps; ;; - (make-mul l r) where l,r are AExps; or ;; - (make-div l r) where l,r are AExps,
Using this data definition, the arithmetic expression above corresponds =
to the structure ae1
defined by
(define= ae1 (make-add 5 (make-mul (make-sub 1 8) (make-add 7 1))))
A trival AExp
is ae2
defined by
(define= ae2 16)
eval: AExp -> N
where (eval =
ae)
returns the number denoted by the expression ae
. Fo=
r example, (eval ae1)
should return -51
, and 16
.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. Rewr=
ite the preceding data definitions, examples, and the function eval=
code> using for this. As a further challenge, extend your data definition t=
o accommodate unary operations including negation and absolute value as una=
ry operators.
The following are data definitions are idealized (for the sake of simpli= city) representations of files and directories (folders). These definitions= follow the Windows convention of attaching a name to a file. They also col= lapse 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 ho= w to write functions that process directories (instead of files). For this = reason, none of the following exercises uses a directory as the primary inp= ut to a function.
Observe the mutual recursion between files and list-of-files.
(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 conten= ts 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
This set of definitions is very similar to the descendant trees data str= ucture discussed in class. Tree-based data structures are very comm= on!
; 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.
man fin= d
find?
. Following the templates leads to an overall strategy known as depth-=
first search, i.e., it explores each tree branch to the end b=
efore moving on to the next branch.; any-d= uplicate-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.
; flatt= en-dir-once : symbol file -> (file or lof) ; Purpose: returns a structure like the original file, except that any (sub= )directory with that name is removed and its contents are promoted up one l= evel in the tree.
f= oo / \ \ bar baz to-remove / \ one two becomes foo / / \ \ bar baz one two
to-rem= ove / \ \ 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.