<commit_before>                FOL as an Intermediate Representation

FOL is not really a programming language; it's an intermediate
representation for the insides of a compiler.  It happens to print out
like Scheme code, which makes it much easier to read; and it happens
to ship with a direct interpreter, which gives it a semantics that can
be used to verify correctness of transformations; but how else is it
different from any other intermediate representation?

FOL occupies a slot in the architecture of VL and DVL that is parallel
to the place where control flow graphs (CFGs) usually sit in other
compilers.  Like a CFG, FOL source statically exposes as much
information about the dynamic control flow of the program it
represents as it possibly can.  Like a CFG, FOL is therefore amenable
to flow-based optimizations, like elimination of dead variables and
common subexpressions.

Given that fundamental similarity, however, there are a number of
substantial differences.  I compare here to the representations in
Appel [1], since those are the ones I know.  In particular, I compare
to Control Flow Graphs (Chapters 17 and 18), Static Single Assignment
Form (Chapter 19), and the otherwise nameless Functional
Representation (19.7).  CFGs and SSA are equivalent, so I will only
remark on them separately at need.

- FOL is oriented around expressions, whereas CFGs are oriented around
  instructions.  Expressions have substructure, and the substructures
  have implicit returns, whereas CFG instructions just read stored
  data for their arguments.  Sufficiently aggressive conversion to
  A-normal form erases this difference.

- All variables in a CFG are in scope in the entire graph, whereas FOL
  bindings have scope.  This is not an essential difference.

- The CFGs from [1] allow assignments to their variables, whereas FOL
  does not.  This is not an essential difference; conversion to SSA
  mitigates it and conversion to the functional representation eliminates
  it entirely.

- The model of un-analyzed memory is different: All three of Appel's
  intermediate representations have primitives that read or write a
  global store at computed indexes, whereas FOL has primitives that
  construct and access immutable objects on a garbage-collected heap.
  I don't think this is an essential difference; just that the
  understanding of the behavior of control is done with respect to a
  different level of abstraction of the memory system.

- Appel and FOL make a different subdivision of the entire program
  into "procedures".  Appel does not discuss how to represent a whole
  program; presumably a map from procedure names to the CFGs for those
  procedures would do.

  - An Appel procedure is a CFG; as such it contains labels and
    branches, so it may run loops, but does not have access to a stack
    (except for calling other procedures, but those are intentionally
    outside the scope of the analyses he discusses).

  - A FOL procedure cannot have loops.  Viewed as a CFG it is
    additionally restricted to be acyclic.

- These subdivisions have different effects on ease of analysis:

  If we are no longer analyzing any data that flows through the
  backing memory (Appel's store or FOL's data structure slots), then
  CFGs are restricted to unbounded-time but bounded-space
  computations.  If we further do not work too hard on discerning the
  different data values that may grace a CFG's variables, they become
  finite-state (except for the non-determinism of multiple possible
  continuations of a branch), and can therefore be analyzed by
  iterating some dataflow crunch to convergence.

  FOL procedures, being more restricted, are easier to analyze: since
  the control flow graph is acyclic, you can do a data flow analysis
  on it in one sweep, provided you sweep in the topological sort order
  (or in reverse).

  In fact, representing FOL procedures as Scheme source code has the
  effect of storing them in a tree whose in-order traversal is a
  topological sort traversal of the control flow graph they represent.

  FOL procedures are not, however, Appel's basic blocks: those are CFG
  subgraphs all but one of whose vertices has out-degree one and all
  but (a different) one of whose vertices has in-degree one.  Basic
  blocks are even easier to analyze, because you don't have to worry
  about branch-points or join-points.

- These subdivisions also have different effects on how whole programs
  are broken up:

  A CFG can represent a larger class of computations (bounded space
  but unbounded time) directly, so a whole program can be broken up
  into fewer CFG procedures; and less information is lost by
  forgetting information across procedure boundaries.

  Conversely, a FOL procedure can only represent a smaller class of
  computations (bounded space and time), so a FOL program may need to
  have more procedures, and lose more information across procedure
  boundaries.  In particular, FOL has no mechanism of allowing a
  single variable to remain in scope over a loop (indeed, all FOL
  variables are in scope over a bounded number of dynamic operations),
  so FOL cannot express the loop optimizations that are the subject of
  Appel's Chapter 18.

- FOL could be extended to match the expressive power of Appel's CFGs
  by adding a construct for locally defining (potentially
  mutually-recursive) functions that (may not be passed around as data
  and) may be called only in tail position.  The names of these
  functions would then behave like the labels of a standard CFG.  In
  fact, I believe this is exactly what Appel had in mind when he
  defined the "functional representation" in section 19.7 of [1],
  except that he didn't say that the local functions may be called
  only in tail position.

  The restriction to call these local functions only in tail position
  would have the effect that anything that looks like a return either
  flies into a statically known let binding, or flies out of the
  entire FOL-procedure; in one case the control transfer from a return
  is known, and in the other it is not modeled by an intraprocedural
  analysis.


[1] Appel, <NAME>.  "Modern Compiler Implementation in ML".
Cambridge University Press, 2004.

----------------------------------------------------------------------

The thing that's unique about interprocedural stuff is that control
flows out of a procedure call into a place that's determined by the
place where it flowed in, and we care about tracing the correspondence
(whether it's implemented by watching the control flow explicitly or
by doing some data flow on some token (or continuation function) that
says where to go is immaterial).

----------------------------------------------------------------------

FOL intraprocedural: Dataflows on an acyclic control flow graph.  This
implies a bounded execution time and therefore a finite number of
modeled memory bits.  These are easy to do by following a topological
sort of the control flow graph (FOL source happens to store these
graphs in topologically sorted form).  Break the full program into
pieces with acyclic control (FOL procedures) and don't model flows of
control or data across the introduced boundaries.

Appel intraprocedural: Dataflows with a finite number of modeled bits
of data but an arbitrary control flow graph.  Break the whole program
into pieces (procedures) that each only use a finite number of modeled
bits of memory (temporaries), and don't model flows of control or data
across the boundaries of these pieces.

Interprocedural: Dataflows with unbounded modeled locations (because
of the procedure stack) and an arbitrary control flow graph.  Since
this is Turing complete, you can't ever get this "right".  You have to
forget somewhere.

The latter but also tracking context: control will flow out of a
procedure call into a place that is determined by where it flowed into
that procedure call.
- Also, if control flowed from here, then I know this about the data
  that flowed in, which I don't know in general.
- I think you can go quite wild wrt the fineness of the context you
  track.

----------------------------------------------------------------------

The art of analyzing programs is the art of forgetting judiciously.
If you forget nothing at all, your "analysis" will consist exactly of
running the entire program and writing down the answer.  In this case,
you will have "accelerated" the program a great deal, but the analysis
will be very slow (namely the runtime of the program) and its range of
validity will be that one run of that one program, so you will not be
able to reuse it.  If you forget everything, your analysis will
consist of doing nothing, will be very fast and very broadly
applicable, but will permit no improvement to the program you were
analyzing.

Different optimizing analyses are characterized by what they model and<commit_msg>Proofreading.  One paragarph turns out to be sufficient to capture what I wanted to capture about interprocedural stuff.<commit_after>                FOL as an Intermediate Representation

FOL is not really a programming language; it's an intermediate
representation for the insides of a compiler.  It happens to print out
like Scheme code, which makes it much easier to read; and it happens
to ship with a direct interpreter, which gives it a semantics that can
be used to verify correctness of transformations; but how else is it
different from any other intermediate representation?

FOL occupies a slot in the architecture of VL and DVL that is parallel
to the place where control flow graphs (CFGs) usually sit in other
compilers.  Like a CFG, FOL source statically exposes as much
information about the dynamic control flow of the program it
represents as it possibly can.  Like a CFG, FOL is therefore amenable
to dataflow-based optimizations, like elimination of dead variables
and common subexpressions.

Given that fundamental similarity, however, there are a number of
substantial differences.  I compare here to the CFGs in Appel [1],
since those are the ones I know.  Appel discusses three variants:
plain vanilla CFGs (Chapters 17 and 18), Static Single Assignment Form
(Chapter 19), and the otherwise nameless "functional representation"
(19.7).  Since they are all equivalent, I will compare to CFGs, and
mention the others at need.

- FOL is oriented around expressions, whereas CFGs are oriented around
  instructions.  Expressions have substructure, and the substructures
  have implicit returns, whereas CFG instructions just read stored
  data for their arguments.  Sufficiently aggressive conversion to
  A-normal form erases this difference.

- All variables in a CFG are in scope in the entire graph, whereas FOL
  bindings have scope.  This is not an essential difference; and
  bindings in the functional representation have scope too.

- CFGs allow assignments to their variables, whereas FOL does not.
  This is not an essential difference; conversion to SSA mitigates it
  and conversion to the functional representation eliminates it
  entirely.

- The model of un-analyzed memory is different: All three of Appel's
  intermediate representations have primitives that read or write a
  global store at computed indexes, whereas FOL has primitives that
  construct and access immutable objects on a garbage-collected heap.
  I don't think this is an essential difference; just that the
  understanding of the behavior of control is done with respect to a
  different level of abstraction of the memory system.

- Appel and FOL make a different subdivision of the entire program
  into "procedures".  Appel does not discuss how to represent a whole
  program; presumably a map from procedure names to the CFGs for those
  procedures would do.

  - An Appel procedure is a CFG; as such it contains labels and
    branches, so it may run loops, but does not have access to a stack
    (except for calling other procedures, but those are intentionally
    outside the scope of the analyses he discusses).

  - A FOL procedure cannot even have loops.  Viewed as a CFG it is
    additionally restricted to be acyclic.

- These subdivisions have different effects on ease of analysis:

  If we are no longer analyzing any data that flows through the
  backing memory (Appel's store or FOL's data structure slots), then
  CFGs are restricted to unbounded-time but bounded-space
  computations.  If we further do not work too hard on discerning the
  different data values that may grace a CFG's variables, they become
  finite-state (except for the non-determinism of multiple possible
  continuations of a branch), and can therefore be analyzed by
  iterating some dataflow crunch to convergence.

  FOL procedures, being more restricted, are easier to analyze: since
  the control flow graph is acyclic, you can do a data flow analysis
  on it in one sweep, provided you sweep in the topological sort order
  (or in reverse).  This is both simpler to code and faster to
  execute.

  In fact, the representation of FOL procedures as Scheme source code
  has the effect of storing them in a tree whose in-order traversal is
  a topological sort traversal of the control flow graph they
  represent.

  FOL procedures are not, however, Appel's basic blocks: those are CFG
  subgraphs all but one of whose vertices has out-degree one and all
  but (a different) one of whose vertices has in-degree one.  Basic
  blocks are even easier to analyze, because you don't have to worry
  about branch-points or join-points.

- These subdivisions also have different effects on how whole programs
  are broken up:

  A CFG can represent a larger class of computations (bounded space
  but unbounded time) directly, so a whole program can be broken up
  into fewer CFG procedures; and less information is lost by
  forgetting information across procedure boundaries.

  Conversely, a FOL procedure can only represent a smaller class of
  computations (bounded space and time), so a FOL program may need to
  have more procedures, and lose more information across procedure
  boundaries.  In particular, FOL has no mechanism of allowing a
  single variable to remain in scope over a loop (indeed, all FOL
  variables are in scope over a bounded number of dynamic operations),
  so FOL cannot express the loop optimizations that are the subject of
  Appel's Chapter 18.

- FOL could be extended to match the expressive power of Appel's CFGs
  by adding a construct for locally defining (potentially
  mutually-recursive) functions that (may not be passed around as data
  and) may be called only in tail position.  The names of these
  functions would then behave like the labels of a standard CFG.  In
  fact, I believe this is exactly what Appel had in mind when he
  defined the "functional representation" in Section 19.7 of [1],
  except that he didn't say that the local functions may be called
  only in tail position.

  The restriction to call these local functions only in tail position
  would have the effect that anything that looks like a return either
  flies into a statically known let binding, or flies out of the
  entire FOL-procedure; in one case the control transfer from a return
  is known, and in the other it is not modeled by an intraprocedural
  analysis.

- Inter-FOL-procedural analyses share some elements in common with
  intra-CFG-analyses, namely that they have to iterate some dataflow
  crunch to convergence; but there is more hair, for two reasons: The
  implicit stack means that you may be modeling an unbounded number of
  memory locations; and you may also wish to model the fact that a
  procedure will return to its caller.  The latter means that the call
  graph of the procedures is no longer the approximation you want for
  the control flow of a program implemented with those procedures.


[1] Appel, <NAME>.  "Modern Compiler Implementation in ML".
Cambridge University Press, 2004.

----------------------------------------------------------------------

The art of analyzing programs is the art of forgetting judiciously.
If you forget nothing at all, your "analysis" will consist exactly of
running the entire program and writing down the answer.  In this case,
you will have "accelerated" the program a great deal, but the analysis
will be very slow (namely the runtime of the program) and its range of
validity will be that one run of that one program, so you will not be
able to reuse it.  If you forget everything, your analysis will
consist of doing nothing, will be very fast and very broadly
applicable, but will permit no improvement to the program you were
analyzing.

Different optimizing analyses are characterized by what they model and
{'fraction_non_alphanumeric': 0.04455741626794258, 'fraction_numerical': 0.00257177033492823, 'mean_word_length': 3.7489349616586196, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4658065', 'n_tokens_mistral': 4156, 'n_tokens_neox': 3903, 'n_words': 2599}