dont forget to test recursive function definitions....

[edwadli]

The type checker might run forever!!!!!!!!!!

[kevin1]

A cheap way to fix this: add an exception handler for the stack overflow exception

Sent from my Apple Watch

On Nov 22, 2015, at 2:57 AM, Edward Li [email protected] wrote:

The type checker might run forever!!!!!!!!!!

—
Reply to this email directly or view it on GitHub.

[kevin1]

Also did you mean recursive type definitions? Not sure how we can have recursive function-definition in our language

[edwadli]

fun Hello x = Hello x

[edwadli]

not fun at all

[kevin1]

There's a similar challenge w/ C++ templates: since they are turing complete, the compiler would have to solve the halting problem. Instead clang has a maximum template instantiation depth of 256 to work around it.

code via http://stackoverflow.com/q/6079603/1489823

Another interesting thing. The program below (which is equivalent of your NH code above) gives the error "no matching function for call to hello."

It think it's because C++ can't overload functions based on return type.

#include <iostream>

template <typename TRet, typename TArg>
TRet hello(TArg x) {
    return hello(x);
}

int main(int argc, const char * argv[]) {
    hello(5);
    return 0;
}

However, by making the call type and the return type the same, the program now compiles and we get a stack overflow, as expected.

template <typename T>
T hello(T x) {
    return hello(x);
}

[edwadli]

i believe the current implementation of type checking for functions runs DFS. We will have to change that to BFS on all exprs that have multiple exprs inside. Otherwise, if you write a recursive function with the base case after the recursion, our type checker will fail to halt, and produce the wrong answer if we just stop it at some arbitrary depth

[kevin1]

Ah was just about to say that but got pulled away from computer for a minute

We can check if the function has a return other than the recursive call, which can distinguish between these two cases:

// Yes:
fun Hello x = (if x == 1 then x else Hello x - 1)
// No:
fun Hello x = Hello x

Eventually we'll find that our compiler accidentally includes a static analyzer :)

[edwadli]

i can smell another dependency graph coming

[edwadli]

instead of checking for cycles we'd check for leaf nodes

[edwadli]

i think that's sufficient?

[kevin1]

Can you clarify? The nodes of this graph are function calls?

[edwadli]

yeah each function is a node in the graph, and the edges are calls to other functions

[kevin1]

Yeah, I think that works. One caveat is you can only ignore a call (edge) if the destination and source's arg types are the same.

[edwadli]

Some things to watch out for
binop -> both branches need a leaf
block -> sequentially check each expr for a leaf
funapply -> every arg expr needs a leaf

[kevin1]

why binop?

fun Hello x = ( 
  if x == 0 then 0 else ( 1 + Hello (x-1) )
)

[kevin1]

^ I think in that case, you'd parse the if-else. Type of if is int, type of else is also int because we already know Hello int returns int.

[edwadli]

yeah conditional -> bool expr needs leaf; one of the two expr needs leaf

[kevin1]

Right but I don't think both children of the binop (+) need leaves

[edwadli]

Hello x = 1 + Hello x

[kevin1]

That case is thrown out because the function doesn't have a base case. I think the binop itself is not the problem.

[edwadli]

in the example u gave the conditional only requires on of the two expr to be valid (which would be the 'then' case in that example)

[edwadli]

i think checking for leaves is the same thing as checking for base cases

[edwadli]

i think base cases are when u hit something with definite type (literal), and every branch of each expr needs to have a leaf, except for conditionals, in which the bool expr needs a leaf, and only one of the two exprs needs a leaf.

[edwadli]

I think i was wrong about the BFS, the DFS is fine but we need an extra halting condition so we don't get stuck in a cycle; but we might have to go back and figure out the types of those calls after we find the base cases in other branches...

[kevin1]

OK, let's hold off on thinking about this until we actually implement it. I think we are both nerd-sniping oureslves

[edwadli]

closed by #104