CS61A

Posted on | Post modified:
Words count in article: 3k

This note is intended to record some useful details in the course CS61A in UCB. Since this class is designed for newbie, I will go through it quickly and just write down some meaningful and interesting details for me, like implementing “quine” in python3.

Homework1

Quine

Write a one-line program that prints itself, using only the following features of the Python language:

  • Number literals
  • Assignment statements
  • String literals that can be expressed using single or double quotes
  • The arithmetic operators +, -, *, and /
  • The built-in print function
  • The built-in eval function, which evaluates a string as a Python expression(运行字符串中存储的指令)
  • The built-in repr function, which returns an expression that evaluates to its argument(返回官方字符串，如果没有repr，那么输出的字符串两边将没有点)
1
s = 'print("s = " + repr(s) + "; eval(s)")'; eval(s)

here is the difference between repr and str:

  • str() is used for creating output for end user while repr() is mainly used for debugging and development. repr’s goal is to be unambiguous and str’s is to be readable. For example, if we suspect a float has a small rounding error, repr will show us while str may not.
  • repr() compute the “official” string representation of an object (a representation that has all information about the abject) and str() is used to compute the “informal” string representation of an object (a representation that is useful for printing the object).
  • The print statement and str() built-in function uses str to display the string representation of the object while the repr() built-in function uses repr to display the object.

Lab 1

  1. The statement True and 13 will return 13

    It turns out that the and statement will return the final variable if the whole statement is true.

  2. It should be noticed that in python 3, all the operation / is float operating, which is different to C++ and Java. And the operation // is the same as those in C++ and Java.

  3. When Python executes a return statement, the function terminates immediately. If Python reaches the end of the function body without executing a return statement, it will automatically return None.

    Notice also that print will display text without the quotes, but return will preserve the quotes.

Higher-Order Functions

PPT: High order function includes the vivid description about high order function and lambda expressions

the difference between high order function and lambda expressions:

• Both create a function with the same domain, range, and behavior.
• Both bind that function to the name square.
• Only the def statement gives the function an intrinsic name, which shows up in
environment diagrams but doesn’t affect execution (unless the function is printed).

Homework 2

To fully understand the application about the recursion method and return some function pointer in python 3, we should abandon the previous mind in C++ and Java which is like by using the parameters this functions have, we can do anything. However, in the recursion method, we could even ask for more parameters, and based on that, we could achieve something better.

Implement a function make_repeater so that make_repeater(f, n)(x) returns f(f(...f(x)...)), where f is applied n times. That is, make_repeater(f, n) returns another function that can then be applied to another argument. For example, make_repeater(square, 3)(42) evaluates to square(square(square(42))). Yes, it makes sense to apply the function zero times! See if you can figure out a reasonable function to return for that case. You may use either loops or recursion in your implementation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def make_repeater(f, n):
    """Return the function that computes the nth application of f.

    >>> add_three = make_repeater(increment, 3)
    >>> add_three(5)
    8
    >>> make_repeater(triple, 5)(1) # 3 * 3 * 3 * 3 * 3 * 1
    243
    >>> make_repeater(square, 2)(5) # square(square(5))
    625
    >>> make_repeater(square, 4)(5) # square(square(square(square(5))))
    152587890625
    >>> make_repeater(square, 0)(5)
    5
    """
    def h(x):
        ans = x
        for i in range(0, n):
            ans = f(ans)
        return ans

    return h

lab 2

What would python display?

  1. What would python display?

    1
    2
    3
    4
    >>> b = lambda x: lambda: x  # Lambdas can return other lambdas!
    >>> c = b(88)
    >>> c
    Function

    这里有一个很简单的记忆方法，那就是有几个lambda，它就需要接收几次参数；如果接收的参数次数不对，那么肯定是一个lambda表达式

  2. What would python display?

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    >>> # Try drawing an environment diagram if you get stuck!
    >>> higher_order_lambda = lambda f: lambda x: f(x)
    >>> def cake():
    ...    print('beets')
    ...    def pie():
    ...        print('sweets')
    ...        return 'cake'
    ...    return pie
    >>> chocolate = cake()
    beets # pie just didn't run
    >>> chocolate()
    sweets # now run the pie
    'cake' # return 'cake'
    >>> more_chocolate, more_cake = chocolate(), cake
    sweets # output the print information but not return information

lab 4

  1. Recall that empty lists, [], are false-y values. Therefore, you can use an if statement like the following if you only want to do operations on non-empty lists:

    1
    2
    if lst:
        # Do stuff with the elements of list

    This is equivalent to:

    1
    2
    if len(lst) > 0:
        # Do stuff

  2. List Comprehensions: The syntax is designed to read like English: “Compute the expression for each element in the sequence if the conditional is true for that element.”

  3. The summation of two list is equal to combine all the elements in two lists into one list. 

    1
    2
    if len(lst) > 0:
        # Do stuff

Data Abstraction, Mutable Functions & Generators

从本节开始记录中文的笔记，一是因为要推送到知乎上面，因此没有必要使用英文；二是因为目前自己的英语写作能力还不强，即便是自顾自地写，也没有人给反馈，没有办法提升。

Trees

Q1: Replace Leaf

题目：Define replace_leaf, which takes a tree t, a value old, and a value new. replace_leaf returns a new tree that’s the same as t except that every leaf value equal to old has been replaced with new.

如果按照C++或者Java的思想，将会通过for循环遍历整棵树，然后首先作一份copy之后修改；可是python的for-each loop不支持这样子做，同时对数据进行抽象的要求也不允许直接越过抽象，因此这里对我来讲就很神奇。

1
2
3
4
5
6
7
8
9
10
11
def replace_leaf(t, old, new):
    """Returns a new tree where every leaf value equal to old has
    been replaced with new."""
	  for branch in branches(t):
        if is_tree(branch):
            replace_leaf(branch, old, new)
        else:
            if branch == old:
                branch = new

    return temp

第一次编程我是这么写的，可是因为for-each loop并不能对枚举到的变量进行修改，因此是一种错误的做法，并且这里是直接对原树进行了修改。

1
2
3
4
5
6
7
8
9
10
11
def replace_leaf(t, old, new):
    """Returns a new tree where every leaf value equal to old has
    been replaced with new."""
    if is_leaf(t):
        if label(t) == old:
            return tree(new)
        else:
            return t
    else:
        temp = [replace_leaf(b, old, new) for b in branches(t)]
        return tree(label(t), temp)

这是正确的做法，其中用到了python的特性，list comprehension。这个特性使用得恰到好处，在创建一棵新树的同时进行修改。另外一个需要注意的点是，对于不需要进行修改的叶结点，直接返回了原树的叶结点，这个操作能够避免创建多余的对象。

Mobile

Q2: Weights

Implement the weight data abstraction by completing the weight constructor and the size selector so that a weight is represented using a two-element list where the first element is the string 'weight'. The total_weightexample is provided to demonstrate use of the mobile, side, and weight abstractions.

第一次接触测试驱动开发，感觉很新奇：通过读测试样例来推敲具体应该如何设计代码

Mutable functions

关于可变变量与不可变变量的内部剖析

总结一下：

  • 可变变量包括dic, set, list

    如果对其中的元素进行增删改查，不会创建新的对象，而只是在原始的对象上面进行操作

  • 不可变变量包括int, str, tuple, float

    它们首先是不可变的，不可以对其中的某个元素进行修改

    如果要修改，那么必定变量本身就会被修改，就是说在内存中的位置也将发生改变

  • 同时也正是因为这个机制以及higher-order function，所以才有了nonlocal的出现，这是介于global 以及local 之间的一种变量，是相对于C++以及Java的一种特性。它使得我们可以更加灵活地掌控函数的state。联想到“万物皆对象”的原则，实际上这是把函数也视为了一种对象呀！通过Higher-order function引入了函数的实例

    必须通过nonlocal来确定，当前的这个与parent framwork中某个变量同名的变量，应该绑定到sub-def framework中，还是parent framework中

    值得注意的是，对于dic, set, list是不需要主动non-local的，可以直接在sub-def framework中使用，我想这个跟对其中的元素进行修改不改变它们的内存地址有关

    可是对于int, str, tuple, float，如果想要修改的是parent framework中的变量，那么就必须首先声明才可以使用

    上述的情形只是需要在sub-def framework中对parent framework中的变量进行修改的时候才会出现，如果只是输出其中的信息，是不必关心这个特性的

这里给出一些关于non-local的好处：

In general, so long as we never modify data objects, we can regard a compound data object to be precisely the totality of its pieces. For example, a rational number is determined by giving its numerator and its denominator. But this view is no longer valid in the presence of change, where a compound data object has an “identity” that is something different from the pieces of which it is composed. A bank account is still “the same” bank account even if we change the balance by making a withdrawal; conversely, we could have two bank accounts that happen to have the same balance, but are different objects.

Despite the complications it introduces, non-local assignment is a powerful tool for creating modular programs. Different parts of a program, which correspond to different environment frames, can evolve separately throughout program execution. Moreover, using functions with local state, we are able to implement mutable data types. In fact, we can implement abstract data types that are equivalent to the built-in list and dict types introduced above.

Q5: Counter

Define a function make_counter that returns a counter function, which takes a string and returns the number of times that the function has been called on that string.

method: dic.get(self, default_value)

通过本题，可以进一步掌握Higher order function & dictionary

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def make_counter():
    """Return a counter function.

    >>> c = make_counter()
    >>> c('a')
    1
    >>> c('a')
    2
    >>> c('b')
    1
    >>> c('a')
    3
    >>> c2 = make_counter()
    >>> c2('b')
    1
    >>> c2('b')
    2
    >>> c('b') + c2('b')
    5
    """
    count = {}
    def counter(string):
        count[string] = count.get(string, 0) + 1
        return count[string]

    return counter

Q7: Password Protected Account

Write a version of the make_withdraw function that returns password-protected withdraw functions. That is, make_withdraw should take a password argument (a string) in addition to an initial balance. The returned function should take two arguments: an amount to withdraw and a password.

下面是我的代码，超丑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def make_withdraw(balance, password):
    """Return a password-protected withdraw function.

    >>> w = make_withdraw(100, 'hax0r')
    >>> w(25, 'hax0r')
    75
    >>> error = w(90, 'hax0r')
    >>> error
    'Insufficient funds'
    >>> error = w(25, 'hwat')
    >>> error
    'Incorrect password'
    >>> new_bal = w(25, 'hax0r')
    >>> new_bal
    50
    >>> w(75, 'a')
    'Incorrect password'
    >>> w(10, 'hax0r')
    40
    >>> w(20, 'n00b')
    'Incorrect password'
    >>> w(10, 'hax0r')
    "Your account is locked. Attempts: ['hwat', 'a', 'n00b']"
    >>> w(10, 'l33t')
    "Your account is locked. Attempts: ['hwat', 'a', 'n00b']"
    >>> type(w(10, 'l33t')) == str
    True
    """
    attempts = []
    def foo(money, input_pwd):
        nonlocal password, balance

        if len(attempts) == 3:
            return "Your account is locked. Attempts: " + str(attempts)

        if password != input_pwd:
            attempts.append(input_pwd)
            return 'Incorrect password'
        else:
            if money <= balance:
                balance -= money
                return balance
            else:
                return 'Insufficient funds'

    return foo

下面是别人家的代码，很优雅

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def make_withdraw(balance, password):
    """Return a password-protected withdraw function."""
    attempts = []
    def withdraw(amount, password_attempt):
        nonlocal balance
        if len(attempts) == 3:
            return 'Your account is locked. Attempts: ' + str(attempts)
        if password_attempt != password:
            attempts.append(password_attempt)
            return 'Incorrect password'
        if amount > balance:
            return 'Insufficient funds'
        balance = balance - amount
        return balance
    return withdraw

Implicit Sequences

一个序列不需要整个都显式地放在内存中，也就是说，我们可以构造一个对象，它能够按需访问序列中的数据。Python中，range就是这样的一个例子，如果我们输入了一个范围非常大的range，可以发现内存的占用并不很大，因为只保存了range的端点信息，而不是全部的数据都放入了内存。这称为lazy computation.

In computer science, lazy computation describes any program that delays the computation of a value until that value is needed.

关于for语句，其内部也是lazy的。

1
2
3
4
5
6
>>> counts = [1, 2, 3]
>>> for item in counts:
        print(item)
1
2
3

等价于

1
2
3
4
5
6
7
8
9
10
>>> items = iter(counts)
>>> try:
        while True:
            item = next(items)
            print(item)
    except StopIteration:
        pass
1
2
3

Generators

Q9: Generate Paths

Define a generator function generate_paths which takes in a tree t, a value x, and yields each path from the root of t to a node that has label x. Each path should be represented as a list of the labels along that path in the tree. You may yield the paths in any order.

本题一方面介绍了产生器，一方面进一步阐明了Python中使用Higher-order function以封装、OOP的思维完成特定需求的方法。另外在本题里面，我还学到了关于深拷贝和浅拷贝。以上两点都让我进一步从C++中脱离出来，更好地学习了Python。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def generate_paths(t, x):
    """Yields all possible paths from the root of t to a node with the label x
    as a list."""
    result = []
    paths = []
    paths.append(label(t))

    def wtf(t, x):
        if label(t) == x:
            result.append(copy.deepcopy(paths))
        for i in branches(t):
            paths.append(label(i))
            wtf(i, x)
            paths.pop()
    wtf(t, x)

    return result.__iter__()

Lab 6: Object Oriented Programming

Q2: What would Python display?

  1. 在Python中，类属性是可以在外部进行修改和访问的，并且可以直接影响到实例属性对其的访问

    这是因为类属性是内部外部公有的

0%