Interpreter does not distinguish the run-time type from the static type of functions and closures

[jurgenvinju]

Describe the bug

This is a continuation of issue #1467;

When a generic function returns a (partially instantiated) function value, the interpreter does not properly instantiate the run-time type of the given closure. (For example when applying the curry function to itself). The result that the interpreter both reports erroneous static types, as well as fails to instantiate the dynamic type of the returned closure (it remains carrying a renamed static type instead).

The root cause is a very basic (and wrong) assumption in the code of the interpreter: for functions (closures and/or generic or otherwise) the static type is equal to their dynamic type. This is because each function instance extends Result<IValue> (which tuples a static type with a dynamic value), as well as implements IFunction and ICalleableValue which are dynamic value implementations. Both Result and IValue implement getType() but their intended semantics is quite different. Fixing this entails a significant rewrite of the function calling semantics in the interpreter.

To Reproduce

rascal>&S(&U) c(&S(&T, &U) f, &T t) = &S (&U u) { return f(t,u); };
rascal>int add(int i, int j) = i + j;
rascal>f = c(c, add);

reports:

rascal>c(c, add)
&S:2f6f1baa-821e-43c2-8591-77e7cec441ae (&U:70a2b6f2-9adc-422a-bd44-4529e7ce9420) (&T:4a61b9aa-89e6-4ccf-b75e-3fcd0ee7537f): function(|prompt:///|(31,28,<1,31>,<1,59>))

here we see too many uninstantiated and renamed type variables.

[jurgenvinju]

A fix to this issue would entail a separation of the Result<?> from the ICalleable and IFunction interfaces in the interpreter for the classes AbstractFunction, NamedFunction, RascalFunction, JavaMethod and anonymous implementations of ICalleableValue, namely that the first four would focus explicitly on the run-time semantics of functions and a new class FunctionResult would (a) couple these dynamic function values with a static type and (b) execute static type-checking rules for function instantiation, combination and application, while the four mentioned classes would be excused from having to do any more static typing checks.

Currently the static and dynamic perspective on Rascal are completely tangled in these four classes and it will be quite a challenge to extract the two perspectives while maintaining functional correctness w.r.t. the current test set.

Separating the static from the dynamic semantics for functions will allow us to implement both perspectives correctly, and especially the hygiene (non leakage) of recursive function application and higher-order self-application can be fixed if function instances will be allowed to have different (more concrete) run-time types while their actual code, declaration scope and variable bindings remain the same.

I expect this to be a major destabilizing operation for the current interpreter. Since this interpreter is also used to bootstrap the compiler which is nearly finished, there is the question: "is this really the right time?" to fix this enormous bug.

[jurgenvinju]

So there is IValue.getType() (a dynamic type) and Result.getType() (a static type) which are conflated in all implementations of function values in the interpreter.

• I am renaming Result.getType to Result.getStaticType, and adding getType implementations which forward to getStaticType in all function implementations
• This makes the problem explicit and visible and should be a semantics preserving refactoring
• After this we may decide what (or if) to fix the issue(s)

[jurgenvinju]

Note that simply implementing the new IValue.getType for all function classes will not work. A lot of other related things will have to be fixed.

The initial new functionality would be is that function instances must receive their "instantiated" run-time type at construction time. After that, there are consequences:

• When functions are looked up from declaration environments or constructed (lamda's, closures), new type computations must be written that create these run-time types, and the instances that come from declaration environments must be cloned (or wrapped) such that their IValue.getType can return the concrete type.
• When functions are called, their dynamic types must have influence on generic type parameter bindings in their (static) function headers. This is also new. Since we will not instantiate AST nodes at function construction time, these "construction-time" bindings must be re-constructed at function call-time.
• When functions are called the dynamic types of their return values must be informed by the previous bindings. This is also new.

[jurgenvinju]

having separated the dynamic types from the static types and also separated tuple type instantiation from function type instantiation has fixed many issues on the current unstable master. However, self-application of curry is still broken. The quest has lead to the match method of ParameterType in vallang; I'm recording my current findings here, for later reference or contradiction:

@Override
	public boolean match(Type matched, Map<Type, Type> bindings) throws FactTypeUseException {
		if (!super.match(matched, bindings)) {
			return false;
		}

		Type earlier = bindings.get(this);
		
		if (earlier != null) {
			// HERE WE HAVE A PROBLEM. Let's see how to describe this...
			// If the earlier binding is an open type (carrying, hopefully renamed, but open type parameters),
			// Then the lub between this type parameter and the open type is bound to reduce to a lub
			// between the bound and the (structured type). 
			// This results in serious information loss. For example a the matched type could be a function
			// type `int (int)` while the `earlier` result is `&U1 (&T2)`. The matching should
			// result in a new binding for the type parameters &U1->int and &T2->int instead of producing
			// `value`, as the code below is doing now. 
			// This bug is causing self application of the id function and curry to fail to resolve to
			// the right types for the values they are returning. 
			Type lub = earlier.lub(matched);
			if (!lub.isSubtypeOf(getBound())) {
				return false;
			}

			bindings.put(this, lub);
			
			// propagate what we've learned about this parametertype
			// to possible open type parameters in its bound
			getBound().match(matched, bindings);
		}
		else {
			bindings.put(this, matched);
			getBound().match(matched, bindings);
		}

		return true;
	}

[jurgenvinju]

resolving usethesource/vallang#99 improved the situation significantly:

rascal>&S(&U) curry(&S(&T, &U) f, &T t) = &S (&U u) { return f(t, u); };
&S (&U) (&S (&T, &U), &T): function(|prompt:///|(0,65,<1,0>,<1,65>))
rascal>int add (int i, int j) = i + j;
int (int, int): function(|prompt:///|(0,31,<1,0>,<1,31>))
rascal>curry(add, 1)
int (int): function(|prompt:///|(35,29,<1,35>,<1,64>))
rascal>curry(add, 1)(2)
int: 3
rascal>curry(curry, add)
int (int) (int): function(|prompt:///|(35,29,<1,35>,<1,64>))
rascal>curry(curry, add)(1)
&S (&U): function(|prompt:///|(35,29,<1,35>,<1,64>))
rascal>curry(curry, add)(1)(2)
&S: 3

but we're not done yet. As we see uninstantiated types in the final two commands. There is some instantiation missing in the interpreter's code?

[jurgenvinju]

And, the new semantics of vallang after fixing usethesource/vallang#99 results in many failing tests in Rascal: https://ci.usethesource.io/job/usethesource/job/rascal/job/master/1718/#showFailuresLink

[jurgenvinju]

all existing tests are working again after fixes in both vallang and rascal. but we're still stuck here:

rascal>curry(curry, add)(1)
&S (&U): function(|prompt:///|(35,29,<1,35>,<1,64>))
rascal>curry(curry, add)(1)(2)
&S: 3

[jurgenvinju]

Almost there!

rascal>&S(&U) curry(&S(&T, &U) f, &T t) = &S (&U u) { return f(t, u); };
&S (&U) (&S (&T, &U), &T): function(|prompt:///|(0,65,<1,0>,<1,65>))
rascal>int add(int i, int j) = i + j;
int (int, int): function(|prompt:///|(0,30,<1,0>,<1,30>))
rascal>curry(curry, add)(1)(2)
int: 3
rascal>curry(curry, add)(1)
int (int): function(|prompt:///|(35,29,<1,35>,<1,64>))

Some test in vallang is failing; have to fix before calling it a day.

[jurgenvinju]

thanks to @rodinaarssen for the help