Previous Table of Contents Next


6.5.2. Eratosthenes’ Sieve

all_primes_less_than2, in this example, instantiates its second argument to a list containing all primes less than its first argument. It uses Eratosthenes’ sieve method to do so:

   all_primes_less_than(N, List) :-
    N1 is N-1,
    all_numbers_between(2, N1, Initial_list),
    sieve(Initial_list, List).

   % all_numbers_between(M, N, List): List is all numbers between
   % M and N, inclusive.
   all_numbers_between(M, N, []) :-
    M > N,
    !.
   all_numbers_between(M, N, [M|Rest]) :-
    M1 is M+1,
    all_numbers_between(M1, N, Rest).

   % sieve(Numbers, Primes): The result of performing an
   % Eratosthenes’ sieve sifting operation on Numbers is Primes.
   sieve([], []).
   sieve([Prime|Rest], [Prime|Primes]) :-
    delete_all_multiples_of(Rest, Prime, Next),
    sieve(Next, Primes).

   % Delete from (sorted) List all multiples of M, giving Result.
   delete_all_multiples_of(List, M, Result) :-
    delete_all_multiples_starting_with(List, M, M, Result).

   % Delete from (sorted) List all multiples of M starting with X,
   % giving Result.
   delete_all_multiples_starting_with([], M, X, []).
   delete_all_multiples_starting_with([X|Rest], M, X, Ys) :-
    !,
    XpM is X+M,
    delete_all_multiples_starting_with(Rest, M, XpM, Ys).
   delete_all_multiples_starting_with([Z|Rest], M, X, [Z|Ys]) :-
    Z > X,
    !,
    XpM is X+M,
    delete_all_multiples_starting_with(Rest, M, XpM, Ys).
   delete_all_multiples_starting_with([Z|Rest], M, X, [Z|Ys]) :-
    delete_all_multiples_starting_with(Rest, M, X, Ys).

6.5.3. A C Leak Checker

The following program illustrates term I/O and the use of Prolog for a task that is a bit awkward when done in simple pattern-matching languages. It helps in detecting memory leaks in C programs.

To use the leak checker on a particular C program, replace all calls to malloc and free in your C code with calls to new functions (say report_malloc and report_free), which call the original functions and also report information about the calls. At initialization, your C program should open a special log file; report_malloc should print a line of the form

   malloc(Pointer, Description).

to the log file after its call to malloc, and report_free should print a line of the form

   free(Pointer).

after its call to free. Here, Pointer is an integer representing the address allocated, and Description is a double-quoted string describing the block being allocated; for instance,

   malloc(4372, “B-tree node”).
   malloc(4400, “Parse tree leaf”).
   free(4372).
   free(4400).

After a run of your program, call the leakcheck predicate on the log file. leakcheck reports on any pointers allocated but not freed and also on any memory that may be allocated twice or freed without being allocated:

Listing 6.4. A C leak checker.

   % leakcheck(Filename):  top-level predicate.  Takes filename
   % (e.g. single-quoted constant) as argument.
   leakcheck(Filename) :-
    see(Filename),
    read_process([]),
    seen.

   % read_process(Allocated):  given the pointers known to be
   % Allocated so far, read and process the rest of the reports in
   % the log file.
   read_process(Allocated) :-
    read(Report),
    process(Report, Allocated).

   % process(Report, Allocated):  process Report and the rest
   % of the reports in the file, given the pointers known to be
   % Allocated so far.
   process(end_of_file, []) :-
    !,
    nl,
    write(‘No leaks detected.’), nl.
   process(end_of_file, Allocated) :-
    nl,
    write(‘Pointers allocated but not freed:’), nl,
    report_allocated(Allocated).
   process(malloc(Pointer,_), Allocated) :-
    member(Allocated, malloc(Pointer,_)),
    !,
    write(‘* Memory allocated twice at address ‘),
    write(Pointer), write(‘.’), nl,
    read_process(Allocated).
   process(malloc(Pointer,Desc), Allocated) :-
    read_process([malloc(Pointer,Desc)|Allocated]).
   process(free(Pointer), Allocated) :-
    delete(Allocated, malloc(Pointer,_), Rest_allocated),
    !,
    read_process(Rest_allocated).
   process(free(Pointer), Allocated) :-
    write(‘* Attempt to free memory not allocated at address    ‘),
    write(Pointer), write(‘.’), nl,
    read_process(Allocated).

   report_allocated([]).
   report_allocated([malloc(Pointer,Desc)|Reports]) :-
     write(‘  Address ‘),
     write(Pointer),
     write(‘: ‘),
     writestring(Desc),
     nl,
     report_allocated(Reports).

   % Standard predicates.

   member([X|_], X).
   member([_|Xs], Y) :-
    member(Xs, Y).

   delete([X|Xs], X, Xs) :-
    !.
   delete([X|Xs], Y, [X|Zs]) :-
     delete(Xs, Y, Zs).

   writestring([]).
   writestring([C|Cs]) :-
     put(C),
     writestring(Cs).

6.5.4. The Game of Life

This program implements John Horton Conway’s Game of Life, as described in Gardner’s work (1983). The implementation incorporates suggestions by William Clocksin, for which I am very grateful. Note the use of an operator declaration and multi-arity predicates and some exploitation of first-argument indexing to achieve efficiency.

The life “game board” is represented as the list of cells that are alive. Each cell is represented by the notation R::C, where R is the row and C is the column of the cell. The live cells are sorted into reading order—that is, left to right and top to bottom—for most of the processing.

To play the game, call life(Num_R, Num_C, Live_Cells, Some_future_gen), where Num_R and Num_C are the number of rows and columns on the desired board, Live_Cells is a list of live R::C cells, and Some_future_gen is an uninstantiated variable. Some_future_gen is instantiated first to the original list of live cells; keep entering the semicolon on the solutions prompt to get succeeding generations. At each solution, the board is printed out.


Previous Table of Contents Next