编程的基本要素

• primitive expressions and statements: which represent the simplest entities the language is concerned with.
• means of combination: by which compound elements are built from simpler ones and
• means of abstraction: by which compound elements can be named and manipulated as units

primitive expressions and statements

• expression: 表达式，必然有返回值
• statement: 语句（过程语句），没有返回值

与lisp，scala（代码都是表达式）不同，python代码基本就是语句的序列，控制结构，赋值语句，返回语句都是简单的statement，而函数定义等则是复杂的。

表达式的展开（解析，求值）： 递归的将参数解析，最后形成 expression tree, node是可以返回值的子表达式。递归的过程：

1. 求各子表达式的值
2. 将表达式中代表过程的第一个值应用到代表于相应的实际参数，实际参数是形参代表的各子表达的值

表达式的解析过程中，会返回变量在此环境中所绑定的过程或者值。

将一个变量绑定到一个值，在python中通常是一个statement。

pure function and non-pure function

pure function:

• doest change anything(including the environment, screen, etc) but returen a value
• the value it returned doesnt change over time

方便测试和组合

定义方法

def square(x):
    return mul(x,x)

以上举例，定义中的x，叫做： formal parameter(形参)，提供了即将要计算的表达式的名字

def <name><formal parameters>:
    return <return expression

环境

这个environment更多指代：context，上下文。

An environment in which an expression is evaluated consists of a sequence of frames, depicted as boxes.

Each frame contains bindings, each of which associates a name with its corresponding value.

There is a single global frame. Assignment and import statements add entires to the friest frame of the current environment.

不同的语句使用不同的方式，来创建function的定义，定义的时候取名（intrinsic name），以后可以将它绑定给一个名字（bounding name）： def, define， intrinsic name只有一个，而bound name可以有许多个， bound name可以随意指向。

python中，function 是：func(formal parameters)

当一个方法被调用的时候， create a second local frame, which only accessible to that function

• bind the arguments（实参） to the names of the function's formal parameters in a new local frame.
• execute the body of the function in the environment that starts with this frame.

被执行的方法的环境包含两部分：1. local frame. 2. global frame contains every thing 。name evaluation从1开始往后找

而方法被定义的时候，只有方法的签名被处理了，一步完成，而方法体只有在被执行的时候，才会开启local frame，并且被处理。

high-order函数

普通函数，限制了自己的表达能力只能在具体参数，缺少进一步表达抽象， 总结出共有模式的能力。高阶函数的重大意义在于它们使得我们可以显式地以编程语言的元素来表达这些抽象，然后可以当成普通元素来对待。

另外，python提供了decorator语法，来进行函数的装饰

函数作为参数，通常是外围函数是通用的模式，而参数函数是某个功能的具体行为

计算黄金比例，开方等，计算方法是使用某个初始值，不断判断，如果达成，则返回，不成则优化初始值

def improve(update, close, guess):
    while not close(guess):
        guess = update(guess)
    return guess

当使用improve定义开方的时候，最好把update，close的定义在开方函数内，以免造成全局范围内有许多的小函数。

闭包：某个函数保存了定义它的那个环境中的变量的引用。

函数作为返回值，通常是组合小函数功能后的函数

1. 类似scala中, andThen, compose
2. 留下部分参数没有被填充, def add_some(x): return lambda y: x+y
3. 闭包了某个变量的函数

举例

牛顿法

一种迭代提升法，找到一个数学函数可以产生零值，零值被称为某些单参数的函数的root，这和某些数学问题很相似。

• square(x) - 16 = 0
• log base 2 of 32 => pow(2, x) - 32 = 0

def square_root(a):
    return find_root(lambda x: square(x)-a)

def logarithm(a, base=2):
    return find_root(lambda x: pow(base, x) - a)

不断寻找值接近0的x，当不够接近的时候，更新x的值继续迭代，如果初始值选的不好，那么计算可能不收敛。

• 迭代计算
• 更新x值
• 判断结果是否够好

# update x
def newton_update(f):
    def update(x):
        return x -f(x)/approx_derivative(f, x)
    return update
def approx_derivative(f, x , delta=1e-5):
    df = f(x + deta) - f(x)
    return df/delta

#iter cal
def iter_imporve(update, is_ok, init):
    if is_ok(init):
        init
    else:
        iter_imporve(update, is_ok, update(init))

lambda

a lambda expression evaluates to a function, called lambda function. A lambda expression itself evaluated to a function but does not bind it to a name, and the returned expression of this function is not evaluated until the lambda is called

def keep_ints(cond, n):
    """Print out all integers 1..i..n where cond(i) is true
    >>> def is_even(x):
    ...     # Even numbers have remainder 0 when divided by 2.
    ...     return x % 2 == 0
    >>> keep_ints(is_even, 5)
    2
    4
    """
    "*** YOUR CODE HERE ***"
    if n == 0:
        return
    if cond(n):
        print(n)
    keep_ints(cond, n - 1)



def make_keeper(n):
    """Returns a function which takes one parameter cond and prints out all integers 1..i..n where calling cond(i) returns True.
        >>> def is_even(x):
        ...     # Even numbers have remainder 0 when divided by 2.
        ...     return x % 2 == 0
        >>> make_keeper(5)(is_even)
        2
        4
    """
    "*** YOUR CODE HERE ***"
    def innal_func(func):
        m = n
        while m > 0:
            if func(m):
                print(m)
            m -= 1
    return innal_func

currying

converting a function that takes multiple arguments into a chain of functions that each takes one parameter.

def curried_pow(x):
    def h(y):
        return pow(x, y)
    return h

curried_pow(2)(3)

// 使每个两参数的func curying
def curry_two(f):
    return lambda x:(lambda y: f(x,y))

self-reference

self-reference refers to a particular design of HOF, where a function eventually returns itself. In particular, a self-referencing function will not return a function call, but rather the function object itself.

对自引用函数的调用最终会返回函数自身。

def make_keeper_redux(n):
    """Returns a function. This function takes one parameter <cond> and prints out
       all integers 1..i..n where calling cond(i) returns True. The returned
       function returns another function with the exact same behavior.

        >>> def multiple_of_4(x):
        ...     return x % 4 == 0
        >>> def ends_with_1(x):
        ...     return x % 10 == 1
        >>> k = make_keeper_redux(11)(multiple_of_4)
        4
        8
        >>> k = k(ends_with_1)
        1
        11
        >>> k
        <function do_keep>
    """
    # Paste your code for make_keeper here!
    
    def inner_func(func):
        m = n
        while m > 0:
            if func(m):
                print(m)
            m -= 1
        return make_keeper_redux(n)
    return inner_func



def print_delayed(x):
    """Return a new function. This new function, when called, will print out x and return another function with the same behavior.
    >>> f = print_delayed(1)
    >>> f = f(2)
    1
    >>> f = f(3)
    2
    >>> f = f(4)(5)
    3
    4
    >>> f("hi") # a function is returned
    5
    <function delay_print>
    """
    def delay_print(y):
        print(x)
        return print_delayed(y)
    return delay_print


def print_n(n):
    """
    >>> f = print_n(2)
    >>> f = f("hi")
    hi
    >>> f = f("hello")
    hello
    >>> f = f("bye")
    done
    >>> g = print_n(1)
    >>> g("first")("second")("third")
    first
    done
    done
    <function inner_print>
    """
    def inner_print(x):
        if n == 0:
            print("done")
        else:
            print(x)
        return print_n(n - 1)
    return inner_print

# Match Maker
def match_k(k):
    """ Return a function that checks if digits k apart match

    >>> match_k(2)(1010)
    True
    >>> match_k(2)(2010)
    False
    >>> match_k(1)(1010)
    False
    >>> match_k(1)(1)
    True
    >>> match_k(1)(2111111111111111)
    False
    >>> match_k(3)(123123)
    True
    >>> match_k(2)(123123)
    False
    """
    def inner_cal(n):
        _k = k
        m = 1
        while _k != 0:
            m *= 10
            _k -= 1
        last = -1
        while n != 0:
            if last != -1 and n % m != last:
                print("here", last, n, m)
                return False
            last = n % m
            n = n // m
            print("there", last, n, m)
        return True
    return inner_cal


# My Last Three Brain Cells
def three_memory(n):
    """
    >>> f = three_memory('first')
    >>> f = f('first')
    Not found
    >>> f = f('second')
    Not found
    >>> f = f('third')
    Not found
    >>> f = f('second') # 'second' was not input three calls ago
    Not found
    >>> f = f('second') # 'second' was input three calls ago
    Found
    >>> f = f('third') # 'third' was input three calls ago
    Found
    >>> f = f('third') # 'third' was not input three calls ago
    Not found
    """
    def f(x, y, z):
        def g(i):
            if x == i:
                print("Found")
            else:
                print("Not found")
            return f(y, z, i)
        return g
    return f(None, None, n)
## 进阶，如果是 k_memory 怎么办？ 那就不能用方法来保存


# natural chainz
def chain_function():
    """
    >>> tester = chain_function()
    >>> x = tester(1)(2)(4)(5) # Expected 3 but got 4, so print 3. 1st chain break, so print 1 too.
    3 1
    >>> x = x(2) # 6 should've followed 5 from above, so print 6. 2nd chain break, so print 2
    6 2
    >>> x = x(8) # The chain restarted at 2 from the previous line, but we got 8. 3rd chain break.
    3 3
    >>> x = x(3)(4)(5) # Chain restarted at 8 in the previous line, but we got 3 instead. 4th break
    9 4
    >>> x = x(9) # Similar logic to the above line
    6 5
    >>> x = x(10) # Nothing is printed because 10 follows 9.
    >>> y = tester(4)(5)(8) # New chain, starting at 4, break at 6, first chain break
    6 1
    >>> y = y(2)(3)(10) # Chain expected 9 next, and 4 after 10. Break 2 and 3.
    9 2
    4 3
    """

    def g(x, y):
        def h(n):
            if x is None:
                return g(n, 0)
            if n == x + 1:
                return g(n, y)
            else:
                print(x+1, y + 1)
                return g(n, y + 1)
        return h
    return g(None, 0)

递归

a function is called recursive if the body of the function calls the function itself, either directly or indirectly

Recursive thinking is the extention of this same discipline to functions as you are defining them. 递归思维是归纳思维的一种。

linear recursive function

线性递归就是普通的递归， 每次调用的时候会调用自身最多一次，需要保存计算的轨迹， 由解释器或者执行器维护将要执行的操作的轨迹，长度L随着n的增加而增加，线性计算过程。

tail-revursion is a sub type of liner recursion： return 语句要么是最后要调用的函数，要么是返回值。它需要编译器支持，会清除上一次递归中的局部变量，参数等，当最后一个func执行完直接返回，避免了栈溢出。聪明的编译器都可以把尾递归优化成迭代计算

迭代计算过程:

一般来说， 状态可以用固定数量的状态变量描述，并且，存在着一套规则，描述了一个状态到另一个状态的转换，可能还有结束状态检测，终止条件。从另外的角度看，recurison由解释器维持

// tail
if continue:    
    return func(x + 1)
else:
    return 1
// linear
if continue:
    return func(x+1) * 4
else:
    return 1


// tail， 假设func不是递归
def find_zero(low, high, func):
    if low > high:
        return None
    middle = (low + high) // 2
    if func(middle) == 0:
        return middle
    else if func(middle) < 0:
        return find_zero(middle+1, high, func)
    else:
        return find_zero(low, middle - 1, func)

def f(a, b):
    if a > b:
        return f(a - 3, 2 * b)
    elif a < b:
        return f(b // 2, a)
    else:
        return b

def summation(n, term):
    """Return the sum of numbers 1 through n (including n) wíth term applied to each number.
    Implement using recursion!

    >>> summation(5, lambda x: x * x * x) # 1^3 + 2^3 + 3^3 + 4^3 + 5^3
    225
    >>> summation(9, lambda x: x + 1) # 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
    54
    >>> summation(5, lambda x: 2**x) # 2^1 + 2^2 + 2^3 + 2^4 + 2^5
    62
    >>> # Do not use while/for loops!
    >>> from construct_check import check
    >>> # ban iteration
    >>> check(HW_SOURCE_FILE, 'summation',
    ...       ['While', 'For'])
    True
    """
    assert n >= 1
    "*** YOUR CODE HERE ***"
    # ans = 0
    # for i in range(1, n + 1):
    #     ans += term(i)
    # return ans
    if n > 1:
        return term(n) + summation(n - 1, term)
    else:
        return term(1)


def pascal(row, column):
    """Returns the value of the item in Pascal's Triangle 
    whose position is specified by row and column.
    >>> pascal(0, 0)
    1
    >>> pascal(0, 5)   # Empty entry; outside of Pascal's Triangle
    0
    >>> pascal(3, 2)   # Row 3 (1 3 3 1), Column 2
    3
    >>> pascal(4, 2)     # Row 4 (1 4 6 4 1), Column 2
    6
    """
    "*** YOUR CODE HERE ***"
    if column > row or column < 0:
        return 0
    elif column == 0 and row == 0:
        return 1
    else:
        return pascal(row - 1, column) + pascal(row - 1, column - 1)


def paths(m, n):
    """Return the number of paths from one corner of an, only two directions
    M by N grid to the opposite corner.

    >>> paths(2, 2)
    2
    >>> paths(5, 7)
    210
    >>> paths(117, 1)
    1
    >>> paths(1, 157)
    1
    """
    "*** YOUR CODE HERE ***"
    if m == 1 or n == 1:
        return 1
    elif m == 0 or n == 0:
        return 0
    else:
        return paths(m - 1, n) + paths(m, n - 2)

disc 3

def is_palindrome(s):
    if len(s) <= 1:
        return True
    return s[0] == s[len(s)-1] and is_palindrome(s[1:(len(s)-1)])

# 最长的
def greatest_pal(s):
    """
    >>> greatest_pal("tenet")
    'tenet'
    >>> greatest_pal("tenets")
    'tenet'
    >>> greatest_pal("stennet")
    'tennet'
    >>> greatest_pal("25 racecars")
    'racecar'
    >>> greatest_pal("abc")
    'a'
    >>> greatest_pal("")
    ''
    """
    if is_palindrome(s):
        return s
    left, right = greatest_pal(s[0:len(s)-1]), greatest_pal(s[1:len(s)])
    if left >= right:
        return left
    return right

def greatest_pal(s):
    def helper(a, b, c):
        if __________________________ > ____________________________:
            return _______________________________________________
        elif ________________________ > ____________________________:
            return _______________________________________________
        elif ________________ and _______________________________
            ______________________________________________________
        return ____________________________________________________
    return helper(1, 0, "")

def greatest_pal(s):
    def helper(a, b):
        if ______________________________________________________:
            return ______________________________________________________
        elif ______________________________________________________:
            return ______________________________________________________
        return ______________________________________________________
    return _________________________________________________________________

square = lambda x: x * x

identity = lambda x: x

triple = lambda x: 3 * x

increment = lambda x: x + 1


HW_SOURCE_FILE = __file__


def compose1(func1, func2):
    """Return a function f, such that f(x) = func1(func2(x))."""
    def f(x):
        return func1(func2(x))
    return f


def make_repeater(func, n):
    """Return the function that computes the nth application of func.

    >>> 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) # Yes, it makes sense to apply the function zero times!
    5
    """
    "*** YOUR CODE HERE ***"
    # def do_func(*args):
    #     if n == 0:
    #         return args[0] if len(args) == 1 else args
    #     elif n == 1:
    #         return func(*args)
    #     else:
    #         return func(make_repeater(func, n - 1)(*args))
    # return do_func

    def do_i(*args):
        if n == 0:
            return args[0] if len(args) == 1 else args
        elif n == 1:
            return func(*args)
        else:
            return make_repeater(func, n - 1)(func(*args))
    return do_i


def num_eights(pos):
    """Returns the number of times 8 appears as a digit of pos.

    >>> num_eights(3)
    0
    >>> num_eights(8)
    1
    >>> num_eights(88888888)
    8
    >>> num_eights(2638)
    1
    >>> num_eights(86380)
    2
    >>> num_eights(12345)
    0
    >>> from construct_check import check
    >>> # ban all assignment statements
    >>> check(HW_SOURCE_FILE, 'num_eights',
    ...       ['Assign', 'AugAssign'])
    True
    """
    "*** YOUR CODE HERE ***"
    if pos == 0:
        return 0
    else:
        return num_eights(pos // 10) + (1 if pos % 10 == 8 else 0)

def pingpong(n):
    """Return the nth element of the ping-pong sequence.

    >>> pingpong(8)
    8
    >>> pingpong(10)
    6
    >>> pingpong(15)
    1
    >>> pingpong(21)
    -1
    >>> pingpong(22)
    -2
    >>> pingpong(30)
    -2
    >>> pingpong(68)
    0
    >>> pingpong(69)
    -1
    >>> pingpong(80)
    0
    >>> pingpong(81)
    1
    >>> pingpong(82)
    0
    >>> pingpong(100)
    -6
    >>> from construct_check import check
    >>> # ban assignment statements
    >>> check(HW_SOURCE_FILE, 'pingpong', ['Assign', 'AugAssign'])
    True
    """
    "*** YOUR CODE HERE ***"
    def help(m, step, v, target):
        if m == target:
            return v
        else:
            if (m % 8 == 0) or num_eights(m) != 0:
                return help(m + 1, -1 * step, v + (-1) * step, target)
            else:
                return help(m + 1, step, v + step, target)
    return help(1, 1, 1, n)

def missing_digits(n):
    """Given a number a that is in sorted, increasing order,
    return the number of missing digits in n. A missing digit is
    a number between the first and last digit of a that is not in n.
    >>> missing_digits(1248) # 3, 5, 6, 7
    4
    >>> missing_digits(19) # 2, 3, 4, 5, 6, 7, 8
    7
    >>> missing_digits(1122) # No missing numbers
    0
    >>> missing_digits(123456) # No missing numbers
    0
    >>> missing_digits(3558) # 4, 6, 7
    3
    >>> missing_digits(35578) # 4, 6
    2
    >>> missing_digits(12456) # 3
    1
    >>> missing_digits(16789) # 2, 3, 4, 5
    4
    
    >>> missing_digits(4) # No missing numbers between 4 and 4
    0
    >>> from construct_check import check
    >>> # ban while or for loops
    >>> check(HW_SOURCE_FILE, 'missing_digits', ['While', 'For'])
    True
    """
    "*** YOUR CODE HERE ***"
    def help(m, last):
        if m == 0:
            return 0
        else:
            return (last -1 - m % 10 if last and m % 10 < last-1 else 0) + help(m // 10, m % 10)
    return help(n, None)


def get_next_coin(coin):
    """Return the next coin. 
    >>> get_next_coin(1)
    5
    >>> get_next_coin(5)
    10
    >>> get_next_coin(10)
    25
    >>> get_next_coin(2) # Other values return None
    """
    if coin == 1:
        return 5
    elif coin == 5:
        return 10
    elif coin == 10:
        return 25


def count_coins(change):
    """Return the number of ways to make change using coins of value of 1, 5, 10, 25.
    >>> count_coins(15)
    6
    >>> count_coins(10)
    4
    >>> count_coins(20)
    9
    >>> count_coins(100) # How many ways to make change for a dollar?
    242
    >>> from construct_check import check
    >>> # ban iteration
    >>> check(HW_SOURCE_FILE, 'count_coins', ['While', 'For'])                                          
    True
    """
    "*** YOUR CODE HERE ***"
    def helper(coin, target):
        if target == coin:
            return 1
        if target < coin:
            return 0
        next_coin = get_next_coin(coin)
        ans = 0
        if next_coin is not None:
            ans += helper(next_coin, target)
        ans += helper(coin, target - coin)
        return ans

    return helper(1, change)

def zero(f):
    return lambda x: x


def successor(n):
    return lambda f: lambda x: f(n(f)(x))


def one(f):
    """Church numeral 1: same as successor(zero)"""
    "*** YOUR CODE HERE ***"
    return lambda *args: f(*args)


def two(f):
    """Church numeral 2: same as successor(successor(zero))"""
    "*** YOUR CODE HERE ***"
    def inter_func(args):
        return f(f(args))
    return inter_func

def two_2(f):
    """Church numeral 2: same as successor(successor(zero))"""
    "*** YOUR CODE HERE ***"
    return lambda *args: f(f(*args))


three = successor(two)

def church_to_int(n):
    """Convert the Church numeral n to a Python integer.

    >>> church_to_int(zero)
    0
    >>> church_to_int(one)
    1
    >>> church_to_int(two)
    2
    >>> church_to_int(three)
    3
    """
    "*** YOUR CODE HERE ***"
    plus1 = lambda x: x+1
    return n(plus1)(0)


def add_church(m, n):
    """Return the Church numeral for m + n, for Church numerals m and n.

    >>> church_to_int(add_church(two, three))
    5
    """
    "*** YOUR CODE HERE ***"
    return m(successor)(n)


def mul_church(m, n):
    """Return the Church numeral for m * n, for Church numerals m and n.

    >>> four = successor(three)
    >>> church_to_int(mul_church(two, three))
    6
    >>> church_to_int(mul_church(three, four))
    12
    """
    "*** YOUR CODE HERE ***"
    return lambda x:m(n(x))

def pow_church(m, n):
    """Return the Church numeral m ** n, for Church numerals m and n.

    >>> church_to_int(pow_church(two, three))
    8
    >>> church_to_int(pow_church(three, two))
    9
    """
    "*** YOUR CODE HERE ***"
    return n(m)

关于丘奇数：并不是数字，而是可以理解为次数，某个操作执行的次数， 它的参数是函数。

Tree recursion

body执行的时候，会调用自身多次（可以0， 1 ，n）

复杂度是指数增长的。

// 分区n， 每个分区的值不能大于k, k>0
def nums_partitions(n, k):
    if n < 0:
        return 0    
    elif n == 0:
        return 1
    elif k == 1:
        return 1  
    else:
        return num_partitions(n-k, k) + num_partitions(n, k-1)