Pages

Saturday, November 14, 2015

Testing Delegate Callbacks Without Mocks

The idea of using protocols in place of mocks was one I first saw at WWDC. More Recently, Eli Perkins explains how to use protocols for an instance of UIApplication.
The basic idea is to declare a protocol that exactly defines what methods I am interested in. When I’m registering for notifications at startup time, I’m not interested in 90% of the features of UIApplication. All I really care about is one method, so I’ll make that explicit with a type:
protocol PushNotificationRegistrar {
    func registerUserNotificationSettings(notificationSettings: UIUserNotificationSettings)
}
Since UIApplication already implements registerUserNotificationSettings(_:), I let the type system know that UIApplications conform to PushNotificationRegistrar with an empty declaration:
extension UIApplication: PushNotificationRegistrar {}
Now for my tests, I’m not trying to mock UIApplication and all of its unrelated baggage. I just need an object (class or struct) that provides the single function registerUserNotificationSettings(_:).
For the full explanation, go read Eli Perkin’s post.
So far so great. The part I haven’t seen discussed is the callback. My custom app delegate has a related delegate call:
optional func application(_ application: UIApplication,
didRegisterUserNotificationSettings notificationSettings: UIUserNotificationSettings)
Because that is defined in UIApplication, I can’t change the method signature to take anything other than a UIApplication. Testing that code path requires a mock UIApplication.
I find myself in this position with any of the system delegate calls. Core Bluetooth passes back CBPeripherals, and there’s no easy way to create a valid instance in a test environment without a mocking library.
I haven’t found a perfect solution, but the strategy I’ve come to adopt is to make your delegate callback methods as “thin” as possible. To show what I mean, I’ll use a CoreBluetooh delegate call from CBCentralManager:
optional func peripheral(_ peripheral: CBPeripheral,
     didDiscoverServices error: NSError?)
That callback passes you a CBPeripheral. The peripheral contains a services property containing an array of CBService. Each CBService contains a id property of CBUUID. So just to identify the service, you’re three properties deep into system provided objects.
optional func peripheral(_ peripheral: CBPeripheral,
     didDiscoverServices error: NSError?) {
     let services = peripheral.services
     for service in services {
        let id = service.UUID.UUIDString
        switch id {
            case .BatteryInfo:
                break
            case .ManufacterInfo:
                break
            // and on and on
        }
     }
}
The method can grow to inclued enough complex switching that you definetly want to test it.
Here’s the stragegy I came up with:
  1. Extract the required data in as few lines of code as possible.
  2. Redispatch to a helper method that takes only easily-created parameters.
Here’s my example:
// Declared in CBPeripheralDelegate
func peripheral(peripheral: CBPeripheral,
     didDiscoverServices error: NSError?) {
     let UUIDs = peripheral.services.map { $0.UUID }
     self.handleDiscoveredServicesWithUUIDs(UUIDs)
}

func handleDiscoveredServicesWithUUIDs(UUIDs: [CBUUID]) {
    // complicated switch statement here
}
CBUUIDs are easy to create in a test environment, so it will be easy to test my new function handleDiscoveredServicesWithUUIDs(UUIDs: [CBUUID]) That leaves one line of untested code: let UUIDs = peripheral.services.map { $0.UUID }. Even if you insisted on testing that line, keeping it so functionally constrained makes your mocking job easier. Personally, I probablby wouldn’t bother.

Wednesday, September 30, 2015

Go the Language

I've been playing with Go recently. Front-end, I'm an iOS dev. Back-end, I'm usually Python. A few thoughts on Go.

  • Types are nice. One reason I'm looking beyond Python is because I like a type system. Go is statically typed.
  • Compiled is nice. Performance is only part of it. Being able to statically link into one library solves deployment problems of a dynamic language. In interpreted languages, it can be a mystery where you're importing from, and leads to solutions like virtualenv or Bundler.
  • Go is lean. Google has mentioned that they want to keep the language minimal, and it shows. The core language is much simpler than Swift.
  • With such a minimal language, it really shows Google's priorities when the stdlib comes with a web server and HTML templating package.
  • Very useful to have a method of automatically pulling dependencies from github and elsewhere. I'm less sure of the philosophy of "All Go development in one directory."
  • Not everything needs to have objects. I though Django's class-based view system was over-engineered. It's actually refreshing that functions are emphasized over classes
I haven't even begun to dig into the concurrency features, which is supposed to be a big highlight. Overall, an interesting language, and one pretty fun to develop in. It's different enough that I need to spend some time developing in it to really understand it. Syntactically it's probably easier than Python, but it clearly requires patterns I'm not yet familiar with. I was going to write a simple blog engine in Go, but it became evident that would be a distraction. Maybe soon though.

Google Code Prettify Lives

Earlier I had expressed doubt about the maintenance of Google's code prettify syntax highlighter in general, and the availability of a Swift lexer in particular. Turns out I was overly pessimistic and they have a new active github repository with a Swift lexer.

Monday, March 30, 2015

NAS on the Way

I've been running a Zyxel NSA320, a two-bay NAS, for about a year now. I've been going slowly into the world of NAS, partly because I wasn't sure how it would fit into my workflow. I chose the Zyxel based on cost. At first I installed a single 500GB drive I had laying around. Once that filled up, I moved to a 3TB WD Red drive. After a while I was noticing I was keeping somewhat important stuff on the NAS, so I decided to add a second 3TB drive and migrate to a RAID 1. All of the migration was seamless. I've been running that RAID 1 setup for about six months now.

Now I'm taking the next step and replacing this NAS with a more capable device. This step is meant to replace a handful of DAS devices, so I'm going to put virtually all of my important info on the NAS, including photos, videos, and personal documents. To that end, I decided on a 4-bay NAS, thinking that RAID 5 would give me the best balance of capacity, performance, and redundancy. I'm going to reuse the 3TB drives I have.

Here are the factors that went into deciding on a solution.

Expandability

One of the advantages of NAS is the way it abstracts the notion of drives from storage. In the long term, I want to be able to expand my volume size. In the short term, I need to be able to go from a single disk, to a two disk mirror, to a three disk RAID 5. This is necessary to migrate my data from a two-drive mirror to a three drive RAID 5 by adding only one drive total, and directly transferring from one device to another (i.e., not backing everything up to a third device and using that to transfer). Most NASes do this with aplomb; it's really their bread-and-butter. A few lackluster consumer models fail in this regard, which is a deal-killer.

Performance

I'm giving up on my DAS drives, partly because of clutter: more Firewire, USB, and power cables than I want to deal with. I don't want this to feel like a big step down in performance. I need Lightroom, iTunes, Photos, etc., to access data on the NAS without feeling slow.

Backup

I'm a big believer of off-site backup. For homes and home offices, that means some cloud service. I need a way to backup the data on the NAS to the cloud. And I don't mean a half-measure like mount the NAS on a Mac and run Arq. I love Arq, but the NAS should have an integrated solution.

Spouse Friendly

The easier it is for my non-technical family members to use, the better. Not specific bullet points on this score.

Other lesser important factors:

  • Media streaming. A bonus. I'm intrigued by the Synology play series. But not a deciding factor.
  • HDMI. It's going under my desk, not in my TV cabinet. Not needed.
  • Pretty much any feature not related to serving files. No, I will not be running a blog, a wiki, or a forum on my NAS.
  • Time Machine. We're a Mac house, so I wish I could count on this. This is the one thing the Zyxel flat-out failed at. After several weeks the backup was inexplicably corrupt. Hopefully a quality NAS will be more reliable, but I'm not counting on it. It's really Apple’s issue. Nothing outside a Time Capsule or OS X Server is supported, and I'm not going either those routes.

So what did I choose? For that, dear reader, you'll have to come back next time. I'll reveal my choice and the rationale. The good news is that there are lots of good choices. The bad news is there isn't one obvious choice, or a singe standout vendor to make the decision easier.

Tuesday, March 24, 2015

Bell Labs Innovation

From Trust Me I'm a Scientist. The article is about audio sampling rates, but this passage stood out.

The mid-20th century was a heady time at Bell Laboratories. Just before its closing, it employed upward of 25,000 people, dedicated entirely to research and development.

Their innovations were enormous ones, and they lie at the root of the very device you are reading this on: The transistor, the laser, semi-conduction, the solar cell, television, C++ programming, the fax machine, and by the 1960s, the goddamn video phone.

For the sake of contrast, Google, one of our greatest innovators of today, employs roughly 50,000 people across all of its departments, and it’s greatest offerings have been, well… a slightly improved version of the fax machine and the videophone.

This passage is perhaps too dismissive of Google, but it is amazing how one of the technological powerhouses of our era pales in the face of Bell Labs.

Math & Code in Blogger

I use Blogger because of its simplicity and general lack of features. I’ve installed WordPress, and for me it’s a quagmire of tinkering and playing with plugins and themes, all in avoidance of writing. Blogger’s lack of features is itself a feature in the same way that full-screen text editors are a feature: it blocks out lots of potential time wasters.

Having said that, there are a few features I miss on Blogger, namely syntax highlighting and math formatting. Luckily there are a couple of easy javascript libraries that can do the job.

Syntax Highlighting with Google Code Prettify

Google has a javascript library for code syntax. It’s pretty basic in its formatting options, but good enough for me. Most importantly, installation is simple. I simply point to a javascript library hosted by google. Installation requires one line in the template:

<script src='https://google-code-prettify.googlecode.com/svn/loader/run_prettify.js'/>

This add a css class, prettyprint. Use it in a pre tag for a code block. This HTML code:

<pre class="prettyprint">
int main(argc, argv[]) {
    printf("Hello, world!\n");
    return 0;
}
</pre>

is formatted like this:

int main(argc, argv[]) {
    printf("Hello, world!\n");
    return 0;
}

Tag inline code with <code> so that <code class="prettyprint">int i = 0;</code> becomes int i = 0;

Most "normal" (i.e., C-like) languages are recognized with the default. If you like oddball languages, like I do, you might need to specify your language. For example, I specify Scheme when I import the javascript like this:

<script src='https://google-code-prettify.googlecode.com/svn/loader/run_prettify.js?lang=scm'/>

and then again specify the language in side the class

<code class="pretty-print lang-scm">
(define (area-of-disk r) 
  (* 3.14 (* r r)))
</code>

Becomes

(define (area-of-disk r) 
  (* 3.14 (* r r)))

I stick with the default style, which is pretty subtle. If you like more emphatic highlighting, the README has instructions of changing themes and other options like line numbering. It also contains the definitive language list.

Math Formatting with MathJax

I don't do a lot of math, but when I do it's important to me that the notation is clear.MathJax is a javascript library to format math. If you use their CDN, installation is one line in the Blogger template:

<script src='//cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML' type='text/javascript' />

Equations are delimited with \[ \]. Now by entering this:

∖[ x = ∖frac{-b ∖pm ∖sqrt{b^2 - 4ac}} {2a} ∖]

You'll get this:

\[ x = \frac{-b \pm \sqrt{b^2 - 4ac}} {2a} \]

Inline latex is delimited with \( \) so that ∖(e = mc^2 ∖) becomes \( e= mc^2 \).

I like working with MathJax so much, it makes me want to include more posts with math.

Drawbacks

One drawback of this method is that you're entering a lot raw HTML in <code> and <pre> tags. It would be nice

Another drawback is that every page is loading the CSS and JavaScript for code and math on every page, regardless of whether there's any need for it or not.

Finally, while MathJax is well maintained, Google Code Prettify is a bit less active. As I write this, the last commit to the subversion repository was Mon, 03 Mar 2014. I won't be holding my breath for a Swift lexer.

Wednesday, December 24, 2014

Why is the Mac DHCP Client so Awesome?

Once upon a time I worked in Apple support, even before the organization was known as AppleCare. I authored a Knowledge Base article that documented the behavior of the Mac DHCP client in Mac OS 8 and 9. It was an implicit answer to the question, “Why don't Macs behave like the other clients?” At the time that meant, “Why don't they behave like Widows?”

With that background, I’m happy to see the article, Rapid DHCP: Or, how do Macs get on the network so fast? These days, the Mac DHCP client kinda kicks ass.

Friday, December 19, 2014

Privacy Matters

Gizmodo on the Sony Hack:

The most painful stuff in the Sony cache is a doctor shopping for Ritalin. It's an email about trying to get pregnant. It's shit-talking coworkers behind their backs, and people's credit card log-ins. It's literally thousands of Social Security numbers laid bare. It's even the harmless, mundane, trivial stuff that makes up any day's email load that suddenly feels ugly and raw out in the open, a digital Babadook brought to life by a scorched earth cyberattack.

These are people who did nothing wrong. They didn't click on phishing links, or use dumb passwords (or even if they did, they didn't cause this). They just showed up. They sent the same banal workplace emails you send every day, some personal, some not, some thoughtful, some dumb. Even if they didn't have the expectation of full privacy, at most they may have assumed that an IT creeper might flip through their inbox, or that it was being crunched in an NSA server somewhere. For better or worse, we've become inured to small, anonymous violations. What happened to Sony Pictures employees, though, is public. And it is total.

The next time you hear about the death of privacy, or some idiot scolds you by saying, “If you have something that you don't want anyone to know, maybe you shouldn't be doing it in the first place,” remember this. There's lot of little niggling things we do every day that need to stay private just to keep our daily lives going.

Stanford Algorithms Course

Stanford is offering their Algorithms I course again (via Coursera): Algorithms: Design and Analysis, Part 1

I took it the first time it was offered, and it was a fantastic course. They take the "analysis" part seriously, covering big-O notation fairly rigorously and covering the Master Method. It's fairly mathematical. I ran into problems when we covered probabilistic algorithms, as I never really studied probability mathematically. It will take a lot of your time, but if you can devote enough time to it, it will be worth it.

Wednesday, December 17, 2014

Blogger Template Formats

I looked into the Blogger template syntax, wondering if I could make a simple template on my own, using Bootstrap or something like that. Google, it turns out, has little documentation. They have a few docs in their support section, but nothing like developer documentation. This one, for example, covers two tags: b:section and b:widget. I can see others in the template: b:loop, b:if, b:else. I can make a good guess about what these do, but I shouldn't have to.

The template is a standard XML document with some blogger-specific tags. Seem like a good system. But what tags are available? What do they mean? Normally, the XML declaration has a source for such questions. Here's the tag from my current template.

<html b:version='2' class='v2' expr:dir='data:blog.languageDirection' xmlns='http://www.w3.org/1999/xhtml' xmlns:b='http://www.google.com/2005/gml/b' xmlns:data='http://www.google.com/2005/gml/data' xmlns:expr='http://www.google.com/2005/gml/expr'>

Guess what? All those links are broken. So maybe I won't put any more time into this after all. It hardly inspires confidence. I remember what happened with the last Google product I really liked. It's a shame, because I like Blogger. It's one case where my interests align pretty well with Google's.

Later, that same decade…

A while back I started this blog to keep track of my progress through SICP. Then I put that project on hold. The problem with putting a project like that on hold is that you forget your progress, then have to backtrack. That kills the fun. I guess I'm saying that I abandoned that project. At the least, you shouldn't expect any more SICP posts here. If I start it up again, consider it a bonus.

It seems a shame to kill the blog just because I'm no longer working through SICP. So I'm going to start back, with a much less focus. I'll probably stick to the geekier end of things, but I'm no longer using this exclusively for study notes.

Monday, September 12, 2011

I'm moving my blog and code over to GitHub. I like the way that lets me keep all my blog posts, essays, and code in a single versioned repository. It's also easier to author and edit. Please visit the new site.

Thursday, July 7, 2011

Exercises 2.38 & 2.39: fold-left and fold-right

These exercises didn't take too long to complete, but I'm still not sure I understand the implications of it, so I'm going to work through it here.

The accumulate procedure in the text is the same as a Scheme procedure called fold-right. There's a similar procedure called fold-left that can be defined like this:

(define (fold-left op initial sequence)
  (define (iter result rest)
    (if (null? rest)
        result
        (iter (op result (car rest))
              (cdr rest))))
  (iter initial sequence))

The first exercise has you work through some sample expressions to see how the two differ. Here are my expansions, using the substitution model we've been using in the text so far.

(fold-right / 1 (list 1 2 3))
(/ 1 (fold-right / 1 (list 2 3)))
(/ 1 (/ 2 (/ 3 (fold-right / 1 (list)))))
(/ 1 (/ 2 (/ 3 1)))
(/ 1 (/ 2 3))
(/ 1 2/3)
3/2


(fold-left / 1 (list 1 2 3))
(iter 1 (list 1 2 3))
(iter (/ 1 1) (list 2 3))
(iter 1 (list 2 3))
(iter (/ 1 2) (list 3))
(iter 1/2 (list 3))
(iter (/ 1/2 3) (list))
(iter 1/6 (list))
1/6

;; or:
(/ (/ (/ 1 1) 2) 3)
Just in case having the initial parameter the same as the first term of the list (i.e., the two 1's) is hiding an error, I'm going to do it again with my own list where every number is unique.
(fold-right / 1 (list 2 3 4))
(/ 2 (fold-right / 1 (list 3 4)))
(/ 2 (/ 3 (/ 4 (fold-right / 1 (list)))))
(/ 2 (/ 3 (/ 4 1)))
(/ 2 (/ 3 4))
(/ 2 3/4)
8/3


(fold-left / 1 (list 2 3 4))
(iter 1 (list 2 3 4))
(iter (/ 1 2) (list 3 4))
(iter 1/2 (list 3 44))
(iter (/ 1/2 3) (list 4))
(iter 1/6 (list 4))
(iter (/ 1/6 4) (list))
(iter 1/24 (list))
1/24

;; or:
(/ (/ (/ 1 2) 3) 4)

With infix notation I could describe these as:

(((1 ÷ 2) ÷ 3) ÷ 4) for fold-left and

(2 ÷ (3 ÷ (4 ÷ 1))) for fold-right.

For the mathematical operators above, fold-left conforms to what you would get if you were to work your way through the list from left to right with a calculator, as 1 ÷ 2 ÷ 3 ÷ 4 =.

Moving on to the list operator:

;;fold-right
(fold-right list nil (list 1 2 3))
(list 1 (fold-right list nil (list 2 3))
(list 1 (list 2 (fold-right list nil (list 3))))
(list 1 (list 2 (list 3 (fold-right list nil (list)))))
(list 1 (list 2 (list 3 '())))
(list 1 (list 2 (3 ())))
(list 1 (2 (3 ())))
(1 (2 (3 ())))

;;fold-left
(fold-left list nil (list 1 2 3))
(iter nil (list 1 2 3))
(iter (list nil 1) (list 2 3))
(iter (() 1) (list 2 3))
(iter (list (() 1) 2) (list 3))
(iter ((() 1) 2) (list 3))
(iter (list ((() 1) 2) 3) (list))
(iter (((() 1) 2) 3) (list))
(((() 1) 2) 3)
;; or:
(list (list (list nil 3) 2) 1)

fold-right seems clear as a recursive process. You take the first item from the list and apply the operator to it and the fold-right of the remainder of the list. One confusing thing is that the initial term provided to the procedure feels like a terminal term when I work through the substitution: it's the last thing the operator works on when it reaches the end of the list. It is, I suppose, the first thing the get evaluated in the chain of deferred recursive expressions.

I have a harder time describing fold-left. As noted above, it feels natural with mathematical operators and conforms to what I get from a calculator. As explained in this Stack Exchange question, these operators are left-associative, so fold-left feels natural. With other operators (like cons), fold-right starts feeling more natural. If your operator is commutative, like addition and multiplication, your result will be the same with either fold-left or fold-right.

Exercise 2.39 has you define reverse in terms of both fold-left and fold-right. First, fold-right:

Given a list (1 2 3), you need an operator (I'll call it op) such that

(op 1 (op 2 (op 3 nil)))

results in

(3 2 1)

(define (reverse sequence)
  (fold-right (lambda (x y) (append y (list x))) nil sequence))

For fold-left, you need an operator such that, given a list (1 2 3),

(op (op (op nil 3) 2) 1)

Evaluates to

(3 2 1)

(define (reverse sequence)
  (fold-left (lambda (x y) (cons y x)) nil sequence))

It was easiest to look at the innermost expression and figure out a way to build the term I want.

Working through these definitely helped my understanding, but it would take a lot more practice before either fold-left or fold-right feels natural, and before it's immediately obvious whether a left fold or right fold is the best fit for a given operation.

Friday, July 1, 2011

Sequences as Conventional Interfaces

map can be combined with other procedures accumulate and filter to build up a conventional way of dealing with sequenced data. Two examples from the text:

Example 1 This program takes a tree, goes through it to find all leaves containing an odd number, and squares those odd leaves, and adds the squares together.

(define (sum-odd-squares tree)
  (cond ((null? tree) 0)
        ((not (pair? tree))
         (if (odd? tree) (square tree) 0))
        (else (+ (sum-odd-squares (car tree))
                 (sum-odd-squares (cdr tree))))))

Program 2 This procedure takes a number n and produces a list of even Fibonacci numbers equal to or less than Fib(n).

(define (even-fibs n)
  (define (next k)
    (if (> k n)
        nil
        (let ((f (fib k)))
          (if (even? f)
              (cons f (next (+ k 1)))
              (next (+ k 1))))))
  (next 0))

The programs don't seem to have a lot in common, but they can be understood like this:

Program 1
Enumerate tree leaves -> Filter odd leaves -> map square procedure -> Accumulate with +

Program 2
Enumerate integers -> map fib procdure -> filter even results -> accumulate with cons.

Seen this way you can abstact out the notions of filtering and accumulating, and the two actually look very similar.

To filter we can define

(define (filter predicate sequence)
  (cond ((null? sequence) nil)
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))

(filter odd? (list 1 2 3 4 5))
;Value: (1 3 5)


and to accumulate

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

(accumulate + 0 (list 1 2 3 4 5))
;Value: 15

(accumulate * 1 (list 1 2 3 4 5))
;Value: 120

(accumulate cons nil (list 1 2 3 4 5))
;Value: (1 2 3 4 5)

We can now define the above procedures in terms of map, filter, and accumulate.
(define (sum-odd-squares tree)
  (accumulate +
              0
              (map square
                   (filter odd?
                           (enumerate-tree tree)))))

(define (even-fibs n)
  (accumulate cons
              nil
              (filter even?
                      (map fib
                           (enumerate-interval 0 n)))))

Monday, June 27, 2011

Mapping Over Lists and Trees

The procedure map takes a procedure and a list, applies the procedure to each element of the list, and returns a list of the results. One way to define map could be

(define (map proc items)
  (if (null? items)
      nil
      (cons (proc (car items))
            (map proc (cdr items)))))

(map square (list 1 2 3 4))
;; (1 4 9)
You can also pass anonymous functions with lambda:
(map (lambda (x) (* x 2)) (list 1 2 3))
;Value 7: (2 4 6)
Then use this for more general procedures.
(define (scale-list items factor)
  (map (lambda (x) (* x factor))
       items))

(scale-list (list 1 2 3) 10)
;Value 8: (10 20 30)
You can use recursion to map over trees. Check for leaves as the terminating condition.
(define (scale-tree tree factor)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (scale-tree sub-tree factor)
             (* sub-tree factor)))
       tree))

(scale-tree (list 1 2 (list 4 5) 5) 10)

;Value 15: (10 20 (40 50) 50)

The built-in map is more general. If the procedure passed in takes multiple arguments, you can also supply multiple lists. The procedure is applied to all the first elements of the lists, then all the second elements of the list, and so on.
(map + (list 1 2 3 4) (list 10 20 30 40))
;Value 3: (11 22 33 44)

Exercise 2.30 Implement square-tree both directly and by using map and recursion.

;;Direct implementation
(define (square-tree tree)
  (cond ((null? tree) nil)
        ((not (pair? (car tree))) (cons (square (car tree))
                                        (square-tree (cdr tree))))
        (else (cons (square-tree (car tree))
                    (square-tree (cdr tree))))))

;;Using map
(define (square-tree tree)
  (map (lambda (x)
  (if (pair? x)
      (square-tree x)
      (square x)))
       tree))
The version using map is much shorter and easier to grok.

Exercise 2.31 Abstract previous exercise to use a procedure tree-map.

(define (tree-map proc tree)
  (map (lambda (x)
         (if (pair? x)
         (tree-map proc x)
         (proc x)))
   tree))

(define (square-tree tree) (tree-map square tree))

Friday, June 24, 2011

Return

I haven't posted in a while for a few reasons. One was that I needed to rest my brain after wrestling with the Church numerals exercise. When I came back to SICP, I worked through the "extended exercise" on interval arithmetic. I found that stupefyingly dull. Exercise 2.11 did me in. It involved building a complicated system of nested condition-checking. It reminded me of the CS courses I took in school that sapped my will to code. That's perhaps a bit harsh, but it did feel like a pedestrian exercise after the eye-opening new ideas that preceded it. So I bailed on the section and moved on to Section 2.2.

I also decided to take a different tack on my posts. If I cruise through an exercise without much difficulty, I'm not going to document it here. The Scheme Wiki has a good set of solutions if that's what you're looking for. Instead, I'm going to document the major points that I need to reiterate to fully digest, or any sections that I find difficult to grasp. I've worked through much of Chapter 2, so I should have more posts up. I need to review accumulation, folding, the picture language.

Monday, May 9, 2011

Exercise 2.6: Church Numerals

Exercise 2.6 Define one and two directly (not in terms of zero and add-1).

The exercise gives the following definitions of zero and add-1

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

OK. Not that I understand how these represent zero and add-1, because trying to evaluate them just returns a procedure.

zero

;Value 22: #[compound-procedure 22 zero]

(add-1 zero)

;Value 23: #[compound-procedure 23]

Still, I'll play along. I'll use the substitution rules to figure out one and two.

(add-1 zero)
(lambda (f) (lambda (x) (f ((zero f) x))))
(lambda (f) (lambda (x) (f (lambda (x1) x1) x)))
(lambda (f) (lambda (x) (f x)))

(define one
  (lambda (f) (lambda (x) (f x)))

(add-1 one)
(lambda (f) (lambda (x) (f ((one f) x))))
(lambda (f) (lambda (x) (f ((lambda (x) f x) x))))
(lambda (f) (lambda (x) (f (f x))))

(define two
    (lambda (f) (lambda (x) (f (f x))))

At this point i can see a pattern emerge. I'm going to venture a guess that three would look like this:

(define three
    (lambda (f) (lambda (x) (f (f (f x)))))


So I don't really know what I did or how to verify whether its right. A little googling reveals a great page on this exercise by Bill the Lizard. And (surprise!) it looks like my substitutions above came out OK.

Reading over Bill's solution, I realize I forgot to define add. So I try not to look at Bill's solution, and work on my own. I do crib Bill's suggestion on how to test these numbers with inc.

So, I start looking at the pattern closer. I know that

(add zero one)

should result in

(lambda (f) (lambda (x) (f x)))

and that

(add one one)

should result in

(lambda (f) (lambda (x) (f (f x))))

And just to make sure I understand what's going on, I define add-2
(define (add-2 n)
  (lambda (f) (lambda (x) (f (f ((n f) x))))))
This seems to work based on my
inc
test.
(((add-2 zero) inc) 0)

;Value: 2
I have a procedure to increase the value of a number. I need to generalize it so that I can increase it value of a number a b times. As it turns out, this "number" b is a procedure which repeats another procedure. So I'll just apply b to (a f) like this.
(define (add a b)
  (lambda (f)
    (lambda (x)
      (f ((b (a f)) x)))))
This look promising at first, but, until I get to adding two and two.
(((add zero one) inc) 0)

;Value: 1

(((add one one) inc) 0)

;Value: 2

(((add one two) inc) 0)

;Value: 3

(((add two two) inc) 0)

;Value: 5

(((add two zero) inc) 0)

;Value: 1

(((add two one) inc) 0)

;Value: 3

So I played around with it until my head hurt. In the end, I read the end of Bill's article. The final solution is this.
(define (add a b)
  (lambda (f)
    (lambda (x)
      ((b f) ((a f) x)))))
Now that I see it, it makes sense. I need b applications of f to ((a f) x), and the way to do this is with the procedure(b f), which will result in the application of procedure f b times. The repeated application of this procedure should be applied to ((a f) x).

Definitely one of the hardest problems I've encountered. I'll have to do some study on church numbers and come back to it.

Friday, May 6, 2011

Exercise 2.5: Yet another definition of cons, car, cdr

Exercise 2.5. Show that we can represent pairs of nonnegative integers using only numbers and arithmetic operations if we represent the pair a and b as the integer that is the product 2a3b. Give the corresponding definitions of the procedures cons, car, and cdr.
This is possible because any number 2n will not contain 3 as a factor. Similarly, any number 3n will not contain 2 as a factor.

cons is a straightforward application of what the exercise describes.
(define (cons3 a b)
  (* (expt 2 a) (expt 3 b)))

car and cdr just repeatedly divide by 2 (car) or 3 (cdr) until the number no longer divides evenly. Count the number of even divisions, and return the count as the result.
(define (cdr3 c)
  (define (helper x count)
    (if (= 0 (remainder x 3))
        (helper (/ x 3) (+ 1 count))
        count))
  (helper c 0))

(define (car3 c)
  (define (helper x count)
    (if (= 0 (remainder x 2))
        (helper (/ x 2) (+ 1 count))
        count))
  (helper c 0))

;;tests
(car3 (cons3 23 67))
;Value: 23

(cdr3 (cons3 23 67))
;Value: 67

Thursday, May 5, 2011

Exercises 2.1 - 2.4

Exercise 2.1 Define a better version of make-rat that handles both positive and negative arguments. make-rat should normalize the sign so that if the rational number is positive, both the numerator and denominator are positive, and if the rational number is negative, only the numerator is negative.
The main trick in this problem was to get the signs to line up after your number comes through the gcd procedure. I could have redefined gcd to return only a positive number, but that seemed to be cheating. So I came up with the method below which calls make-rat again. I could have added more conditional checking to get the signs to work, but somehow this was the first solution to come to me.

;;;from chapter 1
(define (square x) (* x x))

;;;from section 1.2.5, for Section 2.1.1
(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

;; from section 2.1
(define (numer x) (car x))

(define (denom x) (cdr x))

(define (print-rat x)
  (newline)
  (display (numer x))
  (display "/")
  (display (denom x)))

;; original make-rat
(define (make-rat n d)
  (let ((g (gcd n d)))
    (cons (/ n g) (/ d g))))

;;new, improved make-rat
(define (make-rat n d)
  (let ((g (abs (gcd n d))))
    (cond
     ((and (< n 0) (< d 0)) (make-rat (abs n) (abs d)))
     ((and (> n 0) (< d 0)) (make-rat (- n) (- d)))
     (else (cons (/ n g) (/ d g))))))
Exercise 2.2 Specify a constructor make-point and selectors x-point and y-point that define this representation (of a line segment).
;; Exercise 2.2

(define (make-segment a b) (cons a b))

(define (start-segment a) (car a))

(define (end-segment b) (cdr b))

(define (make-point x y) (cons x y))

(define (x-point p) (car p))

(define (y-point p) (cdr p))

(define (midpoint-segment s)
  (make-point (/ (+ (x-point (start-segment s)) (x-point (end-segment s))) 2)
              (/ (+ (y-point (start-segment s)) (y-point (end-segment s))) 2)))

(define (print-point p)
  (newline)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")"))

;;; test out the procedure

(define s1 (make-point 0 0) (make-point 2 4)

(print-point (midpoing s1))

(1,2)
;Unspecified return value
Exercise 2.3 Implement a representation for rectangles in a plane.
I wasn't sure what I was supposed to provide in term of "abstraction barriers." I decided that was the selectors for the width and height of the rectangles. The first definition of rectangle is defined in terms of two points: the top left and the bottom right. Then I define height and width to calculate those values based on the two points.
;; exercise 2.3
;;first definition
(define (make-rect tl br) (cons tl br))

(define (top-left-rect r) (car r))
(define (bottom-right-rect r) (cdr r))

(define (width-rect r)
    (- (x-point (bottom-right-rect r))
       (x-point (top-left-rect r))))

(define (height-rect r)
    (- (y-point (top-left-rect r))
       (y-point (bottom-right-rect r))))
The second definition of rectangle is defined in terms of an origin point and the size. I use coordinates to represent size, which isn't ideal. The data matches up, but it isn't quite right to talk about the x-point of the width. Still, I didn't think it was necessary to define a new kind of size pair for the purpose of this exercise. Height and width selectors return the values of height and width from the size pair.
;; exercise 2.3

;;second definition
(define (make-rect origin size) (cons origin size))
(define (origin-rect r) (car r))
(define (size-rect r) (cdr r))
(define (width-rect r) (x-point (size-rect r)))
(define (height-rect r) (y-point (size-rect r)))
Finally, calculating area and perimeter in terms of size.
;; these procedures work on either representation of rectangle above
(define (perimeter-rect r) (+ (* 2 (width-rect r)) (* 2 (height-rect r))))
(define (area-rect r) (* (width-rect r) (height-rect r)))
Exercise 2.4 What is the corresponding definition of cdr?
This I just worked through with standard substitution rules until the application became clear.
;;exercise 2.4

(define (cons2 x y)
  (lambda (m) (m x y)))

(define (car2 z)
  (z (lambda (p q) p)))

;;substitution for (car (cons 1 2))

(car (cons 1 2))
(car (lambda (m) (m 1 2)))
((lambda (m) (m 1 2)) (lambda (p q) p))
((lambda (p q) p) 1 2)
(lambda (1 2) 1)
1
;; resulting definition of cdr

(define (cdr2 z)
  (z (lambda (p q) q)))

Wednesday, May 4, 2011

Section 2.1: Intro Data Abstraction

Notes from Book section 2.1 and Youtube lecture 2B.

Compound data. So far we've been operating on numbers for a lack of other data types to work on. This chapter introduces data. The basic datatype in Scheme is the pair.

Make pairs with cons.
(cons x y) -> pair (x, y)
Retrieve the first element with car. Retrieve the second element with cdr.
(car (cons x y)) -> x

(cdr (cons x y)) -> y

This is true for any x and y, even if x and y are themselves pairs. The ability to combine not just primitives (like numbers) but also compound data is called closure. Pairs would be limited an uninteresting if we could only crate them with a limited set of primitive data.

Suppose you have a data type of point, defined as a pair created by cons.
(define (make-point x y) (cons x y))

(define (x-coordinate p) (car p))

(define (y-coordinate p) (cdr p))
You can combine the points into a pair to define the endpoints of a line segment...
(define (make-segment a b) (cons a b))

(define (start-segment s) (car s))

(define (end-segmenet s) (cdr s))
...and then define computations based on the points.
(define (midpoint s)
    (make-point (average (x-coordinate (start-segment))
                         (x-coordinate (end-segment)))
                (average (y-coordinate (start-segment))
                         (y-coordinate (end-segment)))))

This definition also make a layered approach to the problem of lines, something like this:

Segments
------------
make-seg, seg-start, seg-end
------------
Points
------------
make-point, x-coordinate, y-coordinate
------------
Pairs, Numbers

The definition of points could change, and as long as the constructors and accessors make-point, x-coordinate, y-coordinate are updated to match the new definition, the line segment procedures don't need to change.

The pair data structure can be represented as procedures:
(define (cons x y)
    (lambda (pick)
        (cond ((= pick 1) x)
              ((= pick 2) y))))

(define (car z) (z 1))

(define (cdr z) (z 2))
Mind-blowing! There is no data, just procedures. Still, it's a valid representation of pairs because it fulfills the contract

(car (cons a b)) -> a

(cdr (cons a b)) -> b

So in some sense you can build data abstractions without data.