Syntax, Formal Language, Pattern Matching

By Xah Lee. Date:

I have realized recently, that if you like formal systems as much as i do, then the only such language are pattern matching systems, or term-rewriting system, which is what Mathematica is.

Following is a excerpt from Wikipedia Formal language. I highlighted the important parts regarding syntax. (in fact, formal language is nothing but syntax, no semantics whatsoever, and is also “formalism” in math. In formalism school of math, math is considered just a string of gibberish symbols that does not necessarily need meaning. (it's a symbolic logic system))

In mathematics, computer science, and linguistics, a formal language is a set of strings of symbols that may be constrained by rules that are specific to it.

The alphabet of a formal language is the set of symbols, letters, or tokens from which the strings of the language may be formed; frequently it is required to be finite. The strings formed from this alphabet are called words, and the words that belong to a particular formal language are sometimes called well-formed words or well-formed formulas. A formal language is often defined by means of a formal grammar such as a regular grammar or context-free grammar, also called its formation rule.

The field of formal language theory studies primarily the purely syntactical aspects of such languages—that is, their internal structural patterns. … In computational complexity theory, decision problems are typically defined as formal languages, and complexity classes are defined as the sets of the formal languages that can be parsed by machines with limited computational power. In logic and the foundations of mathematics, formal languages are used to represent the syntax of axiomatic systems, and mathematical formalism is the philosophy that all of mathematics can be reduced to the syntactic manipulation of formal languages in this way.

This philosophy of math formalism, underlies much of my opinion about programing languages.

of existing languages, the ones that is close is Mathematica. (counting only of those that i know to make a judgement (includes: C, Java, Perl, Python, Ruby, JavaScript, Lisp ) ). Lisp, is actually also very close, but unfortunately, the lispers do NOT understand this aspect. The typical elite lispers you see on geek mecca (such as reddit, hackernews), are not much unlike fanatics of other langs. It's not like there's some underlying principle about a lang that made them like it, it's more like they'll defend the lang in all ways, even when the lang violates its own principle. (one such example is lisp's irregularity in its syntax. See: Concepts and Confusions of Prefix, Infix, Postfix and Lisp Notations • Fundamental Problems of Lisp. )

But i think APL, Tcl, are also close.

Haskell and OCaml are interesting cases. Though, i don't really know them to comment, but i kept getting the feeling that they are not. A closely related concept is Denotational semantics, that's more of what Haskell and OCaml are about. But denotational semantics is about semantics, while formal language is about syntax.

btw, for you lispers out there, here's a one-sentence intro on what coding in a term-rewriting system is like. Imagine, when coding lisp, vast majority your function definitions are done with lisp macros (but with more extensive features). That's what coding in Mathematica is like. [see Intro to Wolfram Language Pattern Matching for Lisp Programers]

i don't have experience with other term-rewriting systems other than Mathematica.

i started coding in M since 1992 or so, about every day. For example, these projects are all done in M:

though, there's a issue with Mathematica. When i was at the height of Mathematica programing around 1998, i got a feeling of being tired of it. When majority of your code is pattern matching, You get the feeling of losing fine control of your code logic, and not knowing how your code runs. Every function works by matching a pattern, and that expression again matches another pattern, until no pattern matches and that's the result expression. (technically, you can code in Mathematica and not using any pattern matching, but by the language's nature, it's not practical.)

if you never worked with pattern matching, you can think of it as using regex to transform your expressions as a way to eval/compute results, except that instead of strings, you are transforming the lang's expressions.

For more essays about syntax and languages with perspective of formal systems, see: