Coding just likes Art

This is the blog about the coding, the whole coding and nothing but the coding , so God would help me become a better developer.

SanCoder's Blog home

Start to learn LisP

1 Content

2
3
- 3.0.1
- 3.0.2
- 3.0.3
- 3.0.4
- 3.0.5

2 Why LisP

因为 LisP 有着：

简单的语法规则
众多的方言（Emacs LisP, Scheme, Clojure, Guile）
对函数式的良好支持
天然的 λ演算语言
一本 NB 的书（SICP）

3 Rules of LisP

3.0.1 表达式与组合式

(+ 1 3)

(+ 1 2)

(+ 1 (+ 1 1))

3.0.2 命名 α-Conversion

(define (f x) (+ x x))
(f 1)

LisP 使用应用序而非正则序来对组合式求值

3.0.3 替换 β-Reduction

((lambda (x) (+ x x)) 1)

3.0.4 条件与谓词

条件谓词判断语法: cond

(cond (<predicate> <expression>)
      (<predicate> <expression>)
      ...
      [(else <expression>)])

(define (abs x)
  (cond ((> x 0) x)
        ((= x 0) 0)
        (else (- x))))
(abs -3)

条件谓词判断语法: if

(if <predicate> <consequent> <alternative>)

(define (abs x)
  (if (< x 0) (- x) x))
(abs -3)

逻辑运算符: and or not

(and <expression> ... <expression>)
(or <expression> ... <expression>)
(not <expression>)

((lambda (x y) (and x y)) 1 1)

((lambda (x y) (or x y)) 1 0)

((lambda (x) (not x)) (> 1 0))

3.0.5 Abstration of procedures 过程抽象

Local
- Bound Variable 约束变量
- Free Variable 自由变量
- Captured Variable 被捕获变量
Internal Definitions

下方代码的过程 bar 被称为 内部定义过程 , 这种结构被称为 块结构(Block Structure):

(define (foo)
  (define (bar) 2)
  (bar))
(foo)

可以定义 词法作用域(Lexical Scoping):

(define (foo x)
  (define (bar) (+ 2 x))
  (bar))
(foo 2)

3.1 Procedure & Process

过程是一种处理过程的演化(Procedure is a pattern for the local evolution of a computational process.)

3.1.1 Linear Recursion and Iteration

线性递归处理 Linear Recursion Process (NOT Procedure!!)

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))
(factorial 3)

线性迭代处理 Linear Iteration Process (NOT Procedure!!)

(define (fact-iter c i n)
  (if (> i n)
      c
      (fact-iter (* c i) (+ i 1) n)))

(define (factorial n)
  (fact-iter 1 1 n))

(factorial 3)

过程 (Procedure) 描述的是语法形式的事实, 一个递归过程 (Recursion Procedure) 指的是过程的定义中直接或间接的引用了该过程本身。
处理 (Process) 描述的是计算的进展方式。一个递归的过程很可能是以一种迭代进展方式处理的，也就是 尾递归 (Tail-Recursion) 的方式计算的。

3.1.2 Tree Recursion 树形递归

Fibonacci Sequence 斐波那契数列

树形递归法:

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

(list (fib 2)
      (fib 3)
      (fib 4)
      (fib 5)
      (fib 6)
      (fib 7))

迭代递归法:

(define (iter-fib c lc n)
  (if (= n 0)
      lc
      (iter-fib (+ c lc)
                c
                (- n 1))))
(define (fib n)
  (iter-fib 1 0 n))

(list (fib 2)
      (fib 3)
      (fib 4)
      (fib 5)
      (fib 6)
      (fib 7))

算法复杂度 Order

称 Θ(f(n)) 为算法的 复杂度(阶), 当存在与 n 无关的整数k₁和k₂, 使得:
k₁f(n) ≤ Θ(f(n)) ≤ k₂f(n)
对于任意大的 n 成立.

Greatest Common Divisors 最大公约数

(define (gcd-iter x y)
  (if (= y 0)
      x
      (gcd-iter y (remainder x y))))

(define (gcd x y)
  (if (> x y)
      (gcd-iter x y)
      (gcd-iter y x)))

(list (gcd 206 40)
      (gcd 144 81))

Lamé 定理: 如果欧几里得算法需要 k 步计算出一个对偶数的 GCD, 则其中的较小者必大于等于 Fib(k).

3.1.3 高阶函数做抽象

First Class:

可变量定义
可作为过程参数
可作为过程结果被返回
可包含在数据结构中

4 数据抽象导引

4.1 序对 Pairs 与表结构 list-structure

(define (make-rat n d)
  (define (assign x)
    (if (> x 0)
        1
        -1))
  (let ((g (gcd n d))
        (n (abs n))
        (d (abs d))
        (a (assign (* n d))))
    (cons (* (/ n g) a) (/ d g))))

(define (numer x) (car x))

(define (denom x) (cdr x))

(define (print-rat x)
  (newline)
  (display (numer x))
  (display "/")
  (display (denom x)))

(define num (make-rat 4 -8))

(print-rat num)

num

5 LisP 语法

5.1 define

5.1.1 定义变量

(define A 3)

(define (getValue)
  (newline)
  (display "Call getValue ...\n")
  3)

(define B (getValue))

(list A B)

5.1.2 函数定义

语法糖定义

(define (func param)
  (display "The function call need a pair of parentheses.\n")
  (display "This can be a block called sequentially.\n")
  (display "The value of last expression will be the return value of func.\n")
  (+ param 1))

(list (func 1))

匿名 λ 定义

(define func (lambda (param)
               (display "The function call need a pair of parentheses.\n")
               (display "This can be a block called sequentially.\n")
               (display "The value of last expression will be the return value of func.\n")
               (+ param 1)))

(list (func 1))

5.2 if

5.2.1 当 `if` 语句不包含 `else` 时, 返回 `unspecified`.

(define (whatif bool)
  (if bool
     1))

(list (whatif (> 3 2))
      (whatif (< 3 2)))

5.3 let 语法糖

(let ((<var1> <exp1>)
      (<var2> <exp2>)
      .
      .
      .
      (<varn> <expn>))
  <exp-body>)