In studying numbers, one comes across notions like `pythagorean triples' (integers, such that x squared plus y squared equals z squared) as well as the idea that any number can be expressed as the sum of four squares. To investigate these notions, it would be useful to have a predicate that can produce all the lists of k integers, for a given k. This is your task. In this discussion, both integers and numbers refer to non-negative integers (0, 1, 2, 3, and so forth).

Details:

• A given part can be found in Hmwk8.Given.pp It is also available on gaul in the directory: /gaul/s1/usr/faculty/webber/CS342/Homework8 .
• The predicate that you need to define is list_of_k_integers(K, List). This predicate returns all the possible lists of k integers, one list at a time. In order to be sure that it eventually reaches all the possible lists, it first returns that lists of k integers where the integers sum to 0, then the lists that sum to 1, then the lists that sum to 2, and so on.
• Again, cut is not to be used.

Handin Requirements

• What to hand in
  • You will need to handin your source file Hmwk8.pp (the other source files you may not change and you may not use any additional source files, so there is no need to hand in any other source files).
  • On the hardcopy version only, it is required that two test runs be shown. This involves printing the results of using script to capture the results of the following output sequence:

       cat Hmwk8.pp
       cat Hmwk8.Given.pp
       pprolog Hmwk8.pp Hmwk8.Given.pp 
       # :- sum_of_four_squares(159, W, X, Y, Z).  /* stop after first response */
       # :- pythagorean_triples(X, Y, Z).  /* stop after Z = 26 is reached */
       # :- list_of_k_integers(5, X).  /* stop after number 3 appears in list */
    

    By stop in the above instructions, I mean type a period.
  • It is perfectly fine to use your home printers as long as they are readable.
  • The hardcopy version must be in an 8.5x11 envelope if it is being handed in in the locker. If it is being handed in in class, it is ok if it is just stabled together (2 stables) or in a report folder (clasped). Loose pages or pages held together only be a paperclip are too easy to get mixed up together. Envelops that are not 8.5x11 make the pile of assignments difficult to sort through and should not be used. Your name should appear clearly on the outside cover of whatever you are handing in, as well as on each page.
  • For online handin, use CS342HandinFromGaul as was done for Homework 1.
• When to hand it in: the process is the same as for the second homework.

Reference:

Nothing new in terms of Prolog primitives.

Sample Run:

brown[73]: pprolog Hmwk8.Given.pp         Hmwk8.pp
Welcome to picoProlog
Reading Hmwk8.Given.pp
Reading Hmwk8.pp

# :- pythagorean_triples(X, Y, Z).

X = 3
Y = 4
Z = 5 ? 

X = 6
Y = 8
Z = 10 ? 

X = 5
Y = 12
Z = 13 ? .

yes

# :- sum_of_four_squares(99, W, X, Y, Z).

W = 9
X = 4
Y = 1
Z = 1 ? .

yes

# :- list_of_k_integers(3, X).

X = 0:0:0:nil ? 

X = 1:0:0:nil ? 

X = 0:1:0:nil ? 

X = 0:0:1:nil ? 

X = 2:0:0:nil ? 

X = 1:1:0:nil ? 

X = 1:0:1:nil ? 

X = 0:2:0:nil ? 

X = 0:1:1:nil ? 

X = 0:0:2:nil ? 

X = 3:0:0:nil ? 

X = 2:1:0:nil ? 

X = 2:0:1:nil ? 

X = 1:2:0:nil ? 

X = 1:1:1:nil ? 

X = 1:0:2:nil ? 

X = 0:3:0:nil ? 

X = 0:2:1:nil ? 

X = 0:1:2:nil ? 

X = 0:0:3:nil ? 

X = 4:0:0:nil ? 

X = 3:1:0:nil ? 

X = 3:0:1:nil ? .

yes

# :- ^D

Hints:

• Before comments, this assignment took me 29 lines of PicoProlog, consisting of 8 clauses defining four predicates.
• It was useful to have a predicate that would return once for each integer less than or equal to some bound, i.e.,

  brown[67]: pprolog *.pp
  Welcome to picoProlog
  Reading Hmwk8.Given.pp
  Reading Hmwk8.pp
  
  # :- an_integer_less_than_or_equal_to(5, X).
  
  X = 5 ? 
  
  X = 4 ? 
  
  X = 3 ? 
  
  X = 2 ? 
  
  X = 1 ? 
  
  X = 0 ? 
  
  no
  
  # :- ^D
  

• It was also useful to have a predicate that would produce all the lists of size k that sum to S, i.e.,

  brown[68]: pprolog *.pp
  Welcome to picoProlog
  Reading Hmwk8.Given.pp
  Reading Hmwk8.pp
  
  # :- list_of_k_integers_that_sum_to_S(2, 5, X).
  
  X = 5:0:nil ? 
  
  X = 4:1:nil ? 
  
  X = 3:2:nil ? 
  
  X = 2:3:nil ? 
  
  X = 1:4:nil ? 
  
  X = 0:5:nil ? 
  
  no
  
  # :- ^D
  

• Since this homework focusses on returning infinite lists, it never runs to completion. When you have seen enough responses, typing a plain period to the question mark prompt tells the system to stop looking for alternatives. In the event that your program goes off into a infinite loop returning nothing, a control-C under Unix will break the execution and exit you from prolog. This should not happen during the recording of the test runs, but will probably happen a few times during debugging.