1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
-- FILE: /home/diacon/LANG/Cafe/prog/sieve.mod
-- CONTENTS: equational program for computing prime numbers by
-- the Eratostene sieve algorithm featuring
-- evaluation strategies and computation modulo axioms (A)
-- AUTHOR: Razvan Diaconescu
-- DIFFICULTY: ***
set tram path brute
mod! LAZYLIST (X :: TRIV ) {
[ Elt < List ]
op nil : -> List
op __ : List List -> List {assoc idr: nil strat: (0)}
}
mod* INFLIST {
protecting(LAZYLIST(INT))
[ List < InfList ]
op __ : List InfList -> InfList {strat: (0)}
op ints-from_ : Int -> InfList
op show_upto_ : InfList Int -> List
op force : List InfList -> InfList {strat: (1 2 0)}
vars E I : Int
var L : List
var S : InfList
eq force(L,S) = L S .
eq show nil upto I = nil .
eq show E S upto I = if I == 0 then nil
else force(E,show S upto (I - 1)) fi .
eq ints-from I = I (ints-from (I + 1)) .
}
mod* SIEVE {
protecting(INFLIST)
op sieve_ : List -> List
op sieve_ : InfList -> InfList
op primes : -> InfList
op filter_with_ : List Int -> List
op filter_with_ : InfList Int -> InfList
vars E I P : Int
var S : InfList
eq filter nil with P = nil .
eq filter I S with P = if (I rem P) == 0 then filter S with P
else I (filter S with P) fi .
eq sieve nil = nil .
eq sieve (I S) = I (sieve (filter S with I)) .
eq primes = sieve (ints-from 2) .
}
-- tram red in SIEVE : show primes upto 200 .
red in SIEVE : show primes upto 100 .
--
eof
--
$Id: sieve.mod,v 1.2 2010-06-17 08:23:18 sawada Exp $
|
