Tell a PL researcher that you have a new programming language and one of the first things they want to know is whether you can do static analysis on it. Lucky for us, we can! But first, some background in this space:

Prior work on static analysis for surveys

I mentioned earlier that there is some prior work on using programming languages to address survey problems.

Static analysis in Topsl is constrained by the fact that Topsl permits users to define questions whose text depends on the answers to previous questions. Matthews is primarily concerned that each question is asked. While it can support randomization, this feature belongs to the containing language, Scheme, and so is not considered part of of the Topsl core. Although the 2004 paper mentions randomization as a feature that can be implemented, there is no formal treatment in any of the three Topsl-related publications.

If we also consider type-checking answer fields or enforce constraints on responses as static analysis, then most online survey tools, Blaise, QPL, and probably many more tools and services perform some kind of static analysis.

Static Analysis in SurveyMan

Surveys are interpreted by a finite state machine implemented in Javascript. To ensure that we don't cause undefined behavior, we must check that the csv is well-formed. After parsing, the SurveyMan runtime performs the following checks:

  • Forward Branch Since we require the survey to be a DAG, all branching must be forward. We can do this easily by comparing branch destination ids with the ids of the branch question's containing block. This check takes time linear in the block's depth.
  • Top Level Branch At the moment, we only allow branching to top level blocks. This check is constant.
  • Consistent Branch Paradigms Having one "true" branch question per top level block is critically important for our survey language. Every block has a flag for its "branch paradigm." This flag indicates whether there is no branching in the block, one branch question, or whether the block should emulate sampling behavior. This check ensures that for every block, if it has a parent or siblings the following relations hold:

    [table id=1 /]

    We use the following classification algorithm to assign branch paradigms:

    function getAllQuestionsForBlock
      input : a block
      output : a list of questions
    begin
      questions <- this block's questions
      if this block's branch paradigm is SAMPLE
        q <- randomly select one of questions
        return [ q ]
      else
        qList <- shuffled questions
        for each subblock b in this block
        begin
          bqList <- getAllQuestionsForBlock(b)
          append bqList to qList
        end
        return qList
      fi
    end


    function classifyBlockParadigm
      input : a block
      output : one of { NONE, ONE, SAMPLE }
    begin
      questions <- this block's questions
      subblocks <- this block's subblocks
      if every q in questions has a branch map
        branchMap <- select one branch map
        if every target block in branchMap is NULL
          return SAMPLE
        else
          return ONE
      else if one q in questions has a branch map
        return ONE
      else if there is no q in questions having a branch map
        for each b in subblocks
        begin
          paradigm <- classifyBlockParadigm(b)
          if paradigm is ONE
            return ONE
        end
        return NONE
      fi
    end

    The ONE branch paradigm gets propagated up the block hierarchy and pushes constraints down the block hierarchy. The SAMPLE branch paradigm pushes constraints down the block hierarchy, but has no impact on parent blocks. Finally, NONE is the weakest paradigm, as it imposes no constraints on its parents or children. All blocks are set to NONE by default and are overwritten by ONE when appropriate.

  • No Duplicates We check the features of each question to ensure that there are no duplicate questions. Duplicates can creep in if surveys are constructed programmatically.
  • Compactness Checks whether we have any gaps in the order of blocks. Block ordering begins at 1. This check is linear in the total number of blocks. (This check should be deprecated, due to randomized blocks.)
  • No branching to or from top level randomized blocks We can think of the survey as a container for blocks, and blocks as containers for questions and other blocks. The top-level blocks are those immediately contained by the survey. While we permit branching from randomizable blocks that are sub-blocks of some containing block, we do not allow branching to or from top-level randomized blocks. The check for whether we have branched from a top-level block is linear in the number of top-level blocks. The check for whether we try branching to a top-level randomizable block is linear in the number of questions.
  • Branch map uniformity If a block has more than one branch question, then all of its questions must be branch questions. The options and their targets are expected to be aligned. In the notation we used in a previous post, for a survey csv $$S$$, if one question, $$q_1$$ in the block spans indices $$i,...,j$$ and another question $$q_2$$ spans indices $$k,...,l$$, then we expect $$S[BLOCK][i] = S[BLOCK][k] \wedge ... \wedge S[BLOCK][j] = S[BLOCK][l]$$.
  • Exclusive Branching Branching is only permitted on questions where EXCLUSIVE is true.

The above are required for correctness of the input program. We also report back the following information, which can be used to estimate some of the dynamic behavior of the survey:

  • Maximum Entropy
    For a survey of $$n$$ questions each having $$m_i$$ responses, we can trivially obtain a gross upper bound on the entropy on the survey : $$n \log_2 (\text{max}(\lbrace m_i : 1 \leq i \leq n \rbrace))$$.
  • Path Lengths

    • Minimum Path Length Branching in surveys is typically related to some kind of division in the underlying population. In the previous post, we showed how branching could be used to run two versions of a survey at the same time. More often branching is used to restrict questions by relevance. It will be appropriate for some subpopulations to see certain questions, but not others.

      When surveys have sufficient branching, it may be possible for some respondents to answer far fewer questions than the survey designer intended -- they may "short circuit" the survey. Sometimes this is by design; if we are running a survey but are only interested in curly-haired respondents, we have no way to screen the population over the web. We may design the survey so that answering "no" to "Do you have curly hair?" sends the respondent straight to the end. In other cases, this is not the intended effect and is either a typographical error or is a case of poor survey design.

      We can compute minimum path length using a greedy algorithm:

      function minPathLength
        input : survey
        output : minimum path length through the survey
      begin
        size <- 0
        randomizableBlocks <- randomizable top level blocks
        staticBlocks <- static top level blocks
        branchDestination <- stores block that we will branch to
        for block b in randomizableBlocks
        begin
          size <- size + length(getAllQuestionsForBlock(b))
        end
        for block b in staticBlocks
        begin
          paradigm <- b's branch paradigm
          if branchDestination is initialized but b is not branchDestination
            continue
          fi
          size <- size + length(getAllQuestionsForBlock(b))
          if branchDestination is initialized and set to b
            unset branchDestination
          fi
          if paradigm = ONE
            branchMapDestinations <- b's branch question's branch map values
            possibleBlockDestinations <- sort branchMapDestinations ascending
            branchDestination <- last(possibleBlockDestinations)
          fi
        end
        return size
      end

    • Maximum Path Length Maximum path length can be used to estimate breakoff. This information may also be of interest to the survey designer -- surveys that are too long may require additional analysis for inattentive and lazy responses.

      Maximum path length is computed using almost exactly the same algorithm as min path length, except we choose the first block in the list of branch targets, rather than the last.

      We verified these algorithms empirically by simulating 1,000 random respondents and returning the minimum path.

    • Average Path Length Backends such as AMT require the requester to provide a time limit on surveys and a payment. While we currently cannot compute the optimal payment in SurveyMan, we can use the average path length through the survey to estimate the time it would take to complete, and from that compute the baseline payment.

      The average path length is computed empirically. We have implemented a random respondent that chooses paths on the basis of positional preferences. One of the profiles implemented is a Uniform respondent; this profile simply selects one of the options with uniform probability over the total possible options. We run 5,000 iterations of this respondent to compute the average path length.

      Note that average path length is the average over possible paths; the true average path length will depend upon the preferences of the underlying population.