COMP24412 Academic Session: 2021-22
Lab 1: Prolog
Assessed exercises
Joe and is via git for this lab – see the section at the end of this document about submission. You should use your comp24412 repository (branch lab1) as a starting point. Please let me know if running git checkout lab1 doesn’t work. You should see a file called database.pl.
Copyright By PowCoder代写 加微信 powcoder
Learning Objectives
At the end of this lab you should be able to:
1. Use the Prolog interactive mode to load and query Prolog programs 2. Model simple constraint solving problems in Prolog
3. Define recursive relations in Prolog
Additionally, if you complete the formative exercises you should be able to: 5. Explain issues surrounding termination in Prolog
6. Use an accumulator approach to detect cycles in reasoning
Part 0: Getting Started
As noted above, you don’t get any marks for doing things in Part 0 but doing some of it will probably help with your Prolog in general. The important thing is that you think about what you’re doing and what you’ve learnt – don’t just go through the exercises completing them and skipping the thinking parts! There are solutions to all of the exercises in Part 0 at the end but we strongly suggest you give things a go before taking a look! (The last of these warmup exercises were the assessed exercises last year!)
Running Prolog (read this)
Open up a terminal and run swipl. You have just started the SWI-Prolog interactive mode, it should look a bit like this.
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 5.7.11)
Copyright (c) 1990-2009 University of Amsterdam.
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.
For help, use ?- help(Topic). or ?- apropos(Word).
The ?- is the prompt where we can type things. To get out of interactive mode you should type halt. (the . is necessary).
The expected usage is that your Prolog program (knowledge base) is stored in a file and you load this into the interactive mode and query it. For the warmup exercises we suggest you create a file warmup.pl (open it in gedit or similar) and run swipl in the same directory. Alter- natively, we can add queries directly to a program and run this from the command line using the pl command but we assume that you are using the interactive mode.
Warning. Not all Prolog implementations are the same. We are using SWI-Prolog in this course because it is what is on the teaching machines. They also have if you prefer to use that.
To load your warmup.pl file into interactive mode type 1 ?- [warmup].
The true response tells you that the file was loaded correctly. You can now type queries directly in the interactive mode. Add the line loves(mouse,cheese) and loves(monkey,banana) to warmup.pl and run the following query
2 ?- loves(X,Y).
X = mouse,
Y = cheese
(You probably need to reload the file). Recall that this returns an answer substitution (assignment to variables). Type ; to get more answers or . to stop searching. In this example what happens to the answers you get if you swap the two lines you have in warmup.pl?
If you change warmup.pl you can reload it into interactive mode by typing [warmup] again. You don’t need to stop and restart interactive mode.
The rest of this document contains the assessed exercise. Formative exercises in more of a tutorial style continue in the other document provided.
Part 1: Electrical Interference
You have joined a team working on the space program of a small country. The team is working hard trying to design a probe to send to a distant planet. The electrical engineering department is working on a list of components of the probe. For each pair of components, they have done tests to see whether the components can be put close to each other without interfering with each other and breaking. They have summarised their results so far in the following Prolog database (there is a copy of this in database.pl in the lab1 branch of your git repo.).
component(antenna).
component(transponder).
component(radar).
component(spectrometer).
component(imu).
component(camera).
component(cpu).
component(ram).
safe_with(radar,cpu).
safe_with(cpu,radar).
safe_with(radar,imu).
safe_with(imu,radar).
safe_with(imu,camera).
safe_with(camera,imu).
safe_with(imu,cpu).
safe_with(cpu,imu).
safe_with(imu,ram).
safe_with(ram,imu).
safe_with(ram,cpu).
safe_with(cpu,ram).
safe_with(ram,camera).
safe_with(camera,ram).
safe_with(camera,transponder).
safe_with(transponder,camera).
safe_with(camera,cpu).
safe_with(cpu,camera).
safe_with(cpu,spectrometer).
safe_with(spectrometer,cpu).
safe_with(cpu,antenna).
safe_with(antenna,cpu).
safe_with(antenna,spectrometer).
safe_with(spectrometer,antenna).
safe_with(antenna,transponder).
safe_with(transponder,antenna).
safe_with(transponder,spectrometer).
safe_with(spectrometer,transponder).
Your task is to write software in Prolog to help the designers of the probe check that their designs will work, in that they only place components close together if the engineers have shown those com- ponents don’t interfere. You should create a file electrical.pl to work in (make sure it is added to the lab1 branch of your repo!). Note that to gain full marks you must provide an explanation of what you have done (see mark scheme at the end).
Exercise 1
To get started, write a predicate safe_list/1 (i.e. a predicate with functor name safe_list and taking 1 argument) which takes a list of components and which succeeds if and only if every component in the list is safe for use with every other component. For example safe_list([cpu,imu,radar]) should succeed, but safe_list([ram,cpu,radar]) should fail. You may define extra predicates if you wish (this is true for all exercises in this lab).
Now, the engineers don’t just want to study lists of components, they also want to analyse abstract designs for the probe. A design is a list where each element is either of the form part(C) for some component C, or else of the form shield(L), where L is a design and the first element of L is of the form part(c). For example
[part(imu), shield([
part(cpu),shield([part(cpu)])
is a design, but
[part(imu), shield([
shield([part(cpu)]),shield([part(cpu)])
is not, because all the elements in the argument of the outermost shield are themselves of the form shield(X) – the first one is not of the form part(X) as required.
You can assume that you will be given a properly formatted design. However, you may find it in- structive to write a predicate to check whether a design is properly formatted (no marks for this).
The meaning of sheild(L) is that the elements of L have been electrically shielded from the outside world. That means that we can check whether a design is safe by checking whether all the parts which are not inside shields are safe when used with each other, then recursively checking whether the contents of each shield are a safe design. For example, the design
[part(radar), part(imu), shield([
part(antenna),part(transponder)])
is safe, because the radar and imu are safe together, and the antenna and transponder are safe together. But
[part(radar), part(camera), shield([
part(antenna),part(transponder)])
is not safe because it puts the radar and camera together without surrounding one of them with shielding, while
[part(radar), part(imu), shield([
part(antenna),part(camera)])
is not safe because the camera and antenna are not safe together.
Exercise 2
Write a predicate safe_design/1 which, when given a design as input, succeeds if and only if the design is safe in the above sense. Note it is unlikely that you will be able to use the predicate safe_list/1 from Exercise 1 directly, however the structure of your answer to this exercise is likely to be similar. It is likely that you will need to define auxiliary predicates. You do not need to worry about how your predicate behaves if the argument is not a design according to the definition above. If you are struggling with this part, you might find the next one easier.
Since the finished probe is supposed to be carried into space by a rocket, it is important for it to be as light as possible. The engineers are trying to use as little shielding as possible. As a first approximation, they want the software to count the number of times shield is used in a design.
Exercise 3
Write a predicate count_shields/2 which succeeds if and only if its second argument is the number of times shield occurs in its first argument. It must be possible to use your predicate in the query count_shields(D,N) where D is a design and N is a variable, so that Prolog returns the number. For example
count_shields([part(imu),shield([
part(ram),shield([part(radar)])
shield([part(cpu)])
should return N = 3. You do not need to worry about the behaviour of your predicate if the first
argument is not a design according to the first definition.
Finally, the engineers want to check that a design does not have any components missing. The idea is that they will provide a design and a list of components, and the software should be able to tell if each component in the list is used exactly once somewhere in the design.
Exercise 4
Write a predicate design_uses/2 which accepts a design and a non-empty list of components as arguments, and succeeds if and only if the first argument is a design, and the components used in the design are exactly those listed in the list. Each element in the list must be used exactly once in the design (if a component is repeated, it should be occur as many times in the design as there are repetitions of it in the list). Note that the elements may appear in a different order in the design compared to the list. Finally, the predicate should fail if the first argument is not a design as defined above (we do count the empty list as a design).
Before attempting to write design_uses/2, you should first write a predicate split_list/3 with three arguments, which succeeds if the first argument can be split up into the other two arguments. For example, the query split_list([1,2,3],X,Y) should return the results
X = [1, 2, 3],
X = [1, 2],
X = [1, 3],
Y = [2, 3]
X = [2, 3],
Y = [1, 3]
Y = [1, 2]
Y = [1, 2, 3]
It may be helpful to think about going through the list element by element, and allocating each el- ement either to the second or third argument, before recursively allocating the rest. You may then like to contemplate the results of the query split_list([1,2,3],[H],R).
Make sure your test your solution(s). You should ensure that your solution works where components are repeated in the component list, for example, design_uses(D,[imu,imu]). More testing data may be provided via Blackboard. Please keep an eye out for announcements.
Exercise 5
Once you have finished the exercises above, you should try running the query design_uses(D,[imu,cpu]). Ideally this will list all possible designs using one imu and one cpu. This will depend on ensuring your previous definitions are not unnecessarily restrictive. If this works, try running the query
design_uses(X,[transponder,spectrometer,antenna,ram,cpu,imu,radar,camera]),
safe_design(X),
count_shields(X,2)
although you might prefer to see if you can find a solution manually first.
It might be that your Prolog code goes into an infinite loop! If you’re really interested in Prolog, ensure that your implementation of design_uses\2 does not go into an infinite loop for the input given. Use comments to describe clearly when your implementation runs forever, and discuss whether it would be efficient to run on large inputs, with clear reasoning for your claims.
Submission and
Submission is via git. You must work on the lab1 branch and tag your submission as lab1 solution. The provided submit.sh script does this for you. Note that you must push your tagged commit to Gitlab before the deadline (it is not good enough just to make the commit locally).
Your work will be marked and returned to you with comments. We may automate some tests on your code so please do not edit the general layout (e.g. headings) of the provided file and make sure you use the specified predicate names.
The marking scheme (10 marks total) is as follows.
(1 mark) for correct safe_list/1
(2 marks) for correct safe_design/1, 1 mark if missing a case
(2 marks) for correct count_shields/2, 1 mark if missing a case
(4 marks) with 2 marks for split_list/2 and 2 marks for the final design_uses/2
(1 mark) for an implementation of design_uses/2 which does not go into an infinite loop together with clear and correct comments answering the questions asked at the end of Exercise 5.
You must provide explanations of the work you have done as comments in the submitted files. These should go beyond standard comments in programs and should not simply reiterate the rules in English e.g. aim to explain the idea not the code. In all cases, up to half of the marks may be deducted if the explanation of the code is not sufficient. You should aim to write in full sentences. You may include brief examples.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com