Python code:

def primes(n):
        sieve=[True for x in range(3,n+1,2)]
        root=n**0.5
        length=len(sieve)
        for i in range(len(sieve)):
                x=2*i+3
                if x>root:
                        break
                if sieve[i]:
                        for j in range((x*x-x)/2+i,length,x):
                                sieve[j]=False
        return [2]+[x*2+3 for x in range(length) if sieve[x]]

Scheme code:

Let me quickly respond with a few comments and a snippet of code.

1. Functional programming is something you can do in every  
programming language: assembly, c, c++, java, python, you name it. I  
bet I could do it in cobol.

2. When you do program functionally, it is not about translating some  
snippet of code from one language to another. In case you know a  
foreign language, doing so is like translating English sentences into  
say German word by word. In all likelihood, it makes no sense  
whatsoever.

3. If your task is to sieve through __all__ natural numbers so that  
you get all prime numbers, you program with the object that comprises  
__all__ naturals and get the object of __all__ primes. Picking the  
first n is boring and it is only done because the typical Python  
programmer isn't trained to think of the full range of possibilities.  
(See 1 -- functional programming can be done in pyton). Here is the  
code for that:

#lang lazy ; this is the lazy scheme dialect available with plt  
scheme, both in drscheme and in mzscheme

;; all natural numbers
(define nats$ (cons 0 (map add1 nats$)))

;; all primes
;; Stream[Number] -> Stream[Number]
;; generative: eliminate all first elements from the rest of the  
stream, then recur
(define (sieve s$)
   (define fst (first s$))
   (cons fst (sieve (filter (lambda (m) (not (= (remainder m fst)  
0))) s$))))

(define primes$ (sieve (rest (rest nats$))))

;; --- for you only ---
;; print the first n primes
(define (print-primes n)
   (for-each (lambda (x) (display x) (newline)) (!list (take n primes
$))))

(print-primes 1000)

Here is how this runs:

[home] $ mzscheme sieve.ss
1.827u 0.205s 0:02.18 92.6%     0+0k 0+1io 0pf+0w

4. Now if you want to learn Scheme programming, you're right in that  
Scheme programmers think functionally a lot of the time. But you also  
need ot know that they throw in assignment statements, exceptions,  
continuations, and other effects when needed. Scheme is a full-
spectrum language.

I'll take a closer look at your code now. -- Matthias

On Aug 1, 2009, at 1:35 PM, SiWi wrote:

A few things that I've noticed can all be seen in this expression that

* "Python lists" are really not the same as "Scheme lists".  In
  Scheme, this refers to a linked list, where each item is a "cons
  cell" which holds a value and a pointer to the next item in the
  list.  This makes certain operations much faster.  For example,
  adding a value at the front of an existing list is a constant time
  operation (since it has a pointer to the input list).  It is also
  very natural for a whole bunch of problems that programmers run
  into, and it is easy to iterate over directly.

  In Python, the lists are really more like arrays.  They are faster
  for things like random-access of some value (you just look at the
  given offset in the array), but if you want to add an item at the
  front of the "list", you need to move everything down.  It is also
  inconvenient to iterate on (you can't do it directly, you need to
  use an index as a counter), and it is natural in cases where you
  know that you need a chunk of values, usually of some fixed size
  (some languages allow these arrays to vary dynamically, or even be
  able to use any value for an index).

* In your python code, you just create one such vector, then change,
  and finally collect the results into the output.  In Scheme, you
  keep creating new lists -- which is very expensive.  Think about it
  this way: your `list-bool' function takes the current sieve as an
  input, *copies* it to a new one while changing some bits to true.
  This is obviously much slower.

* Finally, I didn't talk about adding an item at the end of a list.
  With lists, this (append some-list (list new-value)) is very
  expensive because you need to copy the whole list to have a
  different last value.  If you do this 10000 times, then each of
  these steps creates a new copy of the list so far, which is a lot of
  work for the GC.  But this was not really necessary -- looking at
  your python code, you only add an item at the front of the list.

Just to measure the speed difference, I added this line to your code:

  print(len(primes(100000000)))

And then I did a direct translation of your code to PLT Scheme:

  #lang scheme/base
  (define (primes n)
    (define root  (expt n 0.5))
    (define len   (/ (- (+ n 1) 3) 2))
    (define sieve (make-vector len #t))
    (for ([i (in-range len)])
      (define x (+ (* i 2) 3))
      (unless (> x root)
        (when (vector-ref sieve i)
          (for ([j (in-range (+ (/ (- (* x x) x) 2) i) len x)])
            (vector-set! sieve j #f)))))
    (cons 2 (for/list ([x (in-range len)] #:when (vector-ref sieve x))
              (+ (* x 2) 3))))
  (length (primes 100000000))

This might be fitting on some cases, but it's mostly not an example of
typical Scheme code.  Anyway, the timings I'm getting on my machine
are

  python:   28.64s user 2.94s system 99% cpu 31.891 total
  mzscheme: 10.03s user 0.53s system 99% cpu 10.562 total

Thanks :-)  I had just gotten yeah far:

(define (primes.v1 n)
   (define len (quotient (- (+ n 1) 3) 2))
   (define sieve (make-vector len #t))
   (define root (sqrt n))
   sieve)

:-)

On Aug 2, 2009, at 3:18 PM, Eli Barzilay wrote:

Try to modify it, to use the same sqrt(n) observation the Python code does.

#lang scheme

; any-divisors-in-list? : number list-of-numbers  ->  boolean
;   If a number in the list divisors is a divisor of n,
;   then true is returned, otherwise false is returned
(define (any-divisors-in-list? n divisors)
  (cond [(null? divisors) #f]
        [(= (remainder n (car divisors)) 0) #t]
        [else (any-divisors-in-list? n (cdr divisors))]))

; primes : number -> list-of-number
;  returns a list of the primes below n
(define (primes n)
  (define numbers-from-0-to-n (build-list n  (λ (x) x)))
  (define numbers-from-2-to-n (cdr (cdr numbers-from-0-to-n)))
  (let loop ([primes '()]
             [non-primes '()]
             [candidates numbers-from-2-to-n])
    (if (null? candidates)
        primes
        (let ([n (car candidates)])
          (if (any-divisors-in-list? n non-primes)
              ; n had a divisor
              (loop primes (cons n non-primes) (cdr candidates))
              ; n was a prime
              (loop (cons n primes) non-primes (cdr candidates)))))))

(primes 20)

BTW - Did you take a look at HtDP?

Before we throw out all solutions, let me add a couple of more  
comments to my original post:

(4 expanded)

5. Since Scheme covers imperative as well as functional programming,  
you can do both -- as Jens and Eli showed in detail and, amazingly,  
you can do both in a reasonably elegant manner, close to what you  
would do in conventional languages. But see (*) below.

Question is what is your goal?
  -- functional programming per se (as a philosopher, I would have to  
question if it exists)
  -- Scheme programming in a functional way?
  -- Scheme programming in the 'best' possible way?
        -- best could mean 'fastest' (as you saw Eli's program is faster  
than yours)
        -- best could mean 'suitable for proving theorems automatically'
        -- and many more things

6. Scheme programming is one thing, PLT Scheme is something  
completely different.

In my mind, PLT Scheme relates to Scheme in the same way that Scheme  
relates to Lisp (its original implementation language) and Algol (one  
of its two influential idea-ancestors, the other one being Actors/
Smalltalk).

As such, PLT Scheme would accommodate an OO solution and a lazy  
functional solution (which I showed you in my message) in addition to  
the above.

Better still, as Eli demonstrated, PLT Scheme comes with the right  
kind of 'syntactic sugar' so that you can program imperatively as if  
you were in a plain imperative language like core Python or C. (*) So  
Eli's program isn't real Scheme at all. It is PLT Scheme, and it  
exploits the features that we added (so-called syntactic extensions,  
unavailable in most other languages) to make Scheme code look concise  
and elegant -- in all aspects.

So the last question is:
  -- perhaps you really want to learn to program in PLT Scheme so  
that you can see what
       elegant lazy functional programmers do,
       strict lazy programmers,
       OO programmers,
       logic programmers,
       and imperative programmers
without ever leaving the language.

I am not sure whether you knew what you were getting into but now you  
have at least the landscape laid out for you -- Matthias

  "a direct translation of your code to >>PLT<< Scheme"

([*] Including the philosophical question of whether purely functional
programming exists.)

You may have misinterpreted my email a bit.

If you learn to program well in PLT Scheme, you will learn MORE THAN  
if you just learn to program functionally in ANY OLD Scheme. Once  
again, PLT Scheme is to Scheme what Scheme is to LISP and Algol 60,  
its two acknowledged predecessor. Point blank:

  PLT Scheme is vastly more than Scheme.

Just in case this isn't clear, your primes example demonstrates this  
point more than anything else. For sheer elegance, you should build  
your solution as a two-module program:

  sieve.ss
  #lang lazy ;; the truly functional solution
  (provide take-n-primes)
  ... see old mail

  main.ss
  #lang scheme
  (require "sieve.ss")
  ... now use the lazy stream in regular strict FP ...

NO OTHER LANGUAGE (Scheme or other FP or scripting or whatever) can  
provide this kind of mixed service. BEST OF ALL, the entire thing is  
still shorter than your Python program.

-- Matthias

On Aug 6, 2009, at 4:52 PM, SiWi wrote: