4 ms·

If regexps are understood as a kind of "baby" programming language, and the techniques for implementing it are understood as "baby" implementation techniques fo

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.

mehrdadn 8y ago
> does "differentiation" have any applications in implementing more complete programming languages? It seems to: http://matt.might.net/articles/parsing-with-derivatives/ http://matt.might.net/articles/parsing-with-derivatives/
- man-and-laptop 8y ago
  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.
  - cgrand-net 8y ago
    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 https://arxiv.org/abs/1312.0658
  - DonaldPShimoda 8y ago
    > 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.)
saagarjha 8y ago
> 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!
CuriousSkeptic 8y ago
Zipper is pretty interesting http://okmij.org/ftp/continuations/zipper.html http://okmij.org/ftp/continuations/zipper.html
- deleted 8y ago
  [deleted]
- theoh 8y ago
  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-science/203EBBEE29BEADB035C9DD80191E67B1 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.
- deleted 8y ago
  [deleted]
glangdale 8y ago
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.
- man-and-laptop 8y ago
  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.
  - glangdale 8y ago
    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).
    - deleted 8y ago
      [deleted]
    - deleted 8y ago
      [deleted]
    - HelloNurse 8y ago
      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.
ken 8y ago
> 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-introduction 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.
- chombier 8y ago
  I think Rob Pike mentioned it in a recent talk on the history of Unix https://youtu.be/_2NI6t2r_Hs?t=1901 https://youtu.be/_2NI6t2r_Hs?t=1901
  - ken 8y ago
    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.
    - chombier 8y ago
      less than one minute later he mentions "compiling on the fly" some assembly code https://youtu.be/_2NI6t2r_Hs?t=1944 https://youtu.be/_2NI6t2r_Hs?t=1944
      - ken 8y ago
        Sure, but he never claims that's the first instance of runtime compilation, just that the implementation is "pretty interesting".
fmap 8y ago
> 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/S030439750300392X 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.
tel 8y ago
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.
deleted 8y ago
[deleted]

mehrdadn 8y ago

> does "differentiation" have any applications in implementing more complete programming languages? It seems to: http://matt.might.net/articles/parsing-with-derivatives/ http://matt.might.net/articles/parsing-with-derivatives/

man-and-laptop 8y ago
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.
- cgrand-net 8y ago
  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 https://arxiv.org/abs/1312.0658
- DonaldPShimoda 8y ago
  > 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.)

saagarjha 8y ago

> 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!

CuriousSkeptic 8y ago

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

deleted 8y ago
[deleted]
theoh 8y ago
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-science/203EBBEE29BEADB035C9DD80191E67B1 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.
deleted 8y ago
[deleted]

glangdale 8y ago

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.

man-and-laptop 8y ago
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.
- glangdale 8y ago
  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).
  - deleted 8y ago
    [deleted]
  - deleted 8y ago
    [deleted]
  - HelloNurse 8y ago
    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.

ken 8y ago

> 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-introduction 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.

chombier 8y ago
I think Rob Pike mentioned it in a recent talk on the history of Unix https://youtu.be/_2NI6t2r_Hs?t=1901 https://youtu.be/_2NI6t2r_Hs?t=1901
- ken 8y ago
  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.
  - chombier 8y ago
    less than one minute later he mentions "compiling on the fly" some assembly code https://youtu.be/_2NI6t2r_Hs?t=1944 https://youtu.be/_2NI6t2r_Hs?t=1944
    - ken 8y ago
      Sure, but he never claims that's the first instance of runtime compilation, just that the implementation is "pretty interesting".

fmap 8y ago

> 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/S030439750300392X 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.

tel 8y ago

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.

deleted 8y ago

[deleted]