{"size": 12254, "ext": "scrbl", "max_stars_repo_path": "sparse.scrbl", "max_stars_repo_name": "ricky-escobar/sparse", "max_stars_repo_stars_event_min_datetime": "2017-10-19T05:36:42.000Z", "max_stars_repo_stars_event_max_datetime": "2018-05-21T01:47:57.000Z", "max_issues_repo_path": "sparse.scrbl", "max_issues_repo_name": "ricky-escobar/senior-project", "max_issues_repo_issues_event_min_datetime": "2017-10-17T04:29:33.000Z", "max_issues_repo_issues_event_max_datetime": "2017-10-17T04:29:33.000Z", "max_forks_repo_path": "sparse.scrbl", "max_forks_repo_name": "ricky-escobar/senior-project", "max_forks_repo_forks_event_min_datetime": "2017-10-17T00:35:32.000Z", "max_forks_repo_forks_event_max_datetime": "2017-10-17T04:15:14.000Z"}
{"max_stars_count": 4, "max_issues_count": 1, "max_forks_count": 2, "avg_line_length": 41.1208053691, "max_line_length": 95, "alphanum_fraction": 0.7120124041}
#lang scribble/manual

@(require (for-label "main.rkt"))

@title{Sparse: Test Generation for Simple S-expression Language Parsers}

 Sparse is a tool (written in Racket) for
 generating test cases for parsers for simple S-expression
 languages. It is intended primarily for use by instructors
 of Programming Languages classes in which students implement
 a simple S-expression-based programming language. It takes
 as input a description of the grammar of the language to be
 implemented and produces test cases for the students'
 parsers.

@section{Motivation}

Producing test cases for parsers by hand is tedious and
difficult to do exhaustively. In addition, it is likely that
students will have to implement several different versions
of the language, in which case several different sets of
test cases must be maintained. Furthermore, if any changes
to the language are made from term to term, the test cases
must be updated--and doing so may not always be a simple
find-and-replace. It would be nice to have a tool which
automatically generates exhaustive test cases based solely
on the language's grammar. This is exactly what Sparse does.

@subsection{Example}

Consider the following grammar for a simple language (dubbed
PHYM4) which has conditionals, local variable binding,
lambdas, function applications, numbers, strings, and
identifiers:

@codeblock|{
    Expr = {if Expr Expr Expr}
         | {var {Id = Expr} ... Expr}
         | {lam {Id ...} Expr}
         | {Expr Expr ...}
         | Number
         | String
         | Id
}|

Here, @racket[Number], @racket[String], and @racket[Id] are
not to be taken literally, but rather as placeholders for
literal numbers, strings, and identifiers. Additionally,
@racket[if], @racket[var], @racket[lam], and @racket[=] are to be forbidden as
identifiers. Built-in operations, functions, and constants
like @racket[+], @racket[*], @racket[<=], @racket[substring], or @racket[true] are treated like
any other identifier from the point of view of this language
and so are not treated specially by the grammar. An example
program from this language is

@codeblock|{{{lam {x y} {if {<= x y} x y}} 5 4}}|

which introduces a function to determine the minimum of two
numbers, and then applies it to 5 and 4. Note, that we use
braces as delimiters instead of parentheses to distinguish
this tiny language from Racket. This language is very
simple, and yet writing a suite of input programs to test
students' parsers would be tedious--and would likely fail to
be comprehensive.

Sparse takes as input a description of the grammar which is
not unlike the grammar shown above. It is worth noting here
the largest limitation of Sparse. Sparse's input grammar may
only have one nonterminal. In this example, this is @racket[Expr].
For languages whose grammars have more than one nonterminal,
this can be worked around by only generating test cases for
the core expression grammar, which is more likely to be able
to be expressed as a grammar with one nonterminal, and
leaving the full language to be tested with manually-written
tests.

@codeblock|{
    (define phym4-grammar
      '([true false null + - * / eq? <= substring array new-array aref aset! begin]
        [lam = var if]
        [Expr
         {if Expr Expr Expr}
         {Expr Expr ...}
         {var {[id] = Expr} ... Expr}
         {lam {[id] ...} Expr}
         [id]
         [string "Hello" "World" ""]
         [number 0 1 -1 2.2 -22/7]]))
}|


The details of the format of the input grammar are described
below. Using this grammar, one can call
@racket[generate-valid-testcase] to generate one large test case
which will test to make sure the student's parser accepts
all valid programs. The following is produced for the
grammar defined above:

@codeblock|{
    {if {lam {} {lam {} {{lam {} {var {substring = {lam {} {if {{{var {/ = {{if {var {- =
     {var {+ = {if {if true {lam {true false null +} false} {lam {- * /} "Hello"}} {null
     {lam {eq? <=} 0} {"World" {var {true = +} {1 {if "" {var {false = "Hello"} {var {null
     = -1} {if 2.2 {if {var ""} - {{{{var /} -22/7} "World"} *}} {var 0}}}} {if {var {lam
     {substring} {if {if <= substring -1} 1 "World"}}} "Hello" eq?}} array}} new-array aref}
     aset! begin} a}} b}} {* = c} d} e f}}} {eq? = g} {<= = h} i}}} j k}}} {array = l}
     {new-array = m} {aref = n} o}}}}} p q}}|

Additionally, one can call @racket[generate-invalid-testcases] to
generate a list of test cases which do *not* conform to the
grammar to make sure that the student's parser rejects all
invalid programs. The following are produced for the grammar
defined above.

@codeblock|{
{lam true false null}
{if lam "Hello" "World"}
{if 0 lam 1}
{if + - lam}
{}
{if}
{if ""}
{if -1 "Hello"}
{if 0 "Hello" eq? "World"}
{if <= 1 -1 substring ""}
{if "Hello" array 2.2 new-array "World" -22/7}
{= aref}
{"" =}
{lam {true = e} f}
{var {lam = ""} "World"}
{var {false lam 1} 1}
{var {null = var} j}
{var {} ""}
{var {+} -1}
{var {- =} k}
{var {eq? = g "World"} l}
{var {<= = 2.2 h ""} "World"}
{var {substring = -22/7 i "Hello" 0} -22/7}
{var {array = m} if}
{var}
{var {new-array = ""}}
{var {begin = "World"} o ""}
{var {a = -1} 2.2 p "Hello"}
{var {b = q} -22/7 r "World" 0}
{= {true} s}
{lam {lam} ""}
{lam {aref} =}
{lam}
{lam {aset!}}
{lam {b} 2.2 w}
{lam {c} "Hello" -22/7 x}
{lam {d} "World" 0 y ""}
lam
var}|

Since the "valid" test case produced is so large, it would
likely not be very enlightening to a student trying to
understand where exactly their parser is failing. To help
alleviate this, Sparse includes a utility for producing
minimal failing test cases for a student's parser. For
example, for one student's parser, the following minimal
failing test cases were identified:

@codeblock|{
{lam {true false null +} false}
{lam {- * /} "Hello"}
{lam {eq? <=} 1}
{lam {array} 0}
{var {false = "World"} x}
{var {+ = 0} x}
}|

Here, the student's mistake was forbidding the built-ins as
parameter names; the language's grammar and semantics allow
redefining the names. It is worth noting that this student
had actually passed all of the instructor's original test
cases. Since the instructor's test cases only tried
redefining a built-in once, a student whose submission was
rejected the first time could simply special-case that one
built-in and resubmit their assignment successfully.
Manually writing test cases which redefine each built-in is
rather tedious and requires a fair bit of foresight on the
part of the instructor to know that that is an area where
students might mistakes. By automating the generation of
test cases, we can both reduce the tedium of writing test
cases and make the test suite more comprehensive.

@subsection{Usage}

@defmodule[sparse]{Sparse exposes six functions:
 @racket[generate-valid-testcase], @racket[generate-invalid-testcases],
 @racket[generate-valid-testcase-for-minimization],
 @racket[conforms-to-grammar?]
 @racket[produce-minimum-failing-testcases], and
 @racket[strip-minimization-info].}

The first four of these functions take an S-expression
representing the grammar for which to generate test cases.
Several examples are provided in `example-grammars.rkt`
Consider the example grammar from before:

@codeblock|{
    (define phym4-grammar
      ;; The first list is for any legal identifiers you want Sparse to use explicitly.
      ;; This can be useful if you think students might forbid identifiers that are legal.
      '([true false null + - * / eq? <= substring array new-array aref aset! begin]
        ;; The second list is for the symbols that are not legal identifiers
        [lam = var if]
        ;; The third list is for the production rules of the grammar. The first element
        ;; should be a symbol for the grammar's nonterminal.
        ;; Unfortunately, Sparse does not support more than one nonterminal.
        [Expr
         ;; The production rules. Any numbers and symbols other than the name of
         ;; nonterminal are treated as literals.
         {if Expr Expr Expr}
         ;; '...' means that the term immediately to the left may appear zero or more times.
         {Expr Expr ...}
         ;; [id] (or (id) or {id}) refers to valid identifiers. This will use the
         ;; identifiers provided above, as well as the letters of the alphabet a-z.
         {var {[id] = Expr} ... Expr}
         {lam {[id] ...} Expr}
         [id]
         ;; This represents any string. At least one example string to use must be provided.
         [string "Hello" "World" ""]
         ;; This represents any number. At least one example number to use must be provided
         [number 0 1 -1 2.2 -22/7]]))
}|

@defproc[(generate-valid-testcase [grammar grammar?]) s-expression?]{
 Using the grammar, produces one large S-expression which
 conforms to the grammar and is comprehensive in the
 following sense: each different production rule in the
 grammar will be used in place of each instance of a
 nonterminal in each production rule. For example, using the
 above grammar, the produced S-expression is guaranteed to
 have a subexpression like @code|{{if _ {var {_ = _} _} _}}|. A
 @racket[var] expression is guaranteed to appear in each of the
 three subexpressions of an @racket[if] expression. Likewise, each
 different 'type' of expression is guaranteed to appear in
 each spot where a subexpression is allowed. This process is
 deterministic; there's no point in generating multiple
 expressions from the same grammar.}

@defproc[(generate-invalid-testcases [grammar grammar?]) (listof s-expression?)]{
 Using the grammar,
 produces a list of simple S-expressions which do not conform
 to the grammar. The produced S-expressions are typically
 invalid because they use illegal identifiers or because they
 have incorrect lengths of lists. For instance, the above
 grammar will produce expressions that use @racket[lam] in places
 where @racket[lam] is not allowed, and will create @racket[if] expressions
 that don't have exactly three subexpressions.}

@defproc[(generate-valid-testcase-for-minimization [grammar grammar?]) s-expression?]{
 Produces an expression just like @racket[generate-valid-testcase],
 but that is additionally annotated with information that
 lets the test case minimization know which parts of the
 S-expression it is allowed to recurse into. Use
 @racket[strip-minimization-info] to remove this information and get
 a pure S-expression.}

@defproc[(conforms-to-grammar? [grammar grammar?] [expression sexp?]) boolean?]{
 Checks whether the expression conforms the grammar specified.
 This will return @racket[true] for the return value of
 @racket[generate-valid-testcase] and @racket[false] for
 all of the return values of @racket[generate-invalid-testcases].}

@defproc[(produce-minimum-failing-testcases
          [test-case s-expression?]
          [parser (-> s-expression? any)]
          [preprocess (-> s-expression? s-expression?)])
         (listof s-expression?)]{
Given a test case
 generated by @racket[generate-valid-testcase-for-minimization] and
 a student's parse function, produces a list of "minimal"
 test cases on which the student's parser fails (i.e., throws
 an exception). The list of test cases is not exhaustive in
 the sense that there might be expressions on which the
 parser fails that won't be in the list until other
 expressions in the list have successfully parsed. The list
 of expressions will only be empty if the student's parser
 successfully parses the whole, large test case. If you find
 that the minimization takes longer than you would like, you
 might instruct your students to memoize their parse
 function. The @racket[preprocess] argument is applied to any
 expression before it is passed to the student's parser. This
 is useful if, for instance, the language in question has a
 top-level construct around which expressions must be
 wrapped.}

@defproc[(strip-minimization-info [minimization-testcase s-expression?]) s-expression?]{
 Strips
 the annotations from the return values of
 @racket[generate-valid-testcase-for-minimization] to give a pure
 S-expression. @racket[(strip-minimization-info
 (generate-valid-testcase-for-minimization grammar))] will
 produce the same value as @racket[(generate-valid-testcase
 grammar)].}
