Month: August 2008

How to do something to all elements of a list but the last

In this post on the PLT discussion list I sleepily wondered how to do something to all elements of a list but the last.

The reasons I asked is because I had used ‘do’ loops in lieu of something better, and from what I can gather, you basically never write ‘do’ loops in Scheme (maybe once every 30 years you do use ‘do’).

I hastily posted a solution using the ‘match’ library as I had just read the documentation while cutting over from ‘mzlib/match’ to ‘match’. Both Robby and Ethan replied with much, much faster solutions. Have a look: 


#lang scheme

(require (prefix-in srfi/1: srfi/1))

; Grant's
(define (foo1 args fun last-fun)
  (match args
    [(list arg args ..1)
     (fun arg)
     (foo1 args fun last-fun)]
    [(list arg)
     (last-fun arg)]))

(provide/contract
 [foo2 (-> (cons/c any/c (listof any/c))
           (-> any/c any)
           (-> any/c void?)
           void?)])

; Robby's
(define (foo2 args fun last-fun)
  (let loop ([fst (car args)]
             [rst (cdr args)])
    (cond
      [(empty? rst) (last-fun fst)]
      [else (fun fst) (loop (car rst) (cdr rst))])))

(define data (srfi/1:make-list 10000 "hi"))

; Ethan's
(define (foo3 lst fun funl)
  (begin
    (for-each fun (srfi/1:drop-right lst 1))
    (funl (srfi/1:take-right lst 1))))

(time
 (foo1 data
       (λ (x) (void))
       (λ (x) (void))))

(time
 (foo2 data
       (λ (x) (void))
       (λ (x) (void))))

(time
 (foo3 data
       (λ (x) (void))
       (λ (x) (void))))

> cpu time: 2593 real time: 2625 gc time: 718
> cpu time: 0 real time: 0 gc time: 0
> cpu time: 0 real time: 0 gc time: 0

In the end, I only needed this functionality in two places, and I probably would not have required it if I had designed things better in the first place.

ACM SIGPLAN Lisp Pointers

While reading a (now forgotten) comp.lang.lisp post, I saw the publication ACM SIGPLAN Lisp Pointers mentioned. Unfortunately I don’t have access to this part of the digital library (for that you need to be a paying member). Perhaps this is something in to which it is worth looking.
Any time folks are interested in something which is now seen as arcane ought to look into that topics history. With enough research, the air of mysticism is usually lifted enough so that one may start to grow a more accurate perspective on the topic. This is especially relevant for Lisp and programmers today.

2008 IEEE Jon Von Neumann Award Winner: Leslie Lamport

Via IEEE Bios:

Leslie Lamport’s pioneering work in distributed and concurrent algorithms has improved numerous consumer and industrial computing systems. The result of his work can be found in multi-processor technology such as very-large-scale-integration (VLSI) semiconductors and multi-computer networks used in aircraft control systems. Since 2001 he has been at the Microsoft Research Silicon Valley Center, where he is a principal researcher. Prior to that, Dr. Lamport spent 16 years as a researcher at Digital Equipment Corporation (later Compaq Corporation). There he developed the Temporal Logic of Actions (TLA) system, a toolset for mechanical verification that is used to describe the behaviors of concurrent systems. Dr. Lamport developed several well-known concurrent and distributed algorithms, including solutions for Byzantine Fault Tolerance. The algorithm is a method of prevention against Byzantine Failure, in which a component of a system behaves erroneously while failing to behave consistently when interacting with multiple other components in the system. During his career, he has authored or co-authored nearly 150 publications on concurrent and distributed computing and their applications. One of his most notable papers, “Time, Clocks, and the Ordering of Events in a Distributed System,” still ranks as one of the most important and influential papers in computer science. He is a past recipient of the IEEE Emanuel R. Piore Award, the Edsger W. Dijkstra Prize in Distributed Computing and the influential paper award at the Principles of Distributed Computing Conference. Dr. Lamport holds a bachelor’s degree from the Massachusetts Institute of Technology, Cambridge, as well as a masters and doctorate from Brandeis University, Waltham, Massachusetts.

(via this pdf)

Programming in Education: OLPC Case Studies

Ben blogged here about some stories about OLPC case studies. They are all worth checking out.
Listen to the following NPR articles (both found here):

And read this article One Laptop Per New York City Student a Success and report.
The company WavePlace, mentioned in the story, can be found here. Be sure to have a look around the site!

Analogies are a bridge

Analogies are often used to introduce folks to new ideas, introducing them not directly, but through comparison and inference. This seems to work well in all areas, including technical. The risk in using them in technical matters, though, is that person will never move past the analogy and into the realm of accurately understanding the subject matter.
For a long time, I very much disliked analogies. Perhaps this was due to bad personal experiences in my study path with them, or alternately, hearing other folks go on and on about how “such and such is just like such and such” when that is simply not the case. In the past year, though, three interesting things have happened.
The first is that I’ve chatted with someone, who is very level headed and takes the time to talk through his point of view, who is a proponent of analogies.
The second is that I’ve taken a much closer look at how people teach, and, they certainly don’t do it by throwing their students into the deep end.
The third is that I visited a foreign country where it was clear to me that it wasn’t just the language, but just about everything, that I didn’t understand. On the trip I had the experience of analogies about “how things work” in the country just keep popping into my head. It was the strangest thing, but it was interesting, too, because I finally realized the role of analogies:
Analogies are a helpful bridge, that you must cross. If you stay there, you will never get to where you really want to be.