Homework 1. Fixpoints and grammar filters
131 homeHomework
Introduction
You are a reader for Computer Science 181, which asks students to submit grammars that solve various problems. However, many of the submitted grammars are trivially wrong, in several ways. Here is one. Some grammars contain unreachable rules, that is, rules that can never be reached from the start symbol by applying zero or more rules. Unreachable rules do not affect the language or parse trees generated by a grammar, so in some sense they dont make the answers wrong, but theyre noise and they make grading harder. Youd like to filter out the noise, and just grade the useful parts of each grammar.
Youve heard that OCaml is a good language for writing compilers and whatnot, so you decide to give it a try for this application. While youre at it, you have a background in fixed point and periodic point theory, so you decide to give it a try too.
Definitions
fixed point
of a function f A point x such that f xx. In this description we are using OCaml notation, in which functions always have one argument and parentheses are not needed around arguments.
computed fixed point
of a function f with respect to an initial point x A fixed point of f computed by calculating x, f x, f f x, f f f x, etc., stopping when a fixed point is found for f. If no fixed point is ever found by this procedure, the computed fixed point is not defined for f and x.
periodic point
of a function f with period p A point x such that f f … f xx, where there are p occurrences of f in the call. That is, a periodic point is like a fixed point, except the function returns to the point after p iterations instead of 1 iteration. Every point is a periodic point for p0. A fixed point is a periodic point for p1.
computed periodic point
of a function f with respect to a period p and an initial point x A periodic point of f with period p, computed by calculating x, f x, f f x, f f f x, etc., stopping when a periodic point with period p is found for f. The computed periodic point need not be equal to x. If no periodic point is ever found by this procedure, the computed periodic point is not defined for f, p, and x.
symbol
A symbol used in a grammar. It can be either a nonterminal symbol or a terminal symbol; each kind of symbol has a value, whose type is arbitrary. A symbol has the following OCaml type:
type nonterminal, terminal symbol
N of nonterminal
T of terminal
right hand side
A list of symbols. It corresponds to the right hand side of a single grammar rule. A right hand side can be empty.
rule
A pair, consisting of 1 a nonterminal value the left hand side of the grammar rule and 2 a right hand side.
grammar
A pair, consisting of a start symbol and a list of rules. The start symbol is a nonterminal value.
Assignment
Lets warm up by modeling sets using OCaml lists. The empty list represents the empty set, and if the list t represents the set T, then the list h::t represents the set hT. Although sets by definition do not contain duplicates, the lists that represent sets can contain duplicates. Another set of warmup exercises will compute fixed points. Finally, you can write a function that filters unreachable rules.
1.Write a function subset a b that returns true iff ab, i.e., if the set represented by the list a is a subset of the set represented by the list b. Every set is a subset of itself. This function should be generic to lists of any type: that is, the type of subset should be a generalization of a lista listbool.
2.Write a function equalsets a b that returns true iff the represented sets are equal.
3.Write a function setunion a b that returns a list representing ab.
4.Write a function setintersection a b that returns a list representing ab.
5.Write a function setdiff a b that returns a list representing ab, that is, the set of all members of a that are not also members of b.
6.Write a function computedfixedpoint eq f x that returns the computed fixed point for f with respect to x, assuming that eq is the equality predicate for fs domain. A common case is that eq will be , that is, the builtin equality predicate of OCaml; but any predicate can be used. If there is no computed fixed point, your implementation can do whatever it wants: for example, it can print a diagnostic, or go into a loop, or send nasty email messages to the users relatives.
7.OK, now for the real work. Write a function filterreachable g that returns a copy of the grammar g with all unreachable rules removed. This function should preserve the order of rules: that is, all rules that are returned should be in the same order as the rules in g.
8.Supply at least one test case for each of the above functions in the style shown in the sample test cases below. When testing the function F call the test cases myFtest0, myFtest1, etc. For example, for subset your first test case should be called mysubsettest0. Your test cases should exercise all the above functions, even though the sample test cases do not.
Your code should follow these guidelines:
1.Your code may use the Pervasives and List modules, but it should use no other modules other than your own code.
2.It is OK and indeed encouraged for your solutions to be based on one another; for example, it is fine for filterreachable to use equalsets and computedfixedpoint.
3.Your code should prefer pattern matching to conditionals when pattern matching is natural.
4.Your code should be free of side effects such as loops, assignment, inputoutput, incr, and decr. Use recursion instead of loops.
5.Simplicity is more important than efficiency, but your code should avoid using unnecessary time and space when it is easy to do so. For example, instead of repeating a expression, compute its value once and reuse the computed value.
6.The test cases below should work with your program. You are unlikely to get credit for it otherwise.
Assess your work by writing a brief afteraction report that summarizes why you solved the problem the way you did, other approaches that you considered and rejected and why you rejected them, and any weaknesses in your solution in the context of its intended application. This report should be a plain text file that is no more than 2000 bytes long. See Resources for oral presentations and written reports for advice on how to write assessments; admittedly much of the advice there is overkill for the simple kind of report were looking for here.
Submit
Submit three files via CourseWeb. The file hw1.ml should implement the abovementioned functions, along with any auxiliary types and functions; in particular, it should define the symbol type as shown above. The file hw1test.ml should contain your test cases. The file hw1.txt should hold your assessment. Please do not put your name, student ID, or other personally identifying information in your files.
Sample test cases
See hw1sample.ml for a copy of these tests.
let subsettest0subset1;2;3
let subsettest1subset 3;1;3 1;2;3
let subsettest2not subset 1;3;7 4;1;3
let equalsetstest0equalsets 1;3 3;1;3
let equalsetstest1not equalsets 1;3;4 3;1;3
let setuniontest0equalsets setunion1;2;3 1;2;3
let setuniontest1equalsets setunion 3;1;3 1;2;3 1;2;3
let setuniontest2equalsets setunion
let setintersectiontest0
equalsets setintersection1;2;3
let setintersectiontest1
equalsets setintersection 3;1;3 1;2;3 1;3
let setintersectiontest2
equalsets setintersection 1;2;3;4 3;1;2;4 4;3;2;1
let setdifftest0equalsets setdiff 1;3 1;4;3;1
let setdifftest1equalsets setdiff 4;3;1;1;3 1;3 4
let setdifftest2equalsets setdiff 4;3;11;3;4
let setdifftest3equalsets setdiff4;3;1
let computedfixedpointtest0
computedfixedpointfun xx2 10000000000
let computedfixedpointtest1
computedfixedpointfun xx . 2. 1.infinity
let computedfixedpointtest2
computedfixedpointsqrt 10.1.
let computedfixedpointtest3
computedfixedpoint fun x yabsfloat x . y1.
fun xx . 2.
10.
1.25
An example grammar for a small subset of Awk.
type awksubnonterminals
ExprLvalueIncropBinopNum
let awksubrules
Expr, T; N Expr; T;
Expr, N Num;
Expr, N Expr; N Binop; N Expr;
Expr, N Lvalue;
Expr, N Incrop; N Lvalue;
Expr, N Lvalue; N Incrop;
Lvalue, T; N Expr;
Incrop, T;
Incrop, T;
Binop, T;
Binop, T;
Num, T0;
Num, T1;
Num, T2;
Num, T3;
Num, T4;
Num, T5;
Num, T6;
Num, T7;
Num, T8;
Num, T9
let awksubgrammarExpr, awksubrules
let awksubtest0
filterreachable awksubgrammarawksubgrammar
let awksubtest1
filterreachable Expr, List.tl awksubrulesExpr, List.tl awksubrules
let awksubtest2
filterreachable Lvalue, awksubrulesLvalue, awksubrules
let awksubtest3
filterreachable Expr, List.tl List.tl awksubrules
Expr,
Expr, N Expr; N Binop; N Expr;
Expr, N Lvalue;
Expr, N Incrop; N Lvalue;
Expr, N Lvalue; N Incrop;
Lvalue, T ; N Expr;
Incrop, T ;
Incrop, T ;
Binop, T ;
Binop, T
let awksubtest4
filterreachable Expr, List.tl List.tl List.tl awksubrules
Expr,
Expr, N Lvalue;
Expr, N Incrop; N Lvalue;
Expr, N Lvalue; N Incrop;
Lvalue, T ; N Expr;
Incrop, T ;
Incrop, T
type giantnonterminals
ConversationSentenceGruntSnoreShoutQuiet
let giantgrammar
Conversation,
Snore, TZZZ;
Quiet, ;
Grunt, Tkhrgh;
Shout, Taooogah!;
Sentence, N Quiet;
Sentence, N Grunt;
Sentence, N Shout;
Conversation, N Snore;
Conversation, N Sentence; T,; N Conversation
let gianttest0
filterreachable giantgrammargiantgrammar
let gianttest1
filterreachable Sentence, List.tl snd giantgrammar
Sentence,
Quiet, ; Grunt, T khrgh; Shout, T aooogah!;
Sentence, N Quiet; Sentence, N Grunt; Sentence, N Shout
let gianttest2
filterreachable Quiet, snd giantgrammarQuiet, Quiet,
Sample use of test cases
When testing on SEASnet, use one of the machines lnxsrv06.seas.ucla.edu, lnxsrv07.seas.ucla.edu, lnxsrv09.seas.ucla.edu, and lnxsrv10.seas.ucla.edu. Make sure usrlocalcsbin is at the start of your path, so that you get the proper version of OCaml. To do this, append the following lines to your HOME.profile file if you use bash or ksh:
export PATHusrlocalcsbin:PATH
or the following line to your HOME.login file if you use tcsh or csh:
set pathusrlocalcsbin path
The command ocaml should output the version number 4.07.1.
If you put the sample test cases into a file hw1sample.ml, you should be able to use it as follows to test your hw1.ml solution on the SEASnet implementation of OCaml. Similarly, the command use hw1test.ml;; should run your own test cases on your solution.
ocaml
Objective Caml version 4.07.1
use hw1.ml;;
type a, b symbolN of aT of b
…
use hw1sample.ml;;
val subsettest0 : booltrue
val subsettest1 : booltrue
val subsettest2 : booltrue
val equalsetstest0 : booltrue
val equalsetstest1 : booltrue
val setuniontest0 : booltrue
val setuniontest1 : booltrue
val setuniontest2 : booltrue
val setintersectiontest0 : booltrue
val setintersectiontest1 : booltrue
val setintersectiontest2 : booltrue
val computedfixedpointtest0 : booltrue
val computedfixedpointtest1 : booltrue
val computedfixedpointtest2 : booltrue
val computedfixedpointtest3 : booltrue
type awksubnonterminalsExprLvalueIncropBinopNum
val awksubrules :
awksubnonterminalsawksubnonterminals, string symbol list list
Expr, T ; N Expr; T ; Expr, N Num;
Expr, N Expr; N Binop; N Expr; Expr, N Lvalue;
Expr, N Incrop; N Lvalue; Expr, N Lvalue; N Incrop;
Lvalue, T ; N Expr; Incrop, T ; Incrop, T ;
Binop, T ; Binop, T ; Num, T 0; Num, T 1;
Num, T 2; Num, T 3; Num, T 4; Num, T 5;
Num, T 6; Num, T 7; Num, T 8; Num, T 9
val awksubgrammar :
awksubnonterminals
awksubnonterminalsawksubnonterminals, string symbol list list
Expr,
Expr, T ; N Expr; T ; Expr, N Num;
Expr, N Expr; N Binop; N Expr; Expr, N Lvalue;
Expr, N Incrop; N Lvalue; Expr, N Lvalue; N Incrop;
Lvalue, T ; N Expr; Incrop, T ; Incrop, T ;
Binop, T ; Binop, T ; Num, T 0; Num, T 1;
Num, T 2; Num, T 3; Num, T 4; Num, T 5;
Num, T 6; Num, T 7; Num, T 8; Num, T 9
val awksubtest0 : booltrue
val awksubtest1 : booltrue
val awksubtest2 : booltrue
val awksubtest3 : booltrue
val awksubtest4 : booltrue
type giantnonterminals
Conversation
Sentence
Grunt
Snore
Shout
Quiet
val giantgrammar :
giantnonterminals
giantnonterminalsgiantnonterminals, string symbol list list
Conversation,
Snore, T ZZZ; Quiet, ; Grunt, T khrgh;
Shout, T aooogah!; Sentence, N Quiet; Sentence, N Grunt;
Sentence, N Shout; Conversation, N Snore;
Conversation, N Sentence; T ,; N Conversation
val gianttest0 : booltrue
val gianttest1 : booltrue
val gianttest2 : booltrue
20062011, 20132019 Paul Eggert. See copying rules.
Id: hw1.html,v 1.77 20190925 00:54:08 eggert Exp
Reviews
There are no reviews yet.