{"action":"closed","issue":{"url":"https://api.github.com/repos/gitslaton/ProgLangAssignments/issues/107","repository_url":"https://api.github.com/repos/gitslaton/ProgLangAssignments","labels_url":"https://api.github.com/repos/gitslaton/ProgLangAssignments/issues/107/labels{/name}","comments_url":"https://api.github.com/repos/gitslaton/ProgLangAssignments/issues/107/comments","events_url":"https://api.github.com/repos/gitslaton/ProgLangAssignments/issues/107/events","html_url":"https://github.com/gitslaton/ProgLangAssignments/issues/107","id":140946396,"number":107,"title":"Test Comparison Operators ","user":{"login":"gitslaton","id":10524611,"avatar_url":"https://avatars.githubusercontent.com/u/10524611?v=3","gravatar_id":"","url":"https://api.github.com/users/gitslaton","html_url":"https://github.com/gitslaton","followers_url":"https://api.github.com/users/gitslaton/followers","following_url":"https://api.github.com/users/gitslaton/following{/other_user}","gists_url":"https://api.github.com/users/gitslaton/gists{/gist_id}","starred_url":"https://api.github.com/users/gitslaton/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gitslaton/subscriptions","organizations_url":"https://api.github.com/users/gitslaton/orgs","repos_url":"https://api.github.com/users/gitslaton/repos","events_url":"https://api.github.com/users/gitslaton/events{/privacy}","received_events_url":"https://api.github.com/users/gitslaton/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/gitslaton/ProgLangAssignments/labels/tests","name":"tests","color":"5319e7"}],"state":"closed","locked":false,"assignee":null,"milestone":{"url":"https://api.github.com/repos/gitslaton/ProgLangAssignments/milestones/6","html_url":"https://github.com/gitslaton/ProgLangAssignments/milestones/Interpreter%20","labels_url":"https://api.github.com/repos/gitslaton/ProgLangAssignments/milestones/6/labels","id":1644720,"number":6,"title":"Interpreter ","description":"# Programming Languages, Assignment 8\r\n\r\nBuilding an Interpreter\r\n\r\nThis file contains a description of the tasks you have to perform for assignment 8.\r\n\r\nTo better view the file, make sure your editor \"warps\" lines. In Sublime Text this is the \"Word Wrap\" option in the View menu.\r\n\r\nAlternately, you can view this file in a nice form in GitHub.\r\n\r\nAs in previous assignments, you should NOT specify the types of your functions. Let the system determine them for you.\r\n\r\n**IMPORTANT**: Unlike the prior assignments, this assignment requires you to edit multiple files, contained in the `interpreter` folder. You will need to make additions to the following files:\r\n\r\n- `types.ml`\r\n- `types.mli`\r\n- `parser.mly`\r\n- `lexer.mll`\r\n- `tests.ml`\r\n\r\nThe steps of this assignment are broken up depending on the concept that they add to the language. Each will require you to make additions to one or more of the files above.\r\n\r\nThe automatic tests are only meant to test that the desugar and interp methods are working properly. For the changes in the lexer and parser, you should interact with the `./lang` interpreter directly.\r\n\r\nIt will be important in the following to clarify which exceptions you should be raised when. Anything that violates the semantics of the language should be raising an appropriate exception, typically `Interp ...`. For instance if the description that follows says about \"addition\" that the two summands must be numbers, then your code will need to verify that before trying to perform the addition, and raise an appropriate exception.\r\n\r\nYou will probably want to create different milestones for each of these types of language extensions.\r\n\r\n## Booleans\r\n\r\nThe first thing we will do is add booleans. We will add new values, boolean primitive, conditionals, as well as logical operators desugared into conditionals.\r\n\r\nIt is important to distinguish between talking about the core/surface language's booleans, that we are trying to define, and the implementation/OCAML language's booleans.\r\n\r\n### Boolean primitives\r\n\r\n- Add a new `Bool` variant in the `value` type in the `types.ml` file and the `types.mli` file. It should hold a OCAML boolean. Update the `valToString` function to handle this new kind of value. The `valToString` function is not used in any of the grading tests, you can choose to \"print\" booleans any way you like.\r\n- Add a new `BoolC` variant in the `exprC` type in the `types.ml` file and the `types.mli` file. It should hold a OCAML boolean.\r\n- Add a case in the `interp` match to correctly \"interpret/evaluate\" a `BoolC` to the appropriate `value`.\r\n- Add some tests in `tests.ml` for the correct interpretation of `BoolC`.\r\n- Add a new `BoolS` variant in the `exprS` type in the `types.ml` file and the `types.mli` file. It should hold a OCAML boolean.\r\n- Add a new case in the `desugar` match to correctly desugar a `BoolS` expression to the appropriate `exprC`.\r\n- Add tests for the appropriate desugaring.\r\n- Add two new tokens `TRUE` and `FALSE` at the top of `parser.mly` (where the `FLOAT` token is defined). They should not \"contain\" anything (so no need for `<float>`). You can put them both in one line, like so: `%token TRUE FALSE`.\r\n\r\n### Parser modifications for interpreter\r\n\r\nThe following add the appropriate parser/lexer instructions for processing booleans.\r\n\r\n- Add two new cases to the `expr` set of rules near the bottom of `parser.mly`, one for `TRUE` and one for `FALSE`. The corresponding expressions in braces should simply create the appropriate surface language expressions (involving `BoolS`).\r\n- In `lexer.mll`, add the two regular expression definitions `let true = \"true\" | \"#t\"` (and an analogous one for false). This would allow us to type `true` or `#t` and have it be recognized as a boolean in the language.\r\n- Add cases to the `rule` section in `lexer.mll` that turns the `true` match to the `TRUE` token and similarly for `false`. The order is important, don't put the new cases too far down. The last two rules are catch-alls, and should remain at the end of the options.\r\n\r\nTo test this part, you should follow the compile steps in the README file. Then start the interpreter via `./lang`, and you should be able to type `true;;` or `#t;;` (and similarly for false), and have the interpreter reply appropriately.\r\n\r\n### Conditionals\r\n\r\nWe will now add conditionals. This does not require a new value, but it does require changes to the core and surface language, and the parser and lexer.\r\n\r\n- Add a new variant in the `exprC` type (in both `types.ml` and `types.mli`) for an `IfC` that takes 3 `exprC`s as arguments (a triple). The first of those is meant to be the conditional test, the second is the `then` branch, the third is the `else` branch.\r\n- Add a case in `interp` for properly evaluating a conditional: The test expression should be evaluated first (recursively calling `interp`), and it should be an error (raise `Interp`) if the result is not a `Bool` value. If it is a `Bool` value, then depending on the value either the \"then\" branch or the \"else\" branch should be evaluated. Only one of these branches should be evaluated, and only after the conditional test has first been evaluated. It is *imperative* that you ensure the appropriate evaluation semantics for the conditional. Make sure to parenthesize any inner match that you use.\r\n- Add tests for the correct behavior of the conditional. For example the expression `IfC (BoolC true, NumC 2.3, NumC 4.3)` should evaluate to `Num 2.3`. Make sure to allow the possibility where the \"test\" is not a `BoolC` directly, but something that evaluates to a boolean; for instance it could be another `IfC` expression.\r\n- Add a corresponding expression `IfS` at the surface language, that takes as arguments three `exprS` expressions, and it desugars into an appropriate `IfC` expression.\r\n- Add a case in the `desugar` match to handle `IfS` and convert it to `IfC`.\r\n\r\nWe will now add \"or\", \"and\" and \"not\" to the surface language. They will all convert to `IfC`s.\r\n\r\n- Add an `OrS`, a `AndS` and a `NotS` to the surface language, the first two taking two expressions as arguments, the third taking only one expression.\r\n- Add `desugar` cases for each of them based on the following pseudo-codes: \"`not e` is the same as `if e then false else true`\", \"`e1 or e2` is the same as `if e1 then true else if e2 then true else false`\", and something analogous for `and`. Note that we did not use `if e1 then true else e2` for the \"or\" case, because we want to enforce the behavior that both expressions are booleans. The conditional checks that already for its test, but not for its branch values.\r\n- Add tests to verify the correct implementation of these constructs.\r\n\r\nNow we will add the correct components in the parser and lexer.\r\n\r\n- Add three new tokens in `parser.mly`, called `IF`, `THEN` and `ELSE`, all in one line.\r\n- Add `%nonassoc ELSE` below the `%nonassoc FLOAT` line.\r\n- Add a case in the `expr` rule in `parser.mly` that expects a `IF expr THEN expr ELSE expr` and turns it into an `IfC`. You will need to use `$2`, `$4` and so on to refer to the values of those `expr`s.\r\n- Add three cases in the rules in `lexer.mll` for the strings `\"if\"`, `\"then\"` and `\"else\"` and converting them to the corresponding tokens `IF`, `THEN`, `ELSE`. No need to use `let` assignments for these single cases.\r\n\r\nCompiling after these should allow you to write if-then-else cases. We will now add \"or\" and \"else\".\r\n\r\n- Add three new tokens in `parser.mly`, called `OR`, `AND` and `NOT`.\r\n- We need to specify precedence rules. This would be done by adding `%left OR AND` below the `%nonassoc ELSE` line. This says that both \"or\" and \"and\" should compute in a left-first direction, and they should be treated as having equal precedence to each other and stronger precedence to the `ELSE`. This way, an expression like `if true then false else false or true` would be interpreted as `if true then false else (false or true)` instead of `(if true then false else false) or true`.\r\n- Add in the `expr` rule at the bottom of `parser.mly` cases for `expr OR expr` and `expr AND expr`.\r\n- Add a precedence rule `%nonassoc NOT` below the one for OR and AND.\r\n- Add an `expr` rule at the bottom of `parser.mly` for `NOT expr`.\r\n- Add in `lexer.mll` three rules for `\"or\"`, `\"and\"` and `\"not\"`.\r\n\r\n### Arithmetic Operators\r\n\r\nWe will now add arithmetic operators, followed by comparison operators and finally, equality.\r\n\r\n- Add a new `exprC` type variant `ArithC` that takes a \"string\" for the operator symbol, and two `exprC`s for the two operands.\r\n- Implement a new \"helper method\" called `arithEval` with type `string -> value -> value -> value` that takes the operator and two values. If the two values are not both `Num`s then it should raise an interpreter exception. If they are then it should perform the appropriate operation and return a \"value\" of the result. The operators we will allow will be \"+\", \"-\", \"*\" and \"/\". It should throw an interpreter error if the operator symbol is not one of these. It should also throw an interpreter error about division by zero if the operator is division and the denominator is 0. Remember that in our arithmetic world, all numbers are floating point numbers.\r\n- Add a new case in `interp` to handle `ArithC` cases by evaluating the two operands in the correct order, then calling the `arithEval` helper method.\r\n- Add tests to ensure these cases are handled properly.\r\n- Add a new `exprS` type variant `ArithS` that models `ArithC`.\r\n- Add a new case in the desugarer to convert `ArithS` to `ArithC`.\r\n- Add tests for the desugaring.\r\n\r\nNow we add parser/lexer operations corresponding to these.\r\n\r\n- Add in `parser.mly` four new tokens, `PLUS`, `MINUS`, `TIMES`, `DIVIDE`.\r\n- We next need to set up precedence rules. Place at the bottom of the current list, below the `%nonassoc NOT`, a line `%left PLUS MINUS`, and below that line add `%left TIMES DIVIDE`. This will ensure that all operations are performed in a left-associative way, and that multiplication and division will have higher precedence than addition and subtraction. This will agree with normal algebra rules.\r\n- Add `expr` cases at the bottom of `parser.mly` for `expr PLUS expr` and similarly for the other operations. They should all convert to the appropriate `ArithS` expression.\r\n- Add in `lexer.mll` near the bottom rules for `\"+\"`, `\"-\"` and so on, to be converted to the corresponding tokens `PLUS`, `MINUS` and so on. Remember that the last two rules there about `eof` and `any` are catchalls and need to be the last cases.\r\n\r\nYou should now be able to compile and try various arithmetic operations. Also test something like `if true then 4 else 2 + 3`, and make sure that the addition binds stronger than the conditionals. Also that `2 + 3 * 4` behaves properly.\r\n\r\n### Comparison Operators\r\n\r\nThe comparison operators we will consider are \">\", \">=\", \"<\", \"<=\". We leave equality and non-equality as a separate case, as they make sense for more than just numbers.\r\n\r\n- Add a new `exprC` type variant `CompC` that takes a string and two `exprC`s.\r\n- Create a helper method `compEval` with type `string -> value -> value -> value` that takes as input a string and two values. If the two values are not both `Num`s then it should raise an interpreter error. If they are, then it should perform the appropriate operator and return a `Bool` value. It should be an interpreter error if the operator is not one of the four mentioned above.\r\n- Add a new case in `interp` to handle the `CompC` construct, by evaluating the two expressions in the correct order then passing the work over to `compEval`.\r\n- Add tests for the comparison semantics.\r\n- Add a new `exprS` type variant `CompS` analogous to `CompC`, and the corresponding clause in `desugar` to convert it into `CompC`.\r\n- Add tests for the desugaring.\r\n\r\nNow to adjust the parser/lexer:\r\n\r\n- Add a new token called `COMPOP` that contains a string in it. Model it after the `FLOAT` token.\r\n- Place `%nonassoc COMPOP` between the `%nonassoc NOT` and `%left PLUS MINUS` lines. This should make arithmetic happen first, but comparison right after that, before logical operators are taken into account. So something like `3 < 4 and 1 < 2` would behave properly.\r\n- Add `| expr COMPOP expr    { CompS ($2, $1, $3) }` as a case in the `expr` rule in `parser.mly`.\r\n- In `lexer.mll`, add a new binding `let comp = \">\" | \">=\" | \"<\" | \"<=\"`, then further down a new rule `| comp as s   { COMPOP s }`. This recognizes the above four operators and stores the match as part of the `COMPOP` token.\r\n\r\nAfter you recompile everything, you should be ready to test the interpreter directly.\r\n\r\n### Equality\r\n\r\nEquality is surprisingly a more difficult concept than most. Programmers expect to be able to compare for equality any two expressions. This means that you must handle all value possibilities, both `Num` and `Bool` as well as other values we add in the future. Every time we add a new kind of value (pairs, lists etc) we will need to update our equality function to account for them. We will use `==` to denote equality.\r\n\r\nTesting for non-equality, often denoted by `!=`, will be implemented simply as desugaring via `NotS` and equality. So in the core language we will need to only worry about equality.\r\n\r\n- Add a new `exprC` type variant `EqC` that takes as input two expressions.\r\n- Write a new helper function `eqEval` of type `value -> value -> value` that takes as input two values and returns if those values are equal as a `Bool` value. It should do so as follows: If they are both `Num`s, it should compare the corresponding floats stored there. If they are both `Bool`s it should compare the corresponding booleans stored there. Otherwise it should return `Bool false`. You will need to update this function in the future when we create new kinds of values.\r\n- Add a new case in `interp` to handle the `EqC` by evaluating each operand in turn then calling `eqEval` to compare them.\r\n- Add two `exprC` variants: a `EqS` to mirror `EqC` and a `NeqS` and adjust `desugar` accordingly. For `NeqS` you should convert it into a combination of `NotS` and `EqS`, then desugar that.\r\n\r\nParser/Lexer changes:\r\n\r\n- Add two new tokens `EQ` and `NEQ` to `parser.mly`.\r\n- For precedence, add `%nonassoc EQ NEQ` between `%left OR AND` and `%nonassoc NOT`. Make sure you understand the consequences of this choice.\r\n- Add two more rules for `expr` in `parser.mly` to handle `expr EQ expr` and `expr NEQ expr`.\r\n- Add to the rules at the bottom of `lexer.mll` cases for turning `\"==\"` to `EQ` and `\"!=\"` to `NEQ`.\r\n\r\nYou should be ready to use equality tests now.\r\n","creator":{"login":"gitslaton","id":10524611,"avatar_url":"https://avatars.githubusercontent.com/u/10524611?v=3","gravatar_id":"","url":"https://api.github.com/users/gitslaton","html_url":"https://github.com/gitslaton","followers_url":"https://api.github.com/users/gitslaton/followers","following_url":"https://api.github.com/users/gitslaton/following{/other_user}","gists_url":"https://api.github.com/users/gitslaton/gists{/gist_id}","starred_url":"https://api.github.com/users/gitslaton/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gitslaton/subscriptions","organizations_url":"https://api.github.com/users/gitslaton/orgs","repos_url":"https://api.github.com/users/gitslaton/repos","events_url":"https://api.github.com/users/gitslaton/events{/privacy}","received_events_url":"https://api.github.com/users/gitslaton/received_events","type":"User","site_admin":false},"open_issues":2,"closed_issues":7,"state":"open","created_at":"2016-03-15T04:22:14Z","updated_at":"2016-03-15T23:41:12Z","due_on":null,"closed_at":null},"comments":0,"created_at":"2016-03-15T11:35:36Z","updated_at":"2016-03-15T23:41:12Z","closed_at":"2016-03-15T23:41:12Z","body":""}}