Hacker News Reader

Comment by man-and-laptop | Hacker News Reader

If regexps are understood as a kind of "baby" programming language, and the techniques for implementing it are understood as "baby" implementation techniques for more complete languages, does "differentiation" have any applications in implementing more complete programming languages?

As an aside, why do I think of regexps as a kind of "baby" programming language? Because:

- They can be converted to NFAs or DFAs. These NFAs and DFAs resemble assembly languages. The "assembly language" for NFA is actually quite exotic. Reminds me of compilation.

- NFAs can be understood as a kind of Virtual Machine. DFAs are like a subset of a physical machine.

- Just In Time compilation was first applied to regexps before anything else. This was done by Ken Thompson.

- The interpreter->compiler algorithm in RPython (the program that is used to produce PyPy) works quite well on regexps. This essentially automates the work that Ken Thompson did.

View on HN

> does "differentiation" have any applications in implementing more complete programming languages?

I'm not sure about implementing per se, but you can extend some notion of differentiation to richer programming languages: https://www.sciencedirect.com/science/article/pii/S030439750...

The differential of a term does give you some information about how a term behaves under reduction, so I guess the answer is "maybe" - sounds like a fun project to work on. :)

More generally, there are models of linear logic built on a notion of differentiation (mentioned in the same paper as above), which might translate to a compilation of linear lambda calculus/classical processes/pi calculus/etc.

> does "differentiation" have any applications in implementing more complete programming languages?

It seems to: http://matt.might.net/articles/parsing-with-derivatives/

To clarify, the programming language in your link is BNF. Clearly, BNF is a more expressive language than regexp.

I was actually thinking of differentiating whole programs. But still interesting.

A Theory of Changes for Higher-Order Languages - Incrementalizing λ-Calculi by Static Differentiation

> [...] We present a program transformation taking programs to their derivatives, which is fully static and automatic, supports first-class functions, and produces derivatives amenable to standard optimization.

https://arxiv.org/abs/1312.0658

> the programming language in your link is BNF

The programming language follows a context-free grammar (CFG), which has been written in Backus-Naur Form (BNF). It is technically nonsensical to say "the programming language is BNF". It's like if I were to say "English is a Roman language" because we happen to use the Roman letters for our orthography. Just a technical nitpick.

> BNF is a more expressive language than regexp

The context-free languages are more expressive than the regular languages. BNF is a notation for writing a context-free grammar, and regular expressions are a notation for writing regular languages. (Again, a nitpick of terminology.)

> Just In Time compilation was first applied to regexps before anything else. This was done by Ken Thompson.

Citation for this? I'd be surprised if Thompson was first. Runtime optimization was long the domain of Lisp programmers. Blurring the distinction between compile-time and run-time is one of PG's things that "made Lisp different".

https://eli.thegreenplace.net/2013/11/05/how-to-jit-an-intro... references a paper by Aycock, which says McCarthy was first, in his original Lisp paper, nearly a decade before Thompson.

I think Rob Pike mentioned it in a recent talk on the history of Unix https://youtu.be/_2NI6t2r_Hs?t=1901

He says this is the first case of regular expressions on a computer, which I believe, but I'm not hearing anything about runtime optimization or compilation.

less than one minute later he mentions "compiling on the fly" some assembly code https://youtu.be/_2NI6t2r_Hs?t=1944

Sure, but he never claims that's the first instance of runtime compilation, just that the implementation is "pretty interesting".

NFAs are not a "kind of virtual machine". The "assembly" language for an actual NFA is no more complex than the one for a DFA.

They are state machines that can be in a lot of states at once; that's all. There is a debasement of the term NFA, popularized by Friedl, that "NFA" means "any thingy that implements regex that isn't a DFA". This isn't true and should not be promulgated.

They are a virtual machine because the physical hardware can't be in more than one state at the same time. Representing an NFA as an assembly-type program makes it resemble something like the JVM, in that it looks like an assembly language for a non-physical machine. Virtual=non-physical

I think you're being pedantic.

It's a strained metaphor which casts no light on actual NFA implementation or the true distinction of NFAs and DFAs.

In this case, instead of the distinction between "virtual" and "physical" we have, considerably less pretentiously, an "state id" vs a "set of state ids" (in case of actual NFA implementation, said set might well be represented by a bit-vector whether a general purpose register or a SIMD register).

Making tortured analogies to JVMs and virtual machines doesn't actually help explain anything about what's going on. It certainly fails to provide the insight that you might get from comparing the whole "id vs set-of-ids" (one can instantly intuit the risk of an exponential blowout in NFA->DFA conversion, which does in fact exist).

Regarding the strained metaphor, the "virtual machine" is metaphorical, and it can be simply ignored because any possible implementation of a NFA is actually a DFA. Proof: a finite amount of memory can be considered a DFA state and modifying that memory between consuming successive input symbols can be considered updating the state.

Yes, I think "virtual machine" is too loaded of a term now and is just confusing the point?

An NFA implementation can be "virtual" in the sense of "virtual memory" being virtual. It is a pretense of a practically unbounded set of states while really being bounded like any other practical implementation. It grows on demand and can handle many practical inputs while possibly hitting its implementation limits on a worst-case input.

This is where I got the VM analogy from: https://swtch.com/~rsc/regexp/regexp2.html

My whole comment was about tenuous but interesting analogies, and whether they can lead to somewhere interesting.

Fair enough. I think that implementation is a dreadful straight NFA implementation - and, IIRC, is not used in RE2 for pure NFA code.

It's not a dreadful way of implementing regex as it can do things a straightforward bitset NFA implementation can't.

To be fair, I think your original post does stand, but I guess I am a bit pedantic about the terminology after spending a little bit of time on regex implementation.

In fact, a number of strategies in regex implementation turned out to generalize to broader areas. The bitwise automata are helpful elsewhere, as are many of the strategies one might use to make them fast. The 4 Russians technique ( https://en.wikipedia.org/wiki/Method_of_Four_Russians ) has also cropped up all over the place.

Zipper is pretty interesting http://okmij.org/ftp/continuations/zipper.html

The idea of taking the derivative of an algebraic data type is also discussed in "Categories and Computer Science" from 1992: https://www.cambridge.org/core/books/categories-and-computer...

That discussion covers some of the same ground as the Taylor series idea elsewhere in thus discussion. It doesn't get as far as inventing the zipper concept.

You can see all of these as data structures instead of programs and then derivatives transfer and generalize nicely: see Conoc McBride’s work on zippers.

> NFAs can be understood as a kind of Virtual Machine. DFAs are like a subset of a physical machine.

One of the projects for the class I mentioned in another comment was actually implementing a stack-based virtual machine for regular expressions!

Reply on news.ycombinator.com