Prolog辅导 | CS3mi3 Assignment 3 A nondeterministic language
这个Assignment是用prolog设计一个nondeterministic 语言
CS3mi3 Assignment 3
A nondeterministic language
Mark Armstrong, PhD Candidate, McMaster University
Wednesday November 20th, 2019
Due Wednesday, December 4th by end of day
You should routinely check the course homepage in case of updates to
this assignment; an announcement will be made if an update occurs, and
the content of updates will be documented here.
Updates
Nov 20 • Original version posted.
Instructions
This assignment asks you to define the semantics of a small nondeterminstic
programming language in Prolog.
Submit the following to your course GitLab repository in a folder named
a3 by the deadline.
1. The raw source code for each program, named as specified in the instructions for each program.
• Files which do not “type check” are an automatic failure.
2. A PDF document documenting your source code, and answering any
written questions. Relevant portions of code should be embedded in
the PDF. (Uninteresting portions may be omitted). This can be accomplished using Emacs and Org mode, or by using the listings package for LATEX.
1
A printed copy of your document (which matches the online version) must
also be submitted to the course staff by the end of the day following the due
date (preferably in lecture).
Tests will be provided on the course website and/or in your course GitLab
repository for the coding portions of the assignment, in the form of testing
scripts.
• The testing scripts will generally “import” your submission (the details
will vary by language) and the tests will thus place some requirements
on your implementation.
Usage instructions will be included with the testing scripts.
Note that passing the provided tests does not ensure that you will receive
any particular grade. That is, passing the tests is the bare minimum. It is
your responsibility to ensure that
1. your code works using the implementations of the languages discussed
on the course homepage under Software installation instructions, and
2. your code passes the provided tests.
A nondeterministic language, Nondet
For this assignment, we will reason about a new little language, which we
call Nondet.
Nondet includes only integer variables and constants, an assignment
statement, and composition statements. The unique feature of Nondet is
that it has two ways to compose programs, which we call sequence and
either.
A CFG for Nondet:
⟨stmt⟩ ∷= assign ( var , int )
| sequence ( ⟨stmt⟩ , ⟨stmt⟩ )
| either ( ⟨stmt⟩ , ⟨stmt⟩ )
Informal semantics of Nondet
The informal semantics of Nondet are:
• Executing assign(X,I) assigns the integer constant I to X.
• sequence(S1,S2) executes S1
, and then executes S2
.
• either(S1,S2) executes one of S1 or S2
, but not the other.
2
Task 1 – Inference rules [20 marks]
Create a set of inference rules giving the small-step semantics of Nondet.
Your rules should define a relation _⟶_ : Stmt × State → Stmt ×
State, where State is a functio from variables to integers. (We do not
include an environment in the semantics of this language).
Note that unlike our previous semantic descriptions, because Nondet is
non-deterministic, there should be instances where several rules apply to a
given statement.
Task 2 – Nondet in Prolog [20 marks]
In Prolog, define a ternary relation mightAssign to describe the semantics
of Nondet programs.
The meaning of mightAssign(S,X,I) is that, after executing the statement S, the variable X might be assigned value I.
In your rules, the statements should be of the forms
• assign(X,I),
• sequence(S1,S2), and
• either(S1,S2).
(You may change the variable names if you wish).
Place your code in a file named nondet.pl.
Task 3 – Adding one more command [Bonus: 10
marks]
In a separate file, named nondet_both.pl, repeat the definition of the semantics of Nondet, but add the following additional command.
both(S1,S2) evaluates both of S1 and S2
, but not in a defined order.
S1 may be evaluated first, or S2 may be evaluated first, or the two may be
evaluated concurrently (control flow may pass back and forth).
Testing is not provided for this part; use the unit tests for task 2 to
design your own unit tests for this part, and submit them along with your
code.
3
Testing task 2
These unit tests use the unit testing framework built in in SWI Prolog. See
the documentation.
For this assignment, no interface should be needed.
To run the tests, use the command
swipl -t “load_test_files([]), run_tests.” -s nondet.pl
in your a3 directory.
:- begin_tests(nondet).
:- include(nondet). % Your file.
% Note: the [nondet] option being passed to each call of test below
% suppresses warnings about choice points; it is not related to our nondet file.
% Assignment
test(assign_x_1, [nondet]) :- mightAssign(assign(x,1),x,1).
test(assign_y_10, [nondet]) :- mightAssign(assign(y,10),y,10).
test(x_unassigned, [nondet]) :-
\+ mightAssign(assign(y,10),x,0).
% \+ means this is NOT provable
% Sequence
test(assign_x_then_y, [nondet]) :-
S1 = assign(x,1),
S2 = assign(y,2),
S = sequence(S1,S2),
mightAssign(S,x,1),
mightAssign(S,y,2).
test(assign_x_twice, [nondet]) :-
S1 = assign(x,1),
S2 = assign(x,2),
S = sequence(S1,S2),
mightAssign(S,x,2).
% Either
test(assign_x_or_y, [nondet]) :-
S1 = assign(x,1),
S2 = assign(y,2),
4
S = either(S1,S2),
mightAssign(S,x,1),
mightAssign(S,y,2).
test(assign_x_twice, [nondet]) :-
S1 = assign(x,1),
S2 = assign(x,2),
S = either(S1,S2),
mightAssign(S,x,1),
mightAssign(S,x,2).
:- end_tests(nondet).
5