4 ms·

Scheme supports parametric polymorphism. This language adds only a type system, which supports parametric types needed to describe polymorphic code. (Parametr

Scheme supports parametric polymorphism. This language adds only a type system, which supports parametric types needed to describe polymorphic code. (Parametric polymorphism is a property of code, not of types. Specifically it is the ability for code to operate on data without knowing its ground type. The types which describe such things are called parametric types.) Aside, I've noticed a few other articles which seem to imply that type systems bring capability. Type systems never add capability to an untyped language; they always restrict capability.† That is what makes types useful! † Barring type-based dispatch, which is only dependent on type names; and run-time type introspection, which is wholly misguided.

vbit 12y ago
What is misguided - rtti or type-based dispatch - and why?
- colanderman 12y ago
  RTTI. Specifically the "runtime" part is misguided. Languages which permit runtime type inspection are much more difficult to compile efficiently, since type information must be kept at runtime. (There is no method to identify all cases when such information may be elided, and in any such language which permits "eval", there is no such way to elide RTTI.) Without loss of generality, any program using RTTI can be trivially transformed into one which doesn't use RTTI by tagging types, or by performing type-level computations at compile time. By performing one of these transformations, the compiler is free to generate much more efficient code. (Technically, RTTI includes runtime type-based dispatch; e.g. object-oriented method calls. I similarly avoid such code, preferring instead less-general mechanisms such as OCaml's functors or Haskell's type classes; both of which eliminate, or, in concert with existential types or first-class modules, make the overhead of RTTI explicit. Fortunately in languages such as Java where not everything is an object, the damage of RTTI is somewhat limited.)
bunderbunder 12y ago
Parametric polymorphism (i.e., generics) is a feature you find in statically typed languages, not dynamic languages like Scheme. For example, Scheme doesn't let you do a version of (lambda (a b) (+ a b)) that somehow ensures at compile time that a and a are the same type, or even if the + operation is defined for all possible arguments you could pass into a and b. If you want to make any restrictions on the types of arguments being passed in, you need to handle that by checking the arguments' types at run-time. Whereas with generics, you would have to have a type argument attached to each of the parameters. At compile time, those type arguments are evaluated and everything still has to successfully pass a static type check.
- colanderman 12y ago
  somehow ensures at compile time that a and a are the same type No, that's a feature of parameterized types. Here's a function that utilizes the parametric polymorphism present in Scheme: (lambda (f x) (f x)) Other examples include the built-in functions car, cdr, and cons. None of these functions are permitted in a language which does not support parametric polymorphism, such as C.
  - bunderbunder 12y ago
    Parameterized types are a part of parametric polymorphism. Scheme does allow a function like (lambda (f x) (f x)), but that's because it's dynamically typed. It can just compile a single version of the lambda that is capable of handling all possible input types - no polymorphism required, parametric or otherwise. Whereas in a language like ML with static typing the compiler would need to compile different polymorphic versions of the function for all the different combinations of types for f and x that are being used in the program.
    - colanderman 12y ago
      > It can just compile a single version of the lambda that is capable of handling all possible input types - no polymorphism required, parametric or otherwise. That's the very definition of parametric polymorphism. From http://en.wikipedia.org/wiki/Polymorphism_(computer_science) http://en.wikipedia.org/wiki/Polymorphism_(computer_science): If the code is written without mention of any specific type and thus can be used transparently with any number of new types, it is called parametric polymorphism. > Whereas in a language like ML with static typing the compiler would need to compile different polymorphic versions of the function for all the different combinations of types for f and x that are being used in the program. $ echo 'let f g x = g x' > test.ml $ ocamlopt -c test.ml $ objdump -d test.o 0000000000000000 <camlTest__f_1030>: 0: 48 89 c6 mov %rax,%rsi 3: 48 89 d8 mov %rbx,%rax 6: 48 8b 3e mov (%rsi),%rdi 9: 48 89 f3 mov %rsi,%rbx c: ff e7 jmpq *%rdi e: 66 90 xchg %ax,%ax Not so much. (Yes, type specialization is a strategy used by certain whole-program optimizers, such as the MLton compiler, but this is in no way tied to the language or the type system or lack thereof. Types exist whether you name and control them or not, just like tigers and asteroids do.)
gsg 12y ago
Not really. There are no parameters involved in what a Scheme programmer would call a polymorphic program - instead, such programs simply range over all scheme values. Because the values ranged over in such programs is known rather than being a parameter to the program, they are not polymorphic (in the ML sense).
- colanderman 12y ago
  such programs simply range over all scheme values That's the parametric part. From http://en.wikipedia.org/wiki/Polymorphism_(computer_science) http://en.wikipedia.org/wiki/Polymorphism_(computer_science): If the code is written without mention of any specific type and thus can be used transparently with any number of new types, it is called parametric polymorphism. This definition makes no mention of static typing.

vbit 12y ago

What is misguided - rtti or type-based dispatch - and why?

colanderman 12y ago
RTTI. Specifically the "runtime" part is misguided. Languages which permit runtime type inspection are much more difficult to compile efficiently, since type information must be kept at runtime. (There is no method to identify all cases when such information may be elided, and in any such language which permits "eval", there is no such way to elide RTTI.) Without loss of generality, any program using RTTI can be trivially transformed into one which doesn't use RTTI by tagging types, or by performing type-level computations at compile time. By performing one of these transformations, the compiler is free to generate much more efficient code. (Technically, RTTI includes runtime type-based dispatch; e.g. object-oriented method calls. I similarly avoid such code, preferring instead less-general mechanisms such as OCaml's functors or Haskell's type classes; both of which eliminate, or, in concert with existential types or first-class modules, make the overhead of RTTI explicit. Fortunately in languages such as Java where not everything is an object, the damage of RTTI is somewhat limited.)

bunderbunder 12y ago

Parametric polymorphism (i.e., generics) is a feature you find in statically typed languages, not dynamic languages like Scheme. For example, Scheme doesn't let you do a version of (lambda (a b) (+ a b)) that somehow ensures at compile time that a and a are the same type, or even if the + operation is defined for all possible arguments you could pass into a and b. If you want to make any restrictions on the types of arguments being passed in, you need to handle that by checking the arguments' types at run-time. Whereas with generics, you would have to have a type argument attached to each of the parameters. At compile time, those type arguments are evaluated and everything still has to successfully pass a static type check.

colanderman 12y ago
somehow ensures at compile time that a and a are the same type No, that's a feature of parameterized types. Here's a function that utilizes the parametric polymorphism present in Scheme: (lambda (f x) (f x)) Other examples include the built-in functions car, cdr, and cons. None of these functions are permitted in a language which does not support parametric polymorphism, such as C.
- bunderbunder 12y ago
  Parameterized types are a part of parametric polymorphism. Scheme does allow a function like (lambda (f x) (f x)), but that's because it's dynamically typed. It can just compile a single version of the lambda that is capable of handling all possible input types - no polymorphism required, parametric or otherwise. Whereas in a language like ML with static typing the compiler would need to compile different polymorphic versions of the function for all the different combinations of types for f and x that are being used in the program.
  - colanderman 12y ago
    > It can just compile a single version of the lambda that is capable of handling all possible input types - no polymorphism required, parametric or otherwise. That's the very definition of parametric polymorphism. From http://en.wikipedia.org/wiki/Polymorphism_(computer_science) http://en.wikipedia.org/wiki/Polymorphism_(computer_science): If the code is written without mention of any specific type and thus can be used transparently with any number of new types, it is called parametric polymorphism. > Whereas in a language like ML with static typing the compiler would need to compile different polymorphic versions of the function for all the different combinations of types for f and x that are being used in the program. $ echo 'let f g x = g x' > test.ml $ ocamlopt -c test.ml $ objdump -d test.o 0000000000000000 <camlTest__f_1030>: 0: 48 89 c6 mov %rax,%rsi 3: 48 89 d8 mov %rbx,%rax 6: 48 8b 3e mov (%rsi),%rdi 9: 48 89 f3 mov %rsi,%rbx c: ff e7 jmpq *%rdi e: 66 90 xchg %ax,%ax Not so much. (Yes, type specialization is a strategy used by certain whole-program optimizers, such as the MLton compiler, but this is in no way tied to the language or the type system or lack thereof. Types exist whether you name and control them or not, just like tigers and asteroids do.)

gsg 12y ago

Not really. There are no parameters involved in what a Scheme programmer would call a polymorphic program - instead, such programs simply range over all scheme values. Because the values ranged over in such programs is known rather than being a parameter to the program, they are not polymorphic (in the ML sense).

colanderman 12y ago
such programs simply range over all scheme values That's the parametric part. From http://en.wikipedia.org/wiki/Polymorphism_(computer_science) http://en.wikipedia.org/wiki/Polymorphism_(computer_science): If the code is written without mention of any specific type and thus can be used transparently with any number of new types, it is called parametric polymorphism. This definition makes no mention of static typing.