Category: Relision

Turing Complete

P = computability is the cornerstone of P

SKK = I
SKK = I

The Relision system is now Turing complete. This is a good thing, but there is a crazy amount of work left to do. Right now only the simplest matching is performed to allow somewhat trivial lambda expressions to work.

The screenshot is probably not that impressive. What is going on?

Continue reading “Turing Complete”

Documentation

Documentation is a story about the past. Usually fictional.

A job is not done until you have bragged about it. Let’s call that “documentation.”

I’ve created a wiki to host this documentation, and you can find it here.

One of the magical things about creating user documentation is that you quickly realize what a horrible user experience you have created, and the code starts changing (and improving, one hopes). “Just create a FooFactory instance from the AbstractFooFactoryGenerator, after initializing the configuration system and creating a Context object with your custom Frabulator.” Madness!

In any case, user documentation is now materializing on the wiki, and the code is changing in response. Let’s hope this is a positive development. Feel free to constructively criticize.

Trivial Recursive-Descent Parsing

Adding a tiny parsing module to Relision

Having gotten the basic REPL working, I needed to begin building the parsing stuff. For that, I decided on porting my idiotically simple recursive-descent parser library to Rust because that seemed like a thing I might do, and I’m nothing if not me.

Continue reading “Trivial Recursive-Descent Parsing”

The Relision REPL

Putting the REPL before the horse

I’ve made a few starts at a rewrite of Elision focusing on implementing the terms, but I have been much too busy to make much progress. One of the issues is that as the terms are implemented I need to write a large number of tests. That’s okay – testing is good – but I end up with a lot of code that gets thrown away at some point.

Instead, I decided to write the read, evaluate, print loop (REPL) first this time, followed by iterative implementation of the parser and terms. This means that I can write the tests in the rewriter’s language and just modify the plumbing as I make changes. It also means I can “prime” the system by writing the bootstrapping library as I go.

So that’s the plan. The REPL is now done, complete with configuration, history, command line processing, etc

So now it is on to implementing the terms.

Relision

Rewriting a term rewriter library… in Rust!

I’m the primary author of the Elision term rewriter library, which I donated to Oak Ridge National Laboratory a few years back.  Elision was a core part of the Hyperion static analysis tool, and that tool has subsequently been licensed to a private company, Lenvio (now being renamed as “Affirm Logic”), to grow and improve.  Elision is written in Scala and fits well with the Hyperion system, which is written in a mix of Java and Python.

There are many things I like about Elision, and many things I don’t.  In particular there was a notion of “metavariables” that I really disliked, and some unusually cryptic notation that really just needs to go.  Finally, the choice of Scala had some consequences (such as running on the JVM) which made some of the things we hoped to do (like running on Titan or Summit) hard.

Relision is not a rewrite of Elision, but a new term rewriting library, being written (this time) in Rust.  I considered writing it in C++, but decided that the guarantees that Rust provides, combined with the fact that Rust has become (reasonably) mature, make it the right language to use.

The emphasis in Relision is going to be on performance.  Elision had quite good performance, but I think with native code and concurrency we can do better.

Anyway, that’s my goal and we will see how far I manage to get.