Parsing the Wolfram Language

Good tools make good workers. - French proverbs

Brenton Bostick, Wolfram Research

brenton@wolfram.com

Outline

Overview of WL Syntax

Presenting a new parser for WL

Instrumentation technology (Profiling and Coverage)

Overview of WL Syntax

~1000 longnames

about 2/3 are letterlike and 1/3 are punctuation

a smattering of spacing, newline characters

\[CurlyCapitalUpsilon]

\[ScriptCapitalJ]

\[FiLigature]

\[NotLeftTriangleEqual]

~80 ASCII operators

a ;; b ;; c

a!!

a <-> b

~300 non-ASCII operators

a \[Proportional] b \[Proportional] c

a \[Subset] b

a \[InvisibleApplication] b

Quiz

How well do you know WL syntax?

Quiz (warm-up)

Warm up with some Reals tokenization

1.2`-

What comes after, always a Real?

Answer

1.2`-3

No!

1.2`->3

Quiz (warm-up)

123`.

What comes after, always a Real?

Answer

123`.45

No!

123`.abc

Could be Dot operator!

Quiz

What are these?

0.

0..

0...

0....

0.....

Quiz

Are these the same?

Ordering inside Alternatives does not matter, right?

a | b : c

b : c | a

Quiz

What is this?

a_?b[x]

Then what is this?

a_?b[x]&

? is surprisingly high

& is surprisingly low

Quiz

Using the same name for 2 branches of Alternatives is fine, right?

a : x[] | a : y[]

| is surprisingly high (just above :)

Quiz

What is this?

a;;!b

And what is this?

a;;!

Quiz (quick fire)

What is this?

x=.0

Quiz (quick fire)

What is this?

_...

Quiz (quick fire)

What is this?

_.0

Quiz (quick fire)

What is this?

t/.3->.4

Quiz

Are there operators that are both prefix and infix (possibly postfix) ?

Answer

+a
a + b

-a
a - b

;;
;;b
;;b;;c
;;;;c
a;;
a;;b
a;;;;c
a;;b;;c

! is prefix and postfix

!a
a!

++ is prefix and postfix

++a
a++

-- is prefix and postfix

--a
a--

Quiz

Symbols may have non-ASCII characters. Are there any non-ASCII symbols in System` ?

Answer

Names["System`*"][[;;116]]//InputForm

Quiz

Are there any binary operators that are not infix?

Think Polish or reverse-Polish...

Answer

\[Integral] f \[DifferentialD] x

Moral of the Story

WL syntax is complicated

In WL, tokenizing is harder than parsing

There are a lot of operators in WL

Unintuitive precedences

: is its own beast

Limitations of old parser

Why write a new parser?

Stack depth limit:

ToExpression[StringJoin[Table["f@",260],"a"]]

Error reporting:

ToExpression["f["]

what’s the error?

"featuroids"

These parse differently:

a <> StringJoin[b] //Hold

a <> StringJoin@b //Hold

Kernel and FE are not in parity

Can lead to a lot of head scratching.

(just for Halloween)

spooky edge case bugs
👻

Evaluate at your own risk:

\(12`\)

1.2`-\:0041

Design goals of a new parser

Maintain clean separation between layers

Byte stream, at lowest level

Source character stream

WL character stream

Token stream

Expression stream, at highest level

Maintain clean separation between levels of abstraction

Concrete syntax tree

Aggregate syntax tree

Abstract syntax tree

Error handling, reporting, recovery

Concepts

Source characters and WL characters

\[Alpha]

is 8 source characters, but 1 WL character

α

is 1 source character and 1 WL character

Trivia

comments, whitespace, newlines, line continuations

Levels of abstraction

Concrete syntax (think: boxes in FE)

Aggregate syntax is concrete syntax, with trivia removed

Abstract syntax (think: FullForm)

Implementation details

Modeled as Pratt parser

Recursive descent parser that associates semantics with tokens instead of grammar rules

output of cloc (for Jason):

-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
Mathematica                     27           2532           1320          29114
C++                             27           3416           1684          14032
C/C++ Header                    19            705            324           3850
CMake                           14            214            142            808
C                                2            111             52            530
make                             1            209             98            395
Markdown                         2             66              0            120
XML                              2             38             18             97
-------------------------------------------------------------------------------
SUM:                            94           7291           3638          48946
-------------------------------------------------------------------------------

basic parselets:

BinaryOperatorParselet (for binary operators)

GroupParselet (for group operators like {} )

InfixOperatorParselet (for infix operators)

PostfixOperatorParselet

PrefixOperatorParselet

specialized parselets:

ColonParselet (because : has special rules)

EqualParselet (because of =. )

InequalityParselet and VectorInequalityParselet (to keep them grouped together)

InfixOperatorWithTrailingParselet (for , or ;)

IntegralParselet (for \ [Integral])

LinearSyntaxOpenParenParselet (for \ ( \ ) )

SemiSemiParselet (for ;;)

SlashColonParselet ( for /: )

StartOfLineParselet ( for ? or ?? at start of line )

SymbolParselet ( for a_ )

TildeParselet ( for a ~f~ b)

UnderParselet ( for _a )

New parser

Needs["AST`"]

ParseString["1+1"]

All nodes have a common structure:

Node[tag, children, data]

Parsing strings

Use ParseString if you don’t care about concrete syntax:

ParseString["1+1"]

ToFullFormString[%]

Use ConcreteParseString if you do:

ConcreteParseString["1+(*comment*)1"]

ToSourceCharacterString[%]

Parsing files

codetoolsExamplesDir=NotebookDirectory[];

file=FileNameJoin[{codetoolsExamplesDir,"Collatz","Collatz.m"}]

ParseFile[file]

ConcreteParseFile[file]

Stack depth limit:

ParseString[StringJoin[Table["f@",260],"a"]]

ToFullFormString[%]

ParseString[StringJoin[Table["f@",1000],"a"]]

ToFullFormString[%]

Error reporting

(Using Lint` for nice formatting)

Needs["Lint`"]

LintStringReport["f["]

Salient error messages

Continue parsing in the face of errors

LintStringReport["{ + } * 3"]

Applications: Instrumentation

Rewrite source code to allow collection of data when entering / exiting functions

Profiling

Coverage reporting

Memory allocation tracking

etc.

Other applications:

Code Transformations

Profiling WL Code

The functions in the Instrumentation` context provide support for profiling WL code.

First we must load the Instrumentation` package:

Quit[]

Needs["Instrumentation`"]

Next we must instrument the code to be profiled.

codetoolsExamplesDir=NotebookDirectory[];

ProfileInstrument[FileNameJoin[{codetoolsExamplesDir,"Collatz"}],FileNameJoin[{codetoolsExamplesDir,"Collatz-profile","Collatz"}]]

Verify that instrumented code is found

PrependTo[$Path,FileNameJoin[{codetoolsExamplesDir,"Collatz-profile","Collatz"}]];

FindFile["Collatz`"]

Load the instrumented code

Needs["Collatz`"]

Evaluate an expression to be profiled

{res,profileData}=ProfileEvaluate[Collatz[27]];

See the result

res

Verify the profiling data is present

profileData

Process the profiling data

reportData=ProfileProcess[profileData];

Generate a report in a separate notebook

ProfileReport[reportData,"FileNamePrefixPattern"->"/Users/brenton/development/stash/COD/codetoolsdocs/Presentations/2019/WTC2019/Collatz/"]

Coverage reporting of WL Code

The functions in the Instrumentation` context provide support for coverage reporting of WL code.

First we need to load the Instrumentation` package:

Quit[]

Needs["Instrumentation`"]

Next we must instrument the code for coverage reporting. This tutorial assumes that the codetoolsexamples repo is next to the coverage repo in your setup.

codetoolsExamplesDir=NotebookDirectory[];

baselineData=CoverageInstrument[FileNameJoin[{codetoolsExamplesDir,"Collatz"}],FileNameJoin[{codetoolsExamplesDir,"Collatz-coverage","Collatz"}]];

Verify baselineData is present

baselineData

Verify that instrumented code is found

PrependTo[$Path,FileNameJoin[{codetoolsExamplesDir,"Collatz-coverage","Collatz"}]];

FindFile["Collatz`"]

Evaluate an expression for coverage reporting. We include the Needs because we want to include the code that runs at startup in the coverage report.

{res,runData}=CoverageEvaluate[Needs["Collatz`"];Collatz`Collatz[27]];

Verify runData

runData

runData//InputForm

Process the coverage data

CoverageProcess[baselineData,FileNameJoin[{codetoolsExamplesDir,"Collatz-coverage","Collatz"}],"coverage-baseline.lcov"]

CoverageProcess[runData,FileNameJoin[{codetoolsExamplesDir,"Collatz-coverage","Collatz"}],"coverage-run.lcov"]

Now you must run the lcov and genhtml commands on the command-line.

lcov -a coverage-baseline.lcov -a coverage-run.lcov -o coverage-combined.lcov

genhtml --num-spaces 4 coverage-combined.lcov -o report

Below is a transcript of running the commands on a machine.

brenton2maclap:Collatz brenton$ cd /Users/brenton/development/stash/COD/codetoolsdocs/Presentations/2019/WTC2019/Collatz-coverage/Collatz

brenton2maclap:Collatz brenton$ lcov -a coverage-baseline.lcov -a coverage-run.lcov -o coverage-combined.lcov
Combining tracefiles.
Reading tracefile coverage-baseline.lcov
Reading tracefile coverage-run.lcov
Writing data to coverage-combined.lcov
Summary coverage rate:
  lines......: 80.0% (4 of 5 lines)
  functions..: 80.0% (4 of 5 functions)
  branches...: no data found
brenton2maclap:Collatz brenton$ 
brenton2maclap:Collatz brenton$ 
brenton2maclap:Collatz brenton$ 
brenton2maclap:Collatz brenton$ 
brenton2maclap:Collatz brenton$ genhtml --num-spaces 4 coverage-combined.lcov -o report
Reading data file coverage-combined.lcov
Found 1 entries.
Found common filename prefix "/Users/brenton/development/stash/COD/codetoolsdocs/Presentations/2019/WTC2019"
Writing .css and .png files.
Generating output.
Processing file Collatz/Collatz.m
Writing directory view page.
Overall coverage rate:
  lines......: 80.0% (4 of 5 lines)
  functions..: 80.0% (4 of 5 functions)
brenton2maclap:Collatz brenton$

The report is generated in the report directory. The toplevel index page shows the line coverage and function coverage of each directory.

You can dig down to individual files and see line coverage and function coverage.

Future

Formatter for WL code

Pretty printer.

Actively working on new formatter.

Ideas for formatting, let me know!!

Source map

For debugging

Package format v2

Attribute grammar

Synthesized and inherited attributes

Rewrite as LL(1) parser

Still possible to hit stack limits of OS, just not as easy

New Compiler: return expressions directly kernel

Integration into kernel

Thank you!

(come to my talk Finding Bugs in the Wolfram Language @ 4:30)

Links

In-product docs:

Obtaining AST paclet

PacletUpdate["AST","Site"->"http://pacletserver.wolfram.com","UpdateSites"->True]

Pratt parser

https://en.wikipedia.org/wiki/Pratt_parser

Trivia in Roslyn compiler

https://github.com/dotnet/roslyn/wiki/Roslyn-Overview#syntax-trivia