FP Notes Feedback

[parthsarin]

Functional Programming

Really stellar job, @cooper-mj! You did a really comprehensive job of capturing what we had in the notes last year. I think some of this information should be cut out in lieu of our discussions this time around and I have a few suggestions about how to expand on some details.

General comment: can we please reorder to follow the Learning Goals and modify motivation appropriately?

What is Functional Programming?

I love that we're drawing the connection to OOP but I think that most of the other references (declarative programming, structured programming) will be lost on students or, even worse, confuse them.

For example, I can image a (particularly confused) student reading "in Declarative Programming, the programmer specifies the desired result and leaves it up to the computer to figure out how to obtain it" and thinking that there's a way to code where they don't have to do anything and their will do all the work! Admittedly, that is what the sentence sounds like--DP is most easily seen through database queries, but that's far too off-topic to get into, imo.

These definitions also bend the definitions of words that we've established. Most notably, we've already defined control flow as ordering execution using loops and if/else statements. When we discussed classes, we never talked about them in relation to "control flow" and centering the these definitions around control flow creates a lot of cognitive dissonance for me.

We did this squared_divisible_by_2_9 thing in lecture before and, IMO, we shouldn't be introducing code this early, especially since the only point is "it does not use any stored function state, nor any for or if statements." This feels a little bit like "look at this code without variables and loops!" and it sorta gives me that feeling that I get when I'm looking at a codebase with libraries I've never used for the first time.

It is likely the case that, in your daily programming life, you will use many different paradigms: some problems you may choose to approach with an Object-Oriented minset, while you find that other problems lend themselves more easily to a Declarative paradigm. It is also the case that programming languages tend to incline themselves more toward some paradigms than others. Query languages like SQL were designed with the Declarative paradigm in mind: specifying a SQL query is indicating to the computer the desired result (such as which data to select from a database), and the language determines how to make the appropriate data selection. As another example, C would be a poor choice of programming language for Object-Oriented programming, since it does not natively support classes: a programmer seeking to do Object-Oriented programming would be better served by a language such as Python or C++.

"mindset" is misspelled.

Getting into SQL, as I mentioned earlier, is a little bit strange if people haven't seen it before. I think, in this class, we have had this unspoken rule that the only other languages we'll invoke in detail are C++ and Java, and we'll only invoke them to show topics where they do similar things to each other, but differently from Python. Students will be familiar with those language design decisions from 106B. On the other hand, I don't think they'll be prepared for the level of detail with which you invoke SQL here.

By contrast, invocation of C is really good! It doesn't assume much knowledge other than that C "does not natively support classes", which you spell out explicitly. Students should already know what classes are from 106B and the OOP lecture (and that's not true for queries).

Overall, while this is a really informative section, I don't think it does a good job of motivating the rest of the content and, at times, assumes too much of students. Consider moving this to some sort of appendix/footnote, maybe?

First-Class Functions - Functions are Objects!

I think this is a holdover from the fact that I didn't get this far in the Functions lecture. I think it works better if we move this to that set of course notes.

Lambda - Inline, Anonymous Functions

PEP nitpick: there shouldn't be a space between the params and the colon, so lambda params: expression.

Recall that an "expression" refers to a piece of code which is evaluated to return a value: the result of this expression is the return value of the lambda. Below, we give a simple example of defining a lambda function which accepts two arguments and returns the sum of their squares.

I think this is a weird use of "recall" because I don't think we ever explicitly defined expression; we just kinda used that word. Maybe instead: expression just refers to a piece of Python code that will be evaluated: the result of this expression is the return value of the lambda.

"Return value of the lambda" might be confusing if students don't make the connection to the notion of a Python function. You define lambda as "an anonymous, inline function." That definition does, in fact, use the word "function", so students ought to make the connection, but it qualifies it as "anonymous" and "inline" which could be confusing for people seeing this for the first time causing students to not make that connection and then tripping over themselves when they see the reference to the lambda's return value.

(lambda x, y : x**2 + y**2)(3, 5) # => 34

Style check: (lambda x, y: x**2 + y**2)(3, 5) # => 34

Iterators and Generators - Representing Infinity

One of the strengths of the Functional programming paradigm is that it allows for concrete representations of infinite-length objects.

This isn't attributable to FP: you can have classes/imperative structures that represent infinite-length objects. For example, here's a class that doesn't inherently use any functional structures, but "represents" an infinite object:

class Fibbi:
    def __init__(self):
        self.curr = 0
        self.next = 1

    def __next__(self):
        self.curr, self.next = self.next, self.next + self.curr
        return self.curr

And that doesn't even invoke an iterator! (Though it could, with return self).

Functional programming is uniquely capable of representing infinite-length objects (in comparison with the other paradigms we have briefly discussed) due to its lack of reliance on state: in the Functional paradigm, we do not need to store every element of an infinite-dimentional list over the course of our program.

The above example I gave does maintain an infinite-length object by maintaining state. In fact, it's difficult to write the Fibonacci series without "rel[ying] on state"... the best thing I could come up with is the following, in Haskell:

fibbi = 1 : 1 : zipWith (+) fibbi (tail fibbi)

And I can't think of an elegant, purely functional way to do it in Python (can you?)...

In reality, it's not FP's reliance on state that allows you to represent infinite things in Python, IMO! It's just being clever about what you choose to represent in the state (e.g., only the two latest numbers in the sequence).

This means that we can apply a for or while loop over elements of these objects, and we will obtain something useful.

It's not so much "obtain something useful" as it is "Python allows it."

At a higher level of sophistication, an object of a given type is an iterable if either:

• The iter() method is defined for the type. (By "method", I am referring to a function bound to an instance of a class - for a refresher on classes and object oriented programming, check out our notes on OOP). We will discuss the behaviour of the iter() method in the following segment.

I don't like the idea of exposing the __iter__ method to students in this much detail, especially not before they've seen OOP. As we discussed, I think that we should probably just show off iterators and how they connect to generators. Maybe we can gesture at __iter__ but this is the first time students will see magic methods and they deserve a more thorough treatment, IMO.

Iterators - One Step Further

I think much of this section is, perhaps a bit too technical. If you'd really like to keep this material (and honestly, I'm not sure why we want to get into this much detail), we can revisit it in OOP?

I'd totally be open to you rewriting OOP so that it has an example of building a custom iterator.

As a subtlety, and an aside, the reader will recall that earlier, when we called __iter__() on a dictionary, we obtained a dict_keyiterator. We can then make the connectin between this name, dict_keyiterator, and the behaviour of a for loop when called on a dictionary; namely, looping over a dictionary iterates over only the keys (hence the name dict_keyiterator), and not the values. This is a direct result of the way in which dict_keyiterator is defined differently from its list_iterator and tuple_iterator counterparts.

Typo: "connectin"

Why is this necessary? Is this just saying "a dictionary iterates over its keys" or are you trying to make significance of the fact that it's called a dict_keyiterator? I don't know if you should make too much significance of that name since it's an implementation detail, I believe...

Generators

This poses a problem shoudl we wish to represent an unbounded stream of data.

Typo: "shoudl"

Also, I think "infinite" makes a bit more sense than unbounded. Unbounded could also imply that we don't know how large the values will be, e.g.

In Python, a "generator" is a function which behaves like an iterator. Rather than a standard function, which returns a single value (or multiple values) once it is called, a generator is constructed so that, when called, it yields the next term in the sequence defined by the generator.

Not quite. When a generator function is called, it returns a generator object that has a __next__ method. The object also has an __iter__ method, but that just returns self. Maybe this object is best described as a "lazy iterator."

At this point, we can treat the generator object just as we would treat any other iterator object: crucially, this generator object is defined with a __next__() method. When the __next__() method of the generator object is called, execution of the generate_fib() function will commence, until a yield statement is reached, at which point the value referenced by the yield will be returned to the caller, and execution of the generate_fib() function will pause. The next time that the __next__() method is called, execution of the generate_fib() function will resume, until a yield statement is reached - at that point, again, execution will pause and the value referenced by the yield will be returned to the caller. Reaching a return statement during execution of a generator function will raise a StopIteration exception.

Really nice explanation!

We can convert generator objects to other data structures, by calling a constructor function such as list() or tuple() on a generator object. Calling the list() constructor (this is without loss of generality - we could equivalently be discussing the tuple() constructor) on a generator object abides by something akin to the following procedure:

Do you need to provide the code example? That makes me kind of nervous... Can you just say that it "reads the contents of the generator into a list"? This way we avoid (a) redefining the list function and distinguishing that generator_object is a generator only by its name, (b) risking that we're wrong about this implementation (although it looks correct, but I haven't checked out the CPython implementation).

This works great when generator_object generates a sequence of finite size; if not, your computer's in for a bit of a bad day. (It will infinitely loop until the operating system ends the program since your program will have eaten all the available RAM).

Correct me if I'm wrong, but wouldn't it just swap to disk at that point? After that I think Python will probably raise a MemoryError?

map and filter - Functional Programming Foundations

Three concepts which are fundamental to functional programming are map and filter: these functions support the transformation of arrays without relying on state.

Michael counting mod 1 over here.

It turns out that map accepts either a finite data structure as an interable

Typo: "interable"

It turns out that map accepts either a finite data structure as an interable (list, tuple, etc.), or a generator object.

Is that true? I thought map could accept infinite iterables too? As a silly example:

class MapMe:
    def __iter__(self):
        return self

    def __next__(self):
        return 0

map(lambda e: e + 1, MapMe()) # => <map object at ...>

Instead, the map function circumvents this issue by returning a "map object," a generator, which yields elements of the mapped data structure through a call to the __next__() method.

A small inconsistency: here you're using "generator" to refer to "generator object" where before it was referring to "generator function."

The filter function behaves similarly to the map function: it takes in two arguments, a predicate, and an iterable, and it returns only the elements of the iterable for which the predicate is True. The syntax is as follows:

Beautiful, really solid explanation! If you wanted to be explicit, you could say "returns an iterable that stores only the elements of the input for which the predicate is True.

Due to the stability of Python's math library, this is a pretty safe assumption

Huh! Didn't know that!!

list(
    filter(lambda x : math.sqrt(x) % 1 == 0, lst)
)                                                 # => [1, 9]

A few style notes: first, why the line break? second, the comment should go on the same line as the ).

Decorators

Since functions are objects, we've also passed them as parameters into other functions, as we saw when we used lambdas (which are just smaller, cuter functions) to call the map and filter functions.

Cuter indeed

A "decorator," in brief, is when we pass a function into a function to return a function.

I don't think "to" is the correct operative here. Maybe "which returns"?

(and they are - they're often the most difficult topic for students of CS41)

I don't like this line because (a) I don't think it's true -- I think students found the data model & gc stuff to be trickier, and (b) I don't think it serves a significant pedagogical purpose. What about "Decorators may sound complicated, but you're not alone in thinking that! We're going to build up to them slowly ..."?

IMO, that's better, but still not great: they haven't even seen decorators yet. Why are we telling them to be afraid and get their stuffed unicorns so early?

Functions as Arguments

It's here that we wish to explicitly blur the line between lambdas and functions, if it was not already sufficiently blurred: lambdas are functions.

I don't understand what this means. Were we not saying this before? How is presentation supposed to be different?

Below, we define our own function operation (called fun_polynomial), and we call our cs41_map function using the function that we've just defined as an argument:

Why don't we just pass fun_polynomial directly into map? I'm confused. Shouldn't students have already seen how to pass functions into other functions in the First-Class Functions section? Maybe we should revisit this directly in the map section?

What about all those cute examples from the document like where some caller gives a "value" or "loss" function, pretty print function, etc.

Functions as Return Values

Again, see the document. We brainstormed: Outer function executes things that only need to be run once but inner function can be used repeatedly.

• Autograder? Testing harness where the outer function pulls parameters and names and the inner function repeatedly runs them.

Decorators

By this point, there should be two core takeaways about what it means to say the Python functions are objects:

Can we remove the word "core"?

A "decorator" in Python is defined as any function which is used to modify a function or a class. For the purposes of these notes, we will stick to modifying functions, but it may be useful to understand that these same principles can be applied to decorate classes as well.

I love how you handled this! 😊

Let's take a look at our first decorator. This decorator is going to take in a function (denoted fn), and will return a function (denoted fn_prime).

Nitpick: fn_prime makes me think of prime numbers, not prime in the sense of math notation/derivatives. I think students will be the same way. Rename to out?

# Arguments: (2, 3) {'c': 1}

Typo: there should be a comma between the tuple and dict.

Here, the line foo = print_arguments(foo) redefines foo as the function returned from our print_arguments decorator. Then, calling our decorated version of foo both prints out the arguments passed into it, and returns the correct value.

Can we first see it as print_arguments(foo)(2, 1, c=3)? I think that's what most people would initially think to do.

Then you could say, "but what if we wanted this to be the behavioUr every time foo is called? We could then ..."

Memoization - Decorators in Action!

One such example is memoization.

Yo what's memoization?

Calling recursive_fib(5) is fine: any modern computer can easily resolve the stackframes required to compute such a function. Calling recursive_fib(50)? That's a different story - my computer eventually got there, but it needed to take its time and do some serious thinking to resolve all the stackframes demanded by this function call.

Why does it do this? You should at least state that recursive_fib(n) is O(2^n).

The solution, as you may recall from CS106B, is to memoize the function

I don't think there's just one "solution" and not everyone had memoization in 106B. I think only people that had Keith.

We can test our memoized decorator: previously, the below computations would have taken an unthinkably long time to run, but with our decorator, they can be computed in a matter of seconds.

I think you need to explain why this speeds up recursive_fib