5 ms·

I'm always surprised and delighted to see so many "first implementations" of languages in prolog. It was described to me in college as "just a novelty" but in f

I'm always surprised and delighted to see so many "first implementations" of languages in prolog. It was described to me in college as "just a novelty" but in fact it's used extensively in the JVM internals [1] and apparently is the starting-point impl for other languages. But prolog still seems so..awkward. I wonder why langs like Haskell or OCaml aren't more de-facto for these purposes; they seem to have similar expressive power for parser/grammar things and with less inside-out paradigms (imho). [1] https://docs.oracle.com/javase/specs/jvms/se8/jvms8.pdf https://docs.oracle.com/javase/specs/jvms/se8/jvms8.pdf

davydog187 8y ago
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.
- acdha 8y ago
  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) https://en.wikipedia.org/wiki/Oak_(programming_language)
PaulHoule 8y ago
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.
afrisch 8y ago
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.
- pera 8y ago
  Was Elm originally implemented in OCaml? I thought it was Haskell. Another two relatively popular languages implemented in Haskell are Idris and Agda.
  - Shoop 8y ago
    Elm is still implemented in Haskell. Self-hosting isn't a goal.
  - specializeded 8y ago
    They might have meant ReasonML, both it and Elm interop w/ JS https://github.com/facebook/reason https://github.com/facebook/reason
    - afrisch 8y ago
      I could have added reasonml to the list indeed, but reasonml really is (a different syntax for) ocaml.
  - afrisch 8y ago
    Yes sorry, Elm is indeed implemented in Haskell.
- ecnahc515 8y ago
  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.
chrisseaton 8y ago
> 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?
- ryanianian 8y ago
  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).
OskarS 8y ago
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.
- rvense 8y ago
  Do you know of Mercury? It's Prolog with types, basically. https://mercurylang.org/ 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.
richard_shelton 8y ago
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 http://sovietov.com/tmp/warren1980.pdf (this is excellent article, but, sadly, almost unknown one)
- carapace 8y ago
  It has made the front page now https://news.ycombinator.com/item?id=17674859 https://news.ycombinator.com/item?id=17674859
segmondy 8y ago
"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_and_effect/compilation/cg_flatten.pl 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)
- triska 8y ago
  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.
__s 8y ago
Rust's Traits are basically prolog. http://smallcultfollowing.com/babysteps/blog/2017/01/26/lowering-rust-traits-to-logic http://smallcultfollowing.com/babysteps/blog/2017/01/26/lowe...
bjt 8y ago
Haskell is pretty common for this. See purescript, elm, agda, idris. There are more here: https://wiki.haskell.org/Applications_and_libraries/Compilers_and_interpreters https://wiki.haskell.org/Applications_and_libraries/Compiler...

davydog187 8y ago

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.

acdha 8y ago
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) https://en.wikipedia.org/wiki/Oak_(programming_language)

PaulHoule 8y ago

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.

afrisch 8y ago

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.

pera 8y ago
Was Elm originally implemented in OCaml? I thought it was Haskell. Another two relatively popular languages implemented in Haskell are Idris and Agda.
- Shoop 8y ago
  Elm is still implemented in Haskell. Self-hosting isn't a goal.
- specializeded 8y ago
  They might have meant ReasonML, both it and Elm interop w/ JS https://github.com/facebook/reason https://github.com/facebook/reason
  - afrisch 8y ago
    I could have added reasonml to the list indeed, but reasonml really is (a different syntax for) ocaml.
- afrisch 8y ago
  Yes sorry, Elm is indeed implemented in Haskell.
ecnahc515 8y ago
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.

chrisseaton 8y ago

> 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?

ryanianian 8y ago
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).

OskarS 8y ago

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.

rvense 8y ago
Do you know of Mercury? It's Prolog with types, basically. https://mercurylang.org/ 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.

richard_shelton 8y ago

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 http://sovietov.com/tmp/warren1980.pdf (this is excellent article, but, sadly, almost unknown one)

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

segmondy 8y ago

"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_and_effect/compilation/cg_flatten.pl 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)

triska 8y ago
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.

__s 8y ago

Rust's Traits are basically prolog. http://smallcultfollowing.com/babysteps/blog/2017/01/26/lowering-rust-traits-to-logic http://smallcultfollowing.com/babysteps/blog/2017/01/26/lowe...

bjt 8y ago

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