SICP Under Attack?

Posted on 2011-08-07 by jcs

Vedant Kumar has a provocative post entitled SICP is Under Attack in which he laments the abandonment of SICP by several universities and especially by Berkeley, where he is a EE/CS student. Berkeley, it turns out, is replacing SICP with Dive Into Python. I’m having a hard time getting my mind around this.

I’ve read Dive Into Python and it’s a very nice book—excellent for learning Python—but it’s not really a book about Computer Science or learning to think like a computer scientist. If you’ve watched the famous SICP lectures given by Abelson and Sussman at HP you may recall that in the first lecture Abelson specifically says that Computer Science is no more about computers than geometry is about surveying. That little nugget is from 1986 and has aged well, I think.

How then, does it make sense to replace a book about Computer Science—arguably the best book about Computer Science—with a book that teaches a particular language? Yes, SICP uses Scheme but the point was that Scheme was so easy to pick up that they spent virtually no time on the language; they concentrated on Computer Science concepts such as recursion, complexity theory, and fixed points.

To be fair, Kumar has an update in which he says that Berkeley has assured him that all that’s really happening is that they’re moving from Scheme to Python and that the content from SICP will be preserved. Even if that’s possible, it makes the decision worse in my opinion. SICP is the exemplar of its approach. Why would you replace it with something else? Again, Dive Into Python is a fine book for learning python but in no way does it cover the same material or serve the same ends as SICP.

MIT, of course, famously abandoned SICP too but they, at least, had a reasonable, if not ultimately convincing, rationale for doing so. Sussman explained that software engineering today is all about gluing together huge libraries that hardly anyone understands and that the SICP approach of understanding everything “all the way down” isn’t used anymore or at least is less relevant. That may be true but it’s no reason that students should not learn the material that forms the foundation of their craft.

In the last couple of days. I’ve seen several posts lamenting the fact that younger engineers don’t really understand the fundamentals or what’s going on “under the covers.” Of course some of this could be the normal “kids today!” that fogies have been muttering since Plato but if our very best engineering schools, like Berkeley and MIT, are teaching their students to glue libraries together at the expense of learning and understanding the foundations of CS these observations should come as no surprise.

Posted in General | Tagged | Leave a comment

Desktop Gmail Gets A Preview Pane

Posted on 2011-08-06 by jcs

Back in July I wrote that I preferred reading Gmail on my iPad even when I was home and had my iMac available. That’s because the iPad Gmail has a preview pane. If you haven’t used it, it doesn’t sound like much but it really improves the Gmail work flow. On the desktop I scan the list of emails and delete any that I know I’m not interested in. Then I go to the first unread email, read it, and click on the next button to get the next message. That’s OK but if I want to delete a message or mark it as spam I get taken back to the list of emails and have to click on the next email to read. If I want to keep a message in my inbox, I mark it with a star. When I’ve read all the messages, I tell Gmail to check all the unstarred messages and then click on the archive button to save them.

With the iPad, there are three panes: the menu pain listing mailboxes, the message pane listing the messages, and the preview pane that has the selected message displayed (on the iPad, the menu pane is usually hidden but it can be swapped with the message pane). With this setup, I can just choose archive, delete, or mark as spam and the next message displays. It’s a much easier and more natural flow and when I’m done, I’m done—I don’t have to mark messages for archiving and all that.

Now, at last, desktop Gmail has a preview pane. It’s still a “Gmail Labs” project so you have to enable it—see the linked article for directions—but once you do that it works fine. Jason Kincaid, who wrote the TechCrunch article above, has a few problems with it but I’m happy. Very happy. The first time I used it I expanded my browser to full screen, which on my 27-inch iMac gives everything plenty of room, but I’m not sure I really need to do that; After all, it works fine on the iPad’s 9.7 inch screen. I’ll experiment with it a bit more before I settle on a definite routine. For now, I’m just happy to have this functionality on my desktop as well as my iPad.

Posted in General | Leave a comment

The Emacs Info Apropos Command

Posted on 2011-08-05 by jcs

I’m a longtime Unix programmer. I started before Linux or FreeBSD and if you count Xenix, I programmed on versions as early as System III. As a result, I came to view the man page as the sine qua non of Unix documentation. Later, the GNU project introduced the texinfo format but by then I was well into curmudgeonhood and I never did warm up to info. Part of the problem was info itself. As far as I’m concerned, it’s unusable. I know, I know, lots of people love info. I’m not one of those people. When I absolutely had to read an info page I used a little Tcl/Tk utility called tkinfo. I still used it grudgingly but at least it was usable.

Back in those days, I was a vi user, so info or tkinfo were pretty much the only choices. When I moved to Emacs, I was delighted to discover that its info interface was much better so, while I still preferred man pages, I got much more comfortable with info documentation. One problem I still had even with the Emacs info reader was that it’s hard to search for specific text if you’re not already on the proper node. Now Mickey over at Mastering Emacs has written an excellent post on Full Text Searching In Info Mode With Apropos that showed me how to solve that problem.

The info-apropos command (【Meta+ x】 info-apropos) will do a text search of all the info documentation (not just Emacs documentation) on your system. It produces an apropos-like buffer containing each match and an indication of what node it’s in. You can select one of the matches in the usual info mode way and go directly to the corresponding info node.

Mickey’s post covers other apropos-type commands so you should definitely head over there and absorb some of his wisdom.

Posted in General | Tagged | Leave a comment

Sum Of Two Integers

Posted on 2011-08-04 by jcs

A couple of days ago, I wrote about upgrading to Clozure Lisp 1.7 and remarked that I should try it out with a miniproject, perhaps from Programming Praxis. I went over there and found the Sum of Two Integers problem, which looked interesting. The problem is given a list of integers and a target integer determine if there are two integers in the list that sum to the target.

I chose to interpret the rules strictly:

  • You can make no assumptions about the list of integers. They could be positive, negative, or zero. Numbers might be repeated multiple times. They are not sorted and you do not know the maximum or minimum number without checking the list.
  • Similarly, you can make no assumptions about the target number other than that it’s an integer
  • You must find exactly two integers that sum to the target number—you can’t reuse a number or just find the target in the list. Thus, if the target is 10 and 5 is in the list, there must be another 5 in the list for (5, 5) to be a solution. Similarly, if 10 is in the list, that’s not a solution unless 0 is also in the list.

Truth to tell, if this were a one-off most of us would just hack up the obvious n2 solution with two nested loops checking each pair of numbers in the list. Of course, none of us would admit to doing such a thing so the question is: can we find a better solution? My first thought was to use a bit array where the nth bit is set if n is in the list. That leads to a O(n) solution but there are some problems:

  • You need a second array to indicate whether a given number is repeated at least once in the list.
  • You really need to know the maximum number in the list to size the bit array properly.
  • It doesn’t handle negative numbers gracefully.

I did code up a solution like this under the assumption that there were no negative numbers but that doesn’t solve the problem so we need another solution.

We can use almost the same solution by substituting a hash table for the bit array. With this solution, each integer in the list is a key for the hash table and the value corresponding to the key is the count of the occurrences of the key in the list of integers. We need to go through the list twice1: once to build the hash table and once to check to see if a number in the list has the required number that sums to the target.

The code below implements this solution. The check routine on lines 9–19 does all the real work. For each number in the list (have) we calculate the number we need to sum to the target (need) and then check to see if need is in the hash table. If it is, we’ve found a solution (line 18), if it’s not we recursively call check with the cdr of the list (line 19). Lines 15–17 check for the special case of a number being exactly half of the target. In that case we’ve found the solution if the number is in the list at least twice. 

 1:  (defun hash-numbers (numbers)
 2:    (let ((ht (make-hash-table :size (length numbers))))
 3:      (dolist (n numbers)
 4:        (setf (gethash n ht) (1+ (gethash n ht 0))))
 5:      ht))
 6:  
 7:  (defun check-sums (goal numbers)
 8:    (let ((ht (hash-numbers numbers)))
 9:      (labels ((check (numbers)
10:                 (if (null numbers)
11:                     nil
12:                     (let* ((have (car numbers))
13:                            (need (- goal have)))
14:                       (cond
15:                         ((= need have) (if (> (gethash need ht) 1)
16:                                            (list have have)
17:                                            (check (cdr numbers))))
18:                         ((gethash need ht) (list have need))
19:                         (t (check (cdr numbers))))))))
20:        (check numbers))))
21:

This solution won’t be as fast as the bit array solution (given a decent implementation of bit arrays) but it’s still pretty efficient and it avoids all the problems with the bit array solution.

Can we do better than O(n)? What if we know the list is sorted?

Update: 2011-08-05 Fri
I looked through the solutions that other Programming Praxis readers submitted looking for something better than O(n). I didn’t find anything but Graham and some others noticed that you could combine the testing with the building of the hash table. Here’s my translation of Graham’s Python solution 

(defun check-sums-2 (goal numbers)
  (let ((ht (make-hash-table :size (length numbers))))
    (dolist (n numbers)
      (if (gethash (- goal n) ht)
          (return (list n (- goal n)))
          (setf (gethash n ht) t)))))

It still O(n) but faster because it only goes through the list once. It’s also simpler.

Footnotes:

1 Actually, the solution goes through the list 3 times; calculating the size of the list also requires reading through the list.

Posted in Programming | Tagged | Leave a comment

Some More Emacs Tips

Posted on 2011-08-03 by jcs

Gurmeet Manku shares some Emacs Tips n Tricks for Everybody on his homepage. A lot of these will be familiar to most Emacs users and some are things I wouldn’t want to do but it’s a nice list of things you can add to your .emacs file to make your development work easier and more enjoyable.

One interesting example is a pair of functions that swap the numeric keys with the shifted numeric keys (1 ↔ !, 2 ↔ @, 3 ↔ #, etc.). The idea is that this makes typing faster when editing C/C++ code. A companion function maps __ into -> and .. into [] for pointer notation and array indexing. I’m not sure I’d like this but if you do a lot of C/C++ and can deal with the schizophrenia it could be a time saver.

Another useful trick is to add 

(modify-syntax-entry ?- "w")

to your emacs-lisp-mode-hook so that - is not considered a word delimiter. Similarly, 

(modify-syntax-entry ?_ "w")

when added to c-mode-common-hook will prevent _ from being a word delimiter. I don’t know why this isn’t built into Emacs.

There are a lot of other ideas in the article and it’s well worth a look if you’re interested in ways of streamlining your Emacs work flow.

Posted in General | Tagged | Leave a comment

Clozure Lisp 1.7 Is Out

Posted on 2011-08-02 by jcs

I haven’t been doing very much Common Lisp programming lately but I noticed that Clozure Common Lisp 1.7 has just been released so I upgraded. I always like to do a (rebuild-ccl :full t) when I install a new version but my recent upgrade to Lion meant that I didn’t have up-to-date build tools so I also downloaded the new Xcode.

I have one of the free developer accounts but this time I just used the App store. The download took forever, of course, and then it just left the installer in Launchpad so I didn’t realize it had finished. Once I got the new Xcode installed the rebuild-ccl completed normally.

Now I should try it out with some miniproject. Programming Praxis is always a good source of that type of thing so perhaps I’ll head over there and try one of their recent exercises out.

Posted in Programming | Tagged , | Leave a comment

Putting Shell Output In The Current Buffer

Posted on 2011-08-01 by jcs

I’ve long used 【Meta+|】 to pipe a region to a shell command. I use it all the time to pipe troff input to groff and display the results with gxditview. Recently I learned that if you specify a prefix arg it will place the results in the current buffer. The easiest way to do that is simply to type 【Meta+1 Meta+|】. The same trick works with 【Meta+!】. For example, if I want to insert a directory listing into the current buffer I could type 【Meta+1 Meta+!】 ls.

Summary of Key Sequences

  • 【Meta+|】
    Pipe the highlighted region to a shell command and place the output in a ∗Shell Command Output∗ buffer.
  • 【Meta+1 Meta+|】
    Pipe the highlight region to a shell command and place the output in the current buffer.
  • 【Meta+!】
    Run a shell command and place the output in a ∗Shell Command Output∗ buffer.
  • 【Meta+1 Meta+!】
    Run a shell command and place the output in the current buffer.

Update: prefix tag → prefix arg

Posted in General | Tagged | 3 Comments

The New Luddites Redux

Posted on 2011-07-30 by jcs

It’s been a long time since I’ve written about the New Luddites—the last time was early on in my old blog (1, 2, 3)—but sadly their silliness has surfaced again. I follow Shelly Palmer’s Digital Living blog, which is geared towards the non-technical user of consumer electronics but often has interesting posts. Yesterday he reported on a CNN article that discussed smartphone users obsessively checking their phones. That article, in turn, mentioned a study published in the Journal of Personal and Ubiquitous Computing.

Palmer begins by poking fun at the study for belaboring the obvious but then goes on to take its conclusions seriously and offer “solutions” for our addictive behavior. The study itself is not particularly compelling. Its methodology is ad hoc and its sample sizes are ludicrously small (the largest of the 3 studies had 36 participants, another 12, and the last studied 3 groups with single digit participants).

What are the study’s results that have so alarmed Palmer? The participants checked their smartphones an average of 34 times a day. Really? Assuming they were sleeping 8 hours a day that amounts to checking their phones every half hour. That’s addictive behavior?

First of all, it’s silly to use the word addictive with its overtones of alcoholism or hard drug use. Those habits clearly are harmful both physically and emotionally. The most harmful thing pointed to by the CNN article was that one man’s frequent checking of his smart phone annoyed his wife. Many people today choose to live a digital life: they read ebooks, get their bills as emails, keep electronic diaries, maintain friendships through social media, use Google as a sort of associative memory, and most of all stay connected all the time. The device that enables this lifestyle is the smartphone. Of course these people check their phones frequently.

To devise tactics to reduce smartphone use as Palmer suggests makes no sense except as a bizaro world yes-I-can type of experiment. Twenty years ago the equivalent exercise would have been to go without electricity and air conditioning for a week just to prove you could. Just as it was silly to worry about becoming habituated to electricity and A/C, it’s silly to forgo the advantages of smartphones on the grounds that using them twice an hour is addictive behavior. The New Luddites are always with us, of course, but I was surprised and saddened to see the author of Overcoming the Digital Divide: How to use Social Media and Digital Tools to reinvent yourself and your career give them aid and comfort.

Update: bizzaro → bizaro

Posted in General | Leave a comment

Scrolling With Lion

Posted on 2011-07-28 by jcs

OS X 10.7 (Lion) has been out for about a week and although that’s probably not enough time for any subtle bugs to surface, it is, apparently, enough time for my natural paranoia to be overcome by my desire to give it a spin. So over the last couple of days I’ve updated my machines with Lion—the upgrades went extraordinarily smoothly; thanks for asking.

I’m still getting used to the OS so I don’t have much of substance to say right now but I can comment on one issue that’s getting mentioned a lot in the reviews that I’ve read: scrolling. If you’ve been paying any attention to Lion, you know by now that Apple has “reversed” the scrolling. Swiping down with two fingers used to scroll towards the bottom of the page; now it scrolls towards the top of the page. It’s easy to reinstate the old behavior with the System Preferences pane but that hasn’t stopped the howls of anguish—not to say outrage—from many of the commenters.

The idea is that the new behavior mimics what happens with iOS when you scroll: you’re grabbing the screen and pushing it up or down. Despite having a small problem with muscle memory, I like the change. The old behavior never made sense to me and only muscle memory and the fact that it had always been that way kept me from being totally confused. If I thought too hard about it I would do the “wrong” thing. After only a few hours the new scrolling already feels natural. Sometimes I start to move in the wrong direction but that is already starting to die out. If you’re having trouble with the change, just imagine that you are putting your fingers on the text and pushing it in the direction you want to go.

I’m sure there’ll be lots of kvetching and dark mumbling about Apple oppressing their users and upsetting the natural order of things but, really, all Apple has done is finally have scrolling make sense. And, you know, if you really, really don’t like it, it’s easy to change it back.

Posted in General | Tagged | Leave a comment

Using set-mark-command To Remember Locations

Posted on 2011-07-27 by jcs

A couple of days ago I wrote a note to myself post to help me remember the align-regexp functionality. Today’s post is another note to myself. A recent post by Xah Lee reminded me of some Emacs functionality that I am always forgetting. Every time I see the set-mark-command function described I think, “Boy, that’s really useful, I need to remember it.” Then I promptly forget about it again.

The set-mark-command (bound to 【Ctrl+Space】) sets the mark at the point’s position. The normal way of invoking it to remember locations is to type 【Ctrl+Space Ctrl+Space】. The first 【Ctrl+Space】 sets the mark and the second deactivates it so that no region is highlighted. Emacs also pushes the mark onto the buffer’s mark ring and onto the global mark ring.

This is useful because we can use the marks recorded on the mark rings to return to a remembered location. If we want to return to a previous mark in the same buffer, we type 【Ctrl+u Ctrl+Space】 We can move back several locations by repeating the 【Ctrl+u Ctrl+Space】.

If we want to return to a mark which may be in another buffer we can type 【Ctrl+x Ctrl+Space】. This can also be repeated to move back several marks.

This may seem confusing but it boils down to just three key sequences

  • 【Ctrl+Space Ctrl+Space】 to push the current position onto the mark rings.
  • 【Ctrl+u Ctrl+Space】 to return to a previous position in the same buffer.
  • 【Ctrl+x Ctrl+Space】 to return to the previous position, which may or may not be in the same buffer.
Posted in General | Tagged | 6 Comments