How to read this manual

The different sections of this manual are presented in the theoretical order of operations: you start by preparing your collection of programs, these programs are labeled, these labels are translated into taxa, the results are stored in a database; finally, you filter this database through a command pipeline to extract recommendations.

In practice, your input is only required for the last stage. That's why we suggest you observe the following order:

1. Start by reading the pipeline tutorial: it explains, in a user-friendly style, what you can expect from Paroxython and how you may integrate it into your teaching.
2. Once you are familiar with this aspect, see if you can improve or enrich the results through some preparation of the programs in your collection.
3. If needed, adapt the default taxonomy to your own vision of how to teach programming.
4. Harness the full power of the pipeline with its most advanced commands.

Of course, you can consult at any time the glossary of terms specific to Paroxython.

Preparing your program collection

tl;dr. There is nothing to prepare before launching Paroxython. Nevertheless, for best results:

• don't name things like a first year student (follow PEP 8, good practices and common sense);
• aim at the simplest style. Don't try to outsmart Paroxython: you're sure to win… a lot of false negatives;
• the system is not capable of inference: be direct;
• for the same reason, prefer from foo import bar; bar() to import foo; foo.bar();
• do use:
  • early exits when alternative versions are less clear;
  • infinite loops when you deal with an unpredictable stream of inputs;
  • else after the return statement of then branches which are not guards;
• give manual hints for:
  • correcting a false positive or negative;
  • adding metadata (it's more versatile than a nested directory structure);
  • resolving duck typing on built-in types, if needed.

Naming things

Capitalization

Paroxython takes advantage of the official PEP 8 naming conventions. In a nutshell:

lowercase_with_underscores

Variables, functions (in the broadest sense, including methods), modules, packages.

CapitalizedWords

Classes, exceptions, type variables.

ALL_CAPITAL_LETTERS_WITH_UNDERSCORES

Constants, defined on a module level.

For example, with a careless style like this:

def ComputeSquare(x): # bad: CamelCase for a function name
    return x * x

FOO = 42
FOO = ComputeSquare(FOO) # bad: redefinition of a constant

… Paroxython will wrongly detect two definitions of constants (var/assignment/explicit/constant) and the instanciation of a class (call/class/constructor). To make these false positives disappear, just write:

def compute_square(x):
    return x * x

foo = 42
foo = compute_square(foo)

Leading and trailing underscores

_single_leading_underscore

Weak “internal use” indicator.

__double_leading_underscore

Mangled non-public class attributes.

single_trailing_underscore_

Conflict-averse objects (avoiding a name collision with a keyword).

__double_leading_and_trailing_underscore__

"Magic" methods or attributes (never invent such names).

Other conventions

When the name of a function returning a value starts with "is_", "are_", "has_", "have_", "can_", "must_" or "needs_", it is tagged as predicate ("def/subroutine/function/predicate"):

def is_odd(n):
    return n % 2

When the name of a function returning nothing starts or ends with "test" or "tests", it is tagged as test ("def/subroutine/procedure/test"):

def test_is_odd():
    assert not is_odd(42)
    assert is_odd(5)

Beware of renaming built-ins

It's rarely a good idea to reuse a built-in function name:

max = 42  # mad: max() is a built-in function

In the same way, if you write classes, consider the names of the methods of the built-in types as taboo. Paroxython relies on them to try guessing the type of objects to which they apply. For instance, in:

def change_separator(s, old, new):
    return new.join(s.split(old))

… nothing indicates that s is a type/sequence/string except from the call of its method split().

Style

Be boring

Paroxython is optimized for the most unremarkable style. In the following snippet:

a += 1
a = a + 1
a = 1 + a

… only the first two lines will be labelled as increment:a. Paroxython doesn't bother to decipher the so-called Yoda style. Other examples:

a = -a # labelled as `negate`
a = -1 * a # false negative

a[-i] # labelled as `negative_index`
a[len(a) - i] # false negative

Be direct

Some static analysis tools have inference capabilities. For instance, Astroid can parse:

a = 1
b = 2
c = a + b

… and infer the value of c.

For now, Paroxython makes no inferences. So, using an intermediate assignment will sometimes be enough to make it miss a feature:

s = "hello, %s" % world # labelled as `string_formatting_operator`
template = "hello, %s"
s = template % world # false negative

A string literal on the left hand side of % is needed to recognize the latter as a string formatting operator. Paroxython does not try to guess the type of template.

There are more interesting cases. For instance, the following code is correctly tagged tail_recursive_function:gcd: a function is tail recursive if and only if all its recursive calls return their results immediately, without any further calculation.

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

Now, suppose you want only one exit point, and come up with the following functionally equivalent code:

def gcd(a, b):
    if b != 0:
        a = gcd(b, a % b)
    return a

The result of the recursive call is now assigned to variable a. There is no further calculation as such, but Paroxython expects you to return directly the result. Its no-inference heuristic is fragile: delaying a key treatment is enough to defeat recognition¹.

Importations

So far, the preferred form is:

from a.b.c import d

For instance, writing:

from math import cos, sin
cos(1) - sin(1)

… makes Paroxython able to produce the following (correct) taxa:

• import/standard/math/cos
• import/standard/math/sin
• call/subroutine

But writing:

import math
math.cos(1) - math.sin(1)

… yields subpar results:

• import/standard/math (less specific)
• call/subroutine/method (wrong)

Early exits

Paroxython will rightly identify a universal quantification (pattern/elements/satisfy/all) in:

def is_prime(n):
    for candidate in range(2, n):
        if n % candidate == 0:
            return False
    return n > 1

Not so if you try to force the predicate into the single-point-of-exit dogma of Pascal²:

# Once upon a time... in academia
def is_prime(n):
    candidate = 2
    divisor_found = False
    while candidate < n and not divisor_found:
        if n % candidate == 0:
            divisor_found = True
        candidate += 1
    return n > 1 and not divisor_found

Apart from being twice longer, more error-prone and harder to understand, this style defeats Paroxython, and will always do, sorry.

In any case, take a look at our specifications of iterative patterns. Should there be anything you don't agree with, no problem: just delete the corresponding translations from your copy of taxonomy.tsv.

Infinite loops

Likewise, consider solving the loop-and-a-half problem³ this way:

def input_number_between(prompt, lower_bound, upper_bound):
    while True:
        number = literal_eval(input(prompt))
        if lower_bound <= number <= upper_bound:
            return number
        print(f"Your number should be between {lower_bound} and {upper_bound}!")

… to make it tagged pattern/inputs/find_first_good.

Guards

Numerous guidelines and linters (e.g., LLVM Coding Standards, Pylint, ESLint, TSLint) warn that an else branch following a return statement “is not necessary and increases indentation level”. Although this is technically true, our approach is more nuanced. Specifically, we recommend our students to use the “no else” style when the condition can be seen as a guard, i.e., a pre-condition to avoid failing, complicating or slowing down the main treatment of the subroutine:

def is_prime(n):
    if n < 2: # avoid calculating the square root of a negative number
        return False
    if n == 2: # avoid returning a wrong result for 2
        return True
    if n % 2 == 0: # avoid wasting time in the loop
        return False
    # this is where the real work begins
    for candidate in range(3, int(sqrt(n) + 1), 2):
        if n % candidate == 0:
            return False
    return True

However, as noted here or here, there are situations where applying the blanket rule would break an inherent symmetry in the treatment:

def max_(a, b):
    if a >= b:
        return a
    else: # removing this branch would hurt readability
        return b

So, both styles have their uses. Consider this as an opportunity to better communicate your intention⁴. Remember that when you write an if statement ended by a return and not followed by an else branch, Paroxython will automatically try⁵ to tag it as a guard (flow/conditional/guard).

Manual hints

On a given source code, the tagging algorithm may sometimes result in false positives or false negatives. Moreover, the semantics of some features may be subjective (e.g., meta/topic/fun) or beyond the capabilities of Paroxython (e.g., deciding the relevance of the short_circuit property of a boolean operator). In any case, the user has the possibility to manually tag certain lines of their source code to hint either the presence or absence of a given feature.

Addition

The addition of one or several tags is hinted by a comment starting with # paroxython:.

Hinting with labels

A tag can be a label (of the kind defined, but not necessarily included in spec.md):

if i < len(s) and s[i] == x: # paroxython: short_circuit:And

This is powerful: a label can be derived into several other labels, and then converted into any number of taxa (according to the mapping of taxonomy.tsv). But it asks you to check the taxonomy to see how it will be converted.

Hinting directly with the final taxa

A tag can be a taxon (starting with a non-empty sequence of word characters and a slash):

if i < len(s) and s[i] == x: # paroxython: operator/boolean/and/short_circuit

Hinting with a taxon is easier: you put it directly into the taxonomy. But sometimes you want more.

Deletion

To delete a label, prefix it with a minus symbol. For instance, the following hint requalifies an addition into a string concatenation:

print(a + b) # paroxython: -addition_operator +concatenation_operator

Multiple lines

If a label should span over several lines, it is hinted on the first line with a .​.​. suffix (meaning “to be continued”), and on the last line with a ..​.​ prefix (meaning “continuing”). In the following example, a new label is manually substituted to the calculated label loop:for:

for am in ifera: # paroxython:  -loop:for... +amoeboid_protist...
    catch()
    eat() # paroxython: ...loop:for ...amoeboid_protist

Formatting details

Some tolerances exist for the syntax:

• + can be omitted.
• ..​.​ can be written … (HORIZONTAL ELLIPSIS, U+2026).
• # paroxython: is neither space- nor case-sensitive.

Why would I do that?

On simple programs such as those found in programming education, the results of Paroxython are generally quite satisfactory. But the better the feature labelling, the better the recommendations. You will sometimes, hopefully not too often, feel the need to remove (-) some false positives or correct (+) some false negatives. There are, however, more interesting possibilities.

Adding metadata

Consider the following naive suboptimal solution to the general problem of deduplicating a given sequence:

1   def unique_elements(sequence):
2       result = []
3       for x in sequence:
4           if sequence.count(x) == 1:
5               result.append(x)
6       return result

What if we take the trouble to give Paroxython some hints about what we meant by “naive”, “suboptimal” and “general”?

1   def unique_elements(sequence):
2       result = []
3       for x in sequence: # paroxython: complexity:O(n) complexity:O(n^2)...
4           if sequence.count(x) == 1: # paroxython: complexity:O(n)
5               result.append(x) # paroxython: ...complexity:O(n^2)
6       return result
7   # paroxython: meta/level/naive complexity:suboptimal
8   # paroxython: topic:general

Wow, this is handy. Let's break these comments down:

• We have pinpoint the lines featuring a linear operation: for and count(). The latter is not obvious for most students, and yes, that's the kind of thing you're going to have to repeat over and over again, unless you give up with high level languages like Python, and go back to C, assembler, Turing machines, Brainfuck, whatever.
• Nesting these two operations results in a quadratic complexity, which we have hinted by opening and closing a tag on the lines involved (3-5).
• As stated above, this approach is generally known as naive. No translation for a label level:(.+) is provided in the default taxonomy, so you hint directly at the desired taxon.
• Tagging the program as suboptimal, or as a counter-example, can be useful: when you are setting up an exam, you don't need to be recommended bad programs, do you? With this kind of metadata, you can easily exclude all of them.
• Tagging your programs by topic is an alternative to distributing them in different folders, and is arguably better: when a program belongs to several topics, you don't have to bother with symlinks; and you are not stuck when you change your mind about the categorization (when, suddenly, you decide to classify your programs by technique: like greedy, dynamic programming, divide and conquer, etc.). By the way, remember you can always redirect the recommendations to stdout, and get a simple list of files. See paroxython.cli_recommend for an example of how to copy them in another directory.

Hunting ducks

Python famously thinks that:

If it looks like a duck, swims like a duck, and quacks like a duck, then it is a duck.

This is called duck typing, and the reason why unique_elements() (above) would be happy with either a list, a tuple or a string: all of them sport the same methods, specifically count() (explicit) and __iter__() (implicit).

For us, this cute duck typing comes with a challenge. Although this may change in the future, for now Paroxython ignores your type hints. As already explained, it just relies on the names of the methods and attributes to guess the type of the built-in objects. For instance, the default taxonomy has these two lines:

type/sequence/list            member_call_method:(append|extend|insert|reverse|sort)
call/subroutine/method/sequence/list/\1  member_call_method:(append|extend|insert|reverse|sort)

This is why the expression foo.append(bar) will be tagged member_call_method:append (label), and then call/subroutine/method/sequence/list/append and type/sequence/list (taxa). Here, this technique increases our chances of finding programs that feature lists, but it does not achieve the same accuracy for foo.count(bar): indeed, count() is shared by all sequential types. In the taxonomy, this comes down to:

type/sequence                   member_call_method:(count|index)
call/subroutine/method/sequence_duck/\1 member_call_method:(count|index)

Did you spot the duck in the second row? It's there to tell you: “Quack! that's the best I can say, but in case this sequence can't actually be anything other than a list, just let me know.”

Well, ok. How to do this?

In fact, the taxonomy has two lines for that:

type/sequence/list              member_call_method:list:(count|index|pop|...)
call/subroutine/method/sequence/list/\1 member_call_method:list:(count|index|pop|...)

This means that you can hint at every ambiguous list method (count(), etc.) by deleting the original label and adding a new one with an inserted ":list":

a.count(b)  # paroxython: -member_call_method:count +member_call_method:list:count

Now, the generated taxa will be: type/sequence/list and call/subroutine/method/sequence/list/count⁶. As for the duck, it is no more. It has ceased to be. It is expired and gone to meet its maker. It has run down the curtain and joined the choir invisible. This is an ex-duck.

Admittedly, all of this may be overkill, since a program featuring a list would most of the time feature it in several places, most of them without ambiguity. After all, generally speaking, you just want Paroxython to help you find programs in your repository, but don't need it to find features in a given program (you know better).

But if you feel like it, just fire up this 1 weird pipeline:

{
    [
        "operation": "include",
        "data": [".+\bduck\b"],
    ]
}

… and happy duck hunting!

Taxonomy

Structure

In Paroxython, the default taxonomy is a forest: a handful of separate trees with flow, operator, meta, type, etc. as their roots. We call taxon⁷ a path from a root node to a leaf node. Thus:

type/number/integer/literal

… describes, you know… this kind of literal which is a kind of integer which is a kind of number which is a kind of type (as an example, think of the answer to the ultimate question of life, the universe, and everything).

In the visualization below, we have introduced the pseudo-root “🐍” to gather all the trees into one:

This comes⁸ straight from the tagging of the public repository The Algorithms - Python. The size of a node is relative to the number of times the corresponding taxon's prefix appears in these programs.

Hover over the nodes to see these numbers, or click them to navigate the tree. By the way, you may click on type to better follow the subsequent explanations.

Mapping the labels onto taxa

Paroxython does not directly grow these forest of taxa. Remember, a program is first tagged with labels (as specified in spec.md). Those are then translated into taxa by a purely morphological operation (search and replace), without any more reference to the original source code.

1-1 mappings

Suppose a program has been tagged with the labels:

• literal:True (the constant True).
• literal:False (the constant False).
• external_free_call:bool (a call to the built-in function bool()).

The following conversion table (extracted from taxonomy.tsv) will then give the taxa seen above in the subtree type/boolean:

Note that, somewhat counterintuitively, the conversion goes from right to left. Each line consists of a taxon tab-separated from a label. It is interpreted as “when a program features this label, create that taxon with the same spanning lines”.

All of these rows define 1-1 mappings: each one translates one label into one taxon.

N-1 mappings

The previous table extract represents the simplest case, where both taxon and label patterns are literal. Below, the second label pattern is a non-literal regular expression:

It defines a 5-1 mapping, which converts five possible labels (member_call_method:append, member_call_method:extend, and so on) into a single taxon (the metacharacter "|" meaning “or”). These two rows thus constitute a 6-1 mapping.

1-N mapping

When a source code is, say, 42 lines long, it is tagged with the label "whole_span:42". This is an example of a single label which produces two taxa: "meta/program" and "meta/count/program/sloc/42". Both span the whole program and, although it is not obvious, both have their uses:

• The first one is common to all programs, and provides an invariable access key to an all-encompassing span. In a command pipeline, it can be used to express the absence of a taxon.
• The second one has a variable part, and can be used to filter programs by size (for example, in paroxython.recommend_programs, the pattern "meta/count/program/sloc/[1-4]?[0-9]" will be used to filter out the programs that have 50 lines or more).

This conversions are triggered by the following rows in the default taxonomy:

On the first row, the sequence of metacharacters ".+" means: “eat all you can up to the end of the line.” On the second row, the added parentheses also captures these characters: they are restituted in the replacement pattern by "\1", which denotes a backreference to the first captured group.

Another example could be:

… which means: when you encounter a label member_call_method:sort (for instance), that means the program features a list and a call to the sort() method.

1-0 mapping

At first glance, some of the labels generated during the first tagging step seem redundant, e.g. "binary_operator:Add" and "addition_operator". In fact, the former was used to calculate the latter. In spec.md, the definition of "addition_operator" is introduced by:

An addition operator is a binary operator Add which has not be classified as a concatenation operator.

This is a good example of a label for internal use only. In the conversion step, it will be simply ignored (i.e., it has no entry in the taxonomy).

Back to the roots

Functional inspirations: var, def, call and type

What are the basic concepts on which computing can be built? As you know, Alonso Church answered this very question as early as 1936 (years before the computers were even invented!). The three building blocks of his lambda calculus, namely the concepts of variable, abstraction and application, provide us our first three taxonomic roots, which we will denote respectively by var, def and call. To these we can naturally add that of type, already shown above.

All of these could be enough to describe pure functional programs, at least theoretically. However:

1. Python is no Haskell. It is a multi paradigm language, with a strong emphasis on imperative programming. And its zen famously holds that “practicality beats purity”.
2. Here, we are not interested in teaching generalized computability. Pedagogical considerations take precedence over a crippling respect for mathematical abstractions. For instance, we don't need to explain thoroughly the concepts of literal, string, type, built-in function and call for making our young students feel they understand:

print("hello, world")

For these reasons, choosing to root our taxonomy in the four basic notions of the typed lambda calculus should be seen more as a tribute than a formal commitment. More specifically:

• var will essentially bring together everything relating to the concept of assignment and scoping;
• def will accommodate not only lambda functions, but named ones, methods, generators and even classes. Note that this does not include variable definitions.
• call will cover any call to anything with a __call__() method, which Python calls a callable (sorry);
• finally, type will welcome all types, no purity required.

Imperative needs: flow

The imperative nature of Python demands that we introduce the concept of control flow, under which we put the loops, the conditionals, and some other animals¹⁰.

For your convenience: operator, condition, subscript

Again, those are mainly practical choices. After all, an operator is nothing more than an unassuming function call with a funny name and a funny syntax. And a condition¹¹, a combination of function calls which happens to evaluate to a particular type. As for the creation of the root subscript, it comes from the observation that an lot of exciting programs can be written with sequences before venturing out to direct access (that is, as long as we treat Python lists as lists and not arrays). Not that in our default taxonomy, subscript includes slicing and dictionary access too.

Importations

Previously classified under def, since version 0.6.0, the import statement has now its own root in the taxonomy.

Zooming out: pattern

Now this is arguably the most interesting feature to tag in a beginner-level program. Under pattern, you will find numerous variants of the invaluable accumulation pattern (counting, summing, filtering, finding the “best” element, etc.), but also some early-exit patterns (testing for an universal or existential property, finding the first “good” element, etc.), whether by traversing a sequence or evolving a state. A (currently) small number of common expression patterns are also available. However, the common assignment idioms (such as incrementation, swap, slide, conditional assignment) are classified under var/assignment/explicit.

Although the relative size of pattern is the smallest of the taxonomy, note that it is almost that of meta/program (which has one occurrence per program): in other words, almost all programs feature such a pattern (which spans several lines).

The loop patterns constitute an aspect of programming which is not always taught in a conscious and systematic way, and to which Paroxython intends to draw your attention.

Tagging with style

Paradigms

Python allows you to mix freely multiple paradigms. However, for Paroxython, every program will fall into exactly one of the following four categories, always associated to the whole span:

1. style/object_oriented if it features at least one class definition;
2. style/functional if it is not object oriented, and features at least one function returning something, but no loop and no assignment;
3. style/procedural if it is neither object oriented or functional, and features at least one subroutine definition;
4. style/imperative if it features no subroutine or class definition.

Additionally, style/imperative/flat is the no-indent version of the latter (no loop, conditional, etc.).

Functional traits are also tagged. The corresponding taxa start with: style/functional_trait/, and are suffixed by lambda, higher_order, pure_function, map, filter, reduce, etc. Unlike style/functional, which spans the entire program, these taxa are located on certain lines. They can appear in a program of any (all-encompassing) style.

Independently of the 4-partition, style/one_liner denotes any program whose exactly one SLOC is neither a definition header, an importation or an assertion. For instance, the following program is considered a one-liner:

from sum_proper_divisors_1 import sum_proper_divisors

def abundant_numbers_below(bound):
    # An abundant number is a number for which the sum of its proper divisors
    # is greater than the number itself (Wikipedia).
    return [n for n in range(1, bound) if sum_proper_divisors(n) > n]

Flawed styles

Although Paroxython is no linter, it may tag some unpythonic (i.e., non-idiomatic) or naive patterns, frequent in the beginners' code. For instance:

aux = a
a = b
b = aux

… is tagged style/unpythonic/swap, and:

if condition:
    return False
else:
    return True

is tagged style/naive/return_condition. Search _unpythonic and _naive in spec.md for the current list (which could of course be extended ad libitum).

Going meta

Paroxython will store inside the meta tree some program metadata, such as the number of lines. Some children, such as topic, technique, complexity, are already provided, which you can fill in by adding a manual hint in the source code of the programs.

Modifying the taxonomy

The definition of a taxonomy is, at least partly, a matter of pedagogical choices. You are encouraged to duplicate the default taxonomy, and replace or delete those taxa that do not fit your course purpose or logic.

Copy the default taxonomy.tsv at the same level as the src folder that contains your Python programs:

programming_101/
├── taxonomy.tsv
├── src/
│   ├── hello_world.py
│   ├── gob's_program.py
|   ├── ...

This way, omitting the option --taxonomy like in the command below will use your copy instead of the original.

paroxython collect programming_101/src

You can now freely experiment on this copy.

Pipeline tutorial

How to get recommendations? This tutorial walks you through a series of little “teacher stories” to introduce the pipeline of commands used by Paroxython's recommendation system.

You “execute” this pipeline on command line with:

paroxython recommend -p 'path/to/your/pipe.py' 'path/to/your/programs/db.json'

Covering your base(s)

The simplest pipeline has no command: it just lists the programs of your database, without any filter. This could produce a rather long document, since each source code is printed, along with a list of each and every taxon it implements. Here is the content of your pipe.py:

[]

Imparting knowledge

Tracking the progress of your course

Suppose that, in your first session, you have introduced your students to the hello_world.py, wheat_and_chessboard.py and euler_005_smallest_multiple.py programs. Not only Paroxython should no longer recommend these programs, but the cost of learning the associated concepts should be considered as zero when they are encountered again in the future.

[
  {
    "operation": "impart",
    "data": [
      "hello_world.py",
      "wheat_and_chessboard.py",
      "euler_005_smallest_multiple.py",
    ],
  },
]

Coming after another course

Suppose instead that you intervene after an introductory course given by a colleague. She gives you a folder (named "CS_101"), which contains the programs she has studied with her class. Since you are secretly in love, you assume, somewhat foolishly, that the concepts they implement are mastered by your new students.

[
  {
    "operation": "impart",
    "data": "find CS_101 -path '*.py'",
  },
]

Blacklisting programs

You want to filter out all programs reserved for an exam, or too complex, or not pedagogically interesting enough, or that could get you kicked out of your college, etc.

[
  {
    "operation": "exclude",
    "data": [
      "fizzbuzz.py",
      "alpha_go.py",
      "hello_world_of_pain.py",
      "gob_s_program.py",
    ],
  },
]

Concepts to be introduced later (or never)

For the time being, you don't want to be recommended any program requiring the concepts of recursivity (def/subroutine/recursive), dictionary (type/non_sequence/dictionary) or set (type/non_sequence/set).

[
  {
    "operation": "exclude",
    "data": [
      "def/subroutine/recursive",
      "type/non_sequence",
    ],
  },
]

Concepts to be introduced now

Your next class will be devoted to conditional constructs. Thus, you need to go through programs featuring taxa prefixed by flow/conditional or even, why not, some conditional expressions (operator/ternary). The suggested programs do not necessarily have to implement both concepts at the same time, but at least one. Any other program will be rejected.

[
  {
    "operation": "include",
    "data": [
      "flow/conditional",
      "operator/ternary",
    ],
  },
]

Preparing an assignment

Basically, you provide Paroxython with a list of programs already studied in class, and it suggests new programs that implement only old concepts. This requires the exclusion of all programs featuring at least one concept that has not been seen in any of the programs already seen.

It may sound a little complicated, because it is. But don't panic. Remember that Paroxython always orders its recommendations by increasing cost. Thus, all you have to do is ask it to list the programs that have not been introduced yet. The programs you want to choose among will appear at the top of the results, under the zero-learning cost section. Moreover, inside each section, they will be sorted by increasing size (SLOC), which can be a reasonable proxy for their difficulty.

But in the end, you, the teacher, are the judge. Paroxython is not going to set up a test for you, let alone grade the answers. It is just here to remind you of some possibilities you might not have thought of at the right time, and to give you some confidence that the exercises require no concept you have not pre-introduced in class, which later on might save you some awkward conversations with your dear students.

Since this is the last filter in our tutorial, let's summarize what we've seen by chaining several commands together:

1. Impart the previous knowledge by extracting all the programs listed in the "timeline.txt" file that you update after each session. You can adapt the script parse_syllabus.py to your own needs. If you wish, you can use the base_path variable, which represents the parent of the directory containing the programs of your personal database.
2. Exclude some irrelevant programs.
3. Include the concepts that you want to test during your exam.

[
  {
    "operation": "impart",
    "data": "python helpers/parse_syllabus.py {base_path}/timeline.txt",
  },
  {
    "operation": "exclude",
    "data": [
      "foo.py",
      "bar.py",
      # "buzz.py",
    ],
  },
  {
    "operation": "include",
    "data": [
      "pattern/elements/accumulate",
      "topic/game",
      "type/sequence/list",
    ],
  },
]

This is the end of our pipeline tutorial. If you dare, read on for more advanced features (regular expressions, span algebra, semantic triples, negations).

Pipeline documentation

This part goes deeper into the pipeline by describing in details how the recommendation system works. It assumes you've already read the pipeline tutorial. First of all, let us recall the example of pipeline we gave at the end.

>>> [
...   {
...     "operation": "impart",
...     "data": "python helpers/parse_syllabus.py {base_path}/timeline.txt",
...   },
...   {
...     "operation": "exclude",
...     "data": [
...       "foo.py",
...       "bar.py",
...       # "buzz.py",
...     ],
...   },
...   {
...     "operation": "include",
...     "data": [
...       "pattern/elements/accumulate",
...       "topic/game",
...       "type/sequence/list",
...     ],
...   },
... ]

Regular expression patterns

The first thing to clarify is that the strings which constitute the data lists are not simple names, but “descriptions” of names. These descriptions, or patterns, are written in the language of regular expressions, and more precisely in the dialect implemented by the third-party module regex¹².

The second thing to clarify is that a given pattern will match any string starting with it. Thus, "type/sequence/list" will match not only "type/sequence/list", but "type/sequence/list/empty" and "type/sequence/list/supercalifragilisticexpialidocious" too. The same applies to program paths. For example, in our personal database, all programs from Project Euler start with "euler_". The pattern "euler_" will then match all of them.

In terms of regular expressions, it means that, under the hood, Paroxython invokes match() instead of search(). In the rare cases where you want to restrict the whole matching to the pattern itself, simply suffix it with a dollar sign, i.e., "type/sequence/list$".

Execution of a pipeline

A pipeline is a set (or list, but the order is not important) of commands which apply sequentially to a database of program tags. It returns:

• a list of recommended programs;
• an estimation of the learning cost of each concept (i.e., taxon) they implement.

The set of commands constitutes a pipeline that evolves both:

• a selection of programs (initially all those in the tag database);
• a body of imparted knowledge (initially empty).

A command consists of:

• an operation among "include", "exclude", "impart" and "hide", optionally suffixed by the quantifier (" all");
• the data to which it applies. This data is (or can be interpreted to produce) a list of criteria, each criterion being:
  • either a program pattern,
  • or a taxon pattern,
  • or a relationship between two taxon patterns (more on this in the Semantic triples section).

Combining the operation with a criterion is done in four stages:

1. An auxiliary set of programs is calculated.
2. The set of recommended programs (the selection) is updated.
3. A new set of taxa may be “learned”, i.e., added to the body of imparted knowledge.
4. The set of taxa and programs to hide in the final report may be updated.

Note that each stage depends on both the operation and the nature of the criterion to which it applies. Let us detail every possible case:

"include" command

Its purpose is to keep only those selected programs that satisfy at least one given criterion.

1. The auxiliary set contains any program such that:
   • either its name matches the given pattern,
   • or its source code:
     • either features at least one taxon matching the given pattern,
     • or satisfies the given relationship.
2. The selection is then restricted to its intersection with the auxiliary set.
3. The imparted knowledge is unchanged.

"include all" variant

Its purpose is to keep only those selected programs that satisfy all given criteria.

{
  "operation": "include all",
  "data": [
    criterion_1,
    criterion_2,
    ...,
    criterion_n
  ]
}

… is equivalent to:

  {"operation": "include", "data": [criterion_1]},
  {"operation": "include", "data": [criterion_2]},
  ...,
  {"operation": "include", "data": [criterion_n]}

"exclude" command

Its purpose is to filter out of the selection the programs which satisfy at least one given criterion.

1. The same auxiliary set of programs as above ("include") is calculated, but further extended to the programs which import them (either directly or indirectly). Indeed, when the teacher wants to exclude a certain program, any program that requires it should be excluded as well.
2. The selection is then restricted to its difference with the auxiliary set.
3. The imparted knowledge is unchanged.

"exclude all" variant

Unlike "include all", this variant actually expands the semantics of the system.

{
  "operation": "exclude all",
  "data": [
    criterion_1,
    criterion_2,
    ...,
    criterion_n
  ]
}

… excludes the programs satisfying all the criteria. This cannot be transformed into a sequence of "exclude" commands, which would exclude the programs satisfying any of the criteria.

"impart" command

Its main purpose is to track the acquisition of new knowledge. However, if this knowledge is provided by a given set of programs, there is no more need to keep them in the selection of recommended programs.

1. The auxiliary set contains all programs whose name matches at least one of the given patterns (relationships are not supported), plus those which import (either directly or indirectly) at least one of them. In other words, it is the same as above ("exclude"), but only in the case where the criterion is a program pattern. In all other cases, this auxiliary set will be empty.
2. The selection is then restricted to its difference with the auxiliary set (same as above for "exclude").
3. There are three cases:
   1. If the criterion is a program pattern, all the taxa featured in a program whose name matches this pattern are added to the body of imparted knowledge.
   2. If the criterion is a taxon pattern, all the taxa matching this pattern are added to the body of imparted knowledge.
   3. Otherwise, the body of imparted knowledge is unchanged.

The "impart all" variant is not supported, and treated as "impart".

"hide" command

This is the simplest command of all. It merely accumulates the programs or the taxa matching the given patterns (relationships are not supported), without other effect on the filter. In the final stage, the accumulated programs or taxa will be filtered out of report.

Notes.

• Excluding a program is equivalent to hiding it plus every program importing it.
• The learning costs are not affected whatsoever by the hiding of a taxon: its individual cost continues to contribute towards the total cost of a program.

The "hide all" variant is not supported, and treated as "hide".

Semantic triples

Span algebra

Being given a program $p$ of $n$ lines, a couple $(i_1, i_2)$ of line numbers such that $1 \leq i_1 \leq i_2 \leq n$ represents a span of $p$. When Paroxython finds a taxon $t$ in $p$, it doesn't just say whether $p$ features $t$ or not: it returns the list of spans where $t$ occurs.

It is sometimes interesting to know how the spans of two taxa of the same program are located relatively to each other.

• For instance, a print() statement whose span is inside the span of a function indicates that this function has a side-effect.
• A less trivial application stems from the fact that our taxonomy is multi-dimensional: each algorithmic feature can be associated with several taxa at the same time, characterizing it it along several dimensions. For instance, the taxa flow/loop/for and flow/loop/while describe the category of a loop; whereas the taxa flow/loop/exit/early and flow/loop/exit/late describe its exit behavior. These dimensions are independent and, although it is entirely possible to do so, our default taxonomy does not list the results of the cross-product (i.e., flow/loop/for/exit/early, flow/loop/for/exit/late, flow/loop/while/exit/early and flow/loop/while/exit/late). Querying an hypothetical taxon flow/loop/for/exit/early (or flow/loop/exit/early/for, by the way) comes down to querying the taxa flow/loop/for spanning the same lines as flow/loop/exit/early.

To express a relation $\mathfrak{R}$ between the spans of two taxa, we start from the algebra devised in 1983 by James F. Allen in his seminal paper (PDF) about temporal intervals¹³. The so-called Allen's interval algebra defines 13 basic operators which capture all possible relations between two intervals $X=(x_1, x_2)$ and $Y=(y_1, y_2)$. The table below uses his terminology:

These well-known operators apply quite nicely to our spans, with the following adjustments:

Synonyms. The 13 operator names, whose some don't make much sense in a non-temporal context, are extended with a number of synonyms, such as "inside" for "during", and "equal" or "is" for "equals". The current list can be found here.

Non-strict inequalities. In the above table, contrary to the convention on time intervals, we consider the inequalities to be large. In a program, most features span exactly one (logical) line (i.e., $x_1=x_2$): this is simply not possible with the original relations on endpoints. Besides, when we look for a function which contains a loop, we are generally not interested in whether the loop finishes on the last line. Blind adherence to strictness convention would force us to express our query as a disjunction of these two relations for the following program to be selected:

def first_missing_non_negative(l):
    elements = set(l)
    for natural in range(len(elements) + 1):
        if natural not in elements:
            return natural

Strict inequalities. In addition to the existing relations, all combinations of strict and non-strict conditions are generated, for instance $x_1 < x_2 < y_1 \leq y_2$. That adds up to 162 in total¹⁴.

Keys. As we use many more operators than Allen, giving an English name to every single one is not an option. Paroxython actually identifies them by a unique key (see the last column of the table above) calculated like this:

1. Start from the chain of equalities and inequalities that defines the relations between the two spans' endpoints: $y_1 < x_1 = y_2 \leq x_2$.
2. Drop the indices (since, for a given $x$ or $y$, indice $1$ always comes before indice $2$, no information is lost): $y < x = y \leq x$.
3. Rewrite the formula using only the five characters "=", "<", "≤", "x" and "y": y<x=y≤x.

Key normalization. Paroxython tries (cf. normalize_predicate()) to be tolerant with the user input. The verb "is" is ignored, except when it constitutes the whole string (thus, "is after" comes down to "after"). When an operator is not an Allen's name or a predefined synonym, the following normalization process is applied:

1. Replace any <= by ≤.
2. Replace any == by =.
3. Strip all characters distinct from "=", "<", "≤", "x" and "y".
4. If the string is "x=y" or "y=x", replace it by "x=y≤x=y".
5. If the string contains only one x (resp. y), expand it into x≤x (resp. y≤y).

This allows the user to be understood when entering formulas like x == y, x <= y or y1 < x1 == x2 <= y2.

Positive semantic triples

A pipeline command can apply not only to patterns of programs and taxa, but also to relationships between the spans of two taxon patterns. Being given an operator $\mathfrak{R}$ and two taxon patterns $t_1$ and $t_2$, the statement $t_1 \mathbin{\mathfrak{R}} t_2$ will be codified in the form of the subject–predicate–object expression $(t_1, \mathfrak{R}, t_2)$, which can be entered as a mere Python tuple (t1, R, t2).

The simplest semantic triple is:

("meta/program", "contains", taxon_pattern)

It matches all programs where the span of the taxon "meta/program" includes the span of a given taxon_pattern. Since, by definition, every program features one taxon "meta/program", whose span encompasses the whole program, this is strictly equivalent to:

taxon_pattern

And now for something completely different: the following pipeline command will only keep programs featuring a conditional inside a loop or (inclusive) ended by a return statement (the function first_missing_non_negative() given above satisfies these two criteria).

  {
    "operation": "include",
    "data": [
      ("flow/loop", "contains", "flow/conditional"),
      ("flow/conditional", "finished by", "def/subroutine/return"),
    ]
  },

It is currently not possible to chain several operators with shared operands, for example to keep only the programs that feature a conditional inside a loop and ended by a return statement: the quintuple ("flow/loop", "contains", "flow/conditional", "finished by", "def/subroutine/return") would raise an error. As it stands, the best we can do is to chain the commands themselves:

  {
    "operation": "include",
    "data": [
      ("flow/loop", "contains", "flow/conditional"),
    ]
  },
  {
    "operation": "include",
    "data": [
      ("flow/conditional", "finished by", "def/subroutine/return"),
    ]
  },
  {
    "operation": "include",
    "data": [
      ("def/subroutine/return", "contains", "flow/loop"),
    ]
  },

This keeps only the programs that feature a conditional inside a loop and a conditional ended by a return statement and a return statement inside a loop. The result is a subset of the previous one, but may still include programs where the two loops, conditionals or return statements are distinct.

Negative semantic triples

It is possible to negate the predicate of a semantic triple, either by prefixing it by an exclamation mark (e.g., "!x≤y≤y≤x", or "!contains"), or by adding the word not (e.g, "not x≤y≤y≤x", "not contains", or "contains not"), whether it's grammatically correct or not.

Expressing the absence of a taxon

Here again, the simplest negated semantic triple is:

("meta/program", "not contains", taxon_pattern)

On a set of independent programs (i.e., not importing each other), there is a strict equivalence between:

  {
    "operation": "include",
    "data": [
      ("meta/program", "not contains", taxon_pattern)
    ]
  },

and:

  {
    "operation": "exclude",
    "data": [
      taxon_pattern
    ]
  },

And, conversely, between:

  {
    "operation": "include",
    "data": [
      taxon_pattern
    ]
  },

and:

  {
    "operation": "exclude",
    "data": [
      ("meta/program", "not contains", taxon_pattern)
    ]
  },

This property may be used to select the programs that include any subset of a given set of taxa. This can be done in a systematic way by converting¹⁵ the corresponding logical formula in conjunctive normal form, and transforming each clause into a separate "include" command.

For instance, consider the two taxa "flow/conditional" and "flow/loop". To keep only the programs that feature either a conditional (denoted by the literal $a$) or a loop (denoted by the literal $b$), but not both of them, express first the formula in CNF: $(a \lor b) \land (\neg a \lor \neg b)$, then translate it into:

  {
    "operation": "include",
    "data": [
      "flow/conditional",
      "flow/loop",
    ]
  }, # keep only the programs that feature either a conditional or a loop
  {
    "operation": "include",
    "data": [
      ("meta/program", "not contains", "flow/conditional"),
      ("meta/program", "not contains", "flow/loop"),
    ]
  }, # among them, keep only those that feature no conditional or no loop

For two taxa, there are a total of 16 combinations, listed and tested here.

However, on a set on interdependent programs, "exclude" is not the opposite of "include" anymore: as already explained, excluding a program excludes also the programs which import it. Consequently, including the programs that do not feature a given taxon will filter out those which feature it directly; but excluding the programs that do feature this taxon will filter out those which feature it either directly or indirectly (by importation).

General semantics of the negation

The semantic triple:

(taxon_pattern_1, not predicate, taxon_pattern_2)

… describes the set of programs which feature at least one taxon matching taxon_pattern_1, and such that, for any span s_1 of such a taxon, there exists no span s_2 of a taxon matching taxon_pattern_2 for which predicate(s_1, s_2) is verified.

For example, if the original (negative) predicate is "taxon_pattern_1 not inside taxon_pattern_2", any program consisting in:

• "taxon_2{taxon_1}"¹⁶ is rejected;
• "taxon_1" is accepted (although there is no taxon_2);
• "taxon_2" is rejected (no taxon_1);
• "taxon_1{taxon_2}" is accepted;
• "taxon_1 taxon_2{taxon_1}" is accepted (there exists a couple (s_1, s_2) such that taxon_1 is not inside taxon_2);
• "taxon_1 taxon_2{taxon_1} taxon_2{}" is accepted.

If the predicate is "taxon_pattern_2 not contains taxon_pattern_1" (sic), any program consisting in:

• "taxon_2{taxon_1}" is rejected;
• "taxon_1" is rejected (no taxon_2);
• "taxon_2" is accepted (although there is no taxon_1);
• "taxon_1{taxon_2}" is accepted;
• "taxon_1 taxon_2{taxon_1}" is accepted (there exists a couple (s_1, s_2) such that taxon_2 does not contain taxon_1);
• "taxon_1 taxon_2{taxon_1} taxon_2{}" is accepted.

Note that, due to the rule explained in the warning above, "taxon_pattern_1 not inside taxon_pattern_2" is not equivalent to "taxon_pattern_2 not contains taxon_pattern_1" (differences in bold). However, if taxon_pattern_2 is "meta/program", which is featured by all programs, these two forms become equivalent again.

A practical example

Suppose you want your course on the assignment statements to include the concept of parallel assignment, for example to introduce swapping without an auxiliary variable:

(a, b) = (b, a)

In the taxonomy, this concept is listed as a special case of both tuple ("type/sequence/tuple") and variable assignment ("var/assignment/explicit/parallel").

However, you want to introduce officially the abstract data type “tuple” only much later in your course. You therefore wish to exclude from the recommendations any program implementing a tuple, unless it is part of a parallel assignment. The following command will make the trick:

  {
    "operation": "exclude",
    "data": [
      ("type/sequence/tuple", "is not", "var/assignment/explicit/parallel")
    ]
  },

The triple describes the set of programs which feature at least one tuple, and such that there is no tuple's span coinciding with a parallel assignment's span. In other words, the set of programs which feature at least one “non parallel” tuple. When we exclude these programs, those which remain either feature no tuple, or only the ones involved in a parallel assignment.

The other combinations are listed and tested here.

Glossary

Inside a definition, the terms which have their own entry in the glossary are italicized.

AST (flat —)

The dump of an Abstract Syntax Tree as a sequence of text lines, each one consisting of the whole path from the tree root to the current node, with some tweaks.

Command

A pipeline operation, along with its data.

Criterion (plur. criteria)

Either a taxon pattern, a program pattern or a semantic triple.

Data

In a restricted sense, the second member of a command.

• If it is a string, it is interpreted as a shell command printing a list of program or taxon patterns.

• If it is a list, each element is interpreted as a criterion.

Hint (manual —)

A comment that you may add in a source, either to fix a mislabelling problem, or to specify some metadata. It starts with "# paroxython: and can schedule either a label or a taxon for addition (by default) or deletion. Example:

print(a + b) # paroxython: -addition_operator +concatenation_operator

Label

Name of a feature, as defined in spec.md. Examples:

• simple: swap, if_else_branch, verbose_conditional_assignment;

• with one variable suffix: loop_with_return:for, import_module:foo, member_call_method:append;

• with several variable suffixes: member_call:bar:append, for_range:start:stop:-1.

Comparison with taxa: the taxa aim to represent concepts; labels, not so much. For instance, labelling a = b by assignment:42 captures, in addition to the concept (assignment), an arbitrary piece of information (a name) which may or may not be internally used later to label more complex features. Moreover, taxa are structured into a taxonomy; labels are free form.

Operation

A string among "include", "exclude", "impart" and "hide", with an optional suffix "any" (implicit) or "all".

Path

A continuous sequence of distinct edges from the root to a given node of a tree. Can be used for the taxonomy or for the flat AST.

Pattern

A regular expression describing the name of a program, a label or a taxon.

Pipeline

A list of filtering commands, expressed as a Python value and evaluated by ast.literal_eval().

Predicate

Used in a restricted sense to denote the middle term of a semantic triple. It is a function taking two poor spans x and y and telling whether they satisfy a certain relationship (for instance, “x after y”, or “y not inside x”).

Source

The text of a Python program of your collection.

Span

The location of a given feature, as the couple of its first and last lines. By extension, a third member, the path, identifies the beginning of the feature in the AST.

Span (poor —)

A span deprived from its last member.

Tag

Generic term, covering both labels and taxa.

Taxon (plur. taxa)

Name of a feature, resulting from the conversion of a given label. Examples:

• the label swap is converted to the taxon var/assignment/explicit/parallel/swap;

• the label member_call_method:append is converted to the taxa call/subroutine/method/sequence/list/append and type/sequence/list.

A taxon is a path from a root to a node in the taxonomy. It represents a learning concept that should be of interest to the teacher.

Taxonomy

A forest structuring the learning concepts of the domain. The idea is that the concept represented by a node must be introduced after its parent concept (if any).

Triple (semantic —)

Consists of a taxon pattern (the subject), a predicate and an another taxon pattern (the object). Example: ("flow/conditional", "finished by", "def/subroutine/return").