5

乱点天赋点之Scheme

 3 years ago
source link: https://zhuanlan.zhihu.com/p/359661142
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

乱点天赋点之Scheme

Scheme是什么

它是Lisp的一种方言，而Lisp是一门古老的语言。麻省理工曾经将Scheme作为计算机同学的入门语言，更有著名的《计算机程序的构造和解释》作为入门教程。

Lisp是函数式的鼻祖，它是以函数为核心的语言，函数的入参和返回值可以是数据，也可以是函数，在Scheme中，称之为过程。

本文将介绍Scheme基本的语法和JS借鉴Scheme的地方。本文所有的代码都可以work。

1、规则，以括号包裹表达式 (symbol param1 param2 ...)

最简单的表达式 

(+ 1 2)   
输出结果 3

2、定义变量 

(define size 2)   
(display (+ size 5))   
输出结果 7

3、求圆的面积 

(define (area-of-circle r)    
 (* 3.14 (* r r))   )   
(display (area-of-circle 2))
输出结果 12.56

4、条件表达式 关键字有 cond、if、else、and、or、not 这里介绍一下cond用法，其他用法差不多。 这里举一个求绝对值的例子

(define (abs1 x)
    (cond ((> x 0) x)
          ((= x 0) 0)
          ((< x 0>) (- x))
          )
  )

  (display  (abs1 -5))
  输出结果 5
  (display  (abs1 5))
  输出结果 5

5、在结构内部定义子函数 还是以求圆的面积，我们将半径平方的计算当成内部子函数。

(define (area-of-circle r)
    (define (square x)
      (* x x)
    )
    (* 3.14 (square r))
  )


  (display  (area-of-circle 2))

  输出结果 12.56

6、实现递归 我们以斐波那契的求值为例。 斐波那契的定义 F0 = 0 F1 = 1 Fn = Fn-1 + Fn-2（n≧2）

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

  (display  (fibonacci 10))
  输入结果55

7、迭代实现斐波那契 实际上斐波那契递归的方式虽然直观，但是存在函数调用栈过多的问题。 当 n >= 2; f(2) = f(1) + f(0); f(3) = f(2) + f(1);

即可得出，从前往后遍历的规律如下。令当前项为a，上一项为b。

a <- a + b

b <- a

(define (fibonacci n)
    (define (fibonacci-iter a b count)
      (if (= count 0) 
           b
          (fibonacci-iter (+ a b) a (- count 1))
      )
    )
    (fibonacci-iter 1 0 n)
  )

  (display  (fibonacci 10))
  输出 55

8、lambda表达式

(define square (lambda (x) (* x x)))
  (display  (square 10))

  输出 100

9、创建局部变量 编程多了你就会了解，局部变量，上下文环境是必不可缺的。

我有一个二元一次方程 f(x) = (x + 1)^2 + x + 1; 在数据里，我们会设 a = x + 1，这个其实就是定义局部变量。同样在编程里我们也使用这种方式，所以lisp很大一部分是由数据衍生而来的。

(define (sum1 x)
    (let ((a (+ a 1)))
      (+ a (* a a)))
  )
(display (sum1 10))
输出132

10、有序对 在Lisp里，本身不具备复杂的数据结构，比如数组、树形结构。我们先以有理数的例子介绍有序对，后续我们会实现一个数组结构。通过这个数组结构我们就能实现map、filter、reduce，这三个应该是纯函数典型的例子。

关键字 cons、car、cdr，分别对应 构造函数（Construct），寄存器地址的部分内容（Content of Address part of Register），寄存器递减的部分内容（Content of Decrement part of Register）。

有理数的定义，能以分子分母表示的数则有有理数

(define (make-rational n d) (cons n d))
  (define (numerator x) (car x))
  (define (denominator x) (cdr x))

  (define (print-rat x)
    (newline)
    (display (numerator x))
    (display "/")
    (display (denominator x))
  )

  (define one-half (make-rational 1 2))

  (print-rat one-half)
  输出 1/2

但是我们输出的结果不一定是最简化的，比如 4/6，可以约分为 2/3，那我们可以在make-rational中添加公约数的逻辑

这里说一下求最大公约数的技巧，大的数除以小的数，如果除尽，则小的数为最大公约数。否则用大的数剪小的数得到a。再把a和小的数带入之前的步骤，递归下去。
  (define (make-gcd a b) (if (= b 0)
      a
      (make-gcd b (remainder a b))))

  (define (make-rational n d)
    (let ((m (make-gcd n d)))
      (cons (/ n m) (/ d m))
    )
  )
  (define (numerator x) (car x))
  (define (denominator x) (cdr x))

  (define (print-rat x)
    (newline)
    (display (numerator x))
    (display "/")
    (display (denominator x))
  )

  (define four-sixth (make-rational 4 6))

  (print-rat four-sixth)
  输出 2/3

11、list对象

它是scheme实现复杂数据结构的基础的，它的结构是这样的 (list 1 2 3)，返回的是(1 2 3)集合。它是通过有序对连接的。如下图，cons的第一个指针指向第一个数，第二个指针指向第二个数，这个数也可以是list结构。所以通过最简单的结构就可以构造各种复杂的结构。

(display (list 1 2 3))
输出 (1 2 3)

Scheme的宏

宏是指将代码当作数据一样处理，可以定义自己的语法规则。可能比较抽象。可以参考这个链接。

我举一个简单的例子。正常情况下它的功能和函数有点像，你再每个打印后面添加句号。

(define-macro addDotAfterDisplay        
(lambda (x)      
 (display (string-append x "."))))
(addDotAfterDisplay "ok")

但是上面的功能普通函数也能实现，我们来看看普通函数实现不了的。宏可以对符号进行判断，比如当前是否是if语句。

if结构是Scheme中的最基本的条件分支控制结构，if过程的框架如下：

(if 测试条件
    then-分支
    else-分支)

if语句的例子：

> (define p 100)
> (if (> p 80) "big" "small")
"big"

这个时候使用when语句就更好，它只有then或者else分支。

(define-macro when1     
(lambda (test . branch)       
(list 'if test         
(cons 'begin branch))))

(define x 20)     
(display (when1 (< x 30) x))
 输出 20

如何在线编写Scheme

1、直接通过这个在线网站，Scheme 在线测试。

2、本地搭建scheme环境

下面的安装步骤来自于这篇文章，我如何用二十天刷完 SICP

参考 这个回答 安装 MIT-Scheme。Scheme 是 Lisp 的一种方言，也是 SICP 使用的语言。MIT-Scheme 是 MIT 实现的 Scheme 解释器，和 MIT 教材 SICP 更配哦 打开一个你最喜欢的编辑器（我用的 Sublime Text 3），编写一段 Scheme 代码并保存成 test，可以没有后缀名 打开命令行，输入 scheme < test，即可执行程序

JS中借鉴Scheme的地方

如何实现map

在JS中，我们如何实现一个数组的map

const arr = [1, 2, 3];     
arr = arr.map(val => val / 2);

js中如果数组不支持map，自己实现，应该是这样的，map(arr, fn); 而在scheme中，我们自己来构造一个map。它应该是这样的 (define map fn items)。

(define (add2 x)
      (+ x 2))
  (display (map add2 '(1 2 3)))

  // 输出 (3 4 5)

1、首先需要实现一个迭代器，其次要支持方法回调，并把参数传入回调。下面我们实现一个返回绝对值的例子。

 (define (myMap fn items)        
(if (null? items) '()       
(cons (fn (car items))             
(myMap fn (cdr items))))   )

(display (myMap abs (list -1 2 -3)))

这里又用到了有序对，对于一个list，car list返回当前一个引用的值，cdr list返回从第二个值到最后的值。

filter和reduce也是类似的，通过有序对和list，迭代的处理结果。

JS中不得不说的this

有些编程语言的this代表当前上下文，但是JS中的this指向却要在运行时才能知道，并且this还可能指向undefined，就算是一些老程序员，也会写出this的bug。而Scheme中没有this的概念，而React hooks中也尽量避免使用了this，this带来了一些便利，但是会使程序很不稳定。

Lisp或者Scheme是一门有追求的语言，用最少的API构建了几乎最复杂的语言系统，它之后所有的语言，多多少少都参考了这位鼻祖。

下面对Lisp的评价来自阮一峰老师的博客，为什么Lisp语言如此先进？（译文）

Lisp语言诞生的时候，就包含了9种新思想。这9种思想也在各种语言中出现。

  1. 函数也是一种数据类型。
  2. 变量的动态类型。
  3. 垃圾回收机制。
  4. 程序由表达式组成。
  5. 符号（symbol）类型。
  6. 代码使用符号和常量组成的树形表示法（notation）。
  7. 无论什么时候，整个语言都是可用的。

后话，前领导说我乱点天赋点，之前学了一段时间Android，现在又学函数式语言，不专精，前端首先要把使用的框架（React）理解透彻，然后深入理解JS这门语言，再吃透到JS的宿主环境V8。乱点天赋点虽然视野开阔了，但是基础还是差，我后面会花更多的时间在大前端上，不再乱点天赋点了。

最后附上SICP的英文版下班连接，英文版 SICP。中文版晚上也有免费资源。

《计算机程序的构造和解释》

我如何用二十天刷完 SICP

Common Lisp 的宏(Macro)到底神奇在哪？

为什么Lisp语言如此先进？（译文）


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK