Introduction to Data Structure

What is Meant by Data?

• The definition of Data
• 使用procedure实现cons,car以及cdr.
  • 使用条件语句实现这三个内置函数.
  • 其实可以让cons支持有限个参数(>2个),只需要在条件语句上多加几个情况.
• Message Passing
  • definition: What is message passing?
• Exercises 2.4
  1. Analyse the requirements

  • (car (cons x y))

    • (cons x y) 是作为参数传入car的，实际上会生成一个procedure m
    • (car z) 返回的也是一个procedure，这个返回的procedure的作用就是返回第一个参数。
    • 所以这整个函数的作用就是car，返回第一个参数。

  • 写一个cdr的procedure。

    • Section 1.1.5
      • substitution model
        1. (f 5), this f is the procedure (sum-of-squares )
        • When we are trying to evaluate f ,this f is replaced by procedure (sum-of-squares)
        • Why do we need to use the substitution model?
          • Because we need to verify whether cdr works
    • The idea is to implement a procedure take the second parameter out as the return.
    • We need the cdr procedure to do something as follows

      (cdr (cons x y)) returns y
      * So the arguments of cdr should be a procedure , and the return value should also be a concrete object rather than a procedure.
      >(define (cdr z) (z (lambda (x y) y))

• How to implement the cons as a procedure?
  • (cons a b) -- (lambda (m) (m x y))
  • what is the return value of ‘cons'?
    • The return value is a kind of data structure. 'Data structure Object’
    • The return value can be manipulated by 'car' and 'cdr',
      • So the return value is a procedure.
        • What are the arguments of the procedure?
          """
          (define k (cons 4 5))
          (cdr k)
          (k (lambda (x y) y)
          (cons (4 5)) (lambda (x y) y)
          (lambda (m) (m 4 5)) (lambda ( x y) y)
          (lambda (x y) y) (4 5)
          5
          """

Conclution

• We can implement cons car cdr by ourself
• The cons returns a procedure which is the highest abstraction structure.
  • take procedure as arguments
  • returns object is also a procedure
• We can make up our mind by implement the structure step by step.