Type inference engine

Your program will construct a type environment, and then perform unifications in that type environment, until either the program ends, or a unification fails. For each unification, you will be outputting the most generic type that unifies the two inputs (not the set of substitutions that would unify the type).

That means, as you learn specific information about a generic type, you must keep track of how that information is bound.

For instance, you may be first asked to unify `a and [`b]. After that unification, our type environment must remember that `a should be substituted with [`b]. So, if the next query is to unify `a and `c, the most specific generic type will again be [`b].

1. The grammar for the type language is as follows:


PRIMITIVE_TYPE ::= ‘int’ | ‘float’ | ‘long’ | ‘string’;

TYPEVAR ::= ‘`’ VARNAME; // Note, the character is a backwards apostrophe!

VARNAME ::= [a-zA-Z][a-zA-Z0-9]*; // Initial letter, then can have numbers

FUNCTYPE ::= ‘(‘ ARGLIST ‘)’ -> TYPE | ‘(‘ ‘)’ -> TYPE;


LISTTYPE ::= ‘[‘ TYPE ‘]’;

2. A single input consists of a pair of types on a single line, separated by an ampersand:


NEWLINE ::= ‘\n’;

3. White space (tabs and spaces) cannot occur in the middle of a TYPEVAR or PRIMITIVE_TYPE, but can be added anywhere else. This is true for both input and output.

4. When a UNIFICAITON_QUERY does not match the above grammar, your program shall output only “ERR” followed by a newline, and then exit.

5. Valid input to your program follows this grammar:



6. After you read in each unification query, you must output the correct result, which should either be: a) The most general unifier, if it exists. It should follow the type grammar above.

b) If no most general unifier exists, output: “BOTTOM” (all caps) on a line by itself, and then exit.

7. When the program input consists of a “QUIT” command instead of a UNIFICATION_QUERY, your program should exit without reading further input or producing further output.

8. When your program outputs either “ERR” or “BOTTOM”, you must not read any additional input, or produce any additional output.

9. All input is case sensitive. For instance, `a and `A represent different type variables.

10. If unification would create a recursive type, you must output “BOTTOM”.

11. Different primitive types cannot unify with each other.

12. When you unify two type variables, it does not matter which name you use as the proper name. For instance, if you’re asked to unify `a and `b, either `a or `b are acceptable as an output.

2. Test Cases

Below are four sample test cases for you, which I will use in my testing. Typically, I use anywhere from 20-50 test cases, and will definitely use these three. I strongly recommend you create your own test harness and come up with a large number of test cases to help you get the best possible grade.

For test cases, what one would type on the command line is BLACK, input is in GREEN, and output is in BLUE.

Case 1


(int, int) -> `a & (`a, int) -> int

(int, int)->int


Case 2


[`a] & int


Case 3


(int, int) & (`a, int)


Case 4


(`a, `b) -> int & ([`b], `c) -> `d

([`c], `c) -> int

`z & int


`a & int


Note that, for the first output, it’s equally acceptable to output:

([`b], `b) -> int

For the third unification in this case, it should fail because `a is already bound to a list type (specifically, a list that contains items of type `c).

This project needs to be done in 7 days at the maximum.

Habilidades: Golang

Ver mais: what is recursive, types of use cases, type of use case, true green, recommend letter, quit letter, pair line, follow up letter sample, exit letter, type 7, re-type, Re type, harness, proper letter, match engine, type type, can type letter, testing use cases, letter type, search engine type website, possible letter list, language recursive, travian type game engine, err, command line engine

Acerca do Empregador:
( 0 comentários ) United States

ID do Projeto: #6829449

3 freelancers are bidding on average $311 for this job


Hello, I am certain I can do this assignment since I already did something exactly like this for my university course (it was in a different language - Standard ML, but the algorithm was the same). It was run on man Mais

$555 USD in 3 dias
(0 Comentários)

I can code this in golang and give you the solution with around 20 test cases in around 2-4 days. The output will match for the given test cases and should match for any other test case as well. I have thought out Mais

$155 USD in 4 dias
(0 Comentários)

Hello, I have experince in Go Send me message need to discuss

$222 USD in 7 dias
(0 Comentários)