Streams in Common Lisp

One of nicest techniques from Scheme is the idea of streams. Streams1 let you create a virtually infinite list. For example, we can compute the square roots of the first 5 Fibonacci numbers with

(mapcar #'sqrt '(0 1 1 2 3))
0.0 1.0 1.0 1.4142135 1.7320508

But suppose we want to print the square roots of an arbitrary number of Fibonacci numbers. We'd like something like

(setq list-of-fibonacci-numbers '(0 1 1 2 3 5 8 13 21 34))
(defun sq-roots (n l)
  (when (> n 0)
    (print (sqrt (car l)))
    (sq-roots (1- n) (cdr l))))

(sq-roots 5 list-of-fibonacci-numbers)
0.0 
1.0 
1.0 
1.4142135 
1.7320508 

where list-of-fibonacci-numbers has at least n members. Of course we don't know what n will be so we really need a infinite list of Fibonacci numbers. That's what streams do. They simulate an infinite list by calculating the members of the list on-the-fly as needed.

Atabey Kaygun has a nice post that considers how to implement Scheme streams in Common Lisp. Rather than simply duplicate the Scheme implementation, which, as I show below, is relatively easy, Atabey produces two different implementations. One, that he describes as “stateful,” uses a closure to remember the state of the stream and calculate the next value.

The other method is more functional and builds an actual list as the calculation proceeds. He uses this method to build a stream, fibonacci, that returns the Fibonacci numbers. Using that we can solve our problem as

(defun sq-roots (n)
  (labels ((roots (i l)
             (while (> i 0)
               (print (sqrt (car l)))
               (roots (1- i) (cdr l)))))
    (roots n (f-take n fibonacci))))

We can't express the Fibonacci numbers with Atabey's stateful implementation but it could be trivially modified to permit it. The trouble with the stateful solution, as Atabey tells us, is that it's use-once. Even if we hold its head, any use of the stream modifies its internal state so that further uses reflect what has already happened.

These examples are instructive but notice that we must build the list of n Fibonacci numbers before we can start the calculations. What if n=10^{10}? That's a pretty big list and will almost surely exceed the memory of most computers. What we'd like is a “lazy list” that calculates its elements on-the-fly. That's what streams do.

Here's a Common Lisp implementation based on the Scheme from Section 3.5 of SICP. The real implementation builds memoization into delay but we ignore that for simplicity. See SICP's implementation or Atabey's memoization post for details. The basic building blocks are given below:

(defmacro delay (expr)
  `(lambda () ,expr))

(defun force (delayed-object)
  (funcall delayed-object))

(defmacro cons-stream (x y)
  `(cons ,x (delay ,y)))

(defun stream-car (s)
  (car s))

(defun stream-cdr (s)
  (force (cdr s)))

The delay macro delays the evaluation of expr by wrapping it in a function. The force function evaluates the delayed expression by calling the function that it got wrapped in. The cons-stream builds a cons from x and y but arranges to delay the evaluation of y. The last two functions are direct analogues of their list counterparts but operate on streams instead. Notice that we can do without stream-car since it merely calls car. See SICP for further explanation.

Now, we can build some infinite lists (streams). Suppose we want an infinite list of integers. Here it is:

(defun integers (&optional (n 1))
  (cons-stream n (integers (1+ n))))

The first time it's called, integers returns

(1 . (lambda () (integers (1+ n))))

where n=1 and n is held in integers' closure. When stream-cdr is called on this, the call to integers will be evaluated and return

(2 . (lambda () (integers (1+ n))))

with n=2. Thus, the physical stream is just a single cons but it acts as an infinite list of integers.

Let's take the square root of the first n integers. First we define a function to take the square root of the first n elements of a stream:

(defun sq-roots-of-stream (n s)
  (when (> n 0)
    (print (sqrt (stream-car s)))
    (sq-roots-of-stream (1- n) (stream-cdr s))))

and then pass it a steam of integers:

(sq-roots-of-stream 10 (integers))
1.0 
1.4142135 
1.7320508 
2.0 
2.236068 
2.4494898 
2.6457512 
2.828427 
3.0 
3.1622777

Notice that the list of integers is not calculated in advance.

Here's the solution to our original problem. First, a stream of Fibonacci numubers:

(defun fibs (&optional (a 0) (b 1))
  (cons-stream a (fibs b (+ a b))))

and then we reuse sq-roots-of-stream to calculate the results:

(sq-roots-of-stream 10 (fibs))
0.0 
1.0 
1.0 
1.4142135 
1.7320508 
2.236068 
2.828427 
3.6055512 
4.582576 
5.8309517

Once you get the hang of it, it's really easy to work with streams and it avoids having to precalculate large lists of intermediate results.

Footnotes:

1

In Common Lisp, streams refer to input/output channels such as STDIN and STDOUT. I'm using the term in the Scheme sense.

Posted in Programming | Tagged , | Leave a comment

Comment or Uncomment One of More Lines

Artur Malabarba over at Endless Parentheses has a handy optimization for commenting out a single line or, perhaps, n lines at once. The usual procedure is to select the lines you want to comment and type 【Meta+;】 to call comment-dwim. I use that all the time but what if you want to comment (or uncomment) just one or perhaps a few lines?

Malabarba's code comments/uncomments the current line or n lines if a numerical prefix is given. He binds it to 【Ctrl+;】 which gives it a nice symmetry with 【Meta+;】.

In the comments, Scott Turner suggests a version that calls comment-dwim if there is a region set and Malabarba's code otherwise1. You could then just rebind【Meta+;】to the new version and have the best of both worlds2. Either way, if you find yourself commenting and uncommenting lines a lot, you may find this bit of Elisp handy.

Footnotes:

1

Be aware, though, that comment-dwim has its own default actions if there is no region. You may or may not care about them.

2

This, too, can be problematic. paredit, at least, also remaps 【Meta+;】.

Posted in General | Tagged | Leave a comment

Days of Our Lives

Posted in General | Tagged | Leave a comment

Micro-Habit Video

If you liked Sacha Chua's post on micro-habits that I wrote about yesterday, be sure to check out her video on the same subject. In it, she discusses various packages for switching windows and for jumping around in a buffer or even multiple buffers.

She also discusses how she leverages the key-chord package to invoke her window switching and buffer navigation. You don't have to worry about trying to remember her configuration because it's available online in an excellent literate programming Org file. Watch the video and get any specifics you need from her configuration file.

The video is just over eight and a half minutes so it should be easy to fit a viewing into your schedule. As always with Chua, your time will be well spent.

Posted in General | Tagged | Leave a comment

Sacha on Emacs Micro-Habits

Sacha Chua, as everyone here knows, is relentless about improving her work flow and procedures. Happily for us, she's also diligent about sharing the results of her efforts with the rest of us. Her recent outstanding post on cultivating Emacs micro-habits is an excellent example of this.

She's thought more deeply than most of us about which habits make sense and are worth the effort to burn into our muscle memory. The post represents some of her conclusions so far. Even if you're an experienced Emacs user, you are likely to find something useful in the post that you didn't know.

For example, she has a nice idiom for dealing with the problem of writing commands that work on the entire buffer unless a region is defined. I've long used a macro for that but Chua has another way. Suppose we want to extract the contents of a buffer into a string unless a region is defined, in which case we want the contents of just the region. Chua uses conditon-case like this:

(setq contents (condition-case nil (buffer-substring beg end) (mark-inactive (buffer-string))))

That's not a micro-optimization in itself but is part of a function that copies code into a blog post, posts it as a Gist, and adds a link to the Gist in the blog post. That's something useful too if you post code as a Gist.

Another nice trick I learned is how to programmatically retrieve properties from an Org mode buffer. That's also very useful if you want to write code to automatically process an Org buffer.

The whole post is full of goodness and you really should give it a read. If you're interested in improving your work flow, you'll probably find something useful.

Posted in General | Tagged , | 5 Comments

Identifying Muslim Taxi Drivers

Remember that NYC Taxi Commission data set that was used to identify strip club patrons and the comings and going of celebrities? Another data analyst has shown how it can be used to identify Muslim cab drivers. There's nothing wrong with being Muslim and driving a taxi, of course, but it does seem like a privacy issue. A person's religion and ethnicity is a private matter that only the individual should be able to reveal.

This shows, once again, the dangers of collecting and storing seemingly innocuous data. If you don't care about strip club patrons, how about religious freedom? And what was the rationale for collecting this taxi data again?

Posted in General | Tagged | Leave a comment

The Emacs Operating System

Well, Emacs can't really be an operating system because it doesn't implement things like file systems, device drivers, and a TCP/IP stack. When we joke that Emacs is an OS, what we really mean is that it can replace many or most of the user-mode system utilities.

Remember that experiment that ran Emacs alone on a Linux kernel? That's pretty close to Emacs as an OS but, really, who would want to work in such an environment? It was an interesting and revealing experiment but not really practical.

Now, Howard Abrams has come close to a practical Emacs OS. He configured Emacs to act as a window manager. Almost all of the action takes place in Emacs including shells and, through eww, most browser activity. For the occasional Web page that requires JavaScript or otherwise doesn't render well in eww, Abrams arranged to pop up a Chrome page. Take a look at Abrams' post for the details.

Although the system is clearly usable and useful, it's not one that I'd want to live in. To be fair, it's not one that Abrams lives in either. It's the setup he uses for a virtual machine running on his work laptop that he uses for personal work. That way, he keeps work and personal computing strictly segregated. It's a nice solution for that situation and one that you might want to explore if you have a similar problem.

I'm really comfortable in my highly customized laptop environment and so in a similar situation I'd shove my laptop into my backpack and take it with me. I will say, though, that as I move more and more of my work into Emacs, a setup like Abrams' might be good enough for occasional work like personnel computing at work.

Posted in General | Tagged | Leave a comment

Sacha Chats with Steve Purcell

Sacha Chua has held another excellent Emacs chat. This time, it's with Steve Purcell. I've written about Purcell a few times and I've certainly stolen a ton of Emacs code from him. He's got his fingers in an incredible number of Emacs projects and helps run the MELPA repository.

Like many of us, Purcell came to Emacs from VIM. He was attracted to its extensibility and has been busy extending it ever since. He's an interesting guy and his chat with Chua was very entertaining. As usual, Chua and Purcell explore his Emacs configuration and some of his work flows.

I've already installed two of the packages they discussed. The first is whole-line-or-region, a package that arranges for some of the commands that work on regions to work on the current line if no region is defined. It's more useful than you might think as his demonstration of it in the video shows.

The other package is ibuffer-vc that allows you to group the entries in an ibuffer listing by the repository they inhabit. Then you can act on them as a group. For example, if you are working on several files in a repository, you can delete their buffers all at once when you're done. It's very handy.

As many of you know, I have several pieces of Elisp that run certain applications, such as Eshell, in full screen and then restores the window configuration when I'm done. Purcell has a package that generalizes this capability to make it easy to run any Emacs application in full screen. I didn't install it because I've already solved the problem for the cases I care about but if you think you might like to run some apps in full screen, you should check out the fullframe package in MELPA.

UPDATE: fullscreenfullframe

Posted in General | Tagged | Leave a comment

Another Convert

Picking them off one by one…

Posted in General | Tagged , | Leave a comment

Refactoring CamelCase

If, like me, you consider CamelCase symbol names to be the mark of the beast, Arne Babenhauserheide has you covered. He recently found himself having to convert names like CamelCase to camel_case. He found some code on the Emacs Wiki, added some glue to make it interactive, and used a keyboard macro to convert everything.

If you follow the link to the Wiki page, you'll discover that there's also code to convert to

  • CamelCaseSymbols
  • underscored_symbols
  • dashed-symbols
  • colonized::symbols

The code is simple enough that you can easily add some other special format that you might need.

Again, Emacs letting you have it your way.

Posted in General | Tagged | 3 Comments