Excerpt from:
Where is diao in Wang Yin's 40 lines of code - Alibaba cloud developer community
Who is Wang Yin? Don't tell me!!!
Don't talk nonsense, look!
;; A simple CPS transformer which does proper tail-call and does not;; duplicate contexts for if-expressions.;; author: Yin Wang (yw21@cs.indiana.edu)(load "pmatch.scm")(define cps
(lambda (exp)
(letrec
([trivial? (lambda (x) (memq x '(zero? add1 sub1)))]
[id (lambda (v) v)]
[ctx0 (lambda (v) `(k ,v))] ; tail context
[fv (let ([n -1])
(lambda ()
(set! n (+ 1 n))
(string->symbol (string-append "v" (number->string n)))))]
[cps1
(lambda (exp ctx)
(pmatch exp
[,x (guard (not (pair? x))) (ctx x)]
[(if ,test ,conseq ,alt)
(cps1 test
(lambda (t)
(cond
[(memq ctx (list ctx0 id))
`(if ,t ,(cps1 conseq ctx) ,(cps1 alt ctx))]
[else
(let ([u (fv)])
`(let ([k (lambda (,u) ,(ctx u))])
(if ,t ,(cps1 conseq ctx0) ,(cps1 alt ctx0))))])))]
[(lambda (,x) ,body)
(ctx `(lambda (,x k) ,(cps1 body ctx0)))]
[(,op ,a ,b)
(cps1 a (lambda (v1)
(cps1 b (lambda (v2)
(ctx `(,op ,v1 ,v2))))))]
[(,rator ,rand)
(cps1 rator
(lambda (r)
(cps1 rand
(lambda (d)
(cond
[(trivial? r) (ctx `(,r ,d))]
[(eq? ctx ctx0) `(,r ,d k)] ; tail call
[else
(let ([u (fv)])
`(,r ,d (lambda (,u) ,(ctx u))))])))))]))])
(cps1 exp id))));;; tests;; var(cps 'x)(cps '(lambda (x) x))(cps '(lambda (x) (x 1)));; no lambda (will generate identity functions to return to the toplevel)(cps '(if (f x) a b))(cps '(if x (f a) b));; if stand-alone (tail)(cps '(lambda (x) (if (f x) a b)));; if inside if-test (non-tail)(cps '(lambda (x) (if (if x (f a) b) c d)));; both branches are trivial, should do some more optimizations(cps '(lambda (x) (if (if x (zero? a) b) c d)));; if inside if-branch (tail)(cps '(lambda (x) (if t (if x (f a) b) c)));; if inside if-branch, but again inside another if-test (non-tail)(cps '(lambda (x) (if (if t (if x (f a) b) c) e w)));; if as operand (non-tail)(cps '(lambda (x) (h (if x (f a) b))));; if as operator (non-tail)(cps '(lambda (x) ((if x (f g) h) c)));; why we need more than two names(cps '(((f a) (g b)) ((f c) (g d))));; factorial(define fact-cps
(cps
'(lambda (n)
((lambda (fact)
((fact fact) n))
(lambda (fact)
(lambda (n)
(if (zero? n)
1
(* n ((fact fact) (sub1 n))))))))));; print out CPSed function(pretty-print fact-cps);; =>;; '(lambda (n k);; ((lambda (fact k) (fact fact (lambda (v0) (v0 n k))));; (lambda (fact k);; (k;; (lambda (n k);; (if (zero? n);; (k 1);; (fact;; fact;; (lambda (v1) (v1 (sub1 n) (lambda (v2) (k (* n v2))))))))));; k))((eval fact-cps) 5 (lambda (v) v));; => 120Knowledge background
Scheme
I can't speak this language either, but it doesn't matter. We're looking at ideas
Tail recursion
What is tail recursion?
Baidu Encyclopedia explains as follows:
If all recursive calls in a function appear at the end of the function, we call the recursive function tail recursive. When a recursive call is the last executed statement in the whole function body and its return value does not belong to a part of the expression, the recursive call is tail recursion. Tail recursive function is characterized by no operation in the regression process, which is very important because most modern compilers will use this feature to automatically generate optimized code.
How do modern compilers optimize?
When the compiler detects that a function call is tail recursion, it overwrites the current activity record instead of creating a new one on the stack This is an important guarantee that FP can write fast code without variables and loops and only tail recursion
The following is a simple tail recursion example for calculating factorials:
function tail_fact(n,a) {
if (n == 0)
return a ;
else
return tail_fact(n-1,n*a) ;
}CPS
Learn from http://matt.might.net/articles/by-example-continuation-passing-style/
What is CPS?
Continuation passing style, I translate it into continuous passing style programming, as follows:
(original)
function foo(x) {
return x ;
}(CPS)
function cps_foo(x, return_point) {
return return_point (x) ;
}cps has one more parameter, @ return_point，return_ Point the caller from function is the context where the caller is located. The caller passes this context to cps, so cps does not need to use additional tools (such as stack) to query the caller's environment (call location) for return, but directly enter the environment: return_point (x).
This is the original intention of CPS - to get rid of the nested world. The jargon is desugar.
Syntax sugar is to facilitate human expression and understanding and put a delicious and good-looking coat on the core of the programming language. For the interpretation of the machine to the program, it needs to be restored to the most essential structure for mechanized processing and optimization, which is the meaning of desugation.
Or the factorial Chestnut:
(original)
function tail_fact(n,a) {
if (n == 0)
return a ;
else
return tail_fact(n-1,n*a) ;
}(CPS)
function tail_fact(n,a,ret) {
if (n == 0)
ret(a) ;
else
tail_fact(n-1,n*a,ret) ;
}Blow it up, nothing comes out! Is an extra parameter passed? In fact, to put it bluntly, it is a callback@@@@
Code parsing
This code is a Scheme interpreter written in Scheme language. Through the cps function given by him, I can redefine all Scheme keywords with the symbolic system of Scheme, and execute the correct program semantics. In other words, it allows the language to explain itself. In essence, his code imitates the code given when John McCarthy invented Lisp language, but he rewrites it in Scheme style.
There are some quite technical parts in this code. Mainly the cps1 function. I admit I don't fully understand it, but I can probably understand that it basically minimizes language elements while maintaining semantics. Lines 31 and 37 of his generation are the most critical parts, which realize conditional branches and recursive calls. The basic principle is not complicated. It mainly uses the list of Scheme to deconstruct and disassemble the elements, and finally implements the conditional branches and function calls. If it is more Scheme style, this cps function is an eval function implemented by itself.
This cps implementation contains only a few language features: defining constants, defining functions, branching (if) and recursion. This is necessary to satisfy a meaningful minimization description. If language elements, such as while and loop, are introduced arbitrarily, language elements may explode and fall into an infinite logical circle of self justification.
This paragraph is taken from Wang Yin's "40 line code"_ tianxiamall_51CTO blog
Copyright notice: the content of this article is spontaneously contributed by Alibaba cloud real name registered users. The copyright belongs to the original author. Alibaba cloud developer community does not own its copyright or bear corresponding legal liabilities. Please check the specific rules< Alicloud developer community user service agreement >And< Alibaba cloud developer community intellectual property protection guidelines >. If you find any content suspected of plagiarism in this community, please fill in Infringement complaint form Report, once verified, the community will immediately delete the suspected infringement content.
mp4 code sap code uwp reports an error sqlite module ECS quote dialog box ecs system quot dialog box