title: Scheme入门
date: 2021-12-20 22:54:03
tags: lang

Installation

https://inst.eecs.berkeley.edu/~cs61a/fa14/assets/interpreter/scheme.html 在线的解释器

sudo apt install mit-scheme
#进入scheme交互式界面
scheme
#^C then Q quit

编译

将scheme代码用vscode写好以.scm后缀，如sum.scm

#open interface
scheme
#compile file
(cf "sum")
#import the module
(load "sum")
# import without compile
(load "hello.scm")

语法

基本设定（语言特殊）

一切都是函数。 包括语句。

（后面的标识符代表函数名。

所以一切都是list，确切地说S-表达式（atom或list）

expression

(- 10 3) → 7
(- 10 3 5)  → 2
(* 2 3) → 6
(* 2 3 4) → 24
(/ 29 3) → 29/3
(/ 29 3 7) → 29/21
(/ 9 6) → 3/2
(exact->inexact (/ 29 3 7)) → 1.38095238095238
---
(quotient 7 3) → 2
(modulo 7 3) → 1
(sqrt 8) → 2.8284271247461903
;onerload
(atan 1) → 0.7853981633974483
(atan 1 0) → 1.5707963267948966

list

Lists are (beaded) cons cells with the cdr part of the last cons cell being '() .

. Cons cells are a memory spaces which storage two addresses. Cons cells can be made by function cons

Function cons allocates a memory space for two addresses as shown in Figure 1. and stores the address to 1 in one part and to 2 in the other part. The part storing the address to 1 is called car part and that storing the address to 2 is called cdr part.可以理解成两个指针。

(The name cons is an abbreviation of a English term 'construction' for your information.Car and cdr are abbreviations of Contents of the Address part of the Register and Contents of the Decrement part of the Register. )

(cons 1 2)
;Value 11: (1 . 2)

(cons 3 (cons 1 2))
;Value 15: (3 1 . 2) : (3 1 . 2) is a convenient notation for (3 . (1 . 2)).点和括号可以一起去掉

(cons 1 (cons 2 '()))
;Value: (1 2) : .'()可以去掉，形式上就变成了list，其实也符合“点和括号可以一起去掉”

(car '(1 2 3 4))
;Value: 1

(cdr '(1 2 3 4))
;Value 18: (2 3 4)

atom, special forms, quote, list（函数）

Data structures which do not use cons cells are called atom（对应基本数据类型）. Numbers, characters, strings, vectors, and '() are atom. '() is an atom and a list as well.

Scheme has two kinds of operators: One is functions. Functions evaluate all the arguments to return value. The other is special forms. Special forms do not evaluate all the arguments. Besides quote, lambda, define, if, set!, etc. are special forms.（不计算所有参数，懒求值？

quote is used to protect tokens from evaluation.As quote is frequently used, it is abbreviated as '. e.g.'(+ 2 3) represents a list (+ 2 3) itself.'+ represents a symbol + itself.

Function list is available to make a list consisting of several elements. Function list takes arbitrary numbers of arguments and returns a list of them.

define function 全局变量

The define is a operator to declare variables and takes two arguments. The operator declares to use the first argument as a global parameter and binds it to the second argument. 将第二个参数束定于作为全局变量的第一个参数

The lambda is a special form to define procedures. The lambda takes more than one arguments and the first argument is the list of parameters that the procedure takes as arguments. As fhello takes no argument, the list of the parameters is empty.

; Hello world as a variable
(define vhello "Hello world")     ;1

; Hello world as a function
(define fhello (lambda ()         ;2
		 "Hello world"))

; hello with name
(define hello
  (lambda (name)
    (string-append "Hello " name "!")))


; sum of three numbers
(define sum3
  (lambda (a b c)
    (+ a b c)))

;shorten version,去掉lambda和括号， 把列表里的aug和函数名括起来
; hello with name
(define (hello name)
  (string-append "Hello " name "!"))


; sum of three numbers
(define (sum3 a b c)
  (+ a b c))

控制流

if

True is any value except false which is represented by #f. The representing value of true is #t. #f and '() are defined as the same object. (null? '()) is null?

(if predicate then_value else_value)
;sum of geometric progression
(define (sum-gp a0 r n)
  (* a0
     (if (= r 1)
	 n
	 (/ (- 1 (expt r n)) (- 1 r)))))   ; !!

cond

(cond
  (predicate_1 clauses_1)
  (predicate_2 clauses_2)
    ......
  (predicate_n clauses_n)
  (else        clauses_else))
  
  (define (fee age)
  (cond
   ((or (<= age 3) (>= age 65)) 0)
   ((<= 4 age 6) 0.5)
   ((<= 7 age 12) 1.0)
   ((<= 13 age 15) 1.5)
   ((<= 16 age 18) 1.8)
   (else 2.0)))

布尔函数

Function not is available to negate predicates.

The and takes arbitrary number of arguments and evaluates them from left to right. It returns #f if one of the arguments is #f and the rest of arguments are not evaluated. On the other hand, if all arguments are not #f, it returns the value of the last argument. 真时返回最后一个数。

The or takes arbitrary number of arguments and evaluates them from left to right. It returns the value of the first argument which is not #f and the rest of arguments are not evaluated. It returns the value of the last argument if it is evaluated.感觉0 #f ’（）混用。真时返回第一个真的数。

eq?It compares addresses of two objects and returns #t if they are same.

eqv?It compares types and values of two object stored in the memory space.

equal?It is used to compare sequences such as list or string.

(define str "hello")
;Value: str

(eq? str str)
;Value: #t

;;; comparing numbers depends on implementations
(eq? 1 1)
;Value: #t

(eq? 1.0 1.0)
;Value: ()

(eqv? 1.0 1.0)
;Value: #t

(eqv? 1 1.0)
;Value: ()

;;; the following depends on implementations
(eqv? (lambda(x) x) (lambda (x) x))
;Value: ()

(equal? (list 1 2 3) (list 1 2 3))
;Value: #t

(equal? "hello" "hello")
;Value: #t

=, <, >, <=, >=These functions takes arbitrary number of arguments. If arguments are ordered properly indicated by the function name, the functions return #t.

Functions char=?, char<?, char>?, char<=?, and char>=? are available to compare characters.

Functions char=?, char<?, char>?, char<=?, and char>=? are available to compare characters.

递归循环

(define (fact n)
  (if (= n 1)
      1
      (* n (fact (- n 1)))))
      
(define (list*2 ls)
  (if (null? ls)
      '()
      (cons (* 2 (car ls))
	    (list*2 (cdr ls)))))
	    ;makes all list items twice

尾递归

tail recursive functions include the result as argument and returns it directory when the calculation finishes. 返回值作为参数

Especially, as Scheme specification requires conversion of a tail recursive to a loop, there is no function call overhead.

(define (fact-tail n)
  (fact-rec n n))

(define (fact-rec n p)
  (if (= n 1)
      p
      (let ((m (- n 1)))
	(fact-rec m (* p m)))))

As fact-rec does not wait the result of other functions, it disappears from the memory space when it finishes. 函数不在表达式中

let loop

The named let is available to express loop. [code 3] shows a function fact-let that calculates factorials using named let. The fact-let uses a named let expression (loop), instead of fact-rec shown in [code 2]. First it initializes parameters (n1, p) with n at the line marked with ; 1. These parameters are updated at the line marked with ; 2 after each cycle: Subtracting n1 by one and multiplying p by (n1-1)

A named let is a conventional way to express loops in Scheme.

(define (fact-let n)
  (let loop((n1 n) (p n))           ; 1
    (if (= n1 1)                    
	p
	(let ((m (- n1 1)))
	  (loop m (* p m))))))      ; 2

letrec

While it is similar to the named let, a name defined by letrec can refer itself in its definition. The letrec syntax is used to define complicated recursive functions. [code 4] shows a letrec version of fact.

(define (fact-letrec n)
  (letrec ((iter (lambda (n1 p)
		   (if (= n1 1)
		       p
		       (let ((m (- n1 1)))
			 (iter m (* p m)))))))     ; *
    (iter n n)))

do

Syntax do is available for repetition, even it is not used frequently. The format is like as follows:

(do binds (predicate value)
    body)
 [binds] → ((p1 i1 u1) (p2 i2 u2) ... )
 
 (define (fact-do n)
  (do ((n1 n (- n1 1)) (p n (* p (- n1 1)))) ((= n1 1) p)))

The variables n1 and p are initialized with n and n and subtracted by one and multiplying by (n1 - 1) after each cycle, respectively. The function returns p when n1 becomes one.

I feel do is rather complicated than named let.

局部变量

local variables, which makes defining functions easier. Local variables can be defined using the let expression.

The let expressions can be nested.

(let binds body)
[binds] → ((p1 v1) (p2 v2) ...)

(let ((i 1) (j 2))
  (+ i j))
;Value: 3

(let ((i 1))
  (let ((j (+ i 2)))
    (* i j)))
;Value: 3

(let ((i 1) (j (+ i 2)))
  (* i j))
;Error,As the scope of the variables is the body,

(let* ((i 1) (j (+ i 2)))
  (* i j))
;Value: 3, let* expression is a syntax sugar of nested let expressions.


(define (quadric-equation a b c)
  (if (zero? a)      
      'error                                      ; 1
      (let ((d (- (* b b) (* 4 a c))))            ; 2
	(if (negative? d)
	 '()                                      ; 3
	 (let ((e (/ b a -2)))                    ; 4
	   (if (zero? d)
	       (list e)
	       (let ((f (/ (sqrt d) a 2)))        ; 5
		 (list (+ e f) (- e f)))))))))

Actually let expression is a syntax sugar of lambda expression: As the lambda expressions is function definition, it makes a scope of variables.

(let ((p1 v1) (p2 v2) ...) exp1 exp2 ...)
⇒
((lambda (p1 p2 ...)
    exp1 exp2 ...) v1 v2)

习题

随堂练习

0 A function that takes three real numbers as arguments. It returns the product of these three numbers if at least one of them is negative.

(define (pro3or a b c)
  (if (or (negative? a)
	  (negative? b)
	  (negative? c))
      (* a b c)))

1 my-reverse that reverse the order of list items. (Function reverse is pre-defined.)

2 Summarizing items of a list consisting of numbers.

3 Converting a string that represents a positive integer to the corresponding integer, i.e. "1232" → 1232. Input error check is not required.

Hint:Character to number conversion is done by subtracting 48 from the ASCII codes of characters #\0 ... #\9. Function char->integer is available to get the ASCII code of a character.Function string->list is available to convert string to a list of characters.

; 1
(define (my-reverse ls)
  (my-reverse-rec ls ()))

(define (my-reverse-rec ls0 ls1)
  (if (null? ls0)
      ls1
      (my-reverse-rec (cdr ls0) (cons (car ls0) ls1))))

;-------------------
; 2
(define (my-sum-tail ls)
  (my-sum-rec ls 0))

(define (my-sum-rec ls n)
  (if (null? ls)
      n
      (my-sum-rec (cdr ls) (+ n (car ls)))))

;--------------------
; 3
(define (my-string->integer str)
  (char2int (string->list str) 0))

(define (char2int ls n)
  (if (null? ls)
      n
      (char2int (cdr ls) 
		(+ (- (char->integer (car ls)) 48)
		   (* n 10)))))

反转列表