programmer and corresponds to the encoder associated with the encoder-decoder
architectures used in machine translation and dialogue management. The
(dialogue context) encoder ingests the $N$ words prior to the last utterance.
The (episodic memory) encoder ingests older dialogue selected from episodic
memory. The attentional machinery responsible for the selection and active
maintenance of relevant circuits in the global workspace (GWS) will likely
notice and attend to every utterance produced by the programmer. Attentional
focus and active maintenance of such circuits in the GWS will result in the
corresponding thought vector added to NTM the partition responsible for short-
term memory.

The controller for the NTM partition responsible for short-term (active)
memory then generates keys from the newly added thought vectors and transmits
these keys to the controller of the NTM partition responsible for long-term
(episodic) memory. The episodic memory controller uses these keys to select
episodic memories relevant to the current discourse, combining the selected
memories into a fixed-length composite thought vector that serves as input for
the corresponding encoder. Figure 12 depicts the basic architecture showing
only two of the three encoders and their associated attention networks,
illustrating how the outputs of the attention networks are combined prior to
being used by the decoder to generate the next word or words in the
assistant’s next utterance.

Figure 12: In the programmer’s assistant, the dialogue management and program-
transformation systems are implemented using encoder-decoder sequence-to-
sequence networks with attention. We adapt the pointer-generator network model
developed by See et al [85] to combine and bring to bear contextual
information from multiple sources including short- and long-term memory
systems implemented as Neural Turing Machines as summarized in Figures 6 and
7. This graphic illustrates two out of the three contextual sources of
information employed by the apprentice. Each source is encoded separately, the
relevance of its constituent elements represented as a probability
distribution and resulting distributions combined to guide the decoder in
generating output.

One step of the decoder could add zero, one, or more words, i.e., a phrase, to
the current utterance under construction. Memories — both short- and long-term
— are in the form of thought vectors or word sequences that could be used to
reconstruct the original thought vectors for embedding or constructing
composites by adding context or conditioning to emphasize relevant dimensions.
The dialogue manager — a $Q$-function network trained by reinforcement
learning — can also choose not to respond at all or could respond at some
length perhaps incorporating references to code, explanations for design
choices and demonstrations showing the results of executing code in the IDE.

To control generation, we adapt the pointer-generator network framework
developed by See et al for document summarization [85]. In the standard
sequence-to-sequence machine-translation model a weighted average of encoder
states becomes the decoder state and attention is just the distribution of
weights. In See et al attention is simpler: instead of weighting input
elements, it points at them probabilistically. It isn’t necessary to use all
the pointers; such networks can mark excerpts by pointing to their start and
end constituents. We apply their approach here to digest and integrate
contextual information originating from multiple sources.

In humans, memory formation and consolidation involves several systems,
multiple stages and can span hours, weeks or months depending on the stage and
associated neural circuitry. Our primary interest relates to the earliest
stages of memory formation and role of the hippocampus and entorhinal region
of the frontal cortex along with several ancillary subcortical circuits
including the basal ganglia (BG). Influenced by the work of O’Reilly and Frank
[70], we focus on the function of the dentate gyrus (DG) in the hippocampal
formation and encode thought vectors using a sparse, invertible mapping
thereby providing a high degree of pattern separation in encoding new
information while avoiding interference with existing memories.

We finesse the details of what gets stored and when by simply storing
everything. We could store the sparse representation provided by the DG, but
prefer to use this probe as the key in a key-value pair in the NTM partition
dedicated to episodic memory and store the raw data as the value. This means
we have to reconstruct the original encoding produced when initially ingesting
the text of an utterance. This is preferable for two reasons: (i) we need the
words — or tokens of an abstract syntax tree in the case of ingesting code
fragments — in order for the decoder to generate the apprentice’s response,
and (ii) the embeddings of the symbolic entities that constitute their meaning
are likely to drift during ongoing training.

##  Appendix B Bootstrapped Linguistic Competence

In this appendix, we consider how we might design an end-to-end training
protocol for bootstrapping a variant of the programmer’s apprentice
application. We begin with the analogous stages in early child development.
Each of the following four stages is briefly introduced with additional
technical details provided in the accompanying footnotes:

  * •

Basic cognitive bootstrapping and linguistic grounding11endnote:
1Bootstrapping the programmer’s apprentice: Basic cognitive bootstrapping and
linguistic grounding:
The programmer’s assistant agent is designed to distinguish between three
voices: the voice of the programmer, the voice of the assistant’s automated
tutor and its own voice. We could have provided an audio track to distinguish
these voices, but since there only these three and the overall system can
determine when any one of them is speaking, the system simply adds a few bits
to each utterance as a proxy for an audio signature allowing the assistant to
make such distinctions for itself. When required, we use the same signature to
indicate which of the three speakers is responsible for changes to the shared
input and output associated with the fully instrumented IDE henceforth
abbreviated as FIDE — pronounced ”/fee/’-/day/”, from the Latin meaning: (i)
trust, (ii) credit, (iii) fidelity, (iv) honesty. It will also prove useful to
further distinguish the voice of the assistant as being in one of two modes:
private, engaging in so-called inner speech that is not voiced aloud, and
public, meaning spoken out loud for the explicit purpose of communicating with
the programmer. We borrow the basic framework for modeling other agents and
simple theory-of-mind from Rabinowitz et al [80]. The bootstrap statistical
language model consists of an $n$-gram embedding trained on large general-text
language corpus augmented with programming and software-engineering related
text drawn from online forums and transcripts of pair-programming dialog. For
the time being, we will not pursue the option of trying to acquire a large
enough dialog corpus to train an encoder-decoder LSTM/GRU dialog manager /
conversational model [98]. In the initial prototype, natural language
generation (NLG) output for the automated tutor and assistant will be handled
using hierarchical planning technology leveraging ideas developed in the CMU
RavenClaw dialogue management system [15], but we have plans to explore hybrid
natural language generation by combining hard-coded Python dialog agents
corresponding to hierarchical task networks and differentiable dialogic
encoder-decoder thought-cloud generators using a variant of pointer-generator
networks as described by See et al [85]. Both the tutor and assistant NLG
subsystems will rely on a base-level collection of plans — hierarchical task
network (HTN) — that we employ in several contexts plus a set of specialized
plans — an HTN subnetwork — specific to each subsystem. At any given moment in
time, a meta control system [47] in concert with a reinforcement-learning-
trained policy determines the curricular goal constraining the tutor’s choice
of specific lesson is implemented using a variant of the scheduled auxiliary
control paradigm described by Riedmiller et al [83]. Having selected a subset
of lessons relevant to the current curricular goal, the meta-controller cedes
control to the tutor which selects a specific lesson and a suitable plan to
oversee interaction with the agent over the course of the lesson. Most lessons
will require a combination of spoken dialogue and interactive signaling that
may include both the agent and the tutor pointing, highlighting, performing
edits and controlling the FIDE by executing code and using developer tools
like the debugger to change state, set break points and single step the
interpreter, but we’re getting ahead of ourselves. The curriculum for
mastering the basic referential modes is divided into three levels of mastery
in keeping with Terrence Deacon’s description [24] and Charles Sanders
Peirce’s (semiotic) theory of signs. The tutor will start at the most basic
level, continually evaluating performance to determine when it is time to
graduate to the next level or when it is appropriate to revert to an earlier
level to provide additional training in order to master the less demanding
modes of reference.
:

    * –

modeling language: statistical $n$-gram language model trained on programming
corpus;

    * –

hierarchical planning: automated tutor generates lessons using curriculum
training;

  * •

Simple interactive behavior for signaling and editing22endnote: 2Bootstrapping
the programmer’s apprentice: Simple interactive behavior for signaling and
editing:
In the first stage of bootstrapping, the assistant’s automated tutor engages
in an analog of the sort of simple signaling and reinforcement that a mother
might engage in with her baby in order to encourage the infant to begin taking
notice of its environment and participating in the simplest forms of
communication. The basic exchange goes something like: the mother draws the
baby’s attention to something and the baby acknowledges by making some sound
or movement. This early step requires that the baby can direct its gaze and
attend to changes in its visual field. In the case of the assistant, the
relevant changes would correspond to changes in FIDE or the shared browser
window, pointing would be accomplished by altering the contents of FIDE
buffers or modifying HTML. Since the assistant has an innate capability to
parse language into sequences of words, the tutor can preface each lesson with
short verbal lesson summary, e.g., ”the variable ’foo’”, ”the underlined
variable”, ”the highlighted assignment statement”, ”the expression highlighted
in blue”. The implicit curriculum followed by the tutor would systematically
graduate to more complicated language for specifying referents, e.g., ”the
body of the ’for’ loop”, ”the ’else’ clause in the ’conditional statement”,
”the scope of the variable ’counter’”, ”the expression on the right-hand side
of the first assignment statement”. The goal of the bootstrap tutor is to
eventually graduate to simple substitution and repair activities requiring a
combination of basic attention, signaling, requesting feedback and simple
edits, e.g., ”highlight the scope of the variable shown in red”, ”change the
name of the function to be ”Increment_Counter”, ”insert a ”for” loop with an
iterator over the items in the ”bucket” list”, ”delete the next two
expressions”, with the length and complexity of the specification gradually
increasing until the apprentice is capable of handling code changes that
involve multiple goals and dozens of intermediate steps, e.g., ”delete the
variable ”Interrupt_Flag” from the parameter list of the function declaration
and eliminate all of the expressions that refer to the variable within the
scope of the function definition”. Note the importance of an attentional
system that can notice changes in the integrated development environment and
shared browser window, the ability to use recency to help resolve ambiguities,
and emphasize basic signals that require noticing changes in the IDE and
acknowledging that these changes were made as a means of signaling
expectations relevant to the ongoing conversation between the programmer and
the apprentice. These are certainly subtleties that will have to be introduced
gradually into the curricular repertoire as the apprentice gains experience.
We are depending on employing a variant of Riedmiller et al that will enable
us to employ the FIDE to gamify the process by evaluating progress at
different levels using a combination of general extrinsic reward and policy-
specific intrinsic motivations to guide action selection [83]. Randall
O’Reilly mentioned in his class presentation the idea that natural language
might play an important role in human brains as an intra-cortical lingua
franca. Given that one of the primary roles language serves is to serialize
thought thereby facilitating serial computation with all of its advantages in
terms of logical precision and combinatorial expression, projecting a
distributed connectionist representation through some sort of auto encoder
bottleneck might gain some advantage in combining aspects of symbolic and
connectionist architectures. This also relates to O’Reilly’s discussion of the
hippocampal system and in particular the processing performed by the dentate
gyrus and hippocampal areas CA1 in CA2 in generating a sparse representation
that enables rapid binding of arbitrary informational states and facilitates
encoding and retrieving of episodic memory in the entorhinal cortex.
:

    * –

following instruction: learning to carry out simple plans one instruction at a
time;

    * –

explaining behavior: providing short explanations of behavior, acknowledging
failure;

  * •

Mixed dialogue interleaving instruction and mirroring33endnote: 3Bootstrapping
the programmer’s apprentice: Mixed dialogue interleaving instruction and
mirroring:
Every utterance, whether generated by the programmer or the apprentice’s tutor
or generated by the apprentice either intended for the programmer or sotto
voce for its internal record, has potential future value and hence it makes
sense to record that utterance along with any context that might help to
realize that potential at a later point in time. Endel Tulving coined the
phrase episodic memory to refer to this sort of memory. We’ll forgo discussion
of other types of memory for the time being and focus on what the apprentice
will need to remember in order take advantage of its past experience. Here is
the simplest, stripped-to-its-most-basic-elements scenario outlined in the
class notes: (a) the apprentice performs a sequence of steps that effect a
repair on a code fragment, (b) this experience is recorded in a sequence of
tuples of the form $(s_{t},a_{t},r_{t},s_{t+1})$ and consolidated in episodic
memory, (c) at a subsequent time, days or weeks later, the apprentice
recognizes a similar situation and realizes an opportunity to exercise what
was learned in the earlier episode, and (d) a suitably adapted repair is
applied in the present circumstances and incorporated into a more general
policy so that it can be applied in wider range circumstances. The succinct
notation doesn’t reveal any hint of the complexity and subtlety of the
question. What were the (prior) circumstances — $s_{t}$? What was thought,
said and done to plan, prepare and take action — $a_{t}$? What were the
(posterior) consequences — $r_{t}$ and $s_{t+1}$? We can’t simply record the
entire neural state vector. We could, however, plausibly record the
information temporarily stored in working memory since this is the only
information that could have played any substantive role — for better or worse
— in guiding executive function. We can’t store everything and then carefully
pick through the pile looking for what might have made a difference, but we
can do something almost as useful. We can propagate the reward gradient back
through the value- / $Q$-function and then further back through the activated
circuits in working memory that were used to select $a_{i}$ and adjust their
weights accordingly. The objective in this case being to optimize the
$Q$-function by predicting the state variables that it needs in order to make
an accurate prediction of the value of applying action $a_{t}$ in $s_{t}$ as
described in Wayne et al [102]. Often the problem can be described as a simple
Markov process and the state represented as a vector comprising of a finite
number of state variables,
$s_{t}=\langle{}\sigma{}_{0},\sigma{}_{1},\sigma{}_{2},\sigma{}_{3},\sigma{}_{4},\sigma{}_{5},\sigma{}_{6},\sigma{}_{7},\rangle{}$,
with the implicit assumption that the process is fully observable. More
generally, the Markov property still holds, but the state is only partially
observable resulting in a much harder class of decision problem known as a
POMDP. In some cases, we can finesse the complexity if we can ensure that we
can observe the relevant state variables in any given state, e.g., in one set
of states it is enough to know one subset of the state variables,
$\langle{}\sigma{}_{0},\color[rgb]{1,0,0}\sigma{}_{1}\color[rgb]{0,0,0},\sigma{}_{2},\color[rgb]{1,0,0}\sigma{}_{3}\color[rgb]{0,0,0},\sigma{}_{4},\sigma{}_{5},\sigma{}_{6},\color[rgb]{1,0,0}\sigma{}_{7}\color[rgb]{0,0,0}\rangle{}$,
while in another set of states a different subset of state variables suffices,
$\langle{}\sigma{}_{0},\sigma{}_{1},\sigma{}_{2},\sigma{}_{3},\color[rgb]{1,0,0}\sigma{}_{4}\color[rgb]{0,0,0},\sigma{}_{5},\color[rgb]{1,0,0}\sigma{}_{6}\color[rgb]{0,0,0},\sigma{}_{7}\rangle{}$.
If you can learn which state variables are required and arrange to observe
them, the problem reduces to the fully observed case. There’s a catch however.
The state vector includes state variables that correspond to the observations
of external processes that we have little or no direct control over as well as
the apprehension of internal processes including the activation of
subnetworks. We may need to plan for and carry out the requisite observations
to acquire the external process state and perform the requisite computations
to produce and then access the resulting internal state information. We also
have the ability to perform two fundamentally different types of computation
each of which has different strengths and weaknesses that conveniently
complement the other. The mammalian brain is optimized to efficiently perform
many computations in parallel; however, for the most part it is not
particularly effective dealing with the inconsistencies that arise among those
largely independent computations. Rather than relying on estimating and
conditioning action selection on internally maintained state variables, most
animals rely on environmental cues — callsed affordances [38] — to restrict
the space of possible options and simplify action selection. However, complex
skills like programming require complex serial computations in order to
reconcile and make sense of the contradictory suggestions originating from our
mostly parallel computational substrate. Conventional reinforcement learning
may work for some types of routine programming like writing simple text-
processing scripts, but it is not likely to suffice for programs that involve
more complex logical, mathematical and algorithmic thinking. The programmer’s
apprentice project is intended as a playground in which to explore ideas
derived from biological systems that might help us chip away at these more
difficult problems. For example, the primate brain compensates for the
limitations of its largely parallel processing approach to solving problems by
using specialized networks in the frontal cortex, thalamus, striatum, and
basal ganglia to serialize the computations necessary to perform complex
thinking. At the very least, it seems reasonable to suggest that we need
cognitive machinery that is at least as powerful as the programs we aspire the
apprentice to generate [36]. We need the neural equivalent of the CONTROL UNIT
responsible for maintaining a PROGRAM COUNTER and the analog of loading
instructions and operands into REGISTERS in the ARITHMETIC AND LOGIC UNIT and
subsequently writing the resulting computed products into other registers or
RANDOM ACCESS MEMORY. These particular features of the von Neumann
architecture are not essential — what is required is a lingistic foundation
that supports a complete story of computation and that is grounded in the
detailed — almost visceral — experience of carrying out computations. A single
$Q$ (value) function encoding a single action-selection policy with fixed
finite-discrete or continuous state and action spaces isn’t likely to suffice.
Supporting compiled subroutines doesn’t significantly change the picture. The
addition of a meta controller for orchestrating a finite collection of
separate, special-purpose policies adds complexity without appreciably adding
competence. And simply adding language for describing procedures, composing
production rules, and compiling subroutines as a Sapir-Whorf-induced infusion
of ontological enhancement is — by itself — only a distraction. We need an
approach that exploits a deeper understanding of the role of language in the
modern age — a method of using a subset of natural language to describe
programs in terms of narratives where executing such a program is tantamount
to telling the story. Think about how human cognitive systems encode and
serialize remembered stories, about programs as stories drawing on life
experience by exploiting the serial nature of episodic memory, and about
thought clouds that represent a superposition of eigenstates such that
collapsing the wave function yields coherent narrative that serves as a
program trace.
:

    * –

classifying intention: learning to categorize tasks and summarize intentions
to act;

    * –

confirming comprehension: conveying practical understanding of specific
instructions;

  * •

Composite behaviors corresponding to simple repairs44endnote: 4Bootstrapping
the programmer’s apprentice: Composite behaviors corresponding to simple
repairs:
A software design pattern ”is a general, reusable solution to a commonly
occurring problem within a given context in software design. It is not a
finished design that can be transformed directly into source or machine code.
It is a description or template for how to solve a problem that can be used in
many different situations. Design patterns are formalized best practices that
the programmer can use to solve common problems when designing an application
or system”. They are typically characterized as belonging to one of three
categories: creational, structural, or behavioral. We would like to believe
that such patterns provide clear prescriptions for how to tackle challenging
programming problems, but know better. Studying such patterns and analyzing
examples of their application to practical problems is an excellent exercise
for both computer science students learning to program, and practicing
software engineers wanting to improve their skills. That said, these design
patterns require considerable effort to master and are well beyond what one
might hope to accomplish in bootstrapping basic linguistic and programming
skills. Indeed, mastery depends on already knowing — at the very least — the
rudiments of these skills. We are willing to concede that mental software is
not always expressed in language. For the programmer’s apprentice, we are
thinking of encoding what is essentially static and syntactic knowledge about
programs and programming using four different representations, and what is
essentially dynamic and semantic knowledge in a family of structured
representations that encode program execution traces of one sort or another.
The four static / syntactic representations are summarized as follows:  – (i)
distributed (connectionist) representations of natural language as points in
high-dimensional embedding spaces — thought clouds; – (ii) natural language
transcripts of dialogical utterances / interlocutionary acts encoded as
lexical token streams — word sequences; – (iii) programs in the target
programming language represented as structured objects corresponding to
augmented abstract syntax trees (ASTs)— the augmentations correspond to edges
representing procedure calls, iteration and recursion resulting in directed
acyclic graphs; – (iv) hierarchical plans corresponding to subnetworks of
hierarchical task networks (HTNs) or, if you like, the implied representation
of hierarchical plans encoded in value iteration networks [93] and goal-based
policies [43]. We’re also thinking about encoding HTNs as policies using a
variation on the idea of options [92] as described in Riedmiller et al [83];
The first entry (i) is somewhat misleading in that any one of the remaining
three (ii-iv) can be represented as a point / thought cloud using an
appropriate embedding method. Thought clouds are the Swiss Army knife of
distributed codes. They represent a (constrained) superposition of
possibilities allowing us to convert large corpora of serialized structures
into point clouds that enable massively parallel search, and subsequently
allow us to collapse the wave function, as it were, to read off solutions by
re-serializing the distributed encoding of constraints that result from
conducting such parallel searches. We propose to develop encoders and decoders
to translate between (serial) representations (ii-iv) where only a subset of
conversions are possible or desirable given the expressivity of the underlying
representation language. We imagine autoencoders with an information
bottleneck that take embeddings of natural language descriptions as input and
produces an equivalent HTN representation, combining a mixture of (executable)
interlocutory and code synthesis tasks [2, 95]. The interlocutory tasks
generate explanations and produce comments and specifications. The code-
synthesis tasks serve to generate, repair, debug and test code represented in
the FIDE. Separately encoded embeddings will tend to evolve independently,
frustrating attempts to combine them into composite representations that allow
powerful means of abstraction. The hope is that we can use natural language as
a lingua franca — a ”bridge” language — to coerce agreement among disparate
representations by forcing them to cohere along shared, possibly refactored
dimensions in much the same way that trade languages serve as an expeditious
means of exchanging information between scientists and engineers working in
different disciplines or scholars who do not share a native language or
dialect.
:

    * –

executing complex plans: generating and executing multi-step plans with
contingencies;

    * –

recovering from failure: backtracking, recovering, retracting steps on failed
branches;

###### Footnotes

  1. 1 Bootstrapping the programmer’s apprentice: Basic cognitive bootstrapping and linguistic grounding: The programmer’s assistant agent is designed to distinguish between three voices: the voice of the programmer, the voice of the assistant’s automated tutor and its own voice. We could have provided an audio track to distinguish these voices, but since there only these three and the overall system can determine when any one of them is speaking, the system simply adds a few bits to each utterance as a proxy for an audio signature allowing the assistant to make such distinctions for itself. When required, we use the same signature to indicate which of the three speakers is responsible for changes to the shared input and output associated with the fully instrumented IDE henceforth abbreviated as FIDE — pronounced ”/fee/’-/day/”, from the Latin meaning: (i) trust, (ii) credit, (iii) fidelity, (iv) honesty. It will also prove useful to further distinguish the voice of the assistant as being in one of two modes: private, engaging in so-called inner speech that is not voiced aloud, and public, meaning spoken out loud for the explicit purpose of communicating with the programmer. We borrow the basic framework for modeling other agents and simple theory-of-mind from Rabinowitz et al [80]. The bootstrap statistical language model consists of an $n$-gram embedding trained on large general-text language corpus augmented with programming and software-engineering related text drawn from online forums and transcripts of pair-programming dialog. For the time being, we will not pursue the option of trying to acquire a large enough dialog corpus to train an encoder-decoder LSTM/GRU dialog manager / conversational model [98]. In the initial prototype, natural language generation (NLG) output for the automated tutor and assistant will be handled using hierarchical planning technology leveraging ideas developed in the CMU RavenClaw dialogue management system [15], but we have plans to explore hybrid natural language generation by combining hard-coded Python dialog agents corresponding to hierarchical task networks and differentiable dialogic encoder-decoder thought-cloud generators using a variant of pointer-generator networks as described by See et al [85]. Both the tutor and assistant NLG subsystems will rely on a base-level collection of plans — hierarchical task network (HTN) — that we employ in several contexts plus a set of specialized plans — an HTN subnetwork — specific to each subsystem. At any given moment in time, a meta control system [47] in concert with a reinforcement-learning-trained policy determines the curricular goal constraining the tutor’s choice of specific lesson is implemented using a variant of the scheduled auxiliary control paradigm described by Riedmiller et al [83]. Having selected a subset of lessons relevant to the current curricular goal, the meta-controller cedes control to the tutor which selects a specific lesson and a suitable plan to oversee interaction with the agent over the course of the lesson. Most lessons will require a combination of spoken dialogue and interactive signaling that may include both the agent and the tutor pointing, highlighting, performing edits and controlling the FIDE by executing code and using developer tools like the debugger to change state, set break points and single step the interpreter, but we’re getting ahead of ourselves. The curriculum for mastering the basic referential modes is divided into three levels of mastery in keeping with Terrence Deacon’s description [24] and Charles Sanders Peirce’s (semiotic) theory of signs. The tutor will start at the most basic level, continually evaluating performance to determine when it is time to graduate to the next level or when it is appropriate to revert to an earlier level to provide additional training in order to master the less demanding modes of reference.
  2. 2 Bootstrapping the programmer’s apprentice: Simple interactive behavior for signaling and editing: In the first stage of bootstrapping, the assistant’s automated tutor engages in an analog of the sort of simple signaling and reinforcement that a mother might engage in with her baby in order to encourage the infant to begin taking notice of its environment and participating in the simplest forms of communication. The basic exchange goes something like: the mother draws the baby’s attention to something and the baby acknowledges by making some sound or movement. This early step requires that the baby can direct its gaze and attend to changes in its visual field. In the case of the assistant, the relevant changes would correspond to changes in FIDE or the shared browser window, pointing would be accomplished by altering the contents of FIDE buffers or modifying HTML. Since the assistant has an innate capability to parse language into sequences of words, the tutor can preface each lesson with short verbal lesson summary, e.g., ”the variable ’foo’”, ”the underlined variable”, ”the highlighted assignment statement”, ”the expression highlighted in blue”. The implicit curriculum followed by the tutor would systematically graduate to more complicated language for specifying referents, e.g., ”the body of the ’for’ loop”, ”the ’else’ clause in the ’conditional statement”, ”the scope of the variable ’counter’”, ”the expression on the right-hand side of the first assignment statement”. The goal of the bootstrap tutor is to eventually graduate to simple substitution and repair activities requiring a combination of basic attention, signaling, requesting feedback and simple edits, e.g., ”highlight the scope of the variable shown in red”, ”change the name of the function to be ”Increment_Counter”, ”insert a ”for” loop with an iterator over the items in the ”bucket” list”, ”delete the next two expressions”, with the length and complexity of the specification gradually increasing until the apprentice is capable of handling code changes that involve multiple goals and dozens of intermediate steps, e.g., ”delete the variable ”Interrupt_Flag” from the parameter list of the function declaration and eliminate all of the expressions that refer to the variable within the scope of the function definition”. Note the importance of an attentional system that can notice changes in the integrated development environment and shared browser window, the ability to use recency to help resolve ambiguities, and emphasize basic signals that require noticing changes in the IDE and acknowledging that these changes were made as a means of signaling expectations relevant to the ongoing conversation between the programmer and the apprentice. These are certainly subtleties that will have to be introduced gradually into the curricular repertoire as the apprentice gains experience. We are depending on employing a variant of Riedmiller et al that will enable us to employ the FIDE to gamify the process by evaluating progress at different levels using a combination of general extrinsic reward and policy-specific intrinsic motivations to guide action selection [83]. Randall O’Reilly mentioned in his class presentation the idea that natural language might play an important role in human brains as an intra-cortical lingua franca. Given that one of the primary roles language serves is to serialize thought thereby facilitating serial computation with all of its advantages in terms of logical precision and combinatorial expression, projecting a distributed connectionist representation through some sort of auto encoder bottleneck might gain some advantage in combining aspects of symbolic and connectionist architectures. This also relates to O’Reilly’s discussion of the hippocampal system and in particular the processing performed by the dentate gyrus and hippocampal areas CA1 in CA2 in generating a sparse representation that enables rapid binding of arbitrary informational states and facilitates encoding and retrieving of episodic memory in the entorhinal cortex.
  3. 3 Bootstrapping the programmer’s apprentice: Mixed dialogue interleaving instruction and mirroring: Every utterance, whether generated by the programmer or the apprentice’s tutor or generated by the apprentice either intended for the programmer or sotto voce for its internal record, has potential future value and hence it makes sense to record that utterance along with any context that might help to realize that potential at a later point in time. Endel Tulving coined the phrase episodic memory to refer to this sort of memory. We’ll forgo discussion of other types of memory for the time being and focus on what the apprentice will need to remember in order take advantage of its past experience. Here is the simplest, stripped-to-its-most-basic-elements scenario outlined in the class notes: (a) the apprentice performs a sequence of steps that effect a repair on a code fragment, (b) this experience is recorded in a sequence of tuples of the form $(s_{t},a_{t},r_{t},s_{t+1})$ and consolidated in episodic memory, (c) at a subsequent time, days or weeks later, the apprentice recognizes a similar situation and realizes an opportunity to exercise what was learned in the earlier episode, and (d) a suitably adapted repair is applied in the present circumstances and incorporated into a more general policy so that it can be applied in wider range circumstances. The succinct notation doesn’t reveal any hint of the complexity and subtlety of the question. What were the (prior) circumstances — $s_{t}$? What was thought, said and done to plan, prepare and take action — $a_{t}$? What were the (posterior) consequences — $r_{t}$ and $s_{t+1}$? We can’t simply record the entire neural state vector. We could, however, plausibly record the information temporarily stored in working memory since this is the only information that could have played any substantive role — for better or worse — in guiding executive function. We can’t store everything and then carefully pick through the pile looking for what might have made a difference, but we can do something almost as useful. We can propagate the reward gradient back through the value- / $Q$-function and then further back through the activated circuits in working memory that were used to select $a_{i}$ and adjust their weights accordingly. The objective in this case being to optimize the $Q$-function by predicting the state variables that it needs in order to make an accurate prediction of the value of applying action $a_{t}$ in $s_{t}$ as described in Wayne et al [102]. Often the problem can be described as a simple Markov process and the state represented as a vector comprising of a finite number of state variables, $s_{t}=\langle{}\sigma{}_{0},\sigma{}_{1},\sigma{}_{2},\sigma{}_{3},\sigma{}_{4},\sigma{}_{5},\sigma{}_{6},\sigma{}_{7},\rangle{}$, with the implicit assumption that the process is fully observable. More generally, the Markov property still holds, but the state is only partially observable resulting in a much harder class of decision problem known as a POMDP. In some cases, we can finesse the complexity if we can ensure that we can observe the relevant state variables in any given state, e.g., in one set of states it is enough to know one subset of the state variables, $\langle{}\sigma{}_{0},\color[rgb]{1,0,0}\sigma{}_{1}\color[rgb]{0,0,0},\sigma{}_{2},\color[rgb]{1,0,0}\sigma{}_{3}\color[rgb]{0,0,0},\sigma{}_{4},\sigma{}_{5},\sigma{}_{6},\color[rgb]{1,0,0}\sigma{}_{7}\color[rgb]{0,0,0}\rangle{}$, while in another set of states a different subset of state variables suffices, $\langle{}\sigma{}_{0},\sigma{}_{1},\sigma{}_{2},\sigma{}_{3},\color[rgb]{1,0,0}\sigma{}_{4}\color[rgb]{0,0,0},\sigma{}_{5},\color[rgb]{1,0,0}\sigma{}_{6}\color[rgb]{0,0,0},\sigma{}_{7}\rangle{}$. If you can learn which state variables are required and arrange to observe them, the problem reduces to the fully observed case. There’s a catch however. The state vector includes state variables that correspond to the observations of external processes that we have little or no direct control over as well as the apprehension of internal processes including the activation of subnetworks. We may need to plan for and carry out the requisite observations to acquire the external process state and perform the requisite computations to produce and then access the resulting internal state information. We also have the ability to perform two fundamentally different types of computation each of which has different strengths and weaknesses that conveniently complement the other. The mammalian brain is optimized to efficiently perform many computations in parallel; however, for the most part it is not particularly effective dealing with the inconsistencies that arise among those largely independent computations. Rather than relying on estimating and conditioning action selection on internally maintained state variables, most animals rely on environmental cues — callsed affordances [38] — to restrict the space of possible options and simplify action selection. However, complex skills like programming require complex serial computations in order to reconcile and make sense of the contradictory suggestions originating from our mostly parallel computational substrate. Conventional reinforcement learning may work for some types of routine programming like writing simple text-processing scripts, but it is not likely to suffice for programs that involve more complex logical, mathematical and algorithmic thinking. The programmer’s apprentice project is intended as a playground in which to explore ideas derived from biological systems that might help us chip away at these more difficult problems. For example, the primate brain compensates for the limitations of its largely parallel processing approach to solving problems by using specialized networks in the frontal cortex, thalamus, striatum, and basal ganglia to serialize the computations necessary to perform complex thinking. At the very least, it seems reasonable to suggest that we need cognitive machinery that is at least as powerful as the programs we aspire the apprentice to generate [36]. We need the neural equivalent of the CONTROL UNIT responsible for maintaining a PROGRAM COUNTER and the analog of loading instructions and operands into REGISTERS in the ARITHMETIC AND LOGIC UNIT and subsequently writing the resulting computed products into other registers or RANDOM ACCESS MEMORY. These particular features of the von Neumann architecture are not essential — what is required is a lingistic foundation that supports a complete story of computation and that is grounded in the detailed — almost visceral — experience of carrying out computations. A single $Q$ (value) function encoding a single action-selection policy with fixed finite-discrete or continuous state and action spaces isn’t likely to suffice. Supporting compiled subroutines doesn’t significantly change the picture. The addition of a meta controller for orchestrating a finite collection of separate, special-purpose policies adds complexity without appreciably adding competence. And simply adding language for describing procedures, composing production rules, and compiling subroutines as a Sapir-Whorf-induced infusion of ontological enhancement is — by itself — only a distraction. We need an approach that exploits a deeper understanding of the role of language in the modern age — a method of using a subset of natural language to describe programs in terms of narratives where executing such a program is tantamount to telling the story. Think about how human cognitive systems encode and serialize remembered stories, about programs as stories drawing on life experience by exploiting the serial nature of episodic memory, and about thought clouds that represent a superposition of eigenstates such that collapsing the wave function yields coherent narrative that serves as a program trace.
  4. 4 Bootstrapping the programmer’s apprentice: Composite behaviors corresponding to simple repairs: A software design pattern ”is a general, reusable solution to a commonly occurring problem within a given context in software design. It is not a finished design that can be transformed directly into source or machine code. It is a description or template for how to solve a problem that can be used in many different situations. Design patterns are formalized best practices that the programmer can use to solve common problems when designing an application or system”. They are typically characterized as belonging to one of three categories: creational, structural, or behavioral. We would like to believe that such patterns provide clear prescriptions for how to tackle challenging programming problems, but know better. Studying such patterns and analyzing examples of their application to practical problems is an excellent exercise for both computer science students learning to program, and practicing software engineers wanting to improve their skills. That said, these design patterns require considerable effort to master and are well beyond what one might hope to accomplish in bootstrapping basic linguistic and programming skills. Indeed, mastery depends on already knowing — at the very least — the rudiments of these skills. We are willing to concede that mental software is not always expressed in language. For the programmer’s apprentice, we are thinking of encoding what is essentially static and syntactic knowledge about programs and programming using four different representations, and what is essentially dynamic and semantic knowledge in a family of structured representations that encode program execution traces of one sort or another. The four static / syntactic representations are summarized as follows:  – (i) distributed (connectionist) representations of natural language as points in high-dimensional embedding spaces — thought clouds; – (ii) natural language transcripts of dialogical utterances / interlocutionary acts encoded as lexical token streams — word sequences; – (iii) programs in the target programming language represented as structured objects corresponding to augmented abstract syntax trees (ASTs)— the augmentations correspond to edges representing procedure calls, iteration and recursion resulting in directed acyclic graphs; – (iv) hierarchical plans corresponding to subnetworks of hierarchical task networks (HTNs) or, if you like, the implied representation of hierarchical plans encoded in value iteration networks [93] and goal-based policies [43]. We’re also thinking about encoding HTNs as policies using a variation on the idea of options [92] as described in Riedmiller et al [83]; The first entry (i) is somewhat misleading in that any one of the remaining three (ii-iv) can be represented as a point / thought cloud using an appropriate embedding method. Thought clouds are the Swiss Army knife of distributed codes. They represent a (constrained) superposition of possibilities allowing us to convert large corpora of serialized structures into point clouds that enable massively parallel search, and subsequently allow us to collapse the wave function, as it were, to read off solutions by re-serializing the distributed encoding of constraints that result from conducting such parallel searches. We propose to develop encoders and decoders to translate between (serial) representations (ii-iv) where only a subset of conversions are possible or desirable given the expressivity of the underlying representation language. We imagine autoencoders with an information bottleneck that take embeddings of natural language descriptions as input and produces an equivalent HTN representation, combining a mixture of (executable) interlocutory and code synthesis tasks [2, 95]. The interlocutory tasks generate explanations and produce comments and specifications. The code-synthesis tasks serve to generate, repair, debug and test code represented in the FIDE. Separately encoded embeddings will tend to evolve independently, frustrating attempts to combine them into composite representations that allow powerful means of abstraction. The hope is that we can use natural language as a lingua franca — a ”bridge” language — to coerce agreement among disparate representations by forcing them to cohere along shared, possibly refactored dimensions in much the same way that trade languages serve as an expeditious means of exchanging information between scientists and engineers working in different disciplines or scholars who do not share a native language or dialect.