Patterns in Piggy are regular expressions of parenthesized expressions that represent trees. The conversion of the regular expressions to a finite state automaton is easy (via Thompson’s Construction), but the resulting automaton for the pattern may not work for an important reason: patterns that specify attributes and children of an AST node have an implicit “…” between each attribute or child pattern. While it’s possible to introduce additional states to recognize “…” between each attribute or child node in the pattern, the resulting automaton is ambiguous. For every input AST node, any attribute or child AST node can mismatch a “sub-pattern”, but can still match the complete pattern.
Continue readingSeries on program transformation systems: ROSE (2000)
This is the next entry in the series on program transformation systems. This article describes ROSE, a compiler system for C, C++, Java, Python, PHP source code. It has been in development since 2000 and is actively being developed to this day. ROSE was developed at the Lawrence Livermore National Laboratory.
Continue readingSeries on program transformation systems: Spoon (2005)
This is the next entry in the series on program transformation systems. This article describes Spoon, a system for Java source code. It has been in development since 2005 and is actively being developed to this day.
Continue readingSpeeding up this website
A few months ago, I started to migrate some of my websites to DigitalOcean because the cost of a virtual server is $5/mo. So, I moved CodingGorilla.com to the new host. (Note, a long story, but the name came from an old boss, who saw I have the patience of a saint and attention to minute details, the traits of any good programmer.)
Unfortunately, the website has been painfully slow because I was told that you should keep your database and web server on separate hardware. This may be fine for large corps which have their servers on a fast LAN, but this was the wrong advice for a blog. I moved the MySQL database to the web server, and now the website works ~100x faster. Adage for the day: Believe half of what you see and nothing of what you hear.
Incidentally, the tool which I used to find this problem is Query Monitor by John
Series on program transformation systems: C-Breeze (2004)
This is the next entry in the series on program transformation systems. This article describes C-Breeze, a compiler system for C source code.
Continue readingRewriting the pattern matching engine — part 1
For the last two weeks, I’ve trying to write Piggy patterns to construct a symbol table from a Java AST. Patch after patch, I’d change the pattern matching code to “fix” something that wasn’t working. Unfortunately, I finally wrote a pattern that broke the camel’s back, “< classBodyDeclaration < modifier >* <
So, I decided to rewrite the engine the way it should have been done: using an NFA. It’s so far taken a week or so, but it turns that the pattern matcher is much cleaner, and likely faster. In addition, the output engine–which executes the code blocks in the pattern–is also much cleaner. I’ll try to see if I can combine the patterns together in one automaton.
I really should have known better than to approach the tree regular expression matching problem following what other people did, using a top-down recursive recognizer. Live and learn. Always follow a clean, clear theory instead of just hacking.
Series on program transformation systems: Coccinelle (2006)
Due to my work on Piggy, I’m starting to do a thorough review of the literature on program transformation systems, how Piggy relates to prior research, and what improvements I can make to Piggy. Note, a good list to start from is in Wikipedia: ASF+SDF, CIL (for C), Coccinelle (for C), DMS, Fermat, Spoon (for Java), Stratego/XT, TXL). This is the first entry in the series, on Coccinelle, a system that modifies
What the hell is that?
No ifs, ands, or buts, news about Net Standard may be old and stale, but one thing still applies: As Steve Martin would say, “What the hell is that?” Believe it or not, I started writing this entry years ago, a few months after Net Standard first came out. I had hoped that if I just write about it, I’d somehow stumble across what the hell it is. But, I didn’t get anywhere because most people don’t know what the hell they’re talking about. Fast forward to now.
A quick note on Piggy patterns and comparison with XPath
XPath (1, 2, 3) is a language for finding nodes in an XML tree, and has a long history in AST search. Maletic et al. (4) is probably the first paper on XPath used on ASTs, using Antlr. It was further researched and is now part of the OSS world (5). In 2014, Parr added to Antlr releases an XPath API to search Antlr-generated ASTs (6). Src-d uses XPath and an engine for “universal” ASTs (7).
Piggy as a build tool
One further refinement to Piggy is required before I make a release of the tool: a wrapper to get the tool under MSBuild. Like the Antlr4BuildTasks wrapper I forked from Antlr4cs, I want Piggy to work seamlessly during the build of a C# project that uses a native library. My plan is for C# projects to contain the Piggy templates required to generate the declarations for C# of the interface needed by the project. Required by the user would be a template for Piggy and C++ file for the Clang compiler. During a build, the Piggy tool would run and produce C# output in the build directory, compiled and linked with the project. So, instead of users writing the DllImport decls to work with a native library, just indicate what you want and let Piggy do the rest. The build tool would be released to NuGet, and would contain the Clang serializer, the Piggy tool, the assembly wrapper for the Clang serializer and Piggy, and all the build rules.