Conversational semantic parsers map user utterances to executable programs given dialogue histories composed of previous utterances, programs, and system responses. Existing parsers typically condition on rich representations of history that include the complete set of values and computations previously discussed. We propose a model that abstracts over values to focus prediction on typeand function-level context. This approach provides a compact encoding of dialogue histories and predicted programs, improving generalization and computational efficiency. Our model incorporates several other components, including an atomic span copy operation and structural enforcement of well-formedness constraints on predicted programs, that are particularly advantageous in the low-data regime. Trained on the SMCALFLOW and TREEDST datasets, our model outperforms prior work by 7.3% and 10.6% respectively in terms of absolute accuracy. Trained on only a thousand examples from each dataset, it outperforms strong baselines by 12.4% and 6.4%. These results indicate that simple representations are key to effective generalization in conversational semantic parsing. Conversational semantic parsers, which translate natural language utterances into executable programs while incorporating conversational context, play an increasingly central role in systems for interactive data analysis (Yu et al., 2019), instruction following (Guu et al., 2017), and task-oriented dialogue (Zettlemoyer and Collins, 2009). An example of this task is shown in Figure 1. Typical models are based on an autoregressive sequence prediction approach, in which a detailed representation of the dialogue history is concatenated to the input sequence, and predictors condition on this sequence and all previously generated components of the output (Suhr et al., 2018). While this approach can capture arbitrary dependencies between inputs and outputs, it comes at the cost of sampleand computational inefficiency. We propose a new value-agnostic approach to contextual semantic parsing driven by type-based representations of the dialogue history and function-based representations of the generated programs. Types and functions have long served as a foundation for formal reasoning about programs, but their use in neural semantic parsing has been limited, e.g., to constraining the hypothesis space (Krishna-murthy et al., 2017), guiding data augmentation (Jia and Liang, 2016), and coarsening in coarse-to-fine models (Dong and Lapata, 2018). We show that representing conversation histories and partial programs via the types and functions they contain enables fast, accurate, and sample-efficient contextual semantic parsing. We propose a neural encoder decoder contextual semantic parsing model which, in contrast to prior work: 1. uses a compact yet informative representation of discourse context in the encoder that considers only the types of salient entities that were predicted by the model in previous turns or that appeared in the execution results of the predicted programs, and 2. conditions the decoder state on the sequence of function invocations so far, without conditioning on any concrete values passed as arguments to the functions. Our model substantially improves upon the best published results on the SMCALFLOW (Semantic Machines et al., 2020) and TREEDST (Cheng et al., 2020) conversational semantic parsing datasets, improving model performance by 7.3% and 10.6%, respectively, in terms of absolute accuracy. In further experiments aimed at quantifying sample efficiency, ENTITYPROPOSERS Number(2) Month.May Proposeentitiesfromthecurrentuserutterance. it improves accuracy by 12.4% and 6.4% respectively when trained on only a thousand examples from each dataset. Our model is also effective at non-contextual semantic parsing, matching state-of-the-art results on the JOBS , GEOQUERY , and ATIS datasets (Dong and Lapata, 2016). This is achieved while also reducing the test time computational cost by a factor of 10 (from 80ms per utterance down to 8ms when running on the same machine; more details are provided in Appendix H), when compared to our fastest baseline, which makes it usable as part of a real-time conversational system. One conclusion from these experiments is that most semantic parses have structures that depend only weakly on the values that appear in the dialogue history or in the programs themselves. Our experiments find that hiding values alone results in a 2.6% accuracy improvement in the low-data regime. By treating types and functions, rather than values, as the main ingredients in learned representations for semantic parsing, we improve model accuracy and sample efficiency across a diverse set of language understanding problems, while also significantly reducing computational costs. Our goal is to map natural language utterances to programs while incorporating context from dialogue histories (i.e., past utterances and their associated associated programs and execution results). We model a program as a sequenceo of function invocations , each consisting of a function and zero or more argument values , as illustrated at the lower right of Figure 1. The argument values can be either literal values or references to results of previous function invocations. The ability to reference previous elements of the sequence, sometimes called a target-side copy , allows us to construct programs that involve re-entrancies. Owing to this referential structure, a program can be equivalently represented as a directed acyclic graph (see e.g., Jones et al., 2012; Zhang et al., 2019). We propose a Transformer-based (Vaswani et al., 2017) encoderdecoder model that predicts programs by generating function invocations sequentially, where each invocation can draw its arguments from an inventory of values (2.5)possibly copied from the utteranceand the results of previous function invocations in the current program. The encoder (2.2) transforms a natural language utterance and a dialogue history to a continuous representation. Subsequently, the decoder (2.3) uses this representation to define an autoregressive distribution over function invocation sequences and chooses a high-probability sequence by performing beam search. As our experiments (3) will show, a nave encoding of the complete dialogue history and program results in poor model accuracy. Our approach assumes that programs have type annotations on all values and function calls, similar to the setting of Krishnamurthy et al. (2017). 1 Furthermore, we assume that program prediction is local in that it does not require program fragments to be copied from the dialogue history (but may still depend on history in other ways). Several formalisms, including the typed references of Zettlemoyer and Collins (2009) and the meta-computation operators of Semantic Machines et al. (2020), make it possible to produce local program annotations even for dialogues like the one depicted in Figure 2, which reuse past computations. We transformed the datasets in our experiments to use such meta-computation operators (see Appendix C). We also optionally make use of entity proposers , similar to Krishnamurthy et al. (2017), which annotate spans from the current utterance with typed values. For example, the span one in Change it to one might be annotated with the value 1 of type Number . These values are scored by the decoder along with other values that it considers (2.5) when predicting argument values for function invocations. Using entity proposers aims to 1 This requirement can be trivially satisfied by assigning all expressions the same type, but in practice defining a set of type declarations for the datasets in our experiments was not difficult (refer to Appendix C for details). help the model generalize better to previously unseen values that can be recognized in the utterance using hard-coded heuristics (e.g., regular expres-sions), auxiliary training data, or other runtime information (e.g., a contact list). In our experiments we make use of simple proposers that recognize numbers, months, holidays, and days of the week, but one could define proposers for arbitrary values (e.g., song titles). As described in 2.5, certain values can also be predicted directly without the use of an entity proposer. The encoder, shown in Figure 3, maps a natural language utterance to a continuous representation. Like many neural sequence-to-sequence models, we produce a contextualized token representation of the utterance, H utt  RU  h enc , where U is the number of tokens and h enc is the dimensionality of their embeddings. We use a Transformer encoder (Vaswani et al., 2017), optionally initialized using the BERT pretraining scheme (Devlin et al., 2019). Next, we need to encode the dialogue history and combine its representation with H utt to produce history-contextualized utterance token embeddings. Prior work has incorporated history information by linearizing it and treating it as part of the input utterance (Cheng et al., 2018; Semantic Machines et al., 2020; Aghajanyan et al., 2020). While flexi-ble and easy to implement, this approach presents a number of challenges. In complex dialogues, history encodings can grow extremely long relative to the user utterance, which: (i) increases the risk of overfitting, (ii) increases computational costs (because attentions have to be computed over long sequences), and (iii) necessitates using small batch sizes during training, making optimization difficult. Thanks to the predictive locality of our representations (2.1), our decoder (2.3) never needs to retrieve values or program fragments from the dialogue history. Instead, context enters into programs primarily when programs use referring expressions that point to past computations, or revision expressions that modify them. Even though this allows us to dramatically simplify the dialogue history representation, effective generation of referring expressions still requires knowing something about the past. For example, for the utterance What's next? the model needs to determine what What refers to. Perhaps more interestingly, the presence of dates in recent DIALOGUE HISTORY TYPES Unit Constraint[String] Constraint[Event] Event String EventNotFoundError embed decoder UTTERANCE ENCODER DIALOGUE HISTORY ENCODER USER UTTERANCE "Oh, it's just called shopping. It may be at 2." attention K V Q Figure 3: Illustration of our encoder (2.2), using the example of Figure 1. The utterance is processed by a Transformer-based (Vaswani et al., 2017) encoder and combined with information extracted from the set of dialogue history types using multi-head attention. turns (or values that have dates, such as meetings) should make the decoder more eager to generate referring calls that retrieve dates from the dialogue history; especially so if other words in the current utterance hint that dates may be useful and yet date values cannot be constructed directly from the current utterance. Subsequent steps of the decoder which are triggered by these other words can produce functions that consume the referred dates. We thus hypothesize that it suffices to strip the dialogue history down to its constituent types, hiding all other information. 2 Specifically, we extract a set T of types that appear in the dialogue history up to m turns back, where m = 1 in our experiments. 3 Our encoder then transforms H utt into a sequence of history-contextualized embeddings H enc by allowing each token to attend over T . This is motivated by the fact that, in many cases, dialogue history is important for determining the meaning of specific tokens in the utterance, rather than the whole utterance. Specifically, we learn embeddings T  R |T | h type for the extracted types, where h type is the embedding size, and use the attention mechanism of Vaswani et al. (2017) to contextualize H utt : H enc (cid:44) H utt + MHA ( H utt (cid:124)(cid:123)(cid:122)(cid:125) Queries , T (cid:124)(cid:123)(cid:122)(cid:125) Keys , T (cid:124)(cid:123)(cid:122)(cid:125) Values ) , (1) where MHA stands for multi-head attention, and each head applies a separate linear transformation to the queries, keys, and values. Intuitively, 2 For the previous example, if the type List[Event] appeared in the history then we may infer that What probably refers to an Event . 3 We experimented with different values of m and found that increasing it results in worse performance, presumably due to overfitting. [0] +( 1, 2) [1] +([0], 3) [2] +([1], 4) [3] +([2], 5) [0] +(Number, Number) [1] +(Number, Number) [2] +(Number, Number) Consider the following program representing the expression 1 + 2 + 3 + 4 + 5: While generating this invocation, the decoder only gets to condition on the following program prefix: Argument values are masked out! each utterance-contextualized token is further contextualized in (1) by adding to it a mixture of embeddings of elements in T , where the mixture coefficients depends only on that utterance-contextualized token. This encoder is illustrated in Figure 3. As we show in 3.1, using this mechanism performs better than the nave approach of appending a set-of-types vector to H utt . The decoder uses the history-contextualized representation H enc of the current utterance to predict a distribution over the program  that corresponds to that utterance. Each successive line  i of  invokes a function f i on an argument value tuple ( v i 1 , v i 2 , . . . , v iA i ) , where A i is the number of (for-mal) arguments of f i . Applying f i to this ordered tuple results in the invocation f i ( a i 1 = v i 1 , a i 2 = v i 2 , . . . ) , where ( a i 1 , a i 2 , . . . , a iA i ) name the formal arguments of f i . Each predicted value v ij can be the result of a previous function invocation, a constant value, a value copied from the current utterance, or a proposed entity (2.1), as illustrated in the lower right corner of Figure 1. These different argument sources are described in 2.5. Formally, the decoder defines a distribution of programs  : p (  | H enc ) = P (cid:89) i =1 p (  i | f <i , H enc ) , (2) where P is the number of function invocations in the program, and f <i (cid:44) { f 1 , . . . , f i  1 } . Additionally, we assume that argument values are conditionally independent given f i and f <i , resulting in: p (  i | f <i ) = p ( f i | f <i ) (cid:124) (cid:123)(cid:122) (cid:125) function scoring A i (cid:89) j =1 p ( v ij | f <i , f i ) (cid:124) (cid:123)(cid:122) (cid:125) argument value scoring , (3) where we have elided the conditioning on H enc . Here, functions depend only on previous functions FUNCTIONEMBEDDER from: City NAME TYPE argumentembedding FUNCTIONSIGNATURE NAME TYPE TYPE ARGUMENT ARGUMENT Book[Flight](from: City, to: City): Booking[Flight] POOLING functionembedding ARGUMENTEMBEDDER Figure 5: Illustration of our function encoder (2.4), using a simplified example function signature. (not their argument values or results) and argument values depend only on their calling function (not on one another or any of the previous argument values). 4 This is illustrated in Figure 4. In addition to providing an important inductive bias, these independence assumptions allow our inference procedure to efficiently score all possible function invocations at step i , given the ones at previous steps, at once (i.e., function and argument value assignments together), resulting in an efficient search algorithm (2.6). Note that there is also a corresponding disadvantage (as in many machine translation models) that a meaningful phrase in the utterance could be independently selected for multiple arguments, or not selected at all, but we did not encounter this issue in our experiments; we rely on the model training to evade this problem through the dependence on H enc . In Equation 3, the sequence of functions f 1 , f 2 , . . . in the current program is modeled by (cid:81) i p ( f i | f <i , H enc ) . We use a standard autoregressive Transformer decoder that can also attend to the utterance encoding H enc (2.2), as done by Vaswani et al. (2017). Our decoder generates sequences over the vocabulary of functions . This means that each function f i needs an embedding f i (used as both an input to the decoder and an output), which we construct compositionally . We assume that each unique function f has a type signature that specifies a name n , a list of type parameters {  1 , . . . ,  T } (to support poly-morphism), 5 a list of argument names and types (( a 1 , t 1 ) , . . . , ( a A , t A )) , and a result type r . An 4 We also tried defining a jointly normalized distribution over entire function invocations (Appendix A), but found that it results in a higher training cost for no accuracy benefits. example is shown in Figure 5. We encode the function and argument names using the utterance encoder of 2.2 and learn embeddings for the types, to obtain ( n , r ) , {  1 , . . . ,  T } , and { ( a 1 , t 1 ) , . . . , ( a A , t A ) } . Then, we construct an embedding for each function as follows: a = Pool ( a 1 + t 1 , . . . , a A + t A ) , (4) f = n + Pool (  1 , . . . ,  T ) + a + r , (5) where Pool is the max-pooling operation which is invariant to the arguments' order. Our main motivation for this function embedding mechanism is the ability to take cues from the user utterance (e.g., due to a function being named similarly to a word appearing in the utterance). If the functions and their arguments have names that are semantically similar to corresponding utterance parts, then this approach enables zero-shot generalization. 6 However, there is an additional potential benefit from parameter sharing due to the compositional structure of the embeddings (see e.g., Baroni, 2020). This section describes the implementation of the argument predictor p ( v ij | f <i , f i ) . There are four different kinds of sources that can be used to fill each available argument slot: references to previous function invocations, constants from a static vocabulary, copies that copy string values from the utterance, and entities that come from entity proposers (2.1). Many sources might propose the same value, including multiple sources of the same kind. For example, there may be multiple spans in the utterance that produce the same string value in a program, or an entity may be proposed that is also available as a constant. To address this, we marginalize over the sources of each value: p ( v ij | f <i , f i )= (cid:88) s S ( v ij ) p ( v ij , s | f <i , f i ) , (6) where v ij represents a possible value for the argument named a ij , and s  S ( v ij ) ranges over the possible sources for that value. For example, given the utterance Change that one to 1:30pm and the value 1 , the set S ( 1 ) may contain entities that correspond to both one and 1 from the utterance. 6 The data may contain overloaded functions that have the same name but different type signatures (e.g., due to optional arguments). The overloads are given distinct identifiers f , but they often share argument names, resulting in at least partially shared embeddings. The argument scoring mechanism considers the last-layer decoder state h i dec that was used to predict f i via p ( f i | f <i )  exp( f (cid:62) i h i dec ) . We specialize this decoder state to argument a ij as follows: h i,a ij dec (cid:44)  h i dec (cid:12) tanh ( f i + a ij ) , (7) where (cid:12) represents elementwise multiplication, f i is the embedding of the current function f i , a ij is the encoding of argument a ij as defined in 2.4, and  h dec is a projection of h dec to the necessary dimensionality. Intuitively, tanh( f i + a ij ) acts as a gating function over the decoder state, deciding what is relevant when scoring values for argument a ij . This argument-specific decoder state is then combined with a value embedding to produce a probability for each (sourced) value assignment: p ( v, s | f <i , f i )  exp (cid:110)  v (cid:62) ( h i,a dec + w kind ( s ) a ) + b kind ( s ) a (cid:111) , (8) where a is the argument name a ij , kind( s )  { REFERENCE , CONSTANT , COPY , ENTITY } ,  v is the embedding of ( v, s ) which is described next, and w ka and b ka are model parameters that are specific to a and the kind of the source s . References. References are pointers to the return values of previous function invocations. If the source s for the proposed value v is the result of the k th invocation (where k < i ), we take its embedding  v to be a projection of h k dec that was used to predict that invocation's function and arguments. Constants. Constants are values that are always proposed, so the decoder always has the option of generating them. If the source s for the proposed value v is a constant, we embed it by applying the utterance encoder on a string rendering of the value. The set of constants is automatically extracted from the training data (see Appendix B). Copies. Copies are string values that correspond to substrings of the user utterance (e.g., person names). String values can only enter the program through copying, as they are not in the set of constants (i.e., they cannot be hallucinated by the model; see Pasupat and Liang, 2015; Nie et al., 2019). One might try to construct an approach based on a standard token-based copy mechanism (e.g., Gu et al., 2016). However, this would allow copying non-contiguous spans and would also require marginalizing over identical tokens as opposed to spans, resulting in more ambiguity. Instead, we propose a mechanism that enables the decoder to copy contiguous spans directly from the utterance. Its goal is to produce a score for each of the U ( U + 1) / 2 possible utterance spans. Navely, this would result in a computational cost that is quadratic in the utterance length U , and so we instead chose a simple scoring model that avoids it. Similar to Stern et al. (2017) and Kurib-ayashi et al. (2019), we assume that the score for a span factorizes, and define the embedding of each span value as the concatenation of the contextual embeddings of the first and last tokens of the span,  v = [ h k start utt ; h k end utt ] . To compute the copy scores we also concatenate h i,a dec with itself in Equation 8. Entities. Entities are treated the same way as copies, except that instead of scoring all spans of the input, we only score spans proposed by the external entity proposers discussed in 2.1. Specifically, the proposers provide the model with a list of candidate entities that are each described by an utterance span and an associated value. The candidates are scored using an identical mechanism to the one used for scoring copies. This means that, for example, the string sept could be linked to the value Month.September even though the string representations do not match perfectly. Type Checking. When scoring argument values for function f i , we know the argument types, as they are specified in the function's signature. This enables us to use a type checking mechanism that allows the decoder to directly exclude values with mismatching types. For references, the value types can be obtained by looking up the result types of the corresponding function signatures. Additionally, the types are always pre-specified for constants and entities, and copies are only supported for a subset of types (e.g., String , PersonName ; see Appendix B). The type checking mechanism sets p ( v ij | f <i , f i ) = 0 whenever v ij has a different type than the expected type for a ij . Finally, because copies can correspond to multiple types, we also add a type matching term to the copy score. This term is defined as the inner product of the argument type embedding and a (learnable) linear projection of h k start utt and h k end utt concatenated, where k start and k end denote the span start and end indices. Similar to other sequence-to-sequence models, we employ beam search over the sequence of function invocations when decoding. However, in contrast to other models, our assumptions (2.3) allow us to Dataset SMCALFLOWTREEDSTV 1.1 V 2.0 Best Reported Result 66.5 68.2 62.2 Our Model 73.8 75.3 72.8 Table 1: Test set exact match accuracy comparing our model to the best reported results for SMCALFLOW (Seq2Seq model from the public leaderboard; Semantic Machines et al., 2020) and TREEDST (TED-PP model; Cheng et al., 2020). This computation is parallelizable and it also allows the decoder to avoid choosing a function if there are no high scoring assignments for its arguments (i.e., we are performing a kind of lookahead ). This also means that the paths explored during the search are shorter for our model than for models where each step corresponds to a single decision, allowing for smaller beams and more efficient decoding. We first report results on SMCALFLOW (Semantic Machines et al., 2020) and TREEDST (Cheng et al., 2020), two recently released large-scale conversational semantic parsing datasets. Our model makes use of type information in the programs, so we manually constructed a set of type declarations for each dataset and then used a variant of the Hindley-Milner type inference algorithm (Damas and Milner, 1982) to annotate programs with types. As mentioned in 2.1, we also transformed TREEDST to introduce meta-computation operators for references and revisions (more details can be found in Appendix C). 7 We also report results on nonconversational semantic parsing datasets in 3.2. We use the same hyperparameters across all experiments (see Appendix E), and we use BERT-medium (Turc et al., 2019) to initialize our encoder. Test set results for SMCALFLOW and TREEDST are shown in Table 1. Our model significantly outperforms the best published numbers in each case. 7 The transformed datasets are available at https: //github.com/microsoft/task_oriented_dialogue_as_dataflow_synthesis/tree/master/datasets . In order to further understand the performance characteristics of our model and quantify the impact of each modeling contribution, we also compare to a variety of other models and ablated versions of our model. We implemented the following baselines:  Seq2Seq: The OpenNMT (Klein et al., 2017) implementation of a pointer-generator network (See et al., 2017) that predicts linearized plans represented as S-expressions and is able to copy tokens from the utterance while decoding. This model is very similar to the model used by Semantic Machines et al. (2020) and represents the current state-of-the-art for SMCALFLOW . 8  Seq2Tree: The same as Seq2Seq, except that it generates invocations in a top-down, pre-order program traversal. Each invocation is embedded as a unique item in the output vocabulary. Note that SMCALFLOW contains re-entrant programs represented with LISP-style let bindings. Both the Seq2Tree and Seq2Seq are unaware of the special meaning of let and predict calls to let as any other function, and references to bound 8 Semantic Machines et al. (2020) used linearized plans to represent the dialogue history, but our implementation uses previous user and agent utterances. We found no difference in performance. variables as any other literal. Seq2Tree++: An enhanced version of the model by Krishnamurthy et al. (2017) that predicts typed programs in a top-down fashion. Unlike Seq2Seq and Seq2Tree, this model can only produce well-formed and well-typed programs. It also makes use of the same entity proposers (2.1) similar to our model, and it can atomically copy spans of up to 15 tokens by treating them as additional proposed entities. Furthermore, it uses the linear history encoder that is described in the next paragraph. Like our model, re-entrancies are represented as references to previous outputs in the predicted sequence. We also implemented variants of Seq2Seq and Seq2Tree that use BERT-base 9 (Devlin et al., 2019) as the encoder. Our results are shown in Table 2a. Our model outperforms all baselines on both datasets, showing particularly large gains in the low data regime, even when using BERT. Finally, we implemented the following ablations, with more details provided in Appendix G:  Value Dependence: Introduces a unique function for each value in the training data (except for copies) and transforms the data so that values are always produced by calls to these functions, allowing the model to condition on them. No Name Embedder: Embeds functions and constants atomically instead of using the approach of 2.4 and the utterance encoder. No Types: Collapses all types to a single type, which effectively disables type checking (2.5). No Span Copy: Breaks up span-level copies into token-level copies which are put together using a special concatenate function. Note that our model is value-agnostic and so this ablated model cannot condition on previously copied tokens when copying a span token-by-token. No Entity Proposers: Removes the entity proposers, meaning that previously entity-linked values have to be generated as constants. No History: Sets H enc = H utt (2.2). Previous Turn: Replaces the type-based history encoding with the previous turn user and system utterances or linearized system actions. Linear Encoder: Replaces the history attention 9 We found that BERT-base worked best for these baselines, but was no better than the smaller BERT-medium when used with our model. Also, unfortunately, incorporating BERT in Seq2Tree++ turned out to be challenging due to the way that model was originally implemented. The results, shown in Table 2b, indicate that all of our features play a role in improving accuracy. Perhaps most importantly though, the value dependence ablation shows that our function-based program representations are indeed important, and the previous turn ablation shows that our type-based program representations are also important. Furthermore, the impact of both these modeling decisions grows larger in the low data regime, as does the impact of the span copy mechanism. Our main focus is on conversational semantic parsing, but we also ran experiments on nonconversational semantic parsing benchmarks to show that our model is a strong parser irrespective of context. Specifically, we manually annotated the JOBS , GEOQUERY , and ATIS datasets with typed declarations (Appendix C) and ran experiments comparing with multiple baseline and state-of-the-art methods. The results, shown in Table 3, indicate that our model meets or exceeds state-of-the-art performance in each case. Our approach builds on top of a significant amount of prior work in neural semantic parsing and also context-dependent semantic parsing. was a brief period of interest in using unstructured sequence models for semantic parsing (e.g., Andreas et al., 2013; Dong and Lapata, 2016), most research on semantic parsing has used treeor graph-shaped decoders that exploit program structure. Most such approaches use this structure as a constraint while decoding, filling in function arguments one-at-a-time, in either a top-down fashion (e.g., Dong and Lapata, 2016; Krishnamurthy et al., 2017) or a bottom-up fashion (e.g., Misra and Artzi, 2016; Cheng et al., 2018). Both directions can suffer from exposure bias and search errors during decoding: in top-down when there's no way to realize an argument of a given type in the current context, and in bottom-up when there are no functions in the programming language that combine the predicted arguments. To this end, there has been some work on global search with guarantees for neural semantic parsers (e.g., Lee et al., 2016) but it is expensive and makes certain strong assumptions. In contrast to this prior work, we use program structure not just as a decoder constraint but as a source of independence assumptions: the decoder explicitly decouples some decisions from others, resulting in good inductive biases and fast decoding algorithms. Perhaps closest to our work is that of Dong and Lapata (2018), which is also about decoupling decisions, but uses a dataset-specific notion of an abstracted program sketch along with different independence assumptions, and underperforms our model in comparable settings (3.2). Also close are the models of Cheng et al. (2020) and Zhang et al. (2019). Our method differs in that our beam search uses larger steps that predict functions together with their arguments, rather than predicting the argument values serially in separate dependent steps. Similar to Zhang et al. (2019), we use a target-side copy mechanism for generating references to function invocation results. However, we extend this mechanism to also predict constants, copy spans from the user utterance, and link externally proposed entities. While our span copy mechanism is novel, it is inspired by prior attempts to copy spans instead of tokens (e.g., Singh et al., 2020). Finally, bottom-up models with similarities to ours include SMBOP (Rubin and Berant, 2020) and BUSTLE (Odena et al., 2020). Context-Dependent Semantic Parsing. Prior work on conversational semantic parsing mainly focuses on the decoder, with few efforts on incorporating the dialogue history information in the encoder. Recent work on context-dependent semantic parsing (e.g., Suhr et al., 2018; Yu et al., 2019) conditions on explicit representations of user utterances and programs with a neural encoder. While this results in highly expressive models, it also increases the risk of overfitting. Contrary to this, Zettlemoyer and Collins (2009), Lee et al. (2014) and Semantic Machines et al. (2020) do not use context to resolve references at all. They instead predict context-independent logical forms that are resolved in a separate step. Our approach occupies a middle ground: when combined with local program representations, types, even without any value information, provide enough information to resolve context-dependent meanings that cannot be derived from isolated sentences. The specific mechanism we use to do this infuses contextual type information into input sentence representations, in a manner reminiscent of attention flow models from the QA literature (e.g., Seo et al., 2016). We showed that abstracting away values while encoding the dialogue history and decoding programs significantly improves conversational semantic parsing accuracy. In summary, our goal in this work is to think about types in a new way. Similar to previous neural and non-neural methods, types are an important source of constraints on the behavior of the decoder. Here, for the first time, they are also the primary ingredient in the representation of both the parser actions and the dialogue history. Our approach, which is based on type-centric encodings of dialogue states and function-centric encodings of programs (2), outperforms prior work by 7.3% and 10.6%, on SMCALFLOW and TREEDST, respectively (3), while also being more computationally efficient than competing methods. Perhaps more importantly, it results in even more significant gains in the low-data regime. This indicates that choosing our representations carefully and making appropriate independence assumptions can result in increased accuracy and computational efficiency. We thank the anonymous reviewers for their helpful comments, Jason Eisner for his detailed feedback and suggestions on an early draft of the paper, Abulhair Saparov for helpful conversations and pointers about semantic parsing baselines and prior work, and Theo Lanman for his help in scaling up some of our experiments.
abstain abstain objective abstain method result abstain abstain abstain abstain abstain objective abstain result other result abstain abstain result result abstain result result abstain abstain abstain method abstain abstain abstain abstain abstain method method abstain abstain abstain abstain abstain abstain abstain method abstain abstain method method method abstain abstain abstain abstain abstain abstain method abstain abstain abstain method abstain abstain abstain method method abstain method abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain other method abstain abstain abstain abstain method method method abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain method abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain method abstain method other method abstain abstain abstain result result result result other abstain result abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain result result abstain abstain abstain abstain abstain abstain abstain abstain result abstain result result abstain result abstain result abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method method result objective abstain abstain result abstain result other