Difference between revisions of "Generic function"

From CS 61A Wiki
Jump to: navigation, search
[checked revision][checked revision]
(copyedit; reword)
m ({{C-class}})
 
(One intermediate revision by one user not shown)
Line 1: Line 1:
{{Start-class}}
+
{{C-class}}
 
A '''generic function''' is a function that can operate on multiple types of data. This is especially useful when the objects we are working with have multiple representations. A good example is [https://docs.google.com/presentation/d/1AZSqH0-tbjwJXXZcaqaFnDnfCP-g4wMOxzVPz3aPc4M/edit#slide=id.g3901816cf_022 the variety of number representations] we learned in lecture.
 
A '''generic function''' is a function that can operate on multiple types of data. This is especially useful when the objects we are working with have multiple representations. A good example is [https://docs.google.com/presentation/d/1AZSqH0-tbjwJXXZcaqaFnDnfCP-g4wMOxzVPz3aPc4M/edit#slide=id.g3901816cf_022 the variety of number representations] we learned in lecture.
  
Line 17: Line 17:
  
 
=== Type dispatching ===
 
=== Type dispatching ===
''Type dispatching'' does exactly as its name suggests: depending on the type of the arguments passed in, the function will proceed in different ways. We create a function for each different combination of valid input types and then choose one to use by checking the types of arguments passed in.
+
''Type dispatching'' is a technique in which a function checks the type of the argument passed in and then executes code that is appropriate for the type. To accomplish this, we define a function for each type-operation combination.
  
 
For example, consider the following <code>drive</code> function, which takes in a variety of <code>car</code> types and returns the correct <code>drive</code> method depending on the type given:
 
For example, consider the following <code>drive</code> function, which takes in a variety of <code>car</code> types and returns the correct <code>drive</code> method depending on the type given:
Line 31: Line 31:
 
         return car.drive_tractor()
 
         return car.drive_tractor()
 
</syntaxhighlight>
 
</syntaxhighlight>
 +
 +
==== Tag-based ====
 +
We can implement type dispatching using dictionaries. We define a function <code>type_tag</code> that returns a "tag" representing the type of the argument (the tag is stored in the <code>tags</code> dictionary):
 +
<syntaxhighlight lang="python">
 +
def type_tag(x):
 +
    return tags[type(x)]
 +
 +
tags = {
 +
    <type1> : <tag1>
 +
    <type2> : <tag2>
 +
    ...
 +
}
 +
</syntaxhighlight>
 +
 +
We also define a dictionary <code>implementations</code> that maps from a tuple of the two types to the function that carries out the operation on those types.
 +
<syntaxhighlight lang="python">
 +
implementations = {
 +
    (<tag1>, <tag1>): <fn1>,
 +
    (<tag1>, <tag2>): <fn2>,
 +
    (<tag2>, <tag2>): <fn3>
 +
}
 +
</syntaxhighlight>
 +
 +
Then we can write a generic function as follows:
 +
<syntaxhighlight lang="python">
 +
def op(a, b):
 +
    return implementations[(type_tag(a),type_tag(b))](a, b)
 +
</syntaxhighlight>
 +
 +
For example, here is a generic function to combine two lists (the two possible types are [[Linked list|<code>Link</code>]] and the built-in <code>[[list]]</code>):<ref>https://inst.eecs.berkeley.edu/~cs61a/sp13/labs/lab08/lab08.php</ref>
 +
<syntaxhighlight lang="python">
 +
def type_tag(x):
 +
    return tags[type(x)]
 +
 +
tags = {
 +
    list : 'list'
 +
    Link : 'Link'
 +
}
 +
 +
implementations = {
 +
    ('list', 'list'): lambda a, b: a.extend(b),
 +
    ('list', 'Link'): extend_list_with_link,
 +
    ('Link', 'Link'): extend_link_with_link,
 +
    ('Link', 'list'): extend_link_with_list
 +
}
 +
 +
def extend(lst1, lst2):
 +
    implementations[(type_tag(lst1), type_tag(lst2))](lst1, lst2)
 +
</syntaxhighlight>
 +
 +
<code>extend_list_with_link</code>, <code>extend_link_with_link</code>, and <code>extend_link_with_list</code> are not shown.
  
 
=== Coercion ===
 
=== Coercion ===
''Coercion'' is converting object A into object B so that A can use B's methods. This is useful when the two different objects have some similar properties and when the original object can be seen as the new type with certain modifications.
+
''Coercion'' is converting object A into object B so that A can use B's methods. The general process is:<ref>http://inst.eecs.berkeley.edu/~cs61a/fa12/slides/19-Generics_1pps.pdf</ref>
 +
# Attempt to coerce arguments into values of the same type
 +
# Apply type-specific operations
  
Example:
+
Example:<ref>http://shire.keeganmann.com/~ta/review-typedispatch.html</ref> we have a class representing metric distances:
 +
<syntaxhighlight lang="python">
 +
class MetricDistance:
 +
    def __init__(self, x):
 +
        self.dist = x # assume x is in meters
 +
       
 +
    def compare(self, other):
 +
        """Returns '<', '>' or '=' when comparing self to other."""
 +
        if self.dist < other.dist:
 +
            return '<'
 +
        elif self.dist == other.dist:
 +
            return '='
 +
        else:
 +
            return '>'
 +
</syntaxhighlight>
 +
 
 +
We also have a class representing imperial distances:
 +
<syntaxhighlight lang="python">
 +
class ImperialDistance:
 +
    def __init__(self, x):
 +
        self.dist = x # assume x is in feet
 +
</syntaxhighlight>
 +
 
 +
We want to write a function to compare a <code>MetricDistance</code> and an <code>ImperialDistance</code>. Since <code>MetricDistance</code> already has a <code>compare</code> function, we coerce <code>ImperialDistance</code> to a <code>MetricDistance</code> so we can compare them:
 +
<syntaxhighlight lang="python">
 +
def coerce_imperial_to_metric(imperial):
 +
    return MetricDistance(imperial.dist * 0.3048)
 +
 
 +
def compare_imperial_and_metric(imperial, metric):
 +
    return coerce_imperial_to_metric(imperial).compare(metric)
 +
</syntaxhighlight>
  
 
== Sources ==
 
== Sources ==
 +
<references/>
 
* [https://docs.google.com/presentation/d/1AZSqH0-tbjwJXXZcaqaFnDnfCP-g4wMOxzVPz3aPc4M/edit#slide=id.p CS61A Su14 Lecture 17]
 
* [https://docs.google.com/presentation/d/1AZSqH0-tbjwJXXZcaqaFnDnfCP-g4wMOxzVPz3aPc4M/edit#slide=id.p CS61A Su14 Lecture 17]
 
* [http://inst.eecs.berkeley.edu/~cs61a/su14/discussion/discussion09/discussion09.pdf CS61A Su14 Discussion 9]
 
* [http://inst.eecs.berkeley.edu/~cs61a/su14/discussion/discussion09/discussion09.pdf CS61A Su14 Discussion 9]
 
* [http://wla.berkeley.edu/~cs61a/fa11/lectures/objects.html#generic-operations CS61A Fa11 2.7.3]
 
* [http://wla.berkeley.edu/~cs61a/fa11/lectures/objects.html#generic-operations CS61A Fa11 2.7.3]

Latest revision as of 22:42, 24 July 2014

A generic function is a function that can operate on multiple types of data. This is especially useful when the objects we are working with have multiple representations. A good example is the variety of number representations we learned in lecture.

Techniques

The following are techniques for creating generic functions:

Interfaces

An interface manipulates different data types with the same function. For example, the + operator works with numbers, strings, and lists:

>>> 1 + 2
3
>>> 'hi ' + 'there'
'hi there'
>>> [1, 2] + [3, 4]
[1, 2, 3, 4]

Type dispatching

Type dispatching is a technique in which a function checks the type of the argument passed in and then executes code that is appropriate for the type. To accomplish this, we define a function for each type-operation combination.

For example, consider the following drive function, which takes in a variety of car types and returns the correct drive method depending on the type given:

def drive(car):
    if type(car) == SportsCar:
        return car.drive_sportscar()
    elif type(car) == Van:
        return car.drive_van()
    elif type(car) == SemiTruck:
        return car.drive_semitruck()
    elif type(car) == Tractor:
        return car.drive_tractor()

Tag-based

We can implement type dispatching using dictionaries. We define a function type_tag that returns a "tag" representing the type of the argument (the tag is stored in the tags dictionary):

def type_tag(x):
    return tags[type(x)]
 
tags = {
    <type1> : <tag1>
    <type2> : <tag2>
    ...
}

We also define a dictionary implementations that maps from a tuple of the two types to the function that carries out the operation on those types.

implementations = {
    (<tag1>, <tag1>): <fn1>,
    (<tag1>, <tag2>): <fn2>,
    (<tag2>, <tag2>): <fn3>
}

Then we can write a generic function as follows:

def op(a, b):
    return implementations[(type_tag(a),type_tag(b))](a, b)

For example, here is a generic function to combine two lists (the two possible types are Link and the built-in list):[1]

def type_tag(x):
    return tags[type(x)]
 
tags = {
    list : 'list'
    Link : 'Link'
}
 
implementations = {
    ('list', 'list'): lambda a, b: a.extend(b),
    ('list', 'Link'): extend_list_with_link,
    ('Link', 'Link'): extend_link_with_link,
    ('Link', 'list'): extend_link_with_list
}
 
def extend(lst1, lst2):
    implementations[(type_tag(lst1), type_tag(lst2))](lst1, lst2)

extend_list_with_link, extend_link_with_link, and extend_link_with_list are not shown.

Coercion

Coercion is converting object A into object B so that A can use B's methods. The general process is:[2]

  1. Attempt to coerce arguments into values of the same type
  2. Apply type-specific operations

Example:[3] we have a class representing metric distances:

class MetricDistance:
    def __init__(self, x):
        self.dist = x # assume x is in meters
 
    def compare(self, other):
        """Returns '<', '>' or '=' when comparing self to other."""
        if self.dist < other.dist:
            return '<'
        elif self.dist == other.dist:
            return '='
        else:
            return '>'

We also have a class representing imperial distances:

class ImperialDistance:
    def __init__(self, x):
        self.dist = x # assume x is in feet

We want to write a function to compare a MetricDistance and an ImperialDistance. Since MetricDistance already has a compare function, we coerce ImperialDistance to a MetricDistance so we can compare them:

def coerce_imperial_to_metric(imperial):
    return MetricDistance(imperial.dist * 0.3048)
 
def compare_imperial_and_metric(imperial, metric):
    return coerce_imperial_to_metric(imperial).compare(metric)

Sources

  1. https://inst.eecs.berkeley.edu/~cs61a/sp13/labs/lab08/lab08.php
  2. http://inst.eecs.berkeley.edu/~cs61a/fa12/slides/19-Generics_1pps.pdf
  3. http://shire.keeganmann.com/~ta/review-typedispatch.html