PDD 27: Multiple Dispatch

Abstract

This PDD defines Parrot's multiple dispatch system.

Version

$Revision$

Definitions

Multiple dispatch allows a single function name to be associated with several alternate implementations. It selects the alternate to execute for a particular call at runtime, based on the types of the arguments passed into the call. The selection process compares the arguments of the call and the types declared in the signatures of the alternates, as well as their inherited or composed parents, to find the best match.

A similar selection of alternates based on types at compile time is generally called overloading.

Description

- Parrot supports multiple dispatch in opcodes and user-defined routines.
- A single dispatch system supports MMD in both contexts.
- For user-defined subroutines and methods, the dispatch system is pluggable, allowing users to swap in their own type-matching algorithms.
- For opcodes, the dispatch system is merely extensible, allowing users to define alternates with their own types.
- Dispatch considers both low-level (register) types and high-level (PMC) types, as well as inherited and composed types.
- Dispatch does not consider argument values. HLLs with dispatch systems that do consider argument values will implement their own pluggable matching.

Implementation

The aim of Parrot's multiple dispatch system is not to be an exact match to any one HLL, but to provide the features and tools needed to support multiple dispatch in a number of different HLLs.

Parrot has a single multiple dispatch system, used at the HLL level and internally. {{NOTE: I appreciate the history that led us to have two largely independent MMD systems, but it will cause problems down the road, if we don't fix it now.}}

The heart of the system is the MultiSub PMC. All multiple dispatch routines are MultiSub PMCs, subclasses of MultiSub, or polymorphic equivalents of MultiSub. Calls to multiple dispatch routines use the Parrot calling conventions.

MultiSub PMC API

A MultiSub stores a list of subroutines. When a MultiSub is invoked, it calls an MMD sorting routine to select the best candidate for the current arguments, and invokes that candidate.

A MultiSub can be used anywhere a Sub can be used. It can be stored in a namespace or as a method or vtable override in a class.

An alternate multiple dispatch matching algorithm may be plugged in by subclassing MultiSub and overriding invoke.

Vtable Functions

MultiSub defines the following vtable functions in addition to the ones inherited from ResizablePMCArray.

push_pmc
Add a Sub or NCI sub to the list of candidates. Throw an exception if the value passed in is anything other than a Sub or NCI sub.
set_pmc_keyed_int [deprecated]
Add a Sub or NCI sub to the list of candidates at a particular position in the list. Throw an exception if the value passed in is anything other than a Sub or NCI sub.{{ NOTE: deprecated because MultiSub is no longer an array. }}
get_pmc
Return an array of matching candidates, sorted from best matching to worst matching, for the current call arguments.
get_pmc_keyed
Return an array of matching candidates, sorted from best matching to worst matching, for a passed in signature. The signature passed in is an array of PMCs, and the types are extracted from the types of the array elements.
get_pmc_keyed_str
Return an array of matching candidates, sorted from best matching to worst matching, for a passed in signature. The signature passed in is a simple type string for the signature ('P' for PMC, 'I' for integer, 'N' for number, and 'S' for string).
get_iter
Return an iterator object of matching candidates, sorted from best matching to worst matching, for the current call arguments.
invoke
Return a function pointer to the best matching candidate for the current call arguments, and set up the interpreter preparing for invocation. This vtable function calls Parrot_mmd_sort_manhattan from the public MMD API, but may be changed to call Parrot_mmd_invoke.
set_integer_keyed_int, set_number_keyed_int, set_string_keyed_int [deprecated]
Throw an exception, as an integer, float, or string value is not a Sub or NCI sub. (Masks the vtable functions inherited from ResizablePMCArray.){{NOTE: no longer needed, since not inheriting from ResizablePMCArray.}}

Methods

get_iter
Return an array of matching candidates, sorted from best matching to worst matching, for a passed in signature. If the signature passed in is an array of PMCs, the types are extracted from the types of the array elements. If the signature passed in is a simple type string for the signature ('P' for PMC, 'I' for integer, 'N' for number, and 'S' for string), the types are matched as simple types.

PIR subroutine attributes

The following attributes are used when declaring a MultiSub in PIR.

:multi
  .sub mymultisub :multi(Integer, Integer)
    # ...
  .end
The :multi attribute marks a subroutine or method as participating in multiple dispatch.
:invocant
  .sub mymultisub
  .param pmc first :invocant
  .end
Not all elements of a multi-sub's signature are relevant for the purposes of multiple dispatch. The subroutine parameters that participate in dispatch are marked with the attribute :invocant, and must be contiguous. Subs that are not marked with :multi may not mark parameters with :invocant.{{NOTE: I'm open to other names for the attribute. An English form of the Latin invocare, "to call upon", is pretty appropriate to the act of using an argument as a selector for multiple dispatch.}}

C Multiple Dispatch API

These functions are the public interface to common multiple dispatch operations, and may be called from opcodes, vtable functions, or other C functions.

Parrot_mmd_sort_manhattan
Performs a multiple dispatch lookup on an array of subroutines. The call signature to match is pulled from the current interpreter, following the Parrot calling conventions. Returns a sorted array of candidates that match the call signature, with the best matching candidate as the 0th element.
Parrot_mmd_invoke
Make a multiple dispatch call. Similar in syntax to Parrot_PCCINVOKE, but doesn't separate out the invocant before the signature since the call can have multiple invocants. A significant part of the code from Parrot_PCCINVOKE can be factored out to helper routines used by both Parrot_PCCINVOKE and Parrot_mmd_invoke. 
  void
  Parrot_mmd_invoke(PARROT_INTERP, NOTNULL(STRING *sub_name),
        ARGIN(const char *signature), ...)>
mmd_dispatch* [deprecated]
Dispatch a routine with a fixed low-level (register) type signature, with multiple dispatch on the high-level (PMC) types. The low-level call and return types are specified in the name of the function: 'i' for integer, 'n' for float, 's' for string, 'p' for PMC, and 'v' for void. So, a dispatch of one PMC and one integer argument that returns void is a call to mmd_dispatch_v_pi().

Opcode Multiple Dispatch

Parrot's basic opcodes are not multiple dispatch. They appear to be so, since a single opcode name may have multiple signatures. But, behind the scenes, this is essentially compile-time overloading. (Each different signature is actually a different opcode number, hidden behind the abstraction of a single name.)

Multiple dispatch is only used by a limited set of opcodes. These opcodes directly correspond to standard vtable functions. Multiple dispatch opcodes may take PMC, integer, float, or string arguments and return a PMC, integer, float, or string result.

Multiple dispatch opcodes are standard opcodes that internally call the Parrot_mmd_invoke routine from the public MMD API.

{{NOTE: It is no longer necessary to name multisubs used for opcode dispatch using the "__" names.}}

Vtable Multiple Dispatch

Some PMCs call multiple dispatch routines from their vtable functions. ResizablePMCArray, for example, calls the multiple dispatch equality operation on each element of two arrays from the 'is_equal' vtable function.

Multiple dispatch calls from within vtable functions call the Parrot_mmd_invoke routine from the public MMD API.

Attachments

None.

References

docs/mmd.pod src/multidispatch.c src/pmc/multisub.pmc