In this module we introduce the notions of abstraction and accumulators. First we show how recursive functions can be rewritten to maintain information during each recursive call using accumulators. Second we upgrade to the Intermediate Student Language which allows functions as values. We then show how functions can consume/produce other functions allowing for more abstract, and more elegant, designs.

  1. Given a function that uses mutual recursion, convert it to use accumulators.
  2. Document accumulator arguments by writing an invariant.
  3. Write a function definition that is local in scope to another function.
  4. Given a set of Scheme functions that contain duplicative code, write the abstracted function.
  5. Given a data definition for tree structured data, write a template.
  6. Given a specification for information represented as a tree, write a data definition that maps the information into Scheme data.
  7. Recognize patterns for built-in abstract functions.
  8. Write the contracts for the built-in abstract functions.
  9. Given abstract functions, use Higher Order Function Composition to define a new function.
  10. Given a function that uses structural decomposition, convert it into a function that uses Higher Order Function Composition.
  11. Given a signature that takes other functions as arguments, write down valid inputs for the signature.
  12. Given a recursive data definition, write a fold function.
  13. Recognize patterns for built-in abstract functions.
  14. Write the contracts for the built-in abstract functions.
  15. Given abstract functions, use Higher Order Function Composition to define a new function.
  16. Given a signature that takes other functions as arguments, write down valid inputs for the signature.
  17. Given a function that uses structural decomposition, convert it into a function that uses Higher Order Function Composition.
  18. Given a recursive data definition, write a fold function.
  19. Write an anonymous function using the keyword lambda.
  20. Write a call to an anonymous function with the appropriate number of inputs.
  21. Given a Scheme expression, write down the sequence of steps taken during evaluation.
  22. Use the syntactical conventions for function definitions.
  23. Given a Scheme function, identify the strategy used.
  • DUE DATE: Wednesday November 16th at 11:59pm

S-Expressions

You are given the following data definition


;; An S-Expression (SExp) is one of 
;; - Atom 
;; - LoF<SExp>
;; INTERP: represents an s-expression

;; An Atom is one of 
;; - Number
;; - String 
;; - Symbol 
;; - Boolean 
;; INTERP: represents atomic values
  1. Provide the deconstructor template for SExp
  2. Design a function that given an SExp returns the total number of Atoms in the SExp.
  3. Design a function that given an SExp returns a list of all Symbols in the SExp.
  4. Design a function that given an SExp returns the sum of all Numbers in the SExp.
  5. Design a function that given an SExp and two strings s1 and s2 returns a new SExp where all instance of s1 have been replaced with s2.

Higher Order Functions

DrRacket has lots of abstract functions for processing lists (pg. 313, Sect. 21.2, or the online version).

Given the following data definitions: 


(define-struct grade (letter num))
;; A Grade is: (make-grade LetterGrade Number)
;; INTERP: represents a homework grade as 
;;         a letter grade and number grade

;; A LetterGrade is one of:
;; - 'A  >= 90
;; - 'B  >= 80
;; - 'C  >= 70
;; - 'D  >= 60 
;; - 'F  < 60

;; A LoF<Grades>
(define grades (list (make-grade 'D 62) (make-grade 'C 79) 
                     (make-grade 'A 93) (make-grade 'B 84) 
                     (make-grade 'F 57) (make-grade 'F 38) 
                     (make-grade 'A 90) (make-grade 'A 95)
                     (make-grade 'C 76) (make-grade 'A 90) 
                     (make-grade 'F 55) (make-grade 'C 74)
                     (make-grade 'A 92) (make-grade 'B 86) 
                     (make-grade 'F 43) (make-grade 'C 73)))

Design the requested functions to manipulate Grades. You must use the given list as one of your tests. For each you may use a local expressions.

Note: if you do not use the DrRacket higher order functions from Section 21.2 in the book, you will not receive credit for the sub-problem!

  1. Design the function log->lon that converts a LoF<Grade> into a LoF<Number> that contains just the numerical grade, using the Scheme function map.
  2. Using foldr, design the function best-grade that finds the highest Grade in a LoF<Grade>.
  3. Design a function just-As that returns a list of only the 'A grades, using filter.
  4. Use andmap to design the function all-pass? that checks to see if all the Grades in a given list are not 'F.
  5. Finally design the function bonus that adds 5 to all of the Grades in a given list, and updates the letter portion of the Grade if it changes. Use map to design your function... it must return a LoF<Grade>!

Trees

A friend of your found this online quiz that they are trying to solve and they are stuck. Help them out by solving these questions.

Provide your solutions without using any abstract functions.

  1. Provide a data definition for a Binary Search Tree that contains non-negative Integers (BSTI) and answer the following questions
    1. Design a function that given a BSTI returns the sum of all the integers found inside the BSTI.
    2. Design a function that given a BSTI returns the product of all the integers found inside the BSTI.
    3. Design a funciton that given a BSTI and a non negative integer dx multiplies each integer in the BSTI by dx.
  2. Provide a data definition for a Binary Search Tree that contains Strings (BSTS). Your BSTS should use alphabetical ordering to decide which string should be stored to the left or right subtree. Answer the following questions for a BSTS
    1. Design a function that given a BSTS appends all the strings in the BSTS using an in-order traversal.
    2. Design a function that given a BSTS and a String ds appends ds to each string in the BSTS.
  3. Provide a data defintion for a tuple. A tuple always contains 2 values, the first value is a string and the second value is a non-negative integer. Provide a data definition of a Binary Search Tree that can contain Tuples (BSTT). Your BSTT should use the alphabetical ordering on the String inside the Tuple's in order to decide which tuple should be stored to the left or right subtree of a node. Answer the following questions on BSTT
    1. Design a function that given a BSTT returns the sum of all Integer values in the Tuples found in the BSTT.
    2. Design a function that given a BSTT appends all the String values in the Tuples found int he BSTT using an in-order traversal.
    3. Design a function that given a BSTT returns a BSTS that holds only the String values found in each Tuple in the BSTT.

Now that you have a solution for the 3 different Binary Search Trees we would like to generalize (or abstract) over the data definition and your solution(s).

  1. Provide a generic data definition for a BST (GBST) that can take any kind of data as an element.
  2. The solutions to 1.c., 2.b., and 3.c. are similar. Use your existing solutions to design a generic function on GBST. Use your generic function to provide a second solution to 1.c., 2.b., 3.c.
  3. The solutions to 1.a., 1.b., 2.a., 3.a. and 3.b are similar. Use your existing solutions to design a generic function on GBST. Use your generic function to provide a second solution to 1.a., 1.b., 2.a., 3.a. and 3.b.
  • DUE DATE: Wednesday November 23th at 11:59pm

Refactor Space Invaders

  1. Use your solution from Assignment 6.
  2. Update your Assignment 6 to address all comments made by your Grader. All comments means
    1. comments made that did not cost you points
    2. comments made that cost you points
  3. Review your solution to Assignment 6 and refactor your code such that
    • your code uses generic data definitions
    • your code uses the predefined Higher Order Functions provided by DrRacket (e.g., map, foldl, filter, etc. when appropriate. You are also encouraged to develop your own generic functions if that is applicable (i.e., none of the predefined higher order functions can be used)
    • your code uses local appropriately for helper functions and/or common sub-expressions

Extend Space Invaders

Your space invaders game is popular and you started receiving requests for extensions. Extend your refactored solution to space invaders to accommodate the following extensions.

  1. We would like to have a maximum of 3 lives for our spaceship. The game should therefore implement the following behaviour
    1. When we start a new game the player has 3 lives. When the spaceship gets hit by an invader bullet, instead the player loses one of his lives. The game ends when the user has 0 lives left.
    2. The game should display in the bottom right hand corner of its scene the number of remaining lives. When we start a game that number should be the number 3. Upon losing a life the number should be updated accordingly, e.g., from 3 to 2, from 2 to 1 and from 1 to 0. At 0 lives the game is over.
    3. When an invader bullet hits the spaceship, the spaceship should re-appear in the bottom, center of the screen and moving to the left.
  2. We would like to keep score while a user is playing the game. The game should therefore implement the following behaviour
    1. The total score should be displayed centered at the top of the window.
    2. When we start a new game the total score begins with the value of 0. Then during the game for every invader that we hit the score increases by 5. The value displayed on your scene must be updated to reflect the current score.
  3. We would like to make the game a little more challenging. We would like the invaders to steadily move from the top of the screen to the bottom of the screen. The game should therefore implement the following behaviour
    1. All visible invaders should move down every 10 ticks. Every 10 ticks the invaders should be moved the same amount of units as their height. For example if your invaders have a height of 15 then after 10 ticks all invaders should be moved 15 positions down.
    2. We need to add a new condition for when the game is over. If any visible invader(s) reach the bottom of the field then the game is over. The bottom of the field is defined to be the top line of your spaceship. For example, if your space ship has a height of 30 units and its center is located at coordinate (10,10), then the bottom of the field is the line y = 25.
  4. We would also like to make the game a little more rewarding. We would like to add the ability for the user to be able to boost their scores and gain lives. The game should therefore implement the following behaviour
    1. We would like to create some room at the top of the scene before the first row of invaders. This new space should be wide enough to display 1 new invader invader that we will call mother ship.
    2. The mother ship appears after 30 ticks. The mother ship has the same dimensions as a normal invader but has a different colour than the invaders (and the spaceship).
    3. The mother shop moves from left to right only and at a constant speed. You are free to select the constant speed that you feel is appropriate.
    4. If the mother ship is hit by a spaceship bullet then the player gains 20 points and gains 1 life. The game has to add 20 points to the players current score, and, add 1 life to the current total number of lives available to the player.