<p>Starting with a representation of a item of computation as an object which includes a method says how to perform the next step of its computation.</p>
<pre><code>// a statement, expression etc.
class ExecutableThing
{
   executeStep(C:Context );
}
</code></pre>
<p>Where context here is the execution environment including all the variables in scope.</p>
<p>Now consider a block which is an ordered collection of things to execute following the composite pattern, pseudo code below:</p>
<pre><code>// a statement, expression etc.
class ExecutableThing
{
   X executeStep(C:Context );
}

class Block implements ExecutableThing
{
    vector&lt;ExecutableThing&gt; statements;

    X executeStep(C:Context);
};
</code></pre>
<p>Where X represents an output that indicates what to execute next.</p>
<p>Is that definition sufficient to make it correct to call X a continuation?</p>
<p>There are different ways to think of this.
Taking a very low-level view the vector of statements could be like machine code instructions. The block could be a linear representation of the entire program.
X could be a token meaning increment the program counter.
It could be the program counter itself (for implementing a jump instruction)</p>
<p>For a low-level model where X literally <em>is</em> the program counter would it still be correct to call that program counter a continuation?</p>
<p>Taking a higher level view where X exists in code (rather than being something happening inside a CPU) its a pointer to the next thing to step into.
For the 'block' that pointer is (or includes) an iterator into the vector of statements.
But is still essentially acting as a program counter.</p>
<p>In my mind a continuation normally includes a reference to the execution context. For example, at the very least, a pointer to an activation record in a stack. So calling X a continuation feels wrong.</p>
<p>Depending on your implementation the 'program counter' could literally be a variable in the context.
Such that X means:</p>
<pre><code>context.PC += 1         // for a normal 'statement'

context.PC = address    // for a jump statement.
</code></pre>
<p>Does that make the context its own continuation?</p>
<p>Are there rigorous definitions of the following terms that distinguish them from and relate them to each other?</p>
<ul>
<li>Program Counter</li>
<li>Continuation</li>
<li>Context</li>
<li>Environment</li>
<li>Scope</li>
<li>Activation Record</li>
</ul>
<p>I think its fair to start by saying that a program counter and an activation record are low level implementation details of one or more of the higher level concepts.</p>
<p>I've added environment and scope there as alternative words for context, though I personally think of scope as &quot;set set of variables visible from a given execution context&quot;.</p>
<p>Here's what I have so far please fill in holes as appropriate</p>
<ul>
<li><p>Program Counter</p>
<ul>
<li>a low-level variable points to the next instruction to be executed.</li>
<li>typically a control flow register in a CPU</li>
</ul>
</li>
<li><p>Continuation</p>
<ul>
<li>an object which can be passed to something to indicate where control flow should proceed once its execution has completed.</li>
</ul>
</li>
<li><p>Context</p>
<ul>
<li>the environment in which something executes</li>
<li>includes variables in scope</li>
<li>may also includes some structures relating to control flow
(for example pointers to parent contexts)</li>
</ul>
</li>
<li><p>Environment</p>
<ul>
<li>an alternative word for context</li>
</ul>
</li>
<li><p>Scope</p>
<ul>
<li>the set of variables visible from a given execution context
This is more a logical concept than something you implement.
For example in some implementations the variables in scope might be those from the<br />
current context and any of its parents</li>
</ul>
</li>
<li><p>Activation Record</p>
<ul>
<li>The implementation of a context as a stack frame</li>
<li>composing activation records produces a call stack</li>
</ul>
</li>
</ul>

<control-flow>
Correct terminology and relationship between program counters, continuations & contexts
<p>Some of the terms are ambiguous without additional context. However, here is generally how I would define them:</p>
<ul>
<li><p>The <strong>program counter</strong> is a register of a machine (physical or abstract) that keeps track of the point of execution in a linear stream of instructions. In stored-program computers with addressable program memory, it usually corresponds to a memory address.</p>
</li>
<li><p>The <strong>continuation</strong> refers to “the remainder of the program” at any given point of evaluation. This can be represented in many different forms. In physical computers and <a href="https://en.wikipedia.org/wiki/CEK_Machine" rel="nofollow noreferrer">CEK-style abstract machines</a>, the continuation corresponds to the program counter and call stack. In <a href="https://en.wikipedia.org/wiki/Operational_semantics#Reduction_semantics" rel="nofollow noreferrer">reduction semantics</a>, the continuation corresponds to the portion of the expression that is <em>not</em> the <strong>redex</strong>, which is the minimal subexpression currently being reduced.</p>
<ul>
<li><p>A <strong>first-class continuation</strong> is a value in a programming language obtained by reifying (or <em>capturing</em>) the continuation at some point of execution. The continuation can then be <em>applied</em> or <em>restored</em> to either extend or replace the current continuation with the captured continuation.</p>
</li>
<li><p><a href="https://stackoverflow.com/questions/29838344/what-exactly-is-a-continuation-prompt/29838823#29838823">A <strong>delimited continuation</strong> is a slice of the continuation <em>delimited</em> by some delimiting operator</a>, like <code>try ... catch</code>. A <strong>first-class, delimited continuation</strong> is a delimited continuation reified as a value in the programming language.</p>
</li>
<li><p>All of this stuff can be very confusing without examples and diagrams. Fortunately, <a href="https://www.youtube.com/watch?v=TE48LsgVlIU" rel="nofollow noreferrer">I gave a talk that goes into great detail</a> just a few weeks ago, which has both.</p>
</li>
</ul>
</li>
<li><p>A <strong>context</strong> can be any number of things, depending on… context. Sometimes it refers to an environment. Sometimes it refers to a continuation, particularly when called an <strong>evaluation context</strong>. But it is a very overloaded term.</p>
</li>
<li><p>An <strong>environment</strong> refers to a mapping from variables to types or values. An interpreter maintains an environment that keeps track of the values of variables that are in scope. A compiler maintains a <strong>type environment</strong> that keeps track of the types of variables within a particular expression.</p>
<p>A common aspect of an environment is that it is extended within certain subexpressions in a program. For example, a lambda expression extends the environment within its body. So an environment can be thought of as a flattened mapping that captures a cascade of nested scopes.</p>
</li>
<li><p>The <strong>scope</strong> of a variable binding refers to all of the places where it is <em>bound</em>, i.e. places it can be referenced from.</p>
<ul>
<li><p><strong>Lexical scope</strong> refers to a scoping scheme where the scope of a variable is determined by the relative positions of expressions <em>within the source code</em>.</p>
</li>
<li><p><strong>Dynamic scope</strong> refers to a scoping scheme where the scope of a variable is determined by the continuation (which is a dynamic property of program control flow).</p>
</li>
<li><p>Most modern languages use lexical scope, but dynamic scope is still common in the form of environment variables or (in most shells) shell variables.</p>
</li>
</ul>
</li>
<li><p>An <strong>activation record</strong> is a stack frame that is pushed by the invocation of a procedure and is used to store the return address of its caller and any local variables. In many languages, especially imperative ones, the phrase “activation record” is effectively synonymous with “stack frame”, though some languages may also have other types of stack frames.</p>
</li>
</ul>
<p>Going into great detail about each and every one of these terms would be far too broad for a single answer. Consider asking more specific followup questions if you want to learn more.</p>

CC BY-SA 4.0
2023-06-28T05:30:51.097Z
2023-07-06T17:17:04.060Z
2023-07-06T17:17:04.060Z
Alexis King
# Correct terminology and relationship between program counters, continuations & contexts
Posted by: username_0 on 2023-05-28
Starting with a representation of a item of computation as an object which includes a method says how to perform the next step of its computation.
// a statement, expression etc.
class ExecutableThing
{
   executeStep(C:Context );
}

Where context here is the execution environment including all the variables in scope.
Now consider a block which is an ordered collection of things to execute following the composite pattern, pseudo code below:
// a statement, expression etc.
class ExecutableThing
{
   X executeStep(C:Context );
}

class Block implements ExecutableThing
{
    vector statements;

    X executeStep(C:Context);
};

Where X represents an output that indicates what to execute next.
Is that definition sufficient to make it correct to call X a continuation?
There are different ways to think of this.
Taking a very low-level view the vector of statements could be like machine code instructions. The block could be a linear representation of the entire program.
X could be a token meaning increment the program counter.
It could be the program counter itself (for implementing a jump instruction)
For a low-level model where X literally is the program counter would it still be correct to call that program counter a continuation?
Taking a higher level view where X exists in code (rather than being something happening inside a CPU) its a pointer to the next thing to step into.
For the 'block' that pointer is (or includes) an iterator into the vector of statements.
But is still essentially acting as a program counter.
In my mind a continuation normally includes a reference to the execution context. For example, at the very least, a pointer to an activation record in a stack. So calling X a continuation feels wrong.
Depending on your implementation the 'program counter' could literally be a variable in the context.
Such that X means:
context.PC += 1         // for a normal 'statement'

context.PC = address    // for a jump statement.

Does that make the context its own continuation?
Are there rigorous definitions of the following terms that distinguish them from and relate them to each other?

Program Counter
Continuation
Context
Environment
Scope
Activation Record

I think its fair to start by saying that a program counter and an activation record are low level implementation details of one or more of the higher level concepts.
I've added environment and scope there as alternative words for context, though I personally think of scope as "set set of variables visible from a given execution context".
Here's what I have so far please fill in holes as appropriate

Program Counter

a low-level variable points to the next instruction to be executed.
typically a control flow register in a CPU


Continuation

an object which can be passed to something to indicate where control flow should proceed once its execution has completed.


Context

the environment in which something executes
includes variables in scope
may also includes some structures relating to control flow
(for example pointers to parent contexts)


Environment

an alternative word for context


Scope

the set of variables visible from a given execution context
This is more a logical concept than something you implement.
For example in some implementations the variables in scope might be those from the
current context and any of its parents


Activation Record

The implementation of a context as a stack frame
composing activation records produces a call stack
**Tags:** control-flow
---
## 1 answers
### Answer by username_1 on 2023-06-28. Score: 8
Some of the terms are ambiguous without additional context. However, here is generally how I would define them:

* The **program counter** is a register of a machine (physical or abstract) that keeps track of the point of execution in a linear stream of instructions. In stored-program computers with addressable program memory, it usually corresponds to a memory address.
* The **continuation** refers to “the remainder of the program” at any given point of evaluation. This can be represented in many different forms. In physical computers and [CEK-style abstract machines](https://en.wikipedia.org/wiki/CEK_Machine), the continuation corresponds to the program counter and call stack. In [reduction semantics](https://en.wikipedia.org/wiki/Operational_semantics#Reduction_semantics), the continuation corresponds to the portion of the expression that is *not* the **redex**, which is the minimal subexpression currently being reduced.

  + A **first-class continuation** is a value in a programming language obtained by reifying (or *capturing*) the continuation at some point of execution. The continuation can then be *applied* or *restored* to either extend or replace the current continuation with the captured continuation.
  + [A **delimited continuation** is a slice of the continuation *delimited* by some delimiting operator](https://stackoverflow.com/questions/29838344/what-exactly-is-a-continuation-prompt/29838823#29838823), like `try ... catch`. A **first-class, delimited continuation** is a delimited continuation reified as a value in the programming language.
  + All of this stuff can be very confusing without examples and diagrams. Fortunately, [I gave a talk that goes into great detail](https://www.youtube.com/watch?v=TE48LsgVlIU) just a few weeks ago, which has both.
* A **context** can be any number of things, depending on… context. Sometimes it refers to an environment. Sometimes it refers to a continuation, particularly when called an **evaluation context**. But it is a very overloaded term.
* An **environment** refers to a mapping from variables to types or values. An interpreter maintains an environment that keeps track of the values of variables that are in scope. A compiler maintains a **type environment** that keeps track of the types of variables within a particular expression.

  A common aspect of an environment is that it is extended within certain subexpressions in a program. For example, a lambda expression extends the environment within its body. So an environment can be thought of as a flattened mapping that captures a cascade of nested scopes.
* The **scope** of a variable binding refers to all of the places where it is *bound*, i.e. places it can be referenced from.

  + **Lexical scope** refers to a scoping scheme where the scope of a variable is determined by the relative positions of expressions *within the source code*.
  + **Dynamic scope** refers to a scoping scheme where the scope of a variable is determined by the continuation (which is a dynamic property of program control flow).
  + Most modern languages use lexical scope, but dynamic scope is still common in the form of environment variables or (in most shells) shell variables.
* An **activation record** is a stack frame that is pushed by the invocation of a procedure and is used to store the return address of its caller and any local variables. In many languages, especially imperative ones, the phrase “activation record” is effectively synonymous with “stack frame”, though some languages may also have other types of stack frames.

Going into great detail about each and every one of these terms would be far too broad for a single answer. Consider asking more specific followup questions if you want to learn more.
---
