[Skip Navigation] [Remove Frame] [CS320] [Labs] [Text Version] primes.html Tue Dec 12 15:00:21 PST 2006
Labs: [01] [02] [03] [04] [05] [06] [07] [08] [09] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20]
Tue Dec 12 15:00:21 PST 2006

Contents

    Example of developing a more complex LISP function

     Sometimes you may want to work top-down, breaking down a complex function into smaller steps. Here is a worked example of top-down development.

    As an example consider the problem of listing the primes less than or equal to n you might decompose this into
    Net

    1. Make a list of all numbers from 1 to n
    2. Remove from this list all the non-prime numbers

    (End of Net)

    In LISP: 
     		(Define (Primes N) (RemoveComposite(ListNumbers 1 N)))
    You can input this first... but it won't work until you define the two subfunctions RemoveComposite and ListNumbers. Try this! 
     		(primes 10)

    Next step define one of the subfunctions: 

     		(define (ListNumbers I J)
     			(if (> I J) NIL
     			    (if (= I J) (list I)
     			        (cons I (ListNumbers (+ 1 I) J))
     		)	)   )
    Input this and test it like this 
     	ListNumbers
     	(ListNumbers 1 10)
     	(trace ListNumbers)
     	(ListNumbers 5 10)
     	(untrace ListNumbers)
    Does this fix 'primes'? Test 
     		(primes 10)

    Now we need the function RemoveComposite to remove composite numbers. Decompose this into two steps/functions: A function that tests for a composite number and one to to remove numbers that we don't want. Here is the filter to remove the non-primes:
    (removecomposite L):
    Net

    1. Removing composite numbers from a NULL list leaves a NIL.
    2. If the first item is composite, ignore it and remove composites from the rest.
    3. else leave this prime in front of a list with composites removed from rest

    (End of Net)

     		(define (RemoveComposite L)
     			(if (NULL L) NIL
     			    (if (composite (car L)) (RemoveComposite (cdr L))
     			        (cons (car L) (RemoveComposite (cdr L)))
     		)	)   )

    Again you can test this... and find that composite is not defined.

    How can you see if a number is composite? You need to find out if it is divisible by any of the numbers from 2 up to some number less than that number.

    The word any above is a clue to the need for a new function that doesn't just try numbers from 2 to n, but numbers from I to n for any I. Suppose this function is called (hasdivisor I N) then we can use it like this to define composite 

     		(define (composite n) (hasdivisor 2 N) )

    And if N has a divisor between I and N-1 inclusive then it is either I itself or it is a divisor between I+1 and N-1 inclusive. Further if the square of I is greater than N then we know that there can be NO divisors... 

     		(define (hasdivisor I N)
     			(if (> (* I I) N)  NIL
     			    (if (divides I N) T
     				(hasdivisor (+ 1 I) N)
     		)	)   )
    Note. perhaps we don't have to do every integer to find a divisor, but I leave this improvement until some one complains about the speed. Again if you test this you may find that divides is not defined... This is a standard hack: divide and multiply and check for lost remainders: 
     		(define (divides I N) (= (* I (/ N I)) N))
    Again add this definition and test primes.

    Note.... If you actually develop code like this, you can easily lose track of what you have defined and what is needed and so on. It is best to use an editor to develop the code in a file name.lsp and use lisp name.lsp to test it as it develops.

    Note... You might decompose this problem in a different way and still get a working program. It may be faster, smaller, smarter, longer, shorter, and etc... This decomposition was created solely to demonstrate the decompose/compose for LISP.

    Getting and Loading Existing Programs/Functions

    Note.... I made three mistakes when I did the original code, and fixed them above... the complete code is in [ primes.lsp ] Download/save this file (as ASCII in file primes.lsp) and then run 
     		xlisp primes.lsp
    And you will load a LISP system with added functions for handling prime numbers...

End