Changeset 86c48f5


Ignore:
Timestamp:
Aug 12, 2016, 4:45:35 PM (8 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, ctor, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, memory, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc
Children:
473d8c82
Parents:
afd4cde
Message:

Add discussion of Haskell type classes

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/aaron_comp_II/comp_II.tex

    rafd4cde r86c48f5  
    413413\subsection{Argument-Parameter Matching}
    414414The first axis for consideration is argument-parameter matching direction --- whether the type matching for a candidate function to a set of candidate arguments is directed by the argument types or the parameter types.
     415For programming languages without implicit conversions, argument-parameter matching is essentially the entirety of the expression resolution problem, and is generally referred to as ``overload resolution'' in the literature.
    415416All expression resolution algorithms form a DAG of interpretations, some explicitly, some implicitly; in this DAG, arcs point from function-call interpretations to argument interpretations, as below:
    416417\begin{figure}[h]
     
    472473\subsection{Implicit Conversion Application}
    473474With the exception of Bilson, the authors mentioned above do not account for implicit conversions in their algorithms\footnote{Baker does briefly comment on an approach for handling implicit conversions, but does not provide an implementable algorithm.}; all assume that there is at most one valid interpretation of a given expression for each distinct type.
    474 Cormack and Wright~\cite{Cormack90} present an algorithm which integrates overload resolution with implicit parameter binding and type inference; their presentation of  implicit parameter binding and type inference is largely similar to \CFA's implicit polymorphic type binding, though their algorithm does not account for other implicit conversions and their discussion of their overload resolution algorithm is not sufficiently detailed to classify it with the other argument-parameter matching approaches\footnote{Their overload resolution algorithm is possibly a variant of Ganzinger and Ripken~\cite{Ganzinger80} or Pennello~\etal~\cite{Pennello80}, modified to allow for polymorphic type binding.}.
    475 Integrating implicit conversion handling into the presented argument-parameter matching algorithms provides some choice of implementation approach.
     475Integrating implicit conversion handling into the presented argument-parameter matching algorithms thus provides some choice of implementation approach.
     476
     477Inference of polymorphic type variables can be considered a form of implicit conversion application, where monomorphic types are implicitly converted to instances of some polymorphic type\footnote{This ``conversion'' may not be implemented in any explicit way at runtime, but does need to be handled by the expression resolver as an inexact match between argument and parameter types.}.
     478This form of implicit conversion is particularly common in functional languages; Haskell's type classes~\cite{typeclass} are a particularly well-studied variant of this inference.
     479However, type classes arguably do not allow name overloading, as (at least in the Haskell implmentation) identifiers belonging to type classes may not be overloaded in any other context than an implementation of that type class; this provides a single (possibly polymorphic) interpretation of any identifier, simplifing the expression resolution problem relative to \CFA.
     480Cormack and Wright~\cite{Cormack90} present an algorithm which integrates overload resolution with a polymorphic type inference approach very similar to \CFA's.
     481However, their algorithm does not account for implicit conversions other than polymorphic type binding and their discussion of their overload resolution algorithm is not sufficiently detailed to classify it with the other argument-parameter matching approaches\footnote{Their overload resolution algorithm is possibly a variant of Ganzinger and Ripken~\cite{Ganzinger80} or Pennello~\etal~\cite{Pennello80}, modified to allow for polymorphic type binding.}.
    476482
    477483\subsubsection{On Parameters}
Note: See TracChangeset for help on using the changeset viewer.