Process abstraction of program construction and interpretation

Program construction and interpretation Scheme Basic grammar

author：onceday date: 2022 year 6 month 5 Japan

1. Basic elements of design

Any language needs to pay attention to its The method of combining simple knowledge to form more complex knowledge , There are three mechanisms ：

• Basic expressions ： It is used to express the simplest individual concerned by language .
• The combination method ： Through them, we can construct composite elements from simpler things .
• Abstract methods ： They allow you to name compound objects , And operate them as units .

There are two types of elements in programming ： The process and data

Intuitive, ：

• Data is something we want to manipulate “ thing ”, A process is a description of the rules that operate on the data .

The language used here is scheme.

Syntax reference ：Chez Scheme Version 9 User’s Guide (cisco.github.io)

1.1 expression

456

When you enter an expression with the keyboard , The interpreter will express the result of its evaluation of this expression .

To be precise ,456 Is an expression made up of numbers , It means that 10 A number as a cardinal number .

1.2 combined

(+ 100 10)
(- 1000 220)
(< operation >  object 1  object 2  object 3 ......)

The above expression is called combined , The construction method is to enclose some expressions with a pair of parentheses , It represents a The process .

The leftmost element is called an operator , Other elements are called operands .

When evaluating , The process described by the operator is applied to the relevant actual parameters .

therefore , The procedure and parameters are defined , It doesn't mean that , Will be evaluated immediately .

1.3 Naming and environment

(define size 2)
(define add (+ x y))

The above expression can define Name identifier , That is to say Variable , Value is the object defined .

The object can be operation , It can also be data .

This process corresponds to Abstract methods , Complex programs can be defined through simple processes .

Another aspect , The interpreter must maintain some kind of storage capacity , Keep the relevant names over and over again - Value dual trajectories , This storage is called Environmental Science , Environmental Science It can be divided into many kinds , Such as global environment , And local action environment .

In this environment , Combinatorial expressions can be evaluated according to the following rules ：

• The values of numbers are the values they represent
• The value of the inner operator is the sequence of machine instructions that can complete the corresponding operation
• The value of the other name is the object associated with that name in the environment

Intuitive, ： Environmental Science Is used to determine the meaning of each symbol in the expression .

1.4 Procedural abstraction

(define (square x) (* x x))
(define (<name> <formal parameters>) (body))

body It can be a series of expressions , At this point, the interpreter will evaluate the expressions in this sequence in sequence , And take the value of the last expression as the value applied by the whole process and return it .

Substitution model ：

Expand first , Then specify the evaluation . This way is not very appropriate , But it's easy to understand .

(+ (square 6) (square 10))
(+ (* 6 6) (* 10 10))
(+ 36 100)
136

such “ Fully expanded and then regulated ” The evaluation model of is called regular order evaluation .

But now the interpreter often uses **“ First find the parameters and then apply “ The way **, be called Application order evaluation .

Application order evaluation Don't get the value of the operand first , Do it until you actually need their values .

1.5 Conditional expression

Special cases of case analysis ——cond:

(define (abs x) 
	(cond
    	((> x 0) x)
    	((= x 0) 0)
     	((< x 0) (- x))
     	(<pn> <en>)
    )	
)

Symbol cond It can be followed by many called Clause The bracketed expression duality of (<p><e>)

• <p> Is a predicate expression , It is interpreted as true or false .
• <e> Is a sequence expression , It can be composed of multiple combinations . As a response Expression duality The return value of .

cond The following expressions are used to find the value of predicate expressions in sequence , Until some Predicate expression It's true .

(define (abs x) 
	(cond
    	((> x 0) x)
		(else (- x))
    )	
)

have access to else Used to include situations other than the preceding clause .

When there are only two cases in case analysis , You can use symbols if:

(define (abs x)
	(if (< x 0)
    	(- x)
        x
    )  
)

Here are three common logical compound operators ：

(and <e1> ...... <en>)

Evaluate one by one from left to right <e>, If a <e> Make it worth it , This one and The value of the expression is false , Those behind <e> No more evaluation . When all expressions are true , this and expression The value of is true .

(or <e1> ...... <en>)

From left to right, one by one, find the value to the truth ,or The expression takes the value of this expression as the value , Those behind <e> No more evaluation . When all When the expression is false , this or expression The value of is false .

(not <e>)

If <e> The calculated value is false ,not The value of the expression is true , Otherwise, the value is false .

2. Procedural abstraction

2.1 Descriptive language and descriptive language

(define (sqrt x)
	(the y (and (>= y 0)
                (= (square y) x)
           )
     )  
)

The above describes a square root ：
$$\sqrt{x}=y,Andy\ge 0,y^2=x$$
Although it describes a mathematical definition , but Scheme Language cannot use it to derive the square root .

This is a universal feature , That is, the concrete expression of the universal difference between describing the characteristics of a thing and describing how to do it .

It can also be considered as the difference between illustrative knowledge and actionable knowledge .

Let's use Newton's method ( Gradually approach ) Process abstraction of implementation ：

(define (sqrt_iter guess x)
    (if (good_enough? guess x)
        guess
        (sqrt_iter (improve guess x) x)
    )
)

good_enough? It is used to judge whether the guess value is good enough , This has not yet been achieved .

Empathy ,improve It is also an abstraction of a process , Used to further improve abstract values .

In the process ,sqrt_iter Called itself , This is a recursive process abstraction , But this does not mean that the operation is recursive .

As for the implementation of these process abstractions , You don't need to care , Each floor acts as a black box , Decouple the relationship between layers .

If it is realized in the following way good_enough? and improve The process ：

(define (improve guess x)
	(average guess (/ x guess))
)
(define (good_enough? guess x)
	(< (abs (- (square guess) x)) 0.001)
)

You can see , These procedures also have their own parameter names .

As most programming languages do , The meaning of a procedure should not depend on the name chosen by its author for the formal parameter .

The formal parameter in the procedure is also called Constraint variables , If a constraint variable is defined in a complete process definition Change the name uniformly , Then the meaning of this process will not change . The bound expression range is its scope .

If a variable is not constrained , So it's going to be Free variable .

2.2 Block structure and lexical scope

(define (sqrt_iter guess x)
	(define (improve guess x)
		(average guess (/ x guess))
	)
	(define (good_enough? guess)
		(< (abs (- (square guess) x)) 0.001)
	)
    (if (good_enough? guess x)
        guess
        (sqrt_iter (improve guess x) x)
    )
)

This nested structure is also called Block structure . It can be improve,good_enough? The scope of is limited to sqrt_iter Inside , So as not to interfere with other procedures .

On the other hand , Such as x,guess Such variables can become internal " Free variable ", This reduces the displayed value transfer process .

2.3 Linear recursion and linear iteration

;;; Fiborache series , Tree recursive computation 
(define (fib n) 
    (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1)) (fib (- n 2))))))

;;; Fiborache series , Linear iterative computation 
(define (fib n)
    (define (fib_iter a b count)
            (if (= count 0)
                b
                (fib_iter (+ a b) a (- count 1))))
    (fib_iter 1 0 n))

The above is the two calculation methods of Fibonacci sequence , Recursive computation is a kind of shape that expands step by step and then shrinks , The structure of stack is often needed for auxiliary calculation , The advantage is easy to understand , Easy to implement .

The state of the iterative calculation process can be described by a fixed number of state variables ：

• A definite rule is needed to describe the switching between states
• End detection conditions are required

Most recursive algorithms can write the iterative calculation process .

2.4 High order abstraction - The process of operating process （ Higher order processes ）

Build a summation abstract model ：
$$\sum _{n=a}^{b}f(n)=f(a)+......+f(b)$$
This representation requires only the starting item a, End item b, The next item (next a), And item values (term a). This process can be abstracted , And don't worry about the specific summation sequence .

As shown below ：

(define (sum term a next b)
    (if (> a b)
        0
        (+ (term a) (sum term (next a) next b))
    )
)

among term and next Are as The process To participate .

Popular point ,sum As function , Its parameters are no longer limited to data variables , But it can also include the process , Then it is very flexible to write .

2.5 use lambda Construction process

Anonymous functions （ The process ）, No naming required , Can reduce a lot of meaningless things .

(lambda (<formal-parameters>) <body>)

Usage mode ：

((lambda (x y z) (+ x y (square z))) 1 2 3)

2.6 use let Create local variables

(let ((<var1> <exp1>)
      (<var2> <exp2>)
      ......
      (<varn> <expn>)
      )
  <body>
)

(<var1> <exp1>) It's the name - expression , When let When evaluated , Each name will be associated with the value of the corresponding expression .

And then these names (<var1>) Constraints are local variables , And try to be decent <body> Value .

Its equivalent mode is the following expression ：

((lambda (<var1> ... <varn>))
 <body>)
<exp1>
......
<exp2>)

It also means that let The expression is just the basis lambda It's just the grammar coat of expression .

Be careful ： Yes let The scope of the variable described by the expression is this let The body of .

in addition ,<exp> The value of is in let Outside calculation , And it's **“ Parallel computing ”, So its value Dependent on external scope **.

2.7 First level status （ The process ）

An element with the least restriction is called a state with the first level .

• You can name it as a variable
• The process can be provided as a parameter
• Can be returned by the process as a result
• It can be included in the data structure

If you can operate the process , Then return the process as a result , So greatly improve the abstract ability .

notes ： This content is collected on the Internet , For the purpose of study and communication only ！