August 10, 2007

I’ll never be rich…

Posted in Books, Programming, Scheme at 1:34 pm by pmatos

As already everyone in the Lisp community knows, Lisp In Small Pieces had a small price in the last few days. It became #1 in books and then the price went back to $94.40.

I had the time to buy myself one copy of it yesterday by $3.95. I thought myself as a lucky guy who found a great book for a real bargain and that I was smart buying one. So, I told this story to Jenny, Jordi and Noura here in ECS and it seems Jenny business eye caught immediately how stupid I was in buying only one!!! Well, in fact, if I had any kind of business intuition I would have bought not one but 10 or 20, to sell them afterwards by higher prices but obviously lower elsewhere so that I could sell them and have a huge profit.

Two questions remains: If I had bought 20 of them would I be able to sell them (are there enough Lispers out there without the book willing to buy it)? And out of curiosity, did anyone buy more than one book in order to profit from its selling in the future?

Oh well, this way I’ll definitely never get rich… I’ll just keep saving some money to be able to buy some cheap things for me but I’ll never get to be a wealthy man.

July 24, 2007

Failure Story on ICFP07…

Posted in Programming, Scheme at 9:25 pm by pmatos

My last weekend was spent on working out a solution in PLT-Scheme for the ICFP07 task. Amazingly fun, well-written, well-imagined task and poor code development on my part briefly resumes it. It was nonetheless, a lot of fun!!!

If you’re not confortable with the task description, you should look at it to understand what’s coming next. So I had to read a huge string from a file, Endo DNA, formed by 4 characters I, C, F and P. My approach was “Let’s get something done and then I’ll optimize if I need to.” And so it was…

Reading a file is pretty easy:

(define (get-line-from-file str)
    (let ([filefp (open-input-file str)])
        (read-line filefp)
        (close-input-port filefp))))

I now, started to think that it would be nice not only to have it in the string, but also to optimize prepends to this string and character skips and since th DNA string was global, I decided to make it global in my module also.

  (define *dna* "")
  (define *dna-index* 0)

  (define (set-dna! str)
    (set! *dna* str)
    (set! *dna-index* 0))

  (define (dna-prefix? str)
    (string-prefix? str *dna* 0 (string-length str) *dna-index* (string-length *dna*)))
  (define (dna-drop! n)
    (set! *dna-index* (+ *dna-index* n)))
  (define (dna-substring init end)
    (cond [(or (>= init end) (>= (+ *dna-index* init) (string-length *dna*))) ""]
           (substring *dna* (+ *dna-index* init) (if (> (+ *dna-index* end) (string-length *dna*))
                                                     (string-length *dna*)
                                                     (+ *dna-index* end)))]))
  (define (dna-preppend! str)
    (if (> (string-length str) *dna-index*)
        (set-dna! (string-append str (string-drop *dna* *dna-index*)))
          (set! *dna-index* (- *dna-index* (string-length str)))
          (string-copy! *dna* *dna-index* str))))                                

  (define (dna-ref n)
    (if (>= n (dna-length))
        (string-ref *dna* (+ *dna-index* n))))
  (define (dna-length)
    (- (string-length *dna*) *dna-index*))
  (define (find-smallest-dna-suffix s i)
    (let loop ([k 0])
      (let ([sstr (dna-substring (+ k i) (+ k i (string-length s)))])
        (cond [(string=? sstr "") #f]
              [(string=? s sstr) (+ i k (string-length s))]
              [else (loop (+ k 1))]))))
  (define (dna)
    (dna-substring 0 (dna-length)))

This code basically defines a dna string globally and functions to handle this dna string. Also an index to the start of the real DNA string is maintained, because if I skip n chars I don’t want to be dropping chars and then when prepending ending up putting them again on it. So I used this little trick just to have one constant sized string capable of growing if needed. At this moment I considered using evectors but then again… I thought, later I optimize… Now, the code as you may see in the task manually is pretty written almost in a schemish style (if you look to the lets) and with Cish assignments and loops, so I decided to go ahead and do it in the most straighforward way possible. One problem was the finish function which could be called from any other function and it would finish the processing. After some messing around with Scheme and thinking about it I thought it would be a good time to put call/cc to good use.

  (define exit-now (void))

  (define (execute)
    (call/cc (λ (exit)
               (set! exit-now exit)
               (let loop ([iteration 0] [time (current-inexact-milliseconds)])
                 (printf "Execution Iteration : ~a~n"  iteration)
                 (let ([p (begin0 (pattern))]
                       [t (begin0 (template))])
                   (printf "pattern ~a~n" p)
                   (printf "template ~a~n" t)
                   (matchreplace p t)
                   (printf "len(rna) = ~a~n" (/ (rna-length) 7))
                   (printf "Time taken: ~a~n" (- (current-inexact-milliseconds) time))
                   (loop (+ iteration 1) (current-inexact-milliseconds)))))))

  (define (finish)
    (exit-now *rna*))

Once the function execute is called, it sets the exit-now variable to the continuation of execute and the function finish calls it with the rna global variable that we will look into later.

Defining pattern was just looking to the task manual and almost blindly copy it:

    (define (pattern)
    (let repeat ([p ()] [lvl 0])
      (cond [(dna-prefix? "C")
             (dna-drop! 1)
             (repeat (cons 'I p) lvl)]
            [(dna-prefix? "F")
             (dna-drop! 1)
             (repeat (cons 'C p) lvl)]
            [(dna-prefix? "P")
             (dna-drop! 1)
             (repeat (cons 'F p) lvl)]
            [(dna-prefix? "IC")
             (dna-drop! 2)
             (repeat (cons 'P p) lvl)]
            [(dna-prefix? "IP")
             (dna-drop! 2)
             (repeat (cons `(! ,(nat)) p) lvl)]
            [(dna-prefix? "IF")
             (dna-drop! 3)
             (repeat (cons `(? ,(consts)) p) lvl)]
            [(dna-prefix? "IIP")
             (dna-drop! 3)
             (repeat (cons '( p) (+ lvl 1))]
            [(or (dna-prefix? "IIC") (dna-prefix? "IIF"))
             (dna-drop! 3)
             (if (zero? lvl)
                 (reverse! p)
                 (repeat (cons ') p) (- lvl 1)))]
            [(dna-prefix? "III")
             (rna-append! (dna-substring 3 10))
             (dna-drop! 10)
             (repeat p lvl)]
             (printf "finish: called by pattern can't match beginning of DNA: ~a...~n" (dna-substring 0 10))

And the same was try with the template function:

  (define (template)
    (let repeat ([t ()])
      (cond [(dna-prefix? "C")
             (dna-drop! 1)
             (repeat (cons 'I t))]
            [(dna-prefix? "F")
             (dna-drop! 1)
             (repeat (cons 'C t))]
            [(dna-prefix? "P")
             (dna-drop! 1)
             (repeat (cons 'F t))]
            [(dna-prefix? "IC")
             (dna-drop! 2)
             (repeat (cons 'P t))]
            [(or (dna-prefix? "IF") (dna-prefix? "IP"))
             (dna-drop! 2)
             (repeat (cons `(_ ,(nat) ,(nat)) t))]
            [(or (dna-prefix? "IIC") (dna-prefix? "IIF"))
             (dna-drop! 3)
             (reverse! t)]
            [(dna-prefix? "IIP")
             (dna-drop! 3)
             (repeat (cons `(|| ,(nat)) t))]
            [(dna-prefix? "III")
             (rna-append! (dna-substring 3 10))
             (dna-drop! 10)
             (repeat t)]
             (printf "finish: called by template can't match beginning of DNA: ~a...~n" (dna-substring 0 10))

The nat and consts functions seems that could do a little tweaking but again I postponed. Anyway it was Saturday, first competition day for me and I still had the whole day and still sunday so I just wrote:

  (define (nat)
    (cond [(dna-prefix? "P")
           (dna-drop! 1)
          [(or (dna-prefix? "I") (dna-prefix? "F"))
           (dna-drop! 1)
           (* 2 (nat))]
          [(dna-prefix? "C")
           (dna-drop! 1)
           (+ (* 2 (nat)) 1)]
           (printf "finish: called by nat. dna is empty.~n")

  (define (consts)
    (cond [(dna-prefix? "C")
           (dna-drop! 1)
           (string-append "I" (consts))]
          [(dna-prefix? "F")
           (dna-drop! 1)
           (string-append "C" (consts))]
          [(dna-prefix? "P")
           (dna-drop! 1)
           (string-append "F" (consts))]
          [(dna-prefix? "IC")
           (dna-drop! 2)
           (string-append "P" (consts))]
          [else ""]))

The next one were the straightforward matchreplace and replace itself which were the most bug-ridden functions I had in the competition but not amazingly were quite simple to implement:

  (define (matchreplace p t)
    (call/cc (λ (return)
               (let loop ([i 0] [e ()] [c ()] [cp p])
                 (for-each (λ (envel) (print-seq-info "e" envel)) e)
                 (if (null? cp)
                       (printf "successful match of length: ~a~n" i)
                       (for-each (λ (envel) (print-seq-info "e" envel)) e)
                       (dna-drop! i)
                       (replace t (reverse! e)))
                     (match (car cp)
                       ((? symbol? (or 'I 'C 'F 'P))
                        (let ([dna-symb (string->symbol (string (dna-ref i)))])
                          (if (eqv? dna-symb (car cp))
                              (loop (+ i 1) e c (cdr cp)))))
                       (`(! ,n)
                        (if (not (> (+ i n) (dna-length)))
                            (loop (+ i n) e c (cdr cp))))
                       (`(? ,s)
                        (let ([smallest-suffix (find-smallest-dna-suffix s i)])
                          (if smallest-suffix (loop smallest-suffix e c (cdr cp)))))
                       ((? symbol? '()
                        (loop i e (cons i c) (cdr cp)))
                       ((? symbol? '))
                        (loop i (cons (dna-substring (car c) i) e) (cdr c) (cdr cp)))))))

  (define (replace tpl e)
    (let ([env (list->vector e)])
      (letrec ([env-ref (λ (n) (if (>= n (vector-length env)) "" (vector-ref env n)))])
        (let loop ([r ""] [t tpl])
          (if (null? t)
              (dna-preppend! r)
              (cond [(symbol? (car t)) (loop (string-append r (symbol->string (car t))) (cdr t))]
                    [(list? (car t))
                     (if (eqv? (first (car t)) '_)
                         (loop (string-append r (protect (second (car t)) (env-ref (third (car t))))) (cdr t))
                         (loop (string-append r (asnat (string-length (env-ref (second (car t)))))) (cdr t)))]))))))
              (match (car t)
                ((? symbol? (or 'I 'C 'F 'P))
                 (loop (string-append r (symbol->string (car t))) (cdr t)))
                (`(_ ,l ,n)
                 (loop (string-append r (protect l (env-ref n))) (cdr t)))
                (`(|| ,n)
                 (loop (string-append r (asnat (string-length (env-ref n)))) (cdr t)))))))))

Where the print functions are just debugging aids:

  (define (print-seq-info name seq)
    (printf "~a = ~a...(~a bases)~n" name (if (< (string-length seq) 10) (string-length seq) (substring seq 0 10)) (string-length seq)))
  (define (print-dna-info)
    (printf "dna = ~a... (~a bases)~n" (dna-substring 0 10) (dna-length)))

And follows the utility functions for matchreplace:

  (define (protect l d)
    (if (zero? l) d (protect (- l 1) (dna-quote d))))

  (define (dna-quote d)
    (printf "quote: d=NOTSHOWN~n")
    (cond [(string-prefix? "I" d) (string-append "C" (dna-quote (string-drop d 1)))]
          [(string-prefix? "C" d) (string-append "F" (dna-quote (string-drop d 1)))]
          [(string-prefix? "F" d) (string-append "P" (dna-quote (string-drop d 1)))]
          [(string-prefix? "P" d) (string-append "IC" (dna-quote (string-drop d 1)))]
          [else ""]))

  (define (asnat n)
    (cond [(zero? n) "P"]
          [(even? n) (string-append "I" (asnat (quotient n 2)))]
          [(odd? n) (string-append "C" (asnat (quotient n 2)))]))

This finishes up the hard part DNA->RNA, which I had it finished by saturday afternoon… Now, I needed the bitmap part working. Incredibly, using PLT-Scheme functions to handle bitmaps was easy and produced great results, however, didn’t allow me to run this on my server, without X. This is because I needed library which require X to be running, when in fact, no window is being displayed and apparently, no X is in fact being using directly by me. The RNA variable which I didn’t show was defined similarly to the DNA variable and is of no use to show it here. The RNA to image part is of not much interest (because I never got to really optimize it) and you can find the code online. However, with this much code and a little bit more for bitmap generation was enough to generate this from the prefix found in the last task page after about 140 iterations:

First the part where optimization worked beautifully… the replace function:

  (define (replace tpl e)
    (let ([env (list->vector e)])
      (letrec ([env-ref (λ (n) (if (>= n (vector-length env)) "" (vector-ref env n)))])
        (let loop ([r '()] [t tpl])
          (if (null? t)
              (dna-preppend! (apply string-append (reverse! r)))
              (cond [(symbol? (car t)) (loop (cons (symbol->string (car t)) r) (cdr t))]
                    [(list? (car t))
                     (if (eqv? (first (car t)) '_)
                         (loop (cons (protect (second (car t)) (env-ref (third (car t)))) r) (cdr t))
                         (loop (cons (asnat (string-length (env-ref (second (car t))))) r) (cdr t)))]))))))

This version removed the string-appends from all over the body to apply a string-append to a list of strings which is built in reverse order during the loop. The difference of these two versions is quite big.

Now, using PLT-Scheme profiler I started to optimize everything that should up worse than light green (in DrScheme) and decided to remove the match at matchreplace by something similar which in fact didn’t improve much, if at all, this function. This is what is not in place of the match call:

           (let ([obj (car cp)])
             (if (symbol? obj)
                 (cond [(eqv? obj '()
                        (loop i e (cons i c) (cdr cp))]
                       [(eqv? obj '))
                        (let ([substr (dna-substring (car c) i)])
                          (loop i (cons substr e) (cdr c) (cdr cp)))]
                        (let ([dna-symb (string->symbol (string (dna-ref i)))])
                          (if (eqv? dna-symb (car cp))
                              (loop (+ i 1) e c (cdr cp))
                              (return (printf "failed match~n"))))])
                 (if (eqv? (first obj) '!)
                     (if (not (> (+ i (second obj)) (dna-length))) (loop (+ i (second obj)) e c (cdr cp)) (return (printf "failed match~n")))
                     (let ([smallest-suffix (find-smallest-dna-suffix (second obj) i)]) (if smallest-suffix
                                                                                            (loop smallest-suffix e c (cdr cp))
                                                                                            (return (printf "failed match~n"))))))))))))

I also tried to optimize consts and nat by removing all those function calls without much success:

  (define (nat)
    ;; Search for the first P
    (let ([p-pos (let loop ([i 0])
                   (let ([cc (dna-ref i)])
                     (cond [(string? cc) (printf "finish: called by nat. After eating ~a bases can't find a P starting with ~a..." i (dna-substring 0 10))
                           [(char=? cc #P) i]
                           [else (loop (+ i 1))])))])
        (let loop ([pos (- p-pos 1)] [val 0])
          (cond [(= pos -1) val]
                [(char=? (dna-ref pos) #C) (loop (- pos 1) (+ (* 2 val) 1))]
                [else (loop (- pos 1) (* 2 val))]))
        (dna-drop! (+ p-pos 1))))) 

  (define (consts)
    (let const-loop ([i 0] [transf ()])
      (let ([cc (dna-ref i)])
        (if (and (char=? cc #I)
                 (not (char=? (dna-ref (+ i 1)) #C)))
              (dna-drop! i)
              (apply string (reverse! transf)))
            (cond [(char=? cc #C) (const-loop (+ i 1) (cons #I transf))]
                  [(char=? cc #F) (const-loop (+ i 1) (cons #C transf))]
                  [(char=? cc #P) (const-loop (+ i 1) (cons #F transf))]
                  [else (const-loop (+ i 2) (cons #P transf))])))))

And I even optimized template and pattern by replacing calls from

(dna-prefix? "C")


(char=? (dna-ref 0) #C)

without much, or any, success. These benchmark explain why I tried:

> (time (begin (let loop ([i 0])
                 (unless (>= i 3000000)
                   (cond [(dna-prefix? "IP") "C"]
                         [(dna-prefix? "IF") "P"]
                         [else "K"])
                   (loop (+ i 1))))))
cpu time: 32678 real time: 32821 gc time: 3660
> (time (begin (let loop ([i 0])
                 (unless (>= i 3000000)
                   (cond [(dna-prefix? "I") (if (char=? (dna-ref 1) #\P) "C" "P")]
                         [else "K"])
                   (loop (+ i 1))))))
cpu time: 34970 real time: 36296 gc time: 1664
> (time (begin (let loop ([i 0])
                 (unless (>= i 3000000)
                   (cond [(and (char=? (dna-ref 0) #\I) (char=? (dna-ref 1) #\P) "C" "P")]
                         [else "K"])
                   (loop (+ i 1))))))
cpu time: 38086 real time: 38345 gc time: 0

The optimizations took me almost all saturday night and sunday. Sunday evening I was getting desperate. Then I though that with these datastructures there wasn’t probably much more I could do but I was tired and had to work on the next day so I sent and email to the list to let my frustration go when I was advised to go by #oasis @ where people where talking about datastructures and algorithms. I went by to the channel full of people and went to sleep to do nothing else. I’m doing basically ~1 iterations / sec when I should probably be doing 20000 iterations / sec.

Yesterday, I went to look into the PLT-Scheme manual and remembered myself that PLT Scheme string are unicode and probably perform even worse than normal C-strings (in PLT-Scheme, byte-strings) due to that. I shall try change to byte-string and see the results! :-) The more or less cleanified code of what I had is here. Overall, I already saw many possible optimizations, other that are possibly I certainly have not yet come to think about them but it was a whole lot of fun! :-)

May 4, 2007

5min. fun with Euler

Posted in Programming, Scheme at 7:17 pm by pmatos

Project Euler is a site dedicated to Mathematics and Programming. For fun, I just registered and looked at the 152 problems (one more seems to be coming in 14 hours as announced by them) using fast forward. The problems seem very interesting. I’ve opened DrScheme and the easiest problem of all.

Easily I got the answer with:

(let loop ([n 1] [acc 0])
     (cond [(>= n 1000) acc]
             [(or (zero? (remainder n 3)) (zero? (remainder n 5)))
              (loop (+ n 1) (+ acc n))]
            [else (loop (+ n 1) acc)])))

But then I thought… what about a one liner? Also easy.

(require (lib "") (lib "") (lib ""))
(apply + (filter (λ (n) (or (zero? (remainder n 3)) (zero? (remainder n 5)))) (build-list 999 1+)))

Ahgr, I want to go further so I just decided to generalize it to receive any number of possible divisors and any maximum value.

  (require (prefix srfi1: (lib "" "srfi")))
  (define (divisors-sum max . divisors)
    (let loop ([n 1] [acc 0])
      (cond [(>= n max) acc]
            [(srfi1:any (λ (div)
                          (zero? (remainder n div)))
             (loop (+ n 1) (+ acc n))]
             (loop (+ n 1) acc)])))

So I decided to experiment with some numbers:

> (time (divisors-sum 100 3 5))
cpu time: 0 real time: 0 gc time: 0
> (time (divisors-sum 1000 3 5)) ;; our case
cpu time: 4 real time: 10 gc time: 0
> (time (divisors-sum 10000 3 5))
cpu time: 24 real time: 23 gc time: 0
> (time (divisors-sum 100000 3 5))
cpu time: 224 real time: 231 gc time: 0
> (time (divisors-sum 1000000 3 5))
cpu time: 1544 real time: 1600 gc time: 40
> (time (divisors-sum 10000000 3 5))
cpu time: 12753 real time: 13296 gc time: 320

Well, what do you make up of the result? I’m quite astonished. I have not yet tried to prove it but it seems that for some reason the sum of all the numbers divisible by 3 or 5 below 10^n, for (n >= 2) is a number whose value is composed by the digits: 2 3^(n-1) 1 6^(n-2) 8 where in this case k^(n) means n repetitions of k.

The following function computes this number:

 (define (divisors-sum-3-5-for-10 exp)
    (+ 8
       (sum 1 (- exp 2) (λ (i) (* 6 (expt 10 i))))
       (expt 10 (- exp 1))
       (sum exp (- (* 2 exp) 2) (λ (i) (* 3 (expt 10 i))))
       (* 2 (expt 10 (- (* 2 exp) 1)))))

where sum is a trivial function which may be defined as:

  (define (sum init end proc)
    (let loop ([i init] [acc 0])
      (if (> i end)
          (loop (+ i 1) (+ (proc i) acc)))))

So I conjecture that:

(= (divisors-sum-3-5-for-10 i) (divisors-sum (expt 10 i) 3 5)), for i >= 2

This is what fun is all about! :-)

April 11, 2007

Why Scheme needs no comments…

Posted in Scheme at 8:55 pm by pmatos

(define (select-S-in-F-such-that-S-intersect-U-maximal F U)
— From set–greedy-set-cover.scm in Functional Data Structures Galore 2.1

April 7, 2007

PLT-Scheme and the stupidity syndrome…

Posted in Programming, Scheme at 7:22 pm by pmatos

PLT Scheme is huge as compared to the R5RS Scheme standard, on which PLT Scheme builds upon. No matter how much I spend my free time having fun with Scheme, I always get in the end with an “Aha” moment and then I feel deeply stupid.

Check this… I’ve been developing a graph library and I had it ready to upload to Planet, however, I wanted to tweak it some more. To build a sparse graph I had a very simple structure based on lists. The make-sparse-graph should receive two optional arguments, procedures, and return the structure for an empty graph. My version 30 minutes ago was like this:

  ; Constructor
  ;; make-sparse-graph : [node=?] [node?] -> empty sparse-graph
  (define (make-sparse-graph . fns)
    (define (make node=? node?)
      (cons (cons node=? node?) '()))
    (cond [(= (length fns) 0)
           (make eq? (lambda (x) #t))]
          [(and (= (length fns) 1)
                (procedure? (car fns)))
           (make (car fns) (lambda (x) #t))]
          [(and (= (length fns) 2)
                (procedure? (car fns))
                (procedure? (cadr fns)))
           (make (car fns) (cadr fns))]
           (error "make-sparse-graph: Should receive 0 to 2 optional procedures.")]))

I was not really satisfied with it. Through a discussion on PLT-Scheme mailing list, I got to case-lambda, which seemed very nice so I improved it a little to:

  ;; Constructor
  ;; make-fixed-sparse-graph : node=? node? -> empty sparse-graph
  (define (make-fixed-sparse-graph node=? node?)
    (cons (cons node=? node?) '()))

  ;; make-sparse-graph : [node=?] [node?] -> empty sparse-graph
  (define make-sparse-graph
      [() (make-fixed-sparse-graph eq? (lambda (x) #t))]
      [(node=?) (make-fixed-sparse-graph node=? (lambda (x) #t))]
      [(node=? node?) (make-fixed-sparse-graph node=? node?)]))

But… hey, again, by searching through the docs on contracts I found yet again a another pearl opt-lambda and here’s the current version:

  ;; make-sparse-graph : [node=?] [node?] -> empty sparse-graph
  (define make-sparse-graph
    (opt-lambda ((node=? eq?) (node? (lambda (x) #t)))
      (cons (cons node=? node?) '())))

Well, after this… by looking to my first first and to my last one… damn, I feel stupid! Yes, sometimes I have a love-hate relationship with PLT-Scheme… I wonder if I kept searching I would end up with a 10 character function definition. :-)

SATSCheme… A new Project!

Posted in Programming, SAT, Scheme at 11:40 am by pmatos

SATSCheme is a new project by myself and a colleague of mine to develop 2 SAT Solvers, one in C and other in PLT Scheme. I’ve setup  a blog for the project. This way if you’re interested in the developments you just have to subscribe the feed. From the Scheme perspective, it’ll be nice to see how Scheme GC will cope with the constant memory allocation usually performed by a SAT Solver, and how easy it will be to implement it. Moreover, it’ll be nice to compare it to the C version performance-wise and memory-wise. Other than that, the amount of locs will also be an interest analysis. Well, I’m sure there’ll be a huge space for discussion not only about the code itself but also about the SAT algorithms and structures. Hope you keep an eye at the page. Regarding major announcements, I’ll post them around here also.

March 8, 2007

Scheme Education @ Portugal

Posted in Education, Programming, Scheme at 1:27 pm by pmatos

This post was triggered by the following comment to a recent post:

I’m a student at Faculdade de Engenharia da Universidade do Porto, and this first semester, year 1, we’ve studied the Scheme language. My personal opinion is that it is a bit useless and it lacks power. It cannot be compared with python,C,C++,Java.. It is nice for those learning the logic of programing, but, for real development, I think it is really a weak language!
But, anyway, this is just my opinion, try it out :D .

This is a comment from a 1st year, 1st semester student from a highly regarded university in Portugal, where has been common to teach the fundamentals of programming using the Scheme programming language. Having to teach it a couple of times I’ve had many students and I’ve known many teachers. It all comes down to what someone (I shall not name him, since I was not able to find his exact quote on my mail archives) told me once:

The problem with Scheme education is not about bad students. It’s about bad teachers.

I cannot agree more. Most of the student end with this tendency to say that Scheme is a practically useless, weak and nothing more than a pedagogical programming language. This is definitely sad! And this is the tendency that I tried to fight while teaching students because above all, we are not trying to teach students the Scheme Programming Language (or PLT-Scheme , which is what we use), we try to teach programming concepts and use scheme as a tool. We use about 1% of PLT-Scheme to teach these concepts (in fact, we don’t need PLT-Scheme at all… it’s all too powerful, an R5RS compliant interpreter would be enough). I have to stick with the curriculum, no matter what I think about it.

Even though some students might, or not, go through the subject successfully, the problem is that even those that go through it successfully easily lose any kind of interest in the Scheme Programming Language not only because they don’t know much of what the language is able to offer but also because their subject project doesn’t allow them to expand their knowledge about the language and even the teachers tell them Scheme is useless. And teachers tell them Scheme is useless because they incorrectly think it is useless.

In Portugal, as in many other countries, there are lectures (what in Portugal we call “Theoretical classes”) and labs (the so called “Practica/Laboratory classes”) and even though we have very good teachers in lectures, when students need to choose upon going to lectures or labs 95% will prefer to attend labs and miss the lectures. Missing the lectures means missing what good teachers can teach us and instead be in a lab with (many times) a moron dictating how to solve exam exercises and inventing bullshit regarding everything else. In the University of Southampton you have to attend short courses to be able to work as a demonstrator in a lab or even to teach small groups of people and then you’ll only be able to teach things you are used to work with!

Many Scheme teachers (in Portugal and more specifically @ Instituto Superior Tecnico) are people that just like their students left the subject of Programming Fundamentals teaching that Scheme sucks and that’s what they’re teaching their students. It’s impossible to teach something you don’t like, I know that, I had already to teach  something I didn’t like and something I was not really at ease with it. When this happens, things go wrong!

Scheme teaching should motivate students to understand not only the programming concepts but also the language itself  (in this case PLT-Scheme, since R5RS is just too restrictive to be considered a real language, instead it is just a framework to build a greater language). Even though schedules are tight, PLT-Scheme knowledge could come from its use in worksheets to be done at home introducing language aspects like modules, web programming, system programming, GUI programming, shell scripting, etc all possible within PLT-Scheme). Students love this! What students despise is having to find a way to implement a function generating an iterative process given a function which implements a recursive process. But this is important! But if they have to learn this, teachers might as well find a way to sweet student fingertips by making them play with stuff that’s appealing. Otherwise they see PHP for web programming, C for systems programming, C++ or Java or anything for object, GUI, etc… and still think that Scheme is useful for teaching how to implement a function computing the factorial and which generates an iterative process. What they don’t know is that Scheme is also useful to work with other problems… real problems…

In the end it all comes to down to who’s teaching students… if they think Scheme is useless… students will think Scheme is useless… and worst, will later teach their students of Scheme uselessness. I, on the other hand, had a the best teacher one could have at that subject.

February 26, 2007

Scheme and its implementation

Posted in Scheme at 5:31 pm by pmatos

While trying to find references regarding the keywords “pure interpreter” due to a thread on the r6rs mailing list, I just found out this book: An Introduction to Scheme and its Implementation . I haven’t looked into it yet but it seems to be worthwhile of a look.

February 3, 2007

Religious Cults are Never Enough…

Posted in Computers, Lisp, Programming, Scheme at 1:21 am by pmatos

Ah, the good side of religion…

Scheme Church Sign

Brothers and sisters, by following Paolo Amoroso’s cult… I found the truth! Come with me through the path of thy lord…

Behold our patch to the book of genesis:

— genesis.txt 2007-02-03 00:13:29.000000000 +0000
+++ genesis-scheme.txt 2007-02-03 00:19:04.000000000 +0000
@@ -5,9 +5,11 @@
of them.

002:002 And on the seventh day God ended his work which he had made;
– and he rested on the seventh day from all his work which he
+ but something was missing so he implemented define, lambda and some other mystic functions;
+ and said unto the skies, here lies the foundation for a great language;
+ now, multiply through diverse implementations and grow…
+ and in the remaining minutes of the day he rested from all his work which he
had made.

002:003 And God blessed the seventh day, and sanctified it: because
– that in it he had rested from all his work which God created
– and made.
+ that in it he had created his masterpiece that would enlighten all he had already made.

October 31, 2006

Happy Halloween!

Posted in Life, Scheme at 8:18 pm by pmatos

DrScheme has the excellent tradition to remind us of the good thing the best possible way!

Happy Halloween, DrScheme

Next page