1
$\begingroup$

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 "hello world"
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>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.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ The first thing to do: ask the instructor whether your language is truly what you think (e.g. dynamic, arbitrary types can be passed as parameters in different calls, etc.). You should expect to get a reply: what would be truly unreasonable is to implement semantic analysis without language specification. $\endgroup$
    – user114966
    Commented Jan 14, 2021 at 16:14
  • $\begingroup$ Hey, thanks for the reply. We don't really have a concrete specification about the semantics. But we have been informed that is is dynamic, there is not constraint about the input type of a function, unless it is used in an arithmetic expression in which case we must infer the expected type. $\endgroup$
    – Nikolaos Smyrnioudis
    Commented Jan 14, 2021 at 16:31
  • 1
    $\begingroup$ What about types? If possible types are fixed, you can perform static analysis. Essentially, you need to check whether in a + b ,a and b have the same type, and, since the number of types is fixed, you can compute this information (with a usual assumption that every execution path is possible). $\endgroup$
    – user114966
    Commented Jan 14, 2021 at 16:51
  • $\begingroup$ Yes, the types are fixed. The problem with a+b is that the type of b ,for example, can depend on the runtime value of a variable (say the condition in a previous if statement). I didn't quite understand what you are suggesting though with the execution paths. $\endgroup$
    – Nikolaos Smyrnioudis
    Commented Jan 14, 2021 at 17:01
  • $\begingroup$ Consider two examples: pastebin.com/NNE3RTUX. What I mean by the last sentence is that we assume that all execution paths (2 paths in the first example (since there is only one "if") and 4 paths (since there are 2 "if"s)) are possible. In the first example we can verify that either a and b are both ints, or they are both strings. In the second example, we won't be able to verify it even though the condition is the same (since our 4 paths cover all possible cases for types of a and b). I believe such relaxation is typical in static analysis. $\endgroup$
    – user114966
    Commented Jan 14, 2021 at 17:13

1 Answer 1

Reset to default
1
$\begingroup$

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:
         "Hello, world!"

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.