prolog代写: ECS140A-W18-08 February 27, 2018 ASSIGNMENT 6: Prolog

ECS140A-W18-08 February 27, 2018 ASSIGNMENT 6: Prolog

Due: March 8, 2018, 11:59 PM

Overview

The purpose of this assignment is for you to gain some experience designing and implementing Prolog pro- grams. This assignment explores only a few of the many interesting Prolog features.

This assignment is broken into several parts. The first few parts are fairly straightforward Prolog warmups. The remaining parts, which are more challenging, involve using Prolog’s backtracking to explore memory management schemes.

Coding Restriction N.B., do not use Prolog’s assert predicates (asserta, assertz, or retract) or global variables (the g_ predicates). Their use is unnecessary for this assignment and can lead to poor programming style. You will receive no credit for each part where you use them.

ECS140A-W18-08 February 27, 2018

Part 1: Simple Queries

You will be given some facts about US National Parks of the form: np(name,states,activities).

where name is an atom giving the national park’s name, states is a list indicating the states (as postal state abbreviations) in which the park is located, and activities is a list showing what activities the park offers. For example,

np(grandcanyon, [az,ut], [hiking, camping])
np(yosemite, [ca], [hiking, camping, rockclimbing]) np(everglades, [fl], [swimming,camping])

Write the following separate queries:

names of all national parks (np_names(N))
names of all national parks other than yosemite (np_names_not_yosemite(N))
list of activities available at yosemite (np_activities_yosemite(A))
list of states for yosemite (np_states_yosemite(S))
list of states for grandcanyon (np_states_grandcanyon(S))
list of states for national park with name N (np_states(N, S))
sorted list of activities at yosemite (np_sorted_activities_yosemite(SA)).
Use np_activities_yosemite(A) and Prolog’s sort. (See sort example on next page.)
names of parks that are within exactly one state (np_single_state(N))
names of parks that are within two or more states (np_multi_state(N))
ordered pairs (each as a list of 2) of names of 2 (different) parks that are within exactly one state that is the same (np_pair_names([N1, N2])) Use Prolog’s @< operator to compare state names (atoms).
names of parks that are within exactly two states and offer exactly two activities (np_2_state_2_activi- ties(N))
names of parks that are within exactly one or exactly two states; do this query two ways:
- by defining only 1 rule in your code that uses Prolog’s or operator “;” (np_12_states_1or(N))
- by defining only 2 rules in your code without using Prolog’s or operator “;” (np_12_states_2wo(N))
names of parks that provide exactly camping and hiking (in either order); do this query three ways:
- by defining only 1 rule in your code that uses Prolog’s or operator “;” (np_camping_hiking_1or(N))
- by defining only 2 rules in your code without using Prolog’s or operator “;” (np_camping_hiking_2wo(N))
- by using sort (np_camping_hiking_sort(N))

ECS140A-W18-08 February 27, 2018

When you are through testing your queries interactively, prepare them for use by the testing program via defin- ing predicates with the names shown above; all the predicates take one or two arguments as shown. As give- aways:

/* names of all national parks */ np_names(N) :-

np(N,_,_).

/* names of all national parks other than yosemite */ np_names_not_yosemite(N) :-

np(N,_,_),
N \= yosemite.

Use Prolog’s builtin sort predicate to sort lists, e.g.,

| ?- sort([1,3,2],Z). Z = [1,2,3]

| ?- sort([1,[3],[],[1,9,12],[3,1],2,[2,5]],Z). Z = [1,2,[],[1,9,12],[2,5],[3],[3,1]]

| ?- sort([b,2,[b,xx,5],a,1,c,[b,9]],Z). Z = [1,2,a,b,c,[b,9],[b,xx,5]]

Note how sort removes duplicates, how it orders lists (i.e., much like the usual alphabetic order), and how it uses Prolog’s standard ordering of numbers before atoms before lists.

Note that there are several ways to write the last two sets of queries—i.e., np_12_states_* and np_camp- ing_hiking_*—which can produce outputs in different orders and with or without duplicates. The test pro- gram generates all outputs and then uses sort to order the outputs and eliminate any duplicates. In debugging, you might want to test your query manually.

Write your queries to work with arbitrary facts; do not tailor them to the given facts.

ECS140A-W18-08 February 27, 2018 Part 2: Basic Lists (insert, butlast, naaa)

This part contains three predicates to give you experience using the basic list predicates that will be useful later in the main part of this assignment.

Write the predicate insert(L,E,Z). It returns in list Z all elements of L and element E in sorted order. For example,

| ?- insert([1,5,8],6,Z). Z = [1,5,6,8]

Assume list L’s elements are unique and E is not in list L. Coding hint (giveaway): use append and then sort.

Write the predicate butlast(L,Z). It returns in list Z all elements of L, except for the last element of L. (This predicate is similar to LISP’s builtin butlast function.) For example,

| ?- butlast([1,2,3],Z). Z = [1,2]

butlast fails if the given list is empty.

Write the predicate naaa(L,NAL,AL). Given a list L, it returns in list NAL all the non-atoms from L and in list AL all the atoms from L. naaa preserves order: elements in NAL and AL appear in the same order as they did in L. For example,

| ?- naaa([1,a,2,3,b,c,d,e,4],NAL,AL). NAL = [1,2,3,4]
AL = [a,b,c,d,e]

Use the builtin predicate atom. (Note that Prolog’s idea of an atom differs from LISP’s. In LISP, an atom is a number or a symbol; in Prolog an atom is only a symbol. Prolog also provides the builtin predicate atomic to test for either an atom or a number.)

ECS140A-W18-08 February 27, 2018 Part 3: Splitting Lists (splitlist, split3list)

Write the predicate splitlist(L, Left, Pivot, Right). Given a list L, it returns in list Left all the elements from L that appear before Pivot and in list Right all the elements from L that appear after Pivot. (Hence, Pivot itself appears in neither Left nor Right.) splitlist preserves order: elements in Left and Right appear in the same order as they did in L. For example,

| ?- splitlist([1,2,3,4,5,6],Left,3,Right). Left = [1,2]
Right = [4,5,6]

Pivot may appear anywhere in list L, including as the first or last element. Assume Pivot is unique in list L. If Pivot does not appear in L, then splitlist fails; hence, splitlist fails if list L is empty. Do not assume L is sorted.

Coding hint: use the accumulator list idea (from lecture) to build up a “Left so far” list as your code recurses looking for Pivot.

Write the predicate split3list(L, Owner, Left, Pivot, Right). It is similar to splitlist, but differs in that:

• list L’s elements are triples, e.g., [0,9,a]

• list L needs to be searched to find the triple whose third element is Owner, an input parameter to split3list that splitlist did not have. That triple will serve as the Pivot, which is now an output parameter of split3list.

For example,

| ?- split3list([[0,9,a],[12,15,b],[22,25,c],[33,5,d],[41,2,e]],c,Left,Pivot,Right). Left = [[0,9,a],[12,15,b]]
Pivot = [22,25,c]
Right = [[33,5,d],[41,2,e]]

Coding hint: the code for split3list is structurally very close to that of splitlist.

ECS140A-W18-08 February 27, 2018 Part 4: Permutations (perm, permsub)

Write the predicate perm(L, PermL). Given a list L, it returns in the list PermL a permutation of L. Through backtracking, perm will return subsequent permutations of L until there are no more. For example,

| ?- perm([1,2,3],Z). Z = [1,2,3] ? ;
Z = [1,3,2] ? ;
Z = [2,1,3] ? ;

Z = [2,3,1] ? ; Z = [3,1,2] ? ; Z = [3,2,1] ? ;

Your code must generate permutations in their “natural” order, as illustrated above.
Write perm using select (or the equivalent member/delete) described at the end of this part. N.B., see

Coding Restriction at the end of this part.

Write the predicate permsub(L, PermL). Like perm, permsub returns permutations of L. Unlike perm, though, permsub returns only those permutations of L in which the non-atoms of L appear in the same order as they did in L. (Hence, permsub permutes only a sublist of L.) For example,

| ?- permsub([a,1,b,2],Z). Z = [a,1,b,2] ? ;
Z = [a,1,2,b] ? ;
Z = [a,b,1,2] ? ;

Z = [1,a,b,2] ? ; Z = [1,a,2,b] ? ; Z = [1,b,a,2] ? ; Z = [1,b,2,a] ? ; Z = [1,2,a,b] ? ; Z = [1,2,b,a] ? ; Z = [b,a,1,2] ? ; Z = [b,1,a,2] ? ; Z = [b,1,2,a] ? ;

Your code must generate permutations in their “natural” order, as illustrated above.

Coding hint: There are several ways to approach this problem. The simplest is to generate a permutation of L (using perm) and then test whether it preserves the order of the non-atoms. As part of this last step, use naaa.

Coding Restriction for perm and permsub. N.B., your code
• must not use Prolog’s builtin permutation predicate;
• must not use the permutation predicate from “More Example Programs” chapter in the text; • must not use the append predicate.

You will receive no credit for this part if your code violates the above.

ECS140A-W18-08 February 27, 2018

Using select: Recall from class, Prolog’s select predicate. It takes a list as input and picks an element from the list and returns a new list from which the chosen element has been removed. Recall that if the list’s elements are unique (which you may assume for this assignment), select(E,L,R) is equivalent to mem- ber(E,L),delete(L,E,R).

| ?- select(E,[1,2,3],R). E=1
R = [2,3] ? ;

E=2
R = [1,3] ? ;

E=3
R = [1,2] ? ;

ECS140A-W18-08 February 27, 2018 Part 5: Memory Management Predicates (fit1stRequest, fitRelease)

The remaining parts deal with managing memory as an operating system might do, though greatly simplified of course. Here are the key data representations.

A request for memory is represented [owner, size]

The owner is an atom; it uniquely identifies the request. The size is a positive integer specifying the amount of memory needed.

A release of memory is represented as simply

owner
which specifies the owner on a previous request.

Requests and releases will appear in an RRList. Example: [ [a,3],[b,3],[c,3],b,c,[d,5] ]

This list has 4 requests and 2 releases. Assume that each owner appears at most twice in an RRList (in 1 request and in 1 release) and that a release from a particular owner appears after its request. Do not assume that there is a release for each request; e.g., in this example, there is no release for owner ‘a’.

Memory is represented by blocks. Each Block is a triple [address, size, owner]

The address is a non-negative integer specifying the starting address of the block of memory. The size is a positive integer specifying the size of the block. The owner is an atom indicating the block’s owner, as seen earlier for requests and releases.

How all of memory is presently allocated will appear in a MemList, which is a list of blocks sorted by block address. Example: The MemList

[ [0,3,z],[3,2,b],[5,4,z] ] represents the memory layout

012 34 5678

where the block’s owner appears in the box representing the block and the block addresses appear below the box representing the block (as noted above, the entire block is referenced by the first of those addresses). As seen, this list has 3 blocks. Assume that there are no gaps between blocks, so that, for example, the first block’s address plus the first block’s size matches the second block’s address. Furthermore, this list represents a total memory size of 9 blocks. The owner ‘z’ is used to indicate that the memory space is not presently allo- cated (or, equivalently, as being allocated to the operating system, which is known as ‘z’); the ‘z’ owner will never appear in a request or a release.

ECS140A-W18-08 February 27, 2018

Write the predicate
fit1stRequest([Owner, Size], MemList, NewMemList)

It takes as input a request and a MemList. If it can allocate memory from MemList for the request, it returns a new MemList; if not, it fails. For example,

| ?- fit1stRequest([b,3],[[0,2,a],[2,7,z]],M). M = [[0,2,a],[2,3,b],[5,4,z]]

Note how the free block is split: the first part is given to the request and the second part remains free. (Of course, if the size of a request matches exactly the size of the free block size, there will be no second part.)

fit1stRequest uses a “first fit” scheme: it uses the first free block (the one with the lowest address) that has suf- ficient memory to satisfy the request. For example,

| ?- fit1stRequest([d,2],[[0,2,a],[2,2,z],[4,2,b],[6,2,z],[8,2,c],[10,2,z]],M). M = [[0,2,a],[2,2,d],[4,2,b],[6,2,z],[8,2,c],[10,2,z]]

Note which of the several free blocks of sufficient size was allocated.
Coding hint: fit1stRequest is somewhat similar to the list splitting predicates (Part 3).

Write the predicate
fitRelease(Owner, MemList, NewMemList)

It takes as input a release and a MemList. It frees up the block associated with Owner and returns a new Mem- List; it always succeeds. For example,

| ?- fitRelease(a,[[0,2,a],[2,3,b],[5,4,z]],M). M = [[0,2,z],[2,3,b],[5,4,z]]

When possible, fitRelease combines (“coalesces”) the block with the adjacent block on its left if it is free or the adjacent block on its right if it is free, or both if both are free. Examples:

| ?- fitRelease(a,[[0,3,c],[3,3,z],[6,2,a],[8,1,b]],M). M = [[0,3,c],[3,5,z],[8,1,b]]

| ?- fitRelease(a,[[0,3,c],[3,3,z],[6,2,a],[8,1,z]],M). M = [[0,3,c],[3,6,z]]

Observe that such coalescing means that MemList will never contain two adjacent blocks owned by ‘z’. Coding hint: you might find split3list (Part 3), butlast (Part 2), and last (builtin) useful.

ECS140A-W18-08 February 27, 2018

Part 6: One More Memory Management Predicate (fitanyRequest)

Write the predicate
fitanyRequest([Owner, Size], MemList, NewMemList)

It is similar to fit1stRequest, but it will, through backtracking, allocate memory in any free block it can. Thus, fitanyRequest will help us see whether there are alternatives to what fit1stRequest does. Here’s the same example as the last fit1stRequest1 example:

| ?- fitanyRequest([d,2],[[0,2,a],[2,2,z],[4,2,b],[6,2,z],[8,2,c],[10,2,z]],M). M = [[0,2,a],[2,2,d],[4,2,b],[6,2,z],[8,2,c],[10,2,z]] ?;
M = [[0,2,a],[2,2,z],[4,2,b],[6,2,d],[8,2,c],[10,2,z]] ?;
M = [[0,2,a],[2,2,z],[4,2,b],[6,2,z],[8,2,c],[10,2,d]] ?;

Note how it returns answers in the order of the chosen free blocks in MemList.
Coding hint: you might find insert (Part 2) and select (builtin; see end of Part 2) useful.

Part 7: Putting the Memory Management Predicates Together (fit1st, fitany)

Write the predicate
fit1st(RRList, MemList, NewMemList)

It takes as input an RRList (Part 5) and a MemList (Part 5). It executes each request or release in the RRList, by invoking fit1stRequest or fitRelease. It returns a MemList showing the final memory configuration, if all requests succeeded. (Recall that all releases succeed.)

Write the predicate
fitany(RRList, MemList, NewMemList)

It is similar to fit1st, but invokes fitanyRequest instead of fit1stRequest.

ECS140A-W18-08 February 27, 2018

Part 8: Trying Harder on RRLists (fit1stTryHarder, fitanyTryHarder)

Write the predicate
fit1stTryHarder(RRList, MemList, NewRRList, NewMemList)

It takes as input an RRList and a MemList. It first checks whether fit1st on the given RRList and MemList succeeds; if so, then fit1stTryHarder just fails. On the other hand, if fit1st on the given RRList and MemList failed, then fit1stTryHarder will try to rearrange the RRList so that fit1st on the rearranged RRList does suc- ceed. fit1stTryHarder generates all possible rearranged lists. More specifically, the RRList is rearranged to see whether having releases in different places would make any difference. Example:

| ?- fit1stTryHarder([[a,2],[c,2],[d,2],c,[f,4],d],[[0,8,z]],RR,M). RR = [[a,2],[c,2],[d,2],c,d,[f,4]], M = [[0,2,a],[2,4,f],[6,2,z]] ? ; RR = [[a,2],[c,2],[d,2],d,c,[f,4]], M = [[0,2,a],[2,4,f],[6,2,z]] ? ; RR = [[a,2],[c,2],[d,2],d,[f,4],c], M = [[0,2,a],[2,2,z],[4,4,f]] ? ; RR = [[a,2],[c,2],c,[d,2],[f,4],d], M = [[0,2,a],[2,2,z],[4,4,f]] ? ; RR = [[a,2],[c,2],c,[d,2],d,[f,4]], M = [[0,2,a],[2,4,f],[6,2,z]] ? ;

Note that the NewRRList must still be legal in that an owner’s request must precede that owner’s release. Also note that for RRLists like

request A, request B, release B, release A fit1stTryHarder will succeed with a new RRList like

request A, release A, request B, release B

unless some individual request exceeds available memory size. This pattern is illustrated, partially, in the last RR list in the above example.

Write the predicate
fitanyTryHarder(RRList, MemList, NewRRList, NewMemList)

It is similar to fit1stTryHarder, but invokes fitany instead of fit1st.

Coding notes:

The simplest way is to generate a permutation of RRList (using permsub) and then test whether the NewRRList succeeds (using fit1st or fitany). In using this approach note that, due to how permsub works, the first NewRRList tried will be the same as the original RRLIst; it will fail. Your code may or may not eliminate that redundant test; either way is fine. Given that the lists in our tests are relatively short, the difference in efficiency is likely not significant.
Caution: permsub can return a NewRRList in which the release by a particular owner precedes that owner’s request, which Part 5 said would not happen. Moreover, Part 5 did not specify how fit1stRe- quest and fitanyRequest should behave on such bad input. It’s likely your code just fails (in the normal Prolog sense, i.e., not terminate your whole program). If so, then that’s fine and you don’t need to worry about it further.
However, another approach is to further filter out such a bad NewRRList before using fit1stRequest and fitanyRequest; this approach might be more efficient anyway, although the same comment about effi- ciency from the last bullet applies here too. Again, either approach is fine.

(Of course, if your program aborts due to an error in such a case, your ‘try harder’ code will need to fil- ter out the bad NewRRList or your code that handles requests will need to be changed.)

ECS140A-W18-08 February 27, 2018 Developing your Code

The posted test program and output contains additional specific examples that you should consult to verify your understanding of exactly what the predicates are supposed to do.

Design your solution in a top-down fashion, but develop, test, and debug in a bottom-up fashion. This problem has a fairly nice, natural subdivision into a number of smaller, simple problems. After sketching your design, figure out what the low level routines are and test them individually and exhaustively before using them at the next higher level. The breakdown given above already does so to some extent.

You’ll find it handy to retain earlier working versions of your code in case you need to back out some false starts on subsequent parts. (I.e., you may employ backtracking as part of your coding strategy!)

It is fine to use fairly naive approaches to solving the scheduling problem; efficiency is not our main concern.

ECS140A-W18-08 February 27, 2018

Notes

The command to use is gprolog.
CSIF runs gprolog 1.4.4, the most recent version of gprolog. Older versions of gprolog can give some odd warnings (“… alignment …”) on 64-bit systems. These warnings are likely harmless, but to be safe, you should probably update your gprolog version.
Read Sections 8.1 and 8.2 in the Prolog text for common mistakes to avoid. If your program doesn’t work as you think it should, go through the checklists before doing anything else. In particular, beware of typos, such as:
- space between predicate name and “(“.
- [A,X] instead of [A|X], or vice versa.
- uppercase instead of lowercase, or vice versa.
- period instead of comma, e.g., a(H) :- b(H). c(H). is quite different from a(H) :- b(H), c(H).
- use quotes within consult − e.g., “consult(’mult.pl’).” − if your filename contains anything but letters.
- Use parentheses to make sure you get the precedence you want, especially with expressions involving “;” (or) and “- >” (if-then). E.g., these two predicates are not equivalent:
  A=…, B=… → C=…; D=… . A=…, (B=… → C=…; D=…).
- use is for arithmetic ‘assignment’ and = for binding. (Make sure you understand this important differ- ence!) (Warning: in some cases on some platforms, some Prologs allows bindings like ‘X is [1]’ and then blows up later; I consider that a bug.)
- In some cases, a space needs to precede comments that follow some Prolog code. For example, if your code contains either of the following
  xxxx(yyyy,[zzzz])./*kjkjk*/
  
  xxxx(yyyy,[zzzz]).%kjkjk you’ll get errors like
  
  ** SYNTAX ERROR at byte=19573: atom follows expression xxxx ( yyyy , [ zzzz ] ) <HERE=> ./* kjkjk */
  
  The problem stems from Prolog’s use of “.” as the list construction functor. E.g., .(a,[b]) is the long way to write [a,b]; so you can think of “.” as being the Prolog equivalent of LISP’s cons.
- Use sort/2 (e.g., …,sort(Z,W),…) and not sort/1 (e.g., …,sort(Z),…). The latter does an in-place sort, i.e., it is destructive!
  Also, don’t forget to handle base cases (e.g., for empty lists) and to specify cases in the right order.
Do not define a predicate with the same name as a built-in one. In particular, do not (re)define append or
member. Use gprolog’s \+ for not. (Or, define and use your own mynot, from Prolog code handout.)

ECS140A-W18-08 February 27, 2018

You might get warnings about singleton variables, which are variables that appear only once. E.g., in first([H|T],H).
T is a singleton variable, but H is not. The warning can be eliminated by using a variable name for the sin- gleton that starts with an underscore, e.g.,

first([H|_T],H). or just

first([H|_],H).

The former might be more useful since you can use more meaningful names. You must eliminate all single- ton variables from your code, i.e., your code must not cause any such warnings. Be careful, though, that the variables you rename as indicated above are indeed singletons and not typos!
You may define additional helper predicates (as suggested earlier) that your main predicates use. Be sure, though, to name the main predicates as specified since the test program uses those names.
See the Prolog handout for examples of tracing.
Be aware of the meaning of using consult or reconsult. See the text and the Prolog handout and experiment on simple examples if necessary.
The test program will be provided. It exercises the predicates that you write; hence, there is no test data. Note that it generates all possibilities, and prints each out. Unlike interactive mode, each test predicate labels each predicate being tested, it doesn’t put a “;” at the end of each (as you would get by typing it). An individual test that fails outputs nothing. See the test file for additional information on how to run the tests interactively. The test predicate names begin with “test” or “all”; there are also some aliases that start with the letter ‘t’. Do not use these as the start of any of your predicate names.
We’re also providing a “batch mode” test script, which you should find very helpful.
“Correct” output will also be given. Your output must match exactly.
If you define any facts in the Prolog files that you’ll be consulting when running the test programs, those facts will be in the database in addition to those from the test program. So, if those facts are for one of the predicates being tested (which is likely), your results will appear to be incorrect.
When developing your program, you might find it easier to test your predicates first interactively before using the test program.
You can use Prolog’s debugging facilities or write, nl, and putstring predicates. See the text or the test file for examples of their use.

ECS140A-W18-08 February 27, 2018

Grading will be divided as follows. Percentage
10 Part 1: Simple Queries
10 Part 2: Basic Lists (insert, butlast, naaa)
15 Part 3: Splitting Lists (splitlist, split3list)
15 Part 4: Permutations (perm, permsub)
20 Part 5: Memory Management Predicates (fit1stRequest, fitRelease)
10 Part 6: One More Memory Management Predicate (fitanyRequest)
10 Part 7: Putting the Memory Management Predicates Together (fit1st, fitany) 10 Part 8: Trying Harder on RRLists (fit1stTryHarder, fitanyTryHarder)
A message giving exact details of what to turn in, where the provided source files are, etc. will be posted. You will be expected to turn in all working parts along with your attempt at the next part. So, be sure to save your work for each part. No credit will be given if the initial working parts are not turned in.

Related Posts