lisp语法分析与执行分离

《sicp》4.1.7节读书笔记

这节中将书中之前实现的解释器做了改进,将语法分析于执行分离.这样做能提高很多效率,比如我们需定义一个过程,然后执行该过程多次.分情况说明:

1.语法分析于执行未分离

每次执行都会进行语法分析

2.语法分析于执行分离.

在定义该过程时,已经完成语法分析,该过程名保存在环境中的相应约束

就是,语法分析生成的(lambda (env) …).所以当执行该过程时,只需传入相应环境就可以完成执行,这就实现了一次分析,供永久执行.

实际例子:

输入语句

(define (f x) (+ x x))

(f 4)

分别分析以上两种情况的执行过程



//lisp解释器的语法分析和执行未分离的情况

输入: (define (f x) (+ x x))

==> (eval ('define ('f 'x) ('+ 'x 'x))  env)

==> (eval-definition ('define ('f 'x) ('+ 'x 'x)) env )

==> (define-variable! (definition-variable ('define ('f 'x) ('+ 'x 'x)))

			          (eval (definition-value ('define ('f 'x) ('+ 'x 'x))) env)

					  env)

		;其中的 (definition-variable ('define ('f 'x) ('+ 'x 'x)) ) 返回为 'f

                (eval (definition-value ('define ('f 'x) ('+ 'x 'x))) env)  返回为 ('procedure ('x) ('+ 'x 'x) env)

//所以在这里执行完毕后 env环境中,多了一条f函数的约束.

('f ('procedure ('x) ('+ 'x 'x) env) env )

输入: (f 4)

==> (eval ('f 4) env)

==> (apply (eval 'f env) 4)

		;其中的(eval 'f env) 返回 ('procedure ('x) ('+ 'x 'x) env)

==>(apply ('procedure ('x) (+ 'x 'x) env)  4)

==>(eval-sequence ('+ 'x 'x) (('x:4) (env)) )

		;其中(('x:4) (env)) 是执行(f 4)后创建的新环境

==>(eval ('+ 'x 'x) (('x:4) (env)))

==>(apply (eval '+ (('x:4) (env))) (4 4))

		;其中(eval '+ (('x:4) (env))) 返回 ('primitive +)       (假设初始环境含有 ""+"" 基本过程)

==>(apply ('primitive +) (4 4))

==>(apply-primitive-procedure ('primitive) (4 4))

==>(apply-in-underlying-scheme

   + (4  4))

==>8

如果再输入一次(f 4)仍然将执行以上分析和执行过程,可见每执行次(f 4)解释器都将分析一次 f 函数,然后执行

//lisp解释器的语法分析与执行分开的情况

输入 (define (f x) (+ x x))

==>(eval  ('define ('f 'x) ('+ 'x 'x)  begin_env)

==>((analyze ('define ('f 'x) ('+ 'x 'x))) begin_env)

   ;;;执行 (analyze ('define ('f 'x) ('+ 'x 'x)))

   ==>(analyze ('define ('f 'x) ('+ 'x 'x)) )

   ==>(analyze-definition ('define ('f 'x) ('+ 'x 'x)))

       {

	   (let ((var 'f)

		   (vproc (analyze ('lambda ('x 'x) ('+ 'x 'x))))

	     (lambda (env)

		    (define-variable! var (vproc env) env)

			'ok))

	   }

	  ;;;执行 (vproc (analyze ('lambda  ('x 'x) ('+ 'x 'x)))))

      ==>(analyze('lambda ('x 'x) ('+ 'x 'x)))

	  ==>(analyze-lambda ('lambda ('x 'x) ('+ 'x 'x)))

	     {

		     (let ((vars ('x 'x))

				  ( bproc (analyze-sequence  ( ('+ 'x 'x)) )))

			     (lambda (env) (make-procedure ('x 'x) brpoc env)))

		 }

		 ;;执行bproc

         ==>(analyze-sequence  (('+ 'x 'x)))

		 ==>{ (analyze ('+ 'x 'x))

	           (analyze-application ('+ x x)){

	        (let ((fproc (analyze '+))

				 (aprocs (map analyze ('x 'x))))

			(lambda (env)

			  (execute-application (fproc env)

			                       (map (lambda (aproc) (aproc env) aprocs))))

		    }

		    ;执行(analyze '+)

		    ==>(analyze-variable '+)

		    返回 :(lambda (env) (lookup-variable-value '+ env))

		    ;执行(map analyze ('x 'x))

		    返回 :((lambda (env) (look-variable-value 'x env)) (lambda(env) (look-variable-value 'x env)))

         返回:bproc:

	     (lambda(env)

	     (execute-application ((lambda (env) (lookup-variable-value '+ env)) env)

		 (map (lambda (aproc) (aproc env)) ((lambda (env) (look-variable-value 'x env)) (lambda(env) (look-variable-value 'x env))))

		 ))

		   }}

	    ==>返回:vproc=

		     (lambda (env)  (make-procedure ('x 'x) brpoc env))

			 ==>(make-procedure ('x 'x) brpoc env)

			 ==>返回:('procedure ('x 'x)  brpoc env)

	==>返回:

	(lambda(env)

	        (define-varibale! 'f) (vproc env) env)

;;代入 begin_env

==>((lambda(env) (define-varibale! 'f (vproc env) env) begin_env))

==>(define-varibale! 'f (vproc begin_env) begin_env)

      ==>(vproc begin_env)

		 f   :   ('procedure ('x 'x) brpoc begin_env)

最终:在 begin_env 中

f=('procedure

	('x 'x)

	(lambda(env)

	   (execute-application

		   ((lambda (env) (lookup-variable-value '+ env)) env)

	       (map (lambda (aproc) (aproc env)) ((lambda (env) (look-variable-value 'x env)) (lambda(env) (look-variable-value 'x env)))))))

//输入 (f 4)

==>(eval ('f 4) changed_env)

==>((analyze ('f 4)) changed_env)

  ==>(analyze-application ('f 4))

  ==>{

	 (let ( (fproc (lambda(env) (lookup-varible-value 'f env)))

			(approcs (lambda(env) 4))

			(lambda(env)

			  (execute-application (fproc env)

			                        (map (lambda (aproc) (aproc env)) aproc)))))

  }

==>代入changed_env

==> (execute-application (fproc changed_env)  4)

==> (execute-application

			 ('procedure

	         ('x 'x)

	         (lambda(env)

	         (execute-application

		     ((lambda (env) (lookup-variable-value '+ env)) env)

	         (map (lambda (aproc) (aproc env)) ((lambda (env) (look-variable-value 'x env)) (lambda(env) (look-variable-value 'x env)))))))

			 4)

==>((lambda(env)

	         (execute-application

		     ((lambda (env) (lookup-variable-value '+ env)) env)

	         (map (lambda (aproc) (aproc env)) ((lambda (env) (look-variable-value 'x env)) (lambda(env) (look-variable-value 'x env)))))))

		     ('x:4 (begin_env)))

==>(execute-application ('primitive +) (4 4))

==>(apply-in-underlying-scheme

   + (4  4))

==>8

巴特西

lisp语法分析与执行分离

lisp语法分析与执行分离

《sicp》4.1.7节读书笔记

这节中将书中之前实现的解释器做了改进,将语法分析于执行分离.这样做能提高很多效率,比如我们需定义一个过程,然后执行该过程多次.分情况说明:

1.语法分析于执行未分离

2.语法分析于执行分离.

实际例子:

最新文章

热门文章