Now it's the most critical step in mathematical abstraction ： Let's forget what these symbols mean . It's not supposed to stop here , There are many operations that can be applied to these symbols , And there's no need to think about what they stand for .
--Hermann Weyi 《 The mathematical way of thinking 》
Construct data abstraction
Now consider a system that does rational arithmetic , Imagine an operation
add-rat, Take two rational numbers as parameters , The sum that produces them . Starting from the basic data , A rational number can be regarded as a combination of two integers -- Molecules and denominators , The process can be used
add-rat Realization , A molecule that produces sum numbers , Another one produces the denominator of sum numbers , When using this data , There are many rational numbers , The corresponding numerator and denominator appear in pairs , If there are no rules , It's going to make the code harder to read , So I want to consider a method of composite data , Put the data “ Adhesion ” get up .
A key idea in dealing with composite data is the concept of closure -- in other words , The glue used to combine object data can not only be used to combine basic data objects , It can also be used for composite data objects ; Another key idea is that composite objects can be combined program modules in a mixed and matched way .
Data abstraction Guide
1) The basic idea of abstract data , It's trying to build programs that use composite data objects , Make them feel like they're “ Abstract data ” Same as above .
2) A kind of “ Specifically ” The definition of data representation has nothing to do with the way data is used in a program .
[ notes ] The same idea as object-oriented ,“ Class ”, At the time when the author wrote the book , The concept of object-oriented programming is not mainstream yet , The idea of that era was the method of mathematical logic , Define symbolic variables , And deduce . The idea mentioned above is the properties and methods of classes in object-oriented programming , It's just functional programming .
Today we might build a Point class , From the perspective of data and operation , Process oriented is the same as object-oriented .
class RationalNumber(object): def __init__(self, x, y): # Ordered pair (x,y) They represent the numerator and denominator respectively self.x = x self.y = y def numer(self): return self.x def denom(self): return self.y def get(self): return self.x/self.y if __name__ =='__main__': a = RationalNumber(4,5) print(a.get())
The operation of rational numbers
If you design the program from the top to the bottom , Consider three functions
def make_rat(n,d): Returns a rational number :
def numer(x) Returns a rational number x The molecules of ,
def denom(x) Returns a rational number x Denominator of .
The addition, subtraction, multiplication and division of two rational numbers can be written as ：
def add_rat(x,y): return make_rat(x,y) def make_rat(x,y): return (numer(x)*denom(y) +numer(y)*denom(x))/(denom(x) *denom(y) )
denom Undefined , If you define an ordered pair ,
numer Returns the first position of an ordered pair ( molecular ),
denom Returns the second position of the ordered pair ( The denominator ), And then again ：
x = [1,2] y = [3,4] z = [x,y] def car(x): return x def cdr(x): return x def numer(x): return car(x) def denom(x): return cdr(x) print(numer(cdr(z)))
In the above example
def car(x): amount to
def cdr(x): amount to
x=[6,9] def print_rat(x): print(str(numer(x))+'/'+str(denom(x))) print_rat(x) The output is ：6/9, There is no reduction to the simplest form , In order to simplify , Consider the greatest common divisor def gcd(a,b): if b==0: return a else: return gcd(b,a%b) def print_rat1(x): g = gcd(denom(x),numer(x)) # It must be divisible , however python The language automatically casts types , Keep decimal places , In order to look good ->int() print(str(int(numer(x)/g))+'/'+str(int(denom(x)/g))) print_rat1(x)
[ notes ]: car and cdr It's the concept of registers Contents of Address part of Register” and “Contents of Decrement part of Register“.
All the rational operations given above , It's all based on constructors
make_rat And selection functions
denom(x) Defined , The idea of data abstraction is to identify a set of operations for each type of data object , So that all operations on such data objects can be expressed by these operations , And when you add, delete, modify and query these data, you can only use these operations .
( In terms of function ,
make_rat A number is disassembled and written as a combination of other functions ,
denom(x) These two functions choose the position of the data in the ordered alignment , In computational theory , As long as the functions are the same , It can be regarded as equivalent )
What data means
Rational number x A division that can be written as two integers :
I mentioned the idea of selecting functions and constructors , Rational number
x It is also represented by an ordered pair in the program , stay
python And we used that List To achieve :
x = [a,b]
What is implemented by a given constructor and selection function , It is very difficult to formalize this idea strictly . There are two ways to accomplish this formalization .
1) Methods of abstract models , It formalizes as outlined in the rational number example above “ Process plus conditions ” Specification description of , The abstract model method is always based on some defined data object types , Define a new class of data objects .
2) Algebraic norms . This approach will “ The process ” As elements of an abstract algebraic system , The behavior of the system consists of some corresponding to us “ Conditions ” The axiomatic characterization of , And through the abstract algebra technology to check the data object assertion .
Hierarchical data and closure properties
When we construct rational numbers , Order pairs provide a way to construct a basic data structure “ adhesive ”, And when we use it , The first position is defined as the molecule , The second position is the denominator , call
denom(x) when , The function is just to extract the data from the corresponding location .( Pay attention to the idea of the pointer )
For example, rational numbers 1/2,
cdr Take out the elements in the first and second positions respectively
In addition, the further abstraction of ordered pairs mentioned above can also be expressed as ：
From today's point of view, it is the concept of pointer , Mark the address , Point to data elements , And the linear table mentioned in the data structure . According to rules , The elements created by a combined order pair are still order pairs , So that's the closure property of the rule -- The results obtained by combining data objects can also be combined by the same operation , Through this nature, we can establish a hierarchical structure .
according to SICP The idea of , When abstracting, consider two important factors ：
1) Basic expressions --> Basic representation of data
2) Composition and abstraction of methods --> How to manipulate the data
If you recall the data structure you learned in second grade , The code for writing a linear table is ( Take the addition and traversal in the addition, deletion and modification query as an example )：
class Node(object): def __init__(self, val): # Define the current node value self.val = val self.next_node = None class MyList(object): def __init__(self, node): # Define the current node value self.node = node def add_node(self,node): self.node.next_node = node def print_all_node(self): p_node = self.node while p_node!=None: print(p_node.val) p_node = p_node.next_node if __name__ =='__main__': firstNode = Node(1) secondNode = Node(2) # The first node of the list print(' Create a new node and insert the first list ') myList = MyList(firstNode) myList.print_all_node() # The second node of the list print(' The list inserts the second node ') myList.add_node(secondNode) myList.print_all_node()
And if you learn Python Maybe write like this , also python Of List Built in
pop Methods are used to insert and delete elements
if __name__ =='__main__': lst = [1, 2, 3] for i in iter(lst): print(i)
SICP Sequences and operations in
stay SICP in , The idea of data combination abstraction , Due to the limitation of language ,python Although it can achieve and Lisp Same function , But this is not recommended ：
def car(z): return z def cdr(z): return z if __name__ =='__main__': a = [1,[2,[3,[4,[5,None]]]]] node1 = car(a) print(node1) next_iter = cdr(a) node2 = car(next_iter) print(node2)
If it's the second part of the traversal sequence n A place , Suppose the data of the sequence is expressed as
a=[1,2,3,4,5], Then return the subscript directly . And if the data of the sequence is expressed as
a = [1,[2,[3,[4,[5,None]]]]], You can use the constructed
cdr() Ergodic function ：
# Back to page n Elements of position ( from 0 Start ) def list_ref(a,n): if n==0: return car(n) else: return cdr(a,n-1) # return list The length of def length_recursive(a): if a==None: return 0 else: return 1 + length(cdr(a)) # return list The length of def length_iterative(a): count = 0 def length_iter(a,count): if a == None: return count else: return length_iter(cdr(a),count+1) return length_iter(a,count) #list The joining together of # a=[1,2,3],b=[4,5]==>c=[1,2,3,4,5] def list_append(list1,list2): if list1==None: return list2 else: return [car(list1),list_append(cdr(list1),list2)] #list Of mapping # a = [1,2,3] ==>f(a)=[2,4,6] def scale_list(items, factors): if items==None: return None else: return [car(items)*factors, scale_list(cdr(items),factors)] #mapping High level abstraction of operations def map_higher_order(f,items): if items==None: return None else: return [f(car(items)),map_higher_order(f,cdr(items))] if __name__ =='__main__': a = [1,[2,[3,[4,[5,None]]]]]
If we use the idea of data structure to examine ：
a = [1,[2,[3,[4,[5,None]]]]] difference , The former can be understood as a linear table , The latter is the tree ：
The general interface definition of a sequence
With the idea of data abstraction to compound data ( Basic expression ), The details of program implementation are masked . With abstract data , We should consider the abstraction of data operation , Now in object-oriented software design , Often mentioned some interface design , Consider the following two procedures :
example: Take a tree as a parameter , Calculate the sum of squares of odd leaf nodes
#f For the higher-order abstraction of functions def sum_odd_square(f,tree): def tree_iter(tree): if tree== None: return 0 else: if car(tree)%2==0: return 0 + tree_iter(cdr(tree)) else: return f(car(tree)) + tree_iter(cdr(tree)) return tree_iter(tree) if __name__ == '__main__': tree = [1, [2, [3, [4, [5, [6,None]]]]]] print(sum_odd_square(lambda x:x*x,tree))
example: Construct all even Fibonacci Fib(k) A table of , Among them k Less than a given integer n:
def fib(n): if n==1: return 1 elif n==0: return 0 else: return fib(n-1) + fib(n-2) def even_fibs(n): def next_iter(k): if k>n: return None else: val = fib(k) if val%2==0: return [val, next_iter(k+1)] else: return next_iter(k+1) return next_iter(0)
Compare the functions of the two functions
1) Enumerate all the leaves of the tree
2) Filter leaf nodes , Choose the odd number
3) Find the square
4) Sum up
1) Enumerating integers 0 To n
2) Calculate Fibonacci number
3) Filter results , Take out even numbers
4) Combine the results
def filter(predicate, sequence): if sequence ==None: return None else: if predicate(car(sequence)): return [car(sequence), filter(predicate,cdr(sequence))] else: return filter(predicate, cdr(sequence)) def f(z): if z%2==0: return True else: return False print(filter(f,a))