# Pattern matching, which language first had it

Which programming language was the first to use pattern match? The oldest ones I know are:

• Prolog 1972

• ML 1973

Are there languages older that have pattern matching?

Edit:

By pattern matching I mean you can use patterns to control the flow of exection, like in Haskell for example:

``````factorial 0 = 1

factorial n = n *factorial  (n-1)
``````

Here we match with 0 if we call (factorial 0). And we match n if we call (factorial 1). You can use _ if you want to match with anything and you have list matching too with (head:tail) .

You can use this to replace all if else and switch statments and it can do more.

• Can you narrow down what you mean by pattern matching? Do you mean reg-ex style? or something more sophisticated. Does the matcher have to be an intrinsic part of the language or just easy to implement in it? Taking a fairly broad definition of the answer, I would think that Lisp came first, at a guess. Aug 29, 2017 at 9:36
• @JeremP yes, your right I mean like in Haskell pattern matching ... I've added more discrption to the post. Aug 29, 2017 at 10:36
• Are you confusing recursion with pattern matching? Your example shows recursion.... Sep 1, 2017 at 8:13
• @BrianTompsett-汤莱恩 stackoverflow.com/questions/11015684/… Sep 16, 2017 at 18:34

Refal (conceived 1966, implemented 1968) is a language built upon the idea of structured pattern-matching.

A function definition is a sequence of constructs "pattern = replacement", operating on the function argument that consists of a sequence of terms.

Each term is either a symbol (a character or a meta-symbol like a number of a function ID), or a parenthesized sequence of terms.

A pattern is a similarly-structured sequence with free variables that can match individual symbols, terms or "expressions" (sequences of terms), as well as literal symbols.

A replacement is a sequence of terms with potential function call terms that use magic parentheses and the sequence in parentheses starts from a function ID.

The examples on the Wiki page, like

`````` Fact { 0 = 1;
s.N = <* s.N <Fact <- s.N 1>>>; }
``````

don't do the language justice; the main feature of the language is the ability to pattern-match structured data.

The language had a counter-culture popularity in the programming circles in the USSR after the author had to emigrate to the U.S. in 1977, and was taught by the author, Valentin Turchin, in the City College of New York until his death in 2010. Now, unfortunately, the reference links on the Refal wiki page are also dead.

Searching for "refal" on Github returned 1599 matches, though.

Probably the first language to use string patterns was COMIT in 1957. This was the predecessor to SNOBOL in 1962 from which it is considered most string processing language features claim their origin.

• SNOBOL was my first thought on this (I wasn't aware of COMIT), but then string pattern matching is somewhat different in scope to the structured pattern matching used by Prolog & ML family languages, so I'm not convinced they should really be considered the same thing. Aug 29, 2017 at 10:17

A form of structural pattern matching is presented in a 1963 paper METEOR: A LISP Interpreter for String Transformations by Danied Bobrow.

(Don't be fooled by the term "string").