Content from 2008-08

Random Thoughts

posted on 2008-08-25 14:14:44

It's already Fall semester. How messed up is that? I haven't learned near as much as I was hoping to by now. That said, I'm no longer as much of an idiot when it comes to programming. I'm just unlearned. Well, maybe that's what I was before. At any rate, some good fortune has come my way in that department. I'm helping out with a very cool startup related to cloud computing and getting mentored by a guy doing the sort of work I'd be interested in. He also happens to share some of my views on society and education.

I've had lots of financial thoughts lately. It's funny when you realize that you can count on one hand the material things that make you happy and count on the other hand your material needs. Afterwards you should figure out what it really costs you to happily live (barring dependents) and figure out just how money jobs could consequently sustain you that way. Take that, put it in your pipe and smoke it.

Two parting thoughts:

One, this hackernews discussion on the article Deschooling Society is excellent. Someone should make a Facebook note about it and get some OU kids in on the discussion.

Two, Red Hat and Fedora's servers got hacked recently. The situation was resolved before any nastiness could filter downstream. CentOS servers were unaffected though and this makes me wonder if Fedora didn't share infrastructure whether they would've been hacked as well. What's the thought here? Well, it makes me think there's less incentive to attack community distributions and, similarly, community products. I could certainly be wrong. Your thoughts?

Programming in the Debugger

posted on 2008-08-13 19:57:40

There's a quote I recalled reading on the internet and wanted to send to a friend recently but I couldn't find it. I stumbled across it today over on Lambda the Ultimate and am archiving it here due to awesomeness. Lambda the Ultimate is a fantastic community centered around programming languages and there are many great discussions worth reading. This discussion starts off with the aforementioned quote which I'll excerpt here and goes on to discuss dynamism in languages, specifically as it relates to interactivity versus a specific typing discipline. Ready for the awesome quote? Good.

By way of Luke Gorrie over on Lambda the Ultimate:
By way of Joe Marshall in comp.lang.lisp:
Here's an anecdote I heard once about Minsky.  He was showing a
student how to use ITS to write a program. ITS was an unusual
operating system in that the `shell' was the DDT debugger. You ran
programs by loading them into memory and jumping to the entry point.
But you can also just start writing assembly code directly into memory
from the DDT prompt. Minsky started with the null program.
Obviously, it needs an entry point, so he defined a label for that.
He then told the debugger to jump to that label. This immediately
raised an error of there being no code at the jump target. So he
wrote a few lines of code and restarted the jump instruction. This
time it succeeded and the first few instructions were executed. When
the debugger again halted, he looked at the register contents and
wrote a few more lines. Again proceeding from where he left off he
watched the program run the few more instructions. He developed the
entire program by 'debugging' the null program.

Skate 2

posted on 2008-08-13 12:36:30

So, I'm still into skateboarding these days. I don't mention that too much and I don't go skating as much as I'd like but it's true. I originally got into skateboarding because a dear friend twisted my arm to get me to play the original Tony Hawk's Pro Skater video game on the Playstation 1. God...I feel old now. Did I mention I just turned 22 last Wednesday? It didn't hit until I had to fly to Chicago for business the next day though. I was like, "It's August 7th, 2008? OMG WTF!!". Really.

Anyway, Tony Hawk's Pro Skater was awesome. I think what really captured my imagination was flip tricks. Frankly, I didn't know you could do any tricks at all with skateboards except maybe wheelies (manuals in the common parlance). Wheelies were one thing but the fact that people could jump in the air flip the board over under their feet and land and keep going just surprised me. Neversoft (the developer's of the Tony Hawk's series of games) produced a few more good titles and then had a sharp turn downhill. They were fun games but I worried another good skateboarding game wouldn't get made. Then EA (of all developers) came along last year and released skate. It was beautiful. In so much as you can get a skateboarding game right, they got it right. There's room for nitpicking but the nits are utterly trivial.

And EA is a big conglomerate. You don't expect them to do something that's true to skateboarding and it's culture. You expect cash-in, thanks for your money type work but skate was quality and I was converted. Skate 2 was recently announced and is, by all appearances, going to be fantastic but there's no official word on a release date. It flits from November 08 to March 09 so quickly I could punch a baby in frustration. Maybe not.

Anyway, they're naturally adding more professional skateboarders and companies to the lineup in the game but you can't add everybody. To that effect, a friend and I decided to figure that problem out. The solution, of course, is to cap the game at 50 riders. A representative sample of the world's top skateboarders, right? Well, that's what I figure. To keep the sample somewhat broad, choose 16 of the major board companies and restrict yourself to selecting 3 skateboarders from any given company (that makes 48) with room for two exception companies from which you'll pick 4 riders (50).

I selected all professionals (to my knowledge) and by only choosing pros on board companies I've effectively ruled that if you don't have a pro board you're not pro (sorry, Javier Sarmiento. you know I love you). This could be adjusted to allow for rippers who lack a board sponsor like Javier (inexplicable!) or to allow ams. Obviously, the roster will reflect my friend and I's biases circa 2008. To be fair, I've been bad at keeping up with skateboard news over the last two years (Dude! Boulala's in jail? The Firm shut down? Damn!) but I saw somewhere north of 70% of team videos (shop and indie vids are out) and magazine videos from 2002-2006. Alright, 16 companies, 50 riders. Go!

Alien Workshop: Dill, Kirchart, Saari
Almost: Haslam, Lutzka, Mullen
Baker: Kennedy, Reynolds, Romero
Blind: Brown, Creager, Laitala
Cliche: Brezinski, Nuske, Puig
Chocolate: Anderson, Calloway, Johnson
Darkstar: Gagnon, Machnau, Thomas
Element: Barbee, Stanton, Tim Tim
Enjoi: Barletta, Foster, Hsu
Flip: Appleyard, Burnquist, Glifberg, Rowley ; calling a 4
Girl: Anderson, Carroll, Koston, McCrank ; calling another 4sie
Habitat: Baxter-Neal, Getz, Janoski
Plan B: Duffy, Gallant, Way
Santa Cruz: Carolino, De Gros, Marfaing
Toy Machine: Bucchieri, Harmony, Marks
Zero: Cole, Rattray, Thomas

SICP Section 2.1

posted on 2008-08-07 20:54:02

It's taken far too long to post this up and the last four problems remain unfinished. That said, I want to get more of the solutions I've worked written up and I shouldn't have waited this long in the first place. With any luck Section 2.2 will follow within a week. I'm around half done with it and you can see some solutions here.



Resources:
Read: Chapter 2 through Section 2.1
Watch: Lecture 2-b
Checked against: Eli Bendersky's Blog, SICP Wiki, Ken Dyck's Solutions, Theloserblog, Wfasim's Solutions and the Scheme Wiki and Personal Wiki solutions listed here.

SICP Notes and Exercises:

Notes

Quotes

Exercises
2.1:

(define (make-rat n d)
(let ((g (gcd n d)))
(if (positive? (/ n d))
(cons (abs (/ n g)) (abs (/ d g)))
(cons (- (/ n g)) (abs (/ d g))))))
;Value: make-rat


2.2:

(define (make-point x y)
(cons x y))
;Value: make-point

(define (x-point point)
(car point))
;Value: x-point

(define (y-point point)
(cdr point))
;Value: y-point

(define (start-segment segment)
(car segment))
;Value: start-segment

(define (end-segment segment)
(cdr segment))
;Value: end-segment

(define (make-segment p1 p2)
(cons p1 p2))
;Value: make-segment

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

(define (midpoint-segment s)
(make-point (average (x-point (start-segment s))
(x-point (end-segment s)))
(average (y-point (start-segment s))
(y-point (end-segment s)))))
;Value: midpoint-segment


This is really interesting to me. I feel like midpoint-segment should be expressible in 2 or 4 lines of code but I can't think of a way to elegantly do that with lets or function composition. The problem is each time you're composing different sets of functions. Without defining multiple lets or compositions it doesn't compress and if you do you lose your LOC gains anyway. I've decided this definition is sufficiently succinct.

2.3:

;;representation 1 - procedure based, working by magic:
(define (rect-area r)
(* (length r) (width r)))
;Value: rect-area

(define (rect-perimeter r)
(* 2 (+ (length r) (width r))))
;Value: rect-perimeter

(define (make-rect top-left bottom-right)
(cons top-left bottom-right))
;Value: make-rect

(define (length r)
(- (y-point (car r)) (y-point (cdr r))))
;Value: length

(define (width r)
(- (x-point (cdr r)) (x-point (car r))))
;Value: width

;;representation 2 - not procedure based, working by reality:
(define (make-rect top bottom)
(cons top bottom))
;Value: make-rect

(define (rect-top r)
(car r))
;Value: rect-top

(define (rect-bottom r)
(cdr r))
;Value: rect-bottom

(define (rect-left r)
(make-segment (start-segment top)
(start-segment bottom)))
;Value: rect-left

(define (rect-right r)
(make-segment (end-segment top)
(end-segment bottom)))
;Value: rect-right

(define (length r)
(- (y-point (start-segment (rect-top r)))
(y-point (start-segment (rect-bottom r)))))
;Value: length

(define (width r)
(- (x-point (end-segment (rect-top r)))
(x-point (start-segment (rect-top r)))))
;Value: width


What working by magic really seems to do is make the cruft that's unnecessary to your implementation obvious.

2.4:

(define (cons x y)
(lambda (m) (m x y)))
;Value: cons

(define (car z)
(z (lambda (p q) p)))
;Value: car

(define (cdr z)
(z (lambda (p q) q)))
;Value: cdr


Wow. Just wow.

2.5:

(define (cons a b)
(* (expt 2 a) (expt 3 b)))
;Value: cons

(define (what-exponent x y)
(define (exp-iter count)
(if (= (modulo y (expt x count)) 0)
(exp-iter (+ count 1))
(- count 1)))
(exp-iter 1))
;Value: what-exponent

(define (car x)
(what-exponent 2 x))
;Value: car

(define (cdr x)
(what-exponent 3 x))
;Value: cdr


This isn't quite as evil as the problem description makes it sound.

2.6:
Whew boy. Here goes...


(define zero (lambda (f) (lambda (x) x)))
;Value: zero

(define (add-1 n)
(lambda (f) (lambda (x) (f ((n f) x)))))
;Value: add-1

(add-1 zero)
(lambda (f) (lambda (x) (f ((zero f) x))))
(lambda (f) (lambda (x) (f x))) ;; this was the difficult step for me. why? i couldn't understand how ((zero f) x) got worked down to x. I knew that the identity function was what eventually got returned but I figured it received f as it's argument. The trick was recalling that f gets passed into a function which does NOTHING WITH F and returns the identity function anyway. (zero f) reduces to the identity function because of the first lambda in zero that just throws it's argument away. Hence, you have (identity x) which is just x and leaves this result as one. somewhat sadly, formatting my code so that the substitution wasn't all on one line also could've made the difference and saved me a week or so.

(define one (lambda (f) (lambda (x) (f x))))
;Value: one

(add-1 one)
(lambda (f) (lambda (x) (f ((one f) x))));; again the f arg is thrown away and x is put into the second lambda to give...
(lambda (f) (lambda (x) (f (f x))))

(define two (lambda (f) (lambda (x) (f (f x)))))
;Value: two

;;clearly we're adding an application of f each time we add one. for example...
((two square) 5)
;Value: 625
;; which is the square of the square of 5 (* 25 25)

;;now i'm supposed to define an addition function which should perform like so:
(add one two)
(add (lambda (f) (lambda (x) (f x)))
(lambda (f) (lambda (x) (f (f x)))))
...
(lambda (f) (lambda (x) (f (f (f x)))))
;;and then allow us to do this
(((add one two) square) 5)
(square (square (square 5)))
;Value: 390625

;;maybe the hard part of this problem is holding multiple levels of evaluation in your head at the same time. anyway...
;;it seems like what we really want to do is feed the f chains into each other somehow...p

(define (add a b)
(lambda (f) (lambda (x) ((a f) (b f)) x)))
;Value: add

;;this is tempting but wrong. i realized you had to pass the f in to make sure you got the correct repeated calls but missed that if you passed (b f) into the resulting function you were passing a procedure instead of a value.

(define (add a b)
(lambda (f) (lambda (x) ((a f) ((b f) x)))))
;Value: add

(add one two)
(lambda (f) (lambda (x) ((one f) ((two f) x))))
(lambda (f) (lambda (x) ((one f)
((lambda (x) (f (f x))) x))))
(lambda (f) (lambda (x)
(lambda (x) ((f x)
(lambda (x) (f (f x)) x)))
(lambda (f) (lambda (x) (f (f (f x)))))

;;you want to hear what's really gross? i found that this worked for odd numbers but not even numbers and tried unsuccessfully to figure out what was wrong for an hour before re-evaluating my definitions for one and two and seeing it "just work".

(((add one two) square) 5)

(define (test churchnum)
(define (inc x)
(+ x 1))
((churchnum inc) 0))
;Value: test

(test (add one two))
;Value: 3

;;it's sort of insulting that after writing all that code you realize
you just implemented a fancy lambda version of repeated for
functions/church numerals.

;;proving above point:
(define (compose f g)
(lambda (x) (f (g x))))
;Value: compose

(define (repeated f n)
(if (= n 1)
f
(compose f (repeated f (- n 1)))))
;Value: repeated

(define (add a b)
(lambda (f) (repeated f (+ a b))))
;Value: add

;;of course, this pretends that church numerals are integers but...you get the idea.


This may have been the hardest problem I encountered thus far and I definitely had to peek at the way other people started solving the problem to get my own ideas flowing in the right direction.

2.7:

(define (lower-bound i)
(car i))
;Value: lower-bound

(define (upper-bound i)
(cdr i))
;Value: upper-bound


2.8:

(define (sub-interval x y)
(let ((p1 (- (lower-bound x) (lower-bound y)))
(p2 (- (lower-bound x) (upper-bound y)))
(p3 (- (upper-bound x) (lower-bound y)))
(p4 (- (upper-bound x) (upper-bound y))))
(make-interval (min p1 p2 p3 p4)
(max p1 p2 p3 p4))))
;Value: sub-interval


Similiar to the addition function the maximum value the difference could be is that of the furthest upper and lower bound and the minimum difference is that of the closest upper and lower bound. This seems to be the best way to test for that.

2.9:

(define (width-interval x)
(/ (- (upper-bound x) (lower-bound x))
2))
;Value: width-interval

(width-interval (mul-interval inter1 inter2))
;Value: 24

(width-interval (div-interval inter1 inter2))
;Value: .5333333333333334

(width-interval (add-interval inter1 inter2))
;Value: 4

(width-interval (sub-interval inter1 inter2))
;Value: 4


Observe that the width of the interval which is the difference between inter1 and inter 2 is identical to the width of the interval which is the sum of inter1 and inter2.
This fact indicates that the width of summed or subtracted intervals is a function of the width of their source intervals. You can clearly see that the width of the intervals produced by multiplying or dividing inter1 and inter2 do not share this trait. Thus, the width of multiplied or divided intervals is not a function of their source intervals alone.

2.10:

(define (div-interval x y)
(if (<= (or (upper-bound y) (lower-bound y)) 0)
(error "Cannot divide by an interval that spans zero." y)
(mul-interval x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y))))))
;Value: div-interval


This fixes the issue of dividing by zero in the software by simply not allowing intervals to drop below zero. Whether intervals that "span" zero should be allowed is up for debate.

2.11:

(define (mul-interval x y) ;;even with lets this is ugly. i object!
(let ((a (lower-bound x))
(b (upper-bound x))
(c (lower-bound y))
(d (upper-bonud y)))
(cond ((and (> a 0) (> b 0) (> c 0) (> d 0))
(make-interval (* a c) (* b d)))
((and (> a 0) (> b 0) (< c 0) (> d 0))
(make-interval (* b c) (* b d)))
((and (< a 0) (> b 0) (> c 0) (> d 0))
(make-interval (* a d) (* b d)))
((and (< a 0) (> b 0) (< c 0) (< d 0))
(make-interval (* b d) (* a d)))
((and (< a 0) (< b 0) (< c 0) (> d 0))
(make-interval (* b d) (* b c)))
((and (< a 0) (< b 0) (< c 0) (< d 0))
(make-interval (* a c) (* b d)))
((or (and (> a 0) (> b 0) (< c 0) (< d 0))
(and (< a 0) (< b 0) (> c 0) (> d 0)))
(make-interval (* b d) (* a c)))
(else (make-interval (min (* a d) (* b c))
(max (* a c) (* b d)))))))
;Value: mul-interval


Eww. Gross.

2.12:

(define (make-center-percent center tolerance)
(make-center-width center (* (/ tolerance 100) center)))
;Value: make-center-percent

(define (percent i)
(* (/ (width i) (center i)) 100))
;Value: percent

(percent (make-center-percent 8 5))
;Value: 5


It's not much and I plan on updating and expanding on this but it's done for now.

One Week Worth of Tricks

posted on 2008-08-03 17:18:28

In the course of migrating my webserver to a new box this week I learned two useful tricks. They may or may not prove useful for anybody else but I think they're fun so here we go.

One, SSH Tunnels. SSH Tunnels are useful if you ever need to surf the web securely and you're on public or untrusted wireless (say at Starbucks) or when a website is blocked by a firewall and you need to access it.

SSH Tunnels are actually quite easy. Assuming you've got ssh setup on the remote server and an account at that server all you have to do is run "ssh -D 8080 username@website-or-ip-address.com". Once you're logged in, open the Preferences for your web browser. This example will use Firefox 3. Go to Edit->Preferences, then the Advanced section, the Network tab and click Settings. Click the "Manual Proxy Configuration" radio button and under SOCKS Host put "localhost" and set the port to 8080. That's it! Surf away.

Two, resetting your wordpress admin account password. This is useful if you're such an idiot that you forget to change the random password that's initially on the account after you install wordpress. It assumes you have an ssh account to the server hosting the blog as well as access to the database tables for the blog. SSH into the server and run "echo -n your-new-password | md5sum". Copy that down and hang on to it. Then run "mysql -u user-with-access -p". Then run the following commands:

USE wordpress-database-name;
UPDATE wp_users SET user_pass="md5-you-wrote-down"
WHERE user_login="admin";

Check to make sure it went through with "SELECT user_pass FROM wp_users;" then type "exit".

Yep. It's good stuff. That's all I've got for now. I'm hoping to post up some mostly finished SICP sections in the next few days. If I'm lucky I'll even write something intelligent about education.

Damn Servers...

posted on 2008-08-01 12:59:51

It's been a good while since I posted last. After meaning to do it for months, I've finally migrated to a new web server. I'm self-hosting so I have no one to yell at about everything taking so long but myself. At any rate, I've migrated my Desktop, Server and Laptop from Ubuntu Linux to the custom Arch Linux build I've been working on lately. Some old links in old posts are broken at the moment but I'm hoping to repair them in the coming weeks.

For now, I'm just glad this thing is back up and functioning after the week of chaos. I'm still committing code as regularly as I can and for the first time in a long time Redline Radio is live again as well. Let me know if you're interested in getting access. We will now return to the regular posting schedule. :-)

Unless otherwise credited all material Creative Commons License by Brit Butler