EBoard 30: SoLA 3

Approximate overview

• Admin
• Fun with Compose and Section
• Q&A

Administrative stuff

Introductory notes

• Sorry class started late!

Upcoming activities

Token Events

• CS Extras Thursday at 4pm in 3821: Molecular programming!
• Writers@Grinnell Thursday at 8pm in Bucksbaum 131 with Ralph Savarese and Tilly Woodward.
• Coffee Chat with Prof. Eliott Friday at 5pm in her lab. “Dear students, If you are a first or second year student, I hope you had the chance to visit professor Weinman’s excellent talk last week. In case you would like to continue the conversation… Join me this Friday to chat about a CS major! I will be happy to share how different adventures brought me to CS.”
• Football vs Cornell Saturday at noon
• GSO Saturday at 2pm in Sebring-Lewis
• Grinnell Singers Sunday at 2pm in Sebring-Lewis
• Collegium Sunday the 21st at 2pm.
• ISO Food Bazaar Sunday the 14th.

Other good things

• Men’s Basketball vs Spurgeon, 7pm Tonight
• Open House in the Grinnell Observatory, Thursday at 7pm

Upcoming work

• SoLA 3 due Thursday (tomorrow).
• Reading for Friday on Transforming XML (using Recursion).
• MP 7 assigned Friday: Transforming Web Pages.
  • Add table of contents.
  • Add some interisting info (e.g., Dale-Chall score).
  • Check for accessibility.
  • Faux News (“vaccine” -> “tracing liquid”; “virus” -> “myth”, “progressive” -> “anti-democratic”)
  • Roll your own

Fun with compose and section

• Elegance and concision are two valuable things in computing.
  • We care about elegance in all writing, including writing of code.
  • It’s easier to process shorter pieces of text.
• Both o and section help with both.

Let’s look at a simple example. Suppose I have a list and want to add two to each element of the list.

Starting point

(define add2
  (lambda (x)
    (+ 2 x)))

(map add2 lst)

Note: add2 follows a pattern that is natural for section. That is, it just calls one other procedure (+) and fills in one paramter of the procedure (2). So we could rewrite add2 using section (and without lambda).

(define add2
  (section + 2 <>))

Shorter, initially harder to read.

The section procedure builds a new procedure from an existing procedure, by filling in some of the parameters, but not all of them. In the example above, we’re taking the + procedure, saying “one of the parameters is 2” and leaving the other one open.

Where are we?

(define add2
  (section + 2 <>))
(map add2 lst)

We know that whenever you have a name in code, Racket substitutes the associated value. We could do the same.

(map (section + 2 <>) lst)

Whoo! We’ve cut out three more “words”.

Does this make it more concise? Yes.

Does this make it more readable?

Yes

• There’s only one line to read.
• We hope that, eventually (section + 2 <>) becomes easy to read.
  • It would be nice if we could type (+ 2 <>)

No

• It’s kind of complicated; it’s easier to read “add2” than “(section + 2 <>)”
• Both section and map together hurt our brains.
• This might be okay, but longer versions are harder.

Side note: I love that when I say “talk to your partner about this, I hear lots of chatter”.

Side note: It takes awhile to master this way of writing; that’s part of our goal.

A similar, but different example. Increment then add1 of a list.

(define add1-square
  (lambda (val)
    (sqr (add1 val))))
(define add1-square-list
  (lambda (lst)
    (map add1-square lst)))

add1-square meets the “compose” requirements. That is, it applies one procedure and then applies another procedure to the result. We can therefore rewrite using compose (o) and no lambda.

(define add1-square
  (o sqr add1))

In case you’ve forgotten, (o f1 f2 f3 ... fn), is a new procedure that applies fn and then fn-1 and then …. and then f3 and then f2 and then f1.

Whoo! We saved three words! It’s much shorter. Now we can substitute.

(define add1-square-list
  (lambda (lst)
    (map add1-square lst)))
(define add1-square-list
  (lambda (lst)
    (map (o sqr add1) lst)))

Is this better?

Yes

• It’s kind of intuitive. (o sqr add1) is no harder to read than add1-square.
• The brevity is nice.

No

• The ordering of sqr and add is confusing. Most of us think left to right, rather than right to left.
• But the lambda makes it more explicit where the input goes in.
  • Again, we need practice to say “This is a procedure; there’s an input ‘somewhere’.”

(define add1-square-list
  (lambda (lst)
    (map (o sqr add1) lst)))

Time to be evil. add1-square-list follows the “section” pattern. In particular, it calls one procedure, map, filling in one parameter,. (o sqr add1). So we can rewrite add1-square-list with a section.

(define add1-square-list
  (section map (o sqr add1) <>))

Is this clearer?

• No, unless you are a mentor or grad student studying functional programming.
• Or SamR

Is it somehow hideously beautiful?

• Yes, in Sam’s world

Will the SoLA look like this?

• Yes. Except for the “use section with map”, which is a bit too extreme.

Are there variants of section or composition with more parameters?

• Section does allow multiple parameters: (section string-append <> " " <>)
• o could be rewritten so that the last procedure takes multiple parameters. But it gets complicated.

Q&A on Misc Stuff

Sam, we’ve learned how to write some of the powerful procedures, like map and filter. Will we learn how to write o and section?

Yes, albeit in restricted versions. Soon.

Q&A on SoLA

Can you do the sample Style problem?

Step one: Reindent

(define rab
  (lambda (int str)
    (if (if (equal? #t (integer? (string->number (substring int str))))
            #t
            #f)
        (string->number (substring int str))
        (if (if (equal? (integer? 
                         (string->number (substring int 0 str))) 
                        #f)
                #f
                #t)
            (string->number (substring int 0 str))
            #f))))

Step two: Be ZoBy

(define rab
  (lambda (int str)
    (if (equal? #t (integer? (string->number (substring int str))))
        (string->number (substring int str))
        (if (not (not (integer? 
                         (string->number (substring int 0 str)))))
            (string->number (substring int 0 str))
            #f))))

Step three : More ZoBy

(define rab
  (lambda (int str)
    (if (integer? (string->number (substring int str)))
        (string->number (substring int str))
        (if (integer? (string->number (substring int 0 str)))
            (string->number (substring int 0 str))
            #f))))

Step four : You can never be too Zoby

(define rab
  (lambda (int str)
    (if (integer? (string->number (substring int str)))
        (string->number (substring int str))
        (and (integer? (string->number (substring int 0 str)))
             (string->number (substring int 0 str))))))

Step five: Check the parameter names

(define rab
  (lambda (str idx)
    (if (integer? (string->number (substring str idx)))
        (string->number (substring str idx))
        (and (integer? (string->number (substring str 0 idx)))
             (string->number (substring str 0 idx))))))

Step six: Factor out redundant code with let

(define rab
  (lambda (str idx)
    (let ([str1 (substring str idx)]
          [str2 (substring str 0 idx)])
      (if (integer? str1)
          str1
          (and (integer? (string->number str2))
               (string->number str2))))))

Can you do the sample Documentation problem?

Sure.

;;; (matching-indices pred? lst) -> listof? integer
;;;   pred? : predicate
;;;   lst : list?
;;; Finds the indices of elements of a list that match a particular predicate.
;;; (definition borrowed from exam).

For part b, “pred? must be applicable to all the elements of lst”. Or “When you apply pred? to an element of the list, it should not give you an error.” Maybe: pred? should be a predicate; that is, it should return true or false. (If it returns something else, those indices get selected.)

For part c (badly written), we know that (pred? (list-ref lst i)) holds (aka “is truish”, “does not return false or give an error”).

Should we document helper functions?

It’s nice to do so.

If you have local helpers (using let, or let*, or letrec), a one-sentence summary is fine. (letrec is used to define local recursive functions)

Can we go over data abstraction without structs?

Sure.

Basic idea: Clients focus on how they use the data structure, not how the data are structured.

Simple example: a point in two space.

We could store this as: (a) a list of two elements, (b) a dotted pair, (c) a vector of two elements, (d) a hash table with keys ‘x and ‘y; (e) a string with the x value, a comma, and the y value, ….

As a “client”, you just call point, point-x, and point-y without worrying what the implementation is.

That way, we can change the implementation.

; Defining points as dotted pairs
(define point cons)
(define point-x car)
(define point-y cdr)

(define distance 
  (lambda (pt1 pt2)
    (sqrt (+ (sqr (- (point-x pt1) (point-x pt2)))
             (sqr (- (point-y pt1) (point-y pt2)))))))

Let’s change our mind and rewrite points as hashes

; Defining points as hashes
(define point
  (lambda (x y)
    (make-hash (list (cons 'x x) (cons 'y y)))))
(define point-x
  (section hash-ref <> 'x))
(define point-y
  (section hash-ref <> 'y))

Big picture: We could write distance without caring how points are implemented. We could even change our implementation of points. That’s the big goal of data abstraction.

The kinds of things I’ll ask are “change the implementation of an abstracted data type”, “implement a data type”, “write something that ignores the underlying implementation”.

Can we go over pair structures and lists? (And do the diagram?) [+1]

Sure.

(cons "a"
      (cons (cons (cons (cons null "b")
                        null)
                  (cons null
                        (cons (cons "c" "d")
                              null)))
            (cons "e"
                  (cons "f"
                        null))))

(list "a"
      (list (list (cons null "b"))
            null
            (cons "c" "d"))
      "e"
      "f")

Which form should we use?

Either. But make sure to format so that Sam can read it.