1Better Stack Traces
2===================
3Ideas from working on better stack traces.
4
5Abstract Call_Phrase
6--------------------
7Call_Phrase is a fully abstract class, representing an expression
8that calls a function.
9
10Call_Phrase
11    Represents an expression that calls a function.
12    Eg, like 'f x', but also 'value :: predicate'.
13    An abstract class, with subclasses like Juxta_Phrase.
14    Represents a function call. Methods arg_part() and func_part().
15    Benefits:
16    * cleaner.
17    * needed when general infix expressions become Call_Phrases.
18
19Shared<const Call_Phrase> Frame::call_phrase_
20    // If this is a function call frame, then call_phrase_ is the source code
21    // for the function call, otherwise it's nullptr.
22    //
23    // Program frames do not have a call_phrase_. If the call_phrase_ is null,
24    // then the frame does not appear in a stack trace.
25    //
26    // In the common case, *call_phrase_ is a Call_Phrase. However, in the
27    // case of a builtin function B that takes a function F as an argument,
28    // there is no Call_Phrase in Curv source code where F is called, so
29    // Call_Phrase is a best effort approximation, such as the call to B.
30
31Modified Tail Call Elimination
32------------------------------
33from: [[ideas/compiler/Tail_Recursion]]
34The original goal was to make stack traces complete for traditional
35imperative programs, while guaranteeing that tail-recursive loops
36do not blow up the stack. (Better stack traces for imperative programming.)
37
38    First, consider programs that do not treat functions as value: they are
39    not passed as arguments, returned as results, or stored in data structures.
40    For this subset of programs,
41    * If a program contains no recursion, then no tail call frames are elided.
42      Stack traces are the same as you expect in an imperative language.
43    * If there is recursion, then for a tail call to a recursive function,
44      within a recursive function, the new stack frame is elided.
45
46    Next, consider programs that treat functions as data (a characteristic of
47    functional programming style). Consider tail calls where the identity of
48    the function is not determined until run time. These function calls might
49    be part of a tail recursive loop, but as a first approximation, we don't
50    know. So to be safe, the frames for these tail calls are elided.
51
52    These rules try to achieve two goals:
53    1. We guarantee that tail-recursive loops will not blow up the stack.
54    2. Imperative-style programs will have imperative-style stack traces,
55       except in cases where this violates goal 1.
56
57What rules would achieve these goals, and do they help in fixing the bug?
58
591. We identify recursive functions during analysis. We add a 'recursive' flag
60to Function values. A tail call to a recursive function elides the caller's
61stack frame, based on a dynamic check of the Function value.
62* This doesn't work for the Y combinator, which achieves recursion without
63  using recursive functions. I need to mark function calls at analysis time.
64  A call to a non-constant function is considered recursive.
65
66Current behaviour:
67    FAILALL(
68        "let\n"
69        "    f x = g x + 2;\n"
70        "    g x = h x;\n"
71        "    h x = x + 1;\n"
72        "in f true\n"
73    ,
74        "#true + 1: domain error\n"
75        "at function h:\n"
76        "4|     h x = x + 1;\n"
77        "             ^^^^^ \n"
78        "at function g:\n"
79        "3|     g x = h x;\n"
80        "             ^^^ \n"
81        "at:\n"
82        "5| in f true\n"
83        "      ^^^^^^"
84    );
85
86I'm not happy with the rule. I want the location
87    f x = g x + 2
88          ^^^
89to appear in the stack trace, since f is a non-recursive function.
90The g->h->g->h-> loop can have just the final call represented.
91
92It would be nice to have a visual indication that frames are elided.
93* In the current implementation, we can compare frame->parent->caller
94  to the current function or something and detect call frame elision.
95
962. A tail call from a recursive function, to a recursive function, elides
97the caller's stack frame, and sets a flag in the callee frame that previous
98frames were elided.
99