Content from 2008-04

Moving Out
posted on 2008-04-28 13:44:32
Briefly, I just wanted to mention for those that don't know that I'm moving into a new house later this week. I'll be living with 4 of my friends (Ben, Teresa, Lizzi, and Amy) less than a mile from Oglethorpe University and I'm quite excited about it. Ben and I are sharing a bedroom in the basement and the girls are upstairs. I'll also get to take Marta in to work. Take that gas prices! Anyway, organizing for the move and dealing with taxes has deterred my programming progress somewhat. Of course, my own laziness is always a factor but I promise there will be more code soon.

Other than that I was wondering if anyone was subscribed to this blog via feed (RSS or Atom) and if so what Feed Reader they used (Google Reader, RSSOwl, etc)? What's the story people?
Setting up a Mercurial VCS on Ubuntu
posted on 2008-04-22 17:47:37
I've been meaning to set up a Version Control System for a long time now. VCS as a concept has been around for a while but recently a new paradigm in VCS called DVCS (for distributed version control system) has emerged. This new paradigm has cured or at least mitigated the warts of the old "centralized" version control systems and brought new benefits. The thing is there hadn't been a dominant VCS up until now and though some would argue to the contrary I would claim there still isn't. This article strives not to be concerned with the choice of a DVCS. The truth if you choose any of the 4 relatively high-profile DVCS systems that exist today (darcs, bazaar, mercurial, or git) you'll be able to migrate between any of them later without too much difficulty if you change your mind. I was initially leaning towards bazaar or git but eventually settled on (and am thus far quite happy with) mercurial. If you must know some of my reasoning I find that Dave Dribin has captured something close to my opinions.

So, the three things I'd like to cover in this article are mostly covered in two or so places on the mercurial site. I thought I'd group it all together here for simplicity and future reference. The three things I'll be covering are the initial setup including installation and repository creation, making that repository accessible via web browser through a cgi script, and then setting up some authentication to allow you to push changes over HTTP. Let's get started!

Initial Setup
Installation of the software is really straightforward on Ubuntu (see the mercurial site for other installs). Just run
sudo apt-get install mercurial and you're done. You'll have to set one thing in your configuration file before you can make your repository. Insert the following in ~/.hgrc with nano:

[ui]
your_username = FirstName LastName


Your next step of course will be to create a repository. For this, I assume you have some code you'd like stored. I make no claims about what will happen if you try creating an empty repository. It is also worth noting that mercurial tracks content, not files, so it won't carry empty directories. You can work around this on Linux by dropping a hidden file in the directory like so: touch dirname/.hidden.
Once you've done that navigate to the directory you'd like the repo to be in and run the following commands:

hg init
hg add
hg commit


This should bring up nano for you to enter a commit message into describing what changes you're making. Type in a message, save and exit nano. Now you can check and see if this was successful with hg log. If there are no changes listed or exiting nano generated an error you should check your file permissions and see if entering the [ui] information in another config file (perhaps /etc/mercurial/hgrc) fixes the problem.

Setting up the Web Server
I'm assuming that you already have a working repo (naturally) and an install of apache at this point. If you don't have the apache install try running sudo apt-get install apache2. There should be a copy of the cgi script mercurial uses in /usr/share/doc/mercurial/examples/. Copy that to /var/www/cgi-hg/ and rename it index.cgi, then open it up with nano. Around the the third to last line (under def make_web_app) you should see something like:

return hgweb("/path/to/your/repo", "Your Repo Description Here")


Fill in those values with your information but preserving the quotation marks. Also make sure to remove the comments (#s) before import os and import sys. Finally, be sure to run sudo chmod a+x index.cgi on the file so that Apache can execute it. You'll need to edit your apache config file so fire up nano again and open /etc/apache2/apache2.conf to insert the following:

Alias /code /var/www/cgi-hg

DirectoryIndex index.cgi
AddHandler cgi-script .cgi
Options ExecCGI
Order allow,deny
Allow from all


Finally, restart the server with sudo /etc/init.d/apache2 restart and try navigating your web browser to yourdomain.com/code.

Adding Push Support
Use nano to open your_repo/.hg/hgrc (not ~/.hgrc) again. This time we're putting in the server configuration and it should look something like this:

[web]
allow_push = your_username
push_ssl = false


Now you'll have to set up a file to hold the passwords for the users you want to allow to upload changes. To create it and add the first user and password run sudo htpasswd -c /etc/apache2/hg.pass your_username but make sure to omit the -c argument when adding new users in the future or the file will be overwritten. Then you'll need to set up apache to check this information. Open /etc/apache2/conf.d/hg.conf in nano and add the following:


AuthUserFile /etc/apache2/hg.pass
AuthGroupFile /dev/null
AuthName "Your Repository Name"
AuthType Basic

Require valid-user



Save and exit nano. You'll need to change the permissions on the repo tree to allow apache to write to it so run sudo chown -R www-data:www-data /path/to/your/repo and then restart the apache server again. That's it! Time to test it...

***BONUS ROUND***
To test your setup, go to another computer and use apt-get to install mercurial and set your username in the ~/.hgrc. Then run hg clone http://yourdomain.com/code and you should see mercurial make a clone off of your server. Open one of the cloned files and make a small edit or add some new files, whatever you like. When you're done run hg add and hg commit remembering to add commit messages. If you need to delete a file do it through hg remove filename. Finally, try pushing your changes back to the server by running hg push http://yourdomain.com/code. You should get asked for a username and password and if you give valid login information your changes should push through. Now navigate to http://yourdomain.com/code in the browser and see if the changes show up. If they do, you're off to the races.
Topping off the day
posted on 2008-04-22 04:59:45

Okay, so today has been pretty excellent. I've really gotten a good bit done. I fixed my problem with MIT-Scheme on Hardy by just compiling a new version from source, I figured out how to get Emacs to behave like edwin when evaluating s-expressions (at least with MIT-Scheme) and I tidied up the first two SICP entries with 1.3 left for tomorrow. Finally, I installed a revision control server and moved all my code into it.


I'm really pleased about it because I've been meaning to do it forever. You may remember me babbling on about "git". That was what I initially intended to use as my RCS but I settled on mercurial and I'm quite taken with it. At any rate, to see the fruits of my labor just navigate to the new code section of my website. You can see the two different changesets I've uploaded so far and browse through the files by clicking the "manifest" button at the top, then going to books, then sicp, then chapter01. I'll do a more thorough writeup tomorrow. Hope your days were as joyful and productive.

Emacs and MIT-Scheme on Hardy
posted on 2008-04-21 17:55:30

Okay, quick update. The feature I'm missing from edwin has a name and that name is "Scheme Interaction Mode". This feature is provided in Emacs by using xscheme.el. Just replace (require 'quack) with (require 'xscheme) in your .emacs file. Unfortunately, xscheme only works with MIT-Scheme so as far as I can tell there isn't a general purpose Scheme Interaction Mode for Emacs that works across Schemes. I'll dig around more about that. In the mean time, I got MIT-Scheme to work on Hardy by compiling from the portable C on their website as described here. It took over an hour though. It's not a solution I'm too pleased about and half makes me want to downgrade to Gutsy or switch to a distro that has support for MIT-Scheme altogether. At any rate, more on all this down the line.

Quick Emacs Question
posted on 2008-04-21 04:01:58
Dear Interwebs,

I've gotten rather accustomed to Edwin as I've worked my way through SICP. Eventually I'll want to use a different scheme so I'll have to switch to Emacs. I've been working on that lately but there's one thing holding me back that I can't find a solution to anywhere. I've got quack installed and really like the edwin behavior of C-x C-e. That is, when I evaluate an S-Expression I want it to be evaluated on a REPL in the background and the resulting value or error information dumped into the text editing buffer. I do not want a REPL to show up with that information in a new frame. Please, Emacs folk: Help.
Spontaneous Thursday Song Post
posted on 2008-04-17 19:05:04
I'm in Chicago on business today but I'm in a short lull so I thought I'd post a Radiohead song I've really been enjoying today. This song is fantastic and it has what seem like references to the Odyssey in it but I'm not sure what I'd say the song is actually about. Your thoughts?

Radiohead - There There (The Boney King Of Nowhere)
Found at skreemr.com


Potential ramblings on Obama, the Fed, SICP exercise 2.6 (Church Encoding), and more headed your way soon.
A Morning Repose
posted on 2008-04-16 14:08:39
This is a Czeslaw Milosz poem that should have found it's way here a long time ago. It's called Preparation.

Still one more year of preparation.
Tomorrow at the latest I’ll start working on a great book
In which my century will appear as it really was.
The sun will rise over the righteous and the wicked.
Springs and autumns will unerringly return.
In a wet thicket a thrush will build his nest lined with clay
And foxes will learn their foxy natures.

And that will be the subject, with addenda. Thus: armies
Running across frozen plains, shouting a curse
In a many-voiced chorus; the cannon of a tank
Growing immense at the corner of a street; the ride at dusk
Into a camp with watchtowers and barbed wire.

No, it won’t happen tomorrow. In five or ten years.
I still think too much about the mothers
And ask what is a man born of woman.
He curls himself up and protects his head
While he is kicked by heavy boots; on fire and running,
He burns with a bright flame; a bulldozer sweeps him into a clay pit.
Her child. Embracing a teddy bear. Conceived in ecstasy.

I haven’t learned yet to speak as I should, calmly.
Setting up a MoinMoin Wiki on Ubuntu
posted on 2008-04-15 17:55:23
I had a bit of trouble with one or two things setting this up at work last week so here's a report from my side of the IT world for anyone who is looking to do this.

1) Don't apt-get moinmoin.
2) You will create a specific instance for your wiki separate from the base install. This is explained below.

Okay. So, first things first. Check to see if python is installed by running this on the command line:
python -v

then wget the tar from moinmoin:
wget http://static.moinmo.in/files/moin-1.6.2.tar.gz

extract it:
tar zxvf moin-1.6.2.tar.gz

and then run:
sudo python setup.py install --prefix='/usr/local' --record=install.log

This will get a basic install up and running. Now you need to create a wiki instance. You can create one wherever you like but I'd put it in /var/www/YOURWIKI or whatever you'd like to call it. The moinmoin folks have even created a handy script to take most of the work out of your hands and make sure the permissions are right. Grab and read that, decide where you'd like the files to go and then:

sudo ./createinstance.sh /var/www/YOURWIKI
sudo mkdir /var/www/YOURWIKI/cgi-bin
sudo cp /usr/local/share/moin/server/moin.cgi /var/www/YOURWIKI/cgi-bin/.
cd /var/www
sudo chown -R www-data:www-data YOURWIKI/cgi-bin
sudo chmod -R ug+rx YOURWIKI/cgi-bin
sudo chmod -R o-rwx YOURWIKI/cgi-bin

Your instance is installed, now you just have to set the config files up to point to it. Add the following two lines to /etc/apache2/httpd.conf where the Alias is /moin_staticYOURVERSIONNUMBER:

Alias /moin_static162/ /usr/local/share/moin/htdocs/
ScriptAlias /tvswiki /var/www/tvswiki/cgi-bin/moin.cgi


Set the path to your wiki to /var/www/YOURWIKI in /var/www/YOURWIKI/cgi-bin/moin.cgi
Set the data dir and underlay dir to their (absolute, i.e. /var/www/YOURWIKI/WHATEVER) paths in /var/www/YOURWIKI/wikiconfig.py
Restart apache with
sudo /etc/init.d/apache2 restart

and you're done!
Of course, the next thing to look into will be setting up groups and ACLs and theming it. Happy Hacking!
MIT-Scheme is Broken in Hardy
posted on 2008-04-15 15:57:01
UPDATE: There is a fix for this posted on my blog here. I figured everyone would find that via google but all the traffic seems to be coming here instead. Hit the link.
Now, I realize both that I can use another Scheme to work on SICP and that I can use Launchpad to submit a [patch/bug report/etc] but this is still kind of frustrating. At any rate, going to the source didn't work so I can't just use Debian's unstable packages. Going back in time and using a Gutsy or Debian Etch build might do the trick though. I filed a bug report. We'll see what happens. *sigh* Maybe they're all just trying to tell me to listen to Andy Wingo. I've been meaning to play around with F9 anyway. I always do. Distro release season is so fun and it comes twice a year! More on that later.

For the curious, MIT-Scheme when run from the command line will produce the following error:
Largest address does not fit in datum field of object.
Allocate less space or re-configure without HEAP_IN_LOW_MEMORY.
Encounters with an XO
posted on 2008-04-15 03:28:56
So, I recently received my OLPC XO. After playing with it a bit I'm pleased with it but I don't think that has terribly much to do with the device itself. I didn't really buy it to support One Laptop Per Child though I think the idea of a small, comprehensible system would go a long way towards engendering a new generation of hackers the way something like the Commodore 64 or Amiga did. OLPC: Way more hardcore than your middle school's Laptop Program. It is a goal I can identify with and support but I did this because I think it's a neat piece of hardware produced by passionate people. It may not be the next Lisp Machine but it's pretty cool nonetheless.



I was ecstatic when I got the thing. Naturally, I fiddled with the initial setup a bit but quickly wanted to move on to other things, namely emacs and lisp since I'm working through SICP at the moment. It was trivial to use yum to install emacs-nox and also quite straightforward to set up quack. What surprised me was how easy it was to compile Gambit on the XO as seen on Bill Clementson's blog.



Once that was done two things really started to eat at me. 1) I wanted to try getting a Debian-based install running on the XO. 2) I wanted a different Window Manager. I just am not comfortable with Sugar for some reason and I definitely wanted a browser with tabs. Looking into getting Debian going on the XO made me realize that getting a developer key was my first priority and I'd advise anyone with an XO to do it. Then you can play with the Forth prompts at boot, etc.



As for Window Managers, I've always had a bit of a fetish for them. Of late, I've been meaning to try out a tiling window manager and I got my choices down to ratpoison (which has the most bad ass supported hardware page ever), dwm, and Xmonad. For a variety of reasons, I'm itching to try Xmonad on one of my boxes soon but that will have to get in line behind setting git up on my blog server. At any rate, Xmonad is pretty awesome and it runs on the XO. I'm not sure how much of it is Haskell Voodoo and how much of it would be beginner-friendly but I'm sure that a full-featured 1200-line Window Manager has something to teach. I'll be keeping my eye on the upcoming book. More on all that later.

I read somewhere on laptop.org that they'll rebase a later build on FC9. I hope it's started before F10 hits and I hope that by F10 the 'Good Haskell Support' ticket gets completed. Long story short, I ran olpc-update debian-big on the XO and found that it's not really what I'm looking for. I'll probably later get Xubuntu Hardy on a Flash Drive and then replace the Window Manager with Xmonad but until then Sugar will be fine.

So, aside from my inane banter, is the XO any good? Well, good for what? The stock configuration is good for a limited set of uses but I imagine it'd be great for kids or if, like Luke Gorrie, you're hacking Forth.



An oft overlooked ability of the XO is it's SD expansion slot. If I was looking to do serious programming on it I'd slap the biggest SD card I could in there and hit the road. As long as what you're doing doesn't eat processor and RAM like crazy and you can port your tools over, it's a great travel box. Your hands will get used to the keyboard...eventually.

The Unexpected
posted on 2008-04-08 17:40:24
This poem was unexpected but I blame it's inspiration on Hofstadter, The Feyerabend Project (particularly the Sussman quote at the end, NO ONE pays enough attention to the Sussman quote at the end), and the quants.

There is a dim luminescence
on the edge of the world
drawing close. I hardly
see it's call but hear my
heart rise on approach.

The things unnamed we
can't contain, powerless
we act in vain. The systems
built stay brittle, break
when under stress they
cannot take. The deeper
message anathema to our
craven fantasies.

It may come for ill or gain
and is not my place to complain,
I know not what instruction awaits
so idly move at pleasant gait.
I hope the best for all of us,
for meritocracies in which to trust,
but utopia has no need of randomness
with which the universe is enamored.

The glamor and gore of that
midnight show I will not see
and will not know. I'll laugh
a good deal as I go but it
speeds like a star's falling.
If we find whatever defines
the space where interaction
takes it's place and emerging
from names is a trace
of self I shan't be surprised.

PS: I discovered that the Sussman quote at The Feyerabend Project was sourced from this paper. It may give some insight into all this.
Language Adoption and Lisps
posted on 2008-04-03 01:12:53
Long-Winded Preface
This is my (marginally informed but mostly inexperienced) personal opinion. I have a habit of thinking about things prematurely and overanalyzing them but I indulge in it. It seems most lispers at some point or another either do a roundup of the available lisps to decide on an implementation, try to figure out why lisp isn't more popular, or try to figure out why other languages seem to be growing towards it. I have an opinion on these issues after obsessing over them for a month or two and in the interest of believing some useful knowledge came from that obsession I'll document my opinions here. I should note that I don't yet consider myself a "lisper" for two reasons. One, I haven't yet encountered a formal definition of that term or a sufficiently common form of usage. Two, I simply haven't written enough lisp yet though I am sold on it to date.

Factors in Language Adoption
There are a few things that seem to drive adoption of programming languages generally but I'm interested in a small subset of programming languages so I'll be covering an appropriate subset of influencing factors. Specifically, I'm interested in languages that are not owned or pushed by a corporation but still have achieved some prominence among language elitists and/or some mainstream success. (4/7/08 Edit: This mostly serves as a disclaimer that I won't cover C, C++, C#, or Java here.)

As far as I can tell, these languages all have some of these critical features:
1. A single or dominant implementation.
2. A module system that works across implementations.
3. A killer app or great libraries.

Case(in_point) ->
The languages I'm thinking of are the following: Python, Perl, PHP, Lua, Ruby, Haskell, Erlang, and OCaml. Smalltalk is a perhaps crucial omission from this list but I count both Smalltalk and Lisp on a different language plane because of the sheer history surrounding them. I simply feel more factors are at play.

That said, all of these languages have achieved some preeminence for one reason or another though Haskell, Erlang, and OCaml are certainly not in the mainstream. Erlang sneaks in because of it's recent hype explosion and the limited use it's seen in industry, OCaml sneaks in on the virtue of it's infamous use at Jane Street alone, and Haskell I'm letting in both for it's proselytizing FP userbase and interesting programs (Darcs, Xmonad).

We can see quite clearly that several of these languages have one standard implementation (excluding ports to the JVM or CLR) including Perl, PHP, Lua, and Erlang, Python, and Ruby. As I already mentioned, Haskell has interesting programs at work and OCaml has some commercial usage. Lua has heavy use in the Video Game industry for scripting among other places. Erlang is used at Amazon, Ericsson, Nortel, and T-Mobile. Python, Perl, and PHP are the languages that built that web and Ruby has taken off since all that Rails business.

Common Objections
Many people complain about the communities being elitist or the implementations being insufficient or the syntax being odd. I'd say those are the three complaints I see the most. Certainly, the syntax does scare a few folks. Certainly, there are cases where a lisper doesn't handle a noob with the proper tact. Certainly, there are cases where it makes more sense to use another language on a project in lieu of Lisp. I do not believe that parentheses will deter those actually interested in stretching their abilities and learning a new language. I do not believe that a few flames are indicative of the general lisp community. I do not believe that lisp not being ideal in a given scenario is necessarily a problem with the available implementations.

The Punchline
What I've failed to talk about is point 2 (a standard module system) which I think is presently the most serious drawback to the Lisps. Lisp will never have a standard de facto implementation. There are plenty of implementations already on the scene and many of good quality, combined with the fact that some implementations are designed around a spec (RnRS). I grant that this entire problem could be solved if the Schemes at least standardized on R6RS, or at least the R6RS module system but apparently that isn't happening.

As I've said, we'll never have a standard implementation and, from what I can tell, the absence of both a standard implementation and a standard module system simply slaughters the code portability that would help a healthy community of code sharing. This precludes the libraries and interesting programs that lead languages out of the elitist ghetto. Most programmers won't touch a language regardless of it's feature set if they can't be productive with it fairly rapidly without writing the sort of libraries they've come to expect. If there is something wrong with lisps, this is it. Very few programmers will seriously try a new language without easily available libraries that make the language have a batteries-included feel to it.

Now, I realize that standardizing all Schemes on R6RS is impractical but we don't need even that. If we could manage to just get the three largest Scheme implementations to unite on one module system we would have made tremendous progress. I'd say the three largest Schemes in userbase with a module system are: PLT Scheme, Gambit-C, and Chicken Scheme or Bigloo Scheme. If we could get even these 3 or 4 implementations to standardize, I think it would be enough to really get things rolling. Even 2 of them standardizing on modules might be enough to pull others in. I can't personally think of a bigger win.

The Inflammatory Bit
I don't mention Common Lisp here because, again I stress personally, I hope we stop encouraging it as a starting point for newcomers. I don't think it's a good way to encourage people to use Lisp. I consider it more fragmented and thorny than Scheme for the beginner though I acknowledge it at least has a dominant implementation, from what I can tell, in SBCL. I realize that it has contributed a great deal and I don't mean to discredit it's achievements. It simply seems something better left to the experienced.

Personally, my disagreement with CL probably stems from two things. One, I dislike the design decision of separate namespaces for functions and arguments. Secondly, I feel that if most of CL's added functionality could be bolted on to a Scheme implementation through the use of libraries then why not have a Scheme implementation with said libraries and allow that to usurp the role played by prior CL implementations. I do grant that would be a lot of work to redo without good cause. At any rate, these are my inexperienced preliminary observations and my opinion may change drastically over the next few years as I have time to give it a fair chance and read through PAIP and On Lisp.

The greatest advantages of Common Lisp over Scheme I would expect to hear as arguments are it's use of CLOS and Namespaces, it's libraries, and it's quality implementations. I believe all of those are solvable issues in Scheme provided a standard module system enters the picture. I also have some opinions about why the Schemes should focus on distribution and concurrency after modules and further opinions on compilation to C versus native code. I leave that for another time.

Conclusion
In short, the central problem lisp must overcome for mainstream success (which may not even be desirable) is a standardized module system. The lack of a module system prevents a culture of code sharing which is preventing the creation of a software ecosystem around lisp. This is, at root, a sociological problem emerging from a technical problem. The lack of a standard module system and shared code produces the social effect of Lisp's continued obscurity. Lisp's obscurity does not stem from some deep difficulty inherent to the language, noob-averse communities, shoddy implementations, or the Lots of Spurious Irritating Parentheses.
An Absence
posted on 2008-04-02 13:47:11
These words are caught food
from the flipping plate,
recorded here for your
careful entertainment,
your frolicking scrutiny.
But I can't help wondering
what I missed which fell in the sea,
and what shore those words
finally washed upon. Mostly,
I wish they were here.
SICP Section 1.3
posted on 2008-04-01 02:31:48

At long last, I'm through Chapter 1 of SICP. I'm a bit disappointed that Closures haven't been covered yet but they're in the first few pages of Chapter 2 and I've already got a few problems solved. As a matter of fact, I finished Chapter 1 last Wednesday it just takes time to get these posts up. I have a feeling I need to go back and study those explanations of Lexical Scope in Chapter 1 though. I'll try to write more about the experience thus far in a separate post. For now, here are my results for Section 1.3.



Resources:

Read: Chapter 1 through Section 1.3

Watch: Lectures 2-a

Checked against: Eli Bendersky's Blog, SICP Wiki, Ken Dyck's Solutions, Theloserblog, Wfasim's Solutions, Autodidact and Lispy for Inspiration.


SICP Notes and Exercises:


Notes

Pgs. 63-66: Discussion of Let and Local Variable Binding.

Pg. 76: Discussion of First-Class Status in programming languages.


Quotes

"I'm going to write the...procedure here explicitly without giving it a name. I'm doing it anonymously, I don't necessarily have to give a name to something if I just want to use it once." - Gerald Jay Sussman, approx. 17:00, Lecture 2-a


"Procedures can be named by variables. Procedures are not special...Therefore they can be passed from one to another as arguments." - Gerald Jay Sussman, approx. 20:00, SICP Lecture 1-B from Swiss Archive, Higher-Order Functions Explanation


"Talent is to a great extent knowledge that we haven't yet learned how to formalize." - Gerald Jay Sussman, approx. 55:00, The Legacy of Computer Science


Exercises

1.29:


This exercise definitely wasn't easy. I think most of the difficulty is in figuring out how the math works and how the functions are all feeding into each other.


(define (cube x) (* x x x))
;Value: cube

(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b))))
;Value: sum

(define (simpsons-rule f a b n)
(define h (/ (- b a) n))
(define (k-term x)
(cond ((or (= x 0) (= x n)) 1)
((even? x) 2)
(else 1)))
(define (yk x)
(* (k-term x)
(f (+ a (* x h)))))
(* (sum yk a (lambda (x) (+ x 1)) n)
(/ h 3)))
;Value: simpsons-rule

(simpsons-rule cube 0 1 100)
;Value: 1/4

(simpsons-rule cube 0 1 1000)
;Value: 1/4

1.30:

Personally I think it's really nice that Abelson and Sussman have been throwing in these sort of review problems. They make me feel like I'm learning something. They give me hope. I solved this one in about 1 minute and a half and thought, "Hey, maybe I'm not a complete idiot. Maybe I'll actually know something about programming one day."


(define (sum term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (+ (term a) result))))
(iter a 0))
;Value: sum

1.31:


a.


(define (product term a next b)
(if (> a b)
1
(* (term a)
(product term (next a) next b))))
;Value: product

(define (factorial n)
(product (lambda (x) x) 1 (lambda (x) (+ x 1)) n))
;Value: factorial

(define (pi-approx approximations)
(define (pi-term denom) (/ (- (square denom) 1) (square denom)))
(define (next-term denom) (+ denom 2))
(product pi-term 3 next-term approximations))
;Value: pi-approx

(pi-approx 40)
;Value: 4722366482869645213696/5938020471163465810125 (.795276)

I just changed the variable names and commented pi-approx. The comment is omitted here in favor of this explanation. I couldn't figure out what on earth I was doing in the original so I actually wrote a brand new pi-approx with a different approach before realizing my original version was both correct and, I suspect, faster. I was computing 2 terms at a time based on their shared denominator.


b.


(define (product term a next b)
(define (iter a result)
(if (> a b)
result
(* (term a)
(product term (next a) next b))))
(iter a 1))
;Value: product

1.32:


a.


(define (accumulate combiner null-value term a next b)
(if (> a b)
null-value
(combiner (term a)
(accumulate combiner null-value term (next a) next b))))
;Value: accumulate

(define (sum term a next b)
(accumulate + 0 term a next b))
;Value: sum

(define (product term a next b)
(accumulate * 1 term a next b))
;Value: product

b.


(define (accumulate combiner null-value term a next b)
(define (iter a result)
(if (> a b)
null-value
(combiner (term a)
(iter (next a) result))))
(iter a null-value))
;Value: accumulate

1.33:


(define (filtered-accumulate combiner null-value term a next b filter)
(cond ((> a b) null-value)
((filter a) (combiner (term a)
(filtered-accumulate combiner null-value term
(next a) next b filter)))
(else (filtered-accumulate combiner null-value term
(next a) next b filter))))
;Value: filtered-accumulate

a.


(define (sum-square-primes a b)
(filtered-accumulate + 0 square a inc b prime?))
;Value: sum-square-primes

b.


(define (product-relative-primes n)
(define (relatively-prime i)
(= (gcd i n) 1))
(filtered-accumulate * 1 identity 1 inc n relatively-prime))
;Value: product-relative-primes

1.34:

The procedure f only actually produces output when it's argument is another procedure, specifically a procedure which takes one formal parameter. Given a procedure of a different arity it will produce an error regarding the wrong number of arguments and given a non-procedural argument it will complain about the object not being applicable.


1.35:


(define tolerance 0.00001)
;Value: tolerance

(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
;Value: fixed-point

(define (golden-ratio)
(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0))
;Value: golden-ratio

(golden-ratio)
;Value: 1.6180327868852458

Things are pretty straightforward from 1.29 through 1.36. The main thing to remember on 1.35 and 1.36 is that a transformation is just a function and serves as the f in the fixed-point.


1.36:


(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
(display guess)
(newline)
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
;Value: fixed-point

(define (solve-for-x)
(fixed-point (lambda (x) (/ (log 1000) (log x))) 2.0))
;Value: solve-for-x

(solve-for-x)
2.
9.965784284662087
3.004472209841214
6.279195757507157
3.759850702401539
5.215843784925895
4.182207192401397
4.8277650983445906
4.387593384662677
4.671250085763899
4.481403616895052
4.6053657460929
4.5230849678718865
4.577114682047341
4.541382480151454
4.564903245230833
4.549372679303342
4.559606491913287
4.552853875788271
4.557305529748263
4.554369064436181
4.556305311532999
4.555028263573554
4.555870396702851
4.555315001192079
4.5556812635433275
4.555439715736846
4.555599009998291
4.555493957531389
4.555563237292884
4.555517548417651
4.555547679306398
4.555527808516254
4.555540912917957
;Value: 4.555532270803653

(define (solve-for-x)
(fixed-point (lambda (x) (average x (/ (log 1000) (log x)))) 2.0))
;Value: solve-for-x

(solve-for-x)
2.
5.9828921423310435
4.922168721308343
4.628224318195455
4.568346513136242
4.5577305909237005
4.555909809045131
4.555599411610624
4.5555465521473675
;Value: 4.555537551999825

Pretty impressive. solve-for-x went from taking 34 steps to 9 steps thanks to average damping. I wonder what it does for golden ratio? And sqrt's for various inputs...


1.37:

a.


(define (cont-frac n d k)
(define (frac-iter i)
(if (< i k)
(/ (n i) (+ (d i) (frac-iter (+ i 1))))
(/ (n i) (d i))))
(frac-iter 1))
;Value: cont-frac

(cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 11)
;Value: .6180555555555556

b.


(define (cont-frac n d k)
(define (frac-iter count result)
(if (= count 0)
result
(frac-iter (- count 1)
(/ (n count) (+ (d count) result)))
(frac-iter k 0))
;Value: cont-frac

(cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 11)
;Value: .6180555555555556

The main thing that's tricky about 1.37 is figuring out the math of continued fractions and starting with the base case of the last term and working backwards.


1.38:


(define (euler-expand)
(define (d-fun i)
(cond ((= (modulo i 3) 2) (* (ceiling (/ i 3)) 2))
(else 1)))
(cont-frac (lambda (i) 1.0) d-fun 8))
;Value: euler-expand

(euler-expand)
;Value: .7182795698924731

So, my original iterative version of cont-frac didn't actually work for this problem. The iterative version didn't work for this problem because it treated division as though it's commutative and it isn't. It took me a while to figure that out.


1.39:


(define (tan-cf x k)
(define (d i)
(- (* 2 i) 1))
(define (n i)
(if (= x 1)
x
(square x)))
(cont-frac n d k))
;Value: tan-cf

(tan-cf 1.0 5)
;Value: 1.5574074074074076

This one is actually fairly tricky. If you fail to notice that this is a continued fraction that subtracts rather than adds you're completely hosed. I modified my cont-frac procedure to fix this once I noticed. There's probably an elegant way to extend cont-frac to accomodate these different uses (subtracting versus adding continued fractions, etc.) but I'm not going to chase it down myself. Anybody feel like improving on this?


1.40:


(define (cubic a b c)
(lambda (x) (+ (expt x 3) (* a (expt x 2)) (* b x) c)))

(define dx 0.00001)
;Value: dx

(define (fixed-point-of-transform g transform guess)
(fixed-point (transform g) guess))
;Value: fixed-point-of-transform

(define (cubic a b c)
(lambda (x) (+ (expt x 3) (* a (expt x 2)) (* b x) c)))
;Value: cubic

(define (deriv g)
(lambda (x) (/ (- (g (+ x dx)) (g x)) dx)))
;Value: deriv

(define (newton-transform g)
(lambda (x) (- x (/ (g x) ((deriv g) x)))))
;Value: newton-transform

(define (newtons-method g guess)
(fixed-point (newton-transform g) guess))
;Value: newtons-method

(newtons-method (cubic 4 3 2) 1)
;Value: -3.2695308420809894

I didn't realize I just needed to literally translate the function. After I knew that I was fine. Again, time to study more math.


1.41:


(define (double x)
(lambda (i) (x (x i))))
;Value: double

(define (inc x) (+ x 1))
;Value: inc

((double inc) 0)
;Value: 2

(((double (double double)) inc) 5)
;Value: 21

;;This is because a double on a (double double) is effectively a square.

(double double)
;Value 16: #[compound-procedure 16]

(((double (double double)) inc) 0)
;Value: 16

((double (double (double inc))) 0)
;Value: 8

(((double (double (double double))) inc) 0)
;Value: 256

1.42:


(define (compose f g)
(lambda (i) (f (g i))))
;Value: compose

((compose square inc) 6)
;Value: 49

1.43:


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

((repeated square 2) 5)
;Value: 625

Wow! That was a lot easier to think about using compose.


1.44:


(define (smooth f)
(define dx 0.00001)
(lambda (x) (/ (+ (f (- x dx)) (f x) (f (+ x dx))) 3)))
;Value: smooth

((smooth square) 2)
;Value: 4.000000000066667

(define (n-smoothed f n)
(repeated smooth n) f)
;Value: n-smoothed

((n-smoothed square 16) 2)
;Value: 4

Check The Loser Blog for a potentially better answer.


1.45:


(define tolerance 0.00001)
;Value: tolerance

(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
;Value: fixed-point

(define (average x y)
(/ (+ x y) 2))
;Value: average

(define (average-damp f)
(lambda (x) (average x (f x))))
;Value: average-damp

(define (nth-root x n)
(fixed-point (repeated
(average-damp (lambda (y) (/ x (expt y (- n 1)))))
(ceiling (/ n 2))) 1.0))
;Value: nth-root

(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 (nth-root x n)
(fixed-point-of-transform (lambda (y) (/ x (expt y (- n 1))))
(repeated average-damp (log2 n)) 1.0))
;Value: nth-root

(define (log2 n)
(if (= 1 n)
0
(+ (log2 (floor (/ n 2))) 1)))
;Value: log2

After testing the first 15 powers with my version of nth-root I couldn't figure out the relationship between n and the times to average damp. Just about everyone had trouble with this but I found the correct answer in Eli's comment thread...


1.46:


(define (iterative-improve tester improver)
(define (iter guess x)
(if (tester guess)
guess
(iter (improver guess) x)))
(lambda (x) (iter 1.0 x)))
;Value: iterative-improve

(define (sqrt x)
((iterative-improve
(lambda (guess) (< (abs (- (square guess) x)) 0.00001))
(lambda (guess) (average guess (/ x guess)))) x))
;Value: sqrt

(define (average x y)
(/ (+ x y) 2))
;Value: average

(sqrt 2)
;Value: 1.4142156862745097

(define (fixed-point f x)
((iterative-improve
(lambda (guess) (< (abs (- guess (f guess))) 0.00001))
(lambda (guess) (f guess))) x))
;Value: fixed-point

(fixed-point cos 1.0)
;Value: .7390893414033927

(Edit: 05/18/08) Well, that wraps it up for Section 1.3. I can't believe how long it took me to find the time to come back and clean these answers up a bit. I have had a lot going on though. There will be a few small changes in convention starting in SICP 2.1 to make things more manageable for me. As always, the most up to date code is in the repo.

This blog covers 2015, Books, Butler, C, Dad, Discrete Math, Displays, Education, Erlang, Essay, Gaming, Gapingvoid, HTDP, Hardware, IP Law, LISP, Lecture, Lessig, Linkpost, Linux, Lists, MPAA, Milosz, Music, Neruda, Open Source, Operating Systems, Personal, Pics, Poetry, Programming, Programming Languages, Project Euler, Quotes, Reddit, SICP, Self-Learning, Uncategorized, Webcomic, XKCD, Xmas, \"Real World\", adulthood, apple, careers, coleslaw, consumption, creation, fqa, games, goals, heroes, injustice, linux, lisp, math, melee, metapost, milosz, personal, poetry, programming, ragequit, recreation, rip, strangeloop, work

View content from 2015-05, 2015-03, 2015-02, 2015-01, 2014-11, 2014-09, 2014-07, 2014-05, 2014-01, 2013-10, 2013-09, 2013-07, 2013-06, 2013-05, 2013-04, 2013-03, 2013-01, 2012-12, 2012-10, 2012-09, 2012-08, 2012-06, 2012-05, 2012-04, 2012-03, 2012-01, 2011-10, 2011-09, 2011-08, 2011-07, 2011-06, 2011-05, 2011-04, 2011-02, 2011-01, 2010-11, 2010-10, 2010-09, 2010-08, 2010-07, 2010-05, 2010-04, 2010-03, 2010-02, 2010-01, 2009-12, 2009-11, 2009-10, 2009-09, 2009-08, 2009-07, 2009-06, 2009-05, 2009-04, 2009-03, 2009-02, 2009-01, 2008-12, 2008-11, 2008-10, 2008-09, 2008-08, 2008-07, 2008-06, 2008-05, 2008-04, 2008-03, 2008-02, 2008-01, 2007-12, 2007-11, 2007-10, 2007-09, 2007-08, 2007-07, 2007-06, 2007-05


Unless otherwise credited all material Creative Commons License by Brit Butler