[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))