-
Notifications
You must be signed in to change notification settings - Fork 41
Pseudocode Format
The Refinement Explanation Animation Language (Real) was designed to allow educators, with expertise in algorithms and teaching, to communicate requrements to developers. It shows pseudocode, explanations, and the desired breakdown of the pseudocode into blocks of pseudocode that can be expanded (refined), explained, and collapsed by the user. To date, we have had educators write Real code for algorithms and developers have had to make minor adjustments to incorporate it into the AIA implementation. Educators can potentially make careful changes to text in the implementation (making sure it does not affect how the animation is linked); the problem of multiple versions of Real code may be resolved in the future to make this process easier.
Here, we define the language and make some suggestions for how
it is used. In Real, pseudocode to be displayed in AIA is written
simply as lines of text. The language also contains directives, or
instructions/tags, that are distinguished from pseudocode by starting
with a backslash (\). Because all directives begin with the backslash
character, it is simple to grow the language to include further
directives, if necessary, while maintaining its conceptual integrity.
Real was designed with traditional parsing using grammar rules etc
in mind but the current implementation uses ad hoc line-based parsing
that only allows one directive per line. Real specifications are in
incorporated into AIA code as JavaScript strings so in the code, double
backslashes (\\) are needed (and any backquotes must be preceeded by
\). Other limitations are noted below. See src/algorithms/pseudocode
for examples.
The current list of directives is as follows:
\Overview{: Start of the overview/background of the algorithm displayed
in AIA.
Note: this is currently ignored in the JavaScript string; it is copied
and pasted to a separate file. See src/algorithms/explanations
for examples (yes, there is terminological confusion with
overview/background/explanations).
\Overview}: End of the overview.
\Note{: Start of a note for developers etc. A note is not displayed
in AIA.
\Note}: End of a note. All text between the start of the note and the
end of the note, plus any trailing newline, is ignored for the purposes
of display.
\Code{: Start of a pseudocode code block, that is, a chunk of
pseudocode. The first line of a block is a label that uniquely refers to
that block, and is not displayed. The lines of a block after the label
are the pseudocode, plus the relevant explanations or other directives
such as indentation. All code block labels must be unique.
Code blocks can be top level code or refinements (expansions) of
lines of code that appear elsewhere. The block label links the block
with the line of code it is refining, see \Ref below. Currently the
implementation supports only one top level code block and the label
must be 'Main'. For algorithms with multiple "entry points", such
as insert and search, the implementation uses separate modules so the
Real code must be split. Where code for one entry point calls another
(such as in union-find), Real code must be split and duplicated.
Note: The implementation currently just ignores everything outside code blocks.
\Code}: End of a code block.
\Ref: A line of code may end in \Ref, followed by a label that
names another code block. The \Ref directive shows that the line of
pseudocode can be refined: the user can perform an action, such as a
mouse click, to replace the line by the code block of the name specified
by \Ref. Similarly, the code block specified by \Ref can be condensed,
to show, once again, the original line of pseudocode.
\B: A line of code may end in \B, followed by a label. These labels are
bookmarks, used by the implementation for the purposes of synchronising
the animation and pseudocode. To date, bookmarks have been added by
developers but could potentially be added by educators (note they relate
to just the animation, not the structure of the algorithm). Lines with
no bookmark (or refinements that contain bookmarks) cannot have any
associated animation and are skipped over in the execution. All bookmarks
must be unique. In the animations developed initially, bookmarks were
all numbers, leading to "magic numbers" in the code. There is no reason
why more meaningful names cannot be used, and this is recommended to
make code more readable.
\Expl{: Start of an explanation. This directive appears after a line of
pseudocode (usually on the next line), and is a plain language explanation
of the preceding pseudocode. The explanation is shown in the explanation
display (not directly in the pseudocode) when requested by the user by
some mechanism, such clicking on an icon next to the line of pseudocode.
\Expl}: End of an explanation. All text between the start and the end
of the explanation (plus any trailing newline) is not included in the
displayed pseudocode (but is accessible via the mechanism chosen for
showing explanations). Any trailing newline character is also ignored in
the display.
\In{: Used within code blocks to specify deeper indentation. The lines
of pseudocode between \In{ and \In} will be indented one level more
than the current indentation level. Leading spaces and tabs on code
lines are ignored.
\In}: End indentation, that is, go back to the level of indentation
that was current before the corresponding \In{. Any trailing newlines
after indentation directives are ignored for the purpose of displaying
pseudocode.
\Newline: Display a newline.
\ : that is, a backslash followed by a space. This will be displayed
as a space (and so can be used to force extra indentation).
Note: Not currently implemented.
\\: This is displayed as a single backslash in pseudo-code.
Note: Not currently implemented.
A note about whitespace: Unless otherwise specified, whitespace in
the algorithm specification is for human readability only. Blank lines
outside of a code block contained between \Code{ and \Code} are not
shown in the AIA display. Similarly, indentations outside of a segment
between \In{ and \In} are not displayed.
For educators writing Real specifications, we now provide a few suggestions based on our experiences with writing pseudo-code for AIA over the years.
Forget code efficiency: AIA is designed to teach people about
algorithms, not efficient coding. If you are an algorithm expert you
probably like neat coding as well - try to forget that. No matter how
neat your preferred coding is, the simplest coding that illustrates the
algorithm in the clearest way is better for the goal of AIA. You can
always put extra information in explanations or the overview, mentioning
how the algorithm can be coded more efficiently than the way presented.
Write code as well as pseudo-code: Pseudo-code can have bugs, just as
code can. By writing code based on your psuedo-code you can test and
debug it. Make sure your code really has the same structure as the
pseudo-code - if the code can't easily be structured that way, the
pseudo-code probably needs adjustment. Again, don't worry about style or
efficiency; just concentrate on structure and correctness.
Include your code in a note: This keeps everything relevant in one Real
file. Also, the AIA developers need to code the algorithm in order to
animate it - if you provide code it makes their job easier. Code is also
unambigous, where as psuedo-code can potentially be misunderstood.
Include notes on animation: The AIA developers need to know how you want
the code animated. It's worthwhile at least having an overview in the
Real file, including any subtle points. Details will no doubt need
further refinement and discussion with developers but subtleties can be
missed.
You can always remove clutter: Sometimes Real code can get rather
cluttered with notes, explanations, etc. It's pretty easy to remove
them and we have written a very simple/naive bash script, currently in
doc/Real/cleanreal that removes a bunch of things so the pseudo-code
is easier to read as it is being developed.
Try to be consistent: Ideally we should have a proper style guide for
Real, but currently we don't. However, you can look at animations and
Real code that have been developed and try to follow the same
conventions unless there is a good reason not to.
Consider common structure of different algorithms: Sometimes there are
several algorithms with very similar structure. Real can emphasise this
by having the same (or very similar) top level pseudo-code, which may be
beneficial. This sometimes involves compromises with minor details of
some of the algorithms.
Top level pseudo-code should not be trivial: Very early in the original
development of AIA we had a single line of pseudo-code at the top level:
something like "Sort array". Despite being very elegant, allowing an
explanation of what sorting is and illustration of what the algorithm
computes in a single step, it just confused many of the students. The
top level needs to have at least a couple of distinct steps.
You don't have to spell everything out: It is reasonable to assume that
students using AIA will understand basic coding and will understand
simple concepts before attempting to understand complex algorithms. If
you are writing Real code for something simple like selection sort it's
worth refining a line like
"m <- the index of the minimum element of a[i]...a[max]"
but for more complex algorithms the extra code in the
fully refined version may just be a distraction from the key points in
the algorithm. In theory, the fully refined version could be code that
can be executed - elegant, but AIA is not about coding. Some
students have a "bottom up" learning style, where the first thing they
do is expand everything, and if the fully expanded version is not too
long it may help these students especially.
By AIA Organization