René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"FP Notes Feedback","articleBody":"# Functional Programming\r\nReally 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.\r\n\r\nGeneral comment: can we please reorder to follow [the Learning Goals](https://docs.google.com/document/d/1PeY5Uq7XkpHt_RmSZJCZNYOyUhW0FFCvVCLqf2fe1_c/edit) and modify motivation appropriately?\r\n\r\n## What is Functional Programming?\r\nI 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. \r\n\r\nFor 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.\r\n\r\nThese 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.\r\n\r\nWe 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.\r\n\r\n\u003e 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++.\r\n\r\n\"mindset\" is misspelled.\r\n\r\nGetting 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.\r\n\r\nBy 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).\r\n\r\nOverall, 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?\r\n\r\n## First-Class Functions - Functions are Objects!\r\nI 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.\r\n\r\n## Lambda - Inline, Anonymous Functions\r\nPEP nitpick: there shouldn't be a space between the params and the colon, so `lambda params: expression`.\r\n\r\n\u003e 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.\r\n\r\nI 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`.\r\n\r\n\"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.\r\n\r\n\u003e `(lambda x, y : x**2 + y**2)(3, 5)      # =\u003e 34`\r\n\r\nStyle check:  `(lambda x, y: x**2 + y**2)(3, 5) # =\u003e 34`\r\n\r\n## Iterators and Generators - Representing Infinity\r\n\r\n\u003e One of the strengths of the Functional programming paradigm is that it allows for concrete representations of infinite-length objects.\r\n\r\nThis 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:\r\n\r\n```python\r\nclass Fibbi:\r\n    def __init__(self):\r\n        self.curr = 0\r\n        self.next = 1\r\n\r\n    def __next__(self):\r\n        self.curr, self.next = self.next, self.next + self.curr\r\n        return self.curr\r\n```\r\n\r\nAnd that doesn't even invoke an iterator! (Though it could, with `return self`). \r\n\r\n\u003e 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.\r\n\r\nThe 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:\r\n\r\n```haskell\r\nfibbi = 1 : 1 : zipWith (+) fibbi (tail fibbi)\r\n```\r\n\r\nAnd I can't think of an elegant, purely functional way to do it in Python (can you?)...\r\n\r\nIn 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).\r\n\r\n\u003e This means that we can apply a `for` or `while` loop over elements of these objects, and we will obtain something useful.\r\n\r\nIt's not so much \"obtain something useful\" as it is \"Python allows it.\"\r\n\r\n\u003e At a higher level of sophistication, an object of a given type is an iterable if either:\r\n\u003e * 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.\r\n\r\nI 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.\r\n\r\n### Iterators - One Step Further\r\nI 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?\r\n\r\nI'd totally be open to you rewriting OOP so that it has an example of building a custom iterator.\r\n\r\n\u003e 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.\r\n\r\nTypo: \"connectin\"\r\n\r\nWhy 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...\r\n\r\n### Generators\r\n\r\n\u003e This poses a problem shoudl we wish to represent an unbounded stream of data.\r\n\r\nTypo: \"shoudl\"\r\n\r\nAlso, 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.\r\n\r\n\u003e 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.\r\n\r\nNot 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.\"\r\n\r\n\u003e 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.\r\n\r\nReally nice explanation!\r\n\r\n\u003e 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:\r\n\r\nDo 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).\r\n\r\n\u003e 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).\r\n\r\nCorrect 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`?\r\n\r\n## `map` and `filter` - Functional Programming Foundations\r\n\r\n\u003e Three concepts which are fundamental to functional programming are `map` and `filter`: these functions support the transformation of arrays without relying on state.\r\n\r\nMichael counting mod 1 over here.\r\n\r\n\u003e It turns out that `map` accepts either a finite data structure as an interable\r\n\r\nTypo: \"interable\"\r\n\r\n\u003e It turns out that `map` accepts either a finite data structure as an interable (`list`, `tuple`, etc.), or a generator object.\r\n\r\nIs that true? I thought `map` could accept infinite iterables too? As a silly example:\r\n\r\n```python\r\nclass MapMe:\r\n    def __iter__(self):\r\n        return self\r\n\r\n    def __next__(self):\r\n        return 0\r\n\r\nmap(lambda e: e + 1, MapMe()) # =\u003e \u003cmap object at ...\u003e\r\n```\r\n\r\n\u003e 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.\r\n\r\nA small inconsistency: here you're using \"generator\" to refer to \"generator object\" where before it was referring to \"generator function.\"\r\n\r\n\u003e 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:\r\n\r\nBeautiful, 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`.\r\n\r\n\u003e Due to the stability of Python's `math` library, this is a pretty safe assumption\r\n\r\nHuh! Didn't know that!!\r\n\r\n\u003cblockquote\u003e\r\n\u003cdiv class=\"highlight higlight-source-python\"\u003e\r\n\u003cpre\u003e\r\nlist(\r\n    filter(lambda x : math.sqrt(x) % 1 == 0, lst)\r\n)                                                 # =\u003e [1, 9]\r\n\u003c/pre\u003e\r\n\u003c/div\u003e\r\n\u003c/blockquote\u003e\r\n\r\nA few style notes: first, why the line break? second, the comment should go on the same line as the `)`.\r\n\r\n## Decorators\r\n\r\n\u003e 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.\r\n\r\nCuter indeed\r\n\r\n\u003e A \"decorator,\" in brief, is when we pass a function into a function to return a function.\r\n\r\nI don't think \"to\" is the correct operative here. Maybe \"which returns\"?\r\n\r\n\u003e (and they are - they're often the most difficult topic for students of CS41)\r\n\r\nI don't like this line because (a) I don't think it's true -- I think students found the data model \u0026 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 ...\"?\r\n\r\nIMO, 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?\r\n\r\n### Functions as Arguments\r\n\r\n\u003e 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.\r\n\r\nI don't understand what this means. Were we not saying this before? How is presentation supposed to be different?\r\n\r\n\u003e 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:\r\n\r\nWhy 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?\r\n\r\n\u003e \r\n\r\nWhat about all those cute examples from the document like where some caller gives a \"value\" or \"loss\" function, pretty print function, etc.\r\n\r\n### Functions as Return Values\r\n\r\nAgain, see the document. We brainstormed: Outer function executes things that only need to be run once but inner function can be used repeatedly.\r\n* Autograder? Testing harness where the outer function pulls parameters and names and the inner function repeatedly runs them.\r\n\r\n### Decorators\r\n\r\n\u003e By this point, there should be two core takeaways about what it means to say the Python functions are objects:\r\n\r\nCan we remove the word \"core\"?\r\n\r\n\u003e 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.\r\n\r\nI love how you handled this! 😊\r\n\r\n\u003e 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`).\r\n\r\nNitpick: `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`?\r\n\r\n\u003e `# Arguments: (2, 3) {'c': 1}`\r\n\r\nTypo: there should be a comma between the tuple and dict.\r\n\r\n\u003e 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.\r\n\r\nCan we first see it as `print_arguments(foo)(2, 1, c=3)`? I think that's what most people would initially think to do.\r\n\r\nThen you could say, \"but what if we wanted this to be the behavioUr every time `foo` is called? We could then ...\"\r\n\r\n### Memoization - Decorators in Action!\r\n\r\n\u003e One such example is memoization.\r\n\r\nYo what's memoization?\r\n\r\n\u003e 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.\r\n\r\nWhy does it do this? You should at least state that `recursive_fib(n)` is `O(2^n)`.\r\n\r\n\u003e The solution, as you may recall from CS106B, is to memoize the function\r\n\r\nI don't think there's just one \"solution\" and not everyone had memoization in 106B. I think only people that had Keith.\r\n\r\n\u003e 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.\r\n\r\nI think you need to explain why this speeds up `recursive_fib`","author":{"url":"https://github.com/parthsarin","@type":"Person","name":"parthsarin"},"datePublished":"2020-09-06T05:03:08.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":0},"url":"https://github.com/12/course-reader/issues/12"}