Fun fact: Niko Matsakis is working on a rewrite of Rust's typechecking/trait matching infrastructure in Chalk, which is a derivative of Prolog: https://github.com/rust-lang/chalk
Prolog is surprisingly (or not surprisingly, given the Curry-Howard isomorphism) useful for implementation of programming languages, especially typecheckers.
Story of development of Erlang from 1992.
I don't know why Erlang does not include backtracking. It seems a required part of Prolog. Can anyone explain the advantage?
I read this PDF to see if they answer the question but found no mention of it, as if Prolog doesn't support backtracking at all. Does this make sense to anyone?
Joe Armstrong said the following when he was interviewed by Simon Peyton Jones [1]:
> JA: In the first incarnation of Erlang, it was just... little black boxes were communicating, copying their messages - it's a mailbox model, copying to a mailbox. What we were doing was relational. We had Prolog processes inside the black boxes.
> SPJ: But you saw the light.
> JA: We had to. You are launching a rocket program, because... We wanted from a black box perspective, if you send a certain sequence of messages in, you want the same sequence of messages to come out. You want that to be reproducible and deterministic and Prolog isn't like that. It backtracks, and it has things like that. It just sort of became more natural to make it functional. We never made a decision about having types or not having types. That wasn't an issue. We started with Prolog. Prolog didn't have types, so we got the dynamic type system that Prolog had. The issues we were interested in were limiting errors, propagation of errors, restarting things, restarting bits of the system without taking down all the system, having things which may appear inconsistent while you are upgrading them, continuously evolving systems, not systems you stop and restart.
My take from it is they didn't want backtracking because having backtracking would allow nondeterminism (as in [2]) and they didn't want that.
Because Erlang was not written to be a logic programming language? I may misunderstand your question, but it strikes me as akin to asking why Python doesn't support pointers (since it was initially implemented in C).
What Is it about being a logic programming language that means that backtracking is not a part of it?
I see backtracking as an implementation of search, where Prolog takes expressions and finds bindings for those expressions where the expressions are true. Doesn't Erlang look for solutions to its rules?
I see search as a particular kind of problem that would be defined in a library, not a language. Unless it's a language built specifically to solve constraints (i.e., a logic programming language), which Erlang is not.
Can you point out where within Erlang you feel backtracking should be supported by the core library? It sounds to me like you want the language to be something it fundamentally isn't; i.e., more Prolog-like, and I'm uncertain as to why.
Adding a little support, from Joe Armstrong's thesis (which I've been reading):
"This version of Erlang was embedded in Prolog using Prolog infix operators and did not yet have its own syntax."
"Since Erlang started as an extension to Prolog it seemed reasonable that [...]"
"Erlang now had its own syntax (up to now it could be regarded as a dialect of Prolog) and could be regarded as a language in its own right, rather than as a dialect of Prolog."
Well, yes. 'Originally' being a key word here. It started that way to be something else, and then continued evolving to be something else. Hence my question of what, exactly, the OP wanted backtracking -for-.
Robert Virding (of helped implement Erlang with Joe Armstrong (rip) fame) has developed a logic programming language that runs on the BEAM: https://github.com/rvirding/erlog
I have not tried it yet. I have an idea that I know will work fine on Prolog, but, I want to put it on the web with elixir/phoenix. So I was thinking erlog might be a way to avoid message passing out to a separate prolog process.
Prolog is surprisingly (or not surprisingly, given the Curry-Howard isomorphism) useful for implementation of programming languages, especially typecheckers.