TLS 01 Toys

Posted on Edited on In , , Views:
Symbols count in article: 1.8k Reading time ≈ 2 mins.
The Little Schemer

[The Little Schemer] 01 Toys

About atom, list and S-expression

atom

任何不是 list 的东西，包含 symbol、number 和 bool。

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 可以被写成 AB、ABA、APPLE 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 a 和 b 是否相同，是则返回 #t，否则返回 #f