Neural Task Synthesis for Visual Programming
Authors: Victor-Alexandru Pădurean
Georgios Tzannetos
Adish Singla
Venue: Accepted by TMLR ()

Abstract: Generative neural models hold great promise in enhancing programming education by synthesizing new content. We seek to design neural models that can automatically generate programming tasks for a given specification in the context of visual programming domains. Despite the recent successes of large generative models like GPT-4, our initial results show that these models are ineffective in synthesizing visual programming tasks and struggle with logical and spatial reasoning. We propose a novel neuro-symbolic technique, NeurTaskSyn, that can synthesize programming tasks for a specification given in the form of desired programming concepts exercised by its solution code and constraints on the visual task. NeurTaskSyn has two components: the first component is trained via imitation learning procedure to generate possible solution codes, and the second component is trained via reinforcement learning procedure to guide an underlying symbolic execution engine that generates visual tasks for these codes. We demonstrate the effectiveness of NeurTaskSyn through an extensive empirical evaluation and a qualitative study on reference tasks taken from the Hour of Code: Classic Maze challenge by Code.org and the Intro to Programming with Karel course by CodeHS.com.

Published in Transactions on Machine Learning Research (01/2024)
Neural Task Synthesis for Visual Programming
Victor-Alexandre Pädurean
ypuduren@mpii--ee
Max Planck Institute for Software Systems
Georgios Tzannetos
gtzannet
Mar Planck Institute for Software Systems
Adish Singla
adishs Smpi sus.oy
Max Planck Institute for Software Systems
Reviewed on OpenReview: https:// net/ forum9 id- aYkYajcJDN
Abstract
Generative neural models hold great promise in enhancing programming education by syn- thesizing new content. We seek to design neural models that can automatically generate programming tasks for a given specification in the context of visual programming domains. Despite the recent. successes of large generative models like GPT-4, our initial results show that these models are ineffective in synthesizing visual programming tasks and struggle with logical and spatial reasoning. We propose a novel neuro-symbolic technique, NEUR TASKSYN, that can synthesize programming tasks for specification given in the form of desired programming concepts exercised by its solution code and constraints on the visual task. NEuR TASKSNN has two components: the first component trained via imitation learn- ing procodure to generate possible solution codes, and the second component is trained via reinforcement learning procedure to guide an underlying symbolic execution engine that generates visual tasks for these codes. We demonstrate the effectiveness of NEUR TASKSyN through extensive empirical evaluation and qualitative study on reference tasks taken from the Hour of Code: Classic Maze challenge by Code.org and the Intro to Programming with Karel course by CodeHS.ccom.
1 Introduction
Recent advances in generative AT have demonstrated impressive performance in a variety of domains, in- cluding visual art and music creation (Dong et al.
2018
Briot et al. 2020 Suh et al. 2021 Ramesh et al.
2021
Rombach
al. 2022), medicinal chemistry synthesis (Schneider al. 2020 Walters & Murcko
2020
Tong et al.] 2021 Gao Coley 2020), and
AT-enhanced programming (Finnie-Ansley
al. 2022
Leinonen et al. 2023 Chen et al. 2021 Feng et al.
2020
Phung al. 2023a). These successes are, in part,
driven by advanced capabilities of deep generative models, such as Stable Dilfusion (Rombach al. 2022
ChatGPT [OpenAl 2023a}, and GPT-4 (OpenAl 2023b).
These advancements also hold great promise in enhancing education, for instance, by generating personalized content and new practice tasks for students
allowing them to master required concepts (Sarsa et al. 2022 Tate et al. 2023 Baidoo-Anu Owusu Ansah
2023 Lim et al. 2023 Phung et al. 2023b
In this paper, we explore the role of generative AI in visual programming domains used for introductory programming. Popular domains, such as Scratch (Resnick et al.) 2009 Hour of Code:Maze Challenge by Code.org (HoCMaze) (Code.org) 2013b a), and Karel (Pattis et al. 1995). have become integral part of introductory computer science education and are used by millions of students (Coddeorg) 2013a Wu et al. 2019 Price & Barnes 2017). In existing visual programming platforms, programming tasks are hand-curated
by tutors and the available set tasks typically very limited, posing a major hurdle for novices in mastering the missing concepts ZZi al. 2019 Ahmed et al., (020). To this end, we seek to design generative models that can automatically synthesize visual programming tasks for given specification (see Figure 1

---

Published in Transactions on Machine Learning Research (01/2024)
det RUM() N (goa1) IF IF(pathobead) nove
Allowed blocks: (nove, turnLeft, turnRight, REPEATUNTIL IFELSR)
Riss( 1 ir(pathRighe) surnhight
ELSEC
Student is working on task 7Md struggling with obtain- ing solution code cmM.
Maximum size: 7
(b) Puzzle Tjö (left), code constraints Tcode (middle), and solution craf (right).
daf RuM() REvEATUSrTL türnkight
a blocke is a body basic action blockss from the set (move, turnLeft, turnRight)
Buaa(
Al system extracts the specifi- cations vi for simpler task.
blocks
blocke
Number of blocks S
(c) Specifications vio (left), in
Paketch (middle), and w (right).
ROw
REPEATÜNTAL (goa1) (pathitight)
Allowed blocks: (move, turaleft, turnRight, REPEATUNTIL, IFELsE]
Al system generates task zwl based on gitt. delivers studeent.
BLas turnLeft
(a) interaction be- tween student and AT system.
Maximum sioe: 7
(d) Puzzle Tio (left), code constraints Teode (middle), and cout (right).
Figure 1: (a) Illustration of an Al system helping student, inspired by (Ghosh et al. 2022). The AI system supports the student when trying to solve T The system first extracts specification for a simpler task that can be provided to help the student. then generates a new task based on that specification and delivers it to the student.
(b) shows reference task Tref along with solution code Cref (c) shows specifications i extracted by AT system. (d) shows lask Tout and code Cout syuthesized by AT system.
1.1 Motivation and Overview
Our work motivated by existing literature on AI-driven educational systems that seek to provide leedback
students who are struggling while solving a programming task. For instance, (Zhi et al. 2019) studies feedback provided in the form of worked examples as demonstration and (Ghosh et al.) 2022 studics feedback provided in the form of new simpler tasks for adaptive scaffolding. We have illustrated the interaction between such system and student in Figure [ Previous works have focused studying how to adapt the feedback type according to the student's 's needs. We complement these works by focusing on generating on-the-fl the desired examples and simpler tasks that the system could provide to the student. In our work, we consider that a desired feedback format for student an input specification in the form of puzzle layout, code structure, code size, and selected programming concepts. Since the search space defined by these input specifications is potentially unbounded, designing AI systems that can synthesize correct tasks in real-time for any input specification is critical to cater to diverse set of students' behaviors.
As natural approach, one might be tempted to employ statc-of-the-art large language models (LLMs) to generale a visual programming lask by providing task synthesis specification as prompt. In particular, models like GPT-4 are trained on multi-modal data, including text, code, and visual data, and hence it soems a suitable technique for reasoning about visual programming tasks (OpenA] 2023b Bubeck et al. 2023). However, our results show that these models are ineffective in synthesizing visual programming tasks and struggle with logical and spatial reasoning, as also indicated in recent. literature state-of-the-art
2

---

Published in Transactions on Machine Learning Research (01/2024)
models (Bang et al. 2023 Bubeck et al. 2023 Valmeekam et al. 2022 Huang & Chang 2022
see Section 5
for detailed discussion. In general, a major chal challenge in using purely neural generative models for synthesizing visual programming tasks is that the generative process is highly brittle- even a small modification in the output task could make it invalid or semantically incorrect w.r.t. the input specification (Ahmed et al. 2020).
As an alternative to neural generative models, we could rely on symbolic generative methods driven by search and planning algorithms to generate content that matches a specification. Several works have shown the efficacy of symbolic methods to generate new tasks in various educational domains, e.g., algebra exercises (Singh et al.) 2012; Gulwani 2014), geometric proof problems (Alvin et al. 2014), natural deduc- tion (Ahmed et al., 2013), mathematical word problems (Polozov et al., [0015), Sokoban puzzles (Kartal ett al. 2016), and visual programming tasks (Ahmned et al. 2020 Ghosh et al. 2022). In particular, our work is related to (Ahmed et al., 2020; Ghosh et al., 2022) that proposed symbolic methods guided by hand-crafted constraints and Monte Carlo Tree Search to generate high-quality visual programming tasks. However, their symbolic methods still suffer from intractably large spaces of feasible tasks and codes for a given specification, and could take several minutes to generate an output lask for an input specification; see Section for comparison to technique. In general, a major shortcoming of using purely symbolic gencrative methods in the above-mentionel works is that the generative process is typically time-inefficient and not suitable for applications that require real-time synthesis.
Against that backdrop, the main research question is: Can we develop neuro-symbolic techniques that can synthesize high-quality visual programaming tasks while being robust and efficient? To this end, we develop NEURTASKKYN, a novel couro-symbolie technique that can synthesize programming tasks for input specifications in the form of desired programming concepts exercised by its solution code and constraints the visual task. Given task synthesis specification input (Figure Ic NEUR TASKSyN uses two components trained via reinforcement learning procedure: the first component generates possible solution codes, and the second component involves guiding an underlying symbolic execution engine that generates visual tasks for these codes. Our main results and contributions are summarized below: I. We formulate visual programmnng puzzle synthesis as a sequential decision-making process and propose NEURTASKSYN, a novel meuro-symbolic technique for synthesizing visual programming tasks (Section 3). II. We demonstrate the performance of NEURTASKSYN by comparing it to basclines from existing works (Section 4 III. We demonstrate the effectiveness of NEURTASKSYN through an extensive evaluation task specifications from real-world programming platforms (Section 5 TV. We publicly release the implementation and datasets to facilitate future research
1.2 Related work
Educational task generation. Earlier works task generation considered simpler domains such algebra problems where solutions follow well-defined procedures. These works employed classical methods such as template-based (Polozov et al. 2015
Singh et al. 2012) or exhaustive enumeration-based task gener- ation (Ahmed et al. 2020 Alvin et al. 2014p. We aim to synthesize programming task given well-structured specifications, similar to previous works on visual task synthesis (Ahmed et al. 2020 Ghosh et al.] 2022).
While the existing works focused on offline generation, we seek learn neural models that can generate lasks in real-time, as highlighted in Figure Recent works have also explored the use of LLMs to generate new assignments for Python programming (aasa et al. 2022 Phung et al. 2023b) with mixed results.
Spatial and logical reasoning for LLMs. Recent studies have focused on assessing the various capabilities
of LLMs (Bubeck et al. 2023 Arora et al. 2023 Bang et al. 2023 These works show that such state-of- the-art models have already achieved impressive generative capabilities for several programming education
scenarios, including program repair and hint generation (Sarsa et al. 2022 Leinonen et al. 2023). However, these models still lack crucial capabilities like program execution, symbolic reasoning, and planning that are needed for structured task generation in visual programming domains (Valmeekam et al. 2022 Huang
& Chang 2022 Kaddour et al. 2023 Phung et al.] 2023b). Based on (Huang et al.] 2023 the LLMs inherent capabilities alone are still insuficciet for many general reasoning tasks and require the guidance of an external tool or a human.
HitHub repository:
3

---

Published in Transactions on Machine Learning Research (01/2024)
2 Problem Setup
Visual programming tasks. We define a task a tuple T= (T1o, Toode), where Tro denotes the visual puzzle and Trode denotes additional constraints on solution code of this puzzle. This task space is general enough to encompass popular visual programming domains, including block-based programming domain of Hour of Code:Maze Challenge by Codc.org (HoCMaze) (Codc.org 2013b a and text-based programming domain of Karel (Patii et al., 1995). For instance, the lask in Figure lb is based on HoCMaze:M AZE20 task Code.org (2013a) it comprised of visual puzzle where a solution code, when executed, will take the avatar to the goal without crashing into walls. Additional constraints on a solution code specify that it should use only blocks from the set (move, turnLeft, turnRight, REPEATUNTIL, IFELSE} and have size < 7. We give a similar illustrative example for Karel in Section 5
;=
Solution codes of a task. We define the space of all possible codes C in a domain via a domain- specific language (DSL) (Gulwani et al. 2017). For instance, in our evaluation with HoCMaze and Karel programming domains, we will use their corresponding DST.s as introduced in (Bunel et al. 2018 Ahmed] et al.] 2020). For a given task T, a code C E C is a solution code if the following holds: successfully solves Tro while respecting Teode- For example, the codes in Figures Ib and [d use only blocks from the set {move, turnLeft, turnRight, REPEATUNTIL, IFELSE), have sizes equal to 7, and when executed, will take the avatar to the goal. Note that IFELSE is considered single block.
Task synthesis specification. We now introduce a notation to specily desired tasks for synthesis that exercise certain programming concepts in their solution codes and respect certain constraints on the visual puzzle. We define a task synthesis specification as a tuple == (tho, Psketch; 1/a), where vro is a partially initialized visual puzzle, t'sketch is a code sketch (i.e., partial code) capluring the structure that should be followed by the synthesized task's solution codes, and the specifies additional constraints on solution codes. For instance, the input task synthesis specification iith in Figure Ic is extracted from ree and aref in Figure 1b here, vig is 12x12 maze with certain cells initialized to free or wall cells; / specifies the structure and some already initialized conditionals, loops and actions that should be used in solution codes; 2 specifies constraints related to what kind of blocks can be used and the size of a solution code.
Synthesis objective. Given task synthesis specification si := (vio wiin ssketch: vi)) as input, we seek generate a task Tout == (Tio Toude) as output. Inspired by human-centered task quality criteria for the visual programming domains (Ahmed et al. 2020 Ghosh et al. 2022), we design objectives that capture the quality of desirable tasks. To formally set our synthesis objective and evaluation metrics, below we introduce different binary criteria (taking values 1 or 0) that we want Tout to satisfy w.r.t. shth
Va:Vidiiyty, A task Tout is valid (i.e., value 1) iff: (a) Tou respects vio (b) Tout respects (vi ( and (c) there exists at least one solution code C E C for Tout
O2:Concepts. A task Tout conceptually captures specification th (i.e., value 1) iff: (a) there exists at least one solution code C e C that respects vi sketthh and (b) all solution codes C E C are at least of the complexity required by viin ssketchh We define complexity w.r.t. the total number of programming constructs used (e.g,, REPEATUNTIL, WHILE, IF, IFELsE) and the level of code nesting, We refer to the level of nesting as code depth in the remaining content of the paper.
O3:Trace. A task Tout captures the following synthesis property: for any solution C for Tout that respects (vinetch vidr), the execution trace of on Tout executes each loop or conditional at least n times. This property is inspired by roal-world tasks that are casy to comprehend, as indicated by task quality criteria used in (Ahmed et al. 2020 Ghosh et al., 2022 we will use n 2 in Section 5 evaluation.
04:0verall This objective is only if all the above objectives (01, 02, 03) are satisfied for a task Tout,
O5:Human. This objective captures the quality of a task Tout from an expert's point of view. The assessed criteria are the conceptual correctness w.r.t. the input specification and the visual quality of the task. Based on these criteria, the expert reports an overall binary score.
4

---

Published in Transactions on Machine Learning Research (01/2024)
3 Our Synthesis Technique Neur yy
1/1
In this section, present NEURTASKSYN, neuro- symbolic technique to synthesize visual programming tasks (Tout) for an input specification (zbln).
sketth
Code Generator
Cour
Puzzle Generator
Tout
y in
1
Figure 2: Components of task synthesis.
3.1 Overview
As noted in Section 1 a key challenge in synthesizing tasks is that the mapping from the space of visual tasks to their solution codes is highly discontinuous - a small modification in the output task could make it invalid or semantically incorrect w.r.t. the input specification (Ahmed et al. 2020 One way to tackle this challenge is to first reason about & possible solution code and then generate visual puzzles based on execution traces
of this code (Gulwani. 2014 Kartal et al. 2016; Ahmed et al.) 2020 Tercan et al., 2023). This motivates two components in synthesis process shown in Figure 2 the first component generates possible solution codes C (akin to that of program synthesis (Gulwani et al. 2017)); the second component generates the visual puzzle for these codes via symbolic execution (akin to the idea of (est-case generation (King 1976) ).
After synthesizing both, we can get all the elements of Tout, Tio is based on the generated puzzle, T is extracted from the size and types of blocks of Cout Next, we discuss the components of
3.2 Generating the Solution Code Cout
The code generator component. (akes the elements of the specification; (W v)), that enforce constraints solution codes of the desired task and accordingly generates possible solution code gout, Below, we briefly describe a base symbolic engine to generate syntactically valid codes from specifications via random search and then neural model to guide this base engine; full details of this component are deferred to Appendix D.1
Base symbolic engine. The base engine operates on Abstract Syntax Tree representation of code sketches (i.e., partial codes). The engine generates codes by sampling tokens (i.e., action blocks, conditions, and iterators) from underlying DSL while respecting specification. Even though this ensures that a generated code is syntactically correct and valid w.r.t. specification, it could have semantic irregularities. Such irregularities can lead to confusing tasks (e.g., see Figure Sc. where the IF and ELSE bodies are the same).
Neural model. The neural model is trained to guide the sampling process of the base symbolic engine. This neural model is akin to a program synthesizer, but it has a different objective. It aims to synthesize codes that are semantically correct and can lead to high-quality tasks. One could use a varicty of architectures, for instance, transformer- custom-made encoder-decode approaches (Balog et al. 2017 Bunel et al. 2018 Yin & Neubig 2017). In
(Le et al. 2022: Fried el al. 2022 Li et. al. 2022 Wang al. 2021 ) or
our work, we use an LSTM-based decoder (Hochreiter & Schmichuber 1997) because of their extensive use in the existing literature on generating program solutions for input. visual programming task (Devlin)
ltt al. 2017 Bunel et al. 2018 Shin et al.
2019 Gupta et al. (0220). In our setting, the input corresponds to the code specification. Similar to (Bunel et al. 2018 we use an imitation (supervised) learning approach
to train the LSTM-based neural model, learning to predict in a boken-by-tolee manner.
3.3 Generating the Visual Puzzle Too
The puzzle generator component takes the element of the specification, vho that enforces constraints on the visual puzzle along with generated code gout and accordingly generates a visual puzzle Tip. We first describe base symbolic engine that performs symbolic execution of cout to generate semantically valid puzzle via random search and then describe neural model to guide this base engine. We then offer details regarding how we formulate the neurally guided symbolic engine as reinforcement learning (RL) agent.
Base symbolic engine. The base engine performs symbolic execution of cout on vio which has uninitialized This symbolic execution emulates an execution trace of cout and makes decisions about
2It. is possible that code gont generated during intermediate step solution for rous, e.g., when gout semantically incorrect and cannot generate a corresponding puzde. Tn this case, we set the size constraints Tout as specified by w
5

---

Published in Transactions on Machine Learning Research (01/2024)
del RUN
del R
del Rou()
Row()
R HEPEATURTAL (goal) ir gottt suzoRiggh
def RUN RereaTilrra 1 (pathiltt ght)) turuRight
REPSAT00TIL (
RePEATURiIL (goa1) (pacaRight) tarah
REPEATURTIL (goal))
REPEATÜNTIL (gos1D) Iripetaiigan LuzuRighh
1e (pataili g
Ir In(patkiggh)) Larch
CuraRaght
EL
ELSE! turmlett nove
ELaz(
Biae( turnlate sove
turnlatt
turalett nove
turnLefs
turnlets mave
aove
nove
Figure 3: Mustration of symbolic execution. In the first step, the execution of Cout starts on the partially initialized vio In the second step, the agent's location and orientation are set and execution continues to (UPAAUUNILL(gal)) which is decided to false in this particular example. This decision does not immedi- ately affect the visual grid. In the third step, the execution continues to IF (pathRight), which is decided to false and the avatar moves accordingly. The effect of these actions can be soen in the next state of the visual grid. In the fourth step, the execution continues to RepeatUNTIl, (ggaa)) which is decided to true, giving the goal location at step five. This leads to the sixth step, which the end of the execution. The remaining unknowns are replaced with walls.
unknowns resulting in concrete instantiation of To to Topt The outcome of these decisions affects the quality of the generated Tig.. Figure 3 shows an example of symbolic execution done by the symbolic engine. During this execution process, an emulator will replace unknowns with free cells, walls, the avatar position, and the goal location as indicated by the symbolic engine. The highlighted blocks of code in Figure 3 show the steps where the symbolic execution engine lakes decisions, leading to one possible path in the execution of cout and an instantiation of Too. A code could have a potentially unbounded number of possible execution traces, and randomly taking decisions would typically lead lower quality task (King) 1976 Ahmed al., 2020). Deciding the path of the exccution maps to a sequential decision-making process. We aim to guide this decision-making process to achieve execution traces that lead to higher-quality tasks.
Neural model. We train the neural model to guide the decision-making process of the base symbolic engine. Our neural architecture uses a CNN-based encoder for partial visual puzzles and combines with code execution-related features (e.g., coverage, currently executed code block). This choice based on previous works on program synthesis for visual programming tasks (Bunel et al.) 2018 Gupta et al. 2020 Other works have investigated the use of Monte Carlo Tree Search (MCTS) (Koesis & Szepesvári 2006 strategy to guide the symbolic execution for generating better puzzles with fewer resources (Kartal et al, 2016 Ahmed et al. 2020). However, these works used MCTS at inference time without any learned policy and could take several minutes to generate an output task for an input specification. Instead, a neural model makes use of learned experience to lead to high-quality puzzles.
Neurally guided symbolic engine as an RL agent. To speed up the generation process at inference, we train an RL agent (Sutton & Barto 2018) whose reward is defined via scoring function Fscore that captures the quality of the generated visual puzzle for input specification; this scoring function is similar in spirit to that used for MCTS in (Kartal et al. 2016 Ahmed et al.) 2020).. The agent's goal is to make decisions about the unknowns encountered when symbolically executing a code with the objective of generating high- quality puzzles. More concretely, we consider an episodic Markov Decision Process (MDP) defined as a tuple M = (S, A, P, R, So), where an episode corresponds to a full symbolic exccution of a code and the agent interacts with the environment over discrete time steps The elements of the MDP are defined as follows:
A state s E S is given by current status of visual puzzle and the block being executed (as in Figure 3
A set of state-depended actions A, can either be the set of initialization actions (i.e., {pos,, poss.!! 3), or set of binary decisions (i.e, (true, false));
6

---

Published in Transactions on Machine Learning Research (01/2024)
(1) state: Foodle
action: fill unknown
Environment
Agent
REPEATUNTIL (goaz)) IntporuRight) FuruRight
REPEATUSTL Ir 1r(patazigir) varDRiig
3 reward: 0 or Facare
ELsEi Caznleft
turalefs
aevo
(a) State at time
(b) Interaction at time
(c) State at time ++1
Figure 4: Illustration showing the interaction between the RL agent and the environment. (a) shows state at time 1, composed of code block being executed and status of the visual puzzle. (b) shows the interaction between the environment and the RL agent at time t. The environment comprises the code emulator and the scoring function. The RL agent is the neurally guided symbolic engine. (c) shows state at time / +
P:SxAxA + R denotes deterministic transition dynamics, P(s'ls, a) = for s' s@a, and 0 otherwise.
R x A + R denotes sparse reward. During the episode, the reward values are returned as 0; at the end of an episode, the reward values are computed using Fscore(Tou, )
So C S is the set of initial states. An initial state composed of vio and cout.
In order explain the interaction between the neurally guided symbolic engine and the emulator, we use a concrete example in Figure 4 Let consider that the current state at time t is composed of the block being execuled (i.e., IF(pathRight) interrogation) and the status of the visual puzzle (i.e., the avalar surrounded by unknowns). This is depicted in Figure 4a At this point, the neural model can guide the symbolic engine, as an interaction between the environment and the agent is expected (Figure 4b]. The agent receives the current state of the emulator (i.c., as in Figure 4a) and outputs an action, i.e., the decision on how to in the unknown. In our case, the decision is that there no path to the right. Then the environment computes reward in accordance with the action taken by using Fscore- After the decision is taken, the emulator continues executing the upcoming blocks (i.e., turnLeft, move, move) until reaching the next step where decision is needed (i.e,, REPEATUNTIL(gOa))), The state at time t is represented by the block being exccuted (i.c., REPEATUWTIL(goal)) and the new status of the visual puzzle, as depicted in Figure 4c The implementation details of the RL agent are provided in Appendix D.2
4 Training and Validation on Synthetic Specifications
In this section, train and validate NEURTASKSYN synthetic datasets of task specifications. We employ different variants of NEURTASKSYN to quantify the utility of individual components and evaluate w.r.t. scoring and runtime metrics. Importantly, the models obtained here through training on synthetic dataset will be used for evaluation on real-world specifications in Section
4.1 Evaluation Setup
Visual programming domains. We consider two popular visual programming domains: Hour of Code:Maze Challenge by Codc.org (HoCMaze) (Codc.org. 2013b a) and Karel (Pattis et al. 1995), as intro- duced in Sections [ and Both these programming domains have been studied ex extensively in the literature
on program/tass task synthesis (Bunel et al. 2018 Shin et al. 2019 Ahmed et al.) 2020 Gupta et al., 2020) and computing oducation (Picch et al.)
2015 Efremov et al. 2020 Ghosh et al. 2022). We define a few
domain-specific elements for these visual programming domains. First, introduced in Section
2 we use
two domain-specifie languages (DSLs) adapted from (Bunel al. 2018 Ahmed et al. 2020). Second,
7

---

Published in Transactions on Machine Learning Research (01/2024)
mentioned in Section 3 we will use domain-specific scoring functions FHoCMaaee and FKorel to capture qual- ity of visual programming lask. In our work, we adapt scoring functions used in (Ahmed et al. 2020). Full details are provided in the supplementary material; in a nutshell, these scoring functions are designed to intuitively capture the synthesis objectives set in Section 2 including properties like code coverage and trace quality. These scoring functions will be used in different ways: (a) during training of NEURTASKSYe puzzle generator as a reward for RL agent and during inference to select an output task from candidates; (b) when evaluating different techniques with surrogate metric based on these scoring functions; (c) when computing the quality of expert-designed code-tast tade-task pairs for the runtime experiments. For each domain, we e will make use of an offline, time-intensive, method TASKORACLF(C): it does one million symbolic executions of a given code C and returns highest-scoring task w.r.t. scoring function Fscore (cf. Footnote 3
Scoring-based metrics. We introduce a binary success metric M(Unn T c that is used to compare the performance of different techniques and to pick hyperparameters. More concretely, M(yhh, Tour, couu) ) is if the following hold: (i) the task T is valid w.r.t. " (ii) the generated code c is semantically correct in sense that it can lead to valid task via TASKORACLE, i.e., Fscore (TaskORaCle((ouI)) ) > λ1; (iii) the generated task Tout is good quality in comparison to the oracle-generater task, i.e., Fscore Cou)) > Co We use a = 0 and X = 0.9 in our experiments. For each technique,
cout)
X2 Fscore (TAsKORACLE((C) performance is computed as % success rate across the evaluation dataset w.r.t. M; in total, we compute performance across three seeds and report averaged results as mean (stderr). Importantly, we note that this metric only serves as a surrogate metric for evaluation on synthetic dataset; the neural models trained here will be evaluated on real-world task specifications w.r.t. the synthesis objectives in the next section.
Runtime metrics. We aim to measure the resources needed for technique to reach certain quality thresholds. We do this by first computing the score given by Fscore to an expert-designed task-code pair. Then, we fix the code and measure the time and number of symbolic execution rollouts needed to reach a given % of the computed score. We evaluate each technique multiple times and report averaged results.
4.2 Evaluation w.r.t. Scoring-baac based Metrics
Synthetic task specifications. For training and evaluation of techniques, we create dataset of syn- thetic task specifications per domain, referred to as ID == {zpin.. To create one specification Lbin == (16in
(Mistetch vin v2),, the most crucial part is getting a code sketch wishetch that respects the DSL and can lead to a valid code generation. We start by sampling a code cin from the DSL for a given structure, depth, and constructs this sampling process is inspired by methods for synthetic dataset creation (Bunel et al. 2018 Shin et al., 2019 Ahmed et al.) 2020). For each sampled code, we check its semantic validity, i.c., this code can lead to a high-quality task using TASKORACLE. Afterwards, for a sampled code cin we create its corresponding vin by keeping only the programming constructs (lops/condiitonals with a random subset of the booleans/ booleans/iterators /iterators masked out. The rest of the wi elements are instantiated as follows: vio is 16 x 16 size without any initialization, wi enforces the underlying DSL and a randomly initialized size between the number of blocks in diu and 17. In our evaluation, we split ID as follows: 80% for training the neural models (Iarain)) 10% for calibration (Deal), and a fixed 10% for evaluation (Deeet).
Techniques. First we describe NEURTASKSYN, our main task synthesis technique from Section 3 For each domain (HoCMaze and Karel), we train scparate instance of NEURTASKSYN using the synthetic dataset introduced above. In Section 3 we described the generation process for a single "rollout", i.e., one Cout and one puzzle Tool is generated. In practice, we use multiple rollouts to select a final output task Tout_ More concretely, at inference time for a given uitn as input, NEURTASKSYN generation process is captured by two parameters: number of code rollouts с by the code generator and number of puzzle rollouts p by the puzzle generator for each generated code. We denote these hyperparameters in subscript, e.g., NEUR TASKSYNe:S.p.I for 5 x 10 rollouts. Out of these X p candidates, the technique outputs one task Tout along with solution code Cout using its scoring function. Next, we describe different variants of NEURTASKSSN.. and baselines:
This technique is a variant of NEURTASKSSNN. to evaluate its puzzle generation component, assuming the code generator has access to code cin associated with specification ii in the dataset. At inference, NEURPUZZLEGNNePxp generation process is captured by hyperparameter p. i.e., number of puzzle rollouts. Out of p candidates, technique outputs one task, analogous to NRURTASKSSN.
NEUR.PZZZLEGENerxxp
8

---

Published in Transactions on Machine Learning Research (01/2024)
Metric
Rollouts
Runtime
ALL RASITSYN:ATI
HADD BASITSYNHARD
NEUMPORNIALL
NEURPGeN Haxu BASIPCin HaRn
RAS
Quality
Quality
Technigue:Data
90%
95%
99%
99%
NEIRPCENsAll
30
Performance
Performance
NEunPGex:Haard
15
46
160
11.08a
60-
60-
BAsEPGEN:Ali
91
2502
69105
1977 44s
BAsEPGENaHard
437
17122
405231
11800.11s
MCTS:AI
MCTS:ard
283
6841
10116
88.25s
10
20
30
40
10
20
30
40
50
60
70
90
100
Number of rallouts
Number rollouts
(a) BASETASKSYN, NEURTASKSYN
(b) BASEPUZMEGRN, NEURPUZZLEGEN
(c) Results for runtime evaluation.
Figure 5: (a) Results for BASETASKKYN and NEURTASKSYN.. by increasing code rollouts from 1 to and NEURPUZZLEGGNN.o. by increasing puzzle rollouts p from to 100. (c) Table showing the runtime/rollouts comparison between different techniques, on tasks of different difficulty, when varying the required quality threshold. The quality threshold is expressed as % of the quality score of an expert-designed task. See further details in Section
5 with fixed puzzle rollouts
10. (b) Results for BASEPUZZLEEENN..
BASETASKSYNep and BASEPUZZLEGENerRxpp These techniques operate similar to NEURTASKSYN.. and NEuRPUZZLEGRName but use only symbolic engine with random search
Results. and 5b report results as we vary the number of rollouts for different techniques, evaluated on the full dataset and on a "hard" segment of the dataset, where sketthh uses at least 2 constructs and has depth of 3. In summary, these results demonstrate the utility of different components of NRURTASKSYN and how the synthesis quality improves we increase the number of rollouts.
winn
4.3 Evaluation w.r.t. Runtime Metrics
Code samples for puzzle generation. For evaluating the runtime our technique, we pick a set of codes designed by experts as solutions for six representative tasks from both the HoCMaze and Karel domains. We select those tasks that common among our evaluation in Section (see Figure 6 and the work of (Ahmed) et al. 2013b), and Karel:OurFing Karel:Diagonal (CodeHSS) 2012b).
2020 These tasks are derived from HoC:Maze8, HoC:Maze9, HoC:Mazel3, HoC:Maze18 (Code.org.
Techniques. We focus on evaluating the runtime performance of three techniques. NEURPUZZIEGEN and BAsePtzZHLGGEEEPDD are equivalent to the techniques of Section 4.2 MCTS is the puzzle
generation method based on Monte Carlo tree search (MCTS) (Ahnedd et al. 2020), introduced in Section 3.3. More specifically, we do not set a fixed number of puzzle rollouts p, but we measure the values of p needed to reach certain quality thresholds.
Results. We present our results in Figure 5c averaged over all the selected tasks. Additionally, we define an expert code as "hard" when using at least 2 constructs and having a depth of 3. We separately report the results on HoC:Mazel8, which is considered hard. It can be noticed that the unguided symbolic execu- tion of BASEPUZZLEGEN leads to large exccution times when aiming to synthesize high-quality tasks. MCTS has faster runlimes than BAS:PUuzinGRNNe.n but it becomes less scalable when required to come up with high-quality tasks for the hard code. NEURPUZZLEGEN maintains low execution times and number of rollouts for any of the required quality thresholds, even when faced with hard code.
5 Experiments on Real-World Specifications
In this section, we evaluate our task synthesis technique NEURTASKSYN on real-world specifications.
(AAKOORCCEECC) introduced ahove BAsePuzzieGen with p= 10 rollouts for fixed code

---

Published in Transactions on Machine Learning Research (01/2024)
ginn
Wketch structure
(depth; constructs)
V16
Source
v00
{RUN [REPEAT))
(2, 1)
16x16 empply
HoCMaze, blocks 10
HoC:Maze9
Code.org
2013b
11
{RuM [RSPEATUNTIL]]
[2, 1)
16x16 emply
HoCMaze, blocks $ 10
HoC:Mazel
Code.org
2013b
1/2
{RUM (REPEAT; REPEAT)]
[2, 2)
16x16 emply
HoCMaze, blocks $ 10
HoC:Maze8
Code.org
2013b
13
RUM [REPEATUNIII,(TPELSEE))
2)
16x16 empty
HoCMaze, blocks $ 10
HoC:Mazel5
Code.org
2013b
14
RUM (I: If)))
(3,3) 16x16 empty
HoCMaze, blocks 10
HoC:Mazee0
Code.org
20 1.
15
{Run}
(1,0)
16x16 empty
Karel, blocks - 10
Karel:Our
HS
2012b
86
RuuM (WHTLE})
12, 16x16 empty
Karel, blocks _ 10
Karel:Diagonal
CodeHS
201
97
{Rum (WHILE; WHILE))
(2,2) 16x16 empty
Karel, blocks - 10
Kavel:RowBack
CodeHS
2012h
88
[RuM (I+r)
(3,2) 16x16 empty
Karel, blocks < 10
Karel:Stairway CodeHS
2012b
69
Ruu (REPET)())
(3,2) 16x16 empty
Karel, blocks - 10
Karel:CleanAAl
Real-world task specifications for HoCMaze and Karel; sketth is shortened for brevity; 2/ indicated as booleans and actions allowed by each domain, with the addition of maximum size.
Figure 6:
Real-world task specifications. We use set of 10 task specifications from HoCMaze and Karel domains, shown in Figure G These task specifications are inspired by their source tasks (see "Source" column) in the following sense: we create a specification wit for which the corresponding source task is a desired task as would be created by experts. Figure g shows illustration of task synthesis for a variant of 4/ (source as MAZE18 HoCMaze task) where we used 12x12 grid size with certain cells pre-initialized; analogously, Figure g shows illustration of task synthesis for variant of 48 (source as STAIRWAY Karel task) where we used 12x12 grid size.
Synthesis quality metrics. We evaluate techniques w.r.t. different metrics, each corresponding to a synthesis objective introduced in Section 2 Even though objectives 01 04 are quantitative, it is challenging to fully automate their ovaluation because it requires analyzing propertics of different possible solution codes of a generated lask. We manually did this evaluation when computing performance for each technique and metric. To capture objective 05, we assess the quality of synthesized tasks using human experts' annotations. Each expert independently evaluated all specifications and all techniques. Additionally, we report a binary metric of whether cout solves Tout to provide insight into the robustness of the synthesis process. Results are reported as mcan over 10 specifications with from Figure i we evaluate over three seeds and report averaged results as mean (stderr). In total, three experts (i.e., one per seed) with experience in visual programming provided annotations for 05.
Techniques. We evaluate NEURTAAKKSNN::Ipp with c = 10 and p = 100, i.c., total of c xx] xxp = 1000 rollouts (see Scction 4.. Next, we describe additional techniques evaluated:
BASETTASKSYN:I0pp.u operates similarly to A but uses only base symbolic engine with random scarch without any neural guidance (sec Section
GPTTTASKSSN-conees is based on OpenAl's GPT-4 OpenAl 2023b). It uses conversation-style prompts that involved human guidance to correct mistakes. More concretely, it is based on a two-stage process as shown in Figure 2 we first ask GPTT4 to generate a code Cout for ritn and then ask it to generate a puzzle Too that could be solved by Cout, The first stage comprised 5 separate queries to generate a cout, each query started with an initial prompt and then follow-up prompts to fix any mistakes. The second stage comprised of another separate queries to generate a puzzle Typt: each query started with an initial prompt and then follow-up prompts to fix any mistakes. Once we get cout and TiO, we set Tout for NEURTASKKYN. We defer the prompts to the supplementary material. This variant of GPT4TASKSYN was used to synthesize the tasks in Figures S and g
GPT uses the same two-stage synthesis process, but employs few-shot examples with- out any follow-up conversations.
EXPERT refers to expert-designed tasks. In our setup, EXPERT simply outputs a task Tout based on the source task associated with input specification sin; moreover it appropriately adjusts Tio to match wiin layout and sets Tout as allowed by (winn
Sketch (/l0) and the size of the minimal solution code.
10

---

Published in Transactions on Machine Learning Research (01/2024)
Technique
O1:Validity
O2:Concepts
03:Trace
04:Overall
05:Iluman
gewe solves Tout
1.00 (0.00)
0.83 (0.04)
0.80 (0.00)
0.80 (0.00)
0.77 (0.11)
1.00 (0.00)
0.97 (0.04)
0.37 (0.08)
0.33 (0.04)
0.33 (0.04)
0.20 (0.07)
0.50 (0.12)
GPT#TAsKSSY--ooeerrs
0.97 (0.04)
0.57 (0.11)
0.60 (0.07)
0.43 (0.11)
0.27 (0.08)
0.33 (0.08)
GPT4TAsKSYX-foweho
EXPERT 0.80 (0.07)
0.37 (0.11)
0.57 (0.11)
0.33 (0.08)
0.13 (0.11)
0.27 (0.04)
1.00
1.00
1.00
1.00
1.00
1.00
Figure 7: Results on real-world task specifications for HoCMaze and Karel in Figure see Section this figure, EXPERT refers to expert-designed tasks.
Tn
def ( blocks
blocks is body of basic action blocks from the set (move, turnleft, turnRight)
RapearUurra_gaa1)) blocke { a blocks
is boolean condition from (pathAhead, pathLeft, pathRight)
ÉLaE( a blocks
blocks
Number of blockss should be $
(a) Task synthesis specification wit, with vio (left), wi
Uakethh (middle) and vin (right).
def R REDEATUNSIL burnleft move
def (U( { burnleft turnleft
def RuN()
Ru
Rep KEPEATUNT (goal){
Repzavtiirrs (goat)
REPEA (gr In (pathRight)) nove
turallight
IP (patbeed
nove
Lse
curaLeft
turalaft.
move
BLaE nove
vovR
nove
(b) Tio cout by GPTNTASKSYN (c) Tio cout by BASETASKSYn (d) Tiot, cour by NEARTASKSYN (e) Tout Cous by EXPERT
Figure 8: Illustrative example showcasing task synthesis inspired by the MAZE18 HoCMaze
task Code.org (2013b a) The given specification seeks to synthesize tasks where a solution code has structure.
(a) Task synthesis specification 2itn == (sitg t with) is provided as input: wio is a 12x12 maze with certain cells initialized to free (white) or wall (gray) cells, the rest being marked as unknowns (brown); viin along with vi specify constraints on code solutions of a synthesized task. (b-d) show tasks TouE and codes coutt used as intermediate step to generate output tasks by three techniques. (e) shows task Tout and code gout based on MAZE18. See Section
the (PPPATUUNTIL(EEELE]
Results. Figure 7 reports evaluation results for different techniques w.r.t. our task synthesis objectives. Next, we summarize some of our key findings. First, NEURTASKSYN has high performance of at least 0.77 across all metrics. The illustrative examples in Figures g sized by NEURTASKSYN, matching interesting characteristics of real-world tasks from EXPERT. Second, BASETASKKYN, GPT4TASKSYN-comees
and g showcase the high-quality of tasks synthe-
and TOPTTTAsKSYN-fusshhe struggle on objectives 02 and O3. Their low performance can be explained, in part, by failure to generate a valid task/code pair. The illus- trative examples in Figures 8 and g further highlight the issues of tasks generated by these techniques. For instance, BASETASKSYN'' Tout in Figure Sc can be solved by a simpler code with lower depth than specified in the input specification; CPPTTAASKYNN-CONUS converseess Tout in Figures {bb) Ind are not solvable by codes that would match the input specification. UPTT4AsKSYN-feusst does not help with increasing the performance. In summary, these results demonstrate the effectiveness of NAURTASKS y in synthesizing high-quality visual programming tasks for real-world specifications and some
shows that changing the prompting strategy
11

---

Published in Transactions on Machine Learning Research (01/2024)
def RuN(){ a blocks ( blocks
blacks is a body of hasic action blocks from the aet fuove, turaleft, turnRight, pickMarker, putMarker)
[b(b)
blocke
b a booltan condition from (pathaheed, pathleit, pathRight, no-pathAhead, markerPrasent, no to-markerPresent)
blocks
}
blocks
Number blocks should S 10
(a) Task synthesis specification w with vi8 (left), Valettc (middlee) and v/ (right).
Bun def Rune()
def Bux()
(
WHI ( Te (e(narkerSreeent)
VATLE VA (uo-pacheeeadd) I7 (pachiigghc)
VILLE (pethibead) pá (patbileef))
picktaareer
plckkaa
pickfarker
patMarkor
turnLeft
turaRight
bove
pove
turalaft
ght
EarnRight
nove
bankkarker
Bove
(b) mostt cou by GPTNTASKSYN (c) Tio Cout by BAsETAsKSYn (d) Tio Cout by NEURTASKSYN
(e) TiO Cous by EXPERE
Figure 9: Illustrative example showcasing task synthesis inspired by the STAIRWAY Karel task Pattis et al. (995 CodeHS (2012b/a). This specification soeks synthesize tasks where a solution code has the 4/in [WHILE [F]] structure. (a) Task synthesis specification stdn (vio Vsketcho v/an) is provided input: wio is pregrid-postgrid pair with unitialized grid of size 12x12 yiin Vakkechh along with 1/ specify constraints code solutions of synthesized task. (b d) show tasks Tout and codes cout used intermediate step to generate output tasks by three techniques. (e) shows task Tout and code Cout based on STAIRWAY. See Section
of the challenges in synthesizing visual programming tasks by state-of-the-art neural generative models as the synthesis process requires logical, spatial, and programming skills.
6 Concluding Discussions
We developed novel neuro-symbolic technique, NEURTASKSYN, that can synthesize visual programming tasks for given specification. We demonstrated both the efficiency and effectiveness of TASKSSn through extensive evaluation synthetically generated and reference tasks picked from popular visual programming environments. We believe our proposed technique has the potential to enhance introductory programming education by synthesizing personalized content. Morcover, we showcase the challenges that purely neural generative models and purely symbolic models face. BASETASKSYN, a purely symbolic model, codes and low-quality tasks. On the other hand, purely generative
can lead to semantic irregularities techniques based on GPT-4 struggle to generate high-quality puzzles. This result aligns with findings contemporary studies that GPT-4 may face challenges in code execution, symbolic operations, test-case generation, and task synthesis (Bubeck et al. 2023 Phing et al. 2023b).
12

---

Published in Transactions on Machine Learning Research (01/2024)
There many interesting directions for future work. First, have built our LSTM/CNN-based archi- tecture specialized for task synthesis objectives; it would be interesting to fine-tune models like GPT-4 to improve its capabilities for synthesizing visual programming tasks. Moreover, we can analyze the logical and spatial abilities of these finc-tuned models by curating benchmarks visual programming domains. Sec- ond, our methodology focused on visual programming:; would be interesting to develop generative models for synthesizing tasks other programming domains, such as synthesizing Python problems that match a certain input-output configuration and other specifications regarding the possible solution codes. Third, our evaluation study considered various objectives capturing human-centteed aspects along with expert annota- tions; in the future, it would also be useful to conduct studies with human learners to evaluate the quality in terms of perceived difficulty or interpretability of synthesized tasks.
Acknowledgements
(unded/Coffunded by the European Union (ERC, TOPS, 101039090). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.
References
Umair Z. Ahmed, Sumit Gulwani, and Amey Karkare. Automatically Generating Problems and Solutions for Natural deduction. In IJCAI, 2013.
Umair Z. Ahmed, Maria Christakis, Aleksandr Efremov, Nigel Fernandez, Ahana Ghosh, Abhik Roychoud- hury, and Adish Singla. Synthesizing Tasks for Block-based Programming. In NeurIPS, 2020.
Chris Alvin, Sunit Gulwani, Rupak Majumdar, and Supratik Mukhopadhyay. Synthesis of Geometry Proof Problems. In AAAI, 2014.
Daman Arora, Himanshu Gaurav Singh, and Mausam. Have LLMs Advanced Enough? A Challenging Problem Solving Benchmark For Large Language Models. CoRR, abs/2305.15074, 2023.
David Baidoo- and Leticia Owusu Ansah. Education in the Era of Generative Artificial Intelligence (AI): Understanding the Potential Benefits of ChatGPT in Promoting Teaching and Learning. Available al SSRN 4337484, 2023.
Matej Balog, Alexander L. Gaunt, Mare Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. DeepCoder:
Learning to Write Programs. In ICLR, 2017.
Yejin Bang, Samuel Cahyawijaya, Nayeon Lee, Wenliang Dai, Dan Su, Bryan Wilie, Holy Lovenia, Ziwei Ji, Tiezheng Yu, Willy Chung, Quyet V. Do, Yan Xu, and Pascale Fung. A Multitask, Multilingual, Multimodal Evaluation of Chatgpt on Reasoning, Hallucination, and Interactivity. CoRR, abs/2302-04023, 2023.
Jean-Pierre Briot, Gaëtan Hadjeres, and François-Dare David Pachet. Deep Learning Techniques for Music Gen- eration. Springer, 2020.
Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott M. Lundberg, Harsha Nori, Hamid Palangi, Marco Tílio Ribeiro, and Yi Zhang, Sparks of Artificial General Intelligence: Early Experiments with GPT-4. CoRR, abs/2303.1 12712, 2023.
Grammar and Reinforcement Learning for Neural Program Synthesis. In ICLR, 2018. Rudy Bunel, Matthew J. Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Leveraging
Mark Chen et al. Evaluating Large Language Models Trained on Code. CoRR, abs/2107-033774, 2021.
CodeHS. CodeHS.com: Teaching Coding and Computer Science. https://codehs.cmm 2012a.
13

---

Published in Transactions on Machine Learning Research (01/2024)
CodeHS. Intro to Programming with Karel the http:///w.ooooooccco/////////aaa 2012b.
Code.org. Code.org: Learn Computer Science. httpa://cooe..rg/ 2013a.
Code.org, Hour of Code: Classic Maze Challenge.
2013b.
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. RobustFill: Neural Program Learning under Noisy I/O. In ICML, 2017.
Hao-Wen Dong, Wen-Yi Yi Hsiao, Li-Chia Yang, and Yi-Hsuan Yang. Musegan: Multi-track Sequential Gen- erative Adversarial wetwsrks for Symbolic Music Generation and Accompaniment. In AAAI, 2018.
Aleksandr Efremov, Ahana Ghosh, and Adish Singla. Zero-shot Learning of Hint Policy via Reinforcement
Learning and Program Synthesis. In EDM, 2020.
Zhangyin Feng, Daya Guo, Duyu Tang, Nan Duan, Xiaocheng Feng, Ming Gong, Linjun Shou, Bing Qin, Ting Liu, Daxin Jiang, and Ming Zhou. Codebert: A Pre-Trained Model for Programming and Natural Languages. In EMNLP, 2020.
James Finnie-Ansley Paul Denny, Brett A. Becker, Andrew Luxton-Reilly, and James Prather. The Robots Are Coming: Exploring the Implications of OpenAl Codex on Introductory Programming. In ACE, 2022.
Daniel Fried, Armen Aghajanyan, Jessy Lin, Sida Wang, Eric Wallace, Freda Shi, Ruiqi Zhong, Wen-tau Yih, Luke Zettlemooee,, and Mike Lewis. Incoder: Generative model for Code Infilling and Synthesis. CoRR, abs/2204.05999, 2022.
Wenhao Gao and Connor W Coley. The Synthesizability of Molecules Proposed by Generative Models. Journal of Chemical Information and Modeling, 60(12):5714-5728, 2020.
Ahana Ghosh, Sebastian Tschiatschek, Sam Devlin, and Adish Singla. Adaptive Scaffolding in Block-Basod Programming via Synthesizing New Tasks as Pop Quizzes. In ATED, 2022.
Sumit Gulwani. Example-based Learning in Computer-aided STEM Education. Communications of the ACM, 57()))70-8) 80, 2014.
Sumit Gulwani, Oleksandr Polozov, Rishabh Singh, et al. Program Synthesis. Foundations and Trends3 in Programming Languages, 2017.
Kavi Gupta, Peter Ebert Christensen, Xinyun Chen, and Dawn Song. Synthesize, Execute and Debug: Learning to Repair for Neural Program Synthesis. In NeurIPS, 2020.
Sepp Hochreiter and Jürgen Schmidhuber. Long Short- Term Memory. Neural Computation, 9, 1997.
Jie Huang and Kevin Chen-Chuse Chang. Towards Reasoning in Large Language Models: A Survey. CoRR, abs/2222-10003. 2022.
Jie Huang, Xinyun Chen, Swaroop Mishra, Huaixiu Steven Zheng, Adams Wei Yu, Xinying Song, and Denny Zhou. Large Language Models Cannot
Reasoning Yet. CoRR, abs/2310.01198, 2023.
Jean Kaddour, Joshua Harris, Maximilian Mozes, Herbie Bradley, Roberta Raileanu, and Robert McHardy, Challenges and Applications of Large Language Models. CoRR, abs abs/2307.10169, 2023.
Bilal Kartal, Nick Sohre, and Stephen J. Guy. Data Driven Sokoban Puzzle Generation with Monte Carlo Tree Search. In AIDE, 2016.
James C. King. Symbolic Execution and Program Testing, Communications of ACM, 19(7):385 3944 1976.
Levente Kocsis and Csaba Szepesvári. Bandit based Monte-Carlo Planning, In ECML, 2006.
Hung Le, Yue Wang, Akhilesh Deepak Gotmare, Silvio Savarese, and Steven Chu-Hong Hoi. Coderl: Mas- tering Code Generation through Pretrained Models and Deep Reinforcement Learning. In NeurIPS, 2022.
14

---

Published in Transactions on Machine Learning Research (01/2024)
Juho Leinonen, Arto Hellas, Sami Sarsa, Brent N. Reeves, Paul Denny, James Prather, and Brett A. Becker. Using Large Language Models to Enhance Programming Error Messages. In STGCSE, 2023.
Yujia Li al. Competition-Level Code Generation with Alphacode. CoRR, abs/2203.07814 2022.
Weng Mare Lim, Asanka Gunasekara, Jessica Leigh Pallant, Jason Ian Pallant, and Ekaterina Pechenkina. Generative AT and the Future of Education: Ragnarök or Reformation? A Paradoxical Perspective from Management Educators. The International Journal of Management Education, 21(2):100790, 2023.
OpenAL. ChatGPT. https://openad:: http:::/pppaat..co/////g/caaaaa 2023a.
OpenAL GPT-4 Technical Report. CoRR, abs/2303.08774, 2023b.
Richard E Pattis, Jim Roberts, and Mark Stehlik. Karel the Robot: A Gentle Introduction to the Art of Progrumming. John Wiley Sons, Inc., 1995.
Tung Phung, José Cambronero, Sumit Gulwani, Tobias Kohn, Rupak Majumdar, Adish Singla, and Gustavo Soares. Generating high-precision feedback for programming syntax errors using large language models. EDM, 2023a.
Tung Phung, Victor-Alexante Padurean, José Cambronero, Sumit Gulwani, Tobias Kohn, Rupak Ma- jumdar, Adish Singla, and Gustavo Soares. Generative AI for Programming Education: Benchmarking Chatgpt, Gpt-4, and Human Tutors. In ICER V.2, 2023b.
Chris Piech, Mchran Sahami, Jonathan Huang, and Leonidas J. Guibas. Autonomously Generating Hints by Inferring Problem Solving Policies. In L@S, 2015.
Oleksandr Polozov, Eleanor O'Rourke, Adam M. Smith, Luke Zettlemoyer, Sumit Gulwani, and Zoran Popovic. Personalized Mathematical Word Problem Generation. In IJCAT, 2015.
Thomas W. Price and Tiffany Barnes. Position Paper: Block-Based Programming Should Offer Intelligent Support for Learners. IEEE Blocks and Beyond Workshop, 2017.
Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsca Voss, Alec Radford, Mark Chen, and Ilya Sutskever. Zero-Shot Texl-lo-Image Generation. In ICML, 2021.
Mitchel Resnick, John H. Maloney, Andrés
Natalic Rusk, Evelyn Eastmond, Karen Bremnan, Amon Millner, Eric Rosenbaum, Jay S. Silver, Brian Silverman, and Yasmin B. Kafai. Scratch: Programming for All. Communications of ACM, 52(11):60 67, 2009.
Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. High-Resolution Image Synthesis with Latent Diffusion Models. In CVPR, 2022.
Sami Sarsa, Paul Denny, Arto Hellas, and Juho Leinonen. Automatic Generation of Programming Exerciscs and Code Explanations Using Large Language Models. In ICER, 2022.
Petra Schneider, W Patrick Walters, Alleyn T Plowright, Norman Sieroka, Jennifer Listgarten, Robert A Goodnow Jr, Jasmin Fisher, Johanna M Jansen, José Duca, Thomas Rush, et al. Rethinking Drug Design in the Artificial Intelligence Era. Nature Reviews Drug Discovery, 19(5):353 364, 2020.
Richard Shin, Neel Kant, Kavi Gupta, Chris Bender, Brandon Trabucco, Rishabh Singh, and Dawn Song. Synthetic Datasets for Neural Program Synthesis. In ICLR, 2019.
Rohit Singh, Sumit Gulwani, and Sriram K. Rajamani. Automatically Generating Algebra Problems. In AAAI, 2012.
Minhyang Suh, Emily Youngblom, Michael Terry, and Carrie Cai. AI as Social Glue: Uncovering the Roles of Deep Generative AI during Social Music Composition. In CHI, 2021.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT press, 2018.
15

---

Published in Transactions on Machine Learning Research (01/2024)
Tamara Tate, Shayan Doroudi, Daniel Ritchie, and Ying Xu. Educational Research and AI-Generated
Writing: Confronting the Coming Tsunami. 2023.
Alperen Tercan, Ahana Ghosh, Hasan Ferit Eniser, Maria Christakis, and Adish Singla. Synthesizing a
Progression of Subtasks for Block-Based Visual Programming Tasks. CoRR, abs/2305.17518, 2023.
Xiaochu Tong, Xiaohong Liu, Xiaoqin Tan, Xutong Li, Jiaxin Jiang, Zhaoping Xiong, Tingyang Xu, Hualiang Jiang, Nan Qiao, and Mingyue Zheng. Generative Models for Novo Drug Design. Journal of Medicinal Chemistry, 441194774011114027, 2021.
Karthik Valmeekam, Alberto Olmo Hernandez, Sarath Sreedharan, and Subbarao Kambhampati. Large Language Models Still Can't Plan (A Benchmark for LLMs on Planning and Reasoning about. Change). CoRR, abs/2206-10498 2022.
W. Walters and Mark Murcko. Assessing the Impact of Generative AT on Medicinal Chemistry. Nature Biotechnology, 38(2):143 145, 2020.
Yue Wang, Weishi Wang, Shafiq R. Joty, and Steven C. H. Hoi. CodeT5: Identifier-aware Unified Pre-trained Encoder-Decoder Models for Code Understanding and Generation. In EMNLP, 2021.
Mike Wu, Milan Mosse, Noah D. Goodman, and Chris Piech. Zero Shot Learning for Code Education:
Rubric Sampling with Deep Learning Inference. In AAAI, 2019.
Pengeheng Yin and Graham Neubig. A Syntactic Neural Model for General-Purposc Code Generation. In ACL, 2017.
Rui Zhi, Thomas W. Price, Samiha Marwan, Alexandra Milliken, Tiffany Barnes, and Min Chi. Exploring the Impact of Worked Examples in Novice Programming Environment. In SIGCSE, 2019.
16

---

Published in Transactions on Machine Learning Research (01/2024)
A Table of Contents
In this section, we provide brief description of the content provided in the appendices of the paper.
Appendix B provides discussion of the broader impact of our work and compute resources used.
presents the details about the generation of the illustrative examples from Figures and and shows their relationship with metrics O1-O4 described in Scction
Appendix C
Appendix D gives more insights into the architecture described in Section
Appendix provides additional details about results, the scoring functions, the synthetic dataset creation process, and the training process Scction 4
Appendix provides the source task/code pairs used for creating the real-world task specifications in also provides more insights into the interaction with GPT-4.
Section 5
B Discussion
Broader impact. This paper develops new techniques which have the potent ial of being used for improving pedagogy in visual programming environments. On the existing platforms, content is hand-curated by tutors, offering limited resources for students to practice on. We aim to tackle this challenge by syuthesizing novel practice tasks that match desired level of difficulty with regard exercised content for a student. We believe proposed technique has the potential to drastically enhance introductory programming education by synthesizing personalized content for students.
Compute resources. All the experiments were conducted on cluster of machines equipped with Intel Xeon Gold 6142 CPUs running at frequency of 2.60GHZ.
17

---

Published in Transactions on Machine Learning Research (01/2024)
C Illustrative Examples: Details
In this section, we discuss the details regarding the generation and scoring for cach of the techniques' output in Figure for HoCMaze and Figure 9 for Karel.
C.1 Example for HoCMaze in Figure 8
We present Tout, along with Cout for each of the techniques with w/th input in Figure 11 this ligure expands on Figure ( with additional details. We give additional explanations regarding how each of the techniques' output respects or not metrics O1-03 (see Sections and 5 in Figure 10
for GPT4TaskSyn in Figure When querying GPT-4 for this example, we set wio as an empty 8x8 grid. We then expand the generated grid a 12x12 grid and manually integrate the pattern seen in Figure Iaa to match the specification. We discuss the results obtained by GPT4TAsKSYN-conoesss
ceoneration/ddjustmeen
Ceneration/addjstmenni for BaseTaskSyn and NeurTaskSyn in Figure g The neural model for puzzle generation is trained on 16x16 grids, yet the symbolic engine can support the existence of pre- initialized grids. Thus, we mask the upper-left part of the grid (4 rows and 4 columns), obtaining the 12x12 workspace for the technique. On top that, on the remaining 12x12 grid, we pre-initialize the pattern seen in Figure 11a (i.c., lower-left and upper-right bounded squares).
iiverration/djusstten for Expert in Figure & The output of EXPERT represents manual adaptation of the HoC:Maze18 task to expand it to 12x12 grid and to integrate the pattern seen in in Figure Sa
Technique
O1:Valldity
O2:Concepts
03:Trace 04:0verall
cour solves Toat
GPT4TAsKSYN
1
0
0
BASETASKKYN
1
0
0
0
NEURTASKKYN
1
1
1
1
1
EXPERT
1
1
1
Figure 10: Scores showing whether the output Tout for sstn cach technique respects the four metrics O1-04, with the additional cout solves Tout metric, for this HoCMaze example.
We provide explanations for each entry for the objectives 01-03 in Figure 10
GPT4TAsKSYN for Objective 02: The only possible solution code C has depth and uses constructs (nested IFELSE needed), i.e. viin is respected, hence 02 is
GPT4TASKSYN for Objective 03: There is no solution C that respects valn sketch hence O3 is 0 by definition.
GPT4TASKSYN for cout solves Tout, cout when executed Tio, makes the avatar crash into wall, hence Cout is not solution for Tout
BASETASKSYN for Objective O2: The IFELSE block employed by cout is not required. This implies that there solution code C which has a lower complexity, i.e., smaller depth and less constructs than required by vin sskethh> hence 02 0.
BASETASKKYN for Objective O3: As the employed IFELSE block not required, is possible to design a solution code that uses IFELSE with different. conditional (e-g., IF(pathLeft))et ELLSE) for which the body would never be executed, hence 03 is 0.
18

---

Published in Transactions on Machine Learning Research (01/2024)
Rux(){
blocks body of basic action blocks from the set (move, turnLeft, turnRight)
RepeArUwerI(ggaDD a blocks
{
blacks
}
boolean condition from (pathAbead, pathLeft, pathRight)
ELsE(
blocks
blocks
Number of blocks should be 7
(a) Task synthesis specification s5
def RuN REPEATUNPIL (goal) IF (pathLeft) turnLeft
Allowed blocks: {move, turnLeft, turnRight, REPEATUNTIL, IFELSE)
ELSE( move
Maximum size:
(b) Tous by GPTTTASKSYN
(c) Cout by GPT4TASKSYN
def RUN { turnLeft turnleff
Allowed blocks: {move, turnLeft, turnRight, REPEATUNTIL, IPELSE)
REPEATURTIL (goal)
(pathhiigh)))
ELse( move
Maximum size:
(d) Tout by BASE
(e) cout by BASETASKSYN
def RuN
REPEATURTIL (goal)
Allowed blocks: {move, turnLeft, turnRight, REFEATUNTIL, IFELsE}
IF (pathRight) turnRight
ELse(
turnLeft
move
}
Maximum size:
nove
(I) Tout by NEuRTASKSVV
(H) gout by TARRSSS
def Rux
REPEATUNTIL (goal)) Is (patháhead)) move
Allowed blocks: {move,
turnLeft, turnRight, REPEATUNTIL, IPELSE)
ELSE(
turnleft
Maximum size:
(h) rout by EXPERT
ii) cour by EXPERT
Figure 11: Illustration containing the tuple Tout for each technique, along with cout, for this HoCMaze example.
19

---

Published in Transactions on Machine Learning Research (01/2024)
C.2 Example for Karel in Figure
We present Towt, along with ceut for each of the techniques with w/th input in Figure 13
this ligure expands
on Figure | with additional details. We give additional explanations regarding how each of the techniques' output respects or not metrics O1-03 (see Sections and 5 in Figure 12
for GPT4TaskSyn in Figure For this example, we set vio as an emply 12x12 grid and query GPT-4. We discuss the results obtained by GPT4TAsKSYN-cnne
Ceneration/adjustiie
aadjuttmennn for BaseTaskSyn and NeurTaskSyn in Figure g The neural model for puzzle generation is trained on 16x16 grids, yet. the symbolic engine can support the existence of pre-initialized grids. Thus, we mask the upper-left part of the grid (4 rows and columns), obtaining the 12x12 workspace for the technique.
Generation/adjustment for Expert in Figure the Karcl:Stairway task.
The output EXPERT for this example based on
Technique
O1:Validity
O2:Concepts
03:Trace
04:0verall
C solves Toat
GPT4TAsKSYN
0
0
0
0
BASETASKKYN
1
0
0
NEURTASKSYN
1
1
1
EXPERT
Figure 12: Scores showing whether the output Tout for vitn of each technique respects the six metrics O1-04, with the additional c solves Tout metric, for this Karel example.
We provide explanations for each entry for the objectives 01-03 in Figure 12
GPT4TASKSYN for Objective O1: Tio cannot be solved with any code respecting Teades hence 01
GPT4TASKSYN for Objective 02: Toue cannot be solved with any code respecting Tout hence 02 is 0.
GPT4TAsKSYN for Objective O3: To cannot be solved with any code respocting Toude hence 03
GPT4TASKSYN for cout solves Tout, The generated code cout does not solve Tout i.c., the progrid is not transformed into the postgrid after code execution.
BASETASKKYN for Objective 02: The employed IF block is not required. This implics that there is solution code C which has lower complexity, i.e., a smaller depth and less constructs than required by Waketch: hence 02 is 0.
20

---

Published in Transactions on Machine Learning Research (01/2024)
def Run(){
blocks is a body of basic action blocks from the aet faove, turnLeft, turaRight, pickMarker, putMarker]
blacks WHELE(b)
a blocks [F(b)
blocks
a boolean condition from (pathAhead, pathLeft, pathRight, no aa-pathAhead, markerPrasent, no no-markerPresent)
}
blocka
blocks
Number of blocks should be $ 10
(a) Task synthesis specification iith
def RuN(){ WHILE (BILE(pathAheedd IF (resee)))eeettt pickMarker
Allowed blocks: {move, turnLeft, turnRight, pickMarker, putMarker, WHILE, IF)
Maximum size: 10
(b) Tout by CPTATASKSYN
(c) Cout by GPT4TASKSYN
def Ruw()
Allowed blocks: {move, turnLeft, turnRight, pickMarker, putMarker, WHILE, IF)
WerLe(no--athhhheadY Ir(pathigght)
pickMarker
turnRight
turnRight
PickMarker
Maximum size: 10
move
(d) Tout by BASETASKSYN
(e) Cout by BASETASKSYN
def RuN
Allowed blocks: (move, turnLeft, turnRight, pi picMarkerr, putMarker, WHILE, IF)
W (atra(paahhhead)) pickharker IF (pathlee)))) putMarker
move turnRight
Maximum size:
(f) Tout by NEURTASKSYN
Cout by NEURTASKSYN
def Ruw()
Allowed hlocks: {move, turnLeft, turnRight, pickMarker, putMarker,
WHILE (no (att:e(uo--athhhhaa
pathhheedh
pickMarker
turnLeft
WHTLE, IF)
move
turnRight
move
Maximum size:
(h) Tout by EXPERT
(i) cout by EXPERT
Figure 13: Illustration containing the tuple Tout for each technique, along with cout for this Karel example.
21

---

Published in Transactions on Machine Learning Research (01/2024)
D Our Synthesis Technique NeurTaskSye Details
Next, we give additional details regarding each module of our architecture. We present the interaction between the neural models and the underlying symbolic engines, the neural architecture, and the training procedures.
D.1 Generating the Solution Code Cout
Code generator visualization. We describe the interaction between the neural model and the underlying symbolic engine for the code generator. For better understanding, we use one concrete example, illustrated in Figure 14 We consider the AST at time as presented in Figure 14a where the previously taken decision depth-first. traversal of the AST
was the addition of the turnLeft token. The symbolic engine continues and now needs take the next decision for the subsequent. 'a blocks'. This is achieved by interrogating the neural component; interaction demonstrated in Figure [4b] We introduce the notion of budget, which represents the number of available blocks that can be added to the AST so that the size specified by with is respected; in our example, the remaining budget is 2. It is passed as input for the neural model at time 1. The neural model, based on the budget and its internal state, which keeps track of the previously taken decisions, outputs a logit for each decision, i.e, a set of logits Ldiet. The symbolic engine accepts Laiet and masks them according to the rules in the DSL, thus obtaining masked In our example, the only values masked that are not masked are those of basic action blocks (i.e., move, turnLeft, turnRight) and the in diet
token that represents the end of the ELSE body. After mapping the logits to probability distribution, the symbolic engine proceeds to sample decision from it. In example, move is sampled. The decision is passed to the neural model to update its internal state. The symbolic engine then updates the AST with the taken decision (i.e., move), thus obtaining the updated version of the AST for the next step at time I + 1, illustrated in Figure 14c We generalize this process to every decision that needs to be taken while traversing the AST.
ded Run O REPEATUNTIL ( (p(ataRRigtt) turnRight
(1) budget
def RUN { REPEATUNTIL (goal)
(igatRiiggh(( türnRight
EusK(
Symbolic Engine
(2) logits Liiet
Neural Model
ÉLsE(
turnLeft
turnLeft
blocks
move
blocks
blocks
(3) sample (n.nneeedd
blocks
(a) Code status at time
(b) Interaction at time
(c) Code status at time
Figure 14: Visualization of the interaction process between the neural model and the symbolic engine in the code generator component of NEURTASKSYN. (a) shows the AST at time 4, where the first blocks' needs to be decided. (b) shows the interaction between the symbolic engine and the neural model at time i, where the symbolic engine first passes the budget (available blocks) to the neural model, the neural model computes the logits for all the tokens in the dictionary Ldict and passes them back to the symbolic engine, which finally masks them obtaining I.maeked, applies softmax to obtain a probability and samples the next action, sending it to the neural model. (c) shows the AST at time + 1, where the sampled move was integrated.
Imitation lcarning procedure. We will now give details about the learning procedure we used for the neural model. Given the fact that dataset == [ is accompanied by example codes, i.e., cin for each Jin we employ an imitation (supervised) learning approach, similar to (Devlin et al.) 2017 Bunel et al. 2018). Thus, for each decision, we compute the cross-entropy with respect the target decision. We force the agent to take the target decision afterward so the generated code does not digress from our example code.
22

---

Published in Transactions on Machine Learning Research (01/2024)
Neural architecture. Here, present in detail the architecture of the neural model employ for code generation. Similar to (Bunel et al. 2018), we employ an T.STM-based (Hochreiter & Schmidhuber 1997) recurrent neural network. We first convert code tokens to indexes based on a dictionary, then we pass them through an embedding layer. We do the same with the numeric representation of the budget (introducod previously). We concatenate both embeddings and pass them through a two-layer LSTM. Last, we convert the output of the LSTM logits for each entry the dictionary using a lincar layer. The architecture can be observed in Figure 15
Input
Code token categorical (0-58) Budget ordinal (0-16)
Embedding
Size 256
Size 16
LSTM
Hidden dim 256
LSTM
Hidden dim 256
Linear
Hidden dim Dict size 256 59
Figure 15: Archilecture of the neural model used by the code generator.
23

---

Published in Transactions on Machine Learning Research (01/2024)
D.2 Generating the Visual Puzzle Tio
Reinforcement learning procedure. We describe further details necessary for training our reinforcement learning (RL) agent. To learn a policy, we use policy gradient methods. These methods generally learn by using gradient ascent, thus updating the paramcters of the paramcterized policy To(als) to increase the expected reward of the policy in the MDP. Naturally, a neural network can be used to learn the policy, where 0 represents the network's weights. The network would take action and state s as input, outputting logit [s)() Given the logits, we map them to probabilistic distribution using softmax: sT(aas))
Lala, exp (Ha(''()))) We use an actor-critic policy gradient method for agent training (Sutton & Barto
(Xafala)))
2018). We denote with o(s, w) the value for state s predicted by the critic with parameters w. As we operate on batches, the parameters both the actor and the critic remain unchanged until a buffer is filled with a fixed number of episodes. Thus, for an initial state 8n (i.e., empty or pre-initialized task and code, with the emulator reset), we execute the existing policy тo until the buffer is filled, generating several sequences of experience tuples (st, (e, or) where T represents variable episode length. Thus, the losses for an episode are computed as a sum over the timesteps t E [], as follows, for the actor (Equation [ and for the critic (Equation employing the smooth L1 loss, denoted as L:
T
T
Losso =
Σ 1=
Σ
rr - 8($ b(st,w) w)) Vo (og((T((a(sss)
(1)
T L1
T Σr rr: ((s,, w)
Loss
smooth
(2)
1=
r=t
Finally, 9 and w are updated by using the computed losses over the entire batch, multiplied with a learning rale.
Neural architecture. We describe the architecture of the CNN-based neural model used by the puzzle generator. We employ similar architecture for both the HoCMaze and Karel domains, presented in Figure 16 Only the input size for the grid (i.e., D x 16 x 16, where D = 12 for HoCMaze and D = 14 for Karel) and code features (i.e., F, where F = 9 for HoCMaze and F = 12 for Karel) differ. We process the grid by 3 CNN blocks (i.e,, one block composed of Conv2D, ReLU, and MaxPooling2D layers), after which we apply 5 fully connected (linear) layers, thus obtaining the grid embedding. To the grid embedding, we concatenate the code features, which are represented a binary manner (e-g., increase coverage, current decision type). We then pass the concatenated tensor through an additional fully-connected layer, and its output is then passed to both the action head and the value head (i.e., necessary for the Actor-Critic algorithm).
24

---

Published in Transactions on Machine Learning Research (01/2024)
Input
D 16 x 16 Grid
Conv2D, kernel size padding 1, 64 x 64
CNN Block
ReLU
MaxPool2D, kernel size 2, padding 0
Couv2D, kernel size packing 1, x
Code features, Size F
CNN Block 2
ReLU MaxPool2D, kernel size 2, padding
Conv2D, kernel size = 3, padding 1, 64 x 64
CNN Block
ReLU MaxPool2D, kernel size 2, padding
Linear
CNN output size (256) 1024
Linear
1024 512
Linear
512 256
Linear 4
256 128
Linear
128 x 32
Linear
Concatenated features size (32 F)
Linear 7 (Action and Value)
action space
8
Figure 16: Architecture of the neural model used by the puzzle generator. D denotes the depth of the input
grid and F denotes the size of the code features tensor, both different for each of the HoCMaze and Karel domains.
25

---

Published in Transactions on Machine Learning Research (01/2024)
E
Experimental Evaluation with Synthetic Task Specifications: Details
In this section, we detail the instantiations of the scoring functions, give more insight into the synthetic dataset creation process, and show the details of the training processes for both the code generator and the task generator.
E.1 Scoring Function Fscore
Next, we describe the two instantiations for Fscore as used the two domains HoCMaze and Karel. We adopt scoring function similar to that of (Ahmed et al. 2020), where Fscore is used for guiding a Monte Carlo Tree Scarch, an ovaluation function that describes the desired properties of their system's output. We note that our method can work with any other instantiation of the scoring function Fscore- The instantiations we use for Foooee for each of the HoCMaze and Karel domains are defined in Equations 3 and 4 and are comprised of different components: (i) Feov TTTO, cout) E [0, computes the coverage ratio, i.c., ratio of executed blocks to total number of blocks; (ii) Faol(TTo cout) E {0, 1] evaluates to 1 if cout correctly solves ToO Le., no crashing, reaching the poal/converting the pre-grid to the post-grid; (iii) Fnocross (T cout) E 00 1] computes the ratio of cells visited exactly once with regard to the total number of visited cells; (iv) Frocut (Toot Cout) {0, evaluates to 0 if there is shorteut sequence comprised of basic actions; (v) Fnotred( (TT', cout) E [0, evaluates to 0 if there are redundant. action sequences in Cout, e.g., sequences like turnLeft, turnRight, or if the codes obtained by climinating one action, loop conditional from gout solves Too; ; (vi) (qut cout) E [0, 1] evaluates the visual quality of TiO" as per Equation 5 (vii)
Foutqual
(TT' (T10 Cniit E [0, 1] evaluates visual quality the shortest path made only of basic actions, similar F Fqual- We set 0n = 02 and 03 a4 as 3.
PHoCMaze (Tout cout) =1 F (TTO coul) 1, F (T couu) 1, nocross (Tout cout)
score
F nocut (Tie, cout) 1, F notreed (Tout cout) 1
(3)
a cov
CoverTTi (T10 couu) az qqual (Tout cout)
FKarel couu)
F nov (T cou) 1, Fsol (TTO) cout) 1, F. Forresss (T couu) (out)=/) =
Fnocut (T cont) 1, Fnoreed (TTO" cTut)
(4)
(Tout cout) + FF Fqu aggFeor C
(Tout cout) + atz Feutqual (T
(Tout cour)
We use the same measure of visual quality for both domains, keeping into account the number of moves, turns, segments, seggeessnnts, and turn-segments, as explained next. More specifically, segments and long-segments correspond to consecutive sequences of 'moves' containing more than 3 and 5 actions, respectively; turn-segments correspond to consecutive sequences of 'turnLeft' or 'turnRight' containing more than actions. The formula for Fqual given in Equation 5 below; we also clip the values for each counter # w.r.t. its corresponding normalization factor (not depicted here for brevity).
3
(
#moves 2n
#turns
#segments n/2
# #long- segments
segments)) ))
Fqual (Tout cout)
n
n/3
(5)
eeturn-seements.
4
n1/
E.2 Synthetic Task Specifications
Domain- elements. As introduced in Sections
and we use two DSLs shown in Fig-
17a and 17b adapted from the DSLs in (Bunel et al. 2018 Ahmed et al. 2020
26

---

Published in Transactions on Machine Learning Research (01/2024)
code
1= def RuB () DO
code
== def RUW () 00
rule
: g
rile
aj (b) Ir ELsE
rule
s:a In (b) Do
WHILE (b) Do REPEAT (x) Do
IF (b) E
action
turnLeft turnRight
REPEAT
putMarker pickMarker
rule
REPEATUNTIL (goal)
action a
move turnleft turnRight
bool
pathAhead pathleft pathRight
bool b = pathAhead pathLeft pathRight
1o-pathAbead markerPresent no-markerPreeent
iter x
== 2 2/3/415/60
10
Hee x
3 4
7 9
(a) DSL for HoCMaze domain
(b) DSL for Karel domain
Domain
All
Easy (depth, constructs)
Hard
(depth, constructs)
(1,0)
(2)
(2
(3,2)
(3,3)
HoCMaze
1, 1,016
183
69
47
136
581
Karel
1,027
300
155
277
295
0
(c) Dataset of synthetic task specifications
Figure 17: (a) Synthetic datasets used for training/ovaluuaion in Section
(b) DSLs for two domains.
Algorithm 1: Specification Datasel Collection Procedure
Input: list of tuples (code structure s, required size I); maximum candidate set size m; Dataset initialized empty set
ID + 0;
foreach (s,1) E do C+
/* Candidate set initialized empty */
while (C)) do
code &- GenerateCode(s3)
task + TASSORACLLLCCod)) score t score (task, code); if score then
L add (code, task, score) to C
sort C according to the score, in decreasing order; counter +- 0;
while counter < and C + 0 do (code, task, score) t PC)( accept Inspoct(task, code): if accept then sb + ExtractSpecsscode): add vb to D; counter + counter+1;
/* Inspection step */
Output: Dataset ID:
Dataset. We follow Algorithm I to create dataset D. For each code structure, generate set of candidate codes and obtain an oracle task for these codes. We filter them out if a low-quality task is obtained, supplementing this filtering with an additional inspection step. This inspection step is necessary because semantic irregularities (e.g., IFELSE with the same IF and ELSE bodies) can get past the previous filtering step. As the compute and implementation efforts are larger for an automatic system that would detect such irregularities, which are easy spot, we opt for direct inspection step. Figure 17c provides summary of datasets T3 for each domain.
27

---

Published in Transactions on Machine Learning Research (01/2024)
E.3 Training Process
Training the code generator. We employ standard approach, using imilation (supervised) form of learning, with cross-entropy loss for an LSTM-based architecture (see Appendix D (Devlin et al., 2017 Bunel et al. 2018 We augment Ditrai by adding all the possible combinations of construct instantiations for given code. The training plots and the hyperparameters used can be seen in Figure [8] We report the validation performance smoothed via an exponential decay function, and the batch loss averaged over one epoch.
VisMaieeVlidaaion Perfurmance H.CMao::Tiiiing Los
Validainni Performance
Kerel Triising Loss
HyperParameter
HoCMaze
Karel
1.0
Max. Epochs
100
0.8-
Batch Size
32
32
Learuing Rate
5
4
10-4
Dict. Size
59
59
0.2
Max. Blocks
17
17
00
0.0
Epoch
Epoch
(a) HoCMaze
(b) Karel
(c) Hyperparameters
Illustration of training details for the code generator. (a) and (b) show the training curves with mean epoch loss and validation performance, based on metric M, for both the HoCMaze and Karel domains. (c) shows the hyperparameters employed for the code generator training.
Figure 18:
Training the puzzle generator. We We augment the RL training set with additional codes produced by the previously trained code generator. To encourage higher quality tasks, we use a form of curriculum as follows: after a certain epoch, we give reward larger than only if the ratio between the scores of the output task and the TASKORACLE's task is larger than a factor X2; we gradually increase )a from 0.8 to 0.9. For Karel, we also employ a temperature parameter during training, encouraging exploration during inference. The training plots and the hyperparameters used can be seen in Figures 19 We report the validation performance (i.c., same metric employed for NEUrPuZZLEGEN) smoothed via exponential decay function, and the batch reward averaged over epoch.
RL procedure, using the instantiations of Fscore rewards.
HuCMMae-Validdiion Perfommanc
Kice Vilidziion Pesforaace
Ttaiiigg
Trining
HyperParameter
HoCMaze Karel
Max. Epochs
500
500
Batch Size
32
32
0.5-
Learuing Rate
10
10-4
0.4-
0.4-
www.
Temperature
0.5
0.2
0.2-
Curriculum
Tire
True
0
50
100
150
200
0.0
50
100
150
Epoch
Epoch
(a) HoCMaze
(b) Karel
(c) Hyperparameters
Figure 19: Illustationn of training details for the puzzle generator. (a) and (b) show the training curves with mean epoch reward and validation performance, based on metric M for both the HoCMaze and Karel domains. A form of curriculum learning was employed, which explains the lack of general monotonicity for the reward. (c) shows the hyperparameters employed for the puzzle generator training.
Further implementation details. We limit the number of possible initial locations for a grid to one representative per quadrant. In total, we consider quadrants (i.e., top-left, bottom-left, center, top-right, bottom-right). We do this limit the action space to a more tractable amount for variable grid size. With quadrants and 4 possible orientations, this leads 5 20 possible initial location /oiennaation pairs, offering already enough variability.
28

---

Published in Transactions on Machine Learning Research (01/2024)
Detailed results on synthetic task specifications. Figure 20 reports evaluation results for different
techniques for fixed number of code/puzall rollouts across two domains and segments, complementary to Figure
Technique
HoCMaze
Karel
All
Easy
Hard
All
Easy
Hard
BASE NAs
13.6 (1.3)
46.2 (4.1)
2.0 (1.3)
35.7 (1.0)
49.3 (0.9)
10.9 (2.7)
NeurTAskKYNesspp0
81.4 (3.7)
100.0 (0.0)
74.3 (5.1)
92.6 (1.4)
100.0 (0.0)
79.3 (3.9)
55.6 (1.8)
91.7 (2.4)
41.9 (2.3)
71.8 (3.8)
86.6 (3.8)
45.0 (3.9)
NeunPuzzLeEEN..rrppr
78.4 (2.5)
100.0 (0.0)
70.3 (3.4)
79.8 (0.6)
92.0 (1.3)
57.7 (1.8)
Figure 20: Results on synthetic lask specifications for HoCMaze and Karel; see Figure 17c and Section
29

---

Published in Transactions on Machine Learning Research (01/2024)
F
Experimental Evaluation with Real-World Task Specifications: Details
F.1
Real-World Task Specifications
In Figures
21 and
22
below, list source tasks and codes for 10 task specifications mentioned in Figure
Rux () { REPEAT nove nove turnRight
Allowed blocks: (move; turnleft, REPEAT)
turnRight,
Maximum size: 5
(a) Source T for tho
(b) Source for
def Ruy () {
Allowed blocks: (move; turnLeft, REPEATÜNTIL]
REP NEPEATUNTIL (goal) turnRight
turnRight,
turaLeft move
Maximum size: 6
(c) Source T for th
(d) Source for 1/11
def Run () { AMPRAT((): nove
Allowed blocks: (move, turnLeft, REPEAT]
turnRight,
turnLeft REPEAT(S) move
Maximum size: 6
(e) Source T for 2/2
(f) Source C for 4/2
det BUN(){
Allowed blocks: (move; turnLeft, REFEATUNTIL, IPELSE)
REPEATUNTIL (goal) IF (pathaheead) move
turnRight,
ELse(
turnleft
Maximum size: 5
(g)
Source T for w/s
(h) Source for ths
def Rux ()
Allowed blocks: (move, turnLeft, REPEATÜNTIL, IP)
REPEATURTIL (goal) move
turnRight,
IP (pathleff)) turaLeft
IF (pathRight))
turnRight
A
Maximum size: 7
(i) Source T for ths
(i) Source C for s/a
Figure 21: Overview of HoCMaze sources.
30

---

Published in Transactions on Machine Learning Research (01/2024)
Rux () move more putMarker move move
Allowed blocks: (nove, turnLeft, turnRight, pickMarker, putNarker)
Maximum
(a) Source T for ghs
(b) Source C for t/o
def Rux putMarker
Allowed blocks: (move, turnLeft, turnRight, pickMarker, putMarker, WHILK)
(pathAadad)))e move turnLeft
D C
move
turnRight
putMarker
Maximum size:
(c) Source T for dle
(d) Source C for dhe
RUX () { WHILE (patthhaah))) move pickMarker
Allowed blocks: (move, turnLeft, turaRight, pickMarker, putNarker, WAILE)
turnLeft turnLert
WHILE (Mtthhpathh
move
Maximum size: 10
turnLeft
turnLeft
(e) Source T 1/7
(f) Source for 1/7
def Rux {)
Allowed blocks: (nove, turnLeft, turnRight, pickMarker, putNarker; WHILE, IP)
WHILE pathAhead) Ir Ir(markerrresent)) pickNarker
turnLeft
turnRight move
Maximun size:
(g) Source T for ths
(h) Source C by ths
Rux () [ WHILE WEILe(pathAhees (pathAhead) move REPEAT(()
Allowed blocks: (nove, turnLeft, turaRight, pickMarker, putNarker, WHILE, REPEAT)
pickMarker
Maximum size: 5
(i) Source for the
(j) Source C by V
Figure 22: Overview of Karel sources.
31

---

Published in Transactions on Machine Learning Research (01/2024)
F.2 GPT4TaskSyn
We describe next the details of our interaction with GPT-4 for generaling the visual puzzles TIo and the intermediate code cout via the GPT4TAsKSYN techniques. Our interaction is conducted through the platform (OpenAT, 2023a). We try several strategics and prompts to make GPT-4 work for synthesizing visual programming tasks, as it tends to struggle with logical and spatial reasoning. Thus, we opt for a two-stage task synthesis process which works the best. We first ask GPT-4 to generate a code cous for 1ilh by using separate queries.
For the GPT4TASKSYN-comee converrse technique, start with an initial prompt and then use follow-up prompts to fix any mistakes, GPT-4 occasionally ignores part of the specifications. The initial and follow-up prompts used for generating Cout are presented in Figures 23a and 24a We select the best code generated during the separate queries based on our expertise. The second stage comprises of additional separate queries for generating TiO for the selected code cout, Again, we start with an initial prompt and then use follow-up prompts to fix any issucs. The follow-up prompts are necessary because GPT-4 tends struggle with spatial orientation and with the relationship between Cout and Tio The initial and follow-up prompts used for generating TiO are presented in Figures 23b and 24b Similar to the code selection process, we select the best visual puzzle generated during the 5 separate queries based on our expertise. Once we get cout and Too we set Tond as for BASETASKKYN and NEURTASKKYN.
For the YFT4TA technique, we employ a few-shot approach for both stages, by first giving synthesis examples (i.e., for code and task synthesis, respectively). We do not use follow-up prompts here. The few-shot prompts are presented in Figures and 26
32

---

Published in Transactions on Machine Learning Research (01/2024)
Code: Initial prompt
I am working in the block-based visual programming domain of Hour of Code: Maze Challenge from code.org, In this domain, the following types of coding blocks available:
Basic action blocks: move forward, turn left, turn right.
Boolean conditions: path ahead, path left, path right.
Loops: vepcatuutillgoa),, repeat(int).
Conditionals: if((bollen), if(oollaaneele
In this domain, a task is represented as an 8x88 visual grid that contains WALL cells, FREE cells, AVATAR (with specific location and direction), and GOAL. We represent a task's 8x8 visual grid with the following symbols.
# represents WALL cell.
represents a FREE cell.
represents GOAL.
represents AVATAR's location facing East direction.
W represents AVATAR's location facing West direction.
represents AVATAR's location facing North direction.
represents AVATAR's location facing South direction.
Below, I am giving program structure. Can generate code that respects this program structure?
Structure
[SKETCH]
You should not change the structure. This means that shouldn't add or remove any loops (e-g., peatUntilggoaa), repeat(int)) and conditionals (e-g., if(hholean). if(holleaneelse. The program needs to be valid, meaning that bodies of constructs camnot remain empty. To complete this given structure, you can use basic action blocks, boolean conditions, and iteration numbers that are available in the Hour of Code: Maze Challenge programming.
Code
Code: Follow-up prompt in case of constructs changed
Your code does follow the program structure have given. You shouldn't add remove any loops (e-g., repeatUntill repeat(int)) and conditionals (e.g., if(boollaa)), if(boolean)else). Can you try to generate new code for the same structure?
Code: Follow-up prompt for any other issucs
Your code could be improved! You can think of producing better code by reasoning about the AVATAR's actions when the code is executed. Can you try to generate new code respecting the program structure have given?
(a) Prompts used for obtaining Cont
33

---

Published in Transactions on Machine Learning Research (01/2024)
Task: Initial prompt
I am working in blsek visual programming domain Hour of Code: Maze Challenge from code.org. In this domain, the following types of coding blocks are available:
Basic action blocks: move forward, turn left, turn right.
Boolesn conditions: path ahead, path left, path right.
Loops: repeatUnil(goaa), rintat(int).
Conditionals: if(boolcan), ef(bollean)ele.
this domain, represented as an 8x8 visual grid that contains WALL cells, FREE cells, AVATAR (with specific location and direction), and GOAL. We represent a task's 8x8 visual grid with the following symbols.
# represents a WALL cell.
represents FREE cell.
represents GOAL.
represents AVATAR's location facing East direction.
W represents AVATAR's location facing West direction.
represents AVÄTAR'ss location facing North direction.
S represents AVATAR's location facing South direction.
Below am giving you a solution code. Can you generate task with 8x8 visual grid that would be solved by this code?
Solution
[CODE]
The visual grid must contain AVATAR (with specific location and direction) along with GOAL, and can have WALL cells and FREE cells. Number your grid with numbers (1 8) and column numbers (1 to 8). Also, you should me the position AVATAR and GOAL in your generated task so we are sure about the numbering.
You can verify the correctness of your generated by executing solution code on your task. solution code for task takes AVATAR to GOAL when executed. Note that AVATAR can only move on FREE cells and will crash if it tries to go to WALL cell. If your generated task is not correct, you should try again to generate correct task.
Task
Task: Follow-up prompt for any issues
Your code does not solve the generated grid. Be careful with AVATAR as should reach the goal after the code execntion. Keep the code fixed. Can you try to generate a new visual grid and explain your reasoning? Recall that your code, when executed, should take the AVATAR from its initial location to the GOAL.
(b) Prompts used for obtaining the main part of Tou
Figure 23: Prompts used in the implementation of GPT4TAsKSYX-commersss tcchnin for HoCMaze domain.
34

---

Published in Transactions on Machine Learning Research (01/2024)
Code: Initial prompt
I working in the block-based visual programming domain of Karel programming. In this domain, the following types coding blocks available:
Basic action blocks: move forward, turn left, turn right, pick marker, put marker.
Boolean conditions: path ahead, path left, path right, marker present, no path ahead, no marker present.
Loops: while(boolean), repeat(int).
Conditionals: il(boolcaa), ((boolcan)clse.
In this domain, a task is represented as a pair of 10x10 visual pregrid and 10x10 visual postgrid. This pregrid and postgrid contain WALL cells, FREE cells, AVATAR (with specific location and direction), and markers. represent a task's 10x10 visual pregrid and postgrid with following symbols.
# represents WALL cell.
+ represents a FREE cell.
represents cell with marker.
E represents AVXTAR's location on a cell without marker, facing East direction.
W represents AVATAR's location on a without marker, facing West direction.
N represents AVATAR's location on cell without marker, facing North direction.
represents AVAT'RR's location on cell without marker, facing South direction.
Em represents AVATAR's location cell with marker, facing East direction.
Wm represents AVATAR's location on a cell with marker, facing West direction.
reprosents AVATAR's location on cell with marker, facing North direction.
Sm represents AVATAR's location cell with marker, facing South direction. Below, am giving you a program structure, Can you generate code that respects this program structure?
Structure
[SKETCH]
You should not change the structure. This means that you shouldn't or remove any loops (e.g., while(boolean), repeat(int)) and conditionals (egg. il(boolean), i[(boleea)ells). The program needs to be valid, meaning that bodies of constructs cannot remain empty. To complete this given structure, you basic action blocks, boolean conditions, and iteration numbers that are available in Karel programming.
Code
Code: Follow-up prompt in case of constructs changed
Your code does not follow the programming structure have given. shouldn't add remove any loops (c.g,, while(boolcan), rencat(int)) and conditionals (o.g., if(boolcan), if/boolcan)else. Can you try to generate code for the same structure?
Code: Follow-up prompt for any other issnes
Your code could be improved! You think of producing better code by reasoning about the Karel AVATAR when the code executed. Can you try generate a new code?
(a) Prompts used for obtaining cous
35

---

Published in Transactions on Machine Learning Research (01/2024)
Task: Initial prompt
I am working in the block-based visual programming domain of Karel programming. In this domain, the
following types of coding blocks available:
Basic action blocks: move forward, turn left, turn right, pick marker, put marker.
Boolean conditions: path ahead, path left, path right, marker present, no path ahead, marker present.
Loops: while(boolean), repeat(int).
Conditionals: if(lbollan), if if(boolean)ebe.
In this domain, a task is represented as pair of 10x10 visual pregrid and 10x10 visual postgrid. This pregrid and postgrid contain WALL cells, FREE cells, AVATAR (with specific location and direction), and markers. represent task's 10x10 visual pregrid and postgrid with the following symbols.
# represents WALL cell.
represents a FREE cell.
represents cell with marker.
E represents AVATAR's location on a cell without marker, facing East direction.
W represents AVATAR's location on a without marker, facing West direction.
N represents AVATAR's location on cell without marker, facing North direction.
S represents AVATAR's location on cell without marker, facing South direction.
Em represents AVATAR's location cell with marker, facing East direction.
Wm represents AVATAR's location on a cell with marker, facing West direction.
Nm represents AVATAR's location cell with marker, facing North direction.
Sm represents AVATAR's location cell with marker, facing South direction.
Below am giving you a solution code. Can you generate a task with a pair of 10x10 visual pregrid and 10x10 visual postgrid that would be solved by this code?
Solution
[CODE]
Both the visual pregrid and visual postgrid must contain AVATAR (with specific location and direction), and can have WALL cells, FREE cells, and markers. Number your grids with row numbers (1 to 10) and column numbers (1 10). Also, you should tell the position of AVATAR your generated pregrid and postgrid so we are sure about the numbering.
You can verify the correctness of your generated task by executing the solution code on your task. A solution code task transforms the pregrid into the postgrid when executed. Note AVATAR can ouly move on FREE cells and will crash if it tries to to a WALI. cell. If your generated task is not correct, you should try again to generate a correct task.
Task
Task: Follow-up prompt for any issues
Your code does not solve the generated pregrid and postgrid. Be careful with the AVATAR in the postgrid as it should show the effect the code execution. Keep the code fixed. Can you try to generate a new visual pregrid and postgrid and explain your reasoning? Recall that your code, when executed, should transform the pregrid into the postgrid. Be careful with the AVATAR in the postgrid as it should show the effect of the code exccution.
(b) Prompts used for obtaining the main part of T
Figure 24: Prompts used in the implementation of GPT4TASKSYN-comeers technique for Karel domain.
36

---

Published in Transactions on Machine Learning Research (01/2024)
Code: Few-shot prompt
I am working in block-based visual programming domain Hour of Code: Maze Challenge from code.org. In this domain, the following types of coding blocks are available:
Basic action blocks: move forward, turn left, turn right.
Boolean conditions: path ahead, path left, path right.
Loops: repeatUntil(goa), rineat(int).
Conditionals: if((boolean) [[booleannelse
this domain, a task represented as an 8x88 visual grid that contains WALL cells, FREE cells, AVATAR (with specific location and direction), and GOAL. We represent a task's 8x8 visnal grid with the following symbols.
# represents a WALL cell.
represents FREE cell.
represents GOAL.
represents AVATAR's location facing East direction.
W represents AVATAR's location facing West direction.
represents AVATAR's location facing North direction.
represents AVATAR's location facing South direction.
Below, I will give you a program structure. Can you generate a code that respects this program structure?
You should not change the structure. This means that you shouldn't or remove any loops (e.g., re- peatUntill repeat(int)) and conditionals (e.g., if(boolean), if booleean))lls) The program needs to be valid, meaning that bodies of constructs cannot remain empty. To complete this given structure, you can basic action blocks, boolean conditions, and iteration numbers that available in the Hour of Code: Maze Challenge programming.
I giving you examples comprising program structure and code that respects the structure. Provide the code for the last structure.
Example Structure
[SKETCH i
Example i: Code
[CODE i]
Example n: Structure
[SKETCII n]
Example n: Code
(a) Prompts used obtaining cou
37

---

Published in Transactions on Machine Learning Research (01/2024)
Task: Few-shot prompt
I am working based visual programming domain Hour of Code: Maze Challenge from code.org. In this domain, the following types of coding blocks are available.
Basic action blocks: forward, turn left, turn right.
Hoolean conditions: path ahead, path left, path right.
Loops: repeatUntillgoa)), repeat(int).
Conditionals: if((bollan)) if( ((boolesn)elae.
In this domain, task is represented 8x68 visual grid that contains WALL cells, FREE cells, AVATAR (with specific location and direction), and GOAL. We represent a task's 8x8 visual grid with the following symbols.
# represents WALL cell.
represents FREE cell.
represents GOAL.
represents AVATAR's location facing East direction.
W represents AVATAR's location facing West direction.
represents AVATAR's location facing North direction.
S represents AVATAR's location facing South direction.
Below I will give you solution code. Can you generate task with 8x8 visual grid that would be solved by this code?
The visual grid must contain AVATAR (with specific location and direction) slong with GOAL, and can have WALL cells and FREE cells. Number your grid with numbers (1 8) and column numbers (1 to 8). Also, you should me the position AVATAR and GOAL in your generated task so we are sure. about the numbering.
You can verify the correctness of your generated by executing the solution code on your task. solution code for task takes AVATAR to GOAL when executed. Note that AVATAR can only move on FREE cells and will crash if it tries go WALL cell. If your generated task is not correct, you should try again to generate a correct task.
I am giving you some examples comprising a solution code and task that is solved by this code. Provide the task for the last solution code.
Example Solution
[CODE :]
Example i: Task
[TASK
Example Solution
[CODE n]
Example Task
(b) Prompts used for obtaining the main part of Tout
Figure 25: Prompts used in the implementation GPT4TAssSSYYfeesshoo technique for HoCMaze domain.
38

---

Published in Transactions on Machine Learning Research (01/2024)
Code: Few-shot prompt
I am working in the block-based visual programming domsin Karel programming. this domain, the following types of coding blocks are available:
Basic action blocks: move forward, turn left, turn right, pick marker, put marker.
Boolean conditions: path ahead, path left, path right, marker present, no path ahcad, marker present.
Loops: while(boolean), rentat(int).
Conditionals: if(boolean), if(boolean)cle.
In this domain, task is represented pair of 10x10 visual pregrid and 10x10 visual postgrid. This pregrid and postgrid contain WALL cells, FREE cells, AVATAR (with specific location and direction). and markers. We represent task's 10x10 visual pregrid and postgrid with the following symbols.
# represents WALL cell.
represents FREE coll.
m represents a cell with marker.
represents AVATAR's location cell without marker, facing Fast direction.
W represents AVATAR's location on a cell without marker, facing West direction.
represents AVATAR's location on a cell without marker, facing North direction.
S represents AVATAR's location cell without marker, facing South direction.
Em represents AVATAR's location on a cell with marker, facing East direction.
Wm represents AVATAR's location cell with marker, facing West direction.
Nm represents AVATAR's location ocll with marker, facing North direction.
represents AVATAR's location on a with marker, facing South direction.
Below, I will give you program structure. Can you generate code that respects this program structure?
You should not change the structure. This means that you shouldn't add or remove any loops (e.g.. while(boolean), (int)) and conditionals (e.g., il(boolean), jl(bolean)ells). The program needs to be valid, meaning that bodics constructs cammot remain empty. complete this given structure, you can use basic action blocks, boolean conditions, and iteration mumbers that are available in Karel programming,
giving you some examples comprising program structure and code that respects the structure. Provide the code for the last structure.
Example i: Structure
[SKKTCH_]
Example i: Code
[CODE_E
Example n: Structure
[SKETCH
Example n: Code
(a) Prompts used for obtaining Cous
39

---

Published in Transactions on Machine Learning Research (01/2024)
Task: Few-shot prompt
I am working in the block-based visual programming domain of Karel programming. In this domain, the following types coding blocks are available.
Basic action blocks: move forward, turn left, turn right, pick marker, put marker.
Boolean conditions: path ahead, path left, path right, marker present, no path ahead, no marker present.
Loops: while(boolean), repeat(int).
Conditionals: if(bbollan), if( booleean)eele.
In this domain, a task is represented as pair of 10x10 visual pregrid and 10x10 visual postgrid. This pregrid and postgrid contain WALL cells, FREE cells, AVATAR (with specifie location and direction), and markers. represent a task's 10x10 visual pregrid and postgrid with the following symbols.
represents WALL cell.
+ represents a FREE cell.
represents cell with marker.
E. represents A'XTAR's location on a cell without marker, facing East direction.
W represents AVATAR's location on a cell without marker, facing West direction.
N represents AVATAR's 's location on a cell without marker, facing North direction.
represents AVATAR's location on a cell without marker, facing South direction.
Em represents AVATAR's location cell with marker, facing East direction.
Wm represents AVATAR's location on a cell with marker, facing West direction.
Nm reprosents AVATAR's location on cell with marker, facing North direction.
Sm represents AVATAR's location cell with marker, facing South direction.
Below I will give you solution code. Can you generate a task with a pair of 10x10 visual pregrid and 10x10 visual postgrid that would solved by this code?
Both the visual pregrid and visual postgrid must contain AVATAR (with specific location and direction), and can have WALL cells, FREE colls, and markers. Number your grids with row numbers (1 10) and column numbers (1 to 10). Also, you should tell me the position of AVATAR in your generated progrid and postgrid so we are sure about the numbering.
You can verify the correctness of your generated task by executing the solution code on your task. A solution code for task transforms the pregrid into the postgrid when executed. Note that AVÄTAR can only move on FREE cells and will crash if it tries to go to a WALL cell. If your generated task is not correct, you should try again to generate a correct task.
I am giving you some examples comprising a solution code and task that is solved by this code. Provide the task for the last solution code.
Example Solution
[CODE_ i]
Example i: Task Pregrid
[TASK PREGRID _]]
Example i: Task Postgrid
[TASK POSTGRID
Example n: Solution
[CODE n]
Example n: Task Pregrid
(b) Prompts used obtaining the main part of Tip
Figure 26: Prompts used in the implementation of TTPTTTsssSSS-ffusooo technique for Karel domain.
40


Reviews:
[{"review_id": "oFWpZF9s7M", "reviewer": "Reviewer_Z1kh", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\nThe studied task of automatic content generation for education is well-formulated and impactful. The paper is clearly scoped within the domain of visual programming tasks and the resulting tasks are evaluated by human experts, achieving overall high quality.\n\nThe paper is clearly written and easy to follow. It evaluates the contributions of the individual components of the approach and compares to relevant baselines, like prompt-engineering GPT4.\n\nIt seems the results of the paper could be a useful resource in the programming education community even today.\n\n\n# Weaknesses\n\nA) No comparison to prior work: the paper cites two relevant prior works on task generation in the tested domains (Ahmed et al., Ghosh et al.), but the proposed approach is not compared to these methods, but instead only to a random search baseline and a GPT4-prompting method.\n\nB) No related work section: the paper lacks a related work section that performs a clear compare & contrast to prior work. The introduction captures some of that, but it would be good to have a separate related work section that summarizes the existing work and may also better justify the (lack of?) comparisons in the experimental section.\n\nC) unclear why we need this if we have an oracle: if I understand correctly, there exists and oracle method for generating tasks (called TASKORACLE in the paper), but it’s downside is that it is slow? It is a bit unclear why this is a major problem since the programming tasks could be generated ahead of time and would only need to be generated once, so even some compute expenses could be tolerated. Given that the paper runs the oracle often to generate the training dataset, it seems feasible to just use the oracle instead of the proposed method? Or is there a detail I am missing? If compute / runtime Is the main benefit of the proposed method over the oracle it would be good to experimentally compare the runtimes.\n\nD) method limited to visual programming domains: the method’s contributions are somewhat limited to the narrow domain of visual programming tasks. The comparisons to GPT4 show that on non-visual domains GPT4 is indeed well-able to generate tasks. Thus, it is likely that the introduced advances would not be necessary in those domains.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes an approach for generating visual programming tasks based on a task specification. It first generates a code proposal based on a partial code scaffolding and then generates a visual scene based on code rollouts an a neural decision making model.\nThe paper demonstrates that this hybrid approach of neural code generation and execution results in higher-quality visual programming tasks than brute-force random search and prompting GPT4 language models.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "# Requested Changes\n\n1) add comparison to prior works on visual programming task synthesis \n\n2) add a proper related work section\n\n3) clarify relation to task oracle and possibly add runtime comparison", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "hOWw20rmu9", "reviewer": "Reviewer_Lkyo", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n- **S.1** I appreciate that the authors included code and task specifications with their submission.\n\n### Weaknesses\n\n- **W.1** The work is really hard to parse. And this is also my main reason for rejection - I couldn't reproduce this because I don't understand what's going on. In the main body of the paper, you're hinting at different methods that are only explained in the appendix but that are crucial to understanding the paper. Only on pages 25 and 26, deep in the appendix was I able to find some crucial details of the algorithm. Other points that fall under this:\n    - **W.1.1** \"BaseTaskSyn\" is first mentioned on page 2 but only explained on page 8\n    - **W.1.2** I'm not a computer, so it takes a fair bit of my working memory to execute the code from Fig. 1 and Fig. 2 and apply that to the corresponding maze. You couldn't include a brief summary in the figure caption, what the differences are between the methods? Or maybe include a frame-by-frame \"animation\" of rollouts and how they fail in the respective cases.\n    - **W.1.3** I'm not sure why you're using imitation learning for part of your method and reinforcement learning for the other part of your method\n    - **W.1.4** In general, I have no idea what data comes from different systems, how they're trained, and how everything comes together. Your Fig. 3 is a first step towards this but I'd love if you could also show how exactly the code generator works, i.e. what format the incoming and outgoing data has and how it's trained (and how you're delineating the symbolic and neural parts). Same for the puzzle generator. Again, there was an attempt made here in Fig. 4 but I don't know what \"state (puzzle/code)\" actually means. How is that represented? And what exactly do the decision logits correspond to and change in the symbolic engine? They move the agent, they spawn objects, they remove wall, create walls? How does this guarantee the right number of steps?\n    - **W.1.5** There's a mention of a \"TaskOracle\" that \"does one million symbolic executions of a given code C returns highest-scoring task w.r.t. scoring function\" - I have no idea what any of this means.\n- **W.2** I don't know who this is relevant to. Why is it important for anyone to generate these mazes fast? When does it ever happen that you cannot pre-generate a couple offline and sample them? Also, what is the actual speed difference?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Broadly, this work is interested in generating new visual programming exercises consisting of small 2D mazes, code that solves the maze, and some restrictions in allowed code commands and allowed code structure.\nThe work contributes:\n- (1) a novel method for generating these that's faster and more robust than existing methods.\n- (2) a synthetic dataset for training the method\n- (3) evaluation of the method on self-defined metrics", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "- **R.1** I would require a rewrite of the sections 2, 3, and 4 for clarity and some additional figures to illustrate how everything works together and what data exactly is passed between the different subsystems.\n- **R.2** I need a convincing argument (a) that this is faster than existing methods (to back up contribution (1), and (b) that this is beneficial to the wider TMLR audience.\n\nMy current assessment is:\n\n**Are the claims made in the submission supported by**\n- accurate, -> possibly?\n- convincing and -> no, I cannot follow\n- clear evidence -> no\n\n**Would at least some individuals in TMLR's audience be interested in knowing the findings of this paper?**\n- I honestly don't know who this would apply to or who would benefit from this.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "KTmEVopcHZ", "reviewer": "Reviewer_hZEs", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I found it tricky to follow the paper. Perhaps that's because I am less familiar with task synthesis literature, but in general I found the description of the problem statement and solution to be too abstract until I got further into experiments and played around with Hour of Code / Code.org myself to understand what was going on.\n\nOnce I understood what the paper was doing, I thought it was good. However I do wonder about a \"GPT-4 driven symbolic engine\" baseline. My understanding is that GPT-4 is asked to generate the puzzle without using the symbolic engine in any way. There are a few papers that examine LLMs + tool use, i.e. the prompt describes how the model could use a browser, calculator, etc., in the style of Code-as-Policies / Language Model Programs (https://code-as-policies.github.io/). And I was curious at what would happen if a prompted GPT-4 was used in place of the Neural Model in Figure 4b, i.e. the prompt would be \"here is the state of a helpful puzzle making tool, here are the actions you could take, please output exactly one\", or something along those lines. Essentially I am wondering how necessary the RL step is here.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors study creation of introductory programming content, specifically based on drag-and-drop block style programming (i.e. like Scratch). The goal is to automatically create good programming puzzles, scored according to various criteria (an optimal solution of short length, solutions require demonstrating correct usage of programming concepts, etc.) These criteria are summarized into a final \"score\" for the quality of a puzzle, which can be treated as a scoring signal for an RL type method.\n\nSeparately from this, the authors study the combination of learned neural-net systems with symbolic techniques. We assume access to a baseline symbolic engine for puzzle generation, where state is the current puzzle + code execution, and the engine is driven by actions deciding how to modify the puzzle (i.e. that a certain branch of the if-block should be taken and the puzzle should support this.). One baseline runs this engine using random search whenever an action would be taken. Another baseline runs GPT-4 directly with a prompt to generate a code solution + a corresponding puzzle.\n\nThe method proposed by the authors is to\n\n1) Generate a dataset of synthetic puzzle examples by sampling code + initial constraints on programming constructs\n2) Train a policy (LSTM-based) with RL based on our scoring of what a good puzzle looks like, where the policy's actions drive the symbolic engine.\n\nThe resulting method is compared on some existing introductory programming environments (i.e. Hour of Code)", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "For making the paper clearer, my recommendation would be to modify Figure 1a to describe, in natural language, what the goal of the task synthesis specification is. Just saying \"the DSL constraints specify that boolean conditions should be in this set and use <= 7 blocks\" doesn't  help provide context on those constraints are for. Just a sentence describing the high-level goal would be helpful. Something like \"Generate a grid with start and end such that a coding solution satisfies (these constraints) and matches (this block structure)\"", "broader_impact_concerns": "No concerns here.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors have satisfactorily addressed reviewer concerns during the discussion period. The paper may still be challenging to read for much of the TMLR audience, primarily because the application domain is quite different from what ML folks usually consider.

The general consensus from the reviewers was that the work appeared incremental, and that it is unclear whether the paper will have significant impact. However, they all agreed it met the criteria for TMLR acceptance; and, as society-at-large is rapidly imagining AI-assisted futures for education, I find it easy to imagine future work looking to this kind of formal neural task-generation framework for inspiration.
Decision: Accept (poster)