
\section{Introduction}\label{sec:intro}
\looseness-1The emergence of block-based visual programming platforms has made coding more accessible and appealing to beginners. Block-based programming uses ``code blocks'' that reduce the burden of syntax and introduces concepts in an  interactive way. Led by initiatives like \emph{Hour of Code} by Code.org~\cite{hourofcode,codeorg} and the popularity of languages like \emph{Scratch}~\cite{DBLP:journals/cacm/ResnickMMREBMRSSK09}, block-based programming has become integral to introductory CS education. Considering the \emph{Hour of Code} initiative alone, over one billion hours of programming activity has been spent in learning to solve tasks in such environments~\cite{codeorg}.

Programming tasks on these platforms are conceptual and open-ended, and require multi-step deductive reasoning to solve. Given these aspects, novices often struggle when learning to solve these tasks. The difficulties faced by novice students become evident by looking at the trajectory of students' attempts who are struggling to solve a given task. For instance, in a dataset released by Code.org~\cite{hourofcode,codeorg,DBLP:conf/lats/PiechSHG15}, even for simple tasks where solutions require only $5$ code blocks (see Figure~\ref{fig:overview.hoc18.reftask}), students submitted over $50,000$ unique attempts with some exceeding a size of $50$ code blocks. 

\looseness-1AI-drive programming tutors have the potential to support these struggling students by providing personalized assistance, e.g., feedback as hints or curriculum design~\cite{price2017position}. To effectively assist struggling students, AI-driven systems need several components, a crucial one being \emph{student modelling}. In particular, we need models that have the ability to automatically infer a student's knowledge from
limited interactions and then predict the student's behavior
on new tasks. However, student modeling in block-based visual programming environments can be quite challenging because of the following: (i) programming tasks are conceptual, and there is no well-defined skill-set or problem-solving strategy for mastery~\cite{kaser2020modeling}; (ii) there could be a huge variability in behaviors and a long-tail distribution of students' attempts for a task~\cite{DBLP:conf/aaai/WuMGP19}; (iii) the objective of predicting a student's behavior on new tasks is not limited to coarse-grained success/failure indicators (e.g., \cite{Wang2017LearningTR})---ideally, we should be able to do fine-grained synthesis of attempts for a given student.

\looseness-1Beyond the above-mentioned challenges, there are two critical issues arising from limited resources and data scarcity for a given domain. First, while the space of tasks that could be designed for personalized curriculum is intractably large~\cite{DBLP:conf/nips/AhmedCEFGRS20}, the publicly available datasets of real-world students' attempts are typically limited; e.g., for the \emph{Hour of Code: Maze Challenge} domain, we have datasets for only two tasks~\cite{DBLP:conf/lats/PiechSHG15}. Second, when a deployed system is interacting with a new student, there is limited prior information~\cite{DBLP:conf/edm/EfremovGS20}, and the system would have to infer the student's knowledge by observing behavior on a few reference tasks, e.g., through a quiz~\cite{DBLP:conf/edm/He-YueyaS21}. These two issues, in turn, limit the applicability of state-of-the-art techniques that rely on large-scale datasets across tasks or personalized data per student (e.g., \cite{Wang2017LearningTR,DBLP:conf/kdd/McIlroy-Young0K20,McIlroyYoung2021DetectingID,PortnoffMethodsFL})---we need next-generation student modelling techniques for block-based visual programming that can operate under data scarcity and limited observability. To this end, this paper focuses on the following question:
\begin{quote}
\emph{For a given student, can we synthesize the student's attempt on a new target task after observing the student's attempt on a fixed reference task?}
\end{quote}


\vspace{-1mm}
\looseness-1\subsection{Our Approach and Contributions}\label{sec:intro.contributions}
Figures~\ref{fig:intro.hoc4}~and~\ref{fig:intro.hoc18} illustrate this synthesis question for two scenarios in the context of the \emph{Hour of Code: Maze Challenge}~\cite{hourofcode_maze} by Code.org~\cite{codeorg}. This question is akin to that of program synthesis~\cite{gulwani2017program}; however, instead of synthesizing a \emph{\{solution\}} (i.e., program an expert would write), the goal here is to synthesize a \emph{\{student attempt\}} (i.e., program that a given student would write). This goal of synthesizing student attempts, and not just solutions, requires going beyond state-of-the-art program synthesis techniques~\cite{DBLP:conf/iclr/BunelHDSK18, DBLP:conf/iclr/ChenLS19,li_competition-level}; crucially, we also need to define appropriate metrics to quantitatively measure the performance of different techniques. Our approach and contributions are summarized below:
\vspace{-4mm}
\setlength{\leftmargini}{1.5em}
\begin{enumerate}[label=(\arabic*),parsep=1pt]
\item We formalize the problem of synthesizing a student's attempt on target tasks after observing the student's behavior on a fixed reference task. We introduce a novel benchmark, \ensuremath{\textsc{StudentSyn}}, centered around the above synthesis question, along with generative/discriminative performance measures for evaluation.  (Sections~\ref{sec:problem},~\ref{sec:benchmark.data},~\ref{sec:benchmark.measures})
\item We showcase that human experts (\ensuremath{\textsc{TutorSS}}{}) can achieve high performance on \ensuremath{\textsc{StudentSyn}}, whereas  simple baselines perform poorly.  (Section~\ref{sec:benchmark.initialresults})
\item We develop two techniques inspired by neural (\ensuremath{\textsc{NeurSS}}{}) and symbolic (\ensuremath{\textsc{SymSS}}{}) methods, in a quest to close the gap with human experts (\ensuremath{\textsc{TutorSS}}{}).  (Sections~\ref{sec:continual},~\ref{sec:pcfg},~\ref{sec:experiments})
\item We will publicly release the benchmark and implementations to facilitate future research. (Section~\ref{sec:conclusions})
\end{enumerate}
\setlength{\leftmargini}{2.5em}



\subsection{Related Work}\label{sec:intro.related}
\vspace{1.3mm}
\looseness-1\textbf{Student modelling.}  Inferring the knowledge state of a student is an integral part of AI tutoring systems and relevant to our goal of predicting a student's behavior. For close-ended domains like vocabulary learning (\cite{DBLP:conf/acl/SettlesM16,PortnoffMethodsFL,DBLP:conf/nips/Hunziker0AR0PYS19}) and Algebra problems (\cite{DBLP:journals/umuai/CorbettMS00, DBLP:conf/edm/RaffertyJG16, shakya_student}), the  knowledge components or skills for mastery are typically well-defined and we can use \emph{Knowledge Tracing} techniques to model the knowledge state over time \cite{corbett1994knowledge,DBLP:conf/nips/PiechBHGSGS15}. These modelling techniques, in turn, allow us to provide feedback, predict solution strategies, or infer/quiz a student's knowledge state~\cite{DBLP:conf/edm/RaffertyJG16,DBLP:conf/edm/He-YueyaS21,shakya_student}. Open-ended domains pose unique challenges to directly apply these techniques (see~\cite{kaser2020modeling}); however, there has been some progress in this direction. In recent works \cite{DBLP:conf/kdd/McIlroy-Young0K20,McIlroyYoung2021DetectingID}, models have been proposed to predict human behavior in chess for specific skill levels and to recognize the behavior of individual players. Along these lines, \cite{DBLP:conf/edm/CockMGK21} introduced methods to perform early prediction of struggling students in open-ended interactive simulations. There have also been work on student modelling for  block-based programming domains, for instance, clustering-based methods for misconception discovery~\cite{DBLP:conf/sigcse/EmersonSRWMBL20,DBLP:conf/lak/0004SWMPP21}, and deep learning methods to represent knowledge and predict future performance~\cite{Wang2017LearningTR}.

\looseness-1\textbf{AI-driven systems for programming education.} There has been a surge of interest in developing AI-driven systems for programming education, and in particular, for block-based programming domains~\cite{price2017position,price2017isnap,weintrop2017comparing}. Existing works have studied various aspects of intelligent feedback, for instance, providing next-step hints when a student is stuck~\cite{DBLP:conf/lats/PiechSHG15,yi2017feasibility,DBLP:journals/corr/abs-1708-06564,DBLP:conf/edm/EfremovGS20}, giving data-driven feedback about a student's misconceptions~\cite{singh2013automated,DBLP:conf/icml/PiechHNPSG15,price2017evaluation,DBLP:conf/aaai/WuMGP19}, or generating/recommending new tasks~\cite{DBLP:conf/edm/AiCGZWFW19,DBLP:conf/nips/AhmedCEFGRS20,aied21_popquiz}. Depending on the availability of datasets and resources, different techniques are employed: using historical datasets to learn code embeddings \cite{DBLP:conf/icml/PiechHNPSG15,DBLP:journals/corr/abs-1708-06564}, using reinforcement learning in zero-shot setting~\cite{DBLP:conf/edm/EfremovGS20,DBLP:journals/corr/abs-2107-08828}, bootstrapping from a small set of expert annotations~\cite{DBLP:conf/icml/PiechHNPSG15}, or using expert grammars to generate synthetic training data~\cite{DBLP:conf/aaai/WuMGP19}.

\vspace{-1mm}
\looseness-1\textbf{Neuro-symbolic program synthesis.} 
Our approach is related to program synthesis, i.e., automatically constructing programs that satisfy a given specification~\cite{gulwani2017program}. In recent years, the usage of deep learning models for program synthesis has resulted in significant progress in a variety of domains including string transformations \cite{DBLP:conf/nips/EllisNPSTS19,DBLP:conf/icml/DevlinUBSMK17,DBLP:conf/iclr/ParisottoMS0ZK17}, block-based visual programming~\cite{DBLP:conf/iclr/BunelHDSK18, DBLP:conf/iclr/ChenLS19, DBLP:conf/nips/DevlinBSHK17,DBLP:journals/corr/abs-2108-13643}, and competitive programming~\cite{li_competition-level}. Program synthesis has also been used to learn compositional symbolic rules and mimic abstract human learning \cite{DBLP:conf/nips/NyeS0L20,DBLP:journals/corr/abs-2006-08381}.  Our goal is akin to program synthesis and we leverage the work of \cite{DBLP:conf/iclr/BunelHDSK18} in our technique \ensuremath{\textsc{NeurSS}}, however, with a crucial difference: instead of synthesizing a solution program, we seek to synthesize a student's attempt.

\section{Problem Setup}\label{sec:problem}
In this section, we introduce important definitions and formalize our objective.

\subsection{Preliminaries}\label{sec:problem.preliminaries}
\looseness-1\textbf{The space of tasks.} We define the space of tasks as~\ensuremath{\mathbb{T}}; in this paper, \ensuremath{\mathbb{T}}{} is inspired by the popular \emph{Hour of Code: Maze Challenge}~\cite{hourofcode_maze} from Code.org~\cite{codeorg}; see Figures~\ref{fig:overview.hoc4.reftask}~and~\ref{fig:overview.hoc18.reftask}. We define a task $\text{\textcode{T}} \in \ensuremath{\mathbb{T}}$ as a tuple $(\text{\textcode{T}}_\textnormal{vis}, \text{\textcode{T}}_\textnormal{store}, \text{\textcode{T}}_\textnormal{size})$, where $\text{\textcode{T}}_\textnormal{vis}$ denotes a visual puzzle,  $\text{\textcode{T}}_\textnormal{store}$ the available block types, and $\text{\textcode{T}}_\textnormal{size}$ the maximum number of blocks allowed in the solution code.  For instance, considering the task $\text{\textcode{T}}$ in Figure~\ref{fig:overview.hoc18.reftask}, we have the following specification: the visual puzzle $\text{\textcode{T}}_\textnormal{vis}$ comprises of a maze where the objective is to navigate the ``avatar'' (blue-colored triangle) to the ``goal'' (red-colored star) by executing a code; the set of available types of blocks $\text{\textcode{T}}_\textnormal{store}$ is \{\textcode{move}, \textcode{turnLeft}, \textcode{turnRight}, \textcode{\textsc{RepeatUntil}}{(\textcode{goal}}), \textcode{\textsc{IfElse}}{(\textcode{pathAhead}}), \textcode{\textsc{IfElse}}{(\textcode{pathLeft}}), \textcode{\textsc{IfElse}}{(\textcode{pathRight}})\}, and the size threshold $\text{\textcode{T}}_\textnormal{size}$ is $5$ blocks; this particular task in Figure~\ref{fig:overview.hoc18.reftask} corresponds to Maze\#$18$ in the \emph{Hour of Code: Maze Challenge}~\cite{hourofcode_maze}, and has been studied in a number of prior works~\cite{DBLP:conf/lats/PiechSHG15,DBLP:conf/edm/EfremovGS20,DBLP:conf/nips/AhmedCEFGRS20}.

\vspace{-1mm}
\textbf{The space of codes.\footnote{Codes are also interchangeably referred to as programs.}} We define the space of all possible codes as \ensuremath{\mathbb{C}}{} and represent them using a \emph{Domain Specific Language }(DSL)~\cite{gulwani2017program}. In particular, for codes relevant to  tasks considered in this paper, we use a DSL from~\cite{DBLP:conf/nips/AhmedCEFGRS20}. A code $\text{\textcode{C}} \in \ensuremath{\mathbb{C}}$ has the following attributes: $\text{\textcode{C}}_\text{blocks}$ is the set of types of code blocks used in $\text{\textcode{C}}$, $\text{\textcode{C}}_\text{size}$ is the number of code blocks used, and $\text{\textcode{C}}_\text{depth}$ is the depth of the \emph{Abstract Syntax Tree} of $\text{\textcode{C}}$. Details of this DSL and code attributes are not crucial for the readability of subsequent sections; however, they provide useful formalism when implementing different techniques introduced in this paper.

\vspace{-1mm}
\textbf{Solution code and student attempt.} For a given task $\text{\textcode{T}}$, a \emph{solution code} $\text{\textcode{C}}^{\star}_{\text{\textcode{T}}} \in \ensuremath{\mathbb{C}}$ should solve the visual puzzle; additionally, it can only use the allowed types of code blocks (i.e., $\text{\textcode{C}}_\text{blocks} \subseteq \text{\textcode{T}}_\textnormal{store}$) and should be within the specified size threshold (i.e., $\text{\textcode{C}}_\text{size} \leq \text{\textcode{T}}_\textnormal{size}$). We note that a task $\text{\textcode{T}} \in \ensuremath{\mathbb{T}}$ in general may have multiple solution codes; in this paper, we typically refer to a single solution code that is provided as input. A \emph{student attempt} for a task $\text{\textcode{T}}$ refers to a code that is being written by students (including incorrect or partial codes). A student attempt could be any code $\text{\textcode{C}} \in \ensuremath{\mathbb{C}}$ as long as it uses the set of available types of code blocks (i.e., $\text{\textcode{C}}_\text{blocks} \subseteq \text{\textcode{T}}_\textnormal{store}$); importantly, it is not restricted by the size threshold $\text{\textcode{T}}_\textnormal{size}$---same setting as in the programming environment of \emph{Hour of Code: Maze Challenge}~\cite{hourofcode_maze}.

\subsection{Objective}\label{sec:problem.objectives}

\textbf{Distinct phases.}  To formalize our objective, we introduce three distinct phases in our problem setup that provide a conceptual separation in terms of information and computation available to a system. More concretely, we have:

\vspace{-4mm}
\setlength{\leftmargini}{1.3em}
\begin{enumerate}[label=(\arabic*)]
    \item Reference task $\text{\textcode{T}}^{\text{ref}}$: We are given a reference task $\text{\textcode{T}}^{\text{ref}}$ for which we have real-world datasets of different students' attempts as well as access to other data resources. Reference tasks are fixed and the system can use any computation a priori (e.g., compute code embeddings).
    %
    \item Student \textcode{stu}{} attempts $\text{\textcode{T}}^{\text{ref}}$: The system interacts with a student, namely \textcode{stu}{}, who attempts the reference task $\text{\textcode{T}}^{\text{ref}}$ and submits a code, denoted as $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{ref}}}$. At the end of this phase, the system has observed \textcode{stu}{}'s behavior on $\text{\textcode{T}}^{\text{ref}}$ and we denote this observation by the tuple $(\text{\textcode{T}}^{\text{ref}}, \text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{ref}}})$.\footnote{In practice, the system might have more information, e.g., the whole trajectory of edits leading to $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{ref}}}$ or access to some prior information about the student \textcode{stu}{}.}
    %
    \item Target task $\text{\textcode{T}}^{\text{tar}}$: The system seeks to synthesize the student \textcode{stu}{}'s behavior on a target task $\text{\textcode{T}}^{\text{tar}}$. Importantly, the target task $\text{\textcode{T}}^{\text{tar}}$ is not available a priori and this synthesis process would be done in real-time, possibly with constrained computational resources. Furthermore, the system may have to synthesize the \textcode{stu}{}'s behavior on a large number of different target tasks from the space \ensuremath{\mathbb{T}}{} (e.g., to personalize the next task in a curriculum).\footnote{We note that, even though the \emph{Hour of Code: Maze Challenge}~\cite{hourofcode_maze} has only $20$ tasks, the space \ensuremath{\mathbb{T}}{} is intractably large and new tasks can be generated automatically, e.g., when providing feedback or for additional practice~\cite{DBLP:conf/nips/AhmedCEFGRS20}.} 
    \vspace{-4mm}
    %
\end{enumerate}
\setlength{\leftmargini}{2.5em}

\vspace{-0.5mm}
\textbf{Granularity level of our objective.}  
There are several different granularity levels at which we can set up the goal of predicting the student \textcode{stu}{}'s behavior for the target task $\text{\textcode{T}}^{\text{tar}}$, including: (a) a coarse-level binary prediction of whether \textcode{stu}{} will successfully solve $\text{\textcode{T}}^{\text{tar}}$, (b) a medium-level prediction about \textcode{stu}{}'s behavior w.r.t. to a predefined feature set (e.g., labelled misconceptions or programmatic features); (c) a fine-level prediction in terms of synthesizing $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{tar}}}$, i.e., a program that \textcode{stu}{} would write if the system would assign $\text{\textcode{T}}^{\text{tar}}$ to the student. In this work, we focus on this fine-level, arguably also the most challenging, synthesis objective.

\vspace{-1.5mm}
\textbf{Performance evaluation.} So far, we have concretized the synthesis objective; however, there is still a question of how to quantitatively measure the performance of a technique set out to achieve this objective. The key challenge stems from the open-ended and conceptual nature of programming tasks. Even for seemingly simple tasks such as in Figures~\ref{fig:overview.hoc4.reftask}~and~\ref{fig:overview.hoc18.reftask}, the students' attempts can be highly diverse, it is difficult to detect the student's misconceptions from observed behaviors, and the space of misconceptions itself is not clearly understood. To this end, we begin by designing a benchmark to quantitatively measure  the performance of different techniques w.r.t. our objective.

\section{Benchmark and Initial Results}\label{sec:benchmark}
In this section, we introduce our benchmark, \ensuremath{\textsc{StudentSyn}}{}, and report initial results highlighting the gap in performance of simple baselines and human experts.

\subsection{S{\footnotesize \textbf{TUDENT}}S{\footnotesize \textbf{YN}}: Data Curation}\label{sec:benchmark.data}
We begin by curating a synthetic dataset for the benchmark, designed to capture different scenarios of the three distinct phases mentioned in Section~\ref{sec:problem.objectives}. In particular, each scenario corresponds to a 4-tuple $(\text{\textcode{T}}^{\text{ref}}, \text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{ref}}}, \text{\textcode{T}}^{\text{tar}}, \text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{tar}}})$, where $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{ref}}}$ (observed by the system) and $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{tar}}}$ (to be synthesized by the system) correspond to a student \textcode{stu}'s attempts.

\looseness-1\textbf{Reference and target tasks.} 
We select two reference tasks for this benchmark, namely $\text{\textcode{T}}^{4}$ and $\text{\textcode{T}}^{18}$, as illustrated in Figures~\ref{fig:overview.hoc4.reftask}~and~\ref{fig:overview.hoc18.reftask}. These tasks correspond to Maze\#$4$ and Maze\#$18$ in the \emph{Hour of Code: Maze Challenge}~\cite{hourofcode_maze}, and have been studied in a number of prior works~\cite{DBLP:conf/lats/PiechSHG15,DBLP:conf/edm/EfremovGS20,DBLP:conf/nips/AhmedCEFGRS20}, because of the availability of large-scale datasets of students' attempts for these two tasks.
For each reference task, we manually create three target tasks as shown in Figures~\ref{fig:benchmark.hoc4.targettasks}~and~\ref{fig:benchmark.hoc18.targettasks}; as discussed in the figure captions, these target tasks are similar to the corresponding reference task in a sense that the set of available block types is same and the nesting structure of programming constructs in solution codes is same.

\vspace{-1mm}
\textbf{Types of students' behaviors and students' attempts.} For a given reference-target task pair $(\text{\textcode{T}}^{\text{ref}}, \text{\textcode{T}}^{\text{tar}})$, next we seek to simulate a student \textcode{stu} to create \textcode{stu}'s attempts $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{ref}}}$ and $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{tar}}}$. We begin by identifying a set of salient students' behaviors and misconceptions for reference tasks $\text{\textcode{T}}^{\text{4}}$ and $\text{\textcode{T}}^{\text{18}}$ based on students' attempts observed in the real-world dataset of~\cite{DBLP:conf/lats/PiechSHG15}. In this benchmark, we select $6$ types of students' behaviors for each reference task---these types are highlighted in Figures~\ref{fig:benchmark.hoc4.students}~and~\ref{fig:benchmark.hoc18.students} for $\text{\textcode{T}}^{\text{4}}$ and $\text{\textcode{T}}^{\text{18}}$, respectively.\footnote{In real-world settings, the types of students' behaviors and their attempts have a much larger variability and complexities with a long-tail; in future work, we plan to extend our benchmark to cover more scenarios, see Section~\ref{sec:conclusions}.}
For a given pair $(\text{\textcode{T}}^{\text{ref}}, \text{\textcode{T}}^{\text{tar}})$, we first simulate a student \textcode{stu} by associating this student to one of the $6$ types, and then manually create \textcode{stu}'s attempts $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{ref}}}$ and $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{tar}}}$. For a given scenario $(\text{\textcode{T}}^{\text{ref}}, \text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{ref}}}, \text{\textcode{T}}^{\text{tar}}, \text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{tar}}})$, the attempt $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{tar}}}$ is not observed by the system and serves as a \emph{ground truth} in our benchmark for evaluation purposes; in the following, we interchangeably write a scenario as $(\text{\textcode{T}}^{\text{ref}}, \text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{ref}}}, \text{\textcode{T}}^{\text{tar}}, \text{\textcode{?}})$.

\vspace{-1mm}
\textbf{Total scenarios.} In total, we create $72$ unique scenarios $(\text{\textcode{T}}^{\text{ref}}, \text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{ref}}}, \text{\textcode{T}}^{\text{tar}}, \text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{tar}}})$ in the benchmark corresponding to (i) $2$ reference tasks, (ii) $3$ target tasks per reference task, (iii) $6$ types of students' behaviors per reference task, and (iv) $2$ students per type. This, in turn, leads to a total of $72$ ($=2\times3\times6\times2$) unique scenarios.

\subsection{S{\footnotesize \textbf{TUDENT}}S{\footnotesize \textbf{YN}}: Performance Measures} \label{sec:benchmark.measures}
We introduce two performance measures to capture our synthesis objective. Our first measure, namely \emph{generative performance}, is to directly capture the quality of fine-level synthesis of the student \textcode{stu}'s attempt; however, this measure requires a human-in-the-loop evaluation. To automate the evaluation process, we then introduce a second performance measure, namely \emph{discriminative performance}.

\vspace{-1mm}
\looseness-1\textbf{Generative performance.}
As a generative performance measure, we introduce a $4$-point \textit{Likert scale} to evaluate the quality of synthesizing \textcode{stu}'s attempt $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{tar}}}$ for a scenario $(\text{\textcode{T}}^{\text{ref}}, \text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{ref}}}, \text{\textcode{T}}^{\text{tar}}, \text{\textcode{?}})$. The scale is captured to assign scores based on two factors: (a) whether the elements of the student's behavior observed in $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\textnormal{ref}}}$ are present, (b) whether the elements of the target task $\text{\textcode{T}}^{\textnormal{tar}}$ (e.g., parts of its solution) are present. More concretely, the scores are assigned as follows (with higher scores being better): (i) Score $1$ means the technique does not have synthesis capability; (ii) Score $2$ means the synthesis fails to capture the elements of $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\textnormal{ref}}}$ and  $\text{\textcode{T}}^{\textnormal{tar}}$; (iii) Score $3$ means the synthesis captures the elements only of $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\textnormal{ref}}}$ or of $\text{\textcode{T}}^{\textnormal{tar}}$, but not both; (iv) Score $4$ means the synthesis captures the elements of both $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\textnormal{ref}}}$ and $\text{\textcode{T}}^{\textnormal{tar}}$.

\vspace{-1mm}
\looseness-1\textbf{Discriminative performance.} 
As the generative performance requires human-in-the-loop evaluation, we also introduce a disciminative performance measure based on the prediction accuracy of choosing the student attempt from a set.
More concretely, given a scenario $(\text{\textcode{T}}^{\text{ref}}, \text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{ref}}}, \text{\textcode{T}}^{\text{tar}}, \text{\textcode{?}})$, the discriminative objective is to choose $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\textnormal{tar}}}$ from ten candidate codes; see Figure~\ref{fig:benchmark.hoc18.discriminative}. These ten options are created automatically in a systematic way and include: (a) the \emph{ground-truth} $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\textnormal{tar}}}$ from the benchmark, (b) the solution code  $\text{\textcode{C}}^{\star}_{\text{\textcode{T}}^{\textnormal{tar}}}$, (c) five codes $\text{\textcode{C}}^{\text{\textcode{stu}'}}_{\text{\textcode{T}}^{\textnormal{tar}}}$ from the benchmark associated with other students \textcode{stu}' whose behavior type is different from \textcode{stu}, and (iv) three \emph{randomly} constructed codes obtained by editing $\text{\textcode{C}}^*_{\text{\textcode{T}}^{\textnormal{tar}}}$.

\input{fig/_benchmark/fig_benchmark_table_initial_results} 

\subsection{Initial Results}\label{sec:benchmark.initialresults}
As a starting point, we design a few simple baselines and compare their performance with that of human experts. %

\vspace{-1mm}
\looseness-1\textbf{Simple baselines.}
 The simple baselines that we develop here are meant for the discriminative-only objective; they do not have  synthesis capability. Our first baseline \ensuremath{\textsc{RandD}}{} simply chooses a code from the $10$ options at random.  Our next two baselines, \ensuremath{\textsc{EditD}}{} and \ensuremath{\textsc{EditEmbD}}{}, are defined through a distance function $\text{D}_{\text{\textcode{T}}^{\textnormal{ref}}}(\text{\textcode{C}}, \text{\textcode{C}}')$ that quantifies a notion of distance between any two codes $\text{\textcode{C}}, \text{\textcode{C}}'$  for a fixed reference task. For a scenario $(\text{\textcode{T}}^{\text{ref}}, \text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{ref}}}, \text{\textcode{T}}^{\text{tar}}, \text{\textcode{?}})$ and ten option codes, these baselines select the code  \text{\textcode{C}}{} that minimizes $\text{D}_{\text{\textcode{T}}^{\textnormal{ref}}}(\text{\textcode{C}}, \text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{ref}}})$. \ensuremath{\textsc{EditD}}{} uses a tree-edit distance between \emph{Abstract Syntax Trees} as the distance function, denoted as $\text{D}^{\textnormal{edit}}_{\text{\textcode{T}}^{\textnormal{ref}}}$. \ensuremath{\textsc{EditEmbD}}{} extends \ensuremath{\textsc{EditD}}{} by considering a distance function that combines $\text{D}^{\textnormal{edit}}_{\text{\textcode{T}}^{\textnormal{ref}}}$ and a code-embedding based distance function $\text{D}^{\textnormal{emb}}_{\text{\textcode{T}}^{\textnormal{ref}}}$; in this paper, we trained code embeddings with the methodology of \cite{DBLP:conf/edm/EfremovGS20} using a real-world dataset of student attempts on $\text{\textcode{T}}^{\textnormal{ref}}$. \ensuremath{\textsc{EditEmbD}}{} then uses a distance function as a convex combination $\big(\alpha \cdot \text{D}^{\textnormal{edit}}_{\text{\textcode{T}}^{\textnormal{ref}}}(\text{\textcode{C}}, \text{\textcode{C}}') + (1-\alpha)\cdot  \text{D}^{\textnormal{emb}}_{\text{\textcode{T}}^{\textnormal{ref}}}(\text{\textcode{C}}, \text{\textcode{C}}')\big)$ where $\alpha$ is optimized for each reference task separately. For measuring the discriminative performance, we randomly sample a scenario, create ten options, and measure the predictive accuracy of the technique---the details of this experimental evaluation are provided in Section~\ref{sec:experiments:dicriminative}.

\vspace{-1mm}
\textbf{Human experts.} Next, we evaluate the performance of human experts; these evaluations are done through a web platform where an expert would provide a generative or discriminative response to a given scenario $(\text{\textcode{T}}^{\text{ref}}, \text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{ref}}}, \text{\textcode{T}}^{\text{tar}}, \text{\textcode{?}})$. A total of three experts, with experience in block-based programming and tutoring, participated in our evaluation. We first carried out generative performance evaluations where an expert has to write the student attempt code; afterwards, we carried out discriminative performance evaluations where an expert would choose one of the options. In total, each expert participated in $36$ generative evaluations ($18$ per reference task) and $72$ discriminative evaluations ($36$ per reference task). Results in Table~\ref{table:benchmark.initialresults} highlight the huge performance gap between the human experts and simple baselines; further details are provided in Section~\ref{sec:experiments}.

\section{Neural Synthesizer N{\footnotesize \textbf{EUR}}SS{}}
\label{sec:continual}
\looseness-1Our first technique, \ensuremath{\textsc{NeurSS}}{} (\emph{Neural Program Synthesis for \ensuremath{\textsc{StudentSyn}}}), is inspired by recent advances in neural program synthesis~\cite{DBLP:conf/iclr/BunelHDSK18,DBLP:conf/iclr/ChenLS19}. In our work, we use the neural architecture proposed in~\cite{DBLP:conf/iclr/BunelHDSK18}---at a high-level, the neural synthesizer model takes as input a visual task $\text{\textcode{T}}$, and then sequentially synthesizes a code $\text{\textcode{C}}$ by using programming tokens in  $\text{\textcode{T}}_{\textnormal{store}}$. However, our goal is not simply to synthesize a solution code, instead, we want to synthesize attempts of a given student that the system is interacting with at real-time/deployment. To achieve this goal, \ensuremath{\textsc{NeurSS}}{} operates in three stages as illustrated in Figure~\ref{fig:continual.pipeline}. Each stage is in line with a phase of our objective described in Section~\ref{sec:problem.objectives}. For each stage, we provide an overview of the key ideas and high-level implementation details in the following paragraphs. We will publicly release our implementation with full details.

\vspace{-1.2mm}
\textbf{N{\scriptsize \textbf{EUR}}SS{}-Stage1.i:} Given a reference task and its solution $(\text{\textcode{T}}^{\textnormal{ref}}, \text{\textcode{C}}^{\star}_{\text{\textcode{T}}^{\textnormal{ref}}})$, the goal of this stage is to train a neural synthesizer model that can synthesize solutions for any task similar to  $\text{\textcode{T}}^{\textnormal{ref}}$.  In this stage, we use a synthetic dataset $\mathcal{D}^{\text{tasks}}_{\text{\textcode{T}}^{\text{ref}}}$ comprising of task-solution pairs $(\text{\textcode{T}}, \text{\textcode{C}}^{\star}_{\text{\textcode{T}}})$; the notion of similarity here means that $\text{\textcode{T}}_\textnormal{store}$ is the same as $\text{\textcode{T}}^{\textnormal{ref}}_\textnormal{store}$ and the nesting structure of programming constructs in $\text{\textcode{C}}^{\star}_{\text{\textcode{T}}}$ is the same as in $\text{\textcode{C}}^{\star}_{\text{\textcode{T}}^{\textnormal{ref}}}$. To train this synthesizer, we leverage recent advances in neural program synthesis~\cite{DBLP:conf/iclr/BunelHDSK18, DBLP:conf/iclr/ChenLS19}; in particular, we use the encoder-decoder architecture and imitation learning procedure from \cite{DBLP:conf/iclr/BunelHDSK18}. The model we use in our experiments has  deep-CNN layers for extracting task features and an LSTM for sequentially generating programming tokens. The input to the synthesizer is a one-hot task representation of the visual grid denoting different elements of the grid (e.g., ``goal'', ``walls'', and position/orientation of the ``avatar''), as well as the programming tokens synthesized by the model so far. To generate the synthetic dataset $\mathcal{D}^{\text{tasks}}_{\text{\textcode{T}}^{\text{ref}}}$, we use the  task generation procedure from \cite{DBLP:conf/nips/AhmedCEFGRS20}. For the reference task $\text{\textcode{T}}^{\textnormal{4}}$, we generated $\mathcal{D}^{\text{tasks}}_{\text{\textcode{T}}^{\text{4}}}$ of size $50,000$; for the reference task $\text{\textcode{T}}^{\textnormal{18}}$, we generated $\mathcal{D}^{\text{tasks}}_{\text{\textcode{T}}^{\text{18}}}$ of size $200,000$.
\input{fig/_continual/fig_continual_pipeline}

\vspace{-1.2mm}
\looseness-1\textbf{N{\scriptsize \textbf{EUR}}SS{}-Stage1.ii:} Given a reference task $\text{\textcode{T}}^{\textnormal{ref}}$, the goal of this stage is to train a code embedding network that maps an input code $\text{\textcode{C}}$ to a feature vector $\phi(\text{\textcode{C}})$. This code embedding space will be useful later in N{\scriptsize \textbf{EUR}}SS{}-Stage2 when we observe the student \textcode{stu}'s attempt. For each $\text{\textcode{T}}^{\textnormal{ref}}$, we use a real-world dataset of students' attempts $\mathcal{D}^{\text{attempts}}_{\text{\textcode{T}}^{\text{ref}}}$ on $\text{\textcode{T}}^{\textnormal{ref}}$ to train this embedding network using the methodology of \cite{DBLP:conf/edm/EfremovGS20}. To train this embedding network, we construct a set with triplets $(\text{\textcode{C}}, \text{\textcode{C}}', \text{D}^{\textnormal{edit}}_{\text{\textcode{T}}^{\textnormal{ref}}}(\text{\textcode{C}},\text{\textcode{C}}'))$ where $\text{\textcode{C}}, \text{\textcode{C}}' \in \mathcal{D}^{\text{attempts}}_{\text{\textcode{T}}^{\text{ref}}}$ and $\text{D}^{\textnormal{edit}}_{\text{\textcode{T}}^{\textnormal{ref}}}$ computes the tree-edit distance between \emph{Abstract Syntax Trees} of two codes (see Section~\ref{sec:benchmark.initialresults}). The embedding network is trained so the embedding space preserves given distances, i.e., $||\phi(\text{\textcode{C}}) - \phi(\text{\textcode{C}}')|| \approx \text{D}_{\text{\textcode{T}}^{\textnormal{ref}}}^{\textnormal{edit}}(\text{\textcode{C}},\text{\textcode{C}}')$ for a triplet. Following the setup in \cite{DBLP:conf/edm/EfremovGS20}, we use a bidirectional LSTM architecture for the network and use $\mathbb{R}^{80}$ embedding space. 

\vspace{-1.2mm}
\looseness-1\textbf{N{\scriptsize \textbf{EUR}}SS{}-Stage2:} In this stage, the system observes the student \textcode{stu}'s attempt $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\textnormal{ref}}}$ and initiates continual training of the neural synthesizer model from Stage1.i in real-time. More concretely, we fine-tune the pre-trained synthesizer model from Stage 1.i with the goal of transferring the student \textcode{stu}'s behavior from  the reference task $\text{\textcode{T}}^{\text{ref}}$ to any target task $\text{\textcode{T}}^{\textnormal{tar}}$. Here, we make use of the embedding network from Stage1.ii that enables us to find neighboring codes $\text{\textcode{C}} \in \mathcal{D}^{\text{attempts}}_{\text{\textcode{T}}^{\text{ref}}}$ such that $\phi(\text{\textcode{C}})$ is close to $\phi(\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\textnormal{ref}}})$. More formally, the set of neighbors is given by $\{ \text{\textcode{C}} \in  \mathcal{D}^{\text{attempts}}_{\text{\textcode{T}}^{\text{ref}}} : ||\phi(\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\textnormal{ref}}}) - \phi(\text{\textcode{C}})||_2 \leq r\}$ where the threshold $r$ is a hyperparameter.
Next, we use these neighboring codes to create a small dataset for continual training: this dataset comprises of the task-code pairs $(\text{\textcode{C}}, \text{\textcode{T}}^{\text{ref}})$ where $\text{\textcode{C}}$ is a neighboring code for $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\textnormal{ref}}}$ and $\text{\textcode{T}}^{\text{ref}}$ is the reference task. There are two crucial ideas behind the design of this stage. First, we do this continual training using a set of neighboring codes w.r.t. $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\textnormal{ref}}}$ instead of just using $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\textnormal{ref}}}$---this is important to avoid overfitting during the process. Second, during this continual training, we train for a small number of epochs (a hyperparameter), and only fine-tune the decoder by freezing the encoder---this is important so that the network obtained after continual training still maintains its synthesis capability. The hyperparameters in this stage (threshold $r$, the number of epochs and learning rate) are obtained through cross-validation in our experiments (see Section~\ref{sec.experiments.discriminative})

\vspace{-1.2mm}
\looseness-1\textbf{N{\scriptsize \textbf{EUR}}SS{}-Stage3:} In this stage, the system observes $\text{\textcode{T}}^{\textnormal{tar}}$ and uses the model from Stage2 to synthesize $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\textnormal{tar}}}$. More concretely, we provide $\text{\textcode{T}}^{\textnormal{tar}}$ as an input to the Stage2 model and then synthesize a small set of codes as outputs using a \emph{beam search} procedure proposed in \cite{DBLP:conf/iclr/BunelHDSK18}. This procedure allows us to output codes that have high likelihood or probability of synthesis with the model. In our experiments, we use a \emph{beam size} of $64$; Figures~\ref{fig:experiments.hoc4.generative.continual}~and~\ref{fig:experiments.hoc18.generative.continual} illustrate Top-$3$ synthesized codes for different scenarios obtained through this procedure. The Top-$1$ code is then used for generative performance evaluation. For the discriminative performance evaluation, we are given a set of option codes; here we use the model of Stage2 to compute the likelihood of provided options and then select one with the highest probability.

\section{Symbolic Synthesizer S{\footnotesize \textbf{YM}}SS{}}
\label{sec:pcfg}
In the previous section, we introduced \ensuremath{\textsc{NeurSS}}{} inspired by neural program synthesis. In our experiments (see Section~\ref{sec:experiments}), \ensuremath{\textsc{NeurSS}}{} significantly outperforms the simple baselines introduced earlier; yet, there is a substantial gap in the performances of \ensuremath{\textsc{NeurSS}}{} and \ensuremath{\textsc{TutorSS}}{}. An important question that we seek to resolve is how much of this performance gap can be reduced by leveraging domain knowledge such as the types of students' behaviors. To this end, we introduce our second technique, \ensuremath{\textsc{SymSS}}{} (\emph{Symbolic Program Synthesis for \ensuremath{\textsc{StudentSyn}}}), inspired by recent advances in using symbolic methods for program synthesis~\cite{lake2015human,DBLP:conf/aaai/WuMGP19,DBLP:conf/nips/AhmedCEFGRS20,DBLP:conf/edm/MalikWVSCMGP21}. Similar in spirit to \ensuremath{\textsc{NeurSS}}{}, \ensuremath{\textsc{SymSS}}{} operates in three stages as illustrated in Figure~\ref{fig:pcfg.pipeline}. Each stage is in line with a phase of our objective described in Section~\ref{sec:problem.objectives}. For each stage, we provide an overview of the key ideas and high-level implementation details in the following paragraphs. We will publicly release our implementation with full details.

\vspace{-1mm}
\textbf{S{\scriptsize \textbf{YM}}SS{}-Stage1 (High-level design).} For a given reference task and its solution $(\text{\textcode{T}}^{\textnormal{ref}}, \text{\textcode{C}}^{\star}_{\text{\textcode{T}}^{\textnormal{ref}}})$, the goal of this stage is to create a symbolic program synthesizer that encodes domain knowledge. In this stage, we need access to the following: (i) a set of types of students' behaviors the system is expected to encounter at deployment, denoted by $\mathcal{M}$ in Figure~\ref{fig:pcfg.pipeline}; (ii) an expert with domain knowledge.\footnote{We note that \ensuremath{\textsc{SymSS}}{} is the only technique that requires access to the types of students' behaviors; in our implementation and experiments, we considered $\mathcal{M}$ to be the same as the types of students' behaviors in \ensuremath{\textsc{StudentSyn}}. In practice, there could potentially be a large number of types of behaviors, that manifest in students' attempts in an unknown way; hence, \ensuremath{\textsc{SymSS}}{} in a real-world setting could perform worse than the performance reported on \ensuremath{\textsc{StudentSyn}}. Also, we note that human experts in \ensuremath{\textsc{TutorSS}}{} were not told about the types of students' behaviors in \ensuremath{\textsc{StudentSyn}}.}
The expert then designs a symbolic program synthesizer  $\mathcal{G}_{\text{\textcode{T}}^{\textnormal{ref}}}(\text{\textcode{T}},\text{\textcode{C}}_{\text{\textcode{T}}}^\star, \text{M})$ for the reference task $\text{\textcode{T}}^{\textnormal{ref}}$ that operates as follows: (a) as first input, it takes a task-solution pair ($\text{\textcode{T}}, \text{\textcode{C}}^\star_{\text{\textcode{T}}}$) where $\text{\textcode{T}}$ is expected to be similar to $\text{\textcode{T}}^{\textnormal{ref}}$; (b) as second input, it takes a type of student behavior $\text{M} \in \mathcal{M}$; (c) as outputs, it synthesizes a code $\text{\textcode{C}}$ along with the probability $p$ of synthesis. This symbolic synthesizer $\mathcal{G}_{\text{\textcode{T}}^{\text{ref}}}(\text{\textcode{T}},\text{\textcode{C}}^\star_{\text{\textcode{T}}},\text{M})$ is designed as a \emph{grammar creator module}: internally, it first automatically creates a specific \emph{grammar} corresponding to its input arguments and then generates codes based on this \emph{grammar}.

\vspace{-1mm}
\textbf{S{\scriptsize \textbf{YM}}SS{}-Stage1 (PCFG).} 
Inspired by recent work on modeling students' misconceptions via \emph{Probabilistic Context Free Grammars} (PCFG)s \cite{DBLP:conf/aaai/WuMGP19}, we consider a PCFG family of grammars inside $\mathcal{G}_{\text{\textcode{T}}^{\text{ref}}}$.\footnote{Context Free Grammars (CFG)s generate strings by applying a set of production rules where each symbol is expanded independently of its context~\cite{martin1991introduction}. These rules are defined through a \emph{start} symbol, \emph{non-terminal} symbols, and \emph{terminal} symbols. PCFGs additionally assign a probability to each production rule; see Figure~\ref{fig:pcfg.grammar} as an example.}
More concretely, given a reference task $\text{\textcode{T}}^{\textnormal{ref}}$, a task-solution pair $(\text{\textcode{T}}, \text{\textcode{C}}^\star_{\text{\textcode{T}}})$, and a type M, the expert has designed an automated function that creates a PCFG corresponding to $\mathcal{G}_{\text{\textcode{T}}^{\textnormal{ref}}}(\text{\textcode{T}},\text{\textcode{C}}_{\text{\textcode{T}}}^\star, \text{M})$ which is then used to sample/synthesize codes. This PCFG is created automatically and the production rules are based on: the type M, the input solution code $\text{\textcode{C}}_{\text{\textcode{T}}}^\star$, and optionally features of $\text{\textcode{T}}$. In our implementation, we designed two separate symbolic synthesizers $\mathcal{G}_{\text{\textcode{T}}^{\text{4}}}$ and $\mathcal{G}_{\text{\textcode{T}}^{\text{18}}}$ associated with two reference tasks. As a concrete example, consider the scenario in Figure~\ref{fig:intro.hoc4}: the PCFG created internally at \ensuremath{\textsc{SymSS}}{}-Stage3 corresponds to $\mathcal{G}_{\text{\textcode{T}}^{\textnormal{4}}}(\text{\textcode{T}}^{\textnormal{4x}}, \text{\textcode{C}}^{\star}_{\text{\textcode{T}}^{\textnormal{4x}}}, \textnormal{M}^{\textnormal{\textcode{stu}}})$ and is illustrated in Figure~\ref{fig:pcfg.grammar}; details are provided in the caption and as comments within the figure.

\input{fig/_pcfg/fig_pcfg_pipeline}
\input{fig/_pcfg/fig_pcfg_grammer}

\vspace{-1mm}
\textbf{S{\scriptsize \textbf{YM}}SS{}-Stage2}.
In this stage, the system observes the student \textcode{stu}'s attempt $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\textnormal{ref}}}$ and makes a prediction about the  behavior type $\text{M}^{\text{\textcode{stu}}} \in \mathcal{M}$. For each behavior type $\text{M} \in \mathcal{M}$ specified at Stage1, we use $\mathcal{G}_{\text{\textcode{T}}^{\textnormal{ref}}}$ with arguments $(\text{\textcode{T}}^{\text{ref}}, \text{\textcode{C}}^{\star}_{\textnormal{ref}}, \text{M})$ to calculate the probability of synthesizing $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{ref}}}$ w.r.t. $\text{M}$, referred to as $p(\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{ref}}}|\text{M})$. This is done by internally creating a corresponding PCFG for $\mathcal{G}_{\text{\textcode{T}}^{\textnormal{ref}}}(\text{\textcode{T}}^{\text{ref}}, \text{\textcode{C}}^{\star}_{\textnormal{ref}}, \text{M})$. To predict M$^{\text{\textcode{stu}}}$, we pick the behavior type M with the highest probability. As an implementation detail, we construct PCFGs in a special form called the \emph{Chmosky Normal Form} (CNF) \cite{Chomsky1959OnCF,martin1991introduction} (though the PCFG illustrated in Figure~\ref{fig:pcfg.grammar} is not in CNF).
This form imposes constraints to the grammar rules that add extra difficulty in grammar creation, but enables the efficient calculation of $p(\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{ref}}}|\text{M})$.

\vspace{-1mm}
\looseness-1\textbf{S{\scriptsize \textbf{YM}}SS{}-Stage3.} In this stage, the system observes a target task $\text{\textcode{T}}^{\textnormal{tar}}$ along with its solution $\text{\textcode{C}}^{\star}_{\text{\textcode{T}}^{\textnormal{tar}}}$. Based on the behavior type $\text{M}^{\text{\textcode{stu}}}$ inferred in Stage2, it uses $\mathcal{G}_{\text{\textcode{T}}^{\textnormal{ref}}}$ with input arguments $(\text{\textcode{T}}^{\textnormal{tar}}, \text{\textcode{C}}_{\text{\textcode{T}}^{\textnormal{tar}}}^\star,\text{M}^{\text{\textcode{stu}}})$ to synthesize $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\textnormal{tar}}}$. More concretely, we use $\mathcal{G}_{\text{\textcode{T}}^{\textnormal{ref}}}(\text{\textcode{T}}^{\textnormal{tar}}, \text{\textcode{C}}_{\text{\textcode{T}}^{\textnormal{tar}}}^\star,\text{M}^{\text{\textcode{stu}}})$ to synthesize a large set of codes as outputs along with probabilities. In our implementation, we further normalize these probabilities appropriately by considering the number of production rules involved.  In our experiments, we  sample a set of $1000$ codes and keep the codes with highest probabilities; Figures~\ref{fig:experiments.hoc4.generative.pcfg}~and~\ref{fig:experiments.hoc18.generative.pcfg} illustrate the Top-$3$ synthesized codes for two scenarios, obtained with this procedure. The Top-$1$ code is then used for generative performance evaluation. For the discriminative performance evaluation, we are already given a set of option codes; here we directly compute the likelihood of the provided options and then select one with the highest probability. 

\section{Experimental Evaluation}\label{sec:experiments}
In this section, we expand on the evaluation presented in Section~\ref{sec:benchmark} and include results for \ensuremath{\textsc{NeurSS}}{} and \ensuremath{\textsc{SymSS}}{}. 


\vspace{-1mm}
\subsection{Generative Performance}\label{sec:experiments.generative}
\looseness-1\textbf{Evaluation procedure.} As discussed in Section~\ref{sec:benchmark.measures}, we evaluate the generative performance of a technique in the following steps: (a) a scenario $(\text{\textcode{T}}^{\text{ref}}, \text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{ref}}}, \text{\textcode{T}}^{\text{tar}}, \text{\textcode{?}})$ is picked; (b) the technique synthesizes \textcode{stu}'s attempt, i.e., a program that \textcode{stu}{} would write if the system would assign $\text{\textcode{T}}^{\text{tar}}$ to the student; (c) the generated code is scored on the $4$-point \textit{Likert scale}. The scoring step requires human-in-the-loop evaluation and involved an expert (different from the three experts that are part of \ensuremath{\textsc{TutorSS}}{}). Overall, each technique is evaluated for $36$ unique scenarios in \ensuremath{\textsc{StudentSyn}}{}---we selected $18$ scenarios per reference task by first picking one of the $3$ target tasks and then picking a student from one of the $6$ different types of behavior. The final performance results are reported as an average across these scenarios. 

\vspace{-1mm}
\looseness-1\textbf{Quantitative results.} Table~\ref{table:benchmark.finalresults} expands on Table~\ref{table:benchmark.initialresults} and reports results on the generative performance per reference task for different techniques. As noted in Section~\ref{sec:benchmark.initialresults}, the simple baselines (\ensuremath{\textsc{RandD}}, \ensuremath{\textsc{EditD}}, \ensuremath{\textsc{EditEmbD}}) do not have a synthesis capability and hence have a score $1.00$. \ensuremath{\textsc{TutorSS}}{}, i.e., human experts, achieves the highest performance with aggregated scores of $3.85$ and $3.90$ for two reference tasks respectively; as mentioned in Table~\ref{table:benchmark.initialresults}, these scores are reported as an average over scores achieved by three different experts. \ensuremath{\textsc{SymSS}}{} also achieves high performance with aggregated scores of $3.78$ and $3.72$---only slightly lower than that of \ensuremath{\textsc{TutorSS}}{} and these gaps are not statistically significant w.r.t. $\chi^2$ tests \cite{cochran1952chi2}. The high performance of \ensuremath{\textsc{SymSS}}{} is expected given its knowledge about types of students in \ensuremath{\textsc{StudentSyn}}{} and the expert domain knowledge inherent in its design. \ensuremath{\textsc{NeurSS}}{} achieves aggregated scores of $3.00$ and $2.83$---this performance is significantly worse ($p<0.01$) compared to that of \ensuremath{\textsc{SymSS}}{}  and \ensuremath{\textsc{TutorSS}}{} w.r.t. $\chi^2$ tests.

\input{fig/_experiments/fig_experiments_hoc4_generative}
\input{fig/_experiments/fig_experiments_hoc18_generative}

\vspace{-1mm}
\textbf{Qualitative results.} Figures~\ref{fig:experiments.hoc4.generative}~and~\ref{fig:experiments.hoc18.generative} illustrate the qualitative results in terms of the generative objective for the scenarios in Figures~\ref{fig:intro.hoc4}~and~\ref{fig:intro.hoc18}, respectively. As can be seen in Figures~\ref{fig:experiments.hoc4.generative.tutor}~and~\ref{fig:experiments.hoc18.generative.tutor}, the codes generated by three human experts in \ensuremath{\textsc{TutorSS}}{} are high-scoring w.r.t. our $4$-point \textit{Likert scale}, and are slight variations of the \emph{ground-truth} codes in \ensuremath{\textsc{StudentSyn}}{}  shown in Figures~\ref{fig:experiments.hoc4.generative.benchmark}~and~\ref{fig:experiments.hoc18.generative.benchmark}. Similarly, the Top-$3$ codes generated by \ensuremath{\textsc{SymSS}}{} in Figures~\ref{fig:experiments.hoc4.generative.pcfg}~and~\ref{fig:experiments.hoc18.generative.pcfg} are high-scoring. In contrast, for the scenario in Figure~\ref{fig:intro.hoc18}, the Top-$3$ codes synthesized by \ensuremath{\textsc{NeurSS}}{} in Figure~\ref{fig:experiments.hoc18.generative.continual} only capture the elements of the student's behavior in $\text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\textnormal{ref}}}$ and miss the elements of the target task $\text{\textcode{T}}^{\textnormal{tar}}$.


\subsection{Discriminative Performance}\label{sec.experiments.discriminative}
\label{sec:experiments:dicriminative}
\looseness-1\textbf{Evaluation procedure: Creating instances.} As discussed in Section~\ref{sec:benchmark.measures}, we evaluate the discriminative performance of a technique  in the following steps: (a) a discriminative instance is created with a scenario $(\text{\textcode{T}}^{\text{ref}}, \text{\textcode{C}}^{\text{\textcode{stu}}}_{\text{\textcode{T}}^{\text{ref}}}, \text{\textcode{T}}^{\text{tar}}, \text{\textcode{?}})$  picked from the benchmark and $10$ code options created automatically; (b) the technique chooses one of the options as \textcode{stu}'s attempt; (c) the chosen option is scored either $100.0$ when correct, or $0.0$ otherwise. We create a number of discriminative instances for evaluation, and then compute an average predictive accuracy in the range $[0.0, 100.0]$. We note that the number of discriminative instances can be much larger than the number of scenarios because of the variability in creating $10$ code options. When sampling large number of instances in our experiments, we ensure that all target tasks and behavior types are represented equally.  

\vspace{-1mm}
\looseness-1\textbf{Evaluation procedure: Details about final performance.} For $\ensuremath{\textsc{TutorSS}}{}$,  we perform evaluation on a small set of $72$ instances ($36$ instances per reference task), to reduce the effort for human experts. The final performance results for $\ensuremath{\textsc{TutorSS}}{}$, as reported in Tables~\ref{table:benchmark.initialresults}~and~\ref{table:benchmark.finalresults}, are computed as an average across these instances. Next, we provide details on how the final performance results are computed for the techniques \ensuremath{\textsc{RandD}}, \ensuremath{\textsc{EditD}}, \ensuremath{\textsc{EditEmbD}}, \ensuremath{\textsc{NeurSS}}{}, and \ensuremath{\textsc{SymSS}}{}. For these techniques, we perform $\text{numEval}=10$ independent evaluation rounds, and report results as a macro-average across these rounds; these rounds are also used for statistical significance tests. Within one round, we create a set of $720$ instances ($360$ instances per reference task).  To allow hyperparameter tuning by techniques, we apply a cross-validation procedure on the $360$ instances per reference task by creating $10$-folds whereby $1$ fold is used to tune hyperparameters and $9$ folds are used to measure performance.

\vspace{-1mm}
\looseness-1\textbf{Quantitative results.}
Table~\ref{table:benchmark.finalresults} reports results on the discriminative performance per reference task for different techniques. As noted in Section~\ref{sec:benchmark.initialresults}, the initial results showed a huge gap between the human experts (\ensuremath{\textsc{TutorSS}}{}) and simple baselines (\ensuremath{\textsc{RandD}}, \ensuremath{\textsc{EditD}}, \ensuremath{\textsc{EditEmbD}}). As can be seen in Table~\ref{table:benchmark.finalresults}, our proposed  techniques (\ensuremath{\textsc{NeurSS}}{} and \ensuremath{\textsc{SymSS}}{}) have substantially reduced this performance gap w.r.t. \ensuremath{\textsc{TutorSS}}{}. \ensuremath{\textsc{SymSS}}{} achieves high performance compared to simple baselines and \ensuremath{\textsc{NeurSS}}{}; moreoever, on the reference task $\text{\textcode{T}}^\text{4}$, its performance ($88.1$) is close to that of \ensuremath{\textsc{TutorSS}}{} ($89.8$).  The high performance of \ensuremath{\textsc{SymSS}}{} is partly due to its access to types of students in \ensuremath{\textsc{StudentSyn}}{}; in fact, this information is used only by \ensuremath{\textsc{SymSS}}{} and is not even available to human experts in \ensuremath{\textsc{TutorSS}}{}---see column ``Student types'' in Table~\ref{table:benchmark.finalresults}. \ensuremath{\textsc{NeurSS}}{} outperformed simple baselines but its performance is below \ensuremath{\textsc{SymSS}}{} and \ensuremath{\textsc{TutorSS}}{} for both the reference tasks. For the three techniques \ensuremath{\textsc{NeurSS}}{}, \ensuremath{\textsc{SymSS}}{}, and \ensuremath{\textsc{EditEmbD}},  we did  statistical significance tests based on results for $\text{numEval}=10$ independent rounds as mentioned earlier. The difference in reported performances is statistically signifiant ($p < 0.01$) for any pair of these techniques on each reference task w.r.t. Tukey's HSD test \cite{Tukey1949ComparingIM}.


\section{Conclusions and Outlook}\label{sec:conclusions}
We investigated student modelling in the context of block-based visual programming environments, focusing on the ability to automatically infer students' misconceptions and synthesize their expected behavior. We introduced a novel benchmark, \ensuremath{\textsc{StudentSyn}}{}, to objectively measure the generative as well as the discriminative performance of different techniques. The gap in performance between human experts (\ensuremath{\textsc{TutorSS}}) and our techniques (\ensuremath{\textsc{NeurSS}}{}, \ensuremath{\textsc{SymSS}}) highlights the challenges in synthesizing student attempts for programming tasks. We believe that the benchmark will facilitate further research in this crucial area of student modelling for block-based visual programming environments.

There are several important directions for future work, including but not limited to: (a) incorporating more diverse tasks and student misconceptions in the benchmark; (b) scaling up the benchmark and creating a competition with a public leaderboard to facilitate research; (c) developing new neuro-symbolic synthesis techniques that can get close to the performance of \ensuremath{\textsc{TutorSS}}{} without relying on expert inputs; (d) applying our methodology to other programming environments (e.g., Python programming).


















































