Faculty of Technology – Course work Specification
Module name:
Modern Programming Techniques
Module code:
CTEC5726
Title of the Assignment:
Tautology Checker
This coursework item is: (delete as appropriate)
Summative
This summative coursework will be marked anonymously
Yes
The learning outcomes that are assessed by this coursework are:
1 Analyse and critically review the principal concepts of functional software design
2 Critically evaluate the support for the application of functional software design in the context of a contemporary programming language
3 Apply functional software design to produce a software solution to a practical problem
4 Analyse a given functional software solution in terms of relevant performance criteria
This coursework is: (delete as appropriate)
Individual
This coursework constitutes 100% to the overall module mark.
Date Set:
Friday 8th May 2020
Date & Time Due:
Friday 14th August no later than 12:00 (noon)
Your marked coursework and feedback will be available to you on:
If for any reason this is not forthcoming by the due date your module leader will let you know why and when it can be expected. The Head of Studies (headofstudies-tec@dmu.ac.uk ) should be informed of any issues relating to the return of marked coursework and feedback.
Note that you should normally receive feedback on your coursework by no later than four working weeks after the formal hand-in date, provided that you met the submission deadline.
Monday 14th September 2020
When completed you are required to submit your coursework to:
• Blackboard VLE for the Scala code (source code only, zipped into a single compressed file)
• Turnitin through the submission portal for the report
Late submission of coursework policy: Late submissions will be processed in accordance with current University regulations which state:
“the time period during which a student may submit a piece of work late without authorisation and have the work capped at 40% [50% at PG level] if passed is 14 calendar days. Work submitted unauthorised more than 14 calendar days after the original submission date will receive a mark of 0%. These regulations apply to a student’s first attempt at coursework. Work submitted late without authorisation which constitutes reassessment of a previously failed piece of coursework will always receive a mark of 0%.”
Academic Offences and Bad Academic Practices:
These include plagiarism, cheating, collusion, copying work and reuse of your own work, poor referencing or the passing off of somebody else’s ideas as your own. If you are in any doubt about what constitutes an academic offence or bad academic practice you must check with your tutor. Further information and details of how DSU can support you, if needed, is available at:
http://www.dmu.ac.uk/dmu-students/the-student-gateway/academic-support-office/academic-offences.aspx and http://www.dmu.ac.uk/dmu-students/the-student-gateway/academic-support-office/bad-academic-practice.aspx
Tasks to be undertaken: See (following) attached document.
Deliverables to be submitted for assessment: See (following) attached document.
How the work will be marked: See (following) attached document.
Module leader/tutor name:
David Smallwood
Contact details:
drs@dmu.ac.uk (GH6.70)
Important note
Please do NOT be tempted to search the internet for an existing solution and then hand this in – e.g. if you run out of time. This is cheating – it is better to hand in what you have honestly achieved by yourself than try to get credit for someone else’s work and risk getting caught. Cheating is an academic offence.
If you get stuck then please ask the module tutors for assistance and come to the labs – we will be providing help in the labs (but not actually doing it for you of course).
Do NOT use anyone else’s material without referencing it – this is bad academic practice or plagiarism. These are considered as academic offences.
Do NOT work jointly on a solution; do NOT give your solution to anyone else to “help them” and do NOT accept anyone else’s solution as “guidance”. Such practice could lead to an allegation of collusion which is an academic offence. All parties involved in collusion (the givers, the receivers, the collaborators) can be found guilty of an academic offence, irrespective of motive.
Preamble
This assignment uses the lib.expr package and files contained therein. These files are available on Blackboard and are the same ones that were used as part of the delivery of the module.
Submission requirements
There are two submission portals on Blackboard.
• Code (within the Assessment tab on Blackboard)
• Report (a Turnitin link within the Assessment tab on Blackboard)
Make sure that you zip your source code, including Expr.scala and Demo.scala, into a single zip file. Only use zip or gzip for this purpose – please do not use any other compression tools (e.g. do not use rar, 7zip, etc.)
Then upload your compressed file to the Code portal on Blackboard.
Upload your report to the Report Turnitin portal. Please only upload a word document or a pdf file. Please use your P-number within the name of the file. For example, if your P-number was P1234567 then your report would be P1234567Report.docx or P1234567Report.pdf.
Coursework Specification: Requirement 1 (50%)
NB: This is a programming exercise designed to utilise the functional programming techniques that have been studied on the module. Higher marks will be obtained for practical solutions that are written more strongly in a functional style than in a traditional (OO) style. The marking scheme will reflect this.
Your first task is to complete the Expr.scala file by implementing two incomplete functions whose signatures appear in the Expr companion object (object Expr). Each of the functions is defined below:
• isFormula(expr: Expr): Boolean
This function should return true if and only if the expression contains:
• Possibly the literals 0 and 1 (representing false and true), but no other literals
• Possibly variables
• Possibly any of the logical operators, ~, &&, ||, implies, equiv, but no other operators
Thus, isFormula(parse(“0 implies x || ~x”)) is true, whereas
isFormula (parse(“1 + 3 > y && z”)) is false.
Note that it is easier to write the expressions as Strings and then use the parse function (lib.expr.Parser.parse) to convert these into Expr instances. For this purpose, the following overloaded function has been provided (within object Expr):
def isFormula(e: String): Boolean = isFormula(parse(e))
• isTautology(expr: Expr): Option[Boolean]
This function should return Some(true) if and only if the expression is a formula that is also a tautology. If the expression is a logical expression but is not a tautology then the function should return Some(false). If the expression is not a logical expression then the function should return None – this case has been provided for you already.
To establish whether or not the function is a tautology you should, in turn, assign every combination of truth values (0 and 1) to the variables in the expression. If the expression evaluates to true (1) in every case then it is a tautology. This truth table method of proof is illustrated by the following example:
~(a && b) equiv (~a || ~b) is a tautology because it evaluates to true for every combination of inputs a and b.
a
b
~(a&&b) equiv ~a||~b
1
1
1
1
0
1
0
1
1
0
0
1
Once again, an overloaded version of this function has been provided that allows you to pass the expression as a String.
def isTautology(e: String): Boolean = isTautology(parse(e))
Coursework Specification: Requirement 2 (20%)
NB: This aspect can be written in either a functional or a more traditional (OO) style if preferred. For example, a while loop may be used to control the iteration. The marking scheme for this requirement is looking for a working solution that satisfies the specification.
Using the Demo.scala program template provided, complete the program so that it permits the user to enter a String representing a logical expression; then prints out the truth table for the expression; and finally prints out whether or not the expression is a tautology. Your program should permit the user to enter expressions and view results repeatedly until terminated by entering a single full stop “.”
Ensure that your code is well-commented so that the assessor can appreciate how you developed your solution. Put a block comment before each method. You may insert smaller comments inline as and when these are necessary. The comments should clearly indicate your thinking – particularly when the algorithm may have more complicated components to explain.
Coursework Specification: Requirement 3 (30%)
Write a short paper (about 1000 words) in which you analyse and critically review your experience of this assignment, and of functional programming in Scala more generally.
You should select and describe two specific ways in which your experience with the functional programming style has challenged, and possibly changed, your previous understanding of code development. Justify your arguments by pointing to aspects of your own solution to this assignment that support the points you have made.
Finally, reflect on your own personal experience of studying functional software development. Provide two examples: in the first case, describe one aspect of learning and applying functional programming that you found particularly challenging, and explain why. In the second case, describe one aspect of functional programming that has particularly inspired or intrigued you, and explain why.
Help and guidance on how to check for a tautology
NB: This section contains some helpful hints that you may like to consider in constructing a solution to this problem. However, you are free to solve the problem using a different approach to either of those below.
The solution involves evaluation of a formula for every combination of its inputs. This method requires that you find all of the distinct variables within a formula and then evaluate the formula with every combination of truth values to which these variables could be assigned. Effectively, this is computing the formula for every row in the truth table. We suggest that in order to get the variables in a formula you write the following function:
def getVars: List[Var]
When you know how many distinct variables there are in the formula, then you need to generate every combination of truth values that may be assigned to these variables. One way to generate all of the combinations is to construct a table for n variables:
def tt(n: Int): List[List[Lit]]
Now there are two ways in which you might evaluate the formula for each row of the table. For example, suppose you have two variables, “x” and “y”, then the table of combinations would be [ [1, 1], [1, 0], [0, 1], [1, 1] ]. Suppose the formula was “x && y” (which is obviously not a tautology). Then you could do EITHER of the following:
• For each ‘row’ in the table ‘wrap’ the formula in let expressions: e.g. the second row could produce “{let x = 1 in {let y = 0 in x && y}}”. Each “wrapped” formula can be evaluated in turn.
• Alternatively, each ‘row’ could be used to create a new environment (Env) with the appropriate bindings of x and y. Then the formula could be evaluated within each of these environments.
Assessment grid
Requirement 1 50%
NB The requirements here include writing in a functional style rather than in a traditional (OO) style and will be interpreted in this sense. For example, a fully working solution that uses very few functional programming concepts will score poorly.
Fail: 0-19 No solution or code that falls far short of a working program
Fail: 20-39 Poor attempt that fails to meet the basic requirements
Fail: 40-49 Poor attempt that just fails to meet the basic requirements
Pass: 50-59 A solution that just meets the basic requirements
Pass: 60-69 A solution that meets the majority of the requirements
Pass: 70-79 A solution that meets the all of the requirements
Pass: 80-89 A solution that exceeds the requirements and demonstrates flair
Pass: 90-100 As above but demonstrates exceptional analytical/creative skills
Requirement 2 20%
NB This piece of code may be written in a functional or traditional (OO) style or in any combination of these. However, the code should be clear and concise and meet the requirements.
Fail: 0-19 No solution or code that falls far short of a working program
Fail: 20-39 Poor attempt that fails to meet the basic requirements
Fail: 40-49 Poor attempt that just fails to meet the basic requirements
Pass: 50-59 A solution that just meets the basic requirements
Pass: 60-69 A solution that meets the majority of the requirements
Pass: 70-79 A solution that meets the all of the requirements
Pass: 80-89 A solution that exceeds the requirements and demonstrates flair
Pass: 90-100 As above but demonstrates exceptional analytical/creative skills
Analysis 30%
NB The analysis should be critical – points must be substantiated. Vague opinions with little to support them will score poorly. Likewise, examples and theoretical explanations must be appropriate to support the points being argued. This is a reflective piece and it must be rooted in your own practical experience. General aspects of functional programming obtained from external sources and not clearly related to your own practical work will indicate a lack of depth of understanding and will score poorly. Detailed analysis and fair criticism of your own approach, based upon appropriate examples and explanations, are what is required.
Fail: 0-19 Displays only isolated knowledge. Does not address the criteria
Fail: 20-39 Addresses few of the criteria with weak argument/poor understanding
Fail: 40-49 Addresses some of the criteria with weak argument/poor understanding
Pass: 50-59 Addresses most of the criteria with some degree of understanding
Pass: 60-69 Addresses most of the criteria with good degree of understanding
Pass: 70-79 Addresses all of the criteria with good degree of understanding
Pass: 80-89 Addresses all of the criteria demonstrating an authoritative grasp
Pass: 90-100 As above but demonstrates exceptional analytical/creative skills