# `executable_semantics` execution The code in this directory defines all phases of program execution after parsing, including typechecking, name resolution, and execution. The overall flow can be found in [`ExecProgram`](exec_program.cpp), which executes each phase in sequence. ## The Carbon abstract machine Execution is specified in terms of an abstract machine, which executes minimal program steps in a loop until the program terminates. The state of the Carbon program (including the stack as well as the heap) is represented explicitly in C++ data structures, rather than implicitly in the C++ call stack. The [`Interpreter`](interpreter.cpp) class represents an instance of the abstract machine, and is responsible for maintaining those data structures and implementing the steps of abstract machine execution. The control-flow state of the abstract machine is encapsulated in an [`ActionStack`](action_stack.h) object, which a represents a stack of [`Action`s](action.h). An `Action` represents a self-contained computation (such as evaluation of an expression or execution of a statement) as a state machine, and the abstract machine proceeds by repeatedly executing the next state transition of the `Action` at the top of the stack. Executing a step may modify the internal state of the `Action`, and may also modify the `Action` stack, for example by pushing a new `Action` onto it. When an `Action` is done executing, it can optionally produce a value as its result, which is made available to the `Action` below it on the stack. Carbon values are represented as [`Value`](value.h) objects, both at compile time and at run time. Note that in Carbon, a type is a kind of value, so types are represented as `Value`s. More subtly, `Value` can also represent information that isn't a true Carbon value, but needs to be propagated through channels that use `Value`. Most notably, certain kinds of `Value` are used to represent the result of "evaluating" a `Pattern`, which evaluates all the subexpressions nested within it, while preserving the structure of the non-expression parts for use in pattern matching. `Value`s are always immutable. The abstract machine's mutable memory is represented using the [`Heap`](heap.h) class, which is essentially a mapping of [`Address`es](address.h) to `Value`s. ### Example To evaluate the expression `((1 + 2) + 3)`, the interpreter starts by pushing an `Action` onto the stack that corresponds to the whole expression: `((1 + 2) + 3)`[0]{} :: ... In this notation, we're expressing the stack as a sequence of `Action`s separated by `::`, with the top at the left, and representing each `Action` as the expression it evaluates, followed by its state. The state of an `Action` currently consists of: - An integer `pos`, which is initially 0 and usually counts the number of steps executed. Here that's denoted with a number in square brackets. - A vector `results`, which collects the results of any sub-`Action`s spawned by the `Action`. Here that's denoted by a list in curly braces. Then the interpreter proceeds by repeatedly taking the next step of the `Action` at the top of the stack. For expression `Action`s, `pos` typically identifies the operand that the next step should begin evaluation of. In this case, that operand is the expression `(1 + 2)`, so we push a new `Action` onto the stack, and increment `pos` on the old one: `(1 + 2)`[0]{} :: `((1 + 2) + 3)`[1]{} :: ... The next step spawns an action to evaluate `1`: `1`[0]{} :: `(1 + 2)`[1]{} :: `((1 + 2) + 3)`[1]{} :: ... That expression can be fully evaluated in a single step, so the next step evaluates it, appends the result to the next `Action` down the stack, and pops the now-completed `Action` off the stack: `(1 + 2)`[1]{1} :: `((1 + 2) + 3)`[1]{} :: ... The top `Action`'s `pos` is 1, so the next step begins evaluation of the second operand: `2`[0]{} :: `(1 + 2)`[2]{1} :: `((1 + 2) + 3)`[1]{} :: ... Which again can be evaluated immediately: `(1 + 2)`[2]{1, 2} :: `((1 + 2) + 3)`[1]{} :: ... This expression has two operands, so now that `pos` is 2, all operands have been evaluated, and their results are in the corresponding entries of `results`. Thus, the next step can compute the expression value, passing it down to the parent `Action` and popping the completed action as before: `((1 + 2) + 3)`[1]{3} :: ... Evaluation now proceeds to the second operand: `3`[0]{} :: `((1 + 2) + 3)`[2]{3} :: ... Which, again, can be evaluated immediately: `((1 + 2) + 3)`[2]{3, 3} :: ... `pos` now indicates that all subexpressions have been evaluated, so the next step computes the final result of 6, and passes it down the stack.