27 Pages

Computer Science
Course Code
CS 136
Brad Lushman

This preview shows pages 1,2,3,4. Sign up to view the full 27 pages of the document.
CS 136 Midterm Exam-Aid Winter 2012 Waterloo SOS Tutor | Matthew Cheung Package | Kevin Chen 1 Note This package isdesigned to help study the most essential material from Lectures 1 to 9¾. The package does not cover all material, but gives a concise overview of the material for the midterm up to and not includinglecture 10. 2 Lecture 1 Module: a way of packaging code #lang racket makes the full Racket language available inside the module Remember in the full Racket language:  check-expect / stepper no longer exist  “true” and “false” represented by “#t” and “#f”, the actual Boolean values  No restriction on the argument of cons; e.g.(cons 3 4) -> ‘(3 . 4) in interaction window (dotted notation) Modularity  Allows you to share code and make implementation and interaction independentof each other  Improvements on the module’s implementation can be done without changes to the client 3 Lecture 2 Module + Client A file “myfunc.rkt” (module) with code can be accessed from another .rkt file (client) (require …) accesses and evaluates the code in the file  May trigger side effects (printing results)  Only definitions of functions listed in(provide …) in the module will be accessible in the client file myfunc.rkt #lang racket #lang racket (provide func1 func2) (require “myfunc.rkt”) (define func1 …) (func1 …) (func2 …) (define func2 …) begin special form (begin …)  Each is evaluated, in order from left to right, top to bottom. Result of (begin …) is the LAST EXPRESSION (begin (+ 1 3) (+ 3 4) (add1 2)) Interaction 3 >  Begin can allow evaluation of more than one(display …) function 4 Example: (begin (display “Hi! I am taking CS “) (display 136) (display “.\n”)) (display …) prints out values, but the functionoutputs Implicit begin begin is assumed (no need to explicitly writebegin) in the following forms:  Body of function definition(define …)  Body of lambda (lambda …)  Body of local (implicit local also exists)  Answer of cond (cond [(#t) …]) Implicit local  Definitions are allowed at the beginning of a function definition or at the beginning of lambda  No “local” is needed to define functions within a function (define func1 (define func_mini …) ) (define (area-of-square s) (define (area s) (* s s)) (area s)) Formatted printf  (printf …)  Produces Values replaces in order any instances of “~a” in the string. Values can have any type Side effects  Anything produced by a function that is not the RESULT of the function Example from the slides: #lang racket (define (take-headache-pill) 5 (printf "Nausea\n") "Headache gone!") Interaction window: > (define health-state (take-headache-pill)) Nausea -> SIDE EFFECT (because of implicit begin) > (printf health-state) Headache gone! -> RESULT > health-state "Headache gone!" -> RESULT  Result of evaluating (take-headache-pill) is "Headache gone!"  Side-effect of evaluating (take-headache-pill) is printing ofthe word “Nausea”. Keyboard Input  (read) waits for keyboard input, terminated byENTER  Using (define x (read)) gives x the value of the keyboard input Random  Function (random …) consumes and integer >= 1 and produces a random number from 1 to n-1, inclusive For-each  Function (for-each f lst) applies function f to each element inlist lst, but only causes the side effects of functionf. Mutation  (set! …) can change definitions Definition: (define x 4) (set! x 5) Interaction >x 5 6  allows memory management in a Racket module  Encapsulation with modules (implementation on one module, interaction in another) can prevent “queue jumping”, since variables cannot be provided into a client module. Another method is encapsulation with local  variables inside a function are only visible inside the function  return a function as a value Example from the slides: #lang racket (provide make-counter) (define (make-counter) (define count 0) (define (increment-counter) ;; new function! (set! count (add1 count)) count) ;; Modifies and returns the local variable increment-counter);; return the *FUNCTION*  (make-counter) produces the function incremental counter, thus is a way toaccess the “count” variable  An evaluation of (make-counter) creates a new counter (generator) Ex. (from slides) (define next (make-counter)) (define next-serve (make-counter)  To execute, we will use next and next-serve as functions to access the increment- counter function. > (next) (next) (next-serve) (next) (next-serve) ... If we don’t execute them as functions: > next-serve # > (set! count 100) .set!: cannot set variable before its definition: count Modularization: hiding code Encapsulation: hiding data 7 Lecture 3 Separation of Concerns  We need to separate code whichimplements the functionality from the code which uses the functionality (user interface)  We run or test code through a client module. Example from slides:  Here is the interface for game.rkt, the implementation code supplied by Marmoset. ;; Implementation of simple guessing game ;; Provides: startgame, guess ;; (startgame n) starts a new game in which the ;; game [this module] chooses a secret integer ;; between 1 and n, and you [the client module] ;; try to guess it [[STARTGAME PRODUCES (void)]] ;; (guess x) consumes an integer x and produces ;; either 'right or 'wrong, depending on whether ;; or not x is the secret integer  We needed to supply the user interface code playgame.rkt. The interface is as follows: ;; Player for simple guessing game ;; Provides: playgame ;; (playgame n) uses "game.rkt" to start and play an ;; entire game of size n, and produces m, ;; the total number of guesses actually ;; used by playgame to complete the game KEY: the user interface and the behavior of the user should be unchanged even though the implementation method changes 8 Lecture 4 Abstract Data Types  mathematical specification of a collection of data  defined through the operations on how to manipulate the data  can separate implementation from specification (separation of concerns)  one specification can have several implementations!  Implementation of ADT’s are NOT SPECIFIED  Description exists for the KIND of data(string, numbers, characters, etc.), not a specific instance (3, “hello world”, etc.) Specification  Description of parameters  Precondition (what needs to exist in the world before execution of operation)  Post-condition (what happens in the world if theoperation is applied) Forging ADTs  ADT’s can be forged and cause unexpected results (e.g. making queues as a list in Scheme)  Use data hiding through define-struct to only provide necessary functions so that client module cannot forge ADTs Mutable ADTs  Useful to modify the ADT passed onto the ADT operation Example from slides: enqueue  Two parameters, an item e and a queue Q = (q1, q2, ..., qn )  Precondition: True  Postcondition: Produces Q 0 = (e, q1, q2, ..., qn)  This operation creates a new queue, but we want to just mutate the queue itself (aka modify the state associated with the queue) Mutators in Scheme:  definition should be in the form: (define-struct ADT (val1 val2 …) #:mutable)  In addition to the normal type-checkers and accessors, there should be mutators: 9 Mutators: (set-ADT-val1! the-mytype new-a-value) (set-ADT-val2! the-mytype new-b-value) Example from slides of a Mutable ADT:  A mutable queue is a (possibly empty) sequence (q1, q2, ..., qn ). Operations new-queue  Takes no parameters  Precondition: True (operation can always be done)  Postcondition: Produces a queue Q that is the empty sequence queue-empty?  One parameter, a queue Q = (q1, q2, ..., qn )  Precondition: True  Postcondition: produces True if sequence is empty, Falseotherwise enqueue!  Two parameters, an item e and a queue Q = (q1, q2, ..., qn )  Precondition: True  Postcondition: Modifies Q so that now Q = (e, q1, q2, ..., qn ) Head  One parameter, a queue Q = (q1, q2, ..., qn ).  Precondition: n > 1  Postcondition: Produces value qn . dequeue!  One parameter, a queue Q = (q1, q2, ..., qn )  Precondition: n > 1  Postcondition: Modifies Q so that now Q = (q1, ..., qn-1). 10 #lang racket (provide new-queue queue-empty? enqueue! head dequeue!) (define-struct queue (lst) #:mutable) (define (new-queue) (make-queue empty)) (define (queue-empty? the-queue) (empty? (queue-lst the-queue)) ) (define (enqueue! the-queue item) (set-queue-lst! the-queue (cons item (queue-lst the-queue))) ) (define (head the-queue) (last (queue-lst the-queue)) ) (define (dequeue! the-queue) (set-queue-lst! the-queue (drop-right (queue-lst the-queue) 1) ) 11 Lecture 5 Introduction to C  C is based on source files and header files  Implementation files (.c file) andHeader files (.h files)  Execution file (test.c file with a main method) Example: Implementation file //add.c int add (int a, int b){ int c = 4; return a+b; } Header file //add.h int add (int, int); Execution file (used for testing) //test.c #include “add.h” int main (void){ printf(“ 3 + 5 = %d/n“, add(3,5)); return 0; }  must include header file to import the methods (header file contains all signatures)  user include to import files  other files that can be imported: (for printf and scanf) (malloc and free)  must have “return 0” at the end of “main” to terminate evaluation 12 Types in C  parameters, functions, and variables must all have a type  all variables must be given a type before they are used (e.g. int a = 0;) Type int  Can be positive or negative  32 bits of memory 31 31  Can represent integers fr31-2147483648 to 2147483647 or-2 to 2  Arithmetic done modulo 2 Example from slides:  Suppose int a = -2147483648; int b = 2147483647;  What isa-1? 2147483647  What isb+1? -2147483648  What istimestwo(b)? -2  int type not precise  if operation result is non-int (e.g. 5/2), the output would be rounded down (5/2 = 2) Integer comparisons (produces true or false) (int int, e.g. 4==3) == Equals <= Less than or equal to >= Greater than or equal to > Greater than < Less than != Not equal to Boolean operators && and not !(…) or || Combination of Boolean operators and comparisons: Example from slides: (i>3) && (i != 5) 13  use parentheses (…) to control precedence and order Conditional Statements The general form: if ( boolean expression ) { //some statements } if ( boolean expression ) { //some statements } else if{ //some statements (NOT NECESSARY) }else{ //some statements (NOT NECESSARY) } Iteration  repetition is more accepted than recursion while(Boolean expression){ } For loops (counted loops) for(;; initializes a variable to count  tests if the loop should continue  increments the variable in forthe next iteration Example from slides: for(i=1; i <=10; i=i+1) { printf("i=%d\n",i); } 14 Lecture 6 Variables, Memory, Pointers Scope  Variables outside of functions areglobal variables  Variables inside functions arelocal variables. extern keyword - > allows variable declaration only for global variables static keyword ->
More Less
Unlock Document

Only pages 1,2,3,4 are available for preview. Some parts have been intentionally blurred.

Unlock Document
You're Reading a Preview

Unlock to view full version

Unlock Document

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.