# An Emulator Design Pattern

posted on 2012-06-22 17:49:15

Going into this project, I knew almost nothing about emulation. I still know very little. But I was tired of seeing emulators written in C and Java for performance or portability that wound up looking like a big switch statement sooner or later. My 6502 emulator is ANSL CL and should run anywhere that sbcl, clisp, ccl, or any other fine Common Lisp implementation will run. Granted, if a totally new processor architecture comes out, it's probably easier to cross-compile/port a 6502 in C than the CL compiler hosting cl-6502 but I digress. I wanted to write a fast, high-level emulator. The closest thing I found to an emulator design that I liked was py65 but even that was a bit less abstract than I would've hoped.

I'm still searching for ways to improve the core abstractions that I have (and no doubt there are many hardcore low-level hackers that would be disgusted by my work) but I'm enjoying the process and here are some preliminary thoughts...

Addressing modes, addressing modes, addressing modes. This is the biggest difference between assembly language and the languages I use day to day. Hence, it's a crucial abstraction to get correct. For the first time, Common Lisp's notion of "generalized places" has been a real boon. There were two nuances to addressing modes that I found I really needed to account for.

• Some modes access CPU registers, others RAM. (This mostly just effects the way I need to use setf.)

• Most opcodes use the byte /at/ an address rather than the address, but sometimes an opcode *does* need the address.

To solve these issues and abstract some code patterns, I wrote a macro called defaddress. It defines a method on the CPU that returns the address computed by the mode /and/ generates a setf function that sets the register in the CPU struct or the byte in memory based on a cpu-reg keyarg to the macro. Finally, to solve the issue that we most often want the byte, opcodes are defined as either being :raw or not (the default). If they're not, instead of passing the mode symbol to be funcalled, we pass a lambda that gets the byte at the address computed by the mode. So far, concerns seem nicely separated. Time will tell if I've struck on the right design here.

### Opcodes

Opcodes in cl-6502 are really mnemonics, a set of opcodes that encode the same language primitive but for different addressing modes. As long as the foundation of addressing modes as funcallables is there to support the opcodes, you can write any opcode cleanly with a single body of code shared across all addressing modes. This has made me deeply happy as it seems to me to be _THE RIGHT THING_.

The implementation of defopcode is a bit hairy, particularly the EVAL-WHEN block to make sure metadata about the opcodes gets set in the *opcodes* array at load-time, but the supporting defins macro is fairly clean. The important thing is that opcode definitions wind up looking marvelous. For example, here's ASL and BCC:

    (defopcode asl (:docs "Arithmetic Shift Left" :raw t)        ((#x06 5 2 'zero-page)         (#x0a 2 1 'accumulator)         (#x0e 6 3 'absolute)         (#x16 6 2 'zero-page-x)         (#x1e 7 3 'absolute-x))      (update-flags (funcall mode cpu) '(:carry))      (let ((result (wrap-byte (ash (funcall mode cpu) 1))))        (update-flags result)        (funcall setf-form result)))    (defopcode bcc (:docs "Branch on Carry Clear" :track-pc nil)        ((#x90 2 2 'relative))      (branch-if (lambda () (zerop (status-bit :carry cpu))) cpu))

ASL defines 5 methods here each with a different addressing mode but sharing the same body. They update flags in the status register as expected, increment the program counter properly, and put metadata in *opcodes* to aid with dispatch and disassembly. Not bad, eh?

### Objects, Functions, Macros, Whatever!

So far, I've mostly just used objects (read: CLOS) to define some conditions, two core methods on the CPU (step and execute), and the instructions themselves. The CPU itself is defined as a Struct rather than a Class. All the instructions are methods EQL-specialized on the opcode and the opcode alone which should make dispatch pretty speedy. The methods reference the *cpu* global directly and since Common Lisp has /usable global variables/ that look up the most recent binding in the current thread on reference, I should be able to run many instances safely in different threads on a single core. Just do something like...

    (make-thread :foo (lambda ()           (let ((*ram* (make-array (expt 2 16) :element-type '(unsigned-byte 8))                 (*cpu* (make-cpu))))             &body))) ;; and we're off to the races!

### What's next?

I have a bunch of potential ideas for what's next. I want to extend this work towards full NES emulation in the browser. There isn't a formal ordering of priorities or milestones yet (cause this is kind of an art project), but coming up with a sane, RESTful API to sit on top of cl-6502 is probably the next step. Hopefully I'll get some time to hack on that this weekend.

• cl-6502: An assembler! Unit tests + bug fixing.

• famiclon: An NES emulator backend built on romreader and cl-6502. Video, Sound. Input?
• Qeng-Ho: Hunchentoot+ST-JSON, REST API wrapping cl-6502+famiclon, No persistence! Multiple CPUs! Internal private API for now.

• Pham-Nuwen: Clojure+Clojurescript@Deepclouds.net. Persistence! Nice web interface. Graphics w/canvas! Etc...

• cl-z80: DO THAT SHIT! (how hard could it be? just another 8bit thing. see emu-docs.org)

# On Interactive Retrocomputing

posted on 2012-06-18 04:27:59

Lately, I've been working on an emulator for the MOS 6502 processor in Common Lisp that I've been boring enough to name cl-6502. The emulator is basically finished as is the disassembler. There are also pretty solid docs. An assembler should be added soon and hopefully a helper utility or two and unit tests. But why do this? Well, for a couple of reasons.

1) I never did enough Systems Programming. I never did any assembly in college and wrote an absolute paucity of C (granted, that's my fault). I never learned enough about the inner working of Operating Systems or how to exploit memory hierarchies. I want to know more about how the machine works at a low level. Writing an emulator in a high-level language isn't a great way to do that but I wanted to anyway. Writing some assembly programs to run on this emulator might help though and I hope to do some of that later.

2) I was curious how concise, extensible, and performant an emulator could be written with Common Lisp. Most emulators are written in C/C++ for performance reasons. There are a few in Java (for portability?) or Javascript for what we now call portability but even these are not terribly high-level from a design perspective. I don't have all the answers to this question yet but I'm excited by some of the work I've done so far. In particular, writing macros for Addressing Modes and Opcodes has been quite helpful and I expect CLOS's :before, :after, and :around methods to go a long way where extensibility is concerned. I'm hoping the EQL-specialized methods, SBCL, and perhaps some shrewd profiling can lead to good performance. Also, 45 lines of code for a 6502 disassembler doesn't seem bad to me. :P

3) ICU64/Frodo Redpill. I'm not wild about static types and I tend to write tests after the fact because I view programs as clay until they're ready to be fired in the kiln. Roly Perera's work on self-explaning computation interests me a lot as does Chris Granger's work on Light Table. Rapid feedback loops are important. Maintaining flow is important. As far as I'm concerned, all emulators should strive towards the sort of "peek/poke the machine" experience that ICW/Frodo Redpill offers. Games are a very easy way to get people to engage with computers. Everybody likes games. And lots of folks at some point in wondering about programming, ponder how much is involved in changing something about a game they like. With a system like ICU/Frodo Redpill they could literally /see/ the answer. Add an integrated editor and you're in pretty interesting territory. Feel like changing something about the "hardware"? Feel like having breakpoints and step debuggers pop up on arbitrary memory accesses or instruction executions? You got it. But ICU64/Frodo Redpill has this all locked down on desktops. Why not do as much as possible with HTML5, <canvas>, and Clojurescript? I'm not going to be the guy to come up with the next Mother of all Demos ... but I hope to make something cool. And if I'm really lucky, I'll have something interesting to play with online by Strange Loop on September 23rd. I've already got a 6502 emulator. What's next?

# Ye Olde Smorgasborg

posted on 2011-05-06 21:18:23

This post may come off as a bit scattered. The main reason is that so much has been going on. I've finished my last semester at SPSU and should be picking up my diploma soon, I've been running around looking for a loft to move into with my friend Burke come late June and I've been working on getting a job. There's been progress on all of those fronts and I look forward to writing about them soon. Finally, I have a new Lisp project that I've been having fun hacking on and wanted to talk about. I was going to wait until I was ready to release version 0.1 but it's beginning to seem like that might be a few months out and I just can't help myself. I'll talk mostly about my motivations, design goals, some early results, my immediate plans and similar work others have begun recently.

## Motivations

The project is a piece of Lisp blog software I've christened "Coleslaw". I've wanted to write my own blog for a while for a variety of reasons. The most significant is that it would be a good learning experience and fun. Additionally, then I could just run SBCL and PostgreSQL on my servers and scrap MySQL and PHP. I'd been putting it off for some time as I'm no web development expert but I had an opportunity to get course credit for working on it some this semester so I decided to get the ball rolling.

Lately a piece of Ruby blogware named Jekyll became surprisingly popular. There are two interesting things about Jekyll to me. The first is that it uses a static-site compilation model rather than generating pages dynamically (as Wordpress does). The second is that it requires and provides no admin-interface as a result. It simply watches a directory for new posts and regenerates as much of the site as necessary.

The simplicity (and somewhat simpler security model) of writing blogware that didn't have an admin interface and just keeping everything in flat files really appealed to me but I knew many people still love admin interfaces and database backed webapps and for good reason. Though you should always have backups of course. Anyway, it's thanks to Jekyll and several similar clones that I really started looking into the design of something that could support both options.

## Design Goals

The original design goals were to support a *single-user* blog with either a dynamic backend that provided an admin interface and made use of a database or a static backend that simply compiled posts from a watched directory to an HTML output directory. Since then I've decided a bit more separation of concerns is in order. Down the line I'd like to support the following "large-scale" options with Coleslaw:
• Where is the data? (mongodb, postgresql, flat files, lisp data persisted with cl-store or similar, etc)

• How is the data served? (Static files, Dynamically generated w/optional caching)

• How is the data edited? (web-admin-interface-p)

• Who serves the data? (S3, Lisp server (hunchentoot/etc), System HTTPD (lighttpd/apache/etc)

• How are comments handled? (Cloud service (disqus/etc), Stored and generated locally, disabled)

• Above and beyond that I'd like to have a few bundled plugins for things like Analytics, Syntax Hightlighting, LaTeX support, Import from other blogs, Crossposting. Finally, Coleslaw should be easy to theme.

## Early Results

The code is presently on github and I haven't hacked on it for a few days because I've been relaxing post-finals. That said, I'm looking forward to getting back into working on it in the near future. At this time, only the static backend has been started and there's still no implementation for directory watching to update posts. Comment support also hasn't been completed. That said there's a preliminary theme (stolen from ckeen's hyde, thanks ckeen!) and an example site running backed by S3. Note that the posts shown are all imported from an XML export of my Wordpress blog. The current import plugin only supports wordpress and only handles posts, not comments. The code used to generate the example site was pasted here.

I feel pretty solid about the internal API for indexes and posts and my plugin infrastructure as well as the theming situation. cl-fad, local-time, cl-closure-template, cl-docutils and cl-markdown are the current hard dependencies for the core because I'd like to support ReStructuredText, HTML or Markdown input for posts. Just for giggles my friend Neil also made a logo in large, medium and small. Here's medium:

## Immediate Plans

I started working on plugins for disqus comment support as well as mathjax LaTeX support but the whole experience made me want to revamp my API for "injections" which allows plugins to throw various bits of JS in the page HEAD and BODY. I'd like to support arbitrary predicates (say, to only add the mathjax scripts when posts are tagged "math") and allow for distinguishing between whether something should be injected on post pages or index pages in addition to the current "should I inject this in the HEAD or BODY?" functionality. Once that's done, I'd like to support syntax highlighting via Python's pygments library. Then I'll get around to the directory watching/updating semantics. Once that's done I can work on the dynamic backend and start *THINKING* about a 1.0. That's the state of things today. I'd love to hear from you if you have thoughts, opinions or a desire to contribute patches/help. :D

## Recent Similar Efforts

I've found it pretty comical that 2 other (more experienced and talented) lispers recently began writing lisp blog software shortly after I started working on coleslaw. Who knows, if they had gotten around to it 6-9 months earlier I might never have wound up working on coleslaw, but I'm glad I have. It's a lot of fun.

If you find coleslaw interesting it's worth looking at nuclblog(cl-store serialized data, dynamic, Markdown) by Cyrus Harmon (slyrus), lisplog(drupal import, custom flat file database, dynamic) by Bill St. Clair (billstclair) and arblog(mongodb-backed, dynamic, ReStructuredText) by Andrey Moskvitin (archimag).

# Paktahn Progress

posted on 2011-02-01 05:39:00

In the last 3 weeks, Paktahn 0.9.2 and 0.9.3 have been released. Go install or upgrade it, quick! Leslie Polzer has passed on the role of Maintainer to me and I was privileged to accept it. Paktahn had been pretty quiet from May-Aug 2010 and was practically silent Aug-Dec 2010. As a consequence, a big part of my focus right now is revitalizing the project, making it clear we're still working on it and making it easy for new contributors to join in.

The biggest focus of the last two releases have been bugfixes, unifying the code style and reorganizing the project some. For example, my old gitorious repo has been taken down, all the TODO items are now in one place, etc. That doesn't mean there are no new features though. Among other things you can now finally upgrade all packages by running "pak -Syu --aur", pak -Ss which behaves like pacman -Ss extended to support AUR and various UI improvements. The rest is visible in the NEWS as always.

My plans for the next two releases can be found in the TODO. The short version is that I'm going to improve our option handling so pak can be used for as many pacman tasks as possible (i.e. -Q*, etc) and clean up the code for the next release. There should also be some small UI improvements. After that, I'm going to get a solid test suite in place. My github repo is the canonical source location at this point but Leslie's Issues page is the canonical bugtracker. As always, please file any bug reports or feature requests you have there. If there's any other feedback you have about the project you're welcome to post it on our forum thread.

I'm going to try to run a tighter release cycle for a little bit. There have already been two releases in January. I guarantee that there will be another point release so 0.9.4 is out by the end of February, I can't guarantee any more than that at this time though. That's all for now. I've got to get to sleep for an early class.

# Looking Back, Looking Forward

posted on 2011-01-03 01:02:26

### A 2010 Overview

So it's apparently 2011 now. That happened fast.

As I wrote on reddit, I think my year went very well where Lisp is concerned. Aside from Lisp, I can happily say that I'll be receiving my degree in May after completing 3 more courses: CS Capstone, an independent study on Functional Programming with Haskell and Chemistry I. I have 2 potential part time gigs for Spring and enough prospects in general that I'm not afraid of being unable to find a job when I graduate which is nice. I also have enough code projects and ideas to bury myself. I'm pretty happy ultimately with how 2010 turned out. I made some more progress in my development as a programmer and have almost wrapped up my time as an Undergraduate. Finally! It was tough breaking up with my girlfriend of 2+ years, Teresa, back in May but I still feel good about it in the sense that it was the right thing to do. Most of all, I stayed true to myself and I had fun.

### Upcoming Code Stuff

Now for a brief update on Paktahn, Weblocks, Clockwork and the CL Web Primer series...
First of all, the CL Web Primer series is not over. I haven't given up I've just been busy with other projects and some end of year decompression. There's actually going to wind up being one more post about Clockwork itself once I implement the last feature (and maybe do some CSS styling to make it look less like ass). By that point, the Postmodern backend which has been merged into Weblocks should be production ready. The main issue now is that you have to manage the DB connections for each request thread manually which is a real pain. I'm working on fixing it at the moment by extending the Store API and hooking into handle-client-request. Hopefully that will be done tomorrow or at least by the end of this week and get merged shortly after.

Once the Postmodern backend is going and the last clockwork post is made I have ideas for several projects to make use of the Postmodern store. One is a RESTful blog with Wordpress import and crossposting support for Livejournal. Another is a Magic the Gathering card/deck database similar to Deckbox. There are a few other ideas but I'll likely do one of these two and continue the CL Web Primer series with it.

Ah, Paktahn. I would be a little frustrated with us if I were a user. It's been a while since I've had time to hack on bugs or new features and there are 4 or 5 important bugs I'd like to squash so we can get a release out before school starts back up. It'd be particularly nice to get some fresh blood on the project. I can instruct or help reasonably well I just think Leslie and I are pretty preoccupied with other projects. It's a question of time mostly, so if there are any Archlinux using Lispers that have any interest *please* feel free to contact me on twitter, facebook, gmail, fork it on github, leave a comment, etc.

### Holiday Hacking

Personal hacks...
Over the holidays, I did a good bit of hacking on emacs and dotfiles. I also switched from using Chromium to using Conkeror as my browser and from Pidgin to Erc+Jabber.el (emacs modes) as my chat clients to force me into the Emacs mindset a little bit more. For a long time, I've had emacs and stumpwm installed but not really treated them as extensible lisp software that I should be playing with. I also improved my server config and its corresponding build process a bit. You're probably asking why do this. There are a lot of reasons why. All I'll say about it for now is that Archlinux+SBCL+Emacs+Stumpwm+Conkeror is about as close as you can get to a modern day lisp machine and it is a lot of fun.

Other than that, I threw together a version of tic-tac-toe that should never lose as part of a job application. I'd never written any Search algorithms before and knew nothing of Minimax so that was a fun learning experience. As usual, the code is on github. One other thing I've toyed with is a backup script which is made easier by the fact that I recently started using SSH agent. Between that and another Common Lisp script I use called randomfile, I ought to throw those up in my dotfiles in a scripts directory and then make a blog post about CL *nix Scripting or something. Who knows, by 2012 maybe I'll have gotten around to it. ;)

# A Common Lisp Web Development Primer, Part 3

posted on 2010-11-22 04:24:03

Disclaimer: What? You haven't already read the first two parts? Feel free to go ahead and do that. The same disclaimers apply. (require 'cl-wdp-part1 'cl-wdp-part2)

### Today's Topics

The main topics we'll be covering are Weblocks widgets, forms and views along with a brief example of creating a presentation to use jQueryUI's Datepicker. There will also be a brief aside on what to do after an emergency reboot or power outage relating to cl-prevalence and trivial-timers. By the end the clockwork site will be fully functional.

### Form-widgets, Widgets and Views

The User Guide has pretty nice expository summaries of Widgets and Views. The bottom line is that Widgets are what Weblocks pages are composed of and views are different ways to render those widgets. A macro called defwidget is used to construct widgets which are just new classes which inherit from the widget-metaclass. Don't worry if you don't know what that means. Essentially, you define widgets for the data you care about working with and then you define views to render that data, whether as a form for editing, a table for comparing multiple items or some other representation.

Leslie has been working on some new form-widget code intended to remove some of the sharp edges of the current system. As this site is basically just a form it made sense for me to try to use this new code (and Leslie wanted me to help him bang on it). Consequently, one thing you'll need to do is add (load "/path/to/weblocks/contrib/lpolzer/form-widget.lisp") to your init.lisp file that runs on startup. It should be placed after weblocks is loaded and before the loading of clockwork.

Last time we defined a reminder class with slots for the data we really care about: a list of emails, a title and summary and timestamps for when to send that message and when the event itself occurs. However, it won't do to ask our users to input timestamps or to tell us the "email" for their cell phone's SMS gateway. To that end, we'll define a view to gather the information we really need to construct the timestamps and other parts of the reminder. We need to know whether they want to be notified by email, text message or both. We'll need the corresponding contact info, including their cell carrier if they want to be notified by text message. We'll also need to note the event date, timezone and time as well as how long before the event they'd like to be reminded and a message and title. I've also thrown in a "honeypot" field. In theory, spam bots will indiscriminately fill it so we won't get any bogus submissions because the form won't validate. Maybe later we'll replace this with reCaptchas.

So let's get to it and define a view for our form in a new file src/forms.lisp. Insert the following code:
(in-package :clockwork)(defview reminder-form-view (:type form :caption "Schedule an Event Reminder..."			     :buttons '((:submit . "Submit")) :persistp nil)  (send-as :present-as (dropdown :choices '(("An email and a text." . :both)					    ("Just an e-mail." . :email)					    ("Just a text." . :text))				 :welcome-name "How to send it")	   :requiredp t)  (email :satisfies 'valid-email)  (cell-number :satisfies 'valid-cell-number)  (cell-carrier :present-as (dropdown :choices *sms-gateways*))  (event-date :present-as (calendar) :requiredp t)  (event-hour :present-as (dropdown :choices *hour-choices*)	      :requiredp t)  (event-minute :present-as (dropdown :choices   '(("00" . 0)						   ("15" . 15)						   ("30" . 30)						   ("45" . 45)))		:requiredp t)  (timezone :present-as (dropdown :choices *timezones*)	    :requiredp t)  (remind-me :present-as (dropdown :choices '(("At the event" . 0)					      ("5 minutes before" . 300)					      ("10 minutes before" . 600)					      ("15 minutes before" . 900)					      ("30 minutes before" . 1800)					      ("45 minutes before" . 2700)					      ("1 hour before" . 3600)					      ("2 hours before" . 7200)					      ("1 day before" . 86400)					      ("2 days before" . 172800)					      ("1 week before" . 604800)					      ("2 weeks before" . 1209600)))	     :requiredp t)  (subject :requiredp t)  (summary :present-as (textarea :rows 5))  (honeypot :label "Leave this blank" :satisfies #'null))(defparameter *timezones*  '(("UTC-12:00 (Eniwetok, Kwajalein)" . -43200)    ("UTC-11:00 (Midway Island, Samoa)" . -39600)    ("UTC-10:00 (Hawaii)" . -36000)    ("UTC-09:00 (Alaska)" . -32400)    ("UTC-08:00 (Pacific Time)" . -28800)    ("UTC-07:00 (Mountain Time)" . -25200)    ("UTC-06:00 (Central Time)" . -21600)    ("UTC-05:00 (Eastern Time)" . -18000)    ("UTC-04:00 (Atlantic Time, Caracas)" . -14400)    ("UTC-03:30 (Newfoundland)" . -12600)    ("UTC-03:00 (Brazil, Buenos Aires, Georgetown)" . -10800)    ("UTC-02:00 (Mid-Atlantic)" . -7200)    ("UTC-01:00 (Azores, Cape Verde Islands)" . -3600)    ("UTC+00:00 (Lisbon, London, Casablanca)" . 0)    ("UTC+01:00 (Berlin, Brussels, Copenhagen, Madrid, Paris)" . 3600)    ("UTC+02:00 (Kaliningrad, South Africa)" . 7200)    ("UTC+03:00 (Baghdad, Moscow, Riyadh, St. Petersburg)" . 10800)    ("UTC+03:30 (Tehran)" . 12600)    ("UTC+04:00 (Abu Dhabi, Baku, Muscat, Tbilisi)" . 14400)    ("UTC+04:30 (Kabul)" . 16200)    ("UTC+05:00 (Ekaterinburg, Islamabad, Karachi, Tashkent)" . 18000)    ("UTC+05:30 (Bombay, Calcutta, Madras, New Delhi)" . 19800)    ("UTC+05:45 (Kathmandu)" . 20700)    ("UTC+06:00 (Almaty, Colombo, Dhaka)" . 21600)    ("UTC+07:00 (Bangkok, Hanoi, Jakarta)" . 25200)    ("UTC+08:00 (Beijing, Hong Kong, Perth, Singapore)" . 28800)    ("UTC+09:00 (Osaka, Seoul, Sapporo, Tokyo, Yakutsk)" . 32400)    ("UTC+09:30 (Adelaide, Darwin)" . 34200)    ("UTC+10:00 (Eastern Australia, Guam, Vladivostok)" . 36000)    ("UTC+11:00 (Magadan, New Caledonia, Solomon Islands)" . 39600)    ("UTC+12:00 (Auckland, Fiji, Kamchatka, Wellington)". 43200)))(defparameter *hour-choices*  (loop for i from 0 to 23     collecting (,(format nil "~d" i) . ,i)))

So here we're defining a view called reminder-form-view and passing in a list of arguments *about* the view as well as a list of fields in the view. In the list of arguments about the view we note that it's a form and we don't want to persist the form contents directly. We use a variety of keywords in the list of form fields to get the behavior we want including :present-as, :requiredp, :satisfies and :label. Present-as allows us to make something a dropdown or any other defined presentation. Note that some presentations do take arguments. Dropdown in particular takes a list of dotted pairs representing the Dropdown choice and it's corresponding value. Requiredp does what you'd expect and marks a form field as required. Satisfies takes a lambda or the name of a function which will validate the field's data. By default, the view will "humanize" the field names and use those humanized names as labels. If you want a different label for some reason, you can achieve that with the :label keyword.

Now we have a form that takes all the data we need to construct a reminder but we still need to validate the emails and cell phone numbers. Additionally, we'll need to write helper functions to construct the email list and timestamps that the reminder's emails and timestamp slots will be set to. Consequently, add this code to the bottom of the file:

(defun valid-email (user-input)  "Ensure that there is an @ and a . and input not containing @s before and after each."  (or (cl-ppcre:scan "^[^@]+@[^@]+\\.[^@]+$" user-input) (values nil "Your email must have an @, a . and text before and after both.")))(defun valid-cell-number (user-input) "Ensure that only numbers are given and there are at least 10." (or (cl-ppcre:scan "^[0-9]{10,}$" user-input)      (values nil "Your number must have only numbers and at least 10 of them.")))(defun get-emails (form-data)  (with-form-values (send-as email cell-number cell-carrier) form-data    (let ((sms-mail (concatenate 'string cell-number "@" cell-carrier)))      ;; this was an ecase with keywords but weblocks converts      ;; the keywords to strings somewhere in form submission      (cond ((string= send-as "BOTH") (list email sms-mail))	    ((string= send-as "EMAIL") (list email))	    ((string= send-as "TEXT") (list sms-mail))))))(defun get-timestamps (form-data)  (with-form-values (event-date event-hour event-minute		     remind-me timezone) form-data    (let* ((hour (parse-integer event-hour))	   (minute (parse-integer event-minute))	   (reminder-time-period (parse-integer remind-me))	   (timezone (parse-integer timezone))	   (datestring (split-sequence #\- event-date))	   (day (parse-integer (first datestring)))	   (month (parse-integer (second datestring)))	   (year (parse-integer (third datestring)))	   (event-time (encode-timestamp 0 0 minute hour day month year :offset timezone)))      (list event-time	    (timestamp- event-time reminder-time-period :sec)))))

The validation functions are ORs with the function testing the input as the first clause and a VALUES form returning nil (a failed submission) and an appropriate error message as the second. The helper functions use the with-form-values macro to grab the relevant fields of the form and construct the resulting slot. Get-timestamps is rather nasty but we're essentially just grabbing all those fields pertaining to the time, parsing the integers from them and passing those on to the appropriate timestamp functions in the local-time library.

### A Calendar Presentation

It would certainly be better to have a nice calendar than have users enter dates as strings and then try to validate them and God forbid we roll our own given the number of Javascript calendars already out there. Since it's fairly well established I opted for the jQueryUI Datepicker. Previously to use Javascript libraries you needed to download them and place them in your Weblocks project's pub/script folder but thanks to a quick patch by Leslie Polzer remote dependencies are now also supported. In case you didn't read the previous article, when you first start a project with (wop:make-app 'name "/path/to/app") weblocks generates a defwebapp form and a basic package for that app along with setting up a store and some basic resources. To include the jQuery code on our page we'll modify our defwebapp form in clockwork.lisp like so:
(defwebapp clockwork    :prefix "/"    :description "Fire-and-Forget Event Reminders"    :init-user-session 'clockwork::init-user-session    :autostart nil                   ;; have to start the app manually    :ignore-default-dependencies nil ;; accept the defaults    :hostnames '("clockwork.redlinernotes.com")    :dependencies '((:stylesheet "http://ajax.googleapis.com/ajax/libs/jqueryui/1.8.5/themes/ui-darkness/jquery-ui.css")		    (:script "http://ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.min.js")		    (:script "http://ajax.googleapis.com/ajax/libs/jqueryui/1.8.5/jquery-ui.min.js")		    (:javascript-code "var $jquery = jQuery.noConflict();")) :debug t) First let's note that this will include these dependencies in the "HEAD" of every page. If you want to have per-widget dependencies Weblocks does support that by (if I'm not mistaken) defining a widget-public-dependencies method specialized on that widget. Since we only have one page in this app anyway we'll just list them here. We've done that by adding entries to the dependencies list that use Google's CDN to supply the minified jQuery and jQueryUI libraries along with a stylesheet for the jQueryUI stuff. We added the :hostnames argument which specifies that requests to any host besides those listed are to be ignored. This is particularly helpful if you're running multiple webapps off of one server but want them to share a Lisp image and port rather than fire up separate Hunchentoot servers for each one. Additionally, we're inlining the js code that calls jQuery.noConflict() in the header because Weblocks uses prototype and scriptaculous out of the box and jQuery will happily steal the$ global variable from Prototype which causes all sorts of havoc. While there is interest in removing the prototype and scriptaculous dependencies it hasn't happened yet. It would be greatly appreciated if any developer felt like taking a little time to tackle this.

So now that we've included the JS code, let's write a presentation. The presentation lets us add the code :present-as (calendar) to a slot in our View and have it render as a calendar. This presentation will be a little different as we're using Leslie's new form-widget code. A more traditional coverage of presentations can be found in this blog post. Create a new file in the src directory called calendar.lisp and insert the following code:

### The Linux Distro and Programs

Any Linux distribution should be suitable for lisp web server duties. Personally, I would lean towards Archlinux as their default install is quite lean and they keep very recent versions of SBCL(1.0.42), CMUCL(20a) and others packaged. There's even a CCL AUR package (Archwiki AUR article) maintained by Leslie Polzer. Whatever distribution you wind up using to follow along with this series I recommend you also install screen, emacs, sbcl and lighttpd with your package manager. You should also grab the VCS pentafecta of darcs, git, mercurial, subversion and cvs.

### Setting up Emacs and SLIME

Note that there are many other, probably better, Emacs+SLIME tutorials out there. Since the original writing of this article, Quicklisp has become the dominant method for acquiring Common Lisp libraries. Instructions for its use are here and the clbuild instructions are maintained below for posterity. First grab quicklisp with curl -O http://beta.quicklisp.org/quicklisp.lisp then load and install it by running sbcl --load quicklisp.lisp, followed by evaluating (quicklisp-quickstart:install), (ql:add-to-init-file) and (ql:quickload "quicklisp-slime-helper"). Finally, add (setq inferior-lisp-program "sbcl") and (load (expand-file-name "~/quicklisp/slime-helper.el")) to your ~/.emacs.

Alternate clbuild instructions
The first thing to do is grab clbuild. At least until quicklisp is released, clbuild will remain the easiest way to get all the necessary lisp libraries to get cranking on web development in linux. I like to keep clbuild in ~/builds but place it where you like. Download it with darcs get http://common-lisp.net/project/clbuild/clbuild. Then cd into the clbuild directory and make it executable by running chmod +x clbuild. I'd also add the directory to your path in .bashrc or add an alias like alias clbuild='/home/redline/builds/clbuild/clbuild'.

With that done, it's time to start grabbing libraries. First, get SLIME by running clbuild update slime. Then you'll want to run clbuild slime-configuration and stick that in your ~/.emacs file, taking care to change the (setq inferior-lisp-program "/home/.../.../clbuild/clbuild lisp") to (setq inferior-lisp-program "sbcl") or "/usr/bin/sbcl" or whatever is appropriate.
End clbuild-specifics

At this point you should be able to ssh into your development server, run emacs -nw (for no-window-system/terminal mode) and then type M-x (alt-x) slime and enter to get to a lisp prompt.

### Getting the Lisp Libraries

After talking with Leslie a bit, I'll be using weblocks-dev over weblocks-stable. Weblocks-dev use is encouraged over stable at this time. Quicklisp uses weblocks-dev already and makes this insanely easy, just evaluate (ql:quickload 'weblocks). Done.

clbuild specifics
If you'd like to use weblocks-dev, open /path/to/your/clbuild/wnpp-projects in your favorite text editor and change the following:
1) Find elephant and change it's darcs repo from blah/blah/blah/elephant to blah/blah/blah/elephant-1.0
2) Find weblocks and change it's hg repo from http://www.bitbucket.org/skypher/weblocks-stable/ to http://www.bitbucket.org/S11001001/weblocks-dev/
3) Find cl-prevalence and change it's repo to cl-prevalence get_hg http://www.bitbucket.org/skypher/cl-prevalence/
Then run clbuild update weblocks and, if prompted about whether or not to download dependencies, enter 'y'. Let it work it's most excellent magic.
End clbuild-specifics

### The Framework Selection

There are a multitude of ways to do web development in Common Lisp. There are web servers such as Araneida and Portable Allegroserve (both effectively unmaintained), Hunchentoot (which is dominant in the way *Ediware* often is), Apache with mod_lisp, relatively obscure or undocumented combination server/frameworks like Antiweb, Symbolicweb/SW-HTTP and Teepeedee2 and frameworks like Weblocks, UCW and RESTAS.

I wanted something relatively commonly used and well-documented but I wanted a framework as opposed to just using libraries like CL-WHO, Parenscript and Postmodern on top of hunchentoot. Since UCW already has a blog series and I've worked with Leslie on Paktahn a while, Weblocks was a natural choice for me.

### The App Setup

I already run a wordpress blog and some other stuff on a lighttpd server on my Linode. Consequently, it made sense to just map a subdomain to my lisp experiments and leave the rest alone. To do this with lighttpd, add the following to /etc/lighttpd/lighttpd.conf:
$HTTP["host"] =~ "testbed.redlinernotes.com" { proxy.server = ( "/" => ( ( "host" => "127.0.0.1", "port" => 4242 ) ) )} Now you wouldn't want your webapp to not restart if you had to reboot the server would you? Of course you wouldn't. I've taken a cue from Xach and daemonized it via screen as follows: Open /etc/rc.local in your favorite text editor and insert a line similar to su redline -c 'screen -d -m -S screenslime -c /home/redline/webapps/screenrc'. This will ensure that the redline user starts a screen instance in detached mode with the name "screenslime" when the system boots that will use /home/redline/webapps/screenrc as it's configuration. If you don't know what any of that means, don't worry. It means screen is cool and you want it. Now, you should add something like the following to whatever file you listed as your screenrc: chdir /home/redline/projectsscreen emacs -nwscreen sbcl --userinit /home/redline/.sbclrc --load /home/redline/webapps/init.lisp This will ensure screen defaults to the /home/redline/webapps directory, starts an emacs instance in no-window-systems mode in screen window 0 and starts sbcl loading your .sbclrc and a lisp init script for your webapp(s) in screen window 1. Next, we need to actually write the init file for your webapp. For now, it will be quite simple as I'm just playing with weblocks. In the next article, we'll build something (probably un) interesting. In your init.lisp file (or whatever you called it) insert something like: (ql:quickload '(weblocks swank))(setf swank-loader::*contribs* '(swank-c-p-c swank-arglists swank-fuzzy swank-fancy-inspector swank-package-fu))(swank-loader::loadup)(swank:create-server :dont-close t :port 4010 :coding-system "utf-8-unix") This will ensure weblocks loads and swank serves on port 4010 so that we can use SLIME to connect and work on the running system. Note that you could've also put (load "/path/to/my/.sbclrc") or inlined the following as the first line(s) in your init file and avoided the --userinit portion of the sbcl invocation in screenrc. My .sbclrc simply points sbcl to the clbuild libraries like so: (require 'asdf)(setf asdf:*central-registry* '("/home/redline/clbuild/systems" *default-pathname-defaults*)) Unless you're using clbuild, you won't need this in your .sbclrc but if you are it's important that you do this so that sbcl can find the lisp libraries we downloaded with clbuild. If you don't, it'll be looking in ~/.sbcl/systems. Finally, I would also add a bash alias to your ~/.bashrc to get you right back to where you were with screen+SLIME. Mine is alias webslime='screen -dR'. I also added stty -ixon to my .bashrc as detailed in my last post because screen was capturing keystrokes I wanted sent to emacs. Xach pointed out that this could be toggled in screen with C-a C-f but I preferred having it as a default. See, now that was mostly painless, wasn't it? Next time I'll cover the basics of weblocks and develop a simple starter application. Or if I'm feeling particularly lazy, maybe I'll just walk us through the simple-blog example-app. Cheers. # Paktahn 0.9 is out! posted on 2010-05-18 18:16:40 Well, it's been a long spell since the last paktahn release. There are reasons for it but I'm just glad we got the release out. The "big feature" of the release is AUR updates which I am happy to have implemented. I wouldn't have been able to get it done if versioning support hadn't been kicked off by Wei Hu (wh5a) a while back though. At any rate, AUR Updates are in as is support for the .tar.xz format which Arch has adopted for packages going forward. Beyond that we have a new contributor to the project, Justin Caratzas, that I've enjoyed working with and hope to work with more in the future. Justin fixed a bug in how AUR packages were installed regarding whether or not they were installed as dependencies. I should have more time to hack on paktahn this semester than last semester so hopefully there won't be a commit gap for 2 months like there was before. I'm already looking at features for 1.0 and my biggest priority is reworking the command-line option handling using astine's unix-options and then extending paktahn to support pacman's -Syu, -Sy and -Su. Then I wouldn't ever need to call down to "regular old" pacman. Other than that it might be nice to get support for Paktahn on CCL or ECL and a test suite written. CCL support is complete save catching Ctrl+C and offering restarts as appropriate. There isn't exactly a clear path to implementing said support... Anyway, if you're a user and you find a bug or want a feature, head for the issues page and let us know about it! # LIMIT and OFFSET in Postmodern posted on 2010-04-25 17:58:09 I've been using the Postmodern library in Common Lisp to access PostgresQL databases of late and it's been a pretty good experience. That said, I had a little trouble using LIMIT and OFFSET to get DAO objects and wanted to put an example online in case anyone else has trouble with this. Future Postmoderners, May Google protect you. You'll want to use query-dao instead of select-dao and wrap the limit around a select statement. It winds up looking something like this: (query-dao 'card (:limit (:select (:distinct 'name) :from 'card) 10 0)) In this example, we're selecting the first 10 rows (that are distinct by name) from the card table. Obviously, you could use '* instead of (:distinct 'name) to select from all rows. That's not much of a post but here it is. Once I'm through finals I'll try to start posting a bit more regularly. Then again, I'll be moving once in May and once in June so we'll see what happens. # A Brief, "Postmodern" Shout-out posted on 2010-04-12 01:11:48 Things have been crazy lately but I'm not here to give a full update. I will say that there's been good with the bad, family, friends and supporters all the while and that the bad is mostly the usual bureaucratic and financial troubles that are just a part of life. I'm trying to post more regularly. Today is a brief programming post. This semester I've been taking a database course and we're building a small, silly webapp as the final project. The course uses SQL+PHP and I asked my professor if he wouldn't mind if I used SQL+Common Lisp. He accepted and so I've been using the Postmodern library for Common Lisp to talk to my Postgresql database. Postmodern has been really nice to use so far but there's one thing that I had a little trouble with that I'd like to document here. Generally, if you're writing classes in Lisp you're using CLOS and an example might be something like this: (defclass user () ((username :initarg :username :reader :username) (password :initarg :password :reader :password) (salt :initarg :salt :reader :salt) (email :initarg :email :reader :email) (first-name :initarg :first-name :reader :first-name) (last-name :initarg :last-name :reader :last-name) (zip :initarg :zip :reader :zip))) Postmodern has a nice method for interacting with the database via class definitions that it coins "Database Access Objects". Note that DAOs neither are nor attempt to be a full ORM solution, a very sane decision in my humble and inexperienced opinion. Anyway, to make a normal class into a DAO class is easy, just do this: (defclass user () ((username :col-type string :initarg :username :reader :username) (password :col-type string :initarg :password :reader :password) (salt :col-type string :initarg :salt :reader :salt) (email :col-type string :initarg :email :reader :email) (first-name :col-type string :initarg :first-name :reader :first-name) (last-name :col-type string :initarg :last-name :reader :last-name) (zip :col-type integer :initarg :zip :reader :zip)) (:metaclass dao-class) (:keys username)) All you have to do is add col-types to each slot so the system knows what type is stored in the database rows, list the components of the primary key and declare it a member of the dao-class metaclass. With that done, you can easily work with CLOS objects and fairly seamlessly select, update, delete or instantiate+insert them into the database. Creating the table itself can be done as follows: (execute (dao-table-definition 'user)). However, this is really intended as a shortcut for cases where you have a simple table definition. Say you wanted to allowed users to own collections of things, maybe collectible cards, and track those in the database as well. You ought to have foreign key constraints on the database so that collections couldn't be owned by users that didn't exist or consist of cards that didn't exist or were made up. In the case where foreign key constraints are desired or other more complex checks should be made, the preferred method is to write a deftable definition in addition to the class and then create the table with (create-table 'class) or (create-all-tables) if you have several tables. This would make for nasty code duplication since you'd still need a dao-object class to interact with the tables as nicely as possible. Thankfully, there's a macro to clear the situation up and import the simple parts from your dao-class specification. A possible deftable for the collection class might look like this: (deftable collection (!dao-def) ;; Import the existing info from the dao-class definition. (!foreign 'user 'username) ;; Ensure that the username that owns the collection exists in our user table. ;; Ensure that each card in a collection has a name and edition corresponding to a card in our database. (!foreign 'card '(card-name card-edition) '(name edition))) Of course, if your tables are already created and you just want to access them or you want to create them at the psql prompt, you don't care about any of this. Hmm...I guess that's supposed to go at the top. Anyway, a more careful and thorough reading of the documentation would've shown me this but examples are nice and here one is in case anyone googles around for it like I did. As far as I can tell, this is the preferred current approach for table creation. Corrections welcome and thanks to Marijn Haverbeke for writing postmodern. It's been wonderful so far. # Paktahn 0.8.2 and other news... posted on 2010-01-14 04:36:33 The last week has been thoroughly insane in ways both good and bad. As a gift, I had my thoroughly aged Nokia 6010 replaced by a shiny new Nexus One. Much as I would've liked an N900 they aren't subsidized by any carrier and so will remain out of my price range. I've also switched service to T-Mobile and thus far been quite satisfied. Then again, coming from a phone without a data plan I have no way of evaluating the 3G I'm getting. The holidays were good. I have a skateboard again so when the weather clears up I can get back to enjoying that. Time with mom was really good as was some peace and quiet and time to reflect. I took the opportunity to discover some new music as I usually do and also to read two novels by Vernor Vinge that I thoroughly enjoyed: A Fire Upon the Deep and A Deepness in the Sky. Careful, those wiki links have spoilers. As for the music, I've considered compiling a top 5 favorite albums of 2009 list but haven't gotten around to it. Besides, last.fm should tell you most of that. I will say I've been deeply enjoying Jon Hopkins, Ametsub and Minus the Bear this week. It's kind of an odd mix. Moving on, I got back into code last Tuesday after a long holiday absence. I really needed the break to recharge. 2009 was a full year. I spent the bulk of the second half of last week and the weekend writing code, reading code or screwing around with configuration files...which are all things I enjoy a good bit. Over the break I had fooled around with a new window manager (StumpWM in lieu of XMonad) and started using clbuild instead of asdf-install. I also spent a little time adding a lot of projects to clbuild in case I felt like playing with them. In the course of all this fiddling, I made a fresh archlinux install in a new partition with essentially nothing but Lisp and C compilers, a tiling window manager, Chromium, Emacs and a music player. To some degree, I'm fleshing it out still. It's a dumb diversion but every now and then I just have to rip my system up a little. It's hard to explain. On Sunday, after 3 months of work Leslie and I finally made the Paktahn 0.8.2 release. For all intents and purposes, the wait was worth it. A lot of new features and fixed bugs are present but there is still so much on my Paktahn.todo list. And of course there are bugs to fix. It's hard to explain why I'm so invested in Paktahn. Part of it is the work I've put in to date, part of it is how pleasant it's been working with Leslie and how much I've learned. Another large part is that there is great joy in having written some part of my day to day software and having a (relatively) deep understanding of it. It's kind of silly because AUR Helpers are a dime a dozen (or two dozen) but I'm still having fun. The Paktahn release was not without some drama though. Almost immediately after the release I started having odd issues building paktahn with sbcl. The resulting executable would exit as soon as you ran it complaining of a fatal error and a lost gc invariant. Not what you want to see. The bad thing was the error was intermittent and I couldn't isolate the cause. I had issues with it in my old archlinux install as well as the new one, with old and current checkouts of my code and with a checkout of Leslie's tree. I'm pretty sure I tried it with a fresh, recompiled sbcl and also tried removing all fasls and recompiling. I got very confused in the course of all that trying to figure out what happened. I should've been taking notes. At this juncture, it builds fine again and I can't get it to act up. :( Ah, well. At least I can get back to developing. It certainly gives me some impetus to finish the CCL port I started Dec 28th. So on to school this semester. I'm interning at a company called Kloudshare and have begun work on open sourcing a portion of their code. It's good fun and I hope to have more to share on that note very shortly. The administrative person I spoke with before break failed to get the internship registered in SPSU's system though so I spent a good deal of Tuesday getting that worked out with her. Then I had the unpleasant experience of learning that online courses are *substantially* more expensive than offline ones. Apparently, the state doesn't subsidize them because they can be taken advantage of by anyone or something like that. In my case, I was just trying to avoid an hour and a half commute both ways and try to find more time to code. I guess you really can't have it all. Now I have to jump through more financial aid hoops. Joy. Soon I hope to have some code to show here. Maybe I'll spend 10 minutes and just throw my dotfiles up on github for the hell of it tomorrow. Other than that...I miss long form writing, poetry, essays...but my focus is elsewhere. Plus I'm tired. The rest will have to wait for another day. # Since Last Time posted on 2009-10-19 23:04:56 Well, it seems a lot has happened since last time. An additional lisp library for concurrency called Calispel has been released and is up on Cliki. Unfortunately, it depends on cl-jpl-utils which in turn depends on cl-rsm-queue, neither of which are on Cliki. Such is life. There are good things though, a release candidate for CCL 1.4 has been put out. I've also started a branch porting Paktahn to Embedded Common Lisp. It didn't wind up being as tricky as I thought. Hopefully, I'll have something I can merge to master in a week or two. Of course, I wouldn't have gotten anywhere without Leslie. Geez, that guy is patient. Anyway, what about non-lisp news? The ACM Reflections conference is over and hopefully videos will be posted soon. Additionally, there's been some discussion about whether or not it's time for Factor 1.0. There's still really great work being done on the language implementation. I would like a proper book for it and binaries to be available in my linux distro but I can wait. There's also been a good discussion on what math programmers need to know on reddit recently. The outstanding comments (IMO) are here, here, here and here. Similarly, there was a good thread a few weeks back titled "What do you wish you knew when you started programming?". A few of my favorite comments are here, here, here and here. More importantly, there was a very enjoyable article and followup about Office Politics as interpreted by Hugh MacLeod and The Office. As some folks in the hackernews thread mention, the model isn't universally applicable. Yep, that's right. It's a model. Go figure. Well, it's been a very hard week. Mostly because I just hate my Algorithms class. I don't hate algortihms just the way it's being presented and taught. I'm pretty sure I can overcome the obstacles involved, I'm just much less motivated to do so than I would like. The last two semesters I really had a fire under my butt about school for some reason. Maybe not but when I had to rise to the challenge, it was relatively easy to do so and I was kind of proud of that since it was a divergence from my past. This semester the fight just isn't in me and I have next to no pride in what I'm doing in school. I'm sort of coasting and I'm finding it hard to break out of that. Of course, I'm learning the material and I'm doing extracurricular things to improve my knowledge, joy and understanding because I care about programming. Whether that's stupid or not is another question but also kind of irrelevant, I didn't choose to be fascinated by this stuff. I just can't help it. So I'm not doing what I love, I'm doing what I can't help but do. It's gonna be a long road. I've still been getting a few things done. I've written a few quick hackish, sbcl-dependent scripts. Maybe I'll post some of the code for them soon. I started working on Redlinux again. The last release I made was back in May and a lot has changed since then, more about my approach than about Redlinux. I'm hoping to make a new release by the end of November. So far the big change is my build process. As in, now there actually is one. It should be trivial to rebuild from scratch in the future. See what a non-distribution it is? The upcoming release should have a nice proper script for creating a new user and doing a little initial setup. Above and beyond that, I'm hoping to work on the documentation some. If anything, the real problem is it may not fit on a single CD with all the programming software I've bundled in. A while back I wrote a post on getting an undergraduate CS education for under$1,000. It was mostly focused on which books and resources were ideal for self-study. I reworked said list and posted it on Amazon over the weekend. A lot of my decisions about what's worthwhile for self-study has changed (since I've actually read more). My motivation stems largely from the fact that I prefer self-study to school. Finally, there are two slightly older articles of mine that linked to a bunch of really interesting articles that are still among my favorite blog posts I've stumbled upon since trolling the internet for programming stuff. I'm hoping to do a real writeup on a number of these articles and add in a few of my own ideas in the near future. And since I'm calling it "the near future" you know advance I'll never get around to it. Well, hopefully not. :)

That's all for now. Back to homework guys.

# Just a Feeling

posted on 2009-10-13 23:33:16

Last time I blogged, I was midway through midterms and just starting to work on some lisp projects. It's hard to imagine that was only a week ago. Since then, midterms are over, I've realized my only difficult class is Algorithm Analysis (the nature of whose difficulty I've blogged about before) and become an official Open Source contributor. Admittedly, it's on a small scale but when I was just getting interested in open source a few years ago I never would've figured this would happen so soon. It's been a great learning experience so far and incredibly fun. I still need to get started working on adding libvorbisfile bindings to Andy Hefner's Mixalot but today I'm going to try to dump some links out of my browser, get some thoughts down and do some Algo homework.

I mentioned recently that I've been wanting to write a lisp post but been unsure what to focus on. I've wanted to respond to posts made by others in various places over the last few months asking about the liveliness or validity of lisp as well as whether the language is still changing or whether the departures of prominent Common Lisp users matters (search for the second occurrence of "norvig"). Experienced lispers might just ignore that question at this point, I don't know. It does come up far too often. For my part though I want to try and address this because I know the more attention I've paid to the lisp community, the more I've seen how active, alive and, most importantly, friendly it is. It's been a little surprising in some ways compared to the false preconceptions one can get from blog and reddit chatter. Now, it may be undermanned. There's certainly more work to go around than people to do it but that's true of many places. Anyway, I simply have to get some of this out of my system. Here are a few thoughts...and links.

First of all, just this morning I poked around for libraries on concurrency and parallelism and found the following: erlisp, erlang-in-lisp (which may become active again, who knows), cl-future, csp, pcall, eager-future, cl-muproc, cl-stm, chanl, patron, philip-jose, cl-mpi, cl-cluster and, of course, the distributed schemes Termite and Gerbil. Poking around for GUI libraries I quickly found: cl-gtk2, ltk, mcclim, commonqt, celtk, cells-gtk3, cl-smoke, cello, wxCL, cells-gtk, lisp-tk, clg, and cl-ncurses. Even cl-ncurses has seen some recent activity! :)

Now I grant some of these libraries are unmaintained and others are code stubs that never quite got off the ground. But 6 of the concurrency libs were started this year and of those 6, 3 have seen code updates in the past 3 weeks. Of the GUI libs, the CommonQT and CL-GTK2 bindings have both seen commits in the last month. Sadly, the libraries are spread out all over everywhere from Cliki to Github to random repositories dotting the cyber landscape. There are many reasons the library situation isn't perfect but it isn't dead either. Just look at all the projects and work-in-progress-projects in clbuild! Moreover, there are discussions about what Lisp needs to move forward. Some of them involve CLtL3, a new standardization effort, and others involve infrastructure improvements, a central package respository for example. The talk is out there. Books are still being written, people are still working on the implementations and making releases, low level experiments are still being done even though the lisp machines are gone...well, mostly.

But mostly I just wanted to put this all out there for now. To celebrate the tremendous, if seemingly fractured, development and FUN people are having with this language. Because that's what I'm having. Fun. You want in on it? Then get ready to get your hands dirty.

# Keep It Together

posted on 2009-10-06 15:25:26

So, the last time I really posted a personal update I didn't have many good things to say. I was a bit depressed. But I seem to have climbed out of that hole. Midterms are mostly over and I have a much better feel for my classes with them behind me. The only one I haven't taken is the American Government midterm which I'll take tomorrow at 3pm. A decent amount of stress is off now that they're out of the way. I'm still a bit overextended. I'm pulled in many directions by a desire to do many things but I might as well be honest. I like it that way.

Particularly, I'm trying to contribute to two different pieces of Open Source Software. One is Mixalot, a suite of Common Lisp libraries for interfacing with Linux's ALSA sound sytem and playback of MP3 files. The other is Paktahn, a package management wrapper for Arch Linux which is meant to replace Yaourt. Paktahn is also written in Common Lisp. Notice a trend? I want to use Mixalot to work with Ogg Vorbis (*.ogg) files which it doesn't support. I told Andy Hefner I'd like to try and contribute some libvorbisfile bindings which would let Mixalot work with that file format. Unfortunately, that involves interfacing with C code which I don't know much about. It's definitely an order of magnitude harder than most things I've worked on before. Plus I've had exams...so I haven't gotten much done on that front yet. Leslie Polzer is writing Paktahn and he pointed me in the direction of a fairly straightforward, well-defined problem that needed solving. I got around to working on that and have made pretty good progress. With a little more work it may even make it upstream for the next release. That's wicked fun!

I've wanted to write a blog post on Lisp for a little while but couldn't narrow down what about Lisp to focus on. Lately I had been looking at mailing lists, documentation and source code repos for a lot of Common Lisp libraries. Perhaps what shocked me most was the realization that Lisp has plenty of work to go around for silly noobs like myself. There are all sorts of trivial little tasks all over the place that maintainers are too busy solving real problems to fix. And that's awesome! I can be very helpful probably to a wide number of different projects. Now, I don't know a lot and I don't have time to "help" near as much as I'd like...but I can still learn something and be of use. And I'm pretty happy about that. So Common Lisp: Have fun on the fringe, benefit from learning a non-standard language with some awesome features, be useful and get mentored by some smart folks. What's not to love? I'll try to post something more thoughtful about this later. But for now, all I have to say is that this is a really good thing and I can't wait to see where it takes me.

For now though, it's back to studying.

# Scripting with SBCL

posted on 2009-09-09 17:40:14

Over the labor day weekend, I had fun. I avoided dreary schoolwork, I played guitar, I hung out with cool people, I celebated my second anniversary with a lovely lady, I wrote code.

One bit of code I worked on is a script to read in AT&T call logs and figure out the 5 people you call most often. As you might guess, this can be useful for people contemplating switching to T-Mobile (say, for an upcoming piece of hardware designed for their 3G network). In short, the script is run from the command prompt with ./myfaves.lisp and prints out the 5 people you've talked to the most based on your call logs and the total percentage of your minutes those calls account for. The call logs this script processes can be downloaded from wireless.att.com. Login to your wireless.att.com account, go to "Bill & Payments". Under "Wireless Statement Summary" click the "Call Details" tab and finally scroll down a bit and click "Download Call Details". Using the dropdown box, select each month then click CSV format and submit. Put all those files in the same directory and then execute the following lisp script from that directory.

#!/usr/bin/sbcl --script(declaim (sb-ext:muffle-conditions style-warning))(eval-when (:compile-toplevel :load-toplevel :execute)  (let ((*standard-output* (make-broadcast-stream))	(*error-output* (make-broadcast-stream)))    (require 'asdf)    (require 'split-sequence)    (require 'osicat)    (require 'cl-containers)))  (defpackage :my-faves  (:use :common-lisp :cl-containers :osicat)  (:import-from split-sequence split-sequence))(in-package :my-faves);; ATT CSV info;; call logs start on line 24, entries on every other line (evens);; voice calls final line starts with "Totals";; 5th comma-entry is number, 7th is duration in minutes(defparameter *months* nil)(defparameter *results* (make-array 6 :fill-pointer 0))(defparameter *call-log* (make-container 'sorted-list-container					 :test #'equal					 :key #'car					 :sorter #'string<))(defun init ()  (loop for path in (list-directory (truename ".")) do    (let* ((pathstr (native-namestring path))	   (ext (subseq pathstr (- (length pathstr) 3))))      (when (string= "csv" ext)	(push path *months*)))))(defun find-faves ()  (loop for file in *months* do    (load-calls file))  (analyze-data)  (print-results))(defun load-calls (path)  (catch 'load-calls    (with-open-file (in path)      (loop for i from 1 to 23 do	(read-line in nil))      (loop for line = (read-line in nil) do	(parse-call line)))))(defun parse-call (csv-line)  (cond ((string= "" csv-line))	((finished-voice csv-line) (throw 'load-calls 'done))	(t (let* ((split-line (split-sequence #\, csv-line))		  (number (fifth split-line))		  (minutes (parse-integer (seventh split-line))))	     (insert-call-sorted number minutes)))))(defun finished-voice (csv-line)  (string= "Totals" (subseq csv-line 0 6)))(defun insert-call-sorted (number minutes)  (let ((present (search-for-item *call-log* number :key #'car)))    (if present	(incf (cdr (search-for-item *call-log* number :key #'car)) minutes)	(insert-item *call-log* (cons number minutes)))))(defun analyze-data ()  (ensure-sorted *call-log*)  (sort-elements *call-log* #'> :key #'cdr)  (loop for number from 0 to 4 do    (vector-push (item-at *call-log* number) *results*))  (let ((total-free (loop for i from 0 to 4 summing (cdr (aref *results* i))))	(total-mins (reduce-elements *call-log* #'+ :key #'cdr)))    (setf (aref *results* 5) (round (* 100 (/ total-free total-mins))))))(defun print-results ()  (format t "AT&T -> T-Mobile myFaves Recommendations:~%")  (format t "-----------------------------------------~%")  (format t "According to our analysis of your call logs, these are your 5 most frequently dialed numbers.~%")  (format t "-----------------------------------------~%~%")  (loop for i from 0 to 4 do    (format t "~A whom you spoke to for ~A minutes.~%~%" (car (aref *results* i)) (cdr (aref *results* i))))  (format t "These numbers should be your myFaves as they accounted for ~A% of your total minutes.~%" (aref *results* 5)))(init)(find-faves)

I'm sure it's not the prettiest, lispiest code out there but it could be an awful lot worse. Also, sbcl emitted style-warnings when the script was run. This behavior surprised me a little bit. After all, if I'm running the script I have little need for the style-warnings. After some digging, I learned enough to write this patch for the program which suppressed the undesirable output. I hope to submit a patch to the SBCL manual in the next week or so that notes this may be desired as nothing on the current page regarding sbcl --script would indicate that any output from the compiler would appear.

# Quick Code Post

posted on 2009-08-25 20:04:17

I'm hoping to get back on track with my blogging (and following other folks blogs) in the next few days. I wanted to post this code real quick though before I forget about it. I've had a lot of fun playing with lisp lately and have written...4 silly, small scripts in the last week.

- The first goes through 12 months of CSV call logs from AT&T to find out the 5 people I spend the most minutes talking to.

- The second recurses through a directory running an external program to find the bpm on each one and logging the difference from the current BPM in id3 tag to a file. It's 90% done, I just have to clean up some of the output parsing from the external process. Very rarely, my cl-ppcre regex doesn't match. Silly corner cases.

- The third takes a directory of 20 or fewer *.ogg files, maps them to keystrokes and I'm working on a simple loop so that they play in a spawned "ogg123" whenever I press said keys. The main hold-up at present is that (read-char) blocks while waiting for a #\Newline and (read-char-no-hang) gave me some other error I forgot.

More on all that later. Some M3U files (playlists) I had laying around weren't importing into a different mp3 player. The reason? They weren't using absolute pathnames. My solution was hackish but I coded it, fixed them and moved on with my life in about 3-5 minutes. Hard to argue with that. And the code:

(defpackage :fix-m3u  (:use :common-lisp))(in-package :fix-m3u)(defun fix-m3u (path)  (let ((new-m3u (make-array 16 :adjustable t :fill-pointer 0)))    (with-open-file (in path)      (loop for line = (read-line in nil) while line do	(let ((abspath (concatenate 'string "/home/redline/music/" line)))	  (vector-push-extend abspath new-m3u))))    (with-open-file (out path :direction :output			      :if-exists :supersede)      (loop for line across new-m3u do	(format out "~a~%" line)))))

# Silly Slime

posted on 2009-06-11 18:00:40

Recently, SLIME has been acting funny. I think it's since an archlinux update but I hadn't had time to look into it. When I used the ~ key in the SLIME editor window (not the REPL) was causing some debugger error. So if I wanted to write a format string like "~a~%" then I was hosed. So...today I got fed up with it and using Emacs C-h k found that the key was invoking the "slime-sync-package-and-default-directory" function. Googling seemed to indicate this function was normally bound to "C-c ~".

At any rate, it shouldn't be bound to "~" so I went to the slime site lisp directory and ran grep -r "slime-sync-package-and-default-directory" *. Among the results was this:
contrib/slime-repl.el: ("~" 'slime-sync-package-and-default-directory))
Aha. So the simple fix was changing the "~" to "\C-c ~". All seems to be well now...but what an odd thing to have to fix in the first place. *shrug*

Back to studying for Data Structures...and maybe lunch.

# Lisp is Lovable

posted on 2009-05-27 15:59:11

I'm about to run to class but I thought I'd throw up a Lisp solution I coded to the Funny Words problem which I worked through in Haskell earlier. I used sb-ext:save-lisp-and-die thanks to a helpful guide to dump a core image and used unix's time command to time it. The output of time ./funnyWords.core english-words.txt was as follows:
real 0m4.053s
user 0m3.913s
sys 0m0.057s

That's significantly shorter than the corresponding Haskell time and I wonder why. This code is a lot more imperative but I'm curious exactly where the speedups are. By the way, LOOP is awesome. As for the differences, I'll spend time sorting it out when I have time later. NOTE: solrize posted an improvement to my Haskell code that made it run in umm...half a second? Less? The main speedup seemed to be coming from using Data.Map and using the sort of each word as the key during insertion. That way, you get isAnagram for free, among other things. If you have thoughts on this code or the earlier Haskell code, where the differences lie or how to make them lispier or haskellier please let me know! :) Here's the code:
;; how to find words like cosmicomics:;; words which can be split into anagrams by the middle letter;; PRESENTLY ASSUME THAT ALL WORDS ARE LOWERCASE! how can we type/test for this?(defparameter *dict* nil)(defparameter *results* nil)(defparameter *file* nil)(defun main ()  (let ((*file* (or (second *posix-argv*)		    *file*)))    (funny-words *file*))  1)(defun funny-words (wordlist)  (let ((result nil))    (with-open-file (in wordlist)      (loop for word = (read-line in nil) while word do	(push word result)))    (setf *dict* result))  (mapcar #'partial-find *dict*));;  (concat-map #'partial-find *dict*))(defun is-anagram (word1 word2)  (string= (sort (copy-seq word1) #'char-lessp)	   (sort (copy-seq word2) #'char-lessp)))(defun has-joiner (word1 word2)  (let ((strlen (- (length word1) 1)))    (char= (elt word1 strlen) (elt word2 0))))(defun is-funny-word (word1 word2)  (and (has-joiner word1 word2)       (is-anagram word1 word2)       (not (string= word1 word2))))(defun build-word (word1 word2)  (concatenate 'string word1 (subseq word2 1)))(defun same-length (word lst)  (loop for item in lst	when (= (length word) (length item))	  collecting item))(defun partial-find (word)  (loop for item in (same-length word *dict*)	when (is-funny-word item word)	  do (let ((answer (build-word item word)))	       (push answer *results*)	       (print answer))));;(defun concat-map (f lst);;  (loop for item in lst appending (funcall f item)))

# Mercurially Me

posted on 2008-10-23 05:34:39

Something non-techy for starters, Don Gerz has posted three separate entries about Alan Moore's Watchmen in the last week. In two days, actually. And (perhaps due to my prodding) Kris Osterhage threw up a post mentioning his Watchmen experience among other things. It's fun. Maybe I should try to re-read it and write a nice essay before the movie comes out in March.

I haven't been getting quite enough done lately but what else is new. I have been learning some good things and as always there's good stuff coming down the pipe. I've banged out the features I thought my version of hangman was most lacking, a real word-list\dictionary and a fix for a bug I may not have mentioned. If a letter occurred more than once in a word (i.e. "o" in "cook") and was guessed only the first instance of the letter would show up. Those fixes are committed and I'm moving on to things like the cleanup suggestions Xach made and then who knows.

Finishing PCL is probably next on the priority list. I took some crappy notes which I keep telling myself to turn into a "Common Lisp for Schemers" series of articles but I haven't gotten around to it. Maybe because I'll just embarass myself but that's what the internet is for so I'll probably do it anyway. I've also been wanting to finish the Picture Language stuff in SICP 2.2. But whenever I try to load the SICP module in DrScheme my CPU utilisation goes through the roof and it just sits there for a while. Personally, I'm not one for waiting as this seems to happen with any module on PLaneT. It's probably just me though and I'm willing to look into it more later. There are some .scm files for MIT-Scheme on the SICP site and I'm still considering what to do.

Also, I've been peeking at Scheme implementations again. I'm still fond of the massive concurrency option of Gambit/Termite and I like DrScheme for it's strong community and many good features...but my heavens, Chicken Scheme is armed to the teeth with eggs. Is it even for real? That looks like fun to me. Implementation surfing is a dangerous distraction when you should be writing code though. I'll worry more about scheme implementations when I bang out a x86_64 edition of RedLinux before college starts (hopefully in the Spring). I'll write more about that tomorrow but I've been worrying about my upgrade path for a while now and going back to school has brought some of those issues back to the front for me. My laptop positively refuses to get on a secured wireless network. Now, that's probably something to fix with a usb wifi card or something but the battery life is also under an hour. I'll just say I've been thinking about it a lot and come to some conclusions.

Additionally, OOPSLA and Lisp50 just wrapped up. I really wanted to go but I wouldn't have been much more than a fanboy at this point and my funds were limited. Hopefully videos of a few talks and more blogging on the conference will trickle out. The clatter about clojure continues to grow too. It's something worth keeping an eye on no doubt.

Last but not least, more mercurial fun tonight. What you didn't guess from the title? I found two good sources on Mercurial today. The first was a general mercurial guide and the other dealt with emacs integration. On to some quick tips.

Let's assume you forgot to setup your username in .hgrc and you've just fired off the old add-commit. You haven't pushed (and we'll assume no one had the ability to pull) yet so no one has to know about your silly mistake and crazy machine name. Just run hg rollback to eliminate that last commit but be forewarned that you can't rollback a rollback. For simpler cases where you've added, removed or something similar but haven't committed yet just use hg revert. You can also use hg revert filename to undo changes to a particular file.

Also, I'm enjoying using mercurial.el in emacs. Just drop mercurial.el into your emacs/site-lisp directory and (require 'mercurial) into your .emacs file. C-c h s does hg-status and C-c h c will start a commit but allow you to unmark any files you don't want to commit before doing so. C-c h a is hg-add and C-c h U is hg revert, C-x v u being for the current file only. C-c h < works as hg-pull and C-c h u is hg-update. Finally, C-c h > is hg-push. There you have it folks. Mercurial in a paragraph. I'm a bit tired so that's all for tonight. See you tomorrow.

# Hangman's Hope

posted on 2008-10-17 08:02:04

The last week has been really, really hard. Mostly because I've been confronted with something I hoped wouldn't have to happen: The necessity of returning to academia. I've applied to a few more jobs and we'll see what happens there. I got turned down by King & Spalding in a letter today and am going to call tomorrow and ask why. I'm really just not getting enough done on my own to justify being out of school. I'm not learning enough. Perhaps I do need the structure. I'm disappointed but I have to re-evaluate based on my experience. State changes and given my present state I'm looking at returning to SPSU in the Spring or Fall of next of year. There's some notion of transferring to GA Tech as well but I'm not sure what I think about that.

One nice thing about SPSU would be that I'd at least have the spare time to continue pursuing LISP and other personal studies. It's also worth noting that a significant motivation in this year off was to at least get the fundamental concepts of programming down some before being buried in the specifics of the monstrous languages used to instruct most Freshman in Computer Science these days (i.e. Java; pythonistas at Tech, you're lucky).

Anyway, tonight I was frustrated with the fact that I hadn't written any code in a long time and I hadn't written a real program of my own in an even longer time. For one reason or another, implementing Hangman in Common Lisp seemed like a good idea. Now, I'm not claiming that hangman is ever any great feat...except maybe if you write it in BrainFuck. Nor is it any great feat to write it in under a hundred lines. Worse still is that it lacks any ASCII art. That said, I did this in a few hours, found it pretty fun and think it came out fairly readable and concise in the end. After all, how couldn't it? It's hangman.

;; Hangman;; Brit Butler ;; v.01;; Feature Ideas: ASCII hangman. Eliminate explicit elt references and other hackish;; stuff, especially show-letter. Import dictionary in place of *word-list*.(defparameter *word-list* '("cookies" "kittens" "fairies"			    "unicorns" "words" "linux"			    "lisp" "music" "songs"			    "sex" "love" "fun"			    "code" "cease" "and"			    "desist" "read" "print"			    "eval" "loop" "macro"))(defparameter *turn-count* '())(defparameter *letters-picked* '())(defparameter *word-in-progress* '())(defparameter *solved-word* '())(defun hangman ()  (setf *turn-count* 7)  (setf *letters-picked* '())  (select-game-type)  (work-on-word))(defun select-game-type ()  (if (y-or-n-p "Would you prefer to have a word chosen at random?")      (set-the-words (elt *word-list* (random (length *word-list*))))      (set-the-words (string-downcase (read-prompt "Please input your desired word: ")))))(defun set-the-words (word-of-the-run)  (setf *solved-word* word-of-the-run)  (setf *word-in-progress* (make-array (length word-of-the-run)                                       :initial-element #\- :element-type 'character))  (format t "~a~%" *word-in-progress*))(defun read-prompt (query-string)  (format *query-io* query-string)  (read-line *query-io*))(defun check-letter (letter)  (if (already-picked? letter)      (format t "You already picked that goofball! Try again...~%")      (push letter *letters-picked*))  (cond ((is-in-word? letter) (show-letter letter))	((not (is-in-word? letter)) (decf *turn-count*)	 (format t "Nope. Not in there. ~a turns left.~%" *turn-count*))))(defun is-in-word? (letter &key (start 0))  (position letter *solved-word* :start start))(defun already-picked? (letter)  (position letter *letters-picked*))(defun show-letter (letter)  (setf (elt *word-in-progress* (is-in-word? letter)) letter)  (format t "~a~%" *word-in-progress*))(defun pick-a-letter (&key (message "Pick a letter please: "))  (let ((rtn (read-prompt message)))    (if (> (length rtn) 1)	(pick-a-letter          :message "We only need ONE letter thank you very much. Try again: ")	(check-letter (elt rtn 0)))))(defun work-on-word ()  (pick-a-letter)  (word-finished?))(defun word-finished? ()  (if (= *turn-count* 0)      (game-over)  (if (string= *solved-word* *word-in-progress*)      (play-again? "Congratulations.")      (work-on-word))))(defun game-over ()  (format t "Sorry. The word was ~a.~%" *solved-word*)  (play-again? "You're all out of turns. Game over."))(defun play-again? (message)  (format t "~a~%" message)  (if (y-or-n-p "Would you like to play again?")      (hangman)      (format t "Thanks for playing!~%")))

# Another Emacs/Slime Cheatsheet

posted on 2008-10-12 05:37:04

I've been picking up more and more Emacs and SLIME while working my way through Practical Common Lisp over the last week or two. I'm really happy with it as a work environment at this point but have tons left to learn. I haven't even written any elisp code to script it. Of course, I haven't had a need yet. I'll get there and I'll update this as I learn new things. I'll just note that I'm also quite attached to ArchLinux as my distro and, increasingly, Xmonad as my window manager. It's the first time I've felt really settled on an Operating System/environment since moving to Linux. Maybe ever. I'm pretty happy about it and aside from using RedLinux as a way to see what I like, I've posted all the config files here. Before the cheatsheet here's a quick Linux tip on killing processes I found. Try passing -1 or -9 to kill along with the PID. Try -1 first then -9 if all else fails. On to the cheatsheet.

EDIT: Yes, it's ugly. Piss off. I miss monospaced fonts already, I'm grumpy, I'm tired, it's 1:40 am and I haven't been up this late in forever. I'll fix it later. ;-P

;;Emacs Cheatsheet:

; C-7                         Undo.
; C-8                         Backspace.
; C-s                          I-search forward.
; C-v                          Page-down
; M-v                         Page-up
; M-<                        Beginning of document/file.
; M->                        End of document/file.
; C-l                          Center screen on cursor.
; C-n                         Next-line/Down-arrow
; C-p                         Previous-line/Up-arrow
; M-f                         Forward a word
; M-b                         Backward a word
; M-bksp                    Delete previous word.
; C-k                         Send a line to the kill ring. Cut.
; C-y                         Place a line from the kill ring. Paste.
; C-x C-f                    Find (or create) a file and open it in the buffer.
; C-x C-s                    Save the file in the buffer.
; C-x b                       Switches to a buffer. Type for a specific buffer or hit enter to go with the default (last buffer).
; C-x o                       Moves the cursor between windows.
; C-x 0                       Closes the current window if other windows exist. (Kill this window.)
; C-x 1                       Makes the current window the only window. (Kill all other windows.)
; C-h t                       Start the emacs tutorial.
; C-h k                       Prompts for a keystroke and tells what command it invokes.
; C-h w                      Prompts for a command and describes the keystroke it's bound to.
; C-h b                       Displays a list of bindings to various commands.
; C-u num command   Repeats the given command num times.

;; Slime Cheatsheet:

; M-p                                  Is the up arrow for the slime repl.
; C-c C-c                             Sends an s-expression to slime.
; C-c C-k                             Compile and load the file represented by the current buffer.
; C-C C-L                             Load a file in slime, defaults to the file in the current buffer.
; C-c C-z                              Pulls up the repl in a frame and moves the cursor there.
; C-c RET                             Runs macroexpansion.
; , quit                                 Kills the running inferior-lisp and closes all the SLIME buffers.
; M-x Slime-inspect               Run the inspector.
; M-x Slime-profile-package   Run the profiler.
; M-x Slime-profile-report      Check the profiler results.
; M-x Slime-profile-reset        Reset the profiler.

# Everything in the World

posted on 2008-10-12 05:08:07

I can't believe it's already October. It seems like only yesterday that I decided to take a break from school. For that matter, it seems like only yesterday that I became unemployed...but this was week 3 and a pleasant week it was. I'm continuing to try and buckle down and be more productive in various ways in spite of the fact that I don't really need money for another month and a half or so. So, what's been going on of late?

The Employment World: My interview with King and Spalding went pretty well. It was very straightforward and none of the technical questions were remotely difficult. By the sound of it, it will also pay more than my last job. That's a good and bad thing. It's good because a decent wage would be nice and my last job wasn't one in my opinion. It's bad because it may be more remedial than my last job. It's a little retroactively upsetting to realize that I'd be paid more here for what sounds like substantially less difficult technical work. We'll see. I also know it'll take a week or two before they let me know whether or not I'm on the list for an in-person interview. Thanks to everyone who asked about it and or wished me well. Devon and Don, I'm looking at ya'll.

The Education World: My friend Will keeps sending me awesome links to research, papers, sites and articles. I also had a fascinating conversation on schools and education with Oglethorpian Chris Latshaw and was reminded why I love Oglethorpe in the process. Conversations like those made the school worth it. I should get around to writing more about all that next week. Also, (to Will) I'm half-way through Practical Common Lisp and hung up on an element of the chat program. I'm being a sissy about e-mailing you questions. I'll write this one off soon, I promise but I'm just trying to wrap a sane Chat UI around the Spread library. I'll send more details soon. Finally, I've downloaded about 100GB of video lectures about coding and math this week. I spent an afternoon queuing them up and left it running a few days. Remember me complaining about everything being in Real Format? Well, I still won in the end. It wrapped up this afternoon. My apologies to the Internet Archive's Ars Digita mirror. They must feel violated.

The Linux World: The Linux Kernel version 2.6.27 was released Friday. Development will start on 2.6.28 now. I'm excited about 2.6.28 because I'm hoping btrfs gets pushed into mainline. That could take a little while but it's still fun. Also, this is the first time that release season has come around and I'm really not interested in Ubuntu or Fedora. Arch/RedLinux has me pretty satisfied.

The Code World: There are some really cool lectures at the S3 conference. I posted about it before because Dan Ingalls presented the Lively Kernel but at this point I'm also really interested in the STEPS project and Ian Piumarta's work. Partially because I'm really jealous of Luke Gorrie, again. And I hope that OLPC XO's really do become more reflective and Lisp Machine like. Beyond that, I stumbled on two web framework tutorials lately, neither of which I have the time to work through really. Sad. One is in Factor and the other is in PLT Scheme. Sexy!!!

The Friends World: Don Gerz has written a number of things that caught my eye lately. Particularly a piece about Kierkegaard. Lex has also written some provocative questions about Banksy. I hope she'll post her paper when it's done. She's also looking to try Ubuntu in the near future. Go lex! Kris Osterhage simply hasn't been posting enough. ;-)
Chris Blair wants this election to be over. I'm rather with him on that one.

That's most of it. I need to write up a cheatsheet for the emacs and slime commands I'm using and then 2 or 3 articles on the stuff about Common Lisp I've been learning. Maybe at the end of it all I'll go back and revise my positions from the Language Adoption and Lisp article. Other than that, I'm trying to get through Season 2 of 30 Rock before Season 3 kicks off at the end of this month and really enjoying the break from employment that I have. Now somebody hire me already! More soon, everyone.

# Funcalls and Fun w/Code

posted on 2008-09-29 17:49:22

Life: I have a part-time job interview tomorrow and I've gotten by so far through contract work. I'm also really enjoying not having a car. I've picked up some new tunes and am in guitar fingerpicking mode. I should learn how to myself, really. For now though I'm just listening to Kaki King and Andy McKee. Oh, and Calexico too. They're awesome. Moving on...

Techie stuff: I've pretty much completely switched to Xmonad. It's great and I've polished up my key layout and config for it. There will be some changes in that sense in my next RedLinux release (Fast Amazon download mirror and install guide here). For example, there won't be a Caps Lock key in my Linux. It will just be another Control key. It's not like you use it anyway, right? I'm also starting to finally get comfortable with emacs and slime. And Practical Common Lisp is a really fun and great book to pick up lisp. More on all that later. Here are some fun code snippets:

(dotimes (x 30)  (dotimes (y 30)    (format t "~3d" (* (1+ x) (1+ y))))  (format t "~%"))

(do ((n 0 (1+ n))       (cur 0 next)       (next 1 (+ cur next)))      ((= 10 n) cur))

Pop quiz: What do these two Common Lisp snippets do?
(reverse '(The first prints out a multiplication table up to 30x30. The second computes the 11th fibonacci number.))

And the first macro:
(defmacro do-primes ((binder lbound ubound) &rest expr)  (do ((,binder (next-prime ,lbound) (next-prime (1+ ,binder))))         ((> ,binder ,ubound))      ,@expr))

Sure it's useless but it makes sense and points the way to some great possiblities. Additionally, destructured lists like so are grand. That's enough lisp to bug you folks with for one day. Deuces.

# 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 realizeyou just implemented a fancy lambda version of repeated forfunctions/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.

# HTDP Section 04

posted on 2008-05-19 14:13:12

Well, here's Section 04.

Resources:
Watch: Nothing. To my knowledge there are no online lectures based around HTDP. Correct me if I’m wrong.
Checked against: Nothing.

Exercises

4.1.1:
1. (and true true) -> true
2. (or true false) -> true
3. (not false) -> true

4.1.2:
1. (a) true, (b) false, (c) true
2. (a) false, (b) false, (c) true
3. (a) false, (b) false, (c) false

4.2.1:
;;1.(define (is-between-3-and-7? n)  (and (> n 3) (<= n 10)));;2.(define (is-between-3-7? n)  (and (> n 3) (< n 10)));;3.(define (is-between-3-9? n)  (and (>= n 3) (< n 9)));;4.(define (is-1-3-or-9-11? n)  (or (is-1-3? n) (is-9-11? n)))(define (is-1-3? n)  (and (> n 1) (< n 3)))(define (is-9-11? n)  (and (> n 9) (< n 11)));;alternate implementation in case the first smacks of premature optimization:;;(both suffer from an ominous arbitrary function naming schema!)(define (is-1-3-or-9-11? n)  (or (and (> n 1) (< n 3))      (and (> n 9) (< n 11))));;5.(define (is-outside-1-3? n)  (not (and (>= n 1) (<= n 3))))

4.2.2:
;; 1. | | | | | | | | | | |;;   -5         0         5;;        (-----);; Contract: in-interval-1? : number -> boolean;; Purpose: To test if a number is between -3 and 0.(in-interval-1? -2)(and (< -3 -2) (< -2 0))(and true true)true;;2.  | | | | | | | | | | |;;    0         5         10;;    --) (----------------;; Contract: in-interval-2? : number -> boolean;; Purpose: To test if a number is less than 1 or greater than 2.(in-interval-2? -2)(or (< -2 1) (> -2 2))(or true false)true;;3.  | | | | | | | | | | |;;    0         5         10;;    --)       (----------;; Contract: in-interval-3? : number -> boolean;; Purpose: To test if a number is less than 1 or greater than 5.(in-interval-3? -2)(not (and (<= 1 -2) (<= -2 5)))(not (and false true))(not false)true

4.2.3:
;;1.(define (is-solution-1? x)  (= (+ (* 4 x) 2) 62));;2.(define (is-solution-2? x)  (= (* (sqr x) 2) 102));;3.(define (is-solution-3? x)  (= (+ 2 (* 4 (sqr x)) (* 6 x)) 462))

10 is a solution to 3. 12 and 14 are not solutions.

4.2.4:
;; I don't know what specific test cases the authors are referring to for problems 2.2.1 - 2.2.4 so I'll just make up a few.(= (Fahrenheit->Celsius 32) 0)(= (dollar->euro 20) 12.8399) ;; as of 05/18/08(= (triangle 5 2) 5)(= (convert3 9 2 7) 729)

4.3.1:
The left cond is legal. The right cond is illegal because it's second clause has no answer to evaluate. The last cond is illegal because it has no second clause to evaluate.

4.3.2:
(a) .040
(b) .045
(c) .060

4.3.3:
(a) 40
(b) 121
(c) 595

4.4.1:
(define (interest x)  (cond ((<= x 1000) (* .04 x))        ((<= x 5000) (* .045 x))        (else (* .05 x))))

4.4.2:
(define (tax x)  (cond ((<= x 240) 0)        ((<= x 480) (* .15 x))        (else (* .28 x))))(define (netpay hrs)  (- (grosspay hrs) (tax (grosspay hrs))))(define (grosspay hrs)  (* 12 hrs))

4.4.3:
(define (pay-back charges)  (cond ((<= charges 500) (* .025 charges))        ((<= charges 1500) (* .05 charges))        ((<= charges 2500) (* .075 charges))        (else (* .01 charges))))

4.4.4:
(define (how-many a b c)  (cond ((> (sqr b) (* 4 a c)) 2)        ((= (sqr b) (* 4 a c)) 1)        ((< (sqr b) (* 4 a c)) 0))) ;; or else 0));; (how-many 1 0 1) = 0

If we didn't assume the equation was proper we'd need to check (with
a cond) to see if a equaled 0 and return an error if it did.

That does it for Section 04. Hopefully, I'll get my act together and wrap up SICP Section 2.1 in the next week or so. :-) You've gotta work on some hard stuff too, right? Besides it's more interesting anyway.

# HTDP Section 03

posted on 2008-05-19 13:43:29

As promised, here’s Section 03 with 04 soon to follow. Sections 03 and 04 are pretty unremarkable and the questions and answers are pretty self-explanatory. Again, you can check all the latest code in my repo by going to manifest, then books, htdp, and navigating to the various source files.

Resources:
Watch: Nothing. To my knowledge there are no online lectures based around HTDP. Correct me if I’m wrong.
Checked against: Nothing. Again, to my knowledge there are no available sources to check your answers beyond the locked solutions on the official site and message boards. That’s one reason I’m excited about doing HTDP this way along with SICP. The plethora of SICP resources stand in contrast to an absolute dearth of resources for HTDP.

Exercises

3.1.1:
(define (attendees ticket-price)  (- 870 (* 150 ticket-price)))

This function will give incorrect answers for negative values of ticket-price.

3.1.2:
(define (revenue ticket-price)  (* (attendees ticket-price) ticket-price))(define (costs ticket-price)  (+ 180 (* .04 (attendees ticket-price))))(define (profit ticket-price)  (- (revenue ticket-price) (costs ticket-price)))

(profit 3) returns the best price which is 1063.2.

3.1.3:
Both program definitions return the same results for inputs of 3, 4
and 5.

3.1.4:
(define (profit ticket-price)  (- (revenue ticket-price)     (cost ticket-price)))(define (revenue ticket-price)  (*  (attendees ticket-price) ticket-price))(define (cost ticket-price)  (* 1.5 (attendees ticket-price)))(define (attendees ticket-price)  (+ 120     (* (/ 15 .10) (- 5.00 ticket-price))))(define (profit price)  (- (* (+ 120	   (* (/ 15 .10)	      (- 5.00 price)))	price)     (* 1.5	   (+ 120	      (* (/ 15 .10)		 (- 5.00 price))))))

Both programs return the same results but profit margins have changed based on the new costs. (max (profit 3) (profit 4) (profit 5) is now (profit 4).

3.2.1:
(define fixed-costs 180)(define price-per-attendee .04)(define start-attendees 120)(define attendees-per-dime 15)(define dime .10)(define start-price 5.00)

3.3.1:
(define inches-in-cm 2.54)(define inches-in-ft 12)(define feet-in-yard 3)(define yards-in-rod 5.5)(define rods-in-furlong 40)(define furlongs-in-mile 8)(define (inches->cm inches)  (* inches-in-cm inches))(define (feet->inches feet)  (* inches-in-ft feet))(define (yards->feet yards)  (* feet-in-yard yards))(define (rods->yards rods)  (* yards-in-rod rods))(define (furlongs->rods furlongs)  (* rods-in-furlong furlongs))(define (miles->furlongs miles)  (* furlongs-in-mile miles))(define (feet->cm feet)  (inches->cm (feet->inches feet)))(define (yards->cm yards)  (feet->cm (yards->feet yards)))(define (rods->inches rods)  (feet->inches (yards->feet (rods->yards rods))))(define (miles->feet miles)  (yards->feet (rods->yards (furlongs->yards                             (miles-furlongs miles)))))

3.3.2:
(define pi 3.14159)(define (volume-cylinder radius height)  (* pi (sqr radius) height))

3.3.3:
(define pi 3.14159)(define (area-cylinder radius height)  (* 2 pi radius (+ radius height)))

3.3.4:
(define (area-pipe inner-radius length thickness)  (+ (* 2 pi length (+ inner-radius thickness))      (* 2 (- (* pi (+ inner-radius thickness))               (* pi inner-radius)))))(define (area-pipe inner-radius length thickness)  (+ (area-pipe-side inner-radius length thickness)     (* 2 (area-pipe-ring inner-radius thickness))))(define (area-pipe-side inner-radius length thickness)  (* 2 pi length (+ inner-radius thickness)))(define (area-pipe-ring inner-radius thickness)  (* 2 (- (* pi (+ inner-radius thickness))          (* pi inner-radius))))

This problem reminds me of several in SICP in that the real difficulty with it is a misunderstanding of the question. Once you understand what is desired it’s pretty easy to bang the code out. This seems analogous to the idea that once you have a well-understood, well-specified set of requirements producing the code is trivial and that the requirements are the difficult part. Of course, this leads to blather about how good enough specifications (and UML Diagrams) are equivalent to code (which is bullshit). People forget that requirements change and that unambiguous well-specified requirements are often impossible.

3.3.5:
(define (height time)  (* .5 time (speed time)))(define (speed time acceleration)  (* time acceleration))

3.3.6:
(define (Celsius->Fahrenheit cels)  (+ 32 (/ (* cels 9) 5)))(I 32)(Celsius->Fahrenheit (Fahrenheit->Celsius 32))(Celsius->Fahrenheit (* (- 32 32) (/ 5 9)))(Celsius->Fahrenheit (* 0 (/ 5 9)))(Celsius->Fahrenheit 0)(+ 32 (/ (* 0 9) 5))(+ 32 (/ 0 5))(+ 32 0)32

Plainly, these functions are inverses of each other though that should be self evident. Since they are inverses their composition returns the original input. The stepper returns the same results.

Well, that’s it for Section 03. It seems that the first 8 Sections at least deal with language primitives and fairly basic material. It certainly is easier to progress through HTDP relative to SICP but I have had the sense that I was learning more in SICP. We’ll see if this changes at all once I progress beyond the early sections though I haven’t decided whether I’ll keep going through HTDP or forge ahead on SICP.

# HTDP Section 02

posted on 2008-05-19 03:25:27

So, I've finally gotten around to cleaning up SICP Section 1.3. It's not quite done but it's damn close. For now, I want to start posting some of the HTDP code I've been writing to get back in the hacking habit over the past few days. I also have some of Concrete Abstractions done and in my source code repository but it's nothing substantial. Without further ado, here's HTDP Section 02 (of 43!). Sections 03 and 04 will go up tomorrow. Note: I skipped HTDP Section 01 because there are no exercises or problems whatsoever.

Resources:

Watch: Nothing. To my knowledge there are no online lectures based around HTDP. Correct me if I'm wrong.

Checked against: Nothing. Again, to my knowledge there are no available sources to check your answers beyond the locked solutions on the official site and message boards. That's one reason I'm excited about doing HTDP this way along with SICP. The plethora of SICP resources stand in contrast to an absolute dearth of resources for HTDP.

Exercises

2.1.1:

Dr. Scheme does have operations for squaring (sqr x), computing sines (sin x), and finding maximums (max x). If you are not running in the HTDP Beginning Student Language though these functions may not be available.

2.1.2:

(sqrt 4)2(sqrt 2)#i1.4142135623730951(sqrt -1)0+1i;;(tan x) determines the tangent of a given angle.

2.2.1:

(define (Fahrenheit->Celsius fahr)  (* (- fahr 32) (/ 5 9)))

The teachpack worked as intended. Just go to Language -> Add Teachpack. Feel free to test the different convert-*s on your own.

2.2.2:

(define (dollar->euro dollars)  (* .642 dollars)) ;; as of 05/18/08

2.2.3:

(define (triangle side height)  (/ (* side height) 2))

2.2.4:

(define (convert3 first second third)  (+ (* 100 third) (* 10 second) (* 1 first)))

This was sort of counter-intuitive. The idea that this is related to something in an Algebra book is true but misleadingly so. You could try to do something fancy with max but that's not the idea.

2.2.5:

(define (f n)  (+ (/ n 3) 2));;The evaluations for 2, 5, and 9 are 2.6, 3.6 and 5, respectively.(define (f n)  (+ 10 (sqr n)));;The evaluations for 2 and 9 are 14 and 91, respectively.(define (f n)  (+ 20 (* (sqr n) .5)));;The evaluations for 2 and 9 are 22 and 60.5, respectively.(define (f n)  (- 2 (/ 1 n)));;The evaluations for 2 and 9 are 1.5 and 1.8, respectively.

2.3.1:

(define (tax income)  (* .15 income))(define (netpay hrs)  (- (wage hrs) (tax (wage hrs))));;supplementary functions:(define (wage hrs)  (* 12 hrs))

2.3.2:

(define (sum-coins pennies nickels dimes quarters)  (+ (* .01 pennies) (* .05 nickels) (* .1 dimes) (* .25 quarters)))

2.3.3:

(define (total-function attendees)  (- (* 5 attendees) (+ 20 (* .5 attendees))))

2.4.1:

(10) causes the interpreter to expect a function, procedure or expression but it is in fact primitive data, i.e. a number.

(10 + 20) is incorrect because the expression uses infix rather than prefix notation but the error from the interpreter is the same. This is due to the fact that the interpreter has been given a number rather than an procedure as it's operator.

(+ +) fails because the operator + is only given one argument (it requires a minimum of two) and that argument is a function which is the wrong type of input.

2.4.2:

(define (f x)  (+ x 10));;The argument to f needed to be changed.(define (g x)  (+ x 10));;There was a missing open-paren before the + operator.(define (h x)  (+ x 10));;The open-paren was in front of x when it should have been in front of h.

2.4.3:

;;> (+ 5 (/ 1 0));;/: division by zero;;> (sin 10 20);;sin: expects 1 argument, given 2: 10 20;;> (somef 10);;reference to an identifier before its definition: somef

2.4.4:

(define (somef x)  (sin x x));;> (somef 10 20);;somef: this procedure expects 1 argument, here it is provided 2 arguments;;> (somef 10);;sin: expects 1 argument, given 2: 10 10

The section ends with a bit on program design. It makes the important note of having human solved examples to test against. Sounds like an argument for unit tests to me.

# Official Fix for MIT-Scheme in Hardy

posted on 2008-05-05 15:34:39

Bug reports work! Finlay McWalter commented on the bug report saying that the package maintainer, Chris Hanson, found a fix for the issue. His fix is far better than my workaround. Apparently, AppArmor is preventing applications (such as MIT-Scheme) from accessing lower memory. The fix is to edit /etc/sysctl.conf and change the vm.mmap_min_addr value from 65536 to 0. Afterwards, MIT-Scheme works just fine.

In other news, this has been a really disastrous Monday.

# 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.

# 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.

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.

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.

# 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.9657842846620873.0044722098412146.2791957575071573.7598507024015395.2158437849258954.1822071924013974.82776509834459064.3875933846626774.6712500857638994.4814036168950524.60536574609294.52308496787188654.5771146820473414.5413824801514544.5649032452308334.5493726793033424.5596064919132874.5528538757882714.5573055297482634.5543690644361814.5563053115329994.5550282635735544.5558703967028514.5553150011920794.55568126354332754.5554397157368464.5555990099982914.5554939575313894.5555632372928844.5555175484176514.5555476793063984.5555278085162544.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.98289214233104354.9221687213083434.6282243181954554.5683465131362424.55773059092370054.5559098090451314.5555994116106244.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.

# On Schemes…

posted on 2008-03-05 21:28:56

One thing I've been thinking about a lot lately (even if it's premature) is what scheme implementation I want to settle on. Presumably at some point I'll be developing real applications. Or at least applications that I'll want to be able to pass along to one or two friends. At that point I'll need a way to pass said applications on without asking the friends to download and install the scheme environment themselves. See, Scheme is a LISP and LISPs are interpreted languages. There are native code compilers but they're not guaranteed.

So, my wishlist for a scheme implementation was something that was fairly fast, had a good FFI because we live in an inexorably polyglot programming age, could compile native binaries to be passed on to whomever without requiring a scheme install on their part, and decent library\module support. Other interesting features would be support for concurrency, documentation and community size, the corresponding development activity, and R6RS compliance (or plans of compliance).

This already cut my options down pretty quickly. The standout option was PLT Scheme/MzScheme. Bill Clementson proclaimed it the best open source LISP and in the general case I might agree with him. Now, I am another person that disagrees with DrScheme as an editor but I wouldn't let that stop me from using it. There's no reason one can't incorporate it into emacs, after all.

However, I couldn't find a way to force PLT Scheme to produce a standalone executable instead of a launcher and a cursory google does not lend me to believe that there is any way. That's more or less a deal breaker for me. PLT Scheme has incredible momentum and fantastic module support but what's a guy to do? There may be a way in here but I'm not really looking to embed MzScheme in whatever standalone I want to produce.

As I said, the options were already limited. Ikarus is of course the closest thing to R6RS but it's still sitting at 0.0.3. It's receiving heavy attention but I wouldn't use it yet. It's more something to keep an eye on. Scheme48 and Scsh would be great for Unix scripting but I'm interested in something with a larger community and more cross-platform nature. Guile has limitations to it's garbage collector that I question, it was designed as an extension language, and the community seems fairly small.

Bigloo, Gambit, and Chicken were the remaining options and of the three Gambit swayed me over. It's hard to say what factors exactly did the trick. Bigloo, Gambit, and Chicken all have FFI's to C and will generate native code. All three have active communities and decent module systems. I think what really compelled me in the end were three things, Gambit had some impressive benchmarks (even though they were on the Gambit homepage), I was compelled by Snow as a package system, and the fact that Termite is implemented on top of Gambit and it had such lightweight threads was highly compelling. After all, I do think concurrency via lightweight threads and message passing is going to matter a lot down the road so that was a pretty enticing bonus. As a final bonus, it runs on the OLPC.

So, now I had to figure out how to set it up. I won't keep you waiting but I should first note that I'll be installing the terminal (no-X) version of emacs because GTK emacs annoys me (aesthetically speaking).
sudo apt-get install emacs-snapshot-nox gambc

Create a desktop launcher thusly:
locate emacs-snapshot.desktopsudo nano /your/path/to/emacs-snapshot.desktop

Change name to Emacs Snapshot (nox)
Change Terminal to true
Change Exec to /usr/bin/emacs-snapshot-nox)

Then install quack:
cd /usr/share/emacs/site-lispsudo wget http://www.neilvandyke.org/quack/quack.el

And to start out you'll want to edit your .emacs using
sudo nano ~/.emacs

to look something like this:
(require 'quack)(custom-set-variables  ;; custom-set-variables was added by Custom.  ;; If you edit it by hand, you could mess it up, so be careful.  ;; Your init file should contain only one such instance.  ;; If there is more than one, they won't work right. '(quack-default-program "gsi") '(quack-pretty-lambda-p t))(custom-set-faces  ;; custom-set-faces was added by Custom.  ;; If you edit it by hand, you could mess it up, so be careful.  ;; Your init file should contain only one such instance.  ;; If there is more than one, they won't work right. )

And last but not least, a few choice commands:
C-x 1 kills all other windows
C-x C-s saves the buffer
C-x C-c exits immediately
M-x run-scheme RET drops you into the repl
C-d backs you out of runlevels
C-/ is undo

Snow will come next...

# SICP Section 1.2

posted on 2008-02-29 19:39:36

I finally finished SICP Section 1.2 last night. I'm tremendously excited because this means that next week I can start tackling Higher Order Functions and (I hope) Closures. At any rate, here is the last month's work:

Resources:

Read: Chapter 1 through Section 1.2

Watch: Lectures 1-b

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

SICP Notes and Exercises:

Notes

Pg. 35: Explanations of Iteration and Recursion in Processes and Procedures and Tail-Recursion in Compilers.

Maybe I was wrong about SICP. I mean the hardest thing about these exercises was letting the stuff sit in my head for a bit. And the motivation to get some of the more lengthy ones done. We'll see how this goes.

Quotes

"A recursive definition does not necessarily lead to a recursive process." - Gerald Jay Sussman, SICP Lecture 1-B's Time-Space Complexity explanation, approx. 25:30 - 30:30

"The key to understanding complicated things is knowing what not to look at." - Gerald Jay Sussman, SICP Lecture 1-B from Swiss Archive, approx. 10:00

"The reason why people think of programming as being hard is because you're writing down a general rule which is going to be used for lots of instances that a particular instance must process correctly." - Gerald Jay Sussman, SICP Lecture 1-B from Swiss Archive, approx. 46:45

Exercises

1.9:

The first procedure evaluates as follows:

(inc (+ 3 5))(inc (inc (+ 2 5)))(inc (inc (inc (+ 1 5))))(inc (inc (inc (inc (+ 0 5)))))(inc (inc (inc (inc 5))))(inc (inc (inc 6)))(inc (inc 7))(inc 8)9

This is a recursive procedure and a recursive process.

The second procedure evaluates as follows:

(+ 3 6)(+ 2 7)(+ 1 8)(+ 0 9)9

This is a recursive procedure but an iterative process.

1.10:

(A 1 10) evaluates as follows:

(A 0 (A 1 9))(A 0 (A 0 (A 1 8)))(A 0 (A 0 (A 0 (A 1 7))))(A 0 (A 0 (A 0 (A 0 (A 1 6)))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))(A 0 (A 0 (A 0 (A 0 (A 0 32)))))(A 0 (A 0 (A 0 (A 0 64))))(A 0 (A 0 (A 0 128)))(A 0 (A 0 256))(A 0 512)1024

(A 2 4) evaluates as follows:

(A 1 (A 2 3))(A 1 (A 1 (A 2 2)))(A 1 (A 1 (A 1 (A 2 1))))(A 1 (A 1 (A 1 2)))(A 1 (A 1 (A 0 (A 1 1))))(A 1 (A 1 (A 0 2)))(A 1 (A 1 4))(A 1 (A 0 (A 1 3)))(A 1 (A 0 (A 0 (A 1 2))))(A 1 (A 0 (A 0 (A 0 (A 1 1)))))(A 1 (A 0 (A 0 (A 0 2))))(A 1 (A 0 (A 0 4)))(A 1 (A 0 8))(A 1 16)(A 0 (A 1 15))(A 0 (A 0 (A 1 14)))(A 0 (A 0 (A 0 (A 1 13))))(A 0 (A 0 (A 0 (A 0 (A 1 12)))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 11))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 10)))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 9))))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 8)))))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 7))))))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 6)))))))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 32)))))))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 64))))))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 128)))))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 256))))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 512)))))))(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 1024))))))(A 0 (A 0 (A 0 (A 0 (A 0 2048)))))(A 0 (A 0 (A 0 (A 0 4096))))(A 0 (A 0 (A 0 8192)))(A 0 (A 0 16384))(A 0 32768)65536

(A 3 3) evaluates as follows:

(A 2 (A 3 2))(A 2 (A 2 (A 3 1)))(A 2 (A 2 2))(A 2 (A 1 (A 2 1)))(A 2 (A 1 2))(A 2 (A 0 (A 1 1)))(A 2 (A 0 2))(A 2 4)65536

(see evaluation of (A 2 4) above)

The defined procedures f, g, and h intriguingly map as follows:

(f n) -> (* 2 n)

(g n) -> 2^n

(h n) -> 2 raised to itself, n times.

##NOTE:

In the book examples are given of recursive and iterative ways to compute the fibonacci sequence. However, the example given for the fibonacci sequence computes a term beyond what is desired to arrive at it's final answer. The termination condition is count = 0 at which point b is returned. This is a small change to that program to fix what I perceive as a flaw. Have I missed something?

My version returns a when count = 1.

(define (fib n)  (fib-iter 1 0 n))(define (fib-iter a b count)  (if (= count 1)      a      (fib-iter (+ a b) a (- count 1))))

1.11:

A tree recursive process that computes f is demonstrated in the following procedure:

(define (f n)  (cond ((< n 3) n)	   ((or (= n 3) (> n 3))            (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3)))))))

An iterative process that computes f is demonstrated in the following procedure:

(define (f n)  (f-iter 2 1 0 n))(define (f-iter a b c count)  (cond ((< count 3) count)	(else (f-iter (+ a (* 2 b) (* 3 c)) a b (- count 1)))))

Figuring out the iterative process was scary. It was the first moment I thought I wouldn't be able to do this and might need real help. I was unsure of whether I needed three or four state variables. It clicked after a few minutes of thinking though and was much smoother from there.

1.12:

This one actually gave me some trouble for a bit because I wanted to solve the problem in a non-standard way. After a while, I cracked and read the precursor text (but not the code) to Eli Bendersky's solution and noticing that he defined the function with two arguments (for columns and rows) arrived fairly quickly with that insight at what seems to be the more or less standard solution. I had this much completed for a week or more but got stalled trying to figure out the problem of a pascal function that takes one argument. That diversion contributed greatly to the delay in my progress. I did solve it though and posted the results separately. Here's the standard solution:

(define (pas row col)  (cond ((= row 1) 1)	((= col 1) 1)	((= row col) 1)	(else (+ (pas (- row 1) (- col 1))		 (pas (- row 1) col)))));Value: pas

1.13:

I need to define a few things for this one first.

rad = the square root of 5 or

(sqrt 5)

phi = (1 + rad) / 2 or

(/ (+ 1 rad) 2)

psi = (1 - rad) / 2 or

(/ (- 1 rad) 2)

fib = you remember our fibonacci function from before right? That's all this is.

Prove that Fib(n) is the closest integer to (/ (phi ^ n) rad). Hint: Use psi as defined above, induction and the definition of the Fibonacci numbers to prove that Fib(n) = ((phi ^ n) - (psi ^ n)) / rad.

Okay, this one is intimidating for a number of reasons. One being that I've never done a formal proof before. At least that I can remember. I've seen proofs done and I've read one or two but I've never done one. Either my math education was lax or I was lax about my math education. In fairness, it was probably a bit of both. That unfamiliarity combined with the aforementioned pascal with a single argument problem served to keep me unmotivated and distracted for a bit.

Prove: That Fib(n) = ((phi ^ n) - (psi ^ n)) / rad.

First, you have to prove your base cases.

Fib (0) = ((phi ^ 0) - (psi ^ 0)) / rad.

That reduces to, 0 = (1 - 1) / rad, So the first base case holds.

Fib (1) = ((phi ^ 1) - (psi ^ 1)) / rad.

That reduces to, 1 = ((1 / 2) + (rad / 2) - (1 / 2) + (rad / 2)) / rad.

That reduces to, 1 = rad / rad, so the second base case holds.

The definition of Fibonacci numbers is that fib(n) = fib(n-1) + fib(n-2) so fib(2) = 0 + 1 = 1. Having found that our lemma is true for n-1 and n-2 will it hold for n?

Fib (2) = ((phi ^ 2) - (psi ^ 2)) / rad.

Remembering that Phi is the golden ratio it meets the condition that (phi ^ 2) = phi + 1.

This gives fib (2) = (2.61803398 - 0.38196601) / rad.

This reduces to fib (2) = 2.23606797 / rad giving 1.

Thus, our lemma holds for fib(n). This does not explain how Fib(n) is always the closest integer to phi ^ n / rad though.

To explain that we must note that in the base case of 1 it holds as phi ^ n / rad evaluates to 0.723606798 and Fib(1) is 1. So, it holds here.

We may then observe that psi being less than 1 will always approach zero as it's exponent is increased.

Thus, the difference between the fib(n) and (/ (phi ^ n) rad) will always be less than 0.381 for n >= 2.

This is what we needed to show.

Whew. After checking this against other people's solutions it turns out I'm not crazy and am roughly correct in my proof which is a relief.

1.14:

Okay. I drew the tree on paper but trying to draw this tree in ASCII for you guys would about kill me. Thankfully on checking my solution I was lucky to find a correct tree image which I will steal with credit. Thanks, Bhrgunatha.

Here is the tree.

As for the order, we can observe that at least in terms number of steps the growth follows that of our tree-recursive fibonacci function and is exponential. I think it's growing at O(xn) but it could be growing at O(nx). Has anyone come to a definitive conclusion about this? Upon checking Ken Dyck's site again I see that Tim Eichner has an interesting solution. Can anyone confirm this?

1.15:

a. How many times is the procedure p applied when (sine 12.15) is evaluated?

(p (sine 4.05))(p (p (sine 1.35)))(p (p (p (sine 0.45))))(p (p (p (p (sine 0.15)))))(p (p (p (p (p (sine 0.05))))))(p (p (p (p (p 0.05)))))

P is applied 5 times.

b. What is the order of growth in space and number of steps (as a function of a) used by the process generated by the sine procedure when (sine a) is evaluated?

This one I did need help with. I realized quite clearly that the growth was related to the number of divisions by 3 our angle took to get below the threshold (0.01). I did not realize that the abstraction I was looking for to describe this growth was that of a logarithm. That being said, I checked a few other solutions and went over the wiki page for logarithms once or twice. I really need to order Spivak's Calculus now. Anyway, the process is O(log(a)) in both space and time. Specifically it's O(log3(n)).

1.16:

This was tricky until I modeled the state transformations holding to the rule suggested for (* a (b^n)). Once I did that it was pretty easy.

(define (expt b n)  (define (expt-iter b n a)  (cond ((= n 0) a)	((even? n) (expt-iter (square b) (/ n 2) a))	(else (expt-iter b (- n 1) (* a b)))))  (expt b n 1));Value: expt-iter(expt-iter 2 1000 1)10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376;;That's a 300 digit number. This algorithm is O(log n). This computed in 16 steps.

1.17:

(define (* a b)  (define (double x)    (+ x x))  (define (halve x)    (/ x 2))  (cond ((= b 0) 0)	((= a 0) 0)	((= b 1) a)	((even? b) (* (double a) (halve b)))	(else (+ a (* a (- b 1))))));Value: *(* 2 1000);Value: 2000;;16 steps again. logarithmic in time. space too? I think it's just linear in space.

1.18:

(define (* a b)  (define (double x)    (+ x x))  (define (halve x)    (/ x 2))  (define (*-iter a b c)    (cond ((= b 0) 0)	  ((= a 0) 0)	  ((= b 1) (+ a c))	  ((even? b) (*-iter (double a) (halve b) c))	  (else (*-iter a (- b 1) (+ c a)))))  (*-iter a b 0));Value: *(* 2 1000);Value: 2000;;16 steps again. logarithmic and iterative, so it does it in O(1) space. boo-yah. today was a good day to code.

1.19:

This was just a really difficult problem to understand. I wasn't even sure what they were really asking. Once I realized I just needed to use algebra to try and expand and then factor out a few things I felt a lot more comfortable.

(define (fib n)  (fib-iter 1 0 0 1 n));Value: fib(define (fib-iter a b p q count)  (cond ((= count 0 ) b)	((even? count)	 (fib-iter a		   b		   (+ (square p) (square q)) ;; compute p'		   (+ (* 2 p q) (square q))  ;; compute q'		   (/ count 2)))	(else (fib-iter (+ (* b q) (* a q) (* a p))			(+ (* b p) (* a q))			p			q			(- count 1)))));Value: fib-iter

1.20:

This is one of those exercises that Abelman and Sussman are sort of bastards for including.

;;Normal order evaluation is fully expand to primitives and then reduce.

;;Applicative-order is...well, what we've been doing all along.

How many remainder operations are performed in the normal order version of

(gcd 206 40)?

How many in the applicative order version?

4: (206 4), (40 6), (6 4), (4 2)

Applicative order first:

(gcd 206 40)

(gcd 40 (remainder 206 40))

(gcd 40 6)

(gcd 6 (remainder 40 6))

(gcd 6 4)

(gcd 4 (remainder 6 4))

(gcd 4 2)

(gcd 2 (remainder 4 2))

(gcd 2 0)

2

Normal order version:

(gcd 206 40)

;;we can count the number of times remainders occur in b, which is always evaluated.

(gcd 40 (remainder 206 40)) ;;rc = 1

if (= (remainder 206 40) 0) = false

(gcd (remainder 206 40) (remainder 40 (remainder 206 40)))) ;;rc = 1+2

if (= (remainder 40 6) 0) = false

(gcd (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) ;;rc = 1+2+4

if (= (remainder 6 4) 0) = false

(gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))) ;;rc = 1+2+4+7

if (= (remainder 4 2) 0) = true!

now that if is true we evaluate a: (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) which has 4 remainders to the 14 that have been evaluated in prior predicates. tada! 18 evaluations in total for normal order. 4, if you didn't notice, for applicative order.

GCD is effectively a loop here and the only way for the loop to exit is for the if predicate to evaluate to true, after which the consequent is evaluated. The alternate is only substituted for in this case, never evaluated outright as it never becomes primitive.

In this way, the problem seems to me more of a study into the if conditional than evaluation models. Once you understand that the alternate never gets evaluated, you can simply figure out how many remainders get fed to it before it's true and then how many are in the consequent.

That's the best I could come up with for this one but Eli Bendersky has a solution you may find more clear or detailed.

1.21:

(smallest-divisor 199);Value: 199(smallest-divisor 1999);Value: 1999(smallest-divisor 19999);Value: 7

1.22:

The code for this exercise is not particularly difficult. It's not easy but it's fairly straightforward. Because this exercise was written over 10 years ago though it's pretty difficult to use on modern hardware. You're supposed to observe algorithmic efficiency because this code is supposed to stress your hardware. Unfortunately, in 2008 this code makes my hardware yawn for numbers on the scale they were asking for. So I started things off at 13 digits and scaled up from there. I also decided to rework the code so that it only outputs when it finds a prime.

(define (start-prime-test n start-time)  (if (prime? n)      (report-prime (- (runtime) start-time) n)))(define (report-prime elapsed-time n)  (newline)  (display n)  (display " *** ")  (display elapsed-time))(define (search-for-primes current end)  (cond ((even? current) (search-for-primes (+ current 1) end))	((> current end) (display " done! "))	(else (timed-prime-test current)	      (search-for-primes (+ current 2) end))))

So, there's the code. Now for my results:

(search-for-primes 100000000000 100000000060)

100000000003 *** 1.1600000000000037

100000000019 *** 1.1899999999999977

100000000057 *** 1.240000000000009 done!

;Unspecified return value

(search-for-primes 1000000000000 1000000000070)

1000000000039 *** 3.91

1000000000061 *** 3.759999999999998

1000000000063 *** 3.9400000000000013 done!

;Unspecified return value

(search-for-primes 10000000000000 10000000000100)

10000000000037 *** 12.280000000000001

10000000000051 *** 12.510000000000005

10000000000099 *** 12.200000000000003 done!

;Unspecified return value

(search-for-primes 100000000000000 100000000000098)

100000000000031 *** 38.190000000000026

100000000000067 *** 38.16

100000000000097 *** 37.95000000000002 done!

;Unspecified return value

Checking all of these it appears we are very close to the projected (sqrt 10) increase per digit.

1.23:

(define (find-divisor n test-divisor)  (cond ((> (square n) n) n)	((= (modulo n test-divisor) 0) test-divisor)	(else (find-divisor n (next test-divisor)))));Value: find-divisor(define (next n)  (cond ((even? n) (+ n 1))        (else (+ n 2))));Value: next

The results this time were:

(search-for-primes 100000000000 100000000060)

100000000003 *** .7400000000000091

100000000019 *** .7200000000000273

100000000057 *** .7099999999999795 done!

;Unspecified return value

(search-for-primes 1000000000000 1000000000070)

1000000000039 *** 2.3600000000000136

1000000000061 *** 2.2900000000000205

1000000000063 *** 2.319999999999993 done!

;Unspecified return value

(search-for-primes 10000000000000 10000000000100)

10000000000037 *** 7.350000000000023

10000000000051 *** 7.340000000000032

10000000000099 *** 7.189999999999998 done!

;Unspecified return value

(search-for-primes 100000000000000 100000000000098)

100000000000031 *** 23.110000000000014

100000000000067 *** 22.879999999999995

100000000000097 *** 22.920000000000016 done!

;Unspecified return value

This time we also are pretty close to half the previous times but it's slightly over half.

1.24:

(define (start-prime-test n start-time)  (if (fast-prime? n 500)      (report-prime (- (runtime) start-time) n)));Value: start-prime-test

And these results were:

(search-for-primes 100000000000 100000000060)

100000000003 *** 9.999999999990905e-3

100000000019 *** 0.

100000000057 *** 9.999999999990905e-3 done!

;Unspecified return value

(search-for-primes 1000000000000 1000000000070)

1000000000039 *** 0.

1000000000061 *** 9.999999999990905e-3

1000000000063 *** 0. done!

;Unspecified return value

(search-for-primes 10000000000000 10000000000100)

10000000000037 *** 0.

10000000000051 *** 0.

10000000000099 *** 0. done!

;Unspecified return value

(search-for-primes 100000000000000 100000000000098)

100000000000031 *** 9.999999999990905e-3

100000000000067 *** 0.

100000000000097 *** 0. done!

;Unspecified return value

We can see that this is definitely in O(log(n)). The times have gone below the precision of my instruments in most cases.

1.25:

I honestly had to look to Eli and Ken for help on this one. I was hand evaluating the original code before trying Alyssa's and having some trouble. I had noticed that the fast-expt procedure had two arguments where expmod had three so I figured part of the computation was being moved around. I even realized that Alyssa's way went ahead and computed the base to the exponent and then tested the remainder against it once. That just seemed like it should've been better to me. I didn't have the sense to just add runtime in as an argument and see how much time they were taking. At any rate, the original expmod does lots of little remainder tests but because of Bignum arithmetic that ends up being faster than a single test on a huge number.

1.26:

(expmod base (/ exp 2) m) has to be evaluated an extra time each time the (even? exp) condition evaluates to true. This moves the algorithm from log n to n because, as I somewhat foolishly missed, it shifts the recursion from a linear recursion to a tree recursion. See the SICP Wiki's solution for more detail, it seems to be the best resource for rigorous complexity analysis.

1.27:

(define (expmod base exp m)  (cond ((= exp 0) 1)	((even? exp)	 (remainder (square (expmod base (/ exp 2) m)) m))	(else	 (remainder (* base (expmod base (- exp 1) m)) m))));Value: expmod(define (carmichael-test n)  (define (try-it a)    (= (expmod a n n) a))  (define (carmichael-iter times)    (cond ((= times 0) true)	  ((try-it times) (carmichael-iter (- times 1)))	  (else false)))  (carmichael-iter (- n 1)));Value: carmichael-test

1.28:

(define (expmod base exp m)  (define (miller-rabin x)    (and (not (= x 1)) (not (= x m)) (= (square x) (modulo 1 m))))  (cond ((= exp 0) 1)	((even? exp)	 (if (miller-rabin (square (expmod base (/ exp 2) m)))	     0	     (remainder (square (expmod base (/ exp 2) m))			m)))	(else	 (remainder (* base (expmod base (- exp 1) m))		    m))));Value: expmod(define (miller-rabin-search n)  (define (try-it a)    (= (expmod a (- n 1) n) 1))  (try-it (+ 1 (random (- n 1)))));Value: miller-rabin-search(define (miller-rabin-test n)  (define (mr-iter count)    (cond ((= count 1) #t)             ((miller-rabin-search n) (mr-iter (- count 1)))             (else #f)))  (mr-iter (floor (/ n 2))));Value: miller-rabin-test;;I got everything written right on this one but I had to check Ken's page again to notice that my try-it definition was;;testing the expmod result against a, not 1. Once I fixed that I was right as rain.

As a final note, I should point out that my solution here differs a bit from the norm. One, I'm pretty serious about not using primitives that haven't been introduced yet. Even Ken Dyck's solution uses let (though the SICP wiki avoids it). After all, this is my first serious work in programming ever. The closest thing besides this was my read through the first chapter of K&R in summer of 2006. Anyway, just keep in mind I'm taking this as my formal education.

# Pascal’s Triangle

posted on 2008-02-07 03:25:28

A little over two weeks ago I came up against Exercise 1.12 in the venerable Structure and Interpretation of Computer Programs.

The exercise wants you to write a recursive program to compute elements of Pascal's Triangle.

This exercise has pretty much infuriated me and it's all my own fault. Upon first hearing the problem statement I got it in my head that the function should look something like "(define (pas n)...)". I always think of number series being described in terms of a single argument (i.e. the 12th element) so it seemed natural to me that the pascal's triangle function should be computed in this way even though it is not, in some sense, a traditional series.

After a while, I cracked and read the precursor text (but not the code) to Eli Bendersky's solution and noticing that he defined the function with two arguments (for columns and rows) arrived fairly quickly with that insight at what seems to be the more or less standard solution. I have had this much completed for a week but gotten stalled trying to figure out the problem of a pascal function that takes one argument.

As of today I've solved the problem though and hoped to share my results here. First, the throwaway code that ended up being good for nothing!

(define (is-one? element)  (define (is-one-iter ones count flag)    (cond ((< element 5) #t)	  ((= ones element) #t)	  ((> ones element) #f)	  ((= flag 1) (is-one-iter (+ ones 1) count (- flag 1)))	  (else (is-one-iter (+ ones count) (+ count 1) (+ flag 1)))))  (is-one-iter 4 2 0));Value: is-one?

That code tests to see whether a given element equals one and it does take a single argument which is nice. I couldn't figure out a way to use it to compute the actual elements though.

After a little bit of experimenting I stumbled on this number sequence (OEIS #A080956) which when put in the following procedure would allow me to compute n from a given column and row.

EDIT: Corrected dyslexic mistake in my code (I'd replaced all instances of col with row and vice versa). See comments.

(define (n-from-rowcol row col)  (define (f x)    (- (/ (* (+ x 1) (- 2 x)) 2)))  (+ row col (f (- row 1))));Value: n-from-rowcol

Now all I had to do was find a way to reverse the function to give me the inputs if I gave it the output. I actually stumbled upon another number sequence (OEIS #A000124, also known as the Lazy Caterer's Sequence) which when put into the following procedure returns the correct column and row for a given element. At last, working code:

(define (pascal n)  (define (pas col row)    (cond ((= col 1) 1)	  ((= row 1) 1)	  ((= col row) 1)	  (else (+ (pas (- col 1) row)		   (pas (- col 1) (- row 1))))))  (define (colrow-from-n)    (define (col-iter count)      (define (f x)	(- (/ (+ (square x) x 2) 2) x))      (cond ((> (f count) n) (pas (- count 1) (- n (- (f (- count 1)) 1))))	    ((= (f count) n) (pas (f count) 1))	    (else (col-iter (+ count 1)))))    (col-iter 1))(colrow-from-n));Value: pascal

Any insights into cleaner code, better algorithms, or comparisons between the two number series are welcomed.

# Still Kicking

posted on 2008-01-30 19:26:42

Okay. So, I didn't get the week 2 recap posted last Friday and I'm not getting it posted today either. Before you folks go judging me and deciding I turned into a lazy bum I thought I should make some note of progress.

As I've mentioned, SICP isn't going as fast as I hoped but I won't skip a thing. If my schedule goes out the window so be it but this book is getting finished. Of course, hopefully I can conform somewhat to the schedule as well. There will be an update this weekend even if I'm not through section 1.2.

In the meantime, I thought that I'd post up something I've been working on during my lunch hour. Namely, Project Euler code. Project Euler is a website that has about 180 Programming Problems of escalating difficult. I've only devoted one lunch hour to it so far but it's been fun and I'd love to get through a quarter to half the problems this year.

The challenge for me I think will come from the math side as well as the programming and some of these I just won't be able to solve for a while. Better to challenge myself from both ends, right? The code's hidden behind a cut for those who don't want their eyes scarred by this programming nonsense. Also, I'll be improving these as I discover better programming formalisms. I'm also solving each problem in both C and Scheme. I want to solve each problem from two paradigms (or more) if possible.

Problem 1 in C:
//Project Euler Problem 1://Sum the numbers below 1000 divisible by 3 or 5.#include int main (void){	int count;	int sum = 0;	for (count = 1; count < 1000; count++){		if ((count % 3 == 0) || (count % 5 == 0))			sum += count;}	printf ("The sum of all multiples of 3 or 5 below 1000 is %d.n", sum);	return (0);}

Problem 1 in Scheme:
;;Project Euler Problem 1:;;Sum the numbers below 1,000 divisible by 3 or 5.(define (euler1 top)  (define (iter count sum)    (define (divides? n)      (or (= (modulo n 3) 0) (= (modulo n 5) 0)))    (cond ((= count top) sum)	  ((divides? count) (iter (+ count 1) (+ sum count)))	  (else (iter (+ count 1) sum))))  (iter 1 0));Value: euler1

Problem 2 in C:
//Project Euler Problem 2://Sum the even-valued terms in the Fibonacci sequence below 1,000,000.#include int main (void){	int a = 1;	int b = 2;	int temp, sum = 0;	while (a <= 1000000){		if (a % 2 == 0){			temp = b;			b += a;			sum += a;			a = temp;}		else{			temp = b;			b += a;			a = temp;}}	printf ("The sum of the even valued Fibonacci terms below 1,000,000 is %d.n", sum);	return (0);}

Problem 2 in Scheme:
;;Project Euler Problem 2:;;Sum the even-valued terms in the Fibonacci sequence below 1,000,000.(define (euler2 top)  (define (iter current sum count)    (define (fib n)      (cond ((< n 3) n)	    (else (+ (fib (- n 1)) (fib (- n 2))))))    (cond ((> current top) sum)	  ((even? current) (iter (fib (+ count 1))				 (+ sum current) (+ count 1)))	  (else (iter (fib (+ count 1)) sum (+ count 1)))))  (iter 0 0 0));Value: euler2

That's all for now. Hope I get section 1.2 done by this weekend!

# The Rubber Meets the Road…

posted on 2008-01-25 05:33:05

and I find the resources to read. This SICP studying is harder than I ever could have imagined. I have done approximately nothing in my math, putting me about two weeks behind tomorrow. My focus has been entirely on SICP. SICP, I'm only a few days behind on thankfully. It's really hard stuff. And as somebody noted, charmingly, at this stage it practically is math. And proof by induction, recursive functions, golden ratios and Fibonacci sequences math. Not your grandpa's arithmetic.

Anyway, I've dug up some resources hitting snags here and there. It's what I do. So far, I've found a really great SICP Wiki (but it's half Russian), and a pack of people that have studied it from the Open Courseware over the past year.

That pack is as follows:
Ken Dyck's Solutions
Peter Sheats Solutions
Chuck Hoffman's Blog
Michael Harrison's Solutions and Commentary
Ozten's Solutions and Commentary
and finally, The Lispy Solutions and Commentary which so wonderfully motivated and inspired me tonight. Particularly with regards to a remark on Section 1.1 "just lulling you into a false sense of security".

Of course, there is also the aforementioned SICP Wiki and Eli Bendersky's Blog. Long story short, I really owe it to Lispy for encouraging me. Half way through section 1.2 I was bogged down. Roughly on exercise 1.13 which apparently gave a few other people trouble too. And I felt all alone.

Anyway, I'm going to try to push my schedule back a week and see if by next Friday I can be up to lambdas and through 80 pages of Discrete Math and then continue as planned. At the very least, I've known from day one that the one thing I want most to accomplish this year is wringing as much as I can out of SICP. So if it takes the whole year just to do that, schedules be damned, so be it.

# SICP Section 1.1

posted on 2008-01-19 03:18:23

Well, I said I would do this and I meant it. These entries will be a bit lengthy. I feel a little pain for any feeds I'm aggregated on. So, in the interest of not driving you all mad, these weekly semester updates will be behind a cut.

Like so.

With that out of the way, here are the details. Each week, I'll post the resources I used (i.e. what I read, what I watched, etc) and the solutions to the relevant problems along with any notes of interest I had. I may offer other general musings (or even specific ones) inspired by my studies in other posts but these will tend towards a cut and dry solution to the exercises. Finally, I'll post a link to any sources I might have found or used to check answers I wasn't sure of and if I got the answer wrong I'll disclose that in the post.

As for the math, I haven't decided what to do about that. I mean, it doesn't make sense to post up a ton of math solutions though I suppose by that logic it doesn't make sense to post code snippets either. If I come up with something I'll let you know. If you have suggestions by all means write them in.

Resources:

Read: Chapter 1 through Section 1.1

Watch: Lectures 1-a

Checked against: Eli Bendersky's Blog

SICP Notes and Exercises:

Notes

Pgs. 28-30: Definitions and explanations of scope and locality. It is becoming evident that subtle errors can easily emerge due to differences in locality and scope. These errors are colluded by the fact that there is no distinction in lisp between variables and procedures. (i.e. you could have a procedure that used abs (another procedure) as a variable.)

Quotes

"First, we want to establish the idea that a computer language is not just a way of getting a computer to perform operations but rather that it is a novel formal medium for expressing ideas about methodology. Thus, programs must be written for people to read, and only incidentally for machines to execute." - Preface to the First Edition

"The computer revolution is a revolution in the way we think and in the way we express what we think. The essence of this change is the emergence of what might best be called procedural epistemology - the study of the structure of knowledge from an imperative point of view, as opposed to the more declarative point of view taken by classical mathematical subjects." - Preface to the First Edition

Exercises

1.2:

(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 3))))) (* 3 (* (- 6 2) (- 2 7))));Value: -23/90

1.3:

(define (two-of-three x y z)  (cond ((< x y z) (+ (* y y) (* z z)))	((< y x z) (+ (* x x) (* z z)))	((< z x y) (+ (* x x) (* y y)))	((or (= x y) (= x z)) (+ (* y y) (* z z)))	((or (= y x) (= y z)) (+ (* x x) (* z z)))	((or (= z x) (= z y)) (+ (* x x) (* y y)))));Value: two-of-three

Comments: The original version of the program lacked the last three lines but I realized if you got inputs that were equal to each other there wasn't a condition that matched that so I changed it. I'm sure there's a much more elegant way to do it but the job is done. And it's mostly readable.

1.4:

This procedure checks to see if B is greater than 0. If it is, it adds A and B. Otherwise, it subtracts B from A.

1.5:

This procedure when evaluated using applicative-order evaluation will not resolve as it infinitely recurses trying to evaluate (p). An interpreter using Normal-order evaluation will not have this problem because in the example the if condition evaluates to true so the p function is never evaluated. (The Scheme interpreter uses Applicative-Order evaluation.)

1.6:

Again, this is a case of infinite recursion due to Applicative-Order evaluation. Sqrt-iter continues to call itself regardless of the value of (good-enough? guess x) if you must know.

1.7:

(define (good-enough? guess x)  (< (abs (- (improve guess x) guess)) (* 0.000001 guess)));Value: good-enough?

1.8:

(define (curt-iter guess x)  (if (good-enough? guess x)      guess      (curt-iter (improve guess x) x)));Value: curt-iter(define (good-enough? guess x)  (< (abs (- (cube guess) x)) 0.001));Value: good-enough?(define (cube x)  (* x (* x x)));Value: cube(define (curt x)  (curt-iter 1.0 x));Value: curt(define (improve guess x)  (/ (+ (/ x (* guess guess)) (* 2 guess)) 3));Value: improve

##NOTE:

Here is an example rewrite of the sqrt program using block structure and lexical scoping. It is inserted here because this was the point of discussion but no relevant exercise was assigned.

(define (sqrt x)    (define (sqrt-iter guess)        (if (good-enough? guess)            guess            (sqrt-iter (improve guess))))    (define (good-enough? guess)        (< (abs (- (square guess) x)) 0.001))    (define (average a b)        (/ (+ a b) 2))    (define (improve guess)        (average guess (/ x guess)))    (sqrt-iter 1.0))

Unless otherwise credited all material by Brit Butler