TLS 01 Toys

[The Little Schemer] 01 Toys

About atom, list and S-expression

atom

任何不是 list 的东西,包含 symbolnumberbool

symbol: character + special character (except ( and)) + number

number: 12, 12.4

bool: #t, #f

list

由圆括号 () 包括起来的 S-expression(s)

例如:(atom)

S-expression

Symbolic expression definition:

  1. Atomic symbols is S-expressions.
  2. if \(e_1\) and \(e_2\) are S-expressions, so is \((e_1, e_2)\).

:warning: Attentions

For Scheme

  • 'atom 等价于 (quote atom)

    • quote 实际上就是 capture expression and not evaluate it

      在 R Language 的 rlang package 中,quote 会将表达式及其执行环境捕获并存放在特殊的数据结构中。

    • 可以将其理解为在表达式外面加了一层引号 "expression",而执行被 quote 的表达式时,会去掉最外面的一层”引号“。

      1
      2
      3
      ; "atom" --eval--> atom
      (quote atom)
      ; output is atom but not the value of evaluating expression atom
  • () 为空列表,因为括号里有 0 个 S-expression。它也是 S-expression

For LISP

Recursive Functions of Symbolic Expressions (stanford.edu)

  • Atomic symbols 可以被写成 ABABAAPPLE PIE NUMBER 3
  • S-expression 是简单的 ordered pair(序对),例如 \((AB\cdot C)\)
  • List \((m_1,m_2,\cdots,m_n)\) 由 S-expression \((m_1\cdot(m_2\cdot(\cdots(m_n\cdot NIL)\cdots)))\) 来表示,是后者的缩写
  • \(NIL\) 是终止列表的 atomic symbol,(m) 实际上是 \((m\cdot NIL)\)

The Five Rules

The Law of Car

  • 仅针对非空列表
  • (car l) 表示取出非空列表 l 中的第一个 S-expression
1
2
3
4
(car '(a b c))
; output is a
(car '((a b c) x y z))
; output is (a b c)

The Law of Cdr

  • 仅针对非空列表
  • (cdr l) 表示非空列表 l 去除 (car l) 的部分
  • cdr 读作 could-er
1
2
3
4
(cdr '(a b c))
; output is (b c)
(cdr '((a b c) x y z))
; output is (x y z)

The Law of Cons

  • 接收两个参数,分别为一个 S-expression s 和一个 list l
  • (cons s l) 表示将 s 添加到列表 l 的开头处,其中第二个参数必须为列表
1
2
3
4
(cons 'atom '(a b c))
; output is (atom a b c)
(cons '(a b c) '(x y z))
; output is ((a b c) x y z)

The Law of Null?

  • 仅针对列表
  • (null? l) 判断列表 l 是否为空列表,是则返回 #t,不是则返回 #f
1
2
3
4
5
6
(null? 'atom)
; output is #f
(null? '())
;output is #t
(null? '(a b c))
; output is #f
  • (atom? s) 判断 S-expression s 是否是一个原子
1
2
3
(define atom?
(lambda (x)
(and (not (pair? x)) (not (null? x)))))
1
2
(define atom? (x)
(not (listp x)))

The Law of Eq?

  • 接收两个参数,它们都必须是非数字的 atom。

    在实践中,例如 Chez Scheme,eq? 也可以接收数字、列表作为参数。

  • (eq? a b) 比较两个 atom ab 是否相同,是则返回 #t,否则返回 #f