3 ms·

"Polymorphism" means that a piece of code can be used, unmodified, for multiple situations. Usually this works by adding parameters to the code, and having each

"Polymorphism" means that a piece of code can be used, unmodified, for multiple situations. Usually this works by adding parameters to the code, and having each situation pass in suitable values of those parameters. From reading section 3, it seems that "stage polymorphism" allows the same piece of code to be used in different "stages". For example, we might have a function call like `square(4)`: if we evaluate it now, like an interpreter, we get the value `16`; if instead we "stage" it, like a compiler, we get code which (when executed) will call `square(4)`. The polymorphism comes from parameterising the 'elimination forms' (branching, function calls, etc.). We can think of `square(4)` as being `call(square, 4)`, and we're overloading the choice of `call`: for an interpreter, we use a `call` which does the function call now; for a compiler, we use a `call` which constructs code for doing the call. As for regular expressions in Javascript, this is more powerful for several reasons. Firstly, regular expressions are so limited that they can't reference other values; hence there's not much difference between interpreting or compiling them. What about a more powerful embedded language, like `eval` running Javascript from within Javascript? That has the problem that we can't send values between different "levels" of Javascript. Say we have a value `x = 42` and we want to create an 'embedded' program `x + x`. We can pass around a string `"x + x"`, but when it eventually gets sent to `eval` it won't necessarily use the same `x` as we intended (it basically suffers from dynamic scope). If we had a way to "stage" Javascript from within Javascript, we could ensure the correct value is used, but we'd probably have to write some funky expression like `<,x + ,x>` (depending on the language; take a look at MetaML for an example!). If we want to stage some Javascript which stages some Javascript (and so on), we'd accumulate horrible nesting/escaping boilerplate. This "stage polymorphism" lets us write `x + x` for all stages, including things which are evaluated immediately. Their technique is also one pass, meaning that we don't have to run evaluators in compilers in evaluators... It also works with reflection, and with interpreters which implement the language semantics differently (they include examples like maintaining a count of how many times a variable is accessed, and for converting to continuation passing style).

reacweb 9y ago
The usage of the word 'polymorphism' in case of 'generic programming' introduces so much confusion. IMHO, polymorphism should be used only for inheritance (virtual inheritance in C++).
- phaedrus 9y ago
  Unless the term 'generic programming' is older than I'm aware of, the word 'polymorphism' has been a technical term in programming language research longer than 'generic programming'. Certainly the word polymorphism has been in use longer than the language C++ has existed. Inheritance polymorphism / class polymorphism is one means of implementing polymorphism. It does cause a moment of confusion the first time you see the word used in a more general sense if you are used to thinking of polymorphism only referring to one kind of polymorphism.
- chriswarbo 9y ago
  Forgive my lack of C++ knowledge, but surely inheritance is a separate topic to polymophism? If we think of a classic OOP example, we might say (in some made-up language): Mammals can breathe Mammals can move Dogs are Mammals Dolphins are Mammals From this, we know that Dogs and Dolphins can breathe and move, so we can write code like: function checkStatus(Mammal m) { try { m.move(); return "Free"; } catch { try { m.breathe(); return "Trapped"; } catch { return "Dead"; } } } This code is subclass polymorphic, since we can pass in a Dog or a Dolphin, or some other type of Mammal, and it will work unchanged. Yet this is completely orthogonal to inheritance! There are two ways we might actually implement these constructs: - Mammal is an interface: Dog implements breathe by operating its lungs and move by operating its legs; Dolphin implements breathe by operating its lungs and move by operating its tail and fins. - Mammal is an abstract class which implements breathe by operating its lungs. Dog inherits breathe and implements move by operating its legs; Dolphin inherits breathe and implements move by operating its tail and fins. Both of these are valid approaches, but consider that: - Only the second approach uses inheritance, so it seems strange to limit "polymorphism" to only this case. - The checkStatus code doesn't actually care which approach we take. It's "polymorphic in our choice of polymorphism"! Also, let's say that we did restrict the term "polymorphism" to these sorts of mechanisms. We might say that the above example is "polymorphic in the choice of Mammal". In which case, the "stage polymorphism" of this article is nothing other than "polymorphic in the choice of stage". We could implement it in a language like C++ something like: Stages can call functions with arguments Stages can branch on booleans ... Interpreter is a Stage Compiler is a Stage We achieve polymophism by passing around the currentStage, and writing code like `currentStage.call(myFunc, myArg)`. If `currentStage` is an `Interpreter`, the call will be performed immediately. If `currentStage` is a `Compiler`, code will be generated to perform the call. The only difference between such an OO setup and the actual implementation in the article is that boilerplate like `currentStage` is all handled implicitly, rather than manually passed around, and we overload the normal language constructs rather than replacing them with methods, e.g. we can write `double(foo)` instead of `currentStage.call(double, foo)`, and `if foo then bar else baz` instead of `currentStage.branch(foo, bar, baz)` (or something even worse, to ensure that `bar` and `baz` get delayed!)
phaedrus 9y ago
Thanks for this explanation. I find the topic interesting because I have been thinking about how to use a similar technique to enable interactive debugging of meta-language expressions using the non-meta-level language's own debugger. Suppose you have a function that builds a (staged) expression object for later interpretation. If an exception occurs while the interpreter is executing it, or perhaps you merely want to see the code showing how/why the expression object was put together how it was, the information you get in the non-meta-level debugger will often be too low-level to be useful. And you can't even walk back up the stack to get it, because the function which built the expression has already returned, having completed it's job which was only to build the expression object, not to run it. A solution is to make the function which builds the expression object be (1) a callback and (2) polymorphic in the staged sense as you described, where the exact same code 'x + x' can have different meanings in different stages. In the first pass, the objects the callback works with have operations which are defined to just build an expression object without evaluating it. In subsequent passes, the same code (or a differently parameterized specialization of the same generic code) is called again but this time it is manipulating objects bound to actual runtime state. The callback may or may not be actually doing any computation (perhaps the interpreter can or is evaluating the expressions itself, and the operations the callback is doing are all nops). But just the act of re-threading execution back through the callback function gets the expression builder function's name back onto the stack for exception stack traces. It also provides a sort of "high level user interface for debugging": if the user puts a breakpoint in the callback code, examining the variables in it gives information about the runtime values passing through the interpreter. I.e. it would provide a way for the user to directly look for temporary variable "x" in the interpreter's current running state. I guess that's in some sense the opposite of collapsing stages? In a way of thinking this is putting stages back in after they have been collapsed, for the purpose of tracing execution.

reacweb 9y ago

The usage of the word 'polymorphism' in case of 'generic programming' introduces so much confusion. IMHO, polymorphism should be used only for inheritance (virtual inheritance in C++).

phaedrus 9y ago
Unless the term 'generic programming' is older than I'm aware of, the word 'polymorphism' has been a technical term in programming language research longer than 'generic programming'. Certainly the word polymorphism has been in use longer than the language C++ has existed. Inheritance polymorphism / class polymorphism is one means of implementing polymorphism. It does cause a moment of confusion the first time you see the word used in a more general sense if you are used to thinking of polymorphism only referring to one kind of polymorphism.
chriswarbo 9y ago
Forgive my lack of C++ knowledge, but surely inheritance is a separate topic to polymophism? If we think of a classic OOP example, we might say (in some made-up language): Mammals can breathe Mammals can move Dogs are Mammals Dolphins are Mammals From this, we know that Dogs and Dolphins can breathe and move, so we can write code like: function checkStatus(Mammal m) { try { m.move(); return "Free"; } catch { try { m.breathe(); return "Trapped"; } catch { return "Dead"; } } } This code is subclass polymorphic, since we can pass in a Dog or a Dolphin, or some other type of Mammal, and it will work unchanged. Yet this is completely orthogonal to inheritance! There are two ways we might actually implement these constructs: - Mammal is an interface: Dog implements breathe by operating its lungs and move by operating its legs; Dolphin implements breathe by operating its lungs and move by operating its tail and fins. - Mammal is an abstract class which implements breathe by operating its lungs. Dog inherits breathe and implements move by operating its legs; Dolphin inherits breathe and implements move by operating its tail and fins. Both of these are valid approaches, but consider that: - Only the second approach uses inheritance, so it seems strange to limit "polymorphism" to only this case. - The checkStatus code doesn't actually care which approach we take. It's "polymorphic in our choice of polymorphism"! Also, let's say that we did restrict the term "polymorphism" to these sorts of mechanisms. We might say that the above example is "polymorphic in the choice of Mammal". In which case, the "stage polymorphism" of this article is nothing other than "polymorphic in the choice of stage". We could implement it in a language like C++ something like: Stages can call functions with arguments Stages can branch on booleans ... Interpreter is a Stage Compiler is a Stage We achieve polymophism by passing around the currentStage, and writing code like `currentStage.call(myFunc, myArg)`. If `currentStage` is an `Interpreter`, the call will be performed immediately. If `currentStage` is a `Compiler`, code will be generated to perform the call. The only difference between such an OO setup and the actual implementation in the article is that boilerplate like `currentStage` is all handled implicitly, rather than manually passed around, and we overload the normal language constructs rather than replacing them with methods, e.g. we can write `double(foo)` instead of `currentStage.call(double, foo)`, and `if foo then bar else baz` instead of `currentStage.branch(foo, bar, baz)` (or something even worse, to ensure that `bar` and `baz` get delayed!)

phaedrus 9y ago

Thanks for this explanation. I find the topic interesting because I have been thinking about how to use a similar technique to enable interactive debugging of meta-language expressions using the non-meta-level language's own debugger. Suppose you have a function that builds a (staged) expression object for later interpretation. If an exception occurs while the interpreter is executing it, or perhaps you merely want to see the code showing how/why the expression object was put together how it was, the information you get in the non-meta-level debugger will often be too low-level to be useful. And you can't even walk back up the stack to get it, because the function which built the expression has already returned, having completed it's job which was only to build the expression object, not to run it. A solution is to make the function which builds the expression object be (1) a callback and (2) polymorphic in the staged sense as you described, where the exact same code 'x + x' can have different meanings in different stages. In the first pass, the objects the callback works with have operations which are defined to just build an expression object without evaluating it. In subsequent passes, the same code (or a differently parameterized specialization of the same generic code) is called again but this time it is manipulating objects bound to actual runtime state. The callback may or may not be actually doing any computation (perhaps the interpreter can or is evaluating the expressions itself, and the operations the callback is doing are all nops). But just the act of re-threading execution back through the callback function gets the expression builder function's name back onto the stack for exception stack traces. It also provides a sort of "high level user interface for debugging": if the user puts a breakpoint in the callback code, examining the variables in it gives information about the runtime values passing through the interpreter. I.e. it would provide a way for the user to directly look for temporary variable "x" in the interpreter's current running state. I guess that's in some sense the opposite of collapsing stages? In a way of thinking this is putting stages back in after they have been collapsed, for the purpose of tracing execution.