1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
= Tail call optimization
JavaScript does not (yet) support tail call optimization.
To circumvent this limitation, and mitigate stack overflows, the Js_of_ocaml
compiler optimizes some common tail call patterns.
Besides, all tail calls are optimized when you set the flag
{{{--enable=effects}}}, at the cost of some performance degradation.
=== Self tail recursive
Self tail recursive function are compiled into a loop.
==== OCaml
<<code language="ocaml"|
let rec fact x acc =
if x = 0
then acc
else fact (pred x) (acc * x)
>>
==== JavaScript
<<code language="javascript"|
function fact(x,acc){
var x$0=x,acc$0=acc;
for(;;){
if(0===x$0) return acc$0;
var acc$1=caml_mul(acc$0,x$0),
x$1=x$0-1|0,
x$0=x$1,
acc$0=acc$1;
continue
}
}
>>
=== Mutually tail recursive functions
Mutually tail recursive functions are compiled using a trampoline.
Note that the generated code does not return to the trampoline at every
recursive call to prevent too much slow down.
==== OCaml
<<code language="ocaml"|
let rec even n =
match n with
| 0 -> true
| x -> odd (x-1)
and odd n =
match n with
| 0 -> false
| x -> even (x-1);;
>>
==== JavaScript
<<code language="javascript"|
function even$0(counter,n){
if(0===n)return 1;
var _e_=n-1|0;
if(counter<50){
var counter$0=counter+1|0;
return odd$0(counter$0,_e_)
}
return caml_trampoline_return(odd$0,[0,_e_])
}
function odd$0(counter,n){
if(0===n)return 0;
var _d_=n-1|0;
if(counter<50){
var counter$0=counter+1|0;
return even$0(counter$0,_d_)
}
return caml_trampoline_return(even$0,[0,_d_])
}
function even(n){return caml_trampoline(even$0(0,n))}
function odd(n){return caml_trampoline(odd$0(0,n))}
>>
== Examples of pattern not optimized
Recursive function where the tail call is made inside an intermediate function.
<<code language="ocaml"|
let rec f x =
let g delta = f (x - delta) in
if x < 0 then 0
else if x mod 2 = 0
then g 2
else g 1;;
>>
Tail call of a function given as argument
<<code language="ocaml"|
let bind x f =
match x with
| None -> None
| Some x -> f x
>>
Note that in the future, more tail call optimizations could be perform with function specialization and
better inlining.
|
