CS 5010: Problem Set 02

Out: Monday, 18 September 2017
Due: Monday, 25 September 2017 at 6pm local time

This is an individual assignment. You are not allowed to discuss this problem set with any other person. You are also not allowed to search for or to view any solutions to similar problems that may be available on the World-Wide Web or in other resources that might otherwise have been available to you.

The main purpose of this problem set is to give you practice with data design.

You must use Racket's HtDP Intermediate Student Language (ISL) for this problem set.

For these problems, download a copy of extras.rkt and put it in the folder with your solutions. Then import this library by including the line

      (require "extras.rkt")

at the top of your file with the other require declarations. Then, for each problem, put in lines that say

      (provide function)

for each deliverable function. Thus, for problem 1, the top of your q1.rkt file should say

      (require rackunit)
      (require "extras.rkt")
      
      (provide
        make-lexer
        lexer-token
        lexer-input
        initial-lexer
        lexer-stuck?
        lexer-shift
        lexer-reset)

This will allow our testing framework to import your file and do automated testing on it.

Remember that you must follow the design recipe, which is a process, not a list of deliverables. Your deliverables include the artifacts produced by the various steps of the design recipe: data definitions (including interpretation and templates, contracts, purpose statements, definitions, and tests). Be sure to follow our coding conventions. Doing so will make codewalks easier for everyone.

Be sure to fill out a work session report at the end of each work session. Tell git to add it to the files you will commit, and then commit and push (sync) that report in addition to committing and pushing your entire set02 directory. Do this at the end of every work session.

Remember to include a copy of extras.rkt racket in your set02 directory.


  1. (Lexer)

    Application programs often have to divide textual inputs into tokens such as identifiers, numbers, and punctuation. That task is known as lexical analysis. This problem asks you to write part of a simple lexical analyzer.

    You are to write a file called q1.rkt that defines a Lexer data type and provides all seven of the following functions:

              ;;; make-lexer : String String -> Lexer
              ;;; GIVEN: two strings s1 and s2
              ;;; RETURNS: a Lexer whose token string is s1
              ;;;     and whose input string is s2
              ;;;
              ;;; lexer-token : Lexer -> String
              ;;; GIVEN: a Lexer
              ;;; RETURNS: its token string
              ;;; EXAMPLE:
              ;;;     (lexer-token (make-lexer "abc" "1234")) =>  "abc"
              ;;;
              ;;; lexer-input : Lexer -> String
              ;;; GIVEN: a Lexer
              ;;; RETURNS: its input string
              ;;; EXAMPLE:
              ;;;     (lexer-input (make-lexer "abc" "1234")) =>  "1234"
              ;;;
              ;;; initial-lexer : String -> Lexer
              ;;; GIVEN: an arbitrary string
              ;;; RETURNS: a Lexer lex whose token string is empty
              ;;;     and whose input string is the given string
              ;;;
              ;;; lexer-stuck? : Lexer -> Boolean
              ;;; GIVEN: a Lexer
              ;;; RETURNS: false if and only if the given Lexer's input string
              ;;;     is non-empty and begins with an English letter or digit;
              ;;;     otherwise returns true.
              ;;; EXAMPLES:
              ;;;     (lexer-stuck? (make-lexer "abc" "1234"))  =>  false
              ;;;     (lexer-stuck? (make-lexer "abc" "+1234"))  =>  true
              ;;;     (lexer-stuck? (make-lexer "abc" ""))  =>  true
              ;;;
              ;;; lexer-shift : Lexer -> Lexer
              ;;; GIVEN: a Lexer
              ;;; RETURNS:
              ;;;   If the given Lexer is stuck, returns the given Lexer.
              ;;;   If the given Lexer is not stuck, then the token string
              ;;;       of the result consists of the characters of the given
              ;;;       Lexer's token string followed by the first character
              ;;;       of that Lexer's input string, and the input string
              ;;;       of the result consists of all but the first character
              ;;;       of the given Lexer's input string.
              ;;; EXAMPLES:
              ;;;     (lexer-shift (make-lexer "abc" ""))
              ;;;         =>  (make-lexer "abc" "")
              ;;;     (lexer-shift (make-lexer "abc" "+1234"))
              ;;;         =>  (make-lexer "abc" "+1234")
              ;;;     (lexer-shift (make-lexer "abc" "1234"))
              ;;;         =>  (make-lexer "abc1" "234")
              ;;;
              ;;; lexer-reset : Lexer -> Lexer
              ;;; GIVEN: a Lexer
              ;;; RETURNS: a Lexer whose token string is empty and whose
              ;;;     input string is empty if the given Lexer's input string
              ;;;     is empty and otherwise consists of all but the first
              ;;;     character of the given Lexer's input string.
              ;;; EXAMPLES:
              ;;;     (lexer-reset (make-lexer "abc" ""))
              ;;;         =>  (make-lexer "" "")
              ;;;     (lexer-reset (make-lexer "abc" "+1234"))
              ;;;         =>  (make-lexer "" "1234")
    

    Remember that we will be doing automated testing of your solution, so be sure your solution is in the right place (set02/q1.rkt in your private cs5010f17/pdp-YOURUSERNAME repository), and that it provides all the functions listed above. To see if your file is in the right place, insert the following line somewhere near the top of your file, but after the require declarations:

              (check-location "02" "q1.rkt")
    
  2. (ChineseTrafficSignal)

    In China, some traffic signals behave differently from those in the US. In this question you will model a traffic signal that is inspired by some of the traffic signals in China. The traffic signal you will model starts out red and remains red for some period of time, such as 30 seconds. The signal then becomes green for three seconds less than the period of time it had been red. The signal then goes blank for one second, then green for another second, and then blank again for one second before returning to its red state and repeating the cycle.

    Note that the signal is red for the same period of time that the signal is green or blank.

    You are to write a file called q2.rkt that defines a ChineseTrafficSignal data type and provides all four of the following functions:

              ;;; initial-state : PosInt -> ChineseTrafficSignal
              ;;; GIVEN: an integer n greater than 3
              ;;; RETURNS: a representation of a Chinese traffic signal
              ;;;     at the beginning of its red state, which will last
              ;;;     for n seconds
              ;;; EXAMPLE:
              ;;;     (is-red? (initial-state 4))  =>  true
              ;;;
              ;;; next-state : ChineseTrafficSignal -> ChineseTrafficSignal
              ;;; GIVEN: a representation of a traffic signal in some state
              ;;; RETURNS: the state that traffic signal should have one
              ;;;     second later
              ;;;
              ;;; is-red? : ChineseTrafficSignal -> Boolean
              ;;; GIVEN: a representation of a traffic signal in some state
              ;;; RETURNS: true if and only if the signal is red
              ;;; EXAMPLES:
              ;;;     (is-red? (next-state (initial-state 4)))  =>  true
              ;;;     (is-red?
              ;;;      (next-state
              ;;;       (next-state
              ;;;        (next-state (initial-state 4)))))  =>  true
              ;;;     (is-red?
              ;;;      (next-state
              ;;;       (next-state
              ;;;        (next-state
              ;;;         (next-state (initial-state 4))))))  =>  false
              ;;;     (is-red?
              ;;;      (next-state
              ;;;       (next-state
              ;;;        (next-state
              ;;;         (next-state
              ;;;          (next-state (initial-state 4)))))))  =>  false
              ;;;
              ;;; is-green? : ChineseTrafficSignal -> Boolean
              ;;; GIVEN: a representation of a traffic signal in some state
              ;;; RETURNS: true if and only if the signal is green
              ;;; EXAMPLES:
              ;;;     (is-green?
              ;;;      (next-state
              ;;;       (next-state
              ;;;        (next-state
              ;;;         (next-state (initial-state 4))))))  =>  true
              ;;;     (is-green?
              ;;;      (next-state
              ;;;       (next-state
              ;;;        (next-state
              ;;;         (next-state
              ;;;          (next-state (initial-state 4)))))))  =>  false
    

    Remember that we will be doing automated testing of your solution, so be sure your solution is in the right place (set02/q2.rkt in your private cs5010f17/pdp-YOURUSERNAME repository), and that it provides all the functions listed above. To see if your file is in the right place, insert the following line somewhere near the top of your file, but after the require declarations:

              (check-location "02" "q2.rkt")
    

Last modified: Tue Sep 19 13:02:48 Eastern Daylight Time 2017