前端圈

分享与交流前端开发相关知识

开始学习Scheme

TL; DR:下载Racket,运行plt-r6rs my-file.scm将这本书加为书签,并在有疑问时进行检查。

Scheme是一种古老的编程语言,起源于七十年代中期。它的标志是极简主义-这里实际上没有那么多语言。不应将它与表达能力相混淆-您可以使用Scheme编写几乎所有当前以您喜欢的语言编写的内容。

但是,这种极简主义使其特别适合于学术研究。语言使您摆脱困境,让您专注于实际的逻辑。

一些采用传统CS大学路线的人可能会在您的课程中接触到此工具。但是,并非所有课程都使用它-我的课程不使用-并且自学者可能不会偶然发现它。我认为您错过了一种用于研究算法和编程语言的完美工具。Scheme是谈论计算本身的一种很棒的语言,几乎是一种正式的表示法。那里没有噪音来分散您的注意力-只有您和您的算法。

这是一个常见的例子。这就是一个人(特别是我)如何编码Euclid的算法,以找到C中两个数字的最大公约数:

// euclid.c

#include <stdio.h>

/**Calculate the greatest common divisor of positive integers m and n.
 * Returns -1 on error
 */
int gcd(int,int);

int main(void)
{
    int m = 119, n = 544, res;
    res = gcd(m,n);
    printf("%d", res);
}

int gcd(int divisor, int dividend)
{
    int m = divisor, n = dividend;
    // Out of bounds
    if (n <= 0 || m <= 0)
        return -1;
    for (;;)
    {
        // 1. Let `r` be the remainder of diving `m / n`.
        int r = m % n;
        // 2. If `r == 0`, complete.  Return `n`.
        if (r == 0)
            return n;
        // 3. `m <- n`, `n <- r`, goto 1.
        m = n;
        n = r;
    }
}

出于类似的原因,C是一种用于算法研究的好语言-它是一门小语言。没有太多的语法噪音,甚至没有更少的内在魔力-当告诉计算机您需要什么时,程序员首当其冲。这个限制实际上根本不是一个限制-您完全坐在驾驶席上,而在研究和优化算法以建立理解力时,这正是您想要的。

但是,它仍然有点吵。什么<stdio.h>啊 什么"%d"啊 为什么int到处都说?

这是Scheme中相同算法的实现:

; euclid.scm

(import (rnrs))

(define (gcd m n)
    (if (and (>= m 0) (>= n 0))
        (cond [(= n 0) m]
              [else (gcd n (mod m n))])
        (- 1)))

(display (gcd 119 544))

简洁得多!

要定义绑定,请使用define

(define my-name "Ben")
(display my-name)

这也适用于功能,上面的代码段为此使用了简写形式。Scheme中的每个函数实际上都是一个匿名lambda,欢迎您为其创建绑定,并且因为这是一种常见的操作,我们可以使用此语法糖。没有它,该程序将如下所示:

(define gcd
    (lambda (m n)
        (if (and (>= m 0) (>= n 0))
            (cond [(= n 0) m]
                  [else (gcd n (mod m n))])
            (- 1))))

该函数本身是一个匿名lambda,我们为其定义了一个出价gcd。当您使用short时(define (gcd m n) (...)),实际上就是这种情况。

这种规律性扩展到语言的所有部分。函数调用是一个列表包装,其内部以函数本身位于第一位置:

(= n 0) ; n == 0
(mod m n) ; n % m

相反condA && condB,我们使用(and condA condB)。这几乎完全消除了歧义-只需遵循paren嵌套,您就可以跟踪逻辑。if语句如下所示:

(if predicate onTrue onFalse)

您可以将所有三个参数替换为所需的实际形式。如果您的代码开始变得太复杂,则可以define在函数之外进行阻塞,也可以使用它let来创建本地绑定。该cond语句是if具有多个臂的的缩写形式,例如switch

一个陷阱是,您甚至不能直接写一个负数: -1在故障分支中不起作用。仅带一个参数,-意思是“取反”-因此,(- 3 2)减法,屈服1,取反(- 1),屈服-1

值得注意的是,此版本以递归方式编写,而我们的C势在必行。Scheme是标准化的,以支持适当的尾部递归,因此,尽管此函数在语法上是递归的,但由于递归发生在尾部位置,因此它实际上将更像是命令式循环,重新使用堆栈帧并交换操作数。

您可以以递归的方式编写遇到的所有命令式算法,尽管它们不一定总是同样方便。如果目前尚不清楚如何针对正在使用的算法执行该操作,则可能需要打破一些Scheme并尝试一下!

我使用的标准称为R6RS,或更笼统RNRS地说是与版本无关的方案。像C ++或ECMAScript一样,Scheme仅作为标准存在,并且存在许多相互竞争的实现。令人沮丧的是,这些实现实际上彼此之间有很大的不同,但是核心语言将是一致的-这就是标准的重点!R6RS标准可在此处找到。

实际上,现在也有R7RS方案,但是不要担心太多,除非您开始认真对待Scheme工作。社区中显然存在着关于极简主义和价值观以及任何东西的争论,例如政治。我不是为了政治,我是为了算法。R6RS完全可以。

我发现开始使用Scheme的最简单方法是通过Racket。Racket是一个比RNRS计划强大得多的系统,但支持称为#lang指令的功能,该功能可让您将Racket限制于此类特定标准。您可以将此#!r6rs指令直接放置在文件中,并使用标准的Racket构建工具,但是Racket还附带了一个名为的CLI工具plt-r6rs。您可以直接在方案文件上调用此文件,而不#lang需要:

$ plt-r6rs euclid.scm
17

有关通过Racket使用R6RS的更多信息,请参见此处。这是Scheme书,也是R6RS标准。这些链接应该可以让您启动并运行自己的实验。如果您渴望下一阶段的Scheme启蒙,请直接运行(不要走路)到The Little Schemer,并为自己做一个三明治。

玩得开心!

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注