Dialogue Manager Programming Language (DMPL)

Final Community Group Report

Latest editor's draft:
https://github.com/w3c/dmpl
Editor:
Nishant Shukla
Authors:
Nelson Solano
Victor Zhang

Copyright © 2019 the Contributors to the Dialogue Manager Programming Language (DMPL) Specification, published by the Conversational Interfaces Working Group under the W3C Community Final Specification Agreement (FSA). A human-readable summary is available.

Abstract

This specification defines the syntax and semantics of a dialogue manager programming language (DMPL). The user specifies the states (i.e. fluents), how they change (i.e. actions), and which are preferred (i.e. utility). These three components characterize a task, so we call DMPL a task-oriented programming language. The interpreter of the language should resolve the task by identifying and executing actions that maximize utility.

Status of This Document

This specification was published by the Conversational Interfaces Working Group. It is not a W3C Standard nor is it on the W3C Standards Track. Please note that under the W3C Community Final Specification Agreement (FSA) other conditions apply. Learn more about W3C Community and Business Groups.

If you wish to make comments regarding this document, please send them to public-conv@w3.org (subscribe, archives).

1. Conformance

As well as sections marked as non-normative, all authoring guidelines, diagrams, examples, and notes in this specification are non-normative. Everything else in this specification is normative.

2. Introduction

This specification aims to decouple the representation of dialogue from its execution. For example, conversational interfaces employ artificial intelligence in different ways: finite state machines, path planning, or reinforcement learning systems. Regardless of the execution framework, the logical representation may be shared. An agreed upon representation of dialogue allows content writers to author and share conversational experiences without being distracted by the underlying runtime.

2.1 Scope

This section is informative.

This document is limited to specifying the syntax and semantics for a task-oriented language for interactive behavior. One example application of DMPL is an authoring tool to be used on a regular basis by a non-technical content writer. Another use-case of DMPL is exporting and importing dialogue content authored by writers from different web platforms. Technologies closely related to these use-cases are in scope.

2.2 Goals and Motivation

This section is informative.

DMPL is a task-oriented programming language, which may be better explained by extending Microsoft's Function Programming vs. Imperative Programming table, shown below.

Imperative Functional Task-Oriented
Programmer Focus How to perform tasks (algorithms) and how to track changes in state What information is desired and what transformations are required Why an action is taken and how information changes
State Changes Important Non-existant (for purely functional languages) Important
Order of Execution Programmer is mostly responsible Hybrid resposibility Compiler is mostly responsible
Loops For/While, Recursion Recursion None, loops are implicit
Primary Manipulation Unit Instances of structures or classes Functions Utility

3. Language Syntax

This section is normative.

This section of the document defines the types used within this specification using EBNF notation with corresponding railroad diagrams.

3.1 Atomic Types

3.1.1 literal

A literal is a terminal atom that may be assigned to a variable, used in a dictionary, or used as an operand to build an expression. 

literal ::= string | number | boolean | 'null'
Literal rail-road diagram
Figure 1 Literal

3.1.2 boolean

A boolean may take on values true or false. 

boolean ::= 'true' | 'false'
Boolean rail-road diagram
Figure 2 Boolean

3.1.3 name

A name is a sequence of characters conforming to those in the XML standard. 

name ::= [ http://www.w3.org/TR/xml-names/#NT-NCName ]
Name rail-road diagram
Figure 3 Name

3.1.4 quote_start

A quote_start is the starting quotation mark, which indicates the beginning of a string. 

quote_start ::= '"' '`'
Quote-start rail-road diagram
Figure 4 Quote-start

3.1.5 quote_close

A quote_close is the ending quotation mark, which indicates the termination of a string. 

quote_close ::= '`' '"'
Quote-close rail-road diagram
Figure 5 Quote-close

3.1.6 string

A string literal represents a finite sequence of characters. It is surrounded by starting and ending quotation marks. 

string ::= quote_start name quote_close
String railroad diagram
Figure 6 String
Example 1: string literal 
"`hello`"

3.1.7 digit

A digit represents a real valued integer in the range [0-9]. 

digit ::= [0-9]
Digit railroad diagram
Figure 7 Digit

3.1.8 number

A number literal may represent either a positive or negative decimal value. 

number ::= '-'? ( digit+ ( '.' digit* )? | '.' digit+ )
Number railroad diagram
Figure 8 Number
Example 2: number literal 
0.2

3.2 Container Structures

3.2.1 variable

A variable is a named reference to the result of evaluating an expression. 

variable :: = '"' name '"'
Variable railroad diagram
Figure 9 Variable
Example 3: variable 
"num_correct_answers" // => 3
A variable should not be confused with a string, which uses backticks (`) like so:
Example 4: string uses backticks 
"`num_correct_answers`" // => "num_correct_answers"

3.2.2 dictionary

A dictionary is a structure that maps data in key-value pairs. The keys and values are all evaluated. The keys can be either strings or variables that evaluate to strings. 

dictionary : : = '{' ( string | variable ) ':' expression
                 ( ',' ( string | variable ) ':' expression )* '}'
Dictionary railroad diagram
Figure 10 Dictionary
Example 5: dictionary 
{"`age`": "x", "`score`": 10, "`name`": "`Joe`"}

3.2.3 expression

An expression may be evaluated, and that result is stored in memory to be referenced later. An expression may be denoted by a JSON array, in which case it is also called a function. The first element of the array represents the operator of the function. The operator can be either a string or a variable that evaluates to a string. All remaining elements of the array constitute the operands. 

expression ::= literal
             | variable
             | dictionary
             | '[' ( literal | variable ) ( ',' expression )* ']'
Expression railroad diagram
Figure 11 Expression
Return Type Operator Example
string 
"++"
Example 6 
["++", "`hello `", "`world`"] // => "`hello world`"
number 
"+"
Example 7 
["+", 1, 2] // => 3
number 
"-"
Example 8 
["-", 5, 3] // => 2
number 
"*"
Example 9 
["*", 2, 4] // => 8
number 
"/"
Example 10 
["/", 1, 2] // => 0.5
number 
"%"
Example 11 
["%", 168, 2] // => 0
list 
""
Example 12 
["", 1, 2, 3, 4, 5] // => [1, 2, 3, 4, 5]
list 
"enumFromTo"
Example 13 
["enumFromTo", 1, 5] // => [1, 2, 3, 4, 5]
list 
"enumFromThenTo"
Example 14 
["enumFromThenTo", 1, 3, 10] // => [1, 3, 5, 7, 9]
boolean 
"=="
Example 15 
["==", 1, 2] // => false
boolean 
"!="
Example 16 
["!=", 1, 2] // => true
boolean 
">"
Example 17 
[">", 2, 3] // => false
boolean 
">="
Example 18 
[">=", 2, 3] // => false
boolean 
"<"
Example 19 
["<", 2, 3] // => true
boolean 
"<="
Example 20 
["<=", 2, 3] // => true
boolean 
"&&"
Example 21 
["&&", true, false] // => false
boolean 
"||"
Example 22 
["||", true, false] // => true
boolean 
"!"
Example 23 
["!", false] // => true
boolean 
"in"
Example 24 
["in", 3, ["", 1, 2, 3]] // => true
boolean 
"input"
Example 25 
["input"] // => true if there's an input
Example 26 
["input", "yes"] // => true if there's an input and it equals "`yes`"
boolean 
"return"
Example 27 
["return"] // => true if there's an return result from callee
boolean 
"exists"
Example 28 
["exists", "`is_greeted`"] // => false if variable not initialized
dynamic 
"get"
Example 29 
["get", 0, ["", 1, 2, 3]] // => 1
Example 30 
["get", "`a`", {"`a`": 1}] // => 1
dynamic 
"pick"
Example 31 
["pick", ["", 1, 2, 3]] // => 1, 2, or 3 uniformly at random

3.3 Statements

3.3.1 statement

A statement may be a non-terminal such as do or fork, or a terminal such as effect. Optionally, statements may contain condition, await, or once flags. 

statement ::= '{' ( condition ',' )?
              ( await ',' )?
              ( once ',' )?
              ( effect | do | fork ) '}'
Statement railroad diagram
Figure 12 Statement

3.3.2 condition

A condition is a boolean expression that runs the statement if the expression evaluates to true. A condition check takes priority over other parts of the statement. If a statement does not explicitly contain a condition, then that statement's condition is trivially true. 

condition : : = '"if"' ':'  expression
Condition railroad diagram
Figure 13 Condition
Example 32: condition 
"if": [">", "num_wrong_answers", 3]

3.3.3 await

An await blocks execution until a boolean expression evaluates to true. 

await ::= '"await"' ':' expression
Await railroad diagram
Figure 14 Await
Example 33: await 
"await": ["input"]

3.3.4 once

A once flag specified whether the statement can only be run once. By default, the once flag is set to false. 

once ::= '"once"' ':' boolean
Once railroad diagram
Figure 15 Once
Example 34: once 
"once": true

3.3.5 effect

An effect is a terminal node, meaning it does not produce more statements. There are 6 types of effects. 

effect ::= act | set | def | run | use | pop
Effect railroad diagram
Figure 16 Effect

3.3.6 act

An act represents an action specified by evaluating the expression. The result is interpreted by a client. For example, the payload of the act statement may be represented using Behavior Markup Language (BML). The client is then responsible for realizing the behavior defined in the act message. 

act ::= '"@act"' ':' expression
Act railroad diagram
Figure 17 Act
Example 35: act 
"@act": {
  "`object`": "`tutor`",
  "`action`": "`say`",
  "`params`": {"`intent`": "`greeting`"}
}

3.3.7 set

A set updates the values of the variables, where the names of the variables and the updated values are specified by evaluating the corresponding expressions. The expression specifying the names of the variables is allowed to contain variables (although static code analysis and possible optimizations would be more difficult), and must evaluate to a string, a list consisting of only strings, or a dictionary consisting of only strings. 

set ::= '"@set"'  ':' expression ',' '"val"' ':' expression
Set railroad diagram
Figure 18 Set
Example 36: set 
"@set": "`is_user_greeted`", "val": true
Example 37: set (unpack) 
"@set": ["", "`is_user_greeted`", "`num_questions`"], "val": ["", true, 7]

3.3.8 def

A def defines a new expression operator that can be used later in the code. The signature of the new expression operator is specified by an expression that must evaluate to a list of strings, which maps to the operator name followed by the argument names. These argument names are valid only for this scope, and may shadow global variables. The result is returned by a pop statement. 

def ::= '"@def"' ':' expression ',' '"val"' ':' statement
Def railroad diagram
Figure 19 Def
Example 38: def 
"@def": ["", "`inc`", "`x`"], "val": {"@pop": ["+", 1, "x"]}

3.3.9 run

A run calls DMPL code in another component, optionally passing in arguments. The name of the called component is specified by an expression that must evaluate to a string. The current variables stored in memory are remembered later. 

run ::= '"@run"' ':' expression ( ',' '"args"' ':' expression )?
Run railroad diagram
Figure 20 Run
Example 39: run 
"@run": "`Outro`"
Example 40: run with args 
"@run": "`Question`", "args": ["", "`What's the largest planet?`", "`Jupiter`"]

3.3.10 use

A use imports variables and expression operators defined in another component. The name of the imported component is specified by an expression that must evaluate to a string. The variable and expression operator names can be optionally specified, or all variables and expression operators will be imported. It's similar to from os import path notation in Python. 

use ::= '"@use"' ':' expression ( ',' '"import"' ':' expression )?
Use railroad diagram
Figure 21 Use
Example 41: use 
"@use": "`MathExpressions`", "import": ["", "`inc`", "`square`", "`exp`"]

3.3.11 pop

A pop quits execution on the current DMPL code, pops the fluent-state from the stack, and resumes execution from the previous run location. 

pop ::= '"@pop"' ':' expression
Pop railroad diagram
Figure 22 Pop
Example 42: pop 
"@pop": true

3.3.12 do

A do statement specifies a list of statements to be executed. 

do ::= '"@do"' ':' '[' ( statement ( ',' statement )* )? ']'
Do railroad diagram
Figure 23 Do
Example 43: do 
"@do": [
  {"@act": "a"},
  {"@act": "b"},
  {"@act": "c"}
]

3.3.13 fork

A fork statement specifies the branch-like behavior of the list of statements that follow. Only one is chosen, and the strategy to pick one may be provided using the scheme attribute. By default, a greedy scheme is used, meaning the first statement whose condition is met will be chosen. More complicated schemes, such as depth-first-search or Monte Carlo Tree Search may be indicated, leaving the implementation up to the interpreter. 

fork ::= '"@fork"' ':' '[' ( statement ( ',' statement )* )? ']' ( ',' scheme )?
Fork railroad diagram
Figure 24 Fork

When no scheme is provided, a fork is essentially the traditional if/elif/else logical flow:

Example 44: fork 
"@fork": [
  {"if": "is_user_greeted", "@act": "a"},
  {"if": [">", "num_wrong_answers", 3], "@act": "b"},
  {"@act": "c"}
]

Providing a scheme allows stochastic behavior to take place:

Example 45: fork with scheme 
"scheme": {"depth": 3}, "@fork": [
  {"@set": "`do_action_1`", "val": "true"},
  {"@set": "`do_action_2`", "val": "true"},
  {"@set": "`do_action_3`", "val": "true"},
  {"if": "is_entry_condition_met", "@set": "`do_action_4`", "val": "true"},
  {"if": false, "@act": "`never reached`"}
]

3.3.14 scheme

A scheme is associated with a fork statement, and it describes the fork branch resolution strategy. 

scheme ::= '"scheme"' ':' expression
Scheme railroad diagram
Figure 25 Scheme
Example 46: scheme 
{"depth": 3}

4. Examples

This section is informative.

This section details DMPL conforming example programs.

The following sends "hello world" to the action realizer.

Example 47: Hello World! 
{
  "@act": "`hello world`"
}

Two actions can be sent sequentially.

Example 48: Do-statement 
{
  "@do": [
    {"@act": "`hello`"},
    {"@act": "`world`"}
  ]
}

Fork statements allow branching logic.

Example 49: If-Else Control Flow 
{
  "@fork": [
    {"if": ["==", ["+", 2, 2], 4], "@act": "`this statement is run`"},
    {"@act": "`never reached`"}
  ]
}

Variables can be set and accessed like so.

Example 50: Variables 
{
  "@do": [
    {"@set": "`a`", "val": 1},
    {"@set": "`b`", "val": 2},
    {"@set": "`c`", "val": ["+", "a", "b"]}
  ]
}

Here we define a new expression called inc which takes an argument called x.

Example 51: Define New Expression 
{
  "@do": [
    {"@def": ["", "`inc`", "`x`"], "val": {"@pop": ["+", 1, "x"]}},
    {"@act", ["`inc`", 5]}
  ]
}

The set statement allows unpacking a list.

Example 52: Unpacking an Array 
{
  "@do": [
    {"@set": "`content`", "val": ["", "`What's the biggest planet?`", "`Jupiter`"]},
    {"@set": ["", "`Prompt`", "`Correct-Answer`"], "val": "`content`"}
  ]
}

Run an external file and pass in arguments. The return value can be considered in the following fork statement.

Example 53: Running Components 
{"@do":
  {"@run": "`Question`", "args": ["", "`What's the biggest planet?`", "`Jupiter`"]},
  {"await": ["return"], "@fork": [
    {"if": ["return", true], "@set": "`score`", "val": 100},
    {"@set": "`score`", "val": 0}
  ]}
}

Expressions and variabels may be imported from other files.

Example 54: Importing Expressions 
{
  "@do": [
    {"@use": "`MathExpressions`", "import": ["", "`square`", "`exp`"]},
    {"@act": ["==", ["`square`", 6], ["`exp`", 6, 2]]}
  ]
}

To halt until a user input is supplied, the await flag on a fork may be used.

Example 55: Input Handling 
{
  "@do": [
    {"@act": "`are you ready?`"},
    {"await": ["input"], "@fork": [
      {"if": ["input", "`yes`"], "@act": "`great`"},
      {"if": ["input", "`no`"], "@act": "`no problem`"}
    ]}
  ]
}

More immersive dialogue can be achieved by setting and checking variables, such as greeted.

Example 56: Greet and Ask Question 
{
  "scheme": {"depth":  2}, "@fork": [
    {"if": ["!", ["exists", "`greeted`"]], "@set": "`greeted`", "val": false},
    {"if": ["!", "greeted"], "@do": [
      {"@act": "`hello`"},
      {"@set": "`greeted`", "val": true}
    ]},
    {"if": "greeted", "@do": [
      {"@act": "`how are you?`"},
      {"@set": "`asked_feelings`", "val": true},
      {"await": ["input"], "@fork": [
        {"if": ["input", "`good`"], "@act": "`great`"}
      ]}
    ]}
  ]
}

More complete question and answering scenarios may be constructed.

Example 57: Planet Trivia 
{
  "@fork": [
    {"if": ["!", ["exists", "`Init`"]], "@do": [
      {"@set": "`Init`", "val": true},
      {"@set": "`Wrong-Counter`", "val": 0},
      {"@set": "`Is-Hint1-Given`", "val": false},
      {"@set": "`Is-Hint2-Given`", "val": false},
      {"@set": "`Is-Answer-Given`", "val": false},
      {"@set": "`Num-Hints-Given`", "val": 0},
      {"@set": "`Question`", "val": "`What's the biggest planet?`"},
      {"@set": "`CA`", "val": "`planet.jupiter`"},
      {"@set": "`CA-Response`", "val": "`Exactly!`"},
      {"@set": "`WA1`", "val": "`planet`"},
      {"@set": "`WA1-Response`", "val": "`Nope. That's not the biggest`"},
      {"@set": "`WA2`", "val": "`nonplanet`"},
      {"@set": "`WA2-Response`", "val": "`That's not a planet`"},
      {"@set": "`Hint1`", "val": "`It has a big red spot`"},
      {"@set": "`Hint2`", "val": "`It's name begins with the letter J`"},
      {"@set": "`Answer`", "val": "`The biggest planet is Jupiter`"},
      {"@set": "`Hint-Announcement`", "val": "`Here's a hint`"}
    ]},
    {"@fork": [
      {"if": ["&&", ["<=", "Wrong-Counter", 3], ["!", "Is-Answer-Given"]], "@do": [
        {"@act": "Question"},
        {"@fork": [
          {"if": ["input", "CA"], "@do": [
            {"@act": "CA-Response"},
            {"@set": "`Is-Answer-Given`", "val": true}
          ]},
          {"if": ["input", "WA1"], "@do": [
            {"@act": "WA1-Response"},
            {"@set": "`Wrong-Counter`", "val":  ["+", 1, "Wrong-Counter"]}
          ]},
          {"if": ["input", "WA2"], "@do": [
            {"@act": "WA2-Response"},
            {"@set": "`Wrong-Counter`", "val":  ["+", 1, "Wrong-Counter"]}
          ]},
          {"@do": [
            {"@set": "`Wrong-Counter`", "val":  ["+", 1, "Wrong-Counter"]}
          ]}
        ], "await": ["input"]}
      ]},
      {"if": ["&&", ["!", "Is-Hint1-Given"], ["==", "Wrong-Counter", 1]], "@do": [
        {"@act": "Hint-Announcement"},
        {"@act": "Hint1"},
        {"@set": "`Is-Hint1-Given`", "val": true}
      ]},
      {"if": ["&&", ["!", "Is-Hint2-Given"], ["==", "Wrong-Counter", 2]], "@do": [
        {"@act": "Hint-Announcement"},
        {"@act": "Hint2"},
        {"@set": "`Is-Hint2-Given`", "val": true}
      ]},
      {"if": ["&&", ["!", "Is-Answer-Given"], ["==", "Wrong-Counter", 3]], "@do": [
        {"@act": "Answer"},
        {"@set": "`Is-Answer-Given`", "val": true}
      ]}
    ], "scheme": {"depth": 3}}
  ]
}

Here's how to handle global interruptions from the user.

Example 58: Interruptions 
{"scheme": {depth: 1}, "@fork": [
  {"@do": [
    {"@act": "`What's your favorite color?`"},
    {"await": ["input"], "@fork": [
      {"if": ["input", "`red`"], "@act": "`That's my favorite color, too!`"}
      {"@act": "`I've never heard of it`"}  
    ]}
  ]},
  {"if": ["input", "`want to quit`"], "@act": "bye"}
]}

6. References

This section is informative.

The primitive data types used and defined within this spec were influenced by ISO/IEC 11404. The conforming DMPL JSON syntax was influenced by json.org and jsonapi.org. The JSON Syntax defined within this document was developed using EBNF. The railroad diagrams were genereated using raildroad diagram generator.