cstjnodLaboratory notebook

Languages / Language

2015

Raku

Where the regular expression grew up and became a grammar.

Raku began life as Perl 6. Larry Wall started designing it in 2000, the first stable release came on Christmas Day 2015, and in 2019 it took a name of its own. It does many things, but the best reason to come here is what it did to the regular expression, the end of a line that runs back to 1951.

The regex line

  • 1951, Kleene. At RAND, the logician Stephen Kleene wrote a memo on which “events” a nerve net or finite automaton can recognise. His answer was the regular events, built from sequence, alternation and repetition. The repetition star still carries his name. The memo was published in 1956 in Automata Studies.
  • 1968, Thompson. Ken Thompson put Kleene’s notation into QED, a text editor on MIT’s CTSS time-sharing system, so you could search a file by pattern. For speed he compiled each pattern into IBM 7094 machine code on the fly, and described how in a short paper in Communications of the ACM. He carried the idea into ed, the Unix editor.
  • The 1970s, the Unix tools. At Bell Labs, ed’s command g/re/p (globally, regular expression, print) became grep, which shipped in Version 4 Unix. Lee McMahon’s sed (1973-74) streamed ed’s substitutions over whole files, and awk (1977, from Aho, Weinberger and Kernighan) wrapped patterns in a small language. Each tool had its own dialect.
  • 1987, Perl. Wall pulled regexes into the language itself: matching and substitution became operators, not another program to pipe through. Its source went round Usenet billed as a “replacement” for awk and sed, and over the 1990s its regexes grew features the Unix tools never had. In 1997 Philip Hazel wrote PCRE, Perl Compatible Regular Expressions, for the Exim mail server, and Perl’s dialect spread to PHP and far beyond. It is the dialect most programmers mean by “regex” today.
  • 2002, Apocalypse 5. Then Wall turned on his own creation. “Regular expression culture is a mess, and I share some of the blame,” he wrote, and redesigned it from the ground up for Perl 6.

What Apocalypse 5 changed

  • Whitespace is for reading. It is ignored inside a pattern unless you ask for it, so a regex can be laid out and commented like code.
  • Named rules. <ident> calls another rule by name; [...] groups without capturing; <[a-z]> is a character class. The old line noise gives way to words.
  • Grammars. Named rules collect into a grammar, a special kind of class you can inherit from and extend. A match returns a tree of named captures, not a row of $1, $2, $3.
  • Parsers, not patterns. Put together, a grammar is a real parser, which regexes alone could never be. It reads a lot like BNF. Rakudo, the main compiler, parses Raku itself with a grammar.

The long road

In July 2000, at the fourth Perl Conference, a morning meeting about how Perl’s development was run turned into something bigger. Jon Orwant argued that new rules would change nothing if nobody was excited any more (the story goes that he threw a coffee mug at the wall to make the point), and by the end of the morning the group had decided to start Perl 6. Wall announced it the next day. The community sent in 361 proposals, and Wall answered them in a series of essays called Apocalypses; the fifth was the one about regexes.

The first stable release, Rakudo’s “Christmas” release of language version 6.c, arrived on 25 December 2015. By then it was plain that Perl 6 was not the next Perl 5 but a different language, and sharing a name was hurting both. In October 2019 Wall approved renaming it Raku, quoting the parable about new wine and old wineskins. Perl 5 went back to being simply Perl.

Beyond grammars, Raku has junctions (if $x == any(1, 2, 3)), lazy lists (0, 1, * + * ... * is the whole Fibonacci sequence), and gradual typing: write no types, then add them where you want the compiler to check.

Where it runs

Rakudo runs on MoarVM, a virtual machine built for Rakudo and its NQP toolchain, and can also target the JVM. The road there was not straight: an early virtual machine called Parrot came and went, and in February 2005 Audrey Tang wrote Pugs, an implementation in Haskell, which showed the design could run. Its tests became the executable specification Raku is still checked against.

The people

  • Larry Wall studied natural and artificial languages, and he and his wife once planned to devise a writing system for an unwritten language; ill health ended that. A linguist’s eye shows in everything he designed. He wrote the rn newsreader and the patch program, and in 1987, at System Development Corporation, he wrote Perl, posting version 1.0 on 18 December. Its manual said it combined some of the best features of C, sed, awk and sh. He led the Perl 6 design through to the 2015 release.
  • Audrey Tang wrote Pugs in Haskell in 2005. It showed the design could run, and its tests outlived it as the language’s specification.
  • Elizabeth Mattijsen opened the 2019 proposal to rename the language, “Path to Raku”, which Wall approved that October.

What made them different was patience, or stubbornness. Most redesigns ship in a couple of years by keeping what they can. Raku took fifteen and broke compatibility on purpose, on the bet that a language built to last should be designed before it is frozen. The regex redesign is the clearest case: Wall had made Perl’s regexes the most copied in the world, and threw them out anyway.

Landmark open-source projects

  • Rakudo: the compiler.
  • MoarVM: the virtual machine it runs on.
  • zef: the module manager.
  • Cro: libraries for building services and web applications.

Try it

# A grammar is a parser you declare. Whitespace in a rule is there to be read.
grammar Settings {
    rule  TOP   { <pair>+ }
    rule  pair  { <key> '=' <value> }
    token key   { \w+ }
    token value { <-[\s]>+ }
}

my $m = Settings.parse('lang = Raku   year = 2015');
say "$_<key> is $_<value>" for $m<pair>;

Sources

See also: BNF, C, Bell Labs.