The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Getting started with Scheme: How can I improve my code for generating prime numbers?
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 10 messages

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Aug 1 2009, 1:35 pm
Date: Sat, 1 Aug 2009 10:35:22 -0700 (PDT)
Local: Sat, Aug 1 2009 1:35 pm
Subject: [plt-scheme] Getting started with Scheme: How can I improve my code for generating prime numbers?
Hello PLT Scheme community,
this is my first post here, so please excuse any mistakes.
I'm 16 years old and so far my programming experience has mainly been
in Python.
To learn about functional programming, I just started with Scheme.
For training I tried to convert some prime number generator code from
Python to Scheme.
It's using a sieve algorithm.
The problem is that my Scheme code is about 1000-10000 times slower
than my Python code.
I would greatly appreciate it if you could give me some hints on how
to improve my code.

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:

(define (primes n)
(letrec ((primes-go (lambda (n lst i x nroot) (if (> x nroot)
lst
(let ((temp-lst (lst-
remove lst 0 (+ (/ (- (* x x) x) 2) i) x)))
(primes-go n temp-
lst (+ i 1) (+ (* 2 i) 3) nroot)))))
(lst-remove (lambda (lst i goal step) (if (null? lst)
'()
(if (= goal i)
(cons #f
(lst-remove (cdr lst) (+ i 1) (+ goal step) step))
(cons (car
lst) (lst-remove (cdr lst) (+ i 1) goal step))))))
(list-bool (lambda (n i) (if (>= i n)
'()
(cons #t (list-bool n (+ i
2))))))
(filter (lambda (lst final i length) (if (>= i length)
final
(if (list-ref lst i)
(filter lst (append final
(list (+ (* 2 i) 3))) (+ i 1) length)
(filter lst final (+ i 1)
length))))))
(filter (primes-go n (list-bool (+ n 1) 3) 0 3 (sqrt n)) (list 2)
0 (length (list-bool (+ n 1) 3)))))
_________________________________________________
http://list.cs.brown.edu/mailman/listinfo/plt-scheme

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 2 2009, 3:06 pm
From: Matthias Felleisen <matth...@ccs.neu.edu>
Date: Sun, 2 Aug 2009 15:06:05 -0400
Local: Sun, Aug 2 2009 3:06 pm
Subject: Re: [plt-scheme] Getting started with Scheme: How can I improve my code for generating prime numbers?

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:

_________________________________________________
http://list.cs.brown.edu/mailman/listinfo/plt-scheme

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 2 2009, 3:18 pm
From: Eli Barzilay <e...@barzilay.org>
Date: Sun, 2 Aug 2009 15:18:58 -0400
Local: Sun, Aug 2 2009 3:18 pm
Subject: Re: [plt-scheme] Getting started with Scheme: How can I improve my code for generating prime numbers?
On Aug  1, SiWi wrote:

> Hello PLT Scheme community,
> this is my first post here, so please excuse any mistakes.  I'm 16
> years old and so far my programming experience has mainly been in
> Python.
> To learn about functional programming, I just started with Scheme.
> For training I tried to convert some prime number generator code
> from Python to Scheme.
> It's using a sieve algorithm.
> The problem is that my Scheme code is about 1000-10000 times slower
> than my Python code.
> I would greatly appreciate it if you could give me some hints on how
> to improve my code.

You have several problems in your code, which are a result of
translating the Python code into a more Scheme-ish version.

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

you wrote:

(append final (list (+ (* 2 i) 3)))

* "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

--
((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
http://barzilay.org/                   Maze is Life!
_________________________________________________
http://list.cs.brown.edu/mailman/listinfo/plt-scheme

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 2 2009, 3:21 pm
From: Matthias Felleisen <matth...@ccs.neu.edu>
Date: Sun, 2 Aug 2009 15:21:39 -0400
Local: Sun, Aug 2 2009 3:21 pm
Subject: Re: [plt-scheme] Getting started with Scheme: How can I improve my code for generating prime numbers?

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:

_________________________________________________
http://list.cs.brown.edu/mailman/listinfo/plt-scheme

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 2 2009, 3:35 pm
From: Jens Axel Søgaard <jensa...@soegaard.net>
Date: Sun, 2 Aug 2009 21:35:40 +0200
Local: Sun, Aug 2 2009 3:35 pm
Subject: Re: [plt-scheme] Getting started with Scheme: How can I improve my code for generating prime numbers?
Instead of translating the Python program as-is, try to rewrite it
little by little.
To get you started, here is a naive prime sieve in standard PLT Scheme.
(Use the module language).

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)
(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?

--
Jens Axel Søgaard
_________________________________________________
http://list.cs.brown.edu/mailman/listinfo/plt-scheme

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 2 2009, 5:37 pm
From: Matthias Felleisen <matth...@ccs.neu.edu>
Date: Sun, 2 Aug 2009 17:37:27 -0400
Local: Sun, Aug 2 2009 5:37 pm
Subject: Re: [plt-scheme] Getting started with Scheme: How can I improve my code for generating prime numbers?

Before we throw out all solutions, let me add a couple of more

(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

_________________________________________________
http://list.cs.brown.edu/mailman/listinfo/plt-scheme

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 2 2009, 6:02 pm
From: Eli Barzilay <e...@barzilay.org>
Date: Sun, 2 Aug 2009 18:02:59 -0400
Local: Sun, Aug 2 2009 6:02 pm
Subject: Re: [plt-scheme] Getting started with Scheme: How can I improve my code for generating prime numbers?
On Aug  2, Matthias Felleisen wrote:

> 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.

A big +1 to everything Matthias said[*], and in addition note that I
was careful to write:

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

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

--
((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
http://barzilay.org/                   Maze is Life!
_________________________________________________
http://list.cs.brown.edu/mailman/listinfo/plt-scheme

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 6 2009, 4:52 pm
Date: Thu, 6 Aug 2009 13:52:09 -0700 (PDT)
Local: Thurs, Aug 6 2009 4:52 pm
Subject: [plt-scheme] Re: Getting started with Scheme: How can I improve my code for generating prime numbers?
Thank you for your hints and tips first of all. As I've been on
holiday the last days, I had no internet access and couln't reply to

> 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

My goal is functional programming in genreral and Scheme programming
in the 'best' way. I'd also be interested in where exactly the
differences between 'best' Scheme programming( where 'best' would
rever to a mixture between speed and idiomatic Scheme programming) and
'best' functional programming style can be found.
On a sidenote, I want to use the primes code to try out a few project
euler problems with Scheme to get started with the language.
Therefore speed matters a bit, but of course it should not be the
world's most efficient prime numbers generator. :)

> 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.

My main goal is to learn something new, not only PLT-Schme, but also
Therefore I want to learn coding in Scheme in general, but I'm also
interested in strict lazy and logic programming.
I've done enough OO and imperative programming in other languages so
I'm not really interested in that at the moment, although I would like
_________________________________________________
http://list.cs.brown.edu/mailman/listinfo/plt-scheme

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 7 2009, 6:35 am
From: Phil Bewig <pbe...@gmail.com>
Date: Fri, 7 Aug 2009 05:35:05 -0500
Local: Fri, Aug 7 2009 6:35 am
Subject: Re: [plt-scheme] Re: Getting started with Scheme: How can I improve my code for generating prime numbers?

When you are ready for more, you can look at the exercises on my blog
http://programmingpraxis.com.  All the solutions are given in Scheme.  One
of the exercises is a Sieve of Eratosthenes.

_________________________________________________
http://list.cs.brown.edu/mailman/listinfo/plt-scheme

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 7 2009, 11:04 am
From: Matthias Felleisen <matth...@ccs.neu.edu>
Date: Fri, 7 Aug 2009 11:04:17 -0400
Local: Fri, Aug 7 2009 11:04 am
Subject: Re: [plt-scheme] Re: Getting started with Scheme: How can I improve my code for generating prime numbers?

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:

_________________________________________________