Is my compilers assignment irrational? In our assignment we are given a grammar (called minipython) and we are asked to implement some phases of compilation (parsing, some semantic analysis).
One of the requirements is to be able to check for types in an arithmetic expression (arithmetic expressions are only defined for integers). For example in the below code:
def add(x,y):
   return &quot;hello world&quot;
print add(2,1)+ 2

We are expected to detect such errors. However the language,like python, seems dynamic to me. Meaning that the return type of a function depends on the runtime (for example the function def f(x): return x
When we showed the instructor the code below:
a=0
b=1
if b&gt;2:
    a = 'a'
c = a + b

The instructor told us we are supposed to detect such errors (in the arithmetic expression one type is string, the other is a number). And also he said we should run the code tracking the value of each variable.
Well... i haven't heard of a compiler that runs the program in order to detect errors. I mean that would be impossible if the language is Turing-complete right? (I'm not sure if minipython is though)
One of my classmates is attempting to do this by setting a limit on the times he remains on any loop or setting a max recursion depth. But I don't think this is right , i mean what compiler does this? I don't know what magic people do in static analysis tools but i don't expect that anyone runs the code in order to check type errors... unit tests are for that.
My question: Are my assignment's tasks irrational?? Can this language have a totally inferred type system? I'm really confused and I don't have much experience with compilers. Please correct me at any point if I have said anything that is wrong
I can also provide minipython's BNF if its necessary.
Sorry, in complete generality this is an undecidable problem. Pick your favorite undecidable problem $P$ and an instance $a$, and write e.g.:
def value(a):
     if P(a):
         1
      else:
         &quot;Hello, world!&quot;

print(41 + value(a))

Under the (conservative!) assumption that all execution paths are possible, you see that the above is badly formed (value returns an integer or a string). That restriction is doable, and not too hard either:   Do a postorder traversal of your AST, recording the possible types of each node. If any node could have conflicting types, flag a (possible) error.