CS275Lab 02
Lists and RecursionDue: Monday, September 24 at 11:59 PM
The goals for this assignment are increasing your skills withWriting Scheme functionsUsing recursion with flat listsUsing lists to structure dataYou can use the solution to any exercise as a helper function in subsequent exercises, and you can also write stand–alone helper functions.. ExercisesPart 1 – Lists as structuresWrite a function merge that merges two sorted lists of numbers onto one sorted list, the way MergeSort works.(merge ‘(1 4 5) ‘(2 3 4 6)) returns (1 2 3 4 4 5 6)
Write a sort function for lists of numbers. Don’t get the idea from (1) that you should do MergeSort. Try InsertionSort.
(sort ‘(5 1 8 3 7)) returns (1 3 5 7 8)
Write function contains-sublist that determines if a list contains a particular sublist:.(contains-sublist ‘(2 3 4) ‘(1 2 3 4 5) ) returns #t(contains-sublist ‘(2 3 4) ‘(1 2 5 3 4)) returns #f
Write function rember-sublist that removes the first occurrance of the sublist from the given list(rember-sublist ‘(2 3 4) ‘(1 2 3 4 5 ) ) returns (1 5)
Part 2 – Association ListsFlat lists aren’t a very good way to store data. An obvious improvement is to have the list consist of elements, each of which is itself a list, representing the data for one individual. For example, we might make a phone-book as a list of name, phone number pairs. Such a structure is called an association list. For example,(define phone-book
‘( (barbara 775-1234) (luke 774-2839) (nick 775-0912) (valerie 775-9043) ))Write function (phone-number person phone-book) that returns the phone number of the given person, or the atom ‘disconnected if there is no entry for the person.
With the phone book defined above (phone-number ‘nick phone-book) returns 775-0912.
Write funtion (person phone-number phone-book)that returns the name of the person with the given phone number.
So (person ‘775-0912 phone-book) returns nick.
Part 3 – Accumulator-Passing StyleWrite function (length lat) that returns the length (number of elements) of lat, and does it by calling an accumulator-passing style function (length-a lat acc). So (length ‘(a b c)) returns 3. Your length-a function should be tail-recursive.
Write function (count a lat) that returns the number of occurrences of atom a in lat, and does it by calling an accumulator-passing style function (count-a a lat acc). So (count ‘x ‘(a b x d c e x x a x)) returns 4.
Your count-a function should be tail-recursive.
Write function (max vec) which returns the largest element in a flat list of positive numbers.. So (max ‘(3 6 1 9 4 7 2 6) should return 9. Function max should call an accumulator-passing style function max-a.
Function (index a lat) returns the 0-based index of the first occurrence of atom a in a flat list of atoms.. As usual, (index a l;at) should return -1 if a is not an element of lat. So (index ‘c ‘(a b c d e d c b a) returns 2 and index( ‘c ‘(a b d e f)) returns -11. Write function index in accumulator-passing style.
CSCI 275Lab 03
Structured ListsDue: Tuesday, October 2 (midnight at the end of Tuesday)
The goals for this assignment are increasing your skills withWriting Scheme functionsUsing recursion with arbitrary listsGetting some practice with Map and ApplyUsing Scheme for some basic mathematical operations with vectors and matrices.You can use the solution to any exercise as a helper function in subsequent exercises.Assume the following data types for input to the functions:a, b, c …atoms (numbers or symbols)n, m, …numberslatA list of atomslystA list of any kindvecA list of numbers (a vector)matA matrix — a list of lists, all of the same length, which make up the rows of the matrix. In this lab the matrix entries will be numbers.ExercisesWrite (firsts llyst) and (rests llyst). For both of these llyst is a list of lists. (firsts llyst) returns a new list with the cars of each element of llyst; (rests llyst) returns a new list with the cdrs of each element of llyst.(firsts ‘( (a b c) (d e f) (g h i) ) ) returns (a d g)(rests ‘( (a b c) (d e f) (g h i) ) ) returns ( (b c) (e f) (h i) )
Write (addvec vec1 vec2), where vec1 and vec2 are vectors (lists of numbers) with the same length. This returns a vector containing the sums of the corresponding elements of vec1 and vec2.(addvec ‘(1 2 3) ‘(4 5 6) ) returns (5 7 9)(addvec ‘( ) ‘( ) ) returrns ( )
Write (dot-product vec1 vec2), where again vec1 and vec2 are vectors with the same length. This returns the sum of the products of the corresponding elements of vec1 and vec2.(dot-product ‘(1 2 3) ‘(4 5 6) ) returns 32 (= 1*4 + 2*5 + 3*6)(dot-product ‘( ) ‘( )) returns 0
Write (dot-row vec mat), where the length of vec is the same as the length of each row of mat. This returns a vector containing the dot-product of vec with each row of mat.(dot-row ‘(1 2 3) ‘((1 4 7) (2 5 8) (3 6 9)) ) returns (30 36 42)
Write (transpose mat), which returns the transpose of mat. This interchanges the rows and the columns of mat, i.e., the first row of mat is the first column of the transpose, the second row of mat becomes the second column of the transpose, and so forth. Hint: use firsts and rests.(transpose ‘((1 2 3) (4 5 6)) ) returns ((1 4) (2 5) (3 6) )
Write (matmult mat1, mat2), which returns the matrix product of mat1 and mat2. The entry of the ith row and jth column of the product is the dot-product of row i of mat1 and column j of mat2. For this to make sense the lengths of the rows of mat1 must be the same as the lengths of the columns of mat2. For example,
(matmult ‘((1 2 3) (4 5 6)) ‘((1 2) (3 4) (5 6)) ) returns ((22 28) (49 64))
Hint: use a helper function that works with mat1 and the transpose of mat2. This helper function makes a lot of use of dot-row.
Write (flatten L) that takes a list L and creates a flat list wth the same elements.
(flatten ‘(x y z z y) ) returns(x y z z y)(flatten ‘(a (x (y)) (((y)) y z)) returns (a x y y y z)
Consider a list, not necessarily flat, of numbers, such as ( (1 (2)) (((4))) 5). Use map and apply to write a procedure (sum L) that sums all of the numbers in such a list.
Again consider a general list of numbers and a function f of one argument. Use map and apply to write a procedure (apply-to f L) that builds a new list with the same structure as L, only f is applied to each of the elements of L to get the values in the new list. For example, (apply-to add1 ‘(3 (4 5))) is (4 (5 6)).
Write the procedure (element-of? a L) that returns true if atom a is an element of (not-necessarily flat) list L.
CS275HW 04
Higher Order FunctionsDue at midnight at the end of Wednesday, October 10. MONDAY, October 15. sigh.
The goal for this assignment is to give you a deeper understanding of recursion, particularly on complex structuresPart 1: FoldIn each of the following you can use either of the folds we have discussed: foldl or foldrUse fold to write (index a lat), which returns the 0-based index of atom a in lat, or -1 if a is not an element of lat.
Use fold to write (replace a b lat), which replaces every instance of atom a with atom b. For example (replace 3 5 ‘(1 2 3 4 5 4 3 2 1)) returns (1 2 5 4 5 4 5 2 1).
Assume bags is globally defined to be an association list containing sublists of two elements. Each sublist represents the name of a piece of luggage and its respective weight, where the car is the name of the piece of luggage and the cadr is the weight. Such a list might look like this:
(define bags ‘((duffle 8) (garment-bag 2) (briefcase 5) (valise 7) (steamer-trunk 65))).Use fold to write a procedure (weigh bags) which takes a baggage list and returns the total weight. For the baggage list shown above this should return 87.Use fold to write a procedure (heaviest bags) which returns the name of the bag with maximum weight. Assume that no weights are negative. For the baggage list above this should return ‘steamer-trunk.Part 2: TreesFor the rest of this assignment you will write a number of procedures that involve trees. Recall that a tree is a data structure that is either empty, or contains some data and has a list of children, each of which is a tree.We will use Scheme procedures to implement the data type. At the beginning of the following section the tree datatype will be defined. All of this code is contained in the file “TreeDatatype.rkt”.#lang racket
(require “TreeDatatype.rkt”)You will need to download the file TreeDatatype.rkt Please include this file in your handin folder.Introduction — the tree structureA tree is eitheran empty tree, which has no fieldsa non-empty tree, which has a value field containing a number and a list-of-children field containing a list of children of the node, which are themselves trees.
(define tree? (lambda (t) (or (empty-tree? t) (non-empty-tree? t))))(define empty-tree? (lambda (x) (null? x)))(define non-empty-tree? (lambda (x) (cond [(list? x) (eq? (car x) 'tree)] [else #f]))); constructors(define non-empty-tree (lambda (value list-of-children) (list 'tree value list-of-children)))(define empty-tree (lambda () null)); Convenience constructor (define makeTree (lambda l (non-empty-tree (car l) (cdr l)))); utility functions(define value (lambda (tree) (cond [(empty-tree? tree) 'error] [else (cadr tree)])))(define list-of-children (lambda (tree) (cond [(empty-tree? tree) 'error] [else (caddr tree)])))(define number-of-children (lambda (tr) (cond [(empty-tree? tree) 'error] [else (length (list-of-children tr))])))(define leaf? (lambda (tr) (cond [(empty-tree? tree) 'error] [else (zero? (number-of-children tr))]))) ; example trees(define Empty (empty-tree))(define T1 (makeTree 50)) (define T2 (makeTree 22)) (define T3 (makeTree 10)) (define T4 (makeTree 5)) (define T5 (makeTree 17)) (define T6 (makeTree 73 T1 T2 T3)) (define T7 (makeTree 100 T4 T5)) (define T8 (makeTree 16 T6 T7))
For example, here is a picture of T8 showing the others as subtrees:
All of this code is in file TreeDatatype.rkt
In the exercises that follow, you should use higher-order functions like map, apply, and fold to make your solution as concise as possible. You should also use letrecto define any recursive help functions.All programs should be written using the tree operators defined above. Don’t directly manipulate the list representations; use the tree procedures.As usual, if the solution to an earlier problem is useful in a later one, go ahead and use it.Tree Exercises:In all of these tr is a value of the tree datatype(childSum tr) This returns the sum of the values in the children of the given node. The tree is assumed to be non-empty.
(childSum T8) returns 173;
(childSum T6) returns 82.(allSum tr) This sums the entire set of values found in the tree. If tree is empty it returns 0.
(allSum T8) is 293
(allSum T6) is 155
(visitTree f tr) Here f is a function of 1 numerical variable. This returns a new tree with the same structure only every value v in tree has been transformed to (f v).
(sizeof tr) This returns the number of nodes in the subtree rooted at the given node.
(sizeof T8) returns 8
(sizeof T6) retrurns 4
(height tr) Returns the height of the tree — the maxiumum number of edges from root to leaf.. Assume that the empty tree has height -1, a single-node tree (a leaf) has height 0, etc.
(height T1) returns 0
(height T8) returns 2
(count n tr) Returns the number of times value n appears in the tree.
(count 22 T8) returns 1
(count 7 T8) returns 0
Each of the next two procedures produces a flat list of the values in the tree. They differ only in the order in which the values are listed:
(preorder tr) lists the value at the root ahead of the values of the children.
(preorder T8) returns (16 73 50 22 10 100 5 17)
(postorder tr) lists the value at the root after the values of the children.
(postorder T8) returns (50 22 10 73 5 17 100 16)
CS275Lab 05
Interpreters 1— Creating an environment
This is due Friday, October 19 at midnight
This is the first portion of your Scheme interpreter. The initial portion of this lab is material we discussed in class on Thursday, March 8. If you followed this you can skip down to the 3 exercises at the end of this document.Section 1: EnvironmentsWe need to create an environment to hold the data for the expressions we will interpret. The scoping rules for Scheme determine the structure of this environment. Consider the following three examples. First
(let ([x 2] [y 3]) (+ x y))
This has an environment with bindings for x and y created in a let-block. These bindings are used in the body of the let.Next, consider the following. This has a let-block that creates a lamba-expression, which is called in the body of the let:
(let ([f (lambda (x) (+ x 4))]) (f 5))
Finally, we combine these. At the outer level in the following expression we have a let-block with bindings for x and y. The body is another, nested, let, which binds a lembda expression with a parameter x. The body of the interior let is a call to the function.
(let ([x 2] [y 3] (let ([f (lambda(x) (+ x y))]) (f 5)))
Environments are extended in two ways. Let expressions have bindings that extend the current environment; the body of the let is evaluated in the extended environment. Lambda expressions do not extend the environment; they simply list the variables that will be bound when the function is called. The function call is the point where the environment (the closure’s environment) is extended, with the parameters from the lambda expression being bound to the values of the arguments.We will define the environment as an association list, where symbols are associated with values. There are two ways we might do this. In the first example above, where x is bound to 2 and y to 3, we might use the list ( (x 2) (y 3) ), or we might use ( (x y) ( 2 3) ). The former structure is closer to the way the bindings appear in let-expressions; the latter is closer to the components of a call. The former structure might appear simpler, but thanks to procedure map, the latter is actually easier to code and we will go with that.Scheme, and most other languages you are likely to use, employs lexical scoping. When we want to resolve the binding for a free variable, we look first in the current scope, then in the surrounding scope, then in the scope that surrounds that, until the variable is found or we reach the outermost scope. To implement this our environments will be structured as linked lists, with the head of the list the current scope and the tail the previous environment. Thus, the environment for the expresson
(let ([x 2] [y 3]) (let ([z 4] [x 5]) (+ x (+ y z))))
will be ( ( (z x) (4 5) ) ((x y) (2 3)) )When we resolve the bindings for x, y and z to evaluate (+ x (+ y z) ) we first find the binding 5 for x, and of course we find 4 for z and 3 for y. This leads to the correct value, 12 for the expression.Similarly, in the expression(let ([x 2]
[y 3]) (let ([f (lambda(x) (+ x y))]) (f 5)))
we evaluate the call (f 5) by evaluating the body of f, (+ x y) in an environment that first has x bound to 5, and then has the environment surrounding the defintion of f:( (x) (5) ( (x y) (2 3) ) )You will see in the next two labs how this environment is created. At present we need to create the tools that will allow this.Section 2: The environment datatypeThe two most important featues of an environment are that we need to be able to look up symbols to get the values they are bound to, and we need to be able to extend an environment with new bindings to get a new environment. We’ll define an environment as either the empty environment, with no bindings, or an extended environment with a list of symbols, a corresponding list of the values those symbols are bound to, and a previous environment that is being extended. Here are constructor functions for the two types of environment:(define empty-env (lambda () (list ’empty-env)))“`
(define extended-env (lambda (syms vals old-env) (list ‘extended-env syms vals old-env)))
These lead to easy recognizer functions:
We can define a unique empty environment (whick lets us check if we are in the empty environment:
(define the-empty-env (empty-env))We build up new environments with procedure extended-env. For example(define EnvA (extended-env ‘(x y) ‘(1 2) the-empty-env))
(define EnvB (extended-env ‘(x z) ‘(5 7) EnvA))
All that remains is to build some helper functions to look up bindings in an environment.Section 3: ExercisesExercise 1: lookup-envCreate a Scheme file env.rkt that contains the datatype definitions above. Write function lookup-env, which takes an environment and a symbol and returns the first binding for that symbol in the environment. For example, with environments EnvA and EnvB defined as above(lookup-env EnvA ‘x) should return 1
(lookup-env EnvB ‘x) should return 5
(lookup-env EnvB ‘y) should return 2
(lookup-env EnvB ‘bob) should cause an errorIf lookup-env does not find a binding for the symbol you should invoke the error handler (error sym string ), as in(error ‘apply-env “No binding for ~s” sym) Exercise 2: init-envAdd to your env.rkt file definitions of the-empty-env and a new environment called init-env that contains bindings for variables x and y to numbers 10 and 23; we will use this initial environment to test out features of the MiniScheme interpreter before we implement expressions that allow us to extend the environment with new bindings.Exercise 3: provide and testingMake your env.rkt file into a module by givng provide directives for all of the objects you want to make availablel to other modules. For example, (provide environment? empty-env? extended-env? …)You can supply any number of these at the top of the program; I find it convenient to group the functions being exported this way into related clusters.To test your module, open a new Scheme file, have it import env.rkt with (require “env.rkt”)and then run (lookup-env init-env ‘x) This should give the value 10 you bound to x in the initial environment.For this lab you only need to hand in the env.rkt file.
CS275
Lab 06
Interpreters 2— Interpreting basic expressions
This is due at 11:59 pm Tuesday, November 6.
In this assignment you will build an interpreter for serveral, increasingly powerful versions of Scheme.
You might want to download this file at the start: REP.rkt
Section 1: MiniSchemeA
We will start with a very basic language called MiniSchemeA, and gradually add language features. As we do so, we will update our parser and interpreter to implement the new language features.
As a convention, the parser and interpreter for MiniSchemeX will reside in “parseX.rkt” and “interpX.rkt” respectively. Since these build on each other you only need to hand in the last pair of files and your env.rkt for this lab. We will grade the last files that you hand in from the sequence (parseA.rkt, interpA.rkt), (parseB.rkt, interpB.rkt), etc. Here is what you should put in each file:
parseX.rkt Datatypes and parser definitionsinterpX.rkteval-exp definitionenv.rktEnvironment datatypes and lookup function
As you go, think about where to put new definitions. Racket has trouble with circular require (such as parseA.rkt requiring interpA.rkt and interpA.rkt requiring parseA.rkt). You probably want your parse and env files to not require any other module, and your interp files to require both parseX.rkt and env.rkt
Our first MiniScheme, MiniSchemeA, will be specified by the following grammar::
EXP ::= EXPRESSIONEXPRESSION ::= number
parse into lit-exp
Our parse procedure will take an input expression and return a parse tree for an EXP. The grammar rule EXP ::= EXPRESSION probably seems redundan;t, but will allow us to easily expand to include definitions in MiniSchemeB.
The only expressions in MiniSchemeA are numbers. Admittedly, this is not very exciting. Our interpreter for Mini-Scheme-A will be very basic as well.
In parseA we need a datatype to hold EXP nodes that represesent numbers. An easy solution is to make a list out of an atom (such as ‘lit-exp) that identifies the datatype and the numeric value being represented. There are other possible representations and it doesn’t matter which you choose as long as you have a constructor (which I’ll call new-lit-exp), recognizer (lit-exp?) and getter (LitValue). You can use any names you want; the required names are parse(for the parser), eval-exp (for the interpreter) and init-env (for the initial environment).
The parser simply creates a lit-exp when it sees a number (and throws an error otherwise). It looks like this
(define parse
(lambda (input)
(expression input)
(define expression
(lambda (input)
(cond
[(number? input) (new-lit-exp input)]
[else (error 'expression "Invalid syntax ~s" input)))))
Save this code in parseA.rkt
As for the interpreter, you know that Scheme evaluates all integers as themselves. Our evaluation function will be very simple. It looks like this.
(require "env.rkt")
(require "parseA.rkt"
(define eval-exp
(lambda (tree env)
(cond
[(lit-exp? tree) (LitValue tree)]
(else (error 'eval-exp "Invalid tree: ~s" tree)))))
Save this as interpA.rkt
We can interpret expressions in the command interpreter of the interpA.rkt file. Run this file to load the interpreter and parser i;nto memory, then type:
(define T (parse ’23)) (eval-exp T init-ent)
This should print the value 23
It quickly becomes tedious to always invoke your interpreter by specifically calling the interpreter eval-exp after calling the parser on the quoted expression. It would be nice if we could write a read-eval-print loop for MiniScheme. This is very easily accomplished with the code found in file REP.rkt. Save this file to your directory and edit it to requrie env.rkt, parseA.rkt, and interpA.rkt. Build a new fle minischeme.rkt with the following:
#lang racket
(require "REP.rkt")
(read-eval-print)
Running this program will give you an input box that allows you to type expressions and get back their value as determined by your parse and interp modules. . For example, if you entere the minischeme expression 23 this evaluates it and prints its value, 23.
The read-eval-print procedure assumes your parse procedure is named parse and your evaulator is called eval-exp and takes as arguments a parse tree and an environment, in that order.
Remember to update the parse and interp modules (from parseA.rkt to parseB.rkt to parseC.rkt and so on as you progress through the project.. An easier approach might be to use parse.rkt and interp.rkt as the names for the current modules; save these as parseX.rkt and interpX.rkt as you finish one stage of the project and are ready to move onto the next.
Section 2: Variables and Definitions; MiniSchemeB
MiniSchemeA is somewhat lacking in utility. Our specification for MiniSchemeB will be only slightly more interesting. Change the names on your parser and interpreter files to parseB.rktand interpB.rktand include the following changes:
We will start with the following grammar for MiniSchemeB:
EXP ::= EXPRESSION
EXPRESSION ::=number parse into lit-exp
| symbol parse into var-ref
The parser is a simple modification of our parseA.rkt parser. Of course, you need a var-ref datatype including a constructor (I call it new-var-ref), recognizer (var-ref?) and getter (Symbol )
To evaluate a variable expression, MiniSchemeB needs to be able to look up references. We evaluate a var-ref node in an envionment by calling lookup on the Symbol from the node in the environment. Since we asked you to include bindings for symbols x and y in the initial environment, you should be able to evaluate the minischeme expressions x or y to get their values. Any other symbol at this point should give you an error message.
Next we add the ability to make definitions. Here is a grammar that enables this:
DEFINITION ::= (define VAR EXPRESSION)
EXPRESSION ::=number parse into lit-exp
| symbol parse into var-ref```
Note that EXPRESSIONs do not include defintions. This is different from Racket (where a definition can occur as a subexpression of another expression), but it is a little easier to implement. We will set up defintions so they extend the top-level environment, init-env.
Parsing this grammar is easy:
(define parse
(lambda (input)
(cond
[(not (pair? input)) (expression input)]
[(eq? (car input) 'define)(new-define-exp (cadr input) (expression (caddr input)))]
[else (expression input)])))
(define expression ....)
Evaluating a definition is a bit tricky. Racket will not allow an external symbol to be modified by a module. Since we have defined init-env in env.rkt, add the following procedure to init-env:
(define do-define (lambda (sym val)
(set! init-env (new-extended-env (list sym)(list val) init-env))))
The interpreter simply neends to call this with values taken from the define-exp data type:
(define eval-exp
(lambda (exp env)
(cond
[lit-exp? exp) ...]
[(var-ref? exp) ...]
[(define-exp? exp) (let ([sym (define-exp-sym exp)]
[val (eval-exp (define-exp-exp exp) env)])
(do-define sym val))]
...
You should now be able to define variables and evalate variables. If this works you can remove the definitions of x and y from init-env.
Section 3: Calls to primitive functions; MiniScheme
Change the names of the parser and interpreter files to parseC.rkt and interpC.rkt. This is a good point to add primitive arithmetic operators to our environment. Nothing needs to be done for parsing– operators like +, – and so forth are symbols, so they will be parsed to var-ref nodes. Our environment needs to associate these symbols to values. There are many ways to do this; the way we will use will be easy to expand to non-primitive procedures derived from lambda expressions. We will first make a datatype prim-proc to represent primitive procedures. This is simple; the only data this type needs to carry is the symbol for the operator, so this looks just like the var-ref type. Make a getter for the datatype: (prim-proc-symbol p) is the symbol stored in prim-proc p.
Next, we make a lists of the primitive arithmetic operators:
(define primitive-operators ‘(+ – * /)
and add the operators to the environment with
(define init-env (extended-env primitive-operators (map new-prim-proc primitive-operators) (new-empty-env)))
We will now extend the grammar to include applications so we can use our primitive operators:
EXP ::= EXPRESSION | DEFINITION
DEFINITION ::= (define VAR EXPRESSION) parse into define-exp
EXPRESSION ::=number parse into lit-exp
| symbol parse into var-ref
| (EXPRESSION EXPRESSION*) parse into app-exp
We now have a language that can do something. parseC.rkt implements an app-exp datatype that can hold a procedure (which is itself a tree) and a list of argument expressions (again, these are trees). Update the parser to build an app-exp node when the expression being parsed is not an atom. Remember to parse the operator and the list of operands.
To evaluate applications, we need to define a function that applies a primitive operator symbol to a list of arguments and obtains the result:
(define apply-primitive-op (lambda (op arg-values)
(cond
[(eq? op '+) (+ (car arg-values) (cadr arg-values))]
[(eq? op '-) (- (car arg-values) (cadr arg-values))]
etc.
Note that in our implementation, (+ 2 3 4) equals 5, not 9. We may change this later.
Here is the first installment of a general routine that applies functions which we will update as we go along. Eventually, we will update this routine to include user-defined functions. For now, only primitive operations will be implemented.
(define apply-proc (lambda (p arg-values)
(cond
[ (prim-proc? p) (apply-primitive-op (prim-proc-symbol p) arg-values)]
(else (error 'apply-proc "Bad procedure: ~s" p)))))
Finally, extend eval-exp to evaluate an app-exp node by calling apply-proc with the evaluated operator and the list of evaluated arguments. We can now apply our primitive operators, in expressions such as (+ 2 4) or (+ x y). Now we are getting somewhere!
Next extend MiniSchemeC to support three new primitive procedures: add1, sub1, and minus. The first two should be obvious; the minus procedure negates its argument: (minus 6) is -6, and (minus (minus 6)) is 6.
What kind of Scheme doesn’t have list processing functions? Extend MiniSchemeC to implement list, build, first, rest, and empty?. (for list, cons, car, cdr, and null?). The initial environment should also include a new variable, nil bound to the empty list.
Section 4: Conditionals; MiniSchemeD
Let’s update our language to include conditional evaluation. We will adopt the convention that zero and False represent false, and everything else represents true.
Write MiniSchemeD, which implements if-expressions. You will need to add False and True to the initial environment. The meaning of (if foo bar baz) is:
if foo evaluates to False or 0, the value is obtained by evaluating baz otherwise the value is obtained by evaluating bar
The new grammar for our language will be:
EXP ::= EXPRESSION | DEFINITION
DEFINITION ::= (define VAR EXPRESSION) parse into define-exp
EXPRESSION ::=number parse into lit-exp
| symbol parse into var-ref
| (EXPRESSION EXPRESSION*) parse into app-exp
| (if EXPRESSION EXPRESSION EXPRESSION) parse into if-exp
You need to make a new datatype and update the parser in parseD.rkt, and upodate the eval-exp procedure in interpD.rkt. For the parser, note that both if expressions and application expressions are lists. We know a list represents an if-expression if its first element is the atom ‘if. Put the test for this above the more general test (pair? exp) — we will assume a pair represents an application expression if we don’t recognize its first element as a keyword denoting a different kind oif expresson.
Finally, extend MiniSchemeD to implement the primitives equals?, lt?, and gt?.
equals? should behave just like Scheme’s eqv? while lt? and gt? are simply < and >.
Section 5: MiniScheme E; Let expressions
The grammar for MiniSchemeE is:
DEFINITION ::= (define VAR EXPRESSION) parse into define-exp
EXPRESSION ::=number parse into lit-exp
| symbol parse into var-ref
| (EXPRESSION EXPRESSION*) parse into app-exp
| (if EXPRESSION EXPRESSION EXPRESSION) parse into if-exp
| (let (LET-BINDINGS) EXPRESSION) parse into let-exp
LET-BINDINGS ::= LET-BINDING*```
LET-BINDING ::= (symbol EXPRESSION)As you can see, we have added a new clause for the let expression. To make eval-exp clearer, I suggest that you make a let-exp datatype that contains three children:
- A list of the symbols that are bound in the binding list
- A list of the expressions (i.e, trees) that the symbols are bound to
- The let body.
Thus, although we have grammar symbols for LET-BINDING and LET-BINDINGS, we choose to build the tree slightly differently.
After the parser is extended to handle let expressions, we extend eval-exp to handle the let-exp nodes created by the parser. This should be straightforward — we evaluate a let-exp node in an environment by extending the envirionment with the let symbols bound to the VALUES of the let–bindings (map a curried version of eval-exp onto the binding expressions), and then evaluate the let body within this extended environment.
When you are finished you should be able to evaluate expressions such as (let ( (a 1) (b 5) ) ) (+ a b)) and (let ( (a 23) (b 24) ) (let ( (c 2) ) (* c (+ a b))))
When you hand in this lab, you only need to hand in the files for MiniSchemeE. You should include the REP and MiniScheme.rkt file, set up to run the final version of your code.
CS275
Lab 07
Interpreters 3
This is due on Wednesday, November 14
Section 1: Lambdas and Closures– MiniSchemeF
No language would be complete without the ability to create new procedures. Our new language will implement the lambda expression. A lambda expression should evaluate to a package containing the formal parameters, the body, and the environment that was current when the procedure was created (i.e. when the lambda expression was evaluated. This package is known as a closure. So start by making a datatype for closures that holds 3 parts: parameters, body, and environment.
We parse a lambda expression such as (lambda (x y) (+ x y) ) into a lambda-exp tree. This is a new kind of tree node with 2 parts: the parameter list (x y) and the tree that results from parsing the body. The parse function doesn’t track the environment, so it can’t build a full closure. If exp is the tree we get from parsing such a lambda expression, (eval-exp exp env) builds a closure with exp’s parameter list and body combined with the environment env.
We are ready for MiniSchemeF. The syntax is extended once more, this time to include lambda expressions. Here is the grammar for MiniSchemeF.
EXP ::= EXPRESSION | DEFINITION
DEFINITION ::= (define VAR EXPRESSION) parse into define-exp
EXPRESSION ::=number parse into lit-exp
| symbol parse into var-ref
| (EXPRESSION EXPRESSION*) parse into app-exp
| (if EXPRESSION EXPRESSION EXPRESSION) parse into if-exp
| (let (LET-BINDINGS) EXPRESSION) parse into let-exp
| (lambda (PARAMS) EXPRESSION) parse into lambda-exp
LET-BINDINGS ::= LET-BINDING*
LET-BINDING ::= (symbol EXPRESSION)
PARAMS ::= symbol*
So we parse a lambda expresion into a lambda-exp node that stores the parameter list and the parsed body. In eval-exp, we evaluate a lambda-exp node as a closure that has the lambda-exp’s parameter list and parsed body and also the current enviornment.
In Section 3 of Lab 6 (Minischeme C) we defined apply-proc like this:
(define apply-proc (lambda (p arg-values)
(cond
[ (prim-proc? p) (apply-primitive-op p arg-values)]
[ else (error 'apply-proc "Bad procedure: ~s" p)])))
We now extend this with a case for p being a closure. To evaluate the application of a closure to some argument values we start with the environment from the closure, extend that environment with bindings of the parameters to the arg-values, and call eval-exp on the closure’s body with this extended environment. After implementing this you should be able to do the following:
> (read-eval-print)
MS> ((lambda (x) x) 1)
1
MS> ((lambda (x y) (* x y)) 2 4)
8
MS> (let ((sqr (lambda (x) (* x x)))) (sqr 64))
4096
MS> (let ((sqr (lambda (x) (* x x)))) (let ((cube (lambda (x) (* x (sqr x))))) (cube 3)))
27
Section 2: Variables, Assignments and Sequencing — MiniSchemeG
Our next feature will be variable assignment, with set!. Unfortunately, our implementation of environments does not provide a way to change the value bound to a variable. We will modify our old implementation so that variable names are bound to a mutable datatype called a box, which is provided by Dr. Racket.
Take a moment to familiarize yourself with boxes in Scheme:
> (define abox (box 17))
> (box? abox)
#t
> (unbox abox)
17
> (set-box! abox 32)
> (unbox abox)
32
> ...
When variables are created we will bind them to boxes. When they are referenced we will unbox their bindings. We will take these tasks sequentially.
First, eval-exp currently evaluates a varref-exp, it gets the symbol from the expression and looks it up in the environment. When our variables all refer to boxes, eval-exp needs to do an extra step — it gets the symbol from the expression, looks it up in the environment, and unboxes the result.
Secondly, whenever the environment is extended, the new bindings will be boxes that contain values. This occurs in two places. One is when we evaluate a let-expression in eval-exp, the other is when we apply a closure in apply-proc. For the latter our code used to be a recursive call to eval-exp on the body from the closure, using the environment (extended-env params arg-values env). After we introduce boxes we will do this with a recursive call to eval-exp on the body using the environment (extended-env params (map box arg-values) env)
We handle let-expressions in the same way..
At this point your interpreter should be running exactly as it did for MiniSchemeF — let expressions, lambda expressions and applications should all work correctly. Make sure this is the case before you procede. We will now take advantage of our boxed bindings to implement set!
MiniSchemeG will implement variable assignment in the form of set! expressions. Note that we will not be implementing set! as a primitive function, but as an expression — in (set! x 5) we don’t want to evaluate variable x to its previous value, as a call would, but rather to store value 5 in its box. . The grammar for MiniSchemeG will be:
EXP ::= EXPRESSION | DEFINITION
DEFINITION ::= (define VAR EXPRESSION) parse into define-exp
EXPRESSION ::=number parse into lit-exp
| symbol parse into var-ref
| (EXPRESSION EXPRESSION*) parse into app-exp
| (if EXPRESSION EXPRESSION EXPRESSION) parse into if-exp
| (let (LET-BINDINGS) EXPRESSION) parse into let-exp
| (lambda (PARAMS) EXPRESSION) parse into lambda-exp
| (set! symbol EXPRESSION) parse into assign-exp
LET-BINDINGS ::= LET-BINDING*
LET-BINDING ::= (symbol EXPRESSION)
PARAMS ::= symbol*
We need to extend eval-exp to handle assing-exp tree nodes. This is just a matter of putting all of the pieces together: we lookup the symbol from the expression (the variablel being assigned to) in the current environment; this should give us a box. We call set-box! on this box with the value we get from recursively calling eval-exp on the expression part of the assign-exp.
Here is what we can do when this is implemented:
> (read-eval-print)
MS> (set! + -)
#
MS> (+ 2 2)
0
MS> (set! + (lambda (x y) (- x (minus y))))
#
MS> (+ 2 2)
4
MS> (+ 2 5)
7
MS> exit
returning to Scheme proper | (begin EXPRESSION*) parse into begin-exp
Now that we have introduced side effects, it seems a natural next step to implement sequencing. We add a begin expression to the grammar:
EXP ::= EXPRESSION | DEFINITION
DEFINITION ::= (define VAR EXPRESSION) parse into define-exp
EXPRESSION ::=number parse into lit-exp
| symbol parse into var-ref
| (EXPRESSION EXPRESSION*) parse into app-exp
| (if EXPRESSION EXPRESSION EXPRESSION) parse into if-exp
| (let (LET-BINDINGS) EXPRESSION) parse into let-exp
| (lambda (PARAMS) EXPRESSION) parse into lambda-exp
| (set! symbol EXPRESSION) parse into assign-exp
| (begin EXPRESSION*) parse into begin-exp
LET-BINDINGS ::= LET-BINDING*
LET-BINDING ::= (symbol EXPRESSION)
PARAMS ::= symbol*
Evaluating (begin e1 e2 … en) results in the evaluation of e1, e2, .. en in that order. The returned result is the last expression, en.
A begin-exp holds a list of parsed expression. You will need to think about how eval-exp. You need to iterate through the list of expressions in such a way that
(let ([x 1] [y 2]) (begin (set! x 23) (+ x y))) returns 25; the whole point of begin is that the subexpressions might have side effects that alter the environment. Perhaps this will encourage you to be more appreciative of functional programming ….
Section 3: Recursion — MiniSchemeH
It looks like we’re about done; we’ve implemented just about everything except for global definitions (i.e. something like define). But let’s take a closer look.
What happens if we try to define a recursive procedure in MiniSchemeG? Let’s try the ever-familiar factorial function:
(read-eval-print)
MS> (let
([fac
(lambda (n)
(if (equals? n 0)
1
(* n (fac (- n 1)))))])
(fac 4))
MS>
This gets an error message saying there is no binding for fac. But we bound fac using let. Why is MiniScheme reporting that fac is unbound? The problem is in the recursive call to fac in (* n (fac (sub1 n))). When we evaluated the lambda expression to create the closure, we did so in an environment in which fac was not bound. Because procedures use static environments when they are executed, the recursive call failed. The same thing would happen in Scheme itself; this is why we have letrec.
Try this
MS> (let ([fac (lambda (x) (+ x 150))])
(let ([fac
(lambda (n)
(if (equals? n 0)
1
(* n (fac (- n 1)))))])
(fac 4)))
This time the program returns 612, which is 153*4; it is the first binding of function fac that is seen in the call to (fac (- n 1)
Recall what happens when a function is created. A closure is created that contains the environment at the time the function was created, along with the body of the function and the formal parameters. MiniScheme had no problems with this, and shouldn’t have.
When a function is called, the formal parameters are bound to the actual parameters, and then all of the remaining free variables in the body are looked up in the environment that was present at the time of the creation of the function. This is where MiniScheme ran into problems. In the first example the fac in the line
(* n (fac (- n 1))))))
was not bound to anything at the time the function was created, and so we got an error. In the second example fac was bound to the earlier procedure produced by evaluating (lambda (x) (+ x 150)), which fortunately wasn’t recursive. But neither case is what we want.
There is a clever way to get around this problem. Try running the following code:
MS> (let ([fac 0])
(let ([f (lambda (n)
(if (equals? n 0)
1
(* n (fac (- n 1)))))])
(begin
(set! fac f)
(fac 4))))
This works correctly. You can use this pattern for all recursive functions.
So then, it appears that recursive procedures are really “syntactic sugar”. Here is the grammar for our final language, Mini-SchemeH:
EXP ::= EXPRESSION | DEFINITION
DEFINITION ::= (define VAR EXPRESSION) parse into define-exp
EXPRESSION ::=number parse into lit-exp
| symbol parse into var-ref
| (EXPRESSION EXPRESSION*) parse into app-exp
| (if EXPRESSION EXPRESSION EXPRESSION) parse into if-exp
| (let (LET-BINDINGS) EXPRESSION) parse into let-exp
| (lambda (PARAMS) EXPRESSION) parse into lambda-exp
| (set! symbol EXPRESSION) parse into assign-exp
| (begin EXPRESSION*) parse into begin-exp
| (letrec (LET-BINDINGS) EXPRESSION) translate to equivalent let expression and parse that
LET-BINDINGS ::= LET-BINDING*
LET-BINDING ::= (symbol EXPRESSION)
PARAMS ::= symbol*
The way we are handling letrecs is what is known as a syntactic transformation. When the parser sees a letrec expression it can either product an equivalent let expression LE and return (parse LE), or it can directly create the appropriate let-exp tree. The latter is what I do, but either approach works.
Implement MiniSchemeH, which implements letrec. You should only have to modify the parser, which means that InterpH is the same as InterpG. Use a help function (make-letrec ids vals body) to do the work so that you don’t clutter your parser.
You will need some fresh variables to play the role of placeholders. The procedure (gensym) always returns a fresh, unused variable.
> (gensym)
g62
In the end the following examples should work.
(read-eval-print)
MS> (letrec ([fac (lambda (x) (if (equals? x 0) 1 (* x (fac (sub1 x)))))]) (fac 4))
24
MS> (letrec ([fac (lambda (x) (if (equals? x 0) 1 (* x (fac (sub1 x)))))]) (fac 10))
3628800
MS> (letrec
([even? (lambda (n)
(if (equals? 0 n)
True
(odd? (sub1 n))))]
[odd? (lambda (n)
(if (equals? 0 n)
False
(even? (sub1 n))))])
(even? 5))
False
MS> exit
returning to Scheme proper
You are done! Make the final versions of your modules be env.rkt, parse.rkt, and interp.rkt so the grader doesn’t have to look through all of your code to figure out where you stopped. Hand in REP.rkt as well as minischeme.rkt along with your modules.
CS275
Lab 08
Streams
This is due on Tuesday,December 4 (at midnight, as usual)
In this lab we will be working with streams. A stream is a data structure made possible by a new version of cons called cons$, which does not evaluate its second argument. Thus a stream consists of a head element, which can be accessed in the usual way using the car$ function and a tail which is a “promised” stream. The tail is accessed via the cdr$ function which forces evaluation of the original second argument to cons$.
You can think of streams as infinite lists which are manipulated with car$, cdr$, and cons$ in much the same way as finite liss are manipulated with car, cdr, and cons.
Here are the files you need to download for this lab::
Section 1: Streams
A stream is a list-like structure, with some of the values actually present and the rest contained in a promise. This can be used to represent infinite sequences. For example, we might have a stream of positive integers:
(1 2 3 <promise>)
Each time we evaluate the promise we get the next value of the stream, and another promise to produce the rest:
(1 2 3 4 <new promise>)
Streams are built from three primitive operators:
- (cons$ x y) This is the same as (cons x (delay y)). Of course, like delay it can’t be written as a lambda expression.
- (car$ s) This is the same as (if (promise? s) (car$ (force s)) (car s)))
- (cdr$ s) This is the same as (if (promise? s) (cdr$ (force s)) (cdr s)))
These three are contained in file “streams.rkt” which we will use for all of our work with streams. You want to download the file streams.rkt and put the line
(require “streams.rkt”)
at the top of any Dr. Racket file using streams.
In addition to car$, cdr$ and cons$, stream.ss defines a number of helper procedures for working with streams:
- (nth$ n s) returns the nth cdr of stream s
- (show$ n s) returns a list (a real list) of the first n elements of stream s, followed by a promise for the rest of s.
- (printn$ s n) prints the first n elements of s
- (print$ s) prints the first 10 elements of s, asks if you want more, and responds.
- (+$ s1 s1) returns a new stream that adds the corresponding entries of s1 and s2 together.
- (filter$ p s) takes a predicate and a stream and returns a new stream consisting of the elements of s that satisfy the predicate.
- (map$ f s) maps procedure f (a function of 1 variable) to stream s
- (append$ s1 s2) appends stream s2 after s1; this doesn’t have much effect unless s1 is finite.
- (fold rec-case base-case base-test s) does fold with stream s.
Here are a few examples:
- (define IntsFrom$ (lambda (n) (cons$ n (IntsFrom$ 0)))
- (define Ints$ (IntsFrom$ 0))
- (define Evens$ (map$ (lambda (x) (* 2 x)) Ints$)
- (define Ones$ (cons$ 1 (Ones$)))
- (define Odds$ (+$ Evens Ones$))
Here is another, more subtle definition of the integers starting from 1:
- (define Ints1$ (cons$ 1 (+$ Ones$ Ints1$)))
The first elements of Ints1$ is certainly 1, since we cons$ 1 onto the front of the stream. The next element is the result of adding the first element of Ones$ (i.e, 1) onto the first element of Ints1$, which we just saw is also 1; so the second element is 2. The next elment is the result of adding 1 onto this second element to get 3, and so forth.
Exercise 1
Write the functions(rember-all$ x s); returns a stream with all occurrences of x removed from the stream s(subst-all$ x y s); returns a stream with all occurrences of x in the stream s replaced withYou can test these out on the stream (define Tester$ (cons$ 1 (cons$ 2 (cons$ 3 Tester$))))
Section 2: Streams of Numbers
Remember our stream construction of the integers:
- (define IntsFrom$ (lambda (n) (cons$ n (IntsFrom$ (+ n 1)))))
- (define Ints$ (IntsFrom$ 0))
A good way to produce streams of numbers is to write a function which produces the next number in the stream given the current number. That is the technique used just now in IntsFrom$: A call to (IntsFrom$ n) does a cons$ of n onto a recursive call to IntsFrom$ passing it the next number (+ n 1).
Here is a challenge. Consider the following grid of pairs of numbers:
1.1 1.2 1.3 1.4 1.5 1.6 1.7 … 2.1 2.2 2.3 2.4 2.5 2.6 2.7 … 3.1 3.2 3.3 3.4 3.5 3.6 3.7 … 4.1 4.2 4.3 4.4 4.5 4.6 4.7 … 5.1 5.2 5.3 5.4 5.5 5.6 5.7 … 6.1 6.2 6.3 6.4 6.5 6.6 6.7 … 7.1 7.2 7.3 7.4 7.5 7.6 7.7 … . . . . . . .
Note that we can display a.b with (cons a b). Of course, it is easy to make the first row of this grid as a stream, but if we try to print the grid row-by-row we will never finish with the fist row. A better approach is to enumerate the elements diagonally. The first diagonal (right-to-left) contains only 1.1 The next diagonal containts 1.2 and 2.1 The enxt 1.3 2.2 and 3.1 And so forth.
We can define this stream of pairs pretty easily, the same way we define our stream of integers:
(define pairsFrom$
(lambda (p)
(cons$ p (pairsFrom$ (nextPair p)))))(define pairs$ (pairsFrom$ (cons 1 1)))
Of course there is a missing piece here:
Exercise 2
Write procedure (nextPair p) that takes one of the pairs for this enumeration and returns the next pair. This is not itself a stream function; it is just what we use to make our stream of pairs.
Exercise 3
A famous problem, first raised by R. Hamming, is to enumerate, in ascending order with no repetitions, all positive integers with no prime factors other than 2, 3, or 5. One obvious way to do this is to simply test each integer in turn to see whether it has any factors other than 2, 3, and 5. But this is very inefficient, since, as the integers get larger, fewer and fewer of them fit the requirement. As an alternative, let us call the required stream of numbers S and notice the following facts about it.S begins with 1.The elements of (scale S 2) are also elements of S.The same is true for (scale S 3) and (scale 5 S).These are all the elements of S.Now all we have to do is combine elements from these sources.Write (merge$ s1 s2), which combines two ordered streams s1 and s2 into one ordered result stream, eliminating repetitions.Construct the desired stream S.You should be able to do the following with S:> (print$ S) 1 2 3 4 5 6 8 9 10 12 Want more? y 15 16 18 20 24 25 27 30 32 36 Want more? y 40 45 48 50 54 60 64 72 75 80 Want more? y 81 90 96 100 108 120 125 128 135 144 Want more? n done >
Section 4: Power Series
Streams can be used to model the power series that define important mathematical functions. Among these are the following that compute the exponential, sine and cosine functions:
Suppose we generate the following streams of coefficients:
e-series$ = (1/0! 1/1! 1/2! … 1/n! … ) sin-series$ = (0 1/1! 0 -1/3! 0 1/5! … ) cos-series$ = (1 0 -1/2! 0 1/4! 0 -1/6! …)
(Powers$ x) = (1 x x^2 x^3 x^4 ….)
Mathematicians use the term “Partial Sums” for the sequence of sums of the first n terms of a sequence. For the sequence a b c d e … the partial sums are a a+b a+b+c a+b+c+d ….. We can write a procedure to make the stream of Partiall Sums of the stream s:
(define PartialSums$ (lambda (s) (cons$ (car$ s) (+$ (PartialSums$ s) (cdr$ s)))))
Then(PartialSums$ (*$ (Powers$ x) sin-series$)) gives increasingly good approximations to sin(x), and the other series act similarly.
To define these streams we start by building the stream of factorials. First we need *$, defined analogously to +$: it takes 2 numerical streams and multiplies them element by element
(define *$ (lambda (s1 s2) (cons$ (* (car$ s1) (car$ s2)) (*$ (cdr$ s1) (cdr$ s2)))))
Now notice that
fact-stream$ = 1 1 (2 * 1) (3 * 2 * 1) … *$ (IntsFrom$ 1) = 1 2 3 4 … ————————————————- 1 (2 * 1) (3 * 2 * 1) (4 * 3 * 2 * 1) …
The last line is just (cdr$ fact-stream$). Consequently we can define fact-stream$ as follows.
(define fact-stream$
(cons$ 1 (*$ fact-stream$ (IntsFrom$ 1))))
Now we can build our power series.
The e-series$ can be built as follows::
(define e-series$ (cons$ 1 (map$ (lambda (x) (/ 1.0 x)) fact-stream$)))
For example, the first few terms of the e-series$ are
1 1 1/2 1/6 1/24 1/120 1/720 1/5040 1/40320 1/362880
If we define (define E (lambda (x) (PartialSums$ (*$ (Powers$ x) e-series$)))) we can get approximations to the values of the exponential function. For example,
(E 1) gives values 1 2.0 2.5 2.66 2.708 2.7166 2.7180 2.71825 … Thanks to being bored once in high school I know that the correct value to 14 decimal places is 2.71828182845904…
Exercises 4 and 5:
Produce the power series forsin-series$ = (0 1/1! 0 -1/3! 0 1/5! … ) cos-series$ = (1 0 -1/2! 0 1/4! 0 -1/6! …) and define the sin and cosine functions as(define sin (lambda (x) (PartialSums$ (*$ (Powers$ x) sin-series$))))
(define cos (lambda (x) (PartialSums$ (*$ (Powers$ x) cos-series$))))If you print$ these streams you should get increasingly accurate approximations to sin(x) and cos(x).
Section 5: Communication Streams
File keyboard.rkt has code that makes a keyboard-stream. This is a stream of whatever s-expressions you type. There is also an output$ function that takes a stream and outputs it one element at a time. Together these set up a communication channel:
(output$ (keyboard-stream))
echoes whatever you type, and continues until you click on the “eof” box at the right. We will use this in the next set of exercises:
Grune’s Problem
There is a famous problem due to Grune that is important in data communications. Consider a stream of characters, which we will model by typing single characters followed by a carriage-return in response tokeyboard-stream’s prompts. Most characters we will allow to pass through unaltered. But if we ever receive two a’s in a row, then we will pass through just a single b and no a.
Exercise 6
Write the filter grune-a-b to work as follows:> (output$ (grune-a-b (keyboard-stream)))
? a
? b
a b
? c
c ? d d ? a ? a b ? a ? b a b ? a ? a b ? <clicks eof> done >
Exercise 7
Now write a similar function, but abstract the a and b. Write a function grune which takes two arguments and produces a filter similar to grune-a-b but with the first argument taking the role of a and the second taking the role of b. Your code should start:(define grune (lambda (a b) where now a and b are variables. (grune ‘x ‘y) needs to return a function, similar to grune-a-b which works as a stream filter replacing two successive x by a single y. Here is a transcript of grune in action:> (output$ ((grune ‘x ‘y) (keyboard-stream))) ? a a ? b b ? c c ? d d ? x ? y x y ? a a ? b b ? x ? x y ? x ? x y ? a a ? b b ? <clicks eof> done > Notice that (grune ‘a ‘b) has the same functionality as grune-a-b.
Grune’s problem becomes interesting when we consider pipelining several Grune operations. If you did the last exercise correctly, you should be able to chain several “grune”s together:> (output$ ((grune ‘c ‘d) ((grune ‘b ‘c) ((grune ‘a ‘b) (keyboard-stream))))) ? a ? b a ? c b ? d c d ? e e ? f f ? g g ? a ? a ? a ? a ? a ? a ? a ? a d ? a ? a ? a ? a ? x c x ? y y ? z z ? x x ? y y ? z z ? <clicks eof> done >
CS275
Lab 10
Continuations
This is due on Wednesday, December 12
Exercise 0. To make grading easier, put the following definition of the top-level continuation into your solution file: (define top (lambda (x) x))
Exercise 1. Give a tail-recursive continuation-passing-style function (rember-k a lat k) that removes the first occurrence (only the first) of atom a from lat and return the result. So (rember-k ‘b ‘(a b a b a b b) top) returns ‘(a a b a b b)
Exercise 2. Give a tail-recursive continuation-passing style function (index-k a lat k)returns the 0-based index of the first occurrence of atom a in lat. So
(index-k ‘b ‘(a b a b b)top) returns 1.
Exercise 3. Give a tail-recursive continuation-passing-style function (max-k L k) that returns the largest element of the not-necessarily-flat list L of numbers. For example,
(max-k ‘(5 3 (4 7 2 (5) 1)) top) returns 7
Exercise 4. Give a tail-recursive continuation-passing style function (replace-k old new L k) that replaces each instance of atom old with atom new in the general list L. For example, (replace-k ‘a ‘x ‘(a b c (b c (a))) top) produces (x b c (b c (x)))
Exercise 5: Here is a deep-recursive procedure. Given two lists, pairall returns a list of all possible pairs where the first element comes from the first list and the second element comes from the second: The call(pairall ‘(1 2 3) ‘(a b c)) produces ((1 a) (1 b) (1 c) (2 a) (2 b) (2 c) (3 a) (3 b) (3 c))
(define pairone (lambda (a l) (if (null? l) null (cons (list a (car l)) (pairone a (cdr l)))))) (define pairall (lambda (l1 l2) (if (null? l1) null (append (pairone (car l1) l2) (pairall (cdr l1) l2)))))
Write CPS versions of these two functions: pairone-k and pairall-k.
