CS 3723
  Programming Languages  
  3.4 Dictionaries   

Reference links given below will be to the online book: Building skills in Python. In this case, see Dictionaries. These are a familiar feature in Perl and other scripting languages, called "hashes" or "associative arrays" in Perl.

3.4.1. Months of the Year: See Dictionaries. Dictionaries can be used to translate data from one form to another. For example, suppose we want to translate the digits representing a month (01 through 12) to the name of the month (January through December). In Python we can use the following dictionary:

Use of Python Dictionary: from digits to months
% python
>>> mon = {'01': 'January', '02': 'February', '03': 'March',
           '04': 'April',   '05': 'May',      '06': 'June', 
           '07': 'July',    '08': 'August',   '09': 'September', 
           '10': 'October', '11': 'November', '12': 'December'}
>>> mon['06']
'June'
# order does not matter, could also be:
>>> mon = {'02': 'February', '10': 'October',   '01': 'January', 
           '06': 'June',     '07': 'July',      '04': 'April', 
           '03': 'March',    '08': 'August',    '05': 'May', 
           '12': 'December', '09': 'September', '11': 'November'}
>>> mon['08']
'August'

Items of Interest or for study:

  • As you can see, from an input like 03, this translates into March. The notation is like an array, where the first item of a pair plays the role of index, which is used to fetch the second item, which is like the value stored in the array at a given index.

  • The first items of pairs are called keys. There must not be any duplicates among the keys. The keys can be an integer like an index in an array, or they can be a string, or anything that is not changeable ("immutable") and "hashable".
  • The second items of pairs are called items. They are also called the value off the key. They can be any Python object at all. (Sometimes pairs themselves are called items.)

  • If we wanted, we could leave off the leading 0's, or strip them off.

3.4.2. The Inverse Dictionary: We might also want to go from the months to the digits. For this we could use the obvious inverse dictionary:

Inverse Python Dictionary: from months to digits
mon_inv = {'January':'01', 'February':'02', 'March':'03', 
           'April':'04',   'May':'05',      'June':'06',      
           'July':'07',    'August':'08',   'September':'09', 
           'October':'10', 'November':'11', 'December':'12'}

But instead of writing out this inverse dictionary, we can use Python code to create it. By definition, there should be no duplicates amoung the first parts of pairs in a dictionary. Otherwise there wouldn't be a unique result of consulting the dictionary. The code below only works if there are no duplicates amonng the second elements of pairs in a dictionary.

Python Dictionary Inverting Program
mon = {'01': 'January', '02': 'February', '03': 'March',
       '04': 'April',   '05': 'May',      '06': 'June', 
       '07': 'July',    '08': 'August',   '09': 'September', 
       '10': 'October', '11': 'November', '12': 'December'}

# construct the inverse dictionary
mon_inv = {} # start with an empty dictionary
for (k, v) in mon.items(): # for digits k and month v:
    mon_inv[v] = k # add (v, k) to mon_inv

sys.stdout.write(str(mon_inv) + "\n\n")
sys.stdout.write(mon['06'] + "\n")
sys.stdout.write(mon_inv['June'] + "\n")
sys.stdout.write(mon[mon_inv['June']] + "\n")
sys.stdout.write(mon_inv[mon['06']] + "\n")
Output (first 4 lines: newlines added, blanks changed)
{'February': '02', 'October': '10',   'March': '03', 
 'August': '08',   'May': '05',       'December': '12', 
 'June': '06',     'September': '09', 'April': '04', 
 'January': '01',  'November': '11',  'July': '07'}

June
06
June
06

Items of Interest or for study:

  • Notice that pairs of the inverse are not in any particular order. (It is the order given by the hash function.)

  • The code to invert the dictionary is not complicated. It uses the dictionary method items(), which returns each ditionary pair in turn (as a tuple). We then construct the dictionary with the pairs reversed. For this code to work, we need a special kind of dictionary: one where the values of keys ( = second items in pairs) have all the properties of the keys: "immutable", "hashable", and "no duplicates".

3.4.3. Example from writing MIPS code: Here is a program that translates simple one-operand assignments for our Tiny project into MIPS assembly language. The first dictionary gives the offset corresponding to each single-character operand. This offset could be calculated with two simple formulas, but the method here is far more general and is used for illustrative purposes. Similarly, the second dictionary translates from a single-character operand to the MIPS op-code.

Translate Assigns to MIPS Output (plus exec frame)
#!/usr/bin/python
import sys
# MIPS offsets for constants and variables
d = {"0":0, "1":   8, "2":  16, "3":  24, "4":  32, 
  "5":  40, "6":  48, "7":  56, "8":  64, "9":  72, 
  "a":  80, "b":  88, "c":  96, "d": 104, "e": 112,
  "f": 120, "g": 128, "h": 136, "i": 144, "j": 152,
  "k": 160, "l": 168, "m": 176, "n": 184, "o": 192,
  "p": 200, "q": 208, "r": 216, "s": 224, "t": 232,
  "u": 240, "v": 248, "w": 256, "x": 264, "y": 272,
  "z": 280}
# MIPS opcodes for operators
op = {"+":"add", "-":"sub", "*":"mul", "/":"div"}

def instr(x):
    s = x[2]
    t = x[4]
    a = x[3]
    r = x[0]
    sys.stdout.write( "\tl.d      $f2, " +
       str(d[s]) + "($s1)\n")
    sys.stdout.write( "\tl.d      $f4, " +
       str(d[t]) + "($s1)\n")
    sys.stdout.write("\t" + str(op[a]) +
       ".d    $f6, $f2, $f4\n")
    sys.stdout.write( "\ts.d      $f6, " +
       str(d[r]) + "($s1)\n\n")
   
instr("a=8*2")
instr("b=7*a")
instr("c=b+1")
instr("d=a/c")
instr("e=3+d")

main:   addu    $s7, $ra, $zero
        la      $s1, M
        l.d      $f2, 64($s1)
        l.d      $f4, 16($s1)
        mul.d    $f6, $f2, $f4
        s.d      $f6, 80($s1)

        l.d      $f2, 56($s1)
        l.d      $f4, 80($s1)
        mul.d    $f6, $f2, $f4
        s.d      $f6, 88($s1)

        l.d      $f2, 88($s1)
        l.d      $f4, 8($s1)
        add.d    $f6, $f2, $f4
        s.d      $f6, 96($s1)

        l.d      $f2, 80($s1)
        l.d      $f4, 96($s1)
        div.d    $f6, $f2, $f4
        s.d      $f6, 104($s1)

        l.d      $f2, 24($s1)
        l.d      $f4, 104($s1)
        add.d    $f6, $f2, $f4
        s.d      $f6, 112($s1)
# Print result + newl
        li      $v0, 3
        l.d     $f12, 112($s1)
        syscall
        li      $v0, 4
        la      $a0, NewL
        syscall
# Stuff at end ################
        addu    $ra, $s7, $zero
        jr      $ra  # ret
        .data
        .align  3
M:      .double 0.,1.,2.,3.,4.
        .double 5.,6.,7.,8.,9.
        .space  208  # a to z
NewL:   .asciiz "\n"

The output of running the MIPS program is: 3.14159292035398252 ( = 355/113).

Items of Interest or for study:

  • Continuation: The definition of the dictionary d can be continued on later lines in any way at all as soon as the { appears. However, you can't start this declaration with d = as the only thing on the line but would need d = \ .

3.4.4. Inverting Dictionary with duplicate second elements: The second components have to be "hashable" for this to work. (I didn't write this code myself.)

Inverting a Dictionary: Operators in C and their precedence
# c_ops.py: precedence of ops in C
# example with no duplicate 2nd components
import sys

op = {"+":"add", "-":"sub", "*":"mul", "/":"div"}
inv_op = {}
for k, v in op.items():
    inv_op[v] = k
sys.stdout.write(str(inv_op) + "\n\n")

# Has duplicate 2nd components (prec of C ops)
prec = {",":0,
    "=":1, "+=":1, "-=":1, "*=":1, "/=":1, "%=":1,
           "&=":1, "^=":1, "|=":1, "<<=":1, ">>=":1,
    "?:":2,
    "||":3,
    "&&":4,
    "|":5,
    "^":6,
    "&":7, 
    "==":8, "!=":8,
    "<":9, "<=":9,  ">":9, ">=": 9,
    "<<":10, ">>":10,
    "+":11,  "-":11,
    "*": 12, "/": 12,  "%":12,
    "!":13, "~":13, "++":13, "--":13, "+(u)":13,
            "-(u)":13, "*(p)":13, "&(a)":13, "(type)":13, "sizeof":13,
    "(group)":14, "[]":14, "->":14,  ".":14,} 
inv_prec = {}
for k, v in prec.items():
    inv_prec[v] = inv_prec.get(v, [])
    inv_prec[v].append(k)

sys.stdout.write(str(inv_prec) + "\n")
Output (edited to group items together with the same precedence)
{'mul': '*', 'add': '+', 'div': '/', 'sub': '-'}

{ 0: [','],
  1: ['%=', '>>=', '|=', '-=', '^=', '<<=', '=', '*=', '&=', '/=', '+='],
  2: ['?:'],
  3: ['||'],
  4: ['&&'],
  5: ['|'],
  6: ['^'],
  7: ['&'],
  8: ['!=', '=='],
  9: ['>=', '<', '>', '<='],
 10: ['>>', '<<'],
 11: ['+', '-'],
 12: ['*', '%', '/'],
 13: ['+(u)', '&(a)', '-(u)', '--', '~', 'sizeof', '!', '(type)', '++', '*(p)'],
 14: ['[]', '.', '(group)', '->']}

Items of Interest or for study:

  • The code above has an initial simple dictionary with no duplicate values.

  • In the second example, the Python code makes a list out of the varous values associated with a given integer precedence.

(Revision date: 2014-07-04. Please use ISO 8601, the International Standard.)