What does it mean for a type system to be “complete”? Type soundness means that well-typed programs do not “get stuck”, but it is not obvious at all (at least to me) what it means for a type system to be complete, formally speaking.
If you just mean that a program has certain properties (like performing IO) that are not expressed in its type, then I can see what you mean. But even in Haskell, some properties like “this function might fail to terminate or throw an exception” are not expressed in the type (although you can use monads for those things in languages where all functions terminate by default). There are no distinctions between a function that performs network accesses and one that does not, or functions that never return odd numbers, etc. There are infinitely many program properties that you can come up with which are not expressible in Haskell types.
Even dependently typed languages with very expressive type systems cannot capture all possible program properties due to logical incompleteness results.
A type system is complete when every error-free program is well-typed. This is, afaik, seldom the case.
I was using the term more informally. In fact it is the operational semantics of your hypothetical language that is not complete in the sense that you will have a hard time putting it into a form that allows you to do anything meaningful (e.g. proof absence of certain errors) with it.
Interestingly, you can define such a language with side effects (think ML), by actually pulling the state monad into your meta-level (for instance by turning your reduction relation into an instance of a state monad).
If you just mean that a program has certain properties (like performing IO) that are not expressed in its type, then I can see what you mean. But even in Haskell, some properties like “this function might fail to terminate or throw an exception” are not expressed in the type (although you can use monads for those things in languages where all functions terminate by default). There are no distinctions between a function that performs network accesses and one that does not, or functions that never return odd numbers, etc. There are infinitely many program properties that you can come up with which are not expressible in Haskell types.
Even dependently typed languages with very expressive type systems cannot capture all possible program properties due to logical incompleteness results.