CMPSC-132 Programming and Computation II - Lecture Notes (PDF)

CMPSC-132: Programming and Computation II Department of Computer Science & Engineering The Pennsylvania State University 1. Functional Programming Functional programming decomposes a problem into a set of functions. In a functional...

CMPSC-132: Programming and Computation II Department of Computer Science & Engineering The Pennsylvania State University 1. Functional Programming Functional programming decomposes a problem into a set of functions. In a functional program, input flows through a set of functions. Each function operates on its input and produces some output. Functional style discourages functions with side effects that modify internal state or make other changes that are not visible in the function’s return value. Functions that have no side effects at all are called purely functional. Avoiding side effects means not using data structures that get updated as a program runs; every function’s output must only depend on its input. However, it is difficult to avoid all side effects. Printing to the screen or writing to a disk file are examples of side effects. Functional programming can be considered the opposite of object-oriented programming. Objects are little capsules containing some internal state along with a collection of method calls that let you modify this state, and programs consist of making the right set of state changes. Functional programming wants to avoid state changes as much as possible and works with data flowing between functions. In Python you might combine the two approaches by writing functions that take and return instances representing objects in your application. Functional design may seem like an odd constraint to work under but it has theoretical and practical advantages for formal provability, molarity, composability and ease of debugging and testing. 1.1 Higher-Order functions We have seen that functions are a method of abstraction that describe compound operations independent of the particular values of their arguments. For example: def square(x): return x * x in the square function from above, we are not talking about the square of a particular number, but rather about a method for obtaining the square of any number. Of course, we could get along without ever defining this function, by always writing expressions such as 3 * 3, 9 * 9, 12 * 12, etc. This practice would suffice for simple computations such as square, but would become arduous for more complex examples such as fib (Fibonacci series). In general, lacking function definition would put us at the disadvantage of forcing us to work always at the level of the particular operations that happen to be primitives in the language (multiplication, in this case) rather than in terms of higher-level operations. Our programs would be able to compute squares, but our language would lack the ability to express the concept of squaring. One of the things we should demand from a programming language is the ability to build abstractions by assigning names to common patterns and then to work in terms of the names directly. Functions provide this ability. To express certain general patterns as named concepts, we will need to construct functions that 1 can accept other functions as arguments or return functions as values. Functions that manipulate functions are called higher-order functions. 1.1.1 Functions as arguments Consider the following two functions, which all compute summations. The first, sum_naturals, computes the sum of natural numbers up to n: def sum_naturals(n): total, k = 0, 1 while k >> 7 In general, Python style prefers explicit def statements to lambda expressions, but allows them in cases where a simple function is needed as an argument or return value. Such stylistic rules are merely guidelines; you can program any way you wish. However, as you write programs, think about the audience of people who might read your program one day and think if your program is easy to understand. 3 1.2.1 The map() function map() takes a function and a collection of items. It makes a new, empty collection, runs the function on each item in the original collection and inserts each return value into the new collection. It returns the new collection. r = map(function_to_apply, list_of_inputs) The code below is a simple map that takes a list of names and returns a list of the lengths of those names: name_lengths = map(len, ["Alex", "Sandy", "Jeffrey"]) print(list(name_lengths)) # >>> [4, 5, 7] The advantage of the lambda operator can be seen when it is used in combination with the map() function: squares = map(lambda x: x * x, [0, 1, 2, 3, 4, 5]) print(list(squares)) # >>> [0, 1, 4, 9, 16, 25] This is a map that squares every number in the passed collection and does not take a named function. It takes an anonymous, inlined function defined with lambda. The parameters of the lambda are defined to the left of the colon. The function body is defined to the right of the colon. The result of running the function body is implicitly returned. map() can be applied to more than one list, however, the lists must have the same length. First, turn the map into a list… Before Python 3, map() used to return a list, where each element of the result list was the result of the function applied on the corresponding element of the list or tuple. With Python 3, map() returns an iterator. 1.2.2 The filter() function filter() offers an elegant way to filter out all the elements of a sequence for which a function returns True: r = filter(function_to_apply, list_of_inputs) The function filter(function_to_apply, list_of_inputs) needs a function as its first argument. This function has to return a Boolean value and will be applied to every element of the list. The example below outputs 4 all the negative values in a sequence of numbers (In this example, the filter resembles a for loop but it is a faster built-in function): number_list = range(-5, 5) less_than_zero = filter(lambda x: x < 0, number_list) print(list(less_than_zero)) # Output: [-5, -4, -3, -2, -1] 1.2.3 The reduce() function reduce() is a really useful function for performing some computation on a list and returning the result. While map will apply a function over a sequence, producing a sequence as output, reduce will apply a function of two arguments cumulatively to the items in a sequence, in order to reduce the sequence to a single value. In Python 3, reduce() is not a core built-in function anymore and it has been moved to functools (still part of the standard library), thus, in order to use it you need to import it like this: from functools import reduce. To illustrate how reduce works, lets use as an example the product of a list of integers. The common way this task can be programmed in python is using a basic for loop: product = 1 list = [1, 2, 3, 4, 5] for num in list: product = product * num print(product) # Output: 120 Using reduce, the code above can be written like this: from functools import reduce product = reduce((lambda x, y: x * y), [1, 2, 3, 4, 5]) print(product) # Output: 120 The function reduce((lambda x, y: x * y), [1, 2, 3, 4, 5]) continually applies the lambda function to the sequence [1, 2, 3, 4, 5] returning a single value. 1 2 3 4 5 2 6 24 120 5 At first the first two elements of the sequence will be applied to the function. In the next step the function will be applied on the previous result and the third element of the list, continuing like this until just one element is left and returning this element as the result of reduce(). 1.3 Operators There are many built-in functions in Python that accept functions as arguments. An example is the filter() function that was used previously. However, there are some basic actions that use operators instead of functions (like +, [], or. operators). The operator module provides function versions of these operators. import operator operator.add(1, 6) # Output: 7 It is possible to create functions dynamically that can know which item to get from a list: import operator get_second = operator.itemgetter(1) get_second(['a', 'b', 'c', 'd']) # Output: 'b' The itemgetter() function will return a tuple if it is given more than one index. import operator get_two = operator.itemgetter(0, 2) get_two(['a', 'b', 'c', 'd']) # Output: ('a', 'c') A typical use for the itemgetter() function is as the key argument to a list sort. import operator band = [('Guitar', 'Jimmy'), ('Vocals', 'Robert'), ('Bass', 'John'), ('Drums', 'John')] sorted(band) [('Bass', 'John Paul'), ('Drums', 'John'), ('Guitar', 'Jimmy'), ('Vocals', 'Robert')] sorted(band, key=operator.itemgetter(1)) [('Guitar', 'Jimmy'), ('Drums', 'John'), ('Bass', 'John'), ('Vocals', 'Robert')] For more operators, read https://docs.python.org/3/library/operator.html 1.4 Function Decorators A function decorator is applied to a function definition by placing it on the line before that function definition begins: @myDecorator def aFunction(): print("inside aFunction") 6  When the compiler passes over this code, aFunction() is compiled and the resulting function object is passed to the myDecorator code, which does something to produce a function-like object that is then substituted for the original aFunction(). Function decorators are simply wrappers to existing functions. Putting the ideas mentioned above together, we can build a decorator. In this example lets consider a function that wraps the string output of another function in tags. def get_text(name): return "Dear {0}, Thank you for your note...".format(name) def p_decorate(func): def func_wrapper(name): return "{0}".format(func(name)) return func_wrapper my_get_text = p_decorate(get_text) print(my_get_text("John")) # Output: Dear John, Thank you for your note... A function that takes another function as an argument, generates a new function, augmenting the work of the original function, and returning the generated function so we can use it anywhere. To have get_text itself be decorated by p_decorate, we just have to assign get_text to the result of p_decorate: def get_text(name): return "Dear {0}, Thank you for your note...".format(name) def p_decorate(func): def func_wrapper(name): return "{0}".format(func(name)) return func_wrapper get_text = p_decorate(get_text) print(get_text("John")) # Output: Dear John, Thank you for your note... Another thing to notice is that our decorated function takes a name argument. All what we had to do in the decorator is to let the wrapper of get_text pass that argument. Because this is such a common programming idiom in Python, there is a special decorator syntax to simplify its use which is to mention the name of the decorating function before the function to be decorated. The name of the decorator should be perpended with an @ symbol: def p_decorate(func): def func_wrapper(name): return "{0}".format(func(name)) return func_wrapper @p_decorate def get_text(name): return "Dear {0}, Thank you for your note...".format(name) print(get_text("John")) # Output: Dear John, Thank you for your note... 7 In other words, this Python syntax: @some_decorator def some_function(): # statements is equivalent to: def some_function(): # statements some_function = some_decorator(some_function) Now, imagine you want to decorate the get_text function by 2 other functions to wrap a and tag around the string output. def get_text(name): return "Dear {0}, Thank you for your note...".format(name) def p_decorate(func): def func_wrapper(name): return "{0}".format(func(name)) return func_wrapper def strong_decorate(func): def func_wrapper(name): return "{0}".format(func(name)) return func_wrapper def div_decorate(func): def func_wrapper(name): return "{0}".format(func(name)) return func_wrapper With the basic approach, decorating get_text would be along the lines of: get_text = div_decorate(p_decorate(strong_decorate(get_text))) print(get_text("John")) With Python’s decorator syntax, same thing can be achieved with much more expressive power: @div_decorate @p_decorate @strong_decorate def get_text(name): return "Dear {0}, Thank you for your note...".format(name) print(get_text("John")) # Output: Dear John, Thank you for your note... One important thing to notice here is that the order of setting our decorators matters. If the order was different in the example above, the output would have been different. 8 The examples above are a little taste of how much you can do with decorators. They can give so much power and elegance to your program. In general, decorators are ideal for extending the behavior of functions that you do not want to modify. You can visit https://wiki.python.org/moin/PythonDecoratorLibrary for a great list of useful decorators. 9 Appendix 1. Iterators Iterators are a Python language feature that is an important foundation for writing functional-style programs. An iterator is an object representing a stream of data; this object returns the data one element at a time. A Python iterator must support a method called __next__() that takes no arguments and always returns the next element of the stream. If there are no more elements in the stream, __next__() must raise the StopIteration exception. Iterators don’t have to be finite, though; it’s perfectly reasonable to write an iterator that produces an infinite stream of data. The built-in iter() function takes an arbitrary object and tries to return an iterator that will return the object’s contents or elements, raising TypeError if the object doesn’t support iteration. Several of Python’s built-in data types support iteration, the most common being lists and dictionaries. An object is called iterable if you can get an iterator for it. You can experiment with the iteration interface manually: >>> L = [1,2,3] >>> it = iter(L) >>> it >>> it.__next__() # same as next(it) 1 >>> next(it) 2 >>> next(it) 3 >>> next(it) Traceback (most recent call last): File "", line 1, in StopIteration Python expects iterable objects in several different contexts, the most important being the for statement. In the statement for X in Y, Y must be an iterator or some object for which iter() can create an iterator. These two statements are equivalent: for i in iter(obj): print(i) for i in obj: print(i) Iterators can be materialized as lists or tuples by using the list() or tuple() constructor functions: >>> L = [1,2,3] >>> L = [1,2,3] >>> iterator = iter(L) >>> iterator = iter(L) >>> t = tuple(iterator) >>> a,b,c = iterator >>> t >>> a,b,c (1, 2, 3) (1, 2, 3) 10 Built-in functions such as max() and min() can take a single iterator argument and will return the largest or smallest element. The "in" and "not in" operators also support iterators: X in iterator is true if X is found in the stream returned by the iterator. You’ll run into obvious problems if the iterator is infinite; max(), min() will never return, and if the element X never appears in the stream, the "in" and "not in" operators won’t return either. Note that you can only go forward in an iterator; there’s no way to get the previous element, reset the iterator, or make a copy of it. Iterator objects can optionally provide these additional capabilities, but the iterator protocol only specifies the __next__() method. Functions may therefore consume all of the iterator’s output, and if you need to do something different with the same stream, you’ll have to create a new iterator. 11 References https://docs.python.org/3/library/functional.html https://docs.python.org/3/howto/functional.html https://www.tutorialspoint.com/python/index.htm https://pythonspot.com/en/python-lambda/ https://docs.python.org/3/howto/functional.html#iterators 12