In my theory of computation class last Spring my professor said in passing that a programming language cannot be both fully recursive and polymorphic. I didn't think much of it till now? What does it mean to be "fully" polymorphic and why does that mean you a language can't be "fully" recursive?

  • 7
    $\begingroup$ Out of context, I have no idea what he meant. There are many ways in which polymorphism and recursion can interact, but just saying “a language can't be both fully recursive and polymorphic” doesn't make sense. It could be part of something that makes sense, but you really need to give us more context. Even if you don't remember exactly, at least tell us what that lecture was about. Was this something about type checking? About decidable type checking? About type inference? About a particular kind of polymorphism? Recursion on values or on types? etc. $\endgroup$ – Gilles 'SO- stop being evil' Aug 2 '15 at 12:30
  • 4
    $\begingroup$ My guess would be that your professor said that you can't have decidable type inference for such a language (because the type inference problem isn't decidable). Does that sound right? $\endgroup$ – D.W. Aug 2 '15 at 14:47
  • 1
    $\begingroup$ You should try asking the professor what s/he meant! $\endgroup$ – David Richerby Aug 3 '15 at 13:14
  • 3
    $\begingroup$ Yes, my guess is that the professor was referring to polymorphic recursion for which type-checking is undecidable without type annotations. $\endgroup$ – cody Aug 3 '15 at 15:34
  • $\begingroup$ was this an undergrad or grad class? there is another (apparently other) widespread use of the word "polymorphism" in OOP that applies to TM complete applied languages eg Java etc. $\endgroup$ – vzn Aug 3 '15 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.