CSE 341 -- Assignment 7 Information and Hints -- Miranda Project

Here is some more information, and hints and suggestions for Assignment 7.

You may work in pairs on this project.

You should handle the binary minus operator -, but you don't need to handle negative constants if you don't want to. In other words, these expressions are OK:

(- x 3)
(+ x (- 0 3))

but you don't need to parse these:

(+ x -1)
(+ x (- 1))

You don't need to handle incorrect expressions. (If you do want to add some error handling, though, see the function error.)

Include simplication rules for minus as well as plus and times.

Hints

Look through the stanard environment for Miranda (linked from the online manual), both as examples of Miranda functions done in good style and for useful built-in functions.

In writing your script, include type declarations. These are good as machine-checked documentation, and will also result in much more useful error messages.

The assignment suggested a collection of user defined types and helper functions. Here is more information on these.

Tokens represent variables, constants, left paren, right paren, and the operators plus, minus, and times.

string == [char]
token ::= VariableToken string | ConstantToken num | LeftParen ...

|| tokens is a function to break up the input string into tokens
tokens :: string -> [token]

You can tell what kind of token is coming by looking at the first character (a digit signifies a number, a variable a VariableToken, etc.)

The type expr represents an expression

expr ::= Variable [char] | Plus expr expr | ...

For example, the expression (+ x (+ y z)) would be represented as

Plus (Variable "x") (Plus (Variable "y") (Variable "z"))

An alternative way to represent expressions (which will result in a shorter script) is to define another type operator, and define expr as

expr ::= Variable [char] | Binary operator expr expr | ...

The function parse takes a list of tokens and converts it to an expression. parse can decide what kind of expression to produce based on the first token. If the token is a VariableToken, then the expression will be a Variable (note that these are two different types). If the token is a left parenthesis, then the expression will be a plus or times.

To parse a plus or minus or times expression, you will need to get the operator (+ - or *), then call parse recursively to parse the two arguments.

There is a subtle issue here. In a parser written in an imperative language, there would probably be a variable nextToken that holds the next token to be processed. The parser would keep calling a procedure getToken to get the next token from the input and store it in the variable nextToken. We can't do this in a purely functional language. However, the parse function must still somehow parse an expression from the list of tokens, and then return the remaining part of the list of tokens so that it can be passed to another call to parse.

One way to do this is to have parse return a pair, consisting of an expression and a list of the remaining unparsed tokens:

parse :: [tokens] -> (expr,[tokens])

For example, suppose we are in the middle of parsing

(+ (+ w x) (+ y z))

parse has been called recursively to parse an expression. Here is the call:

parse [LeftParen, PlusSign, VariableToken "w", 
       VariableToken "x", RightParen, LeftParen, PlusSign, 
       VariableToken "y", VariableToken "z", RightParen, RightParen]

This would return

(Plus (Variable "w") (Variable "x") , 
[LeftParen, PlusSign, VariableToken "y", VariableToken "z", 
   RightParen, RightParen])

This is a pair consisting of the expression

Plus (Variable "w") (Variable "x")

and the list of remaining tokens.

Here is code for one of the cases:

parse (LeftParen : PlusToken : t1) = (Plus arg1 arg2 , t3)
                                     where (arg1,t2) = parse t1
                                     (arg2, RightParen : t3) = parse t2

This case for the parse function matches a list of tokens corresponding to a left paren, followed by a plus sign. We return a Plus expression. To do this, we parse the first argument (arg1) beginning with the tokens at t1. At the same time we compute arg1, t2 is bound to the list of tokens following those for arg1. We then parse arg2 from this list of tokens. The pattern checks that the next token is a right paren, and bind t3 to the remaining tokens after the right paren.

The types of the remaining suggested functions are straightforward:

|| the second argument for basic_deriv is of type expression, but in use
|| should always be a variable, and not an expression
basic_deriv :: expr -> expr -> expr

simplify :: expr -> expr

expr_to_string :: expr -> string