SCHEME教学 第一篇 基本概念

前言

Hi,这里是RMOlive,本系列教程将系统的讲解Scheme这一门Lisp方言。
但是在这里我们并不会介绍Scheme的背景,读者只需要知道这是一个遵从极简主义哲学的lisp分支语言就足够了。

本文假设读者已有一定的编程基础,基础概念将不再重复。

Scheme构造

S Expression

S-Expression是Scheme采用的表达形式,其形式主要表示为

(process data)

构造Scheme

Scheme语言的三个基本构造要素为

  1. 基本表达式形式:构造各种程序的基础
  2. 组合机制:将很多基本表达式组合构造出更复杂的表达式
  3. 抽象机制:为复杂的表达式命名,通过简单的方式使用

简单的说,对于程序

(define (t x y) (+ x (* y y)))

(* y y)就是基本表达式,我们通过和 (+ x …)进行组合构造出了(+ x (* y y))这一表达式,给这一表达式命名为t,其后就可以通过形如(t 4 5)的形式来使用这一表达式。

Continuation

Continuation简单理解就是对于表达式A来说,表达式 B执行完后A剩余部分,需要执行的部分,我们就称其为对于表达式A中表达式B对应的Continuation.

上面也说,我们可以通过(+ x …) 和 (* y y)构造出更复杂的表达式(+ x (* y y)),对于表达式(+ x (* y y))来说,其中对应于(* y y)的Continuation就是(+ x …)。

Lambda

Lambda是一种计算模型,或者说是一种形式,在Scheme中,我们可以这样写:

(lambda parms body)

对于表达式

((lambda x (f x)) 3)

在计算的时候将会把3带入x,将[body]即(f x)的x变成3,然后计算(f 3)。

而上面所说的Continuation,对于表达式(+ x (* y y))来说,其中对应于(* y y)的Continuation则可以写作

(lambda a (+ x a))

其中a就对应着(* y y)。

过程

上面我们已经说过表达式,对于这个表达式表达的计算意义,我们称呼其为该表达式对应的过程。

Environment

Environment,可以简单理解成在每个作用域中都有一个Key-Value对,维护着对于该作用域中当前对于过程的命名和过程之间的对应关系。

黑箱

假如我现在有一个程序

(define (add x y) (+ x y))

我们知道add需要传递x与y来获得过程来计算x与y的和,我们不需要知道该过程的实现细节,我们只需要知道这东西的用处。

所以我们应该:

  1. 把所用过程看作黑箱,关注功能,不关注其实现
  2. 过程抽象本质是功能分解,子功能间互为黑箱

代换模型

对于之前给出的表达式:

(define (t x y) (+ x (* y y)))

表达式(t 3 4)将会被以(+ 3 (* 4 4))的形式取而代之,在计算的时候可以将其展开替换,用以最简单的形式取而代之,这就是代换。

也就是说,对于表达式:

(define (rsc x)
    (if (= x 1)
        1
        (* x (rsc (- x 1)))))

表达式(rsc 5)可展开成:

(if (= 5 1)
    1
    (* 5 (rsc (- 5 1))))

化简一下可得到(* 5 (rsc 4))

而 (rsc 4)由可展开成:

(if (= 4 1)
    1
    (* 4 (rsc (- 4 1))))

化简一下可得到(* 4 (rsc 3)),带入到上面(rsc 5)的可得到(* 5 (* 4 (rsc 3)))

可以重复这种过程得到(rsc 5)即(* 5 (* 4 (* 3 (* 2 1)))),也就是120.

把化简过程写出来就是

(rsc 5)
(* 5 (rsc 4))
(* 5 (* 4 (rsc 3)))
(* 5 (* 4 (* 3 (rsc 2))))
(* 5 (* 4 (* 3 (* 2 (rsc 1)))))
(* 5 (* 4 (* 3 (* 2 1))))
---------------------------------
(* 5 (* 4 (* 3 2)))
(* 5 (* 4 6))
(* 5 24)
120

正则序与应用序

需要注意到,我们上面把表达式

(if (= 5 1)
    1
    (* 5 (rsc (- 5 1))))

直接对于该表达式除(rsc …)外的可以进行求值的地方进行求值了,这种就是应用序,当展开的某一时刻有过程可以被求值,就立刻进行求值。反之就是正则序。

比如对于表达式

(define (t x y) (+ x y))

来说,在应用序的情况下,表达式(t (+ 4 5) (* 2 4))的展开过程如下:

(t (+ 4 5) (* 2 4))
(t 9 8)
(+ 9 8)
17

而在正则序的情况下则是:

(t (+ 4 5) (* 2 4))
(+ (+ 4 5) (* 2 4))
(+ 9 8)
17

也就是说,对于正则序,会把表达式展开成只由基本表达式形式组成,才会进行计算。

结尾

本文让我们了解了Scheme的一些基础的概念,如有疑问可以私信我或发送邮件至rmolives@163.com.

本文《SCHEME教学 第一篇 基本概念》由 RM Olive (rmolives@gmail.com) 发布,如有版权纠纷及其他问题可以与我取得联系进行解决。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇