CMPS 2200¶

Introduction to Algorithms¶

SPARC¶

Agenda:

  • Overview of SPARC language
  • Foundation of cost model framework

Why are we learning another language?

  • allows us to specify parallel programs concisely
  • allows us to analyze runtime of parallel programs
    • particularly for nested recursion
    • recall the recursive sum from before (lec 2)

SPARC¶

  • based on Standard ML
  • functional language

Example SPARC program¶

\begin{array}{l} \texttt{let}\\ ~~~~x = 2 + 3\\ ~~~~f (w) = (w * 4, w - 2)\\ ~~~~(y,z) = f(x-1)\\ \texttt{in}\\ ~~~~x + y + z\\ \texttt{end} \end{array}



binding: associate entities (data or code) with identifiers.

let expression:

let
$\:\: b^+$
in
$\:\:e$
end

Expression $e$ is applied using the bindings defined inside let.



expression e: describes a computation

  • evaluating an expression produces its value
\begin{array}{l} \texttt{let}\\ ~~~~x = 2 + 3\\ ~~~~f (w) = (w * 4, w - 2)\\ ~~~~(y,z) = f(x-1)\\ \texttt{in}\\ ~~~~x + y + z\\ \texttt{end} \end{array}

$x = 2 + 3 = 5$
$f(4) \rightarrow (16, 2)$
$x + y + z= 5 + 16 + 2 = 23$

Values and Functions¶

value: irreducible unit of computation

  • e.g.: $\mathbb{N}$, true, -, and
  • functions are also values (it is a functional language)



SPARC supports lambda functions like:

$ \mathtt{lambda} \: x \: . \: x + 1 $

$\mathtt{lambda} \: (x, y) \: . \: x$

What do these do?

In [ ]:
f1 = lambda x: x+1
f1(10)

11

In [ ]:
f2 = lambda x,y : x
f2(10,20)

10

In [ ]:
f2(100, 200)

100

Function application¶

A function application, $e_1 e_2$, applies the function generated by evaluating e1 to the value generated by evaluating e2.

E.g.,

  • if $e_1$ evaluates to function $f(x)$
  • $e_2$ evaluates to value $v$
  • apply $f$ to $v$ by substituting $v$ in for $x$


What does this evaluate to?

$\mathtt{lambda} \: ((x,y) \: . \: x / y) \: (8,2)$

$4$

Composition¶

sequential composition: $(e_1, e_2)$

parallel composition: $(e_1 \: || \: e_2)$

e.g.

$\mathtt{lambda} \: (x,y) . (x * x, y * y)$

vs

$\mathtt{lambda} \: (x,y) . (x * x \: || \: y * y)$

Python version¶

In [1]:
def compose(g, f):
    """
    Returns a **function** that composes f and g
    """
    return lambda x: g(f(x))  # different from just: g(f(x))

def meter2cm(d):
    return d * 100

def cm2inch(d):
    return d / 2.54


# how many inches in a meter?
meter2inch = compose(cm2inch, meter2cm)
meter2inch(1)

compose(cm2inch, meter2cm)(1)
Out[1]:
39.37007874015748

Recursion: an important detail¶

$ f(p) = e $

vs

$ f = \mathtt{lambda} \: p . e $


When can $f$ be referenced from $e$?

$f$ is only visible from $e$ when defined via the binding $ f(p) = e $

This enables recursive expressions...



What does this do?

\begin{array}{l} \texttt{let}\\ ~~~~f(i) = \texttt{if} ~(i < 2) ~\texttt{then}~ i ~\texttt{else}~ i * f(i - 1) \\ \texttt{in} \\ ~~~~f(5) \\ \texttt{end} \end{array}
In [6]:
factorial = lambda i: i if i < 2 else i*factorial(i-1)
factorial(5)
Out[6]:
120

Binary tree¶

We can also define datatypes recursively like:

\begin{array}{l} \texttt{type}~\mathit{tree} = \mathit{Leaf}~\texttt{of}~\mathbb{Z}~|~\mathit{Node}~\texttt{of}~(\mathit{tree}, \mathbb{Z}, \mathit{tree}) \\ \\\\ \mathit{find}~(t, x) = \\ ~~~~\texttt{case}~t \\ ~~~~|~\mathit{Leaf}~y \Rightarrow x = y \\ ~~~~|~\mathit{Node}~(\mathit{left}, y, \mathit{right}) \Rightarrow \\ ~~~~~~~~~\texttt{if}~x = y~\texttt{then} \\ ~~~~~~~~~~~~~\texttt{return}~\texttt{true} \\ ~~~~~~~~~\texttt{else}~\texttt{if}~x < y~\texttt{then} \\ ~~~~~~~~~~~~~\mathit{find}~(\mathit{left}, x) \\ ~~~~~~~~~\texttt{else} \\ ~~~~~~~~~~~~~\mathit{find}~(\mathit{right}, x) \end{array}
In [ ]:
# translated into python...
class Tree:
    def __init__(self, key, left=None, right=None):
        self.left = left
        self.key = key
        self.right = right
        self.is_leaf = left is None and right is None

t = Tree(4,
        Tree(2,
             Tree(1),
             Tree(3)
            ),
        Tree(5,
             Tree(6),
             Tree(7)
            )
        )

def find(t, x):
    print('find t=%d x=%d' % (t.key, x))
    if t.is_leaf:
        return t.key == x
    else:
        if x == t.key:
            return True
        elif x < t.key:
            return find(t.left, x)
        else:
            return find(t.right, x)
        
find(t, 7)

Pattern matching¶

Pattern matching is a way to do typical if..else statements:

$\mathit{find}~(t, x) =$
$~~~~\texttt{case}~t$
$~~~~|~\mathit{Leaf}~y \Rightarrow x = y$
$~~~~|~\mathit{Node}~(\mathit{left}, y, \mathit{right}) \Rightarrow \ldots$

  • Match $t$ against each of the cases.
  • When a match is found, evaluate the right hand side of $\Rightarrow$

What does this do?

$$ \mathtt{lambda} \: x \: . (\mathtt{lambda} \: y \: . f(x,y)) $$

Currying¶

Convert a function of $n$ variables into a sequence of functions with 1 argument each.

Why?


  • Get specialized functions from more general functions by using composition.
  • DRY: no need to repeat function arguments
  • Lambda calculus: can define a programming language that only allows functions of one argument
    • easier for proofs!

E.g.,

$f(x,y) = x + y^2$

$\mathtt{lambda} \: x \: . (\mathtt{lambda} \: y \: . f(x,y))(10)(20) \rightarrow$

$\mathtt{lambda} \: y \: . f(10, y)(20) \rightarrow$

$\mathtt{lambda} \: y \: . (10 + y^2) (20) \rightarrow$

$ 10 + 20^2 \rightarrow$

$ 410 $

In [2]:
def f(x,y):
     return x + y**2

def curry(f):
    """
    Given a function f of two variables,
    return a function g that binds the first variable
    """
    def g(x):      # nested function 1
        return f(x, 20) 
    return g

print(f)
print(curry(f))         # returns f'n g. input: x, output function of y       
print(curry(f)(10))     # returns f'n h. input: y, output f(10,y)
print(curry(f)(20))

<function f at 0x7fa8e83ae310>
<function curry.<locals>.g at 0x7fa8e83aea60>
410
420

Coming up¶

Next we will establish a framework of easily analyzing the cost of algorithms.