Fricka Fracka

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.

Pages