Stream: cql
Topic: Type Checking order
Justin Pombrio (Nov 05 2019 at 15:25):
I have a question about how type checking should be implemented in CQL.
Defines and functions can appear in any order. But since they can depend on each other, I'm not sure what order they should be type checked in. For example:
define function isSmall(n Integer): lessThanOne(n) define function lessThanOne(n Integer): n < 1
It seems to me that it's important to type check lessThanOne _first_, to figure out that it returns a boolean. (Since the return type isn't written in the program.) And then when type checking isSmall, you can see that lessThanOne(n) will return a boolean.
How can you determine what order to type check functions in?
And if they're recursive, like if f calls g, and g calls f, how do you deal with that? Because when functions are recursive, it seems to me that there's no good order that works.
Chris Moesel (Nov 05 2019 at 16:26):
Is this question in the context of processing/compiling the CQL syntax directly? If you're using the open source CQL-to-ELM translator, there is a flag you can set to have the outputted ELM include the return type for each expression. Of course, you could also look at the CQL-to-ELM translator to see how it approaches type checking. I think @Bryn Rhodes implemented most of the type checking there, so he may be able to provide a high-level overview of the approach.
Justin Pombrio (Nov 05 2019 at 16:29):
It's in the context of implementing a new CQL-to-ELM translator.
Justin Pombrio (Nov 05 2019 at 21:25):
Oh, I missed this part of the spec! "Functions can be defined that reference other functions anywhere within any library and to any degree of nesting, so long as the reference does not result in a circular reference." So recursion simply isn't allowed. That answers my question.
Grahame Grieve (Nov 05 2019 at 21:26):
I would think that there's valid uses for recursion in the CQL space. Certainly FHIR resources have a few structures where recursion is a natural fit...
Justin Pombrio (Nov 05 2019 at 21:43):
It would make type checking difficult. In most statically typed languages, function return types are required for exactly this reason.
In Haskell they're not required. But to support this, it uses type inference and unification, and you can end up with a function's return type being an ununified type variable. Adding type variables would be a pretty big addition to CQL's type system.
I don't know of any easy (and sound) way to support type-checking recursive functions when their return types can be omitted.
Grahame Grieve (Nov 05 2019 at 21:57):
run time resolution....? (javascript?)
Bryn Rhodes (Nov 06 2019 at 18:47):
There are valid uses for recursion, but it is currently explicitly disallowed. One approach would be to allow it generally (and require the explicit declaration of return types where recursion was used in a function declaration that prevented inference of the type). Another approach would be to introduce a recursive construct (like CTEs in T-SQL).
Justin Pombrio (Nov 06 2019 at 22:36):
@Bryn Rhodes That makes sense.
Last updated: Apr 12 2022 at 19:14 UTC
