526互联

Scheme

发布时间 2024-01-03 20:05:31作者: viewoverlook

Scheme

scheme fundamentals

scheme programs consist of expressions, which can be:

  • primitive expression: 2, 3.3, true, +, quotient ……
  • combination: (qutient 10 2), (not true)……
    Numbers are self-evaluating; symbols are bound to values
    Call expressions include an operands and 0 or more operands(操作数) in parentheses(括号)
>(quotient 10 2)
5
>(quotient (+ 8 7) 5)
3

A combination that is not a call expression is a special form:

  • If expression: if <predicate> <consequent> <alternative>
  • And and or: (and <\(e_1\)> \(\dots\) <\(e_n\)>), (or <\(e_1\)> \(\dots\) <\(e_n\)>)
  • Binding symbols: define <symbol> <expression>
  • New procedures: define (<symbol> <formal parameters>) <body>
(define (sqrt x)
	(define (update guess)
		(if (= (square guess) x)
			guess
			(update (average guess (/ x guess)))))
(update 1)

Lambda expressions

与python类似:
<lambda (<formal-parameters) <body>

Lists

  • cons: Two-argument procedure that creates a linked list
  • car: procedure that returns the first element of a list
  • cdr: Procedures that returns the rest of a list
  • nil: The empty list
Scheme lists are written in parentheses with elements separated by space
(cons 1 (cons 2 nil))

(1 2)

正常的显示应该向链表结构:

Symbolic Programming

引用: 使用`'`在需要引用的对象前面 解引用: ``` > (define b 2) b > '(a b c) (a b c) ``` 以上我们希望只是引用而不直接调用b绑定的值 但是如果需要将b=2放入时 可以使用\`表示 同时使用`,`表明解引用的对象 但是解引用作用和引用相同除非我们告诉其准确的目标 ``` > `(a b c) (a b c) > `(a ,b c) (a 2 c) ```

example: 中缀表达式转换为前缀表达式

(define (infix e)
	(if (not (list? e)) e
		`(,(cadr e) ,(infix(car e)) ,(infix(caddr e)))
	)
)

Dynamic Scope

Scheme和python查找命名时通过lexical scope(static scope)

  • lexical scope: 父帧是程序被定义时的环境
  • Dynamic scope: 父帧是程序被调用的环境

example:

(define f (lambda (x) (+ x y)))
(define g (lambda (x y) (f (+ x x)))

lexical scope:f帧的父帧是全局帧(在这里会报错因为y没定义)
Dynamic scope: f帧的父帧是g帧

Tail recursion

key observations:

  • people in the middle of the line don't wait for an answer
    • Tail recursive calls
  • information is passed down, as the questions are being asked.
    • intermediate variable
  • Last person announces answer(there's no going back and forth)
    • base case returns this intermediate variable
Tail contexts

尾递归在传递时并不传递答案的形成过程，而是不断传递子问题(一般通过中间变量传递，没有中间变量可选通常定义一个辅助函数加一个中间变量)
例如:

(define (replicate x n)
  (define (replicate-help x n lst-sofar)
    (if (= n 0)
        lst-sofar
        (replicate-help x (- n 1) (cons x lst-sofar))))
    (replicate-help x n nil))

Macros(宏)

宏是Scheme的一个功能,允许你在语言中定义新的特殊的形式。类似于cond,car……

Macro是源代码在计算前对代码的转化
Macro存在于许多语言中，但是在像Lisp语言中最易实现

So far we've been able to define our own procedures in Scheme using the define special form. When we call these procedures, we have to follow the rules for evaluating call expressions, which involve evaluating all the operands.

目前为止我们已经可以通过define自定义特殊形式代码段。当我们调用代码段时，我们会根据代码段内的规则来计算操作数。

We know that special form expressions do not follow the evaluation rules of call expressions. Instead, each special form has its own rules of evaluation, which may include not evaluating all the operands. Wouldn't it be cool if we could define our own special forms where we decide which operands are evaluated? Consider the following example where we attempt to write a function that evaluates a given expression twice:

我们知道特殊形式表达并不遵循表达式的求值规则。相反，每种特殊形式都有自己的求值规则，其中可能包括不求值所有操作数。如果我们可以定义自己的特殊形式来决定计算那些操作数，那不是很酷？考虑以下实例，我们尝试编写一个对给定表达式求值两次的函数。

scm> (define (twice f) (begin f f))
twice
scm> (twice (print 'woof'))
woof

由于twice是常规过程，对twice的调用过程回遵循于常规调用表达式相同的求值规则；首先评估运算符之后计算操作数。这意味着当计算操作数(print 'woof)时打印了woof。在twice主体内，f绑定的是print返回值None，因此(begin f f)不进行任何操作

The problem here is clear: we need to prevent the given expression from evaluating until we're inside the body of the procedure. This is where the define-macro special form, which has identical syntax to the regular define form, comes in:

这里的问题很明显：我们需要阻止给定的表达式求值，直到我们进入过程主体。这就是 define-macro 特殊形式的用武之地，它与常规 define 形式具有相同的语法：

scm> (define-macro (twice f) (list 'begin f f))
twice

define-macro allows us to define what's known as a macro, which is simply a way for us to combine unevaluated input expressions together into another expression. When we call macros, the operands are not evaluated, but rather are treated as Scheme data. This means that any operands that are call expressions or special form expression are treated like lists.

define-macro 允许我们定义所谓的 macro ，这只是我们将未计算的输入表达式组合到另一个表达式中的一种方法。当我们调用宏时，操作数不会被计算，而是被视为方案数据。这意味着作为调用表达式或特殊形式表达式的任何操作数都将被视为列表。

If we call (twice (print 'woof)), f will actually be bound to the list (print 'woof) instead of the value undefined. Inside the body of define-macro, we can insert these expressions into a larger Scheme expression. In our case, we would want a begin expression that looks like the following:

如果我们调用 (twice (print 'woof)) ， f 实际上将绑定到列表 (print 'woof) 而不是值 undefined 。在 define-macro 的主体中，我们可以将这些表达式插入到更大的Scheme表达式中。在我们的例子中，我们需要一个如下所示的 begin 表达式：

(begin (print 'woof) (print 'woof))

To recap, macros are called similarly to regular procedures, but the rules for evaluating them are different. We evaluated lambda procedures in the following way:
回顾一下，宏的调用方式与常规过程类似，但评估它们的规则不同。我们通过以下方式评估 lambda 过程：

  • Evaluate operator
  • Evaluate operands
  • Apply operator to operands, evaluating the body of the procedure
    将运算符应用于操作数，评估过程的主体

However, the rules for evaluating calls to macro procedures are:
然而，评估对宏过程的调用的规则是：

  • Evaluate operator
  • Apply operator to unevaluated operands
    将运算符应用于未计算的操作数
  • Evaluate the expression returned by the macro in the frame it was called in.
    评估宏在调用它的框架中返回的表达式。

Quasiquotes

Recall that the quote special form prevents the Scheme interpreter from executing a following expression. We saw that this helps us create complex lists more easily than repeatedly calling cons or trying to get the structure right with list. It seems like this form would come in handy if we are trying to construct complex Scheme expressions with many nested lists.

回想一下， quote 特殊形式阻止Scheme 解释器执行以下表达式。我们发现这可以帮助我们更轻松地创建复杂的列表，而不是重复调用 cons 或尝试使用 list 获得正确的结构。如果我们试图用许多嵌套列表构造复杂的Scheme表达式，这种形式似乎会派上用场。

Consider that we rewrite the twice macro as follows:
考虑一下我们重写 twice 宏如下：

(define-macro (twice f)
  '(begin f f))

This seems like it would have the same effect, but since the quote form prevents any evaluation, the resulting expression we create would actually be (begin f f), which is not what we want.
这似乎具有相同的效果，但由于 quote 形式阻止任何计算，我们创建的结果表达式实际上是 (begin f f) ，这不是我们想要的。

The quasiquote allows us to construct literal lists in a similar way as quote, but also lets us specify if any sub-expression within the list should be evaluated.

quasiquote 允许我们以与 quote 类似的方式构造文字列表，而且还允许我们指定是否应计算列表中的任何子表达式。

At first glance, the quasiquote (which can be invoked with the backtick ` or the quasiquote special form) behaves exactly the same as ' or quote. However, using quasiquotes gives you the ability to unquote (which can be invoked with the comma , or the unquote special form). This removes an expression from the quoted context, evaluates it, and places it back in.

乍一看，准引号（可以使用反引号 ` 或 quasiquote 特殊形式调用）的行为与 ' 或 quote 完全相同。但是，使用准引号使您能够取消引号（可以使用逗号 , 或 unquote 特殊形式调用）。这会从引用的上下文中删除表达式，对其求值，然后将其放回原处。

By combining quasiquotes and unquoting, we can often save ourselves a lot of trouble when building macro expressions.

通过结合准引号和取消引号，我们在构建宏表达式时通常可以省去很多麻烦。

Here is how we could use quasiquoting to rewrite our previous example:

以下是我们如何使用准引用来重写我们之前的示例：

(define-macro (twice f)
  `(begin ,f ,f))