tag:blogger.com,1999:blog-5621024.post114790400521830291..comments2024-01-09T03:52:43.027-08:00Comments on The Abstract Factory: SML hacking tip: Turn off polyEqual warningsKeunwoo Lee (Cog)http://www.blogger.com/profile/05577836853536292311noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-5621024.post-35949473578081145262011-06-17T20:07:49.299-07:002011-06-17T20:07:49.299-07:00Thanks! And you're right about the warning st...Thanks! And you're right about the warning status.Norman Ramseyhttp://www.cs.tufts.edu/~nr/noreply@blogger.comtag:blogger.com,1999:blog-5621024.post-6267114779136111062007-11-18T18:47:00.000-08:002007-11-18T18:47:00.000-08:00Many thanks for posting this! I'm just learning M...Many thanks for posting this! I'm just learning ML and wasn't sure if the polyEqual warning was critical.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5621024.post-28009012670344456902007-01-17T16:26:00.000-08:002007-01-17T16:26:00.000-08:00Appreciate you posting this; ML idiosyncracies can...Appreciate you posting this; ML idiosyncracies can be obnoxious and this post is a big help for beginners (it can be a scary message to get :).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5621024.post-9526962143150781032007-01-06T10:02:00.000-08:002007-01-06T10:02:00.000-08:00Short answer:
Unlike most other ML operations, po...Short answer:<br /><br />Unlike most other ML operations, polymorphic equality requires consultation of the runtime type of an object. So, you basically have to look up the complete type, and then invoke a general heap-walking function to compare the two object structures, consulting the type of every subcomponent as you recur.<br /><br />Long answer:<br /><br />ML's carefully designed so that most operations can be applied either to anything (i.e., they are universally polymorphic) or to exactly one type (i.e., they are monomorphic). Given a sound type system, neither universally polymorphic nor monomorphic operations require run-time type information. Therefore, ML doesn't need to attach a type header word to every object in memory.<br /><br />(Note that this contrasts with the standard implementation strategy for most object-oriented or dynamically typed languages. In an object-oriented language, you need to look up an object's type at runtime to do dynamic dispatch. In a dynamically typed language, you need to look up the type to do dynamic type checking. In both cases, typical implementations attach a header word to every object.)<br /><br />To use polymorphic equality, you have to get a complete type descriptor somehow to the site of the equality comparison. I don't remember how SML/NJ does this, but the obvious choices are (1) add type headers to every object or (2) when calling a function over eqtypes, pass a descriptor for each eqtype variable on the stack. (1) is pretty gross, so I assume real ML implementations do (2) (which, not coincidentally, resembles a really stunted version of how Haskell implements type classes).<br /><br />From the programmer's perspective, the alternative to using an eqtype ''a is to use a plain polymorphic type 'a and pass an explicit ('a * 'a) -> bool function. This may seem no better than ''a --- either way you're still passing something on the stack, and invoking a function that may need to inspect a large heap structure. However, the programmer may be able to stash the function somewhere so that it doesn't have to be passed on every call. Also, and probably more importantly, the programmer-provided equality function knows the fully instantiated type of the objects being compared, and was presumably compiled monomorphically, so it doesn't need to look up the types of subcomponents as it recurs down the object structures.<br /><br />In principle, a fancy ML compiler could neutralize the overhead of polymorphic equality through aggressive optimizations --- for example, it could generate specialized equality functions at polymorphic eqtype instantiation sites. I think SML/NJ doesn't bother.Keunwoo Lee (Cog)https://www.blogger.com/profile/05577836853536292311noreply@blogger.comtag:blogger.com,1999:blog-5621024.post-33923738695385496042006-11-04T13:30:00.000-08:002006-11-04T13:30:00.000-08:00use of polymorphic equality is purely a performanc...<i>use of polymorphic equality is purely a performance problem, not a probable logic error</i><br /><br />Interesting. Can you explain this a little bit more? Why does use of polymorphic equality slow things down?Nelshttps://www.blogger.com/profile/07085287093689227850noreply@blogger.comtag:blogger.com,1999:blog-5621024.post-1153770806677119062006-07-24T12:53:00.000-07:002006-07-24T12:53:00.000-07:00Thanks for the Google-food! You just saved me sign...Thanks for the Google-food! You just saved me significant time.Anonymousnoreply@blogger.com