(cons and prose)

I wrote this a while back when I was studying. I didn't publish it because I thought there was something I should double check but I'll just put it up for now.

Permutations

How many different orderings can you make when you...

Choose r things from n things with replacement:

n^r

You have n choices each time.

Choose r things from n things without replacement:

n!/(n-r)! = n * (n - 1) .... * r

You have n choices, then n-1, then n-2 ... hence the factorial. You divide by the factorial of the number of things you don't choose which is the same as stopping the factorial of n calculation early.

Of course, if you're going to use all of the elements, this simplifies to n!.

Combinations

How many different sets can you make when you...

Choose r things from n things with replacement:

(n + r - 1) choose r = (n + r - 1)! / r!(n - 1)!

Choose r things from n things without replacement:

n choose r = n!/r!(n-r)! = permutations_without_replacement(n, r) / r! = permutations_without_replacement(n, r) / permutations_without_replacement(r, r)

The extra division relative to permutations is to avoid counting different orderings of the same items multiple times. You find an answer as if you did care about order, and then correct by dividing by the number of orderings of the number of items you're choosing.

What if the n things in the set S are not all unique?

Invoke the Bookkeeper Rule:

permutations(n, r) / product(S.count(x)! for x in set(S))

For every repeated item in S, divide the number of permutations by the factorial of the number of times that item appears in S. You can do this for unrepeated items, too, but 1! = 1.

I have to learn Perl, so I started working on this and then got nerd-sniped by other things. But Beeminder is making me update my blog so this will have to do for now.

Syntactic Translations

import my_module.my_submodule package MyModule::MyClass; a_dictionary[a_key] $a_hash{$a_key}; an_empty_list = [] $an_empty_list = (); len(a_list) $a_list 'concatenate' + ' ' + 'us' 'concatenate' . ' ' . 'us'; '%(a_variable)s this is string interpolation' '$a_variable this is string interpolation'; # the $ is the sigil, not an operator '''Now I can use ' and " inside this string without escaping them, and I can break lines.''' qq{Now I can use anything besides the symbol right after qq inside this string; it acts like it's doubled quoted.} q{Now I can use anything besides the symbol right after q inside this string; it acts like it's single quoted.} # Inline conditionals: Python has one way to do it foo = 1 if 1 == 0 else 2 # Where in Perl there are many $foo = 1 if 1 == 0; # you can't use else here $foo = 1 == 0 ? 1 : 2; $foo = 1 unless 1 == 0; if 1 == 0: foo() elif 1 > 0: bar() else: baz() if (1 == 0){ foo(); } elsif (1 > 0) { bar(); } else { baz(); } 1 == 0 'a' == 'b' 1 != 0 'a' != 'b' 1 == 0; 'a' eq 'b'; 1 != 0; 'a' ne 'b';

You can declare variables.

Declared but unassigned variables contain undef. defined tests if a variable is defined.

Variable names have sigils. They're kind of like type annotations and they're basically part of the variable name, except you can switch them sometimes.

$a_scalar @an_array %a_hash

You have to put the scalar sigil on an array or hash when you're getting an element out of it.

$an_element = $a_hash{$a_key}; # This is crazy by the way

If you're not accessing an element, the scalar sigil on an array or hash means get the length of the collection.

$a_number = $an_array;

Accessing elements of an array uses [] like Python, but for a hash (dictionary) you use {} as shown above.

Strings are similar (single and double quotes work, \ is escape), but you can't use special characters like \t inside single quotes in Perl, only inside double quotes.

Booleans don't exist in Perl. Here are the things that evaluate to False in Perl: 0, '', "", '0', "0", undef. This is analogous to Python except '0' is True in Python.

Helpful things for readability (yes, Perl has some features that increase readability! I didn't know either!) include heredocs for strings and _ for numbers. The following pairs of code snippets show equivalent constructs.

$a_long_string = 'blah blah blah'; # heredocs are good for long strings with symbols that would need to be escaped # They're put in the kind of quotes you put around the user-defined delimiter. # You can't indent before the delimiter. $a_long_string = <<'the end'; blah blah blah the end $a_long_number = 1000000 $a_long_number = 1_000_000

Pitfalls Perl treats anything that looks like a number as a number. So while you don't have to convert your spreadsheet data from strings to numbers, if you have data on your friend Nan, you're gonna have a bad time. Use looks_like_number if you need to check if something looks like a number to Perl.

Sources:

The stationary distribution of a Markov Chain is the probability distribution over its states such that when you multiply it by the transition probability matrix, it doesn't change.

So the stationary distribution pi is a row vector and its ith cell is equal to the dot product of pi and the ith column of the transition matrix.

pi[i] = dot(pi, T[i])

To find it, write one equation for each of its cells according to the equality above and solve the system of equations. You'll need one extra equation, which is that the sum of all the cells is 1. This normalizes the probabilities and ensures there's only one answer, instead of one answer for every constant the stationary distribution could be multiplied by (that is, infinitely many).

Aren't descriptions of heaps hard to follow? Let's see if we can do better by shamelessly taking notes from the Wikipedia page.

Binary heaps: nodes have two children (it's a binary tree).

** d-ary heaps:** May be faster in practice due to memory caching.

Shape property: all levels of the tree are filled except possibly the leaf level, which is filled from left to right. This means it's a complete binary (or d-ary) tree.

Heap property: a node dominates (is smaller/larger than, depending on the type of heap) all of its children. This doesn't mean the heap is stratified, because a c-command (aunt-niece) relationship could be out of order. It's like family trees: you're likely to be older than your nieces and nephews, but you don't have to be. But you have to be older than your sons and daughters.

One way to remember how the heap operations work is that they always make the heap satisfy the shape property first, then the heap property.

The insert and delete operations move nodes vertically in the tree, and because the height of the tree is log(n), these operations are O(log n).

Insert: You insert into the bottom, in the next empty leaf slot, and then bubble up. Bubbling up means swapping a node with its parent until it gets a parent that dominates it. (Not the first time talking about trees has sounded disturbing, won't be the last.)

Delete: When you delete, you delete the root (min or max), because that's what heaps are for. Then you take a leaf, put it at the root, and bubble down. Bubbling down means swapping a node with its child, the one that dominates it the most, until it dominates both of its children.

Create: Creating a heap naively is n insertions at O(log n) each, so O(nlogn). But you can do it in a way that converges to O(n).

Do the first half of the insert operation on every node - add leaves, but don't bubble up. This makes a binary tree that satisfies the shape property but not the heap property.

Instead of bubbling everything up the whole tree, bubble everything down the sub-tree it is the root of. Start at the leaves and work your way up. Since most subtrees are very short, this turns out to be fast. This way of turning a complete binary tree into a heap is called heapify.

Implementation

In an effort to make our lives harder, or save space or something, heaps are often implemented as arrays where you just know due to the shape property which things are parents of which. Worse, some people start this array at 0, and some start it at 1.

If your root is at 0, and you have the arbitrary node at index i, its parent is at floor((i-1)/2) and its children are at 2i + 1 and 2i + 2.

If your root is at 1, i's parent is at floor(i/2) and its children are at 2i and 2i + 1.

Our reward for dealing with this is that heapsort can operate in place on an array.

Heapsort

Starter Definition

I don't think I ever had to do modular arithmetic in school, and when I first learned to program I read to just read it as a remainder-getter. Simple enough:

5 modulo 2 = the remainder of 5/2 = 1

Congruence

The modulo operator gives you the amount left after you take out all the even multiples of a number (the modulus), so

14 modulo 12 = 2

and

26 modulo 12 = 2

and so

14 modulo 12 is congruent to 26 modulo 12

Numbers that are congruent modulo n are different by a multiple of n.

Odd numbers are congruent modulo 2, and even numbers are as well.

Arithmetic

You can simplify to the smallest congruent number before adding or multiplying when you're doing modular arithmetic.

(2 mod 12) + x = (14 mod 12) + x (2 mod 12) * x = (14 mod 12) * x

In fact, x doesn't have to be the same number on both sides of these equations. The left x just has to be congruent, mod 12, to the right x. (x must be an integer for the second identity to hold, but not for the first).

Negative Numbers

But it turns out that modulo is not the same as getting the remainder, because they behave differently with negative numbers.

15/12 = 1 remainder 3 -15/12 = -1 remainder 3 15 mod 12 = 3 -15 mod 12 = 9

Fuller Definition

This forum thread is where I finally found a definition of the modulo operator that seems to work in the general case:

The mod function is defined as the amount by which a number exceeds the largest integer multiple of the divisor that is not greater than that number.

That is, a mod n is the amount by which a exceeds the largest integer multiple of n that is less than or equal to a.

This actually follows the way the floor function works: floor(1.5) = 1 but floor(-1.5) = -2. By paying attention to regular value instead of absolute value, you get different behavior in positive vs. negative numbers.

I'll write it as a function to make it clear (in pseudo-Python, because Racket is hard to follow here):

def mod(a, n): multiple = floor(a / n) * n return a - multiple

Here's how that works out for positive and negative numbers.

15 mod 12 = 15 - floor(15/12) * 12 = 15 - floor(1.25) * 12 = 15 - 1 * 12 = 15 - 12 = 3 -15 mod 12 = -15 - floor(-15/12) * 12 = -15 - floor(-1.25) * 12 = -15 + 2 * 12 = -15 + 24 = 9

Sources:

I always learn which coding schemes mean what when I need to for a project and then forget again by the next project. Better get it written down!

It's also good to have this lying around:

Interpretation of the coefficients in logistic regression

log(P(y = 1|x)/P(y = 0|x))

Rules for Coding

My notes from Brian Dillon's class tell me that:

levels to be grouped together get same sign

levels to be contrasted get opposite

excluded levels get 0

contrasts have to sum to zero if you want use interactions

Types of Coding

dummy coding or treatment coding:

picks a reference level of the factor and compares other levels to that one

intercept is the mean of the reference level

don't use interactions

contrast matrix for a factor with 3 levels (cell shows the contrast between row and column level)

2 3 1  0 0 2 1 0 3 0 1

simple coding

compares each non-reference level to the reference level

intercept is the grand mean

can use interactions

contrast matrix:

2 3 1  -.33 -.33 2 .66 -.33 3 -.33 .66

sum coding or deviation coding

compares each level to the grand mean

intercept is the grand mean

can use interactions

contrast matrix:

2 3 1  -1 -1 2 1 0 3 0 1

The link below has even more, but that's all I need for now!

Sources:

Brian Dillon's Quantitative Methods class in the UMass Linguistics Department

Yay, I finally get them.

alter_f(old_f): def new_f(*args, **kwargs): return old_f(*args, **kwargs) + 1 return new_f

It's that simple.

@alter_f def old_f(foo): return foo

is syntactic sugar for

old_f = alter_f(old_f)

Either way, this happens.

old_f(1) >>> 2

Because decorators like alter_f update decorated functions like old_f in place, you have to make sure not to get confused.

old_f is gone

old_f means new_f now; there is no function that just returns its argument in this namespace. If you want to be able to use both, you have to forgo the sugar and do

different_f = alter_f(old_f)

old_f needs a docstring

Everything needs docstrings, but decorated functions especially do, because except for that little line above the definition pointing out that this function is wrapped, the source code is lying to you.

new_f needs old_f's metadata

If you use your decorator on several functions (and you probably should), all of the resulting functions will have identical names and docstrings saved in their metadata by default. The name will be new_f. You probably want the metadata from the old functions. Fortunately, someone thought of that, so it's easy to fix -- with another decorator.

def alter_f(old_f) @functools.wraps(old_f) # gives new_f old_f's metadata def new_f(*args, **kwargs): return old_f(*args, **kwargs) + 1 return new_f

Use decorators to avoid code duplication

Since old_f is gone, why didn't we just write it the way we wanted it in the first place?

def old_f(foo): return foo + 1

If old_f is the only function we decorate with alter_f, then the only reason to prefer the decorator pattern is (not in this case but maybe in real code) doing both old_f and new_f's jobs in one function is hard to read, and they make more sense in two different places.

But that's not reason enough, because we break functions down into smaller functions all the time without using decorators. Here's one option:

def old_f(foo): return foo def new_f(bar): foo = old_f(bar) return foo + 1

The decorator pattern is less readable, less testable, and less flexible than this one (and the different_f solution above), all thanks to mutation making the original old_f inaccessible once it's been decorated. So we still haven't found the reason for decorators.

But what if, in my silly little example, we had several functions whose results we wanted to add 1 to? You'd run the risk of developing carpal tunnel if you wrote + 1 at the end of all those functions! A decorator can be written once for any set of pre- and/or post-processing steps, and then slapped on top of all the function definitions that would otherwise have to have those steps in their bodies. As anyone who can stand reading this blog must already know, less repetitious code is less bug-prone code.

Decorator Classes

The reason I finally understood this time was that I read a page that ignored decorators that are classes in favor of decorators that are functions. But now that I get them, decorator classes are equally simple. They also replace the decorated thing with a wrapped version. The difference is just that since the wrapper is a class, the result is an object of that class. That way, you can have state, which can help with neat tricks like pseudo-currying.

Sources:

http://wiki.python.org/moin/PythonDecoratorLibrary#Pseudo-currying

http://simeonfranklin.com/blog/2012/jul/1/python-decorators-in-12-steps/

I've looked at a lot of short Git tutorials and I've learned how to get a basic workflow going several times, but I've never learned how to undo things properly. Every time I need to undo a commit, I google it, and every time, I try to read an explanation so I'll get it for next time, but it never makes any sense to me. Finally I managed to cross reference enough documentation to fill in the gaps, so I'll record it here.

Names

There are some default names for things in Git.

master -- the first branch created in a repository. After this one, you name new branches as you create them.

origin -- the first remote repository you link your repository with.

HEAD -- this is a special name. master and origin could be named differently if you wanted, but HEAD is just a pointer to whichever commit is the most recent one on whichever branch you have checked out at the moment. It's the default commit name in any command that takes an optional commit name.

commits before HEAD -- the commit before HEAD is HEAD^. The commit n before HEAD is HEAD~n.

any commit -- they all have a hash code you can see in the log.

The Commit Graph

If you only have one branch, your commit graph looks like this:

Initial Commit <-- ... <-- Latest Commit (HEAD)

This is a linked list, and keeping that in mind makes some things make more sense. HEAD is the head of the currently checked out linked list (branch). Sometimes the name of a branch refers directly to its head rather than to the whole thing, which makes sense because when you use a linked list you only get a pointer to its head, and you have to follow the links to get to the rest. It also tends to be the desired behavior -- when you merge two branches, you actually want the latest versions of the two branches to merge, not some unfinished work along the way.

The Commit Workflow

Working Tree --add--> Index --commit--> HEAD --push--> origin

The files you see and edit on your computer are your working tree. When you stage them using git add, the changes you've made get logged in the index file. When you commit them to the commit graph using git commit, they end up as your current HEAD. When you push them to a remote repository, well, they end up there (as well as in HEAD on your local repo).

The Undo Workflow

Working Tree <--reset-- Index

Calling git reset with no option, but optional filenames, undoes adding those files (or all staged files). Their changes are still in your working tree but no longer in your index.

You can also call git reset with an option and a commit name. Here are what the different options do. This resets certain parts of the workflow graph to have the same state as the specified commit.

Working Tree       Index       HEAD <--soft-- other_commit

Working Tree       Index <-- HEAD <--mixed-- other_commit

Working Tree <-- Index <-- HEAD <--hard-- other_commit

reset --soft resets only HEAD, undoing the commit command.

reset --mixed resets HEAD and the index, undoing commit and add.

reset --hard resets HEAD, the index, and the working tree, undoing commit, add, and your edits. If those changes don't exist in another branch, they are gone.

Sources:

Git man pages

http://www.sbf5.com/~cduan/technical/git/

There’s a lot of confusion and disagreement in discussions of the relative benefits of object oriented programming (OOP) and functional programming (FP). I noticed that some people say the two are opposed while others (like Martin Odersky, creator of Scala) say they’re orthogonal. Mike noticed that OOP really has two meanings, one that people usually focus on and one that Alan Kay (creator of Smalltalk) thinks is more important. I think both of these issues are clarified if we realize that the distinction between object oriented and functional programming are along two dimensions.

The Dimensions

I’m going to let the linguist in me come out as I write these the way we write phonological binary features.

[side effects] The difference between [+side effects] and [-side effects] goes by many names:

impure vs. purely functional

message passing vs. returning values

statements vs. expressions

telling vs. asking

The Python list method sort has the side effect of sorting the list and returns None, while the Python function sorted has no side effects (doesn’t change the list), but returns a new sorted list.

my_list = [2,3,1] print my_list.sort() > None print my_list > [1,2,3] another_list = [2,3,1] print sorted(another_list) > [1,2,3] print another_list > [2,3,1]

Message passing, I should note, is not simply the opposite of returning values. I’m going to define it as code that causes a side effect and is sent from one encapsulated actor to another. I think that to maximize the effectiveness of message passing it shouldn’t return a value, but that’s not critical to the definition; Ruby is all about message passing but always returns values.

[inheritance] [+inheritance] languages allow you to create a new data type that by default has all the properties of another data type. This goes hand in hand with what “object oriented" most obviously means, which is that decisions about how actions apply to data types are made by the data types, not by the actions. [-inheritance] languages let the actions (functions) make these decisions, so inheritance doesn’t make sense for them.

The Typology

By crossing the possible values of these features, we get a typology of four types of programming.

[+side effects]  [-side effects] [+inheritance]  OOPFOOP [-inheritance]ImperativeFP

Imperative programming doesn’t have inheritance because it doesn’t have objects, and it tends to use statements (hence “imperative"), creating side effects.

Functional programming, in my mind, is defined by avoiding side effects as much as possible. It’s also characterized by the use of higher order functions, but somehow I don’t think that’s what all the fuss is about when people are comparing paradigms. FP is not associated with objects and inheritance; it’s the functions that decide how actions apply to data types. But if you think it could have objects, that’s ok. My point in making this table is that what “functional programming" means is unimportant; which features you want to use is what matters.

Object oriented programming is sometimes seen as being all about message-passing, sometimes seen as being all about inheritance, and sometimes seen as requiring both. In order to fill out the table, I put OOP in the cell that’s both [+side effects] and [+inheritance]. In the [-side effects] [+inheritance] cell, I wrote FOOP, for functional object oriented programming. This is where I’d put Scala, for instance — its standard data types are immutable and it encourages [-side effect] code, but it does make use of objects and inheritance.

So if that’s what’s out there, what should we use?

Side Effects Are Unavoidable

If you want your program to do anything useful, it has to have side effects on the world outside of it, by printing to your terminal, updating your database, changing your webpage, writing to your file, or making your robot play soccer.

Side effects internal to your program are more avoidable, but some data structures, like hash tables, rely on updating existing values to achieve their efficiency.

But Avoid Them

When you change variable values mid-program, you make your program harder to understand, and that increases the risk of bugs and the difficulty of fixing bugs. After Mike primed me to think about side effects, I realized that the bugs that made me the craziest, because they took so long to figure out, where due to unintentional side effects. So I think the best way to program is to limit your side effects — and constructs that make side effects possible (mutable data types, generators) — as much as you can, resulting in a practical functional style.

Haskell is a purely functional language except for its I/O Monad, which encapsulates all the code that has side effects on the outside world. This results in the purest possible program that still does useful things. Compare the idea of using message passing at the top level of a program and FP underneath.

In languages that lack support for some functional programming constructs, or when you’re using a mutable data structure for efficiency, you can have impure programming inside of functions, and make sure that your function doesn’t have side effects outside of it, on global variables. This means you only have to keep track of side effects within a small function, not within your program as a whole.

I do think I should read more of what Alan Kay has to say though, since he thinks there’s really something good in the idea of message passing. (In fact, Mike and I just had a conversation that brought up a benefit of message passing, so I’ll post about that sometime soon.)

Inheritance Has a Specific Purpose

Part of the confusion out there is that people often say OOP is good because it makes programs more modular, which enables more code reuse and makes code easier to understand.

OOP does enable modularity, but to say that’s what makes OOP good implies that other paradigms don’t enable modularity, and that’s just not true. Imperative and functional programs have modules, which separate parts of programs, hide implementations, and enable code reuse.

[+inheritance] languages encapsulate objects while [-inheritance] languages encapsulate functions. Both can encapsulate modules.

The thing that’s special about inheritance is that it makes it easier to add new data types (if they’re related to old ones) than modules and functions do. But there’s also something special about orienting your program around functions instead of objects — that makes it easier to add new functions to your program than objects do.

Sources:

Grossman, Dan. OOP Versus Functional Decomposition. Programming Languages, Section 8. Coursera.

I learned the Master Method once and then forgot it, which means it needs a blog post.

The Master Method is a way of determining the time complexity of a recursive divide-and-conquer algorithm based on its recurrence T(n).

Formulas for Reference

The formula for the recurrence is:

T(n) = aT(n/b) + O(nd)

And the upper bound on the level of work at a level j is:

cnd * (a/bd)j

Needed Values

a = the branching factor of the recurrence tree. When you divide the problem, how many subproblems do you divide it into? How many recursive calls do you make at each step?

b = the number you divide the problem size by. Each subproblem is 1/b the size of the parent problem.

d = the exponent on the big-oh runtime complexity of the work done outside of the recursive calls. Once you've done your recursive calls, how much work do you do?

bd = the rate at which the amount of work per subproblem decreases

Comparison

Since a is the rate at which the number of subproblems increases, we need to compare a to bd to figure out what dominates the runtime complexity: the proliferation of recursive calls (a), or the work done outside of the recursive calls (bd).

Answers

if a = bd: T(n) = O(nd log(n))

In this case, the number of leaves in the recurrence tree grows at the same rate as the amount of work done outside the recursive calls, so you multiply the amount of work done at one level in the tree, nd, by the number of levels, (log(n)).

if a < bd: T(n) = O(nd)

As you go down levels in the recurrence tree, the rate at which the number of subproblems increases is less than the rate at which the amount of work per subproblem decreases. So you end up with less work the further down you go, and the work in the root dominates the running time. The work done in the root is O(nd).

if a > bd: T(n) = O(nlogb(a))

As you go down levels in the recurrence tree, the rate at which the number of subproblems increases is greater than the rate at which the amount of work per subproblem decreases. So you end up with more work the further down you go, and the work in the leaves dominates the running time. There are logb(n) levels in the tree. We multiply the number of leaves by a at each level. So the number of leaves at the end is alogb(n), and the running time in this case is O(alogb(n)). Weirdly, this is the same as O(nlogb(a)).

Another Way

Another way to do the comparisons is to take the logb of both sides, comparing logb(a) with d. This way, you deal with that more complicated value in the beginning of the calculation, and you can just plug it in if you end up using the third case.

Let's define x as logb(a).

if x = d: T(n) = O(ndlog(n))

if x < d: T(n) = O(nd)

if x > d: T(n) = O(nx)

Sources:

Roughgarden, Tim. Algorithms: Design and Analysis, Part I, Week 2. Coursera www.coursera.com.

http://www.cs.ucdavis.edu/~gusfield/cs222f07/mastermethod.pdf

A puzzle from Raymond Smullyan's book To Mock a Mockingbird helped me get a better handle on the Y combinator.

The puzzle says that there is a forest with some number of birds in it where each bird says the name of a bird when it hears the name of a bird. So each bird is a function from bird names to bird names.

For each pair of birds, including a bird and itself, there is a composition bird. That is, for all A in the forest, for all B in the forest, there exists a C such that:

C(x) = A(B(x))

Here's a lambda calculus compose operator that I'll use later:

o = λa. λb. λx.a (b x)

There is a mockingbird. That is, there exists an M in the forest such that M's response to x is x's own response to x:

M(x) = x(x)

Here's the lambda calculus version of the mockingbird:

M = λx.x x

If a bird A says B when it hears B, so that A(B) = B, then A is fond of B.

The question is whether all birds are fond of some other bird.

Spoiler alert - don't keep reading if you want to figure it out yourself!

Fondness is a nice name for fixed points - B is a fixed point for A if A is fond of B. A fixed point is a value that a function maps to itself, so that applying the function to it causes no change.

fixed_point = f(fixed_point) = f(f(fixed_point)) = f(f(f(f(f(f(fixed_point))))))

The Y combinator is a fixed point finder. You give it a function and it gives you the fixed point of that function.

Y f = fixed_point

So to solve the puzzle we need to know if we can make a Y combinator out of the birds in the forest. If so, we could apply it to any bird in the forest and find its fixed point, the bird that it's fond of.

Here's the Y combinator:

Y = λf.(λx.f (x x)) (λx.f (x x))

We can in fact rewrite it in terms of birds in the forest, assuming we have a mockingbird M, some other bird f, and all the composition birds that these require. Specifically, we need the composition bird of A applied to M:

B(x) = f(M(x))

B = f o M

The Y combinator turns out to be a mockingbird of the composition of the function you're interested in and a mockingbird.

Y = λf.(λx. f (x x)) (λx.f (x x))

Y = λf.(λx. f (M x)) (λx.f (M x)) by M x = x x

Y = λf.M (λx.f (M x)) by M x = x x

Y = λf.M (o f M) by o f M = (λa. λb. λx.a (b x)) f M = λx.f (M x)

In the last post, I looked at ways of calling functions in terms of when to evaluate their arguments. Here I'll look at when to evaluate expressions in general, regardless of whether they're arguments to a function. They might be top-level expressions, local expressions, or arguments that are plugged in only to be sent to a second function.

Eager evaluation is strict; evaluation does not get delayed. It's the general version of call-by-value.

Lazy evaluation is a kind of non-strict evaluation. It's the general version of call-by-need. In a lazy language like Haskell, you can have infinite lists (other languages can do this with generators and streams though) and an argument can be passed to a function which passes it to another function which never uses it, and never be evaluated.

Lenient evaluation is an implementation of non-strict evaluation. Instead of saying "evaluate outside-in" or "evaluate inside-out" it says "you have to evaluate something when you need it; otherwise any ordering goes." This flexibility is useful for parallelization - if either can go first, why not both?

There is no general version of call-by-name that I have found, and for good reason - things can be called not just one time too many, as in eager evaluation, but many times too many.

Which is best?

Space

Minimizing the number of evaluations via lazy evaluation can introduce a space-time tradeoff and use too much memory. Eager evaluation is better in cases with a lot of intermediate steps to a small result, like a fold. Lazy evaluation is better when you're increasing the size of your data but only need some of it at a time, like if you're iterating over a cartesian product. Lenient evaluation can be so parallelizable that it uses too much memory, so parallelization may need to be constrained.

Time

In terms of evaluation, there are two ways to speed up a program: avoid unnecessary evaluations or parallelize evaluations. Lazy evaluation does the best at the former and lenient evaluation does the best at the latter.

Clarity

The ability to represent infinite data structures in lazy evaluation can make code very pretty. Lenient evaluation can do some but not all such data structures. Eager evaluation has the edge on the ease with which you can calculate algorithmic complexity, though, because it's more clear when each expression will be evaluated.

Mutation

Non-strict (lazy and lenient) evaluation strategies make it (even more) difficult to keep track of mutations. In Haskell this is not a problem because you can't mutate things anyway.

Make it lazy

In any language with higher-order functions, you can write a thunk. Racket also has a delay function (macro) for this.

Scala has a Stream type and in other languages you can write streams yourself. Python and Ruby generators aren't quite the same, but I'll have to look into that in another post.

Make it call-by-name

Scala can specify individual function parameters to be call-by-name with <= instead of :.

def myfunc(called-normally: Int, called-by-name <= Int): Int = blah

Make it eager

In Haskell, !$ evaluates the following expression eagerly.

Sources:

Tremblay and Gao 1995: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.3751

Wadler 1996 (has some excellent puns): http://homepages.inf.ed.ac.uk/wadler/papers/lazyvsstrict/lazyvsstrict.ps.gz

http://existentialtype.wordpress.com/2011/04/24/the-real-point-of-laziness/

Call-by-value is an implementation of applicative order evaluation. When you call a function, you evaluate its arguments first thing. Now you have values as arguments, and you plug them into the function body.

Call-by-name is an implementation of normal order evaluation. You leave the arguments as they are, passing them around in all their glorious complexity, and start evaluating the function body.

If a language doesn't support call-by-name and you want to use it, you can take advantage of the fact that evaluating an expression is different from calling a function. When you evaluate the name of a function, you get a function that hasn't been called yet, and you can wait to call it until you're good and ready. So you just wrap your expression in a zero-argument function, like this:

(define might-not-be-needed (* 2 3))

(define (thunk) might-not-be-needed)

These are called thunks, but I think they should be called expression burritos or laziness forcefields. Please tell the powers that be.

Call-by-need is another implementation of normal order evaluation. This is call-by-name except that if you do have to evaluate an argument as you're evaluating the function body, you remember its value, so that you don't have to evaluate it again later if it gets used again.

Number of evaluations

Call-by value evaluates arguments exactly once. It's more efficient than call-by-name if an argument is needed more than once in a function call, like here:

(define (call-me-by-value x) (x + x + x))

Call-by-name evaluates arguments exactly as many times as they're needed, from 0 to a whole bunch. It's more efficient than call-by-value if an argument might not be needed at all in a function call, like here:

(define (call-me-by-name x y) (if x y 0))

Call-by-need evaluates arguments 0 or 1 times. It's as efficient as possible in both cases.

But call-by-need has other downsides, which I'll cover in the next post.

Sources:

Coursera: Programming Languages by Dan Grossman, Section 5, Delay and Force

I just found out as I was looking into the cons of lazy evaluation (which seems like the bestest at first glance) that there are two kinds of distinctions at play - the order in which expressions are evaluated and the implementations of these orders. In this post I'll just focus on the orders. In the next post I'll move on to implementations - call by value, call by name, call by need, lazy, eager, and lenient evaluation.

Let's work with a function that takes two arguments and returns their sum. You may know it as "addition," because you're very fancy, as we can tell by the fact that you're reading my blog. So here it is:

(define (add x y) (+ x y))

Now let's call it with the number 4 as the first argument and the expression (* 2 3), the multiplication of 2 and 3, as the second argument.

(add 4 (* 2 3))

We need to simplify it, by applying * and by applying add. The question is, which do we do first? 

In applicative order evaluation (also called strict evaluation), we simplify the arguments to a function before plugging them in and simplifying the function body, like this:

(add 4 6)

(+ 4 6)

10

In normal order evaluation (also called non-strict evaluation), we plug the arguments into the function body before evaluating them, like this:

(+ 4 (* 2 3))

(+ 4 6)

10

Conditionals (if then else) and short-circuit boolean operators (&&, ||) use normal order evaluation, but applicative order evaluation is otherwise the default in many languages (notably not Haskell). 

In the example above, the result is the same no matter which order you choose, but that's not always the case. If evaluating an argument to a function results in an infinite loop or an error, and that argument doesn't have to be evaluated for the function to be evaluated, then normal order evaluation will work and applicative order won't.

Infinite loop in applicative order:

Have some things you want to number? Here's some Haskell code that zips an infinite list of natural numbers with a finite list:

zip [1..] [234, 573, 841]

Because Haskell uses normal order evaluation, it can have infinite lists, because it doesn't have to evaluate them. zip only needs as many items as the smaller list has, and the smaller list is finite, so it stops after taking three items out of the infinite list. Languages that use applicative order evaluation would use a range function here, because they would have to evaluate the infinite list and you don't have time for that.

Error in applicative order:

Say a is going to be either a list or an integer, and you want to return the length of the list or the value of the integer, and asking for the length of an integer raises an error. This will work since if is evaluated in normal order, but in applicative order, (length a) would be evaluated even if (list? a) were false, and you would get an error.

(if (list? a) (length a) a)

But normal order evaluation is not always better, and I'll go through why in the next post.

Sources:

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-10.html#%_sec_1.1.5,