[plt-scheme] Teaching Scheme

Dear Mr Williams, 

the founders of this list have written an extensive list of papers 
on why it is appropriate to NOT teach novices with ANY off the
shelf programming language, including Scheme. ALL languages
for professional programmers are BAD languages for novices. 

Instead of listing all papers, let me suggest two that are good 
starting ponts for chasing our 15 years adventure backwards: 

 http://www.ccs.neu.edu/scheme/pubs/#icfp09-fffk
 a somewhat technical article that includes what we can 
 accomplish with middle school (US terminology!) kids 

 http://www.ccs.neu.edu/scheme/pubs/fk-cacm09.pdf
 the draft of a CACM Viewpoint that provides an abstract 
 perspective of our stuff ; a true print is available in the ACM 
 on-line library 

You have permission to post those links and any other links
from my web site on your site BUT NOT on the "pro Scheme" 
page. 

In my mind there are three critical points: 

1. Don't listen to students and their interests. Teach everyone. 
2. Make sure your teachings help even those who don't pursue
    a college-level CS degree. 
3. Teach systematic program design, not programming. 

For your perusal, I have appended are two versions of your 
'100 doors' problems: 

  FP, good: a functional, well-designed version 

  IMP, sloppy: an attempt on my side to write PLT code that 
    is as bad as the C version at your site. I went thru an 
    intermediate FP version that was as compact and in the 
    end I just couldn't drop the unit tests. Sorry. 

They are both intended to be run from with DrScheme our
pedagogic environment (see web page for another article). 
This prints the results -- as a truly 'interpreted' language 
ought to do. (PLT Scheme is jit-ed, sorry.) 

You're welcome to post these solutions, if you include the 
first paragraph of this message and my name. 

As Dr Bloch showed, a bit of math produces a closed-formula
result. 

If my solution is 'off by one', feel free to fix. I am sure it's 
straightforward. 

-- Matthias


====================================================

FP, good: 
#lang scheme

(require schemeunit)

#| 100 doors is a relatively simple mathematical problem. If you have 100 doors 
   that are initially closed, and follow this procedure:

   Walk past the doors 100 times, the first time you toggle every door (if the 
   door is closed, you open it, and vice versa). The second time, you only visit
   every second door, the third time every third door. This continues until you 
   only visit the 100th door ... what doors are remaining open?
|#

;; Natural -> [Listof Natural]
(define (main tours)
  (define doors0 (build-list 100 (lambda (i) (make-door i CLOSED))))
  (define doors* 
    (for/fold ((doors doors0)) ((s (in-range tours))) 
      (map (lambda (door) (door-toggle door (+ s 1))) doors)))
  (map (lambda (d) (+ (door-index d) 1)) 
       (filter (lambda (door) (eq? OPEN (door-state door))) 
               doors*)))

;; --- door data representation --- 
(define OPEN #t)
(define CLOSED #f)
;; State = (U OPEN CLOSED)

(define-struct door (index state) #:prefab)
;; Door = (make-door Natural State)

;; Door Natural -> Door 
;; toggle state of door if its index is reachable from the beginning via stride
(define (door-toggle door stride)
  (define i (door-index door))
  (define s (door-state door))
  (make-door i (if (= (modulo i stride) 0) (not s) s)))

;; -- tests ---
(check-equal? (door-toggle (make-door 0 CLOSED) 1) (make-door 0 OPEN))
(check-equal? (door-toggle (make-door 1 OPEN) 2) (make-door 1 OPEN))
(check-equal? (main 0) '())
(check-equal? (main 1) (build-list 100 add1))
(check-equal? (main 2) (build-list 50 (lambda (i) (* 2 (+ i 1)))))

;; --- run --- 
(length (main 100))


====================================================
IMP, sloppy 

#lang scheme

(require schemeunit)

#| 100 doors is a relatively simple mathematical problem. If you have 100 doors 
   that are initially closed, and follow this procedure:

   Walk past the doors 100 times, the first time you toggle every door (if the 
   door is closed, you open it, and vice versa). The second time, you only visit
   every second door, the third time every third door. This continues until you 
   only visit the 100th door ... what doors are remaining open?
|#

;; Natural -> [Listof Natural]
;; run t tours of walking along the doors and toggling their state 
(define (main t)
  (define OPEN #t)
  (define CLOSED #f)
  (define DOORS 100)
  (define doors* (make-vector DOORS CLOSED))
  ;; [0,DOORS) [0,DOORS) -> VOID
  ;; toggle the door's state if it is on the stride 
  (define (toggle! door stride)
    (when (= (modulo door (+ stride 1)) 0)
      (vector-set! doors* door (not (vector-ref doors* door)))))
  ;; -- IN -- 
  (for ((stride (in-range t)))
    (for ((door (in-range DOORS)))
      (toggle! door stride)))
  (for/fold ((opens* '())) ((door (in-range DOORS)))
    (if (eq? (vector-ref doors* door) OPEN) (cons (+ door 1) opens*) opens*)))

;; -- tests ---
(check-equal? (main 0) '())
(check-equal? (main 1) (reverse (build-list 100 add1)))
(check-equal? (main 2) (reverse (build-list 50 (lambda (i) (* 2 (+ i 1))))))

;; --- run --- 
(length (main 100))