\documentclass{llncs}	

\title{Active and Passive Strategies in Dialogue Program Generation}
\author{Ivan Kope\v cek}
%\aindex{Kope\v cek, I.}

\institute{Faculty of Informatics, Masaryk University\\ Botanicka 68a,
602 00 Brno\\ Czech Republic\\
\email{kopecek@fi.muni.cz}\\
http://www.fi.muni.cz/\~{}kopecek/
}

\begin{document}

\maketitle

\begin{abstract}
An application of dialogue systems for developing computer programs is described and discussed in the paper. The concept of generating program source code by means of a dialogue involves combining strategies with system and user initiative. The strategy with system initiative safely navigates the user, whereas the strategy with user initiative enables a quick and effective creation of the desired constructions of the source code and collaboration with the system using obtained knowledge to increase the effectiveness of the dialogue. The described system, which was initially developed for visually impaired users, can also be used by novice programmers as a tool for learning programming languages. 
\end{abstract}

\section{Introduction}
The idea of generating source code by means of dialogue systems was initially connected with the problem how to help blind and visually impaired programmers to create computer programs \cite{batusek,jergova,tsd98,london}. The asset of this approach lies in eliminating most of the syntactic errors that can appear in standard programming languages like C++, Java and Prolog by means of inquiring the user to obtain the necessary information. The system also supports automatic generation of some parts of the program (e.g. declarations of variables, parts of the programming language that can be derived from given parameters, etc.).

Dialogue strategy based on inquiring (passive strategy from the user's point of view) is a strategy with the initiative of the system. The user plays a passive role in answering the inquiries of the system. In the system, which is created for generating program source code, such a strategy is derived from a description of the programming language (a context-free grammar, a flowchart definition, etc.). 

Passive dialogue strategy ensures the generation of correct statements. However, as it can be demonstrated by simulations, using this strategy in all situations would be cumbersome, and therefore this strategy has to be combined with other approaches.

The basic feature of active strategy (strategy with the initiative of the user) consists in determining the structure of the generated statement by user description, which can be done either directly in a natural language, or (if we cannot master this problem fully) by describing the generated structure by appropriate  keywords. 

Active and passive strategies can be combined effectively with adaptive approaches, like estimating the user's skill and using it for adaptation of the system, and for adaptation of the system by learning. In what follows, we will discuss it in more detail.

\section{Generating the Dialogue Strategy with System Initiative}

Suppose we have a context-free grammar $G = (V, T, S, P)$ ($V$ is a finite set of nonterminals, $T$ a finite set of terminals, $S$ the start nonterminal and $P$ a finite set of productions of the form $u \rightarrow v$, where $u \in V$, $v \in (V \cup T)^*$. (In this section we use standard terminology of the theory of  formal languages, see e.g. \cite{gruska}.)

Our goal is to assign to $G$ a dialogue strategy that enables to generate an element from $L(G)$. Let $\Rightarrow$ be the derivation relation of the grammar G (see, e.g., \cite{gruska}) and let $S \Rightarrow w(i)$, where $w(i)$ is the sequence which is derived from the start nonterminal $S$ at a time point $i$. Suppose that
$$w(i) = {a_1}{u_1}{a_2}{u_2}{a_3}}...{a_t}{u_t}{a_{t+1}} \,\,\,   (*)$$      
where $u_{r}  \in V, a_{r}  \in T^*.$
The generated dialogue strategy first chooses a nonterminal $u_j$ belonging to the sequence. This can be based on the natural ordering of nonterminals (i.e., from left to right) or it can be, for instance, based on the expected depth of the derived tree (for which the nonterminal is the root). Another possibility is to let the user to choose the nonterminal. 

Now, suppose that all the productions that have $u_j$ on the left side are as follows:
$$u_j \rightarrow {c_{11}}{v_{11}}{c_{12}}{v_{12}} ... {c_{1m}}{v_{1m}}{c_{1 m+1}}$$
$$\vdots$$
$$u_j \rightarrow {c_{k1}}{v_{k1}}{c_{k2}}{v_{k2}} ... {c_{kn}}{v_{kn}}{c_{k n+1}}$$
where $v_{rs}  \in V, c_{rs}  \in T^*.$

The dialogue strategy then inquires the user to determine what next production will be used. If the user  chooses the production with the index $p$, the nonterminal $u_j$ in the expression $(*)$ will be overwritten by ${c_{p1}}{v_{p1}}{c_{p2}}{v_{p2}} ... {c_{pn}}{v_{pn}}{c_{p n+1}}$ and the process continues at the time point $i+1$.


Although this strategy generates a code free of syntactic errors, simulations of the dialogues show that it can be slow and ineffective in some cases. Let us see the following simplified example of a possible communication between the user (U) and the dialogue  system (S) by generating single C (C++) statement $s = 0;$
(the braces enclose the possible choices): \\
\\
S: \{labelled-statement; expression-statement; compound-statement;\\
 selection-statement; iteration-statement; jump-statement\} ?\\
U: expression-statement;\\
S: \{assignment-expression; expression, assignment-expression\} ?\\
U: assignment-expression;\\
S: \{non-conditional-assignment-expression; conditional-expression\} ?\\
U: non-conditional-assignment-expression;\\
S: /definition of non-conditional- assignment-expression/ \\
    Left hand side is: \{identifier; unary expression\} ? \\
U: identifier; \\
S: /definition of non-conditional- assignment-expression/
    input identifier! \\
U: s \\
S: OK 
    /definition of non-conditional- assignment-expression/ \\
    assignment operator is: \{ \verb!=; *=; /=; %=; +=; -=; <<=; >>=; &= ; ^=; !\} ?\\
U: = \\
S: OK \\
    /definition of non-conditional-assignment-expression/ \\
    Right hand side is: \{identifier; constant; string; expression; assignment-expression\} ? \\
U: constant; \\
S: /definition of non-conditional-assignment-expression/ 
    input constant! \\
U: 0 \\
S: OK \\
    /definition of non-conditional-assignment-expression is completed/ \\
    The assignment is: s = 0; \\ 
    /coming back to defining next block: name-of-the-block statement/ \\
\\
In this example, the formal form of the dialogue described above is enriched with simple system descriptions and messages that should help the user in generating the program. Also, the passive generating of the code stops when it is clearly not effective (in our example it is on the level when the user should define the left hand side variable and the right hand side constant. This example demonstrates the basic idea of the passive way of program generating and also clearly indicates that this approach has to be complemented by a strategy with user initiative.

\section{Dialogue Strategy with User Initiative}

The strategy with user initiative tries to determine the structure of the generated statement by user description, which can be formulated in natural language by means of appropriate  keywords. The above presented example can be shortened using this strategy as follows:\\
\\
U: * assign simple \\
S: /definition of non-conditional- assignment-expression/ \\
    input left hand side in the form of identifier!/  \\
U: s \\
etc. \\
\\
The character * indicates that the user takes initiative. This can be signalled by pressing a key or by a keyword. 'assign' is a keyword describing the chosen statement. 'simple' is a keyword which, in this case, says that the user demands the simple form of the corresponding construction. Hence, 'simple' is a keyword that belongs to the category of the keywords with general meaning. Other keywords in this category are, for instance:
\begin{itemize}
\item 'general' - demanding the general form of the specified construction, 
\item 'more simple' - demanding a simpler form of the specified construction, 
\item 'more general' - demanding a more general form of the specified construction, 
\item 'the same' - demands a repetition of the previously specified construction, 
\item 'often used' - demands a choice from the list of often used constructions, 
\item etc. 
\end{itemize}

	Using the active strategy the user tries to find a sufficiently precise characterization of the generated statement and the system tries to guess a probable type of the statement, which is characterized by the given keywords. Both the user and the system have to be ready to face a possible misunderstanding or inaccuracy by determining the statement. Possible ways to handle these situations are as follows:

A: If the system guessed a false type of the generated statement:
\begin{itemize}
\item add new keywords to the given ones and demand a new guess
\item cancel the turn and give another keywords
\item cancel the turn and switch to the "passive" way of generation.
\end{itemize}

B: If the system guessed an inaccurate type of the generated statement:
\begin{itemize}
\item add new keywords to the given ones and demand a new guess
\item demand a more general guess and then specify the right form
\item specify a correction (for instance, if one needs a labelled statement, specify "label")
\item cancel the turn and switch to the "passive" way of generation
\end{itemize}

Direct definition of the source code, which is a special case of the user initiative strategy, allows the user to create some constructions directly (without being navigated by the system). Using this strategy, the user is neither navigated nor has to use keywords, just simply defines the statement directly. The system checks the correctness of the statement  and acknowledges it. If the statement is not correct, the user has to make corrections or switch to other modes. The above example is then maximally shortened into just typing the statement. Clearly, this mode is effective provided that either the generated statement is very simple or the user is sufficiently experienced. On the other hand, this mode can be risky for more complex statements.

\section{Adaptation of the Dialogue Strategies}

The adaptation of dialogue strategies that are based on an estimation of the user's skill utilizes either a direct proclamation of the user (by setting an appropriate option indicating his or her skill and experiences) or
the analysis of the user's behaviour during the session.

Based on this estimation, the system may adapt its dialogue strategies, especially those that are related to on-line and context-sensitive help, to the structure of the list of offered possibilities, and to the type of guessed statements for the active generation.

Adaptation by learning is a method of restructuring the grammar (or assigning weights to some paths that appear to be more frequently used) and making shortcuts by learning from the previous sessions. An observed high frequency for a path indicates a need to create a shortcut.

On the other hand, it is clear that the number of shortcuts in the grammar has to be kept reasonable. To comply with this requirement, we can dynamically update active and passive (not allowed) shortcuts by allowing only a priori estimated number of active shortcuts and by switching the "activity" or "passivity" of a shortcut depending on the observed frequency.

Adaptation by estimation of the probable next statement is a strategy based on the prediction of the next statement. It seems to be obvious that the probability of what statement will be generated for a correct program depends on the previously used statements (more generally on the context). This can be used to make the estimation of the next statement more precise.

\section{Implementation and Applications}

The system has been developed as a multimodal dialogue system supported by a universal speech interface  (allowing direct speech input and output). 

An important feature of the system is using the informative speech and non-speech \cite{stevens} sounds to enable the user to be informed appropriately at each level of program generation. This is supported by a sophisticated multi-structural organization of the help and by adaptation of the system to the user abilities and practice.

The created data involve at any moment their whole history so that they can be edited in the same mode. Of course, the user can export them to usual text form which may be further processed by standard integrated environments. 

Even though the system was initially developed for visually impaired users, it can also be used by novice programmers and for teaching and learning programming languages. 

The effect of learning by using the system (see also \cite{poznan}) is related to the following aspects: 
\begin{itemize}
\item in the passive mode: this mode is used very frequently by inexperienced users who do not know properly the basic structure of the grammar and have to be navigated. The important feature is that the navigation also requires active participation of the user and that he gets a new relevant information in this context. Simultaneously, the user naturally aims to use more frequently the more effective active mode (which is however reachable only with some experience). Those features create feedback effect which strongly motivates the user.
\item in the active mode: this mode is more frequently used by more experienced users. Using this mode, the user learns by repetition of the relevant knowledge obtaining simultaneously new relevant information whenever he or she errs. The background of the system assistance encourages the user to use new statements and techniques.
\end{itemize}



\section{Conclusions}

Development of the dialogue systems oriented to generating program source code raises specific problems that can be partially solved by adaptive dialogue strategies. In the future work, we would like to perform further testing on the possible extensions and modification of the method described in this paper (also by WOZ simulation) to verify and enhance 
the effectiveness of the method. The further development of the dialogue strategies is directed especially towards enabling as much freedom in communication as possible.

\section*{Acknowledgement}
This research has been partially supported 
by the Czech Ministry of Education under  the Grant VS97028 and
by the Grant Agency of the Czech Republic under the Grant 201/99/1248.


\begin{thebibliography}{14}

\bibitem{batusek}
Batu\v sek, R., Kope\v cek, I.: User Interfaces for Visually Impaired People; in Proceedings of the 5th ERCIM  Workshop on User Interfaces for All, Dagstuhl, 1999, pp. 167-173.

\bibitem{jergova}
Kope\v cek, I., Jergov\' a, A.: Programming and Visually Impaired People; in Proceedings of the XV. World Computer Cnogress, ICCHP'98, Wien-Budapest, September 1998, pp. 365-372.

\bibitem{tsd98}
Kope\v cek, I.: Dialog Based Programming; Proceedings of the First Workshop on Text, Speech and Dialogue - TSD'98,
 1998, pp. 407-412. 

\bibitem{tsd99}
Kope\v cek, I.: Modeling the Information Retrieval Dialogue Systems; in Proceedings of the Workshop on Text, Speech and Dialogue - TSD'99, Lectures Notes in Artificial Intelligence 1692, Springer-Verlag, 1999, pp. 302-307

\bibitem{gruska}
Gruska, J: Foundations of Computing, International  Thompson  Computer Press,  London, New York, 1997.

\bibitem{london}
Kope\v cek, I.: Speech Sciences and Visually Impaired Students; In  Proceedings  of  the ESCA Workshop  on Method and  Tool  Innovations  for  Speech  Science  Education, University College London, April 1999, pp. 69-72.

\bibitem{poznan}
Kope\v cek, I.: Generating Source Code by Means of Dialogue and Applications for Learning and Teaching Programming Languages. In  Proceedings  of  the Conference EUNIS 2000, Poznan, pp. 60-67. 

\bibitem{stevens}
Stevens, R.D., Wright, P.C., Edwards, A.D.N., Brewster, S.A. (1996) An Audio Glance at Syntactic Structure Based on Spoken Form; Proceedings of the conference ICCHP'96 1996, Wien-Budapest,  pp. 627-635.

\bibitem{smith}
Smith, R.W., Hipp, R.D.: Spoken Natural Language Dialog Systems: A Practical Approach. Oxford University Press, 1994.
 
\end{thebibliography}


\end{document}





