4 Sep 2013: Introduction to Comp 50

Sign up for Piazza: piazza.com/tufts/fall2013/comp50

Quick start on class home page

Overview: Supports of problem-solving

Diagram of the course:

                  Solve Problems
                /       |        \
   Domain     /         |         \
  Knowledge--/   Design and Build  \- Math
                     Programs           - algebra
                        |               - trig
                        |               - probability (counting)
                Understand **Data**

                                    Ultimately,
                                  **better** programs

Problem-solving technique:

   Problem -> Data -> Design Recipe -> Program -> Better Program

“Better” means

Plus the skill to articulate how you have solved a problem.

Projects

Labs, homeworks, and projects, of which the best are projects. Goals:

Some examples:

Not all guaranteed to be offered, but definitely GPS and definitely web-page language.

What kind of class is this?

Primarily about learning, not grades

What do I do to help you learn?

You’re doing the work of learning, but we do a lot of stuff that helps:

  • In-class quizzes, just about every day.
    Goal: get your brain loaded and into the on position.

    Board: Monday’s quiz (not graded): high-school trigonometry. Review your sines, cosines, and radians.

  • I create labs, which are guided, hands-on experiences.
    These experiences address problem-solving by computer or help you learn technology.

  • I create homeworks and projects, which are independent, hands-on experiences solving problems by computer.

  • My staff and I respond to questions: on Piazza, in labs, in office hours.

    We also teach one on one in labs and office hours.

  • Last but not least, I lecture. This has little to do with transmitting information; my goal here is to empower you to do your best work. For those of you who have played organized sports, it may help to think of me as a coach.

    Don’t try to write it all down; do write down what’s meaningful to you. My notes are all on the web.

But we do get grades, right?

Yes. Although I am not about grades, I recognize that grades are important:

  • No traditional exams: it is too difficult to measure the skills that are really important

  • In-class quizzes, just about every day. Some are graded, pass/fail.

  • Weekly lab sessions. You will perform an activity of learners: articulate what you did and what you learned from it. We’ll help.

  • Homework and projects: we’ll grade something from every homework, but we don’t have enough staff to grade every problem from every homework.

  • In lieu of final exam, learning portfolio. In effect, you identify an area where you can demonstrate learning. It’s two samples of your work and a very short explanation of how they demonstrate learning. Very similar to samples of your work and a cover letter that you might submit to get a job interview or an internship—and we hope you will use it exactly that way.

    We’ll give you lots of help, and we’ll talk more about this later.

What I expect from you

I point out the path up the mountain. You climb it.

  • You understand that lecture is not for transmitting information. You won’t get everything you need in lecture!

  • You understand that to get the information you need, it’s your responsibility to turn to other sources:

    • The textbook

    • Perhaps Khan Academy (if you need to bone up on any math)

    • Perhaps other Web resources

  • You hone your skills through deliberate practice [board] — look it up

Our commitment to you: we work very hard to make it possible for you to have a great experience.

What’s your corresponding commitment to us?
I expect two things:

  1. First, you do something ambitious. You get to define what your ambition is. It might be to build something, to master a new way of thinking about something, to make your math knowledge practical, to articulate your problem-solving skills brilliantly, or something else entirely.

  2. Second, you must engage in brief, daily sessions of deliberate practice:

    • Daily reading
    • At least one exercise per day from the book
    • Look at Piazza once per day

    A couple of words about brief, daily sessions:

    • Trumps prior experience

    • After two or three weeks of 45 to 90 minutes per day, most people start to experience “instant recall” of where they were.

Summary

Are we detecting a theme here? You are responsible for learning new skills and new abilities, and you will learn to assess yourself so that you know where you are. Everything in the course is bent toward that end.

The technical foundation of program design: data

Please have with you a driver’s license, government ID, or Tufts ID.

Setting out: procedures and formulas

You have homework already. Tiny amount of code, serious thinking.

Two goals:

The big picture is that real-world data all come with a form of arithmetic:

In each case, arithmetic leads to formulas

We are therefore about to

All your programs will have formulas in them

Enacting procedures

Class exercise: procedures and formulas, part 1:

  1. Procedure: everybody get up and stand in a line

    (Impossibly complicated for the computer)

  2. Procedure: find the person in the middle

    How do we simplify this enough for a computer?

    • Initialization: Two people on the end raise your hands

    • Step: If a person next to you has hands raised and you do not, raise your hand

    • Termination: last person to raise a hand is the person in the middle (could be one person or two)

    We won’t count these.

  3. Procedure: step forward from the middle out (count and find formula)

    • Initialization: Middle person step forward

    • Step: If the person next to you is forward and you are not, step forward

    • I’m going to put on the board the number of people who are forward at the end of each step

    • Termination: everyone is forward

  4. Procedure: choose two people and sit down (count and find formula)

    • Initialization: I choose someone to raise a hand

    • Step:

      • All those with hands up go to the podium

      • If you are on the podium and your hand is raised, point to two people still in line whose hands are not raised. Then sit down.

    • I’m going to put on the board the number of people who are seated at the end of each step

    • Termination: everyone is seated

Identifying formulas

Formulas:

  • What formula predicts how many people are standing as a function of time?

  • What formula predicts how many people are seated as a function of time?

Writing formulas using Racket

Live coding: check our work

  • Contract purpose and header

  • Examples

  • Body

  • Test

Useful functions: expt

(define (log10 x) (/ (log x) (log 10))) (define (decibans x) ...)

9 Sep 2013: Review; the design recipe; using conditionals

Context

Take the “flash of insight” and put it into place in a system

Part of the system is the table of examples:

We have (N) We want (seated) We also know (expt 2 N)
1 1 2
2 3 4
3 7 8

Use this method for filling in function template.

Homework review

Tesla’s frequency meter

What’s going on with Tesla? What did Tesla measure?

  • Q: How did we discover the rule?

  • It looks like we’re adding a halftone? How does that get translated into multiplication?

    Answer: it’s a fact of human audio perception. True of loudness as well as pitch. Also affects perception of brightness (but this is more complicated).

    Key algebraic question: what function f has the property that
    f(x + y) = f(x) × f(y)? 

    Another question: what function g has the property that
    g(x × y) = g(x) + g(y)? 

    These functions are a key to understanding behaviors and to dealing with large numbers.

    • Example: if you are searching a large collection of things, say 30 million American college students, searching 30 million things could be a big task even for a computer. But if you can cut the number in half at each step, you can zero in on a particular student in only 25 steps. That means you can even afford some expensive steps.

    We won’t worry about efficiency for quite some time. But we will be working sooner with probability, and that second function g will be very handy.

  • Finally, Tesla’s karma problem, anyone?

Probabilities in decibans

Likert scale:

  • If an event is equally likely and unlikely, what are the odds?

    What’s the log of the odds

  • What’s a rational scale look like?

  • What slots did you pick?

  • Where are your events?

Quiz: Spherical geometry

This week, just immigration, conditionals, animations

Next week, GPS. However, I promised you a quiz!

Answers should be two formulas using R and θ

Post-quiz: in the Earth’s frame of reference, how far does Boston travel in an hour?

11 Sep 2013: Design practice

Announcements

Daily practice: reading, at least one exercise, check Piazza

Study groups: lab will help you meet people and form them

Lab today! 3pm

For lab you need a CS account and password.

For lab you need a signed copy of the Bargain.

Commentary on homework:

Quiz

Recapitulating the design process

Problem is to compute “learning capacity hours”

Data includes

Designing programs requires us to (a) make a plan, (b) build the bricks, (c) stack the bricks together.

16 Sep 2013: Variants, structures, interactive programs

Today:

First: any questions about tonight’s homework?

Variants (definition by choices)

Board: latitudes

Goal: review for tonight’s homework

Study abroad: subtropical? temperate? subpolar? How long are the shortest days?

Demonstration: How to design Universe programs

Goal: preparation for next homework (user-interface experiment)

(Demonstrate handin server)

Eventually we will build a simulation of the algorithms from the first day of class. But that simulation will require advanced techniques. Today we will simulate a traffic light.

Ideas of big-bang:

Ideas of how to design programs:

This is a chunk of the skill you’ll develop. You’ll get to practice it over and over. Second time today.

So, questions:

Domain knowledge: the transparent square

18 Sep 2013: Structures, world programs, and GPS navigation

Today:

Homework review

Interest rate best off as a number.

Let’s review the guessing game.

Explain portfolio.

Exercise for pairs, then quads:

Structures (definition by parts)

What’s wrong here?

(make-player "Hamm" "forward")
(make-player "Brady" "quarterback")

Q: What functions do we get from this definition?

Q: What is the template for writing a function consuming player?

Structures in world programs

What if we want proper timing for the traffic light?

What if we add a car to the simulation?

Design practice: GPS navigation

The human and the computer

GPS navigation is a sequence of steps (to waypoints) that reach a destination.

The arithmetic of GPS coordinates

(Forgot my handheld GPS device. But some of you have them in your phones.)

Domain knowledge: GPS navigation

Math for:

  • Flat-earth distance

  • GPS projection

  • (x, y, z) coordinates for great-circle distance using dot products

23 Sep 2013: Understanding big-bang; variants

What we are looking for in the homework

(See handout)

Data description

It’s everywhere. In particular, it’s everywhere in your homework!

Big-bang skits

Ask for a programmer

Roll dice for functions

Variants

Airline customers:

(define-struct mr (first last))
(define-struct ms (first last))
(define-strudr dr (first last))

Design function "Welcome aboard, Mr Ramsey!"

Employees:

(define-struct grad-ta (name stipend))
(define-struct hourly-ta (name wage hours/week))

Design function

Pay to the order of Tom Williams $538

30 Sep 2013: Self-referential data

Board:

                         
       DEFN BY CHOICE <-------> DEFN BY PARTS
                  |            /
                  |         /
                  V     /
                ATOMIC            [SELF-REFERENCE]
             (by name)              (by name)

Add these arrows later:

Quiz: data description

State of the course:

Teaching and research

The university has two missions:

  • Pass on the knowledge we already have
  • Create new knowledge

Every professor contributes to both of these missions.

This past week:

  • Two days teaching at Tufts
  • Five days meeting with 400 other people who are creating new knowledge

For example, I learned that

  • The part where you guess the formula based on your table of examples? There is a web site that tries to do this (but it uses a different language from BSL).

  • There are powerful new techniques for integrating database queries into a language related to Intermediate Student Language

  • Something very like Intermediate Student Language is being used in the Pediatric Anesthesia Research Team and the University Hospital in British Columbia. Computer controls drugs (one of which killed Michael Jackson).

Grading

As a result, very far behind on grading. It’s now the top priority.

Your learning

Congratulations! You’ve reached Level 1: basic programming with bounded data. You also have a lot of practice writing interactive graphics programs with big-bang.

If you’re concerned about the course, I’d love to see you. We’re losing three students a week. I’d like to know what I need to do differently.

What’s next? The last way to organize data. What problem does it solve?

  • We get a way to work with unlimited amounts of data

Who knows Ken Ritchie?

Let’s draw a picture of the conspiracy:


                     NR
                    /  \
         AB                  JA
       /    \
    MW       AP          ?       ?

Plan:

  1. Build it out

  2. Who hasn’t fully recruited yet?

    Get more recruits! (At most two per person)

  3. How long does it take a conspiracy to spread?

    Ask everybody to send email to comp50conspiracy@gmail.com. Include your name and the name of the person who recruited you. If you like, you may include your recruits’ names as well.

How to describe a conspiracy?

Key phrase:

When you have found a new recruit, give your recruit these instructions

The instructions refer to themselves!

The data description is also going to refer to itself.

Data description
A person is a structure:

(make-person first last)

where first and last are strings

A conspiracy is either

  • A structure:

      (make-cell head recruits1 recruits2)

    where

    • head is a person
    • recruits1 is a conspiracy
    • recruits2 is a conspiracy
  • A structure

      (make-no-recruits)

And DRAW THE ARROWS

We need

(define-struct person (first last))
(define-struct conspiracy (head recruits1 recruits2))
(define-struct no-recruits ())

Commentary:

  • A self-referential data structure is always defined by choice

  • There must be
    • At least one choice that is self-referential
    • At least one choice that is not self-referential
  • The empty structure (make-no-recruits) comes up often:
    It acts a bit like “zero.”

What questions can we ask about a conspiracy?

How many people are in the conspiracy?

I can ask Ali and Jordan, who can ask their recruits, and so on…

How do we make this idea precise?

  • Signature/purpose/header
  • Examples
  • Template

    Things to notice about the template:

    • Any self-referential data is wrapped in a call to the function being defined

    • In other words, the instructions refer to themselves!

    • This coding pattern is called natural recursion

  • Coding!
  • Tests!


Question Answer

Does the data definition Your template needs as many cond distinguish among different clauses as subclasses that the
subclasses of data? data definition distinguishes.

How do the subclasses differ from Use the differences to formulate each other? a condition per clause.

Do any of the clauses deal with If so, add appropriate selector structured values? expressions to the clause.

Does the data definition use Formulate “natural recursions” self-references? for the template to represent
the self-references of the data definition.

Does the data definition refer to Contemplate the development another data definition? of a separate template. See Structures In Lists in the book. ———————————————————————————

: Formulating a template for self-referential data


Question Answer

What are the answers for the The examples should tell you which non-recursive cond clauses? values you need here. If not,
formulate appropriate examples and tests.

What do the selector expressions The data definitions tell you what in the recursive clauses compute? kind of data these expressions
extract and the interpretations of the data definitions tell you what this data represents.

What do the natural recursions Use the purpose statement of the
compute function to determine what the
value of the recursion means not
how it computes this answer. If
the purpose statement doesn’t tell
you the answer, improve the
purpose statement.

How can you combine these values If you are stuck here, arrange the into the desired answer? examples from the third step in a table. Place the given input in
the first column and the desired
output in the last column. In the intermediate columns enter the
values of the selector expressions and the natural recursion(s). Add examples until you see a pattern
emerge that suggests a ``combining’’ function.
———————————————————————————

: How to turn the template into a function definition

2 Oct 2013: More trees; lists

Quiz: Function templates

Now you do one:

What is the template for a function that consumes rooms? (Example: capacity)

Announcements

Trees

Revisit the conspiracy tree:

The railway tree

(define bos (make-stn "South Station" 0))
(define bby (make-stn "Back Bay" 1.1))
(define pvd (make-stn "Providence" 42.6))
(define nhv (make-stn "New Haven" 156.4))
(define nro (make-stn "New Rochelle" 212.1))
(define nyp (make-stn "NY Penn Station" 228.7))

What’s different?

The penguins

Data definition for penguins

Function: is there a #12?

BSL lists

Functions:

7 October 2013: More lists and trees; designing

Today:

Coming attraction:

The railway tree

(define nyp (make-stn "NY Penn Station" 228.7))
(define nro (make-stn "New Rochelle" 212.1))
(define nhv (make-stn "New Haven" 156.4))
(define pvd (make-stn "Providence" 42.6))
(define bby (make-stn "Back Bay" 1.1))
(define bos (make-stn "South Station" 0))

Live demo: how to make a tree

Functions:

List design:

The Essential and the Incidental

What are you learning?

What do we think of all this?

  1. Language is dominated by fashion (some languages are better for some purposes, but they don’t always win.

    Vocabulary and grammar are rote learning. Fluency will come with time and practice. Lean on the manuals and the first Intermezzo.

  2. Domain knowledge rocks. Every problem solver needs it. Sometimes (usually later in your career) you will work with a “domain expert.” For example, Professor Brodley works with radiologists to help teach the computer how to read X-rays and MRIs. But while you’re a student, and early in your career, or if you start a company, often you have to become the domain expert.

    Start now. Take your hobbies seriously. Go deep into something that interests you—know more than anybody else.

  3. The rules of computing are necessary. They become interesting when

    • As a last resort, you have to figure out what went wrong

    • You need to know what things cost:
      • Will it run on my PC?
      • Will it run on my phone?
      • Will it support a thousand users? A million?
      • Will it handle big data? Cost is a big point of emphasis in COMP 15.
  4. The key idea of this course is systematic problem solving. It helps you with business (courses), engineering, math, English, journalism, medicine, and other things. I guarantee it.

    Roles:
    • Keeps 15h from turning into 30h
    • By the end of the term, you won’t need a TA

Become a card-carrying member

6. Tests
5. Code
4. Template
3. Functional examples
2. Signature/purpose/header
1b. Data examples
1a. Describe data
The design recipe from the bottom up, with feedback loops

The design recipe from the bottom up, with feedback loops

The Grid

Add variants!

  • cond cases with type predicates
                                        forms of data       
                                        =============

                   |  "atomic"                |  "enumerations"      |  "structure"            
    process steps  |  numbers, images, ...    |  intervals, strings  | define-struct 
    ===============-------------------------------------------------------------------
                   |                          |  [1,3] (1,3) [1,3)   | (make-posn 3 4)
    describe data  |  Number Image            |  color is one of: .. | (make-dst "h")
    ----------------------------------------------------------------------------------
    signature      |  Number -> Image         | XYZ -> Number        | ABC -> String
    purpose        |  create sq of size s     | convert into number  | add "Dear" to name
    header         |  (define (square s) ...) |                      |
    ----------------------------------------------------------------------------------
    functional     |  3 |---> []              | [1,3] |---> 2        | (make-posn 3 4)
    examples       |  ....                    | ...                  | |--> "5"
    ----------------------------------------------------------------------------------
    template       |  domain knowledge        |  cond cases!         | selector expr.
    ----------------------------------------------------------------------------------  
                                        now code 
    ----------------------------------------------------------------------------------
    tests          |                    turn examples into tests (use of check-expect)
                   |  (check-expect (S 3) []) | (check-expect        | (check-expect 5
                   |                          |      (f 1 3) 2)      |    (f (make-posn 3 4)))

Interplay of the steps, e.g., in the line-drawing or circle-dropping programs.

9 October 2013: More with lists

Two more extension tokens

Quiz: function templates

More flexible views of lists

Convert list of points to list of positions:

Followups:

Testing data examples for the apocalyptic railway:

Two lists at once

Three cases:

Two lists in lockstep

Hints to lockstep:

  • Both lists are the same length
  • The last part of the longer list is ignored

Lockstep example: zombies on the railway

(define northeast (list nyp nro nhv pvd bby bos))
(define zs        (list   0   0   7  83  40   0))

Problem: compute a list of stops on the apocalyptic railway, where a stop is either a station or a horde of zombies (see demo).

In-class demo: tally-invasion

Both lists unsealed, not in lockstep

Classic example: merge two sorted lists

In-class demo: merge

15 October 2013: Intertwined data definitions

NOTE: Issued two more extension tokens for a total of 5

Homework review

Quiz: templates

This one is tricky. Luckily you have the template handout!

A nonempty list of strings (1LOS) is one of:

Write a template for a function that consumes a nonempty list of strings. For example, you can imagine a function that puts a space between words instead of the one you did in lab that puts spaces after words.

Representing BSL programs: mutual recursion

Data definition:

; An S-expr (S-expression) is one of:
; – Atom
; – SL
; An SL (S-list) is one of:
; – empty
; – (cons S-expr SL)
; An Atom is one of:
; – Number
; – String
; – Symbol

We must be sure we can build it!

Call for data examples

16 October 2013: Designing functions with mutual recursion

Data definition:

; An SX (S-expression) is one of:
; – Atom
; – SL
; An SL (S-list) is one of:
; – empty
; – (cons SX SL)
; An Atom is one of:
; – Number
; – String
; – Symbol

Examples:

Round SX SL Atom
1 empty 3, "Hello", 'joe, '+
2 3, "Hello", 'joe, '+ empty
3 '(cons 3 empty), '(list 3), '(3), ("Hello"), (+)
'(("Hello") "Hello"), '(* (+ x 1) (- x 1), …

More examples:

Key ideas:

To translate data definition into template, use handout

Programming problems:

Can we define a BSL-expression? (Symbol in operator position)

Two S-expressions!

Are two S-expressions the same except for numbers?

Are two S-expressions different in only one atom?

Are two S-expressions different in only one subexpression?

21 October 2013: Templates and tables of examples

Reading: Part IV, Section 19 (and Intermezzo 3)

Introduction to Level 1?

Placing text in the corners of a game board (and other demos)

Demonstration of costs

23 October 2013: More abstraction

What causes code bloat?

What makes software simple or complex?

28 October 2013

Today:

Relevant reading: First Edition, Sections 19 and 20

Quiz: kinds of data definition, corresponding templates

Homework review:

Local definitions

Example: Corner placement

  • Revisit UR
  • Other corners

Where else have you seen repetition?

There is a demo file for text placement.

30 October 2013: More abstraction using function values

Relevant reading: First Edition, Sections 21 and 22

Do not share code! (Violation may have occurred; I have no choice)

Local definitions for performance (bonus content on web only)

Longest-string example is in demo; see function longest in section “More than just clean laundry”.

Costs of various operations for inputs of size N
“Constant” (means independent of input) logN N NlogN N2 2N (exponential)
cons? find station safely search all stations efficient sort insertion sort (worst case) all arrangements
longest string with repeat calls
find nearest town search a list
length of list
insertion sort (if nearly sorted)
longest string (one call)

Cost table in notes

Abstraction for reuse

Design goal: reuse (a mark of quality software)

Abstraction in data definitions:

Now the data definition looks like a function. The capital X is a type parameter. It stands for an unknown class of values. Like the Stepper, the data definition works by substitution.

A `(listof X) is one of

(See two occurrences of type variable.)

Type variable stands for an unknown type: student, number, string, station, and so on. (In a regular function, the parameter stands for a single unknown value.)

This style of programming is called programming with generics (Java) or sometimes parametric polymorphism. C++ uses something called templates. We will talk about parametric data definitions.

Opportunities for abstraction around lists

Purpose statements:

  • To tell if there is a    student  in this class who carries a MacBook
  • To tell if all           students in this class carry MacBooks
  • To produce a list of all students in this class who carry MacBooks

  • To tell if there is a    student  in this class who lives in Tilton
  • To tell if all           students in this class live in Tilton
  • To produce a list of all students in this class who live in Tilton

  • To tell if there is a    student  in this class who has an Android phone
  • To tell if all           students in this class have Android phones
  • To produce a list of all students in this class who have Android phones

  • To tell if there is a    student  in this class who is a sophomore
  • To tell if all           students in this class are sophomores
  • To produce a list of all students in this class who are sophomores

Other purposes:

  • To produce a list of home states of all students in this class
  • To produce a list of class years of all students in this class
  • To produce a list of heights     of all students in this class

  • What student in this class has the smallest phone?
  • What student in this class has the heaviest backpack?
  • What student in this class lives furthest from Tufts?

  • What string on this list is the longest?
  • What protein on this list is most similar to my new protein?
  • What word on this list is most similar to this one I have misspelled?

To solve these problems, other languages have “loops”. In 15 you will encounter while loops and for loops and perhaps other flavors of loops.

We will define functions. These functions are called polymorphic or generic.

Questions:

  • What are the signatures?
  • What are some code examples?
  • How can we abstract?
  • What does abstraction do to the signatures?

ISL functions

procedure?

map
andmap ; aka forall?
ormap  ; aka exists?

filter
foldl
foldr

compose

build-list

argmax
argmin

apply

quicksort
sort



XXX memf

XXXbuild-string
XXX for-each

4 Nov 2013: More list functions

Responses to midterm evals:

Similar purpose statements:

DEMO: The longest string

DEMO: Let’s generalize!

And other ideas from students.

Function composition

What is the average SAT score of all the freshmen?

6 Nov 2013: Readability of list functions; folds

Today:

Example solution to permissible words (with lambda)

“Do something to each” == fold

13 November 2013: Generative Recursion (guest lecturer Christos Dimoulas)

Today’s topic: Generative recursion First a recap (structural recursion):

Recapitulate structural recursion

A large system, I worked a little bit on it every day.

Now let’s define a function:

;; summarize-table :: table -> line
;; aggregates the elements of the given Table as a Line

[functional examples not captured]

Template:

(define (table-summary a-table)
    (cond 
        [(empty? a-table) ... ]
        [(cons? a-table) (... a-table ... (first a-table)
                          ... (rest a-table) ... (table-summary (rest a-table)))]))

Template lets us know what we have available to us. We get first and rest “for free” when working with lists.

Idea: we need a helper function that adds lines (he’s already written the template)

addTwoLines :: Line -> Line -> Line 

(Now we are talking about this helper function: how many cases do we have?

We go through the template for two lists;

...

Now what’s the last step of the design recipe? Tests. Let’s turn our examples into the tests with check-expects (This has been done already in the code for brevity’s sake).

But first can we can use “loops” to simplify our code. (This is another name for fold, map, and so on).

Hey, let’s use a foldr! (And we do it, all the check-expects pass again. Super.)

Beyond structural recursion

Ok, continuing with the example: I stored my data in a Table, but my friend stored his in an Excel file (CSV format).

We talk about CSV files – Racket has a friendly way of dealing with this format.

A CSV is a (listof datum) 

where a datum is:
  a number 
  eol (end of line character)

Data examples:

empty
(list eol)
(list 60 eol)
(list eol eol) //two empty lines

Hmm now we have two different data representations; we need a function that takes a CSV and returns a Table.

(We go through the purpose statement, contract and examples…should be in the code)

First instinct, let’s write the natural recursion template.

Uh oh, there’s no way to do this with structural recursion. Tricky.

Instead of using the structure to create a new, smaller problem to solve, we generate a new problem from the data.

We don’t have to change the template too much–just rearrange some words.

We need a function called getFirstLine, that returns the first line of the CSV as a list.

(He wrote it for us. This is just structural recursion.)

OK, what else do we need? We only processed the first line, now we need to get the rest of the CSV but we no longer have ‘rest’. We need to generate a new problem, so we want a function that removes the first line (i.e. truncates the CSV file). (He wrote this one again; the template is identical to getFirstLine; we cruised through these two functions…)

Q: What’s the signature for removeFirstLine?

A: CSV -> CSV, because a CSV can be empty.

What’s the trivially solvable problem?

How do we create the new problem?

Now let’s write tests! Make them from our examples.

We’re using a template that looks different but we aren’t going to throw out the design recipe. It’s actually the same template, but we just have different vocabulary.

The structure of the data give you the new problems to solve; be careful, and use your imagination to come up with new ways to solve the problem.

Pitfalls:

We now need to have a termination argument. Every time you write a function using generative recursion, you need to guarantee that the recursive call terminates.

AVOID GENERATIVE RECURSION (if you can): There are usually simpler weapons.

One more example: Fibonacci’s rabbits

Fibonacci numbers. To figure out how fast he’s gonna get more rabbits, Fibonacci made a sequence, etc. Now we are looking at shells and the golden ratio to motivate Fib numbers in real life.

Let’s write a function (in five minutes) to calculate Fib numbers.

Fib : Positive -> Positive

Data definition:
a Positive is either:
 0 or 
(+ 1 n) where n is a Positive

(Now we are looking at the code for the purpose statement; data examples and template; Uh oh, my template doesn’t give me (- 2 n) based on the structure of our data definition;

18 Nov 2013: More generative recursion

Problems:

20 Nov 2013: Generative recursion; probability

Board:

Problems:

Two dice at most N

How many tries should it take you to roll 7 or less?

Odds of dice 1 vs dice 2 = P(observation|dice1) / P(observation|dice2)

How much evidence is added by an observation?

d4+d6:

`((0 = 0)
  (1 = 0)
  (2 = 0.0416)
  (3 = 0.125)
  (4 = 0.25)
  (5 = 0.416)
  (6 = 0.583)
  (7 = 0.75)
  (8 = 0.875)
  (9 = 0.9583)
  (10 = 1))

d4+d8:

`((0 = 0)
  (1 = 0)
  (2 = 0.03125)
  (3 = 0.09375)
  (4 = 0.1875)
  (5 = 0.3125)
  (6 = 0.4375)
  (7 = 0.5625)
  (8 = 0.6875)
  (9 = 0.8125)
  (10 = 0.90625))

d4+d10

`((0 = 0)
  (1 = 0.025)
  (2 = 0.075)
  (3 = 0.15)
  (4 = 0.25)
  (5 = 0.35)
  (6 = 0.45)
  (7 = 0.55)
  (8 = 0.65)
  (9 = 0.75)
  (10 = 0.85))

d4+d12

`((0 = 0)
  (1 = 0)
  (2 = 0.02083)
  (3 = 0.0625)
  (4 = 0.125)
  (5 = 0.2083)
  (6 = 0.2916)
  (7 = 0.375)
  (8 = 0.4583)
  (9 = 0.5416)
  (10 = 0.625))

d4+d20:

`((0 = 0)
  (1 = 0)
  (2 = 0.0125)
  (3 = 0.0375)
  (4 = 0.075)
  (5 = 0.125)
  (6 = 0.175)
  (7 = 0.225)
  (8 = 0.275)
  (9 = 0.325)
  (10 = 0.375))

d6+d8:

`((0 = 0)
  (1 = 0)
  (2 = 0.02083)
  (3 = 0.0625)
  (4 = 0.125)
  (5 = 0.2083)
  (6 = 0.3125)
  (7 = 0.4375)
  (8 = 0.5625)
  (9 = 0.6875)
  (10 = 0.7916))

d6 + d10

`((0 = 0)
  (1 = 0.016)
  (2 = 0.05)
  (3 = 0.1)
  (4 = 0.16)
  (5 = 0.25)
  (6 = 0.35)
  (7 = 0.45)
  (8 = 0.55)
  (9 = 0.65)
  (10 = 0.75))

d6+d12:

`((0 = 0)
  (1 = 0)
  (2 = 0.0138)
  (3 = 0.0416)
  (4 = 0.083)
  (5 = 0.138)
  (6 = 0.2083)
  (7 = 0.2916)
  (8 = 0.375)
  (9 = 0.4583)
  (10 = 0.5416))

d8+d10

`((0 = 0)
  (1 = 0.0125)
  (2 = 0.0375)
  (3 = 0.075)
  (4 = 0.125)
  (5 = 0.1875)
  (6 = 0.2625)
  (7 = 0.35)
  (8 = 0.45)
  (9 = 0.55)
  (10 = 0.65))

d8 + d12:

`((0 = 0)
  (1 = 0)
  (2 = 0.010416)
  (3 = 0.03125)
  (4 = 0.0625)
  (5 = 0.10416)
  (6 = 0.15625)
  (7 = 0.21875)
  (8 = 0.2916)
  (9 = 0.375)
  (10 = 0.4583))

d10+d12

`((0 = 0)
  (1 = 0.0083)
  (2 = 0.025)
  (3 = 0.05)
  (4 = 0.083)
  (5 = 0.125)
  (6 = 0.175)
  (7 = 0.23)
  (8 = 0.3)
  (9 = 0.375)
  (10 = 0.4583))

2 December 2013: Splitting in two

Note: Online course evaluations

Today:

Live coding: writing drop

Live coding: balanced 2D trees

Live coding: path ratio and tree balance
(load a model)

People’s choice:

4 December 2013: Coding in the wild

Handout: creating languages with Racket

Note: course evaluations (labs and projects)

Barriers to entry for beginning programmers

List of barriers to entry (board):

Review of syntactic structure that you know:

Example BSTs:

Concrete syntax:

Mutable state:

Split into “statements” and “expressions”:

Pointers:

Costs matter: arrays

Arrays are like lists except:

The template for arrays:

9 December 2013: Skills transfer

Note: Alert if portfolio in by 9pm

How to approach a new language

Don’t forget you can cheat: It’s always legitimate to solve a problem using Intermediate Student Language, then borrow structure from your solution and transfer to the unfamiliar context.

Data definition

This is the key question:

  • Every language comes with atomic data

  • Numbers are universal, strings are spotty, images are rare, symbols are rare

  • Every language is good at definition by parts.

  • The problem spot is definition by choices:

    • Often the good trick is to put a tag as one of the parts in a definition by parts

Statically typed languages

Data definition is often enforced:

  • Usually less expressive than what you’re used to

  • Not all languages have parametric data definitions (called parametric polymorphism or generics)

    (I know from reading your homework that you mostly understand the concept but have struggled with the details and the notations)

  • The error messages are going to be a barrier. You will break through the barrier with help and persistence. Hold onto your concepts and vocabulary; don’t let the new vocabulary hide the underlying similarities.

Say goodbye to check-expect

Unit testing tends to be much more heavyweight than you are used to.

Most languages have “frameworks.”

  • Fairly large cost of entry

  • Afterward, the marginal cost of adding new tests is relatively small—it is comparable to building code

Templates

People won’t tell them to you—you will have to suss them out. But if you ask how to “examine” or “observe” a data structure, that will help.

  • The principles of choice and selection will always work for you

  • The idea of natural recursion will always work for you

  • In many contexts, people may expect you to write natural recursions using “loops.” You will learn about loops and arrays (called vectors in your book).

Other stuff

Example BSTs:

Concrete syntax: memorize through repetition

Mutable state: a new skill, some support in your book

Split into “statements” and “expressions”: covered last time; not hard

Pointers:

Costs matter: arrays

Arrays are like lists except:

  • Access to any element in constant time

    Versus

    ;; nth : natural (listof X) -> X
    ;; to produce the `n`th element of xs, counting from zero
    (define (nth n xs)
      (first (drop n xs)))
  • But: unlike a list, an array is hard to grow and shrink

    (thus, “dynamic arrays”)

The template for arrays:

  • The for loop (just like a structural recursion)

Back to COMP 50 home page.