|
Jupyter at Bryn Mawr College |
|
|
| Public notebooks: /services/public/dblank / CS245 Programming Languages / 2014-Fall / Notes | |||
Tail Call Optimization¶
Some interpreters and compilers can't get rid of the function call stack, but they can detect when there is nothing to be done after the recursive call. By not using a stack in that situation, they can at least optimize for that. This is called by various names:
- Tail Call Optimization (TCO)
- Tail Recursion Elimination (TRE)
- Tail Call Elimination
- Proper Tail Call handling
Tail Position¶
When there is nothing to be done after the recursive call, we say that the call is in "tail position".
Of course in a proper Scheme, we have continuations, so no function call is ever pushed onto a stack. There are many so-called Scheme implementations that just use a call stack for function calls. To me, this breaks a fundamental property of what a Scheme should be, and these implementations should be called something other than Scheme. Maybe Schlame?
Scheme¶
Berkeley CS61:¶
http://www-inst.eecs.berkeley.edu/~cs61a/sp14/proj/scheme/scheme.html
GNU C¶
Making the tail call not push onto the call stack is natural in a proper Scheme. In other languages that use a call stack, "tall call optimization" is often only performed when requested.
%%file testme.c
int main() {
return main(); // type must be same
}
%%shell
gcc testme.c -o testme
! ./testme
%%shell
gcc -O2 testme.c -o testme
! ./testme
So, this C program runs differently depending on how it is compiled.
Java, version 8¶
http://www.drdobbs.com/jvm/tail-call-optimization-and-java/240167044
"Therefore, it isn't a big deal to most Java developers that Java doesn't perform tail call optimization. In fact, my guess is that many Java developers have never even heard of this optimization. But it does become an issue when you run any of the related functional languages on top of the JVM. All of sudden, recursive code that ran fine with that language's interpreter may begin blowing the stack when executed on the JVM."
"It's important to note that this isn't a bug in the JVM. It's an optimization that can be implemented to help functional programmers who use recursion, which is much more common and normal in those languages. I recently spoke to Brian Goetz at Oracle about this optimization, and he said that it's on a list of things to be added to the JVM, but it's just not a high-priority item. For now, it's best to make this optimization yourself, if you can, by avoiding deeply recursive functions when coding a functional language on the JVM."
Python¶
Guido van Rossum
http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html
"TRE is incompatible with nice stack traces: when a tail recursion is eliminated, there's no stack frame left to use to print a traceback when something goes wrong later. This will confuse users who inadvertently wrote something recursive (the recursion isn't obvious in the stack trace printed), and makes debugging hard. Providing an option to disable TRE seems wrong to me: Python's default is and should always be to be maximally helpful for debugging."
CPython¶
%%python
import traceback
def fact(n):
if n == 1:
return x
else:
return n * fact(n - 1)
try:
fact(5)
except:
kernel.Error(traceback.format_exc())
Calysto Scheme¶
(define fact
(lambda (n)
(if (= n 1)
x
(* n (fact (- n 1))))))
(fact 5)
Guess what? Calysto Scheme has stack traces! And debugging!
"...The idea that TRE is merely an optimization, which each Python implementation can choose to implement or not, is wrong. Once tail recursion elimination exists, developers will start writing code that depends on it, and their code won't run on implementations that don't provide it: a typical Python implementation allows 1000 recursions, which is plenty for non-recursively written code and for code that recurses to traverse, for example, a typical parse tree, but not enough for a recursively written loop over a large list."
I agree. It should always be on.
"I don't believe in recursion as the basis of all programming. This is a fundamental belief of certain computer scientists, especially those who love Scheme and like to teach programming by starting with a "cons" cell and recursion. But to me, seeing recursion as the basis of everything else is just a nice theoretical approach to fundamental mathematics (turtles all the way down), not a day-to-day tool."
I never said that recursion was the basis of everything. I said that it is the right tool to use on recursive data structures, like the interpreter of a programming language. And for many problems, recursive data structures are a day-to-day occurrence.
"Of course, none of this does anything to address my first three arguments. Is it really such a big deal to rewrite your function to use a loop? (After all TRE only addresses recursion that can easily be replaced by a loop. :-)"
Nice use of the JK. Yes, it is a big deal. Use the right tool for the job!
Calysto Scheme¶
- Calysto Scheme is written in Scheme, in CPS
- It can be run and tested directly in Scheme
- Programs are data
- The Scheme CPS is read in by another program and written out as another Scheme program (continuations represented by data structures) [runnable]
- That is read in by another program, and written out again as a Scheme program (written in a simplified manner, with minimal requirements, called a register machine) [runnable]
- That is read in by another program, and written out as C# or as Python (or assembly language)
- The C# Scheme (Calico Scheme) program is compiled, run by Mono or .NET
- The Python Scheme (Calysto Scheme) program is run directly
"Programming languages are the box outside of which most programmers ... cannot think."
Jon Rossie, in http://www.cs.indiana.edu/~dfried/mex.ps
Here is what a human writes, in CPS:
(define* m
(lambda (exp env handler fail k)
(if *tracing-on?* (highlight-expression exp))
(let ((k (if *tracing-on?* (make-debugging-k exp k) k)))
(cases aexpression exp
(lit-aexp (datum info) (k datum fail))
(var-aexp (id info)
(lookup-value id env info handler fail k))
(lexical-address-aexp (depth offset id info)
(lookup-value-by-lexical-address depth offset (frames env) fail k))
(func-aexp (exp info)
(m exp env handler fail
(lambda-cont2 (proc fail)
(k (dlr-func proc) fail))))
(callback-aexp (exp info)
(m exp env handler fail
(lambda-cont2 (proc fail)
(k (callback proc) fail))))
(if-aexp (test-exp then-exp else-exp info)
(m test-exp env handler fail
(lambda-cont2 (bool fail)
(if bool
(m then-exp env handler fail k)
(m else-exp env handler fail k)))))
(help-aexp (var var-info info)
(lookup-variable var env var-info handler fail
(lambda-cont2 (var fail)
(k (help (dlr-env-lookup var)) fail))
(lambda-cont3 (dlr-obj components fail) ;; dlr-obj is Myro, components is (Myro robot)
(k (help (get-external-member dlr-obj components)) fail))
(lambda-cont2 (binding fail)
(k (binding-docstring binding) fail))))
(assign-aexp (var rhs-exp var-info info)
(m rhs-exp env handler fail
(lambda-cont2 (rhs-value fail)
(lookup-variable var env var-info handler fail
(lambda-cont2 (var fail)
(let ((old-value (dlr-env-lookup var)))
;; need to undo the assignment if we back up
(set-global-value! var rhs-value)
(let ((new-fail (lambda-fail () (set-global-value! var old-value) (fail))))
(k void-value new-fail))))
After step 1, data structures:
(define*
m
(lambda (exp env handler fail k)
(if *tracing-on?* (highlight-expression exp))
(let ((k (if *tracing-on?* (make-debugging-k exp k) k)))
(cases aexpression exp
(lit-aexp (datum info) (apply-cont2 k datum fail))
(var-aexp
(id info)
(lookup-value id env info handler fail k))
(lexical-address-aexp
(depth offset id info)
(lookup-value-by-lexical-address depth offset (frames env)
fail k))
(func-aexp
(exp info)
(m exp env handler fail (make-cont2 <cont2-69> k)))
(callback-aexp
(exp info)
(m exp env handler fail (make-cont2 <cont2-68> k)))
(if-aexp
(test-exp then-exp else-exp info)
(m test-exp env handler fail
(make-cont2 <cont2-67> else-exp then-exp env handler k)))
(help-aexp
(var var-info info)
(lookup-variable var env var-info handler fail (make-cont2 <cont2-66> k)
(make-cont3 <cont3-5> k) (make-cont2 <cont2-65> k)))
(assign-aexp
(var rhs-exp var-info info)
(m rhs-exp env handler fail
(make-cont2 <cont2-64> var var-info env handler k)))
(define-aexp
(var docstring rhs-exp info)
(m rhs-exp env handler fail
(make-cont2 <cont2-61> docstring var env handler k)))
(define!-aexp
(var docstring rhs-exp info)
(m rhs-exp env handler fail
(make-cont2 <cont2-59> docstring var k)))
After step 2, register machine:
(define*
m
(lambda ()
(if *tracing-on?* (highlight-expression exp_reg))
(let ((k 'undefined))
(set! k
(if *tracing-on?* (make-debugging-k exp_reg k_reg) k_reg))
(if (eq? (car exp_reg) 'lit-aexp)
(let ((datum 'undefined))
(set! datum (list-ref exp_reg 1))
(set! value2_reg fail_reg)
(set! value1_reg datum)
(set! k_reg k)
(set! pc apply-cont2))
(if (eq? (car exp_reg) 'var-aexp)
(let ((id 'undefined) (info 'undefined))
(set! info (list-ref exp_reg 2))
(set! id (list-ref exp_reg 1))
(set! k_reg k)
(set! var-info_reg info)
(set! var_reg id)
(set! pc lookup-value))
(if (eq? (car exp_reg) 'lexical-address-aexp)
(let ((depth 'undefined) (offset 'undefined))
(set! offset (list-ref exp_reg 2))
(set! depth (list-ref exp_reg 1))
(set! k_reg k)
(set! frames_reg (frames env_reg))
(set! offset_reg offset)
(set! depth_reg depth)
(set! pc lookup-value-by-lexical-address))
(if (eq? (car exp_reg) 'func-aexp)
(let ((exp 'undefined))
(set! exp (list-ref exp_reg 1))
(set! k_reg (make-cont2 <cont2-69> k))
(set! exp_reg exp)
(set! pc m))
(if (eq? (car exp_reg) 'callback-aexp)
(let ((exp 'undefined))
(set! exp (list-ref exp_reg 1))
(set! k_reg (make-cont2 <cont2-68> k))
(set! exp_reg exp)
After step 3, conversion to Python:
def m():
if true_q(_startracing_on_q_star):
highlight_expression(exp_reg)
k = symbol_undefined
k = (make_debugging_k(exp_reg, k_reg) if _startracing_on_q_star else k_reg)
if true_q((car(exp_reg)) is (symbol_lit_aexp)):
datum = symbol_undefined
datum = list_ref(exp_reg, 1)
GLOBALS['value2_reg'] = fail_reg
GLOBALS['value1_reg'] = datum
GLOBALS['k_reg'] = k
GLOBALS['pc'] = apply_cont2
else:
if true_q((car(exp_reg)) is (symbol_var_aexp)):
id = symbol_undefined
info = symbol_undefined
info = list_ref(exp_reg, 2)
id = list_ref(exp_reg, 1)
GLOBALS['k_reg'] = k
GLOBALS['var_info_reg'] = info
GLOBALS['var_reg'] = id
GLOBALS['pc'] = lookup_value
else:
if true_q((car(exp_reg)) is (symbol_lexical_address_aexp)):
depth = symbol_undefined
offset = symbol_undefined
offset = list_ref(exp_reg, 2)
depth = list_ref(exp_reg, 1)
GLOBALS['k_reg'] = k
GLOBALS['frames_reg'] = frames(env_reg)
GLOBALS['offset_reg'] = offset
GLOBALS['depth_reg'] = depth
GLOBALS['pc'] = lookup_value_by_lexical_address
else:
if true_q((car(exp_reg)) is (symbol_func_aexp)):
exp = symbol_undefined
exp = list_ref(exp_reg, 1)
GLOBALS['k_reg'] = make_cont2(b_cont2_69_d, k)
GLOBALS['exp_reg'] = exp
GLOBALS['pc'] = m
else:
if true_q((car(exp_reg)) is (symbol_callback_aexp)):
CPython¶
Written in C. Highly optimized by humans for 20 years.
PyPy¶
Python written in Python. Programming languages ideas applied automatically. Code that rewrites code, including JIT (Just In Time compiler).
Runs faster than CPython.
The power of writing your own language¶
Jim: "Hey, why don't we make Calysto Scheme be non-deterministic with backtracking?"
Doug: "Ok! Will that make it slow?"
Jim: "Let's see!"
(begin
(define x (choose 1 2 3))
(printf "You picked ~a~%" x)
(printf "I guess we are done with that!~%" x)
)
(choose)
x
(choose)
x
(choose)
Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an apartment house that contains only five floors. Baker does not live on the top floor. Cooper does not live on the bottom floor. Fletcher does not live on either the top or the bottom floor. Miller lives on a higher floor than does Cooper. Smith does not live on a floor adjacent to Fletcher's. Fletcher does not live on a floor adjacent to Cooper's. Where does everyone live?
(define distinct?
(lambda (nums)
(or (null? nums)
(null? (cdr nums))
(and (not (member (car nums) (cdr nums)))
(distinct? (cdr nums))))))
(distinct? '(1 2 3 4 5))
(distinct? '(1 2 3 4 5 1))
(define floors
(lambda ()
(let ((baker (choose 1 2 3 4 5))
(cooper (choose 1 2 3 4 5))
(fletcher (choose 1 2 3 4 5))
(miller (choose 1 2 3 4 5))
(smith (choose 1 2 3 4 5)))
(require (distinct? (list baker cooper fletcher miller smith)))
(require (not (= baker 5)))
(require (not (= cooper 1)))
(require (not (= fletcher 5)))
(require (not (= fletcher 1)))
(require (> miller cooper))
(require (not (= (abs (- smith fletcher)) 1)))
(require (not (= (abs (- fletcher cooper)) 1)))
(list
(list 'baker baker)
(list 'cooper cooper)
(list 'fletcher fletcher)
(list 'miller miller)
(list 'smith smith)))))
(floors)
(choose)