Part 2: Microprocessor Constraint Language (50%)
Despite the recent silicon shortage in its industry, microprocessor manufacturing is one of the most key sectors of business in
the modern age. For this problem, you are to implement a natural language processing program that will read in definitions
of processors and constraints on the processor attributes, which are core count, area, and cost. Once several definitions are
specified and all three attributes are constrained, your program should run a constraint computation to calculate how many of
each processor should be placed on a common chip, such that the constraints are satisfied, and return these counts to be
printed.
You can assume for the purposes of this assignment that the maximum count of any processor type arranged on a common
chip is 16. Hence, results for any processor will range in values from 0 to 16 in integer steps. You can also assume that any
group of sentences input into your program will contain at least one definition and at least one constraint for each of the
three constrained values. Hence, do not worry about default values or error handling if you do not get enough information.
Processor definitions take on the following form:
Definition Sentence Blueprint
Processor type [ID] has [C] cores, uses [A] square centimeters, and costs [D] dollars.
• ID: a, b, c, . . . , x, y, z
• C: 1, 2, 3, . . .
• A: 1, 2, 3, . . .
• D: 1, 2, 3, . . .
Constraint Sentence Blueprint
Attribute constraints take on the following form:
[Attribute] [Imperative] be [[Comparison] [Value] | [Interval] [Range]].
• Attribute: (the | ) (core count | area | cost)
– Note that the empty space after the bar in the first parentheses is the empty string, meaning the word “the” is
optional.
• Imperative: must | is to
• Comparison: equal to | less than | greater than
• Value: 1, 2, 3, . . .
• Interval: in the (interval | range) of
• Range: [Value] to [Value]
– Note that intervals are assumed to be closed, hence “12 to 14” includes the values 12, 13, and 14, for example.
What Is To Be Done
This program should run from a main file, either part2.pl or part2.oz depending on your chosen language. As provided,
both main files only read in sentences from stdin that are either definitions or constraints, and print out a list tokens for
each sentence (which are produced by read_line). You should edit the main file to do the following:
1. Use a Natural Language Processing grammar, such as a Definitie Clause Grammar, to be able to take the lists of
tokens produced from read_line and bind the key information (ex. ID, C (core count), Attribute, Constraint, etc.) to
variables
2. store the variables with key information (noted above) so they can be used in a constraint calculation.
3. perform a constraint calculation based on the statements read in once reading is complete
4. output satisfactory results of the constraint computation to stdout (see the example below for sample printout)
3
Example Definitions, Constraints, and Results
Notice: In both languages, all atoms are made lowercase in the tokenization step (In Prolog: read_line, In Oz: Helper.tokenize)
before they reach any of processing you do with your NLP grammer, so do not worry about dealing with upper case letters
that are present in the spec files.
procSpec1.txt
Processor type a has 16 cores, uses 4 square centimeters, and costs 1000 dollars.
Processor type b has 8 cores, uses 3 square centimeters, and costs 100 dollars.
Processor type c has 4 cores, uses 2 square centimeters, and costs 10 dollars.
Processor type d has 2 cores, uses 1 square centimeters, and costs 1 dollars.
The core count must be greater than 49.
Area must be less than 17.
The cost is to be less than 2400.
(Note the extra newline at the end of the file shown above; This is good practice to make it easier to read the last line.)
Results:
a = 2, b = 1, c = 0, d = 5;
a = 2, b = 1, c = 1, d = 3;
a = 2, b = 1, c = 2, d = 1;
a = 2, b = 2, c = 0, d = 1;
a = 2, b = 2, c = 0, d = 2;
a = 2, b = 2, c = 1, d = 0;
procSpec2.txt
Core count is to be in the interval of 48 to 52.
The cost must be greater than 2149.
Processor type d has 2 cores, uses 1 square centimeters, and costs 1 dollars.
Processor type c has 4 cores, uses 2 square centimeters, and costs 10 dollars.
Processor type b has 8 cores, uses 3 square centimeters, and costs 100 dollars.
Processor type a has 16 cores, uses 4 square centimeters, and costs 1000 dollars.
The area must be in the range of 14 to 18.
(Note that the definition sentences occur in between the constraint sentences, but this does not affect the output. Also note
that the order of the definition sentences being reversed causes the output below to be reversed, printing d to a instead of a
to d on each line.)
Results
d = 0, c = 0, b = 2, a = 2;
d = 0, c = 1, b = 0, a = 3;
d = 0, c = 1, b = 2, a = 2;
d = 1, c = 0, b = 2, a = 2;
d = 2, c = 0, b = 0, a = 3;
d = 2, c = 0, b = 2, a = 2;
How to Run in Prolog:
A file, part2.pl, is provided that will read in a file with definitions and constraints until encountering the end of the file
(EOF). Note that part2.pl imports the file read_line.pl, which is also provided in the PA3 web directory. As it stands, all
it does is print out the parsed data from the statements. See the What Is To Be Done section above on what you need to
add to part2.pl.
To test this file, run the following:
swipl -f part2.pl -g main < procSpec1.txt 4 Notes for Oz Programmers: Compiling and Running All coding will be done in part2.oz. part2Helper.oz contains a helper (Helper.tokenize) that will read and tokenize the spec file for you. ozc -c part2Helper.oz #Only need to do this once ozc -c part2.oz ozengine part2.ozf procSpec1.txt #Run one or both of these to test ozengine part2.ozf procSpec2.txt A Warning About Attempting to Circumvent The Natural Language Processing Grammar in Oz In Oz, it is possible to do much more advanced list manipulation out of the box than in prolog. Hence, many people may be inclined to make an attempt at extracting the relevant information from the token list by looking at the positions of tokens in the line or looking for keywords that surround a token and extracting from there. While it is certainly possible to do this, we have explicitly designed the grammar so this approach will be very difficult. Thus, you are strongly encouraged to make use of a Natural Language Processing Grammar and to avoid naive extraction approaches. What To Submit & Grading For Part 1, please submit either relations.pl or relations.oz, depending on the language you choose. These files will be tested with a main file similar to part1_template.pl or part1Tester.oz, but with queries not revealed publicly. This should be no issue, as properly implemented rules should be rather flexible. For Part 2, please submit either your completed version of part2.pl or part2.oz, depending on the language you choose. The read_line (Helper.tokenize) files in both languages are provided and do not need to be edited. You should also submit a readme.txt file with your name (or names if you have a partner). If you have any comments; reports of bugs, self assessments, anything, put it in your readme. For all submitted files, please zip them up into a .zip file, with its filename matching the pattern: [your_rcs_id]_[language_identifier].zip For example, jsmith_pl.zip and jdoe_oz.zip are acceptable. For partners, please specify both of your RCS ID’s, like so: jdoe_jsmith_pl.zip. The grade components are as follows: Part Percentage 1: A Family Tree 40% 2: Microprocessor Constraint Language (see sub-parts below) 2a: NLP Parser 25% 2b: Constraint Calculation 25% Code Clarity & Comments 10% Warning About Posting Solutions Publicly & Inter-Team Code Sharing Do not post any code you submit for this assignment onto any public website or network share. Also, your code from your team (which can be at most two people) should be wholly yours; Do not look at or use code made by other students and/or teams as your own. If violation of either of these rules is detected, your grade will be heavily affected. Links & Documentation for (SWI) Prolog • Quickstart documentation: – https://www.swi-prolog.org/pldoc/man?section=quickstart • Installers for version 8.4 (Windows/MAC): – https://www.swi-prolog.org/download/stable (for Linux, check your package manager for swi-prolog) • Definate Clause Grammar documentation: – https://www.swi-prolog.org/pldoc/man?section=DCG 5