"seem so..awkward"? Sure because you don't understand prolog. it's very easy to implement languages.

Look how simple I can compile down to asm code in 35 lines of pure prolog code.

https://github.com/segmond/PrologThingz/blob/master/clause_a...

  /*
  	c := 1;
  	r := 1;
  	while c < n do
  	     (c := c + 1;
  	      r := r * c)
  */
  program(1, (
      assign(c,1);
      assign(r,1);
         while((c < n),
  	  (assign(c, c+1);
             assign(r, r*c))))).

  ?- compile(1).
    movc(1,r(1))
    stm(r(1),c)
    movc(1,r(1))
    stm(r(1),r)
  label(_G3638)
    movm(c,r(1))
    movm(n,r(2))
    cmp(1,2)
    bge(1)
    movm(c,r(1))
    movc(1,r(2))
    add(r(2),r(1))
    stm(r(1),c)
    movm(r,r(1))
    movm(c,r(2))
    mul(r(2),r(1))
    stm(r(1),r)
    br(_G3638)
  label(1)

This is great, thank you for sharing this!

Your Prolog compiler is also notable because it can be easily made so general that it not only compiles, but even generates programs.

For example, if I use pattern matching to generalize the first two clauses via:

    cg(i(I), R, [movc(I, r(R))|Z]-Z).
    cg(a(A), R, [movm(a(A), r(R))|Z]-Z).

then we can already use the same code to generate programs and compiled instructions:

    ?- cg(Prog, N, Asm-[]).
    Prog = i(_5354),
    Asm = [movc(_5354, r(N))] ;
    Prog = a(_5354),
    Asm = [movm(a(_5354), r(N))] .

The other clauses can be also generalized, using integer constraints to make them usable in all directions.

For example, if we write:

    cg(X+Y, R, C0-C2):-
            cg(X, R, C0-C1),
            R1 #= R + 1,
            cg(Y, R1, C1-[add(r(R1),r(R))|C2]).

then we can compile an addition whose operands are not even yet fully known:

    ?- cg(i(X)+i(Y), N, Asm-[]).
    Asm = [movc(X, r(N)), movc(Y, r(_8850)), add(r(_8850), r(N))],
    N+1#=_8850.

Still, we can inspect the general pattern that is generated as a result of the compilation, and therefore write for example test cases that subsume many possible concrete cases!

On a general note, one reason why Prolog is so popular for writing compilers is that the language has a built-in mechanism for writing parsers, and in fact describing all kinds of sequences (for example, of tokens, of instructions etc.) in a very convenient way.

For example, the above three clauses can be written equivalently as a so-called definite clause grammar (DCG):

    cg(i(I), R) --> [movc(I, r(R))].
    cg(a(A), R) --> [movm(a(A), r(R))].
    cg(X+Y, R)  -->
            { R1 #= R + 1 },
            cg(X, R),
            cg(Y, R1),
            [add(r(R1),r(R))].

This makes it very easy to see the key aspects of the code. At the same time, the description is so general that it can be used in all directions, to generate, parse and test instructions.

Sample query:

    ?- phrase(cg(i(X)+i(Y), N), Ls).
    Ls = [movc(X, r(N)), movc(Y, r(_2288)), add(r(_2288), r(N))],
    N+1#=_2288.

How about Forth/Factor vs Prolog to implementing languages?

https://en.wikipedia.org/wiki/Forth_(programming_language) https://factorcode.org/

http://www.bradrodriguez.com/papers/bnfparse.htm http://www.forth.org/literature/bnfparse.html :-)

The "inside out" paradigm of Prolog is what it is good for. Try to write complex procedural programs and you will be driven to insanity by the cuts, using logical failure to express procedural success, etc.

The original sin of conventional programming languages is that we write a sequence of operations that happen one after another in time. Thus we find concurrency, dealing with asynchronous events, and reacting effectively to the environment difficult.

Prolog makes writing simple parsers simple. Certain kinds of search problems are easy to solve, and some kinds of operations (say involving transitive closure) can be defined in two or three lines of Prolog that hopefully you could implement in 50 lines in a more normal language after looking at an algorithms book.

There has been a huge amount of research and commercial implementation of things that are like Prolog but different, for instance having built-in satisfaction solving, combinatorical optimization, etc. Prolog is backwards-chaining (finds rules to justify a conclusion) but other engines are forward chaining like Drools, the Jena Rules Engine, IBM iLog.

I would love to see this approach get more popular.

Thanks for the link!

There is a good reason for using Prolog-like language in a compiler-related project. Prolog was used for rapid prototyping of compilers since the end of 70s and it's still ahead of the time. And if you take a look at a code from old Warren article [1], for example, you'll see that even today almost nobody uses so high-level description of a compiler. The main power of Prolog is not in parsing. Prolog is unbeatable in a program analysis and transformations. See Datalog (you may find it even in a Dragon book nowadays!), see Stratego/XT, they all inspired by good old Prolog.

By the way, Prolog is also good in describing formal semantics of PLs. Good PL reference or a standard should include clean formal notation for semanics of the language, not some bureaucratic English text... Because it's already 2018, we need it for compiler developers and for deeper understanding of a language.

[1] http://sovietov.com/tmp/warren1980.pdf (this is excellent article, but, sadly, almost unknown one)

It has made the front page now https://news.ycombinator.com/item?id=17674859

> in fact it's used extensively in the JVM internals

I've not seen Prolog used in the JVM internals myself - it's just being used in this document as an inference notation to explain things as far as I know. Unless you know specifically where it's used, which would be interesting?

That's a good point - the doc uses it for notational clarity but it's not clear if it's actually used in the implementation(s).

Well, OCaml is indeed rather popular for implementing compilers for new languages (sometimes later bootstrapped), including ones which became rather popular. I can think of F#, Rust, Elm, Haxe, FlowType for instance.

Was Elm originally implemented in OCaml? I thought it was Haskell.

Another two relatively popular languages implemented in Haskell are Idris and Agda.

They might have meant ReasonML, both it and Elm interop w/ JS

https://github.com/facebook/reason

I could have added reasonml to the list indeed, but reasonml really is (a different syntax for) ocaml.

Elm is still implemented in Haskell. Self-hosting isn't a goal.

Yes sorry, Elm is indeed implemented in Haskell.

There's also a project for implementing a prolog like interpreter for doing type checking and other logic for Rust, I think it works on the MIR level, but could be wrong on that.

Having some experience with both languages (though not professionally), I personally much prefer Prolog to Haskell. There's an initial hurdle with Prolog because it uses such an unfamiliar paradigm, but once you get good with it, programming in Prolog is pure pleasure for me.

I like Haskell just fine, it's an excellent language, but my heart belongs to Prolog.

Do you know of Mercury? It's Prolog with types, basically.

https://mercurylang.org/

The language is fantastic, but I think it's fair to say that the implementation and ecosystem leave some things to be desired.

Rust's Traits are basically prolog. http://smallcultfollowing.com/babysteps/blog/2017/01/26/lowe...

Probably because they predate haskell. In the case of Java, thats not true, but Haskell would have only been 5 years old at the time, and was largely academic.

Not even 5 years old — Java started development in 1991 as Oak so it would have been really early:

https://en.wikipedia.org/wiki/Oak_(programming_language)

Haskell is pretty common for this. See purescript, elm, agda, idris. There are more here: https://wiki.haskell.org/Applications_and_libraries/Compiler...