4 ms·

> I think that depends on what you meany by "pattern matching" Oh, yes, that's true. "Pattern matching" as that what normally is used in "functional programm

• YeGoblynQueenne 2y ago
  Thanks, I don't really know much about Functional Programming. My expertise is in logic programming which btw is a different paradigm. I've heard it said that they're similar and it seems to me the reason was the support for pattern matching in functional languages. I agree that what "pattern matching" means depends on a programmer's background. It's interesting that the wikipedia article that you link to does not mention "unification" at all and only has one reference in Prolog as one of a group of example languages with a "pattern matching construct"; which is not how I would describe the use of the unification algorithm in Prolog. To be honest, I am not sure what is meant by "pattern matching". It seems to be a loosely defined term, like "Finite State Machine" (as opposed to "Finite State Automaton"). I expect that the book you linked to has a more formal treating, perhaps, but from what I can tell from a quick look the "pattern matching" here is based on types. In Prolog, unification is used to bind values to logic variables, which do not have types. So a variable, X, in Prolog can unify, i.e. "match with" absolutely anything. A "pattern" then can be formed by constructing terms (the only data structure in Prolog) with "holes" like p(X, a, b, Y,[1,2,3|Tail], f(Z)) etc. where capital letters are variables. One use of this ability is to manipulate singly-linked lists to insert in or remove elements from their tail, where normally only the head of such a list can be accessed directly. What I mean is that in Prolog a list is denoted by the special syntax [H|T] where H is the head of a list (and can be any term, including another list) and T is the tail of the list, another list. Normally one appends to a list in Prolog using the append/3 predicate: append([], L, L). append([H|T], L, [H|R]) :- append(T, L, R). This works on ordinary lists, but it is also possible to define a "difference list" as a term, e.g. like: [a,b,c,d|T]-T Where T is a variable bound to the end of the tail of the list. Two difference lists like that one can be appended with the following predicate: append_dl(Xs-Ys, Ys-Zs, Xs-Zs). For example: ?- Xs = [a,b,c,d|T1]-T1, Ys = [e,f,g,h|T2]-T2, append_dl(Xs,Ys,Zs). Xs = [a,b,c,d,e,f,g,h|T2]-[e,f,g,h|T2], T1 = [e,f,g,h|T2], Ys = [e,f,g,h|T2]-T2, Zs = [a,b,c,d,e,f,g,h|T2]-T2. The result of appending is in Zs, but you can see the result of the intermediary unification steps in the other variables echoed in the Prolog REPL (the "listener"). Of course, because this is Prolog you can also use the same predicate to split a list: ?- Xs = [a,b,c,d|T1]-T1, Zs = [a,b,c,d,e,f,g,h|T2]-T2, append_dl(Xs,Ys,Zs). Xs = [a,b,c,d,e,f,g,h|T2]-[e,f,g,h|T2], T1 = [e,f,g,h|T2], Zs = [a,b,c,d,e,f,g,h|T2]-T2, Ys = [e,f,g,h|T2]-T2. Where Ys is what remains if we split Xs from Zs. Appending or splitting lists like this is preferred to append/3 because it appends the two lists in a single operation so it can be used to economically put a list together in a loop. The same technique is used with Prolog's Definite Clause Grammars where the "difference" in a difference list is the start and end of a string accepted by a grammar, acting as a parser. https://en.wikipedia.org/wiki/Definite_clause_grammar https://en.wikipedia.org/wiki/Definite_clause_grammar Sterling and Shapiro's "The Craft of Prolog" has a nice chapter on "Incomplete Data Structures" using difference lists and patterns with "holes" but I don't think there's a free version online, unfortunately.
  • ReleaseCandidat 2y ago
    > To be honest, I am not sure what is meant by "pattern matching". I'd say that "pattern matching" is unification, where there are no free variables on the right side and the left side is the "pattern" to match. As Prolog code, something like ?- [X|Xs] = [a, b, c] where X = a and Xs = [b, c] would be "pattern matching" the head and the tail of the list [a, b, c], but ?- [X|[b, c]] = [a|Xs] where X = a and Xs = [b, c] would be "real" unification, if [X|[b, c]] would be valid syntax. Oh, and both unification for type checking (inference) and pattern matching are compile time actions (or done before evaluating the generated functions). A (simple) pattern match like match list with | head :: tail -> do_something(head, tail) | [] -> do_something_else() is "compiled" to something like if list != [] then do_something(head(list), tail(list)) else do_something_else()
    • YeGoblynQueenne 2y ago
      That sounds right. I guess then "pattern matching" as in Elixir et al. is really just one-sided unification. Which makes me wonder- why don't those languages go all the way? At a guess, that's something to do with the difficulty to implement unification efficiently. The first description of Unification, by J. Alan Robinson (who first described Resolution) had exponential time complexity and it took a while to find efficient unification algorithms. Perhaps the designers of functional languages simply don't need the hassle and can make do with something more efficient, less complete. That would make good, practical sense in languages that do not use Resolution as an interpreter- it's Resolution that absolutely needs unification (there's ground Resolution, without the need for unification, but it's restricted to propositional terms without first-order variables).
      • rdtsc 2y ago
        Pattern matching as is in Erlang, or how it is in most modern languages, was not there at some point and was considered novel and exotic. Now most everyone can do [X, Y | _] = [1, [2], 3, 4] and it's not a seen as something advanced. I am not sure if it was ever called "unification" in Erlang, it was always called "pattern matching". But the equal sign did retain its name as the "match" operator: https://www.erlang.org/doc/system/expressions.html#the-match-operator-and-the-compound-pattern-operator https://www.erlang.org/doc/system/expressions.html#the-match.... And that is a legacy of Prolog. I never read X=1 as "make X equal to 1", in my head I always read it as "match X to 1". At some point, I also wondered: why didn't they go all the way and just bring in Prolog's full unification. They obviously liked Prolog; Erlang was developed in Prolog initially, even. Well, it turns out with unification we'd have to carry the match "hole" around until we might a match. But Erlang has lightweight processes with isolated heaps which communicate via messages, so now we'd need to pass these "holes" around from process to process until say one of the processes somewhere manages to unify the value, and then have it propagate across the system to original query. That breaks isolation. So you see how the two neat features came into a conflict and they picked one over the other, and rightly so it seems.