Connection Status:
Competition Arena > MonomorphicTyper

MonomorphicTyper

SRM 286 · 2006-01-30 · by ged

SRM 286 · 2006-01-30 · by ged · Recursion, String Parsing
Class Name: MonomorphicTyper
Return Type: String
Method Name: infer
Arg Types: (string, vector<string>)
Problem Statement

Problem Statement

Given an expression, we must determine its type. Expressions are formatted as follows:

  • <expression> ::= <constant> | <function>(<args>)
  • <args> ::= <expression> | <expression>,<args>
  • <constant> ::= <identifier>
  • <function> ::= <identifier>
  • <identifier> ::= between 1 and 10 letters ('a'-'z', 'A'-'Z'), inclusive

Some examples of valid expressions are "x", "upper(x)", "ord(upper(x))", "succ(succ)", "fst(x,x)".

To aid us in determining the type of an expression, we are given a list of type definitions. Each element of the String[] definitions is formatted as follows:

  • <definition> ::= <type_expression>:<type_name>
  • <type_expression> ::= <constant> | <function>(<type_args>)
  • <type_args> ::= <type_name> | <type_name>,<type_args>
  • <type_name> ::= <identifier>

For example:

  • "x:Char" means that the constant "x" has type "Char".
  • "succ(Int):Int" means that the function named "succ" that takes a parameter of type "Int" has type "Int".
  • "upper(Char):Char" means that the function named "upper" that takes a parameter of type "Char" has type "Char".
  • "ord(Char):Int" means that the function named "ord" that takes a parameter of type "Char" has type "Int".
  • "fst(Int,Int):Int" means that the function named "fst" that takes two parameters, both of type "Int", has type "Int".

In general, "<constant>:<type_name>" means that the constant named <constant> will have type <type_name>, and "<function>(<type_args>):<type_name>" means that the function named <function> will have type <type_name> if and only if its argument types match <type_args> exactly (the same number of arguments, with the types in the exact order given).

Using these example definitions, we can determine the types of three of the example expressions given above. "x" has type "Char", "upper(x)" has type "Char", and "ord(upper(x))" has type "Int". We cannot determine the type of "succ(succ)" because all we know is that a function named "succ" has type "Int" if its argument is of type "Int". In this case, we cannot determine the type of its argument. We cannot determine the type of "fst(x,x)" because all we know is that "fst" is of type "Int" if its two arguments are of type "Int". In this case, both arguments are of type "Char".

Given a String expression and a String[] definitions, return the type of expression. If the type cannot be determined using the given definitions, return an empty String ("").

Notes

  • All identifiers used are case-sensitive, i.e., "a" is not the same identifier as "A".

Constraints

  • expression will be a valid expression (as described in the problem statement).
  • expression will contain between 1 and 50 characters, inclusive.
  • definitions will contain between 0 and 20 elements, inclusive.
  • Each element of definitions will contain between 3 and 50 characters, inclusive.
  • Each element of definitions will be a valid definition (as described in the problem statement); they will contain no spaces.
  • definitions will contain no duplicate s and no duplicate s.
  • No in definitions will have the same name as a in definitions.
Examples
0)
"x"
{"x:Char"}
Returns: "Char"

definitions tells us that a constant with the name "x" has type "Char". expression is a constant named "x", so we know that its type is "Char".

1)
"upper(x)"
{"x:Char","upper(Char):Char"}
Returns: "Char"

expression is a function named "upper" that takes a constant named "x" as an argument. According to the definitions, a constant named "x" has type "Char", and a function named "upper" that takes an argument of type "Char" has type "Char". Therefore, we know that the type of "upper(x)" is "Char".

2)
"ord(upper(letter))"
{"ord(Char):Int","upper(Char):Char","letter:Char","Letter:String"}
Returns: "Int"

Here, the argument to the outer function "ord" is a function named "upper", which takes a constant named "letter" as its argument. Using the logic from the previous example, we can determine that "upper(letter)" has type "Char". This means that the function "ord" in our expression is given an argument of type "Char". We can therefore conclude that the expression has type "Int". Note also that "letter" and "Letter" are different constants (with different types).

3)
"id(id)"
{"id(Int):Int"}
Returns: ""

expression is a function named "id" that takes a constant named "id" as an argument. definitions contains no type definition for a constant named "id", so we cannot determine the type of the expression.

4)
"abcdefghij(abcdefghik(abcdefghil(abcdefghiJ)))"
{"abcdefghij(abcdefghik):abcdefghij","abcdefghik(abcdefghil):abcdefghik","abcdefghil(abcdefghiJ):abcdefghil","abcdefghiJ:abcdefghiJ"}
Returns: "abcdefghij"

long and similar indentifiers. typenames equal to constants.

5)
"f(f(c,c),f(f(f(c,c),f(c,c)),f(f(c,c),f(c,c))))"
{"f(C,C):C","c:C"}
Returns: "C"

just some recursion

6)
"ff(f(c,c),f(f(f(cc,c),f(c,c)),f(f(cc,c),ff(c,c))))"
{"f(C,C):C","ff(C,C):C","c:C","cc:C"}
Returns: "C"

exactly 50 chars long

7)
"f(unknown)"
{"f(A):B"}
Returns: ""

The constant passed as a parameter has no declared type.

8)
"fst(zero)"
{"fst(Int,Int):Int","zero:Int"}
Returns: ""

The definition of "fst" takes two "Int" parameters, but only one is provided in the expression.

9)
"Func(Int,Char,a)"
{"Int:Char", "Func(Char,Char,Int):Int", "Char:Char", "a:Int"}
Returns: "Int"

Function and constant names are not the same as type names. The expression is well-typed and has type "Int".

Submissions are judged against all 48 archived test cases, of which 10 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MonomorphicTyper with a public method string infer(string expression, vector<string> definitions) · 48 test cases · 2 s / 256 MB per case

Submitting as anonymous