Can you do Logic Programming in Scala?

Question

I read somewhere that Pattern Matching like that supported by the match/case feature in Scala was actually borrowed from Logic languages like Prolog.

Can you use Scala to elegantly solve problems like the Connected Graph problem? e.g. https://www.csupomona.edu/~jrfisher/www/prolog_tutorial/2_15.html

Answer 1

No, you can't do it, unless you actually create a logic engine, which kind of defeats the whole purpose.

Furthermore, pattern matching itself is wholly unsuited for this, for many reasons. Consider, for instance, the basic query itself: path(1, 5, P). In Scala's pattern matching, 1, 5 and P are outputs. You can't provide an input that could be used to produce the output.

With Prolog, this is like, assuming that 1 and 5 are fixed, what possible values could P take on? That's just now how pattern matching works.

Edit: With Scala 2.10, pattern matching is now compiled to an intermediate operation like for-comprehensions are, and then the default translation is further optimized. However, it is possible to define your own class to handle pattern matching, and I have seen it used to implement prolog login -- though I can't find the link, sorry.

Answer 2

See http://kanren.sourceforge.net/ for details on how functional and logic programming aren't really all that far apart. Stream structures are the key to understanding how the two paradigms can come together. By "lifting" standard functions into a stream/logic format, they can exhibit problem solving behavior that looks a lot like Prolog.

You should also look at parser combinators. With the right combinators in place, efficient Prolog-like solving capabilities are possible.

Answer 3

Haskell and Functional Programming Languages have been the direct source of inspiration for Scala. One of the applications inherited from those languages is the development of Domain Specific Languages (DSLs). There are quite a few DSLs for Logic Programming (Prolog) in Haskell. It should be quite possible to port such a DSL library to Scala, if that has not happened yet.

Answer 4

I know I am late but searching re: kanren I found this [dead link] There is also this: http://code.google.com/p/scalalogic/

I am just researching the topic and only have a very dim understanding of it but the links may be of some interest anyway.

Answer 5

Styla is a fairly complete Prolog interpreter written in Scala, derived from Kernel Prolog (see Fluents: A Refactoring of Prolog for Uniform Reflection and Interoperation with External Objects in CL'2000).

The genuinely open sourced (Apache license) code is hosted at:

http://code.google.com/p/styla/

and it is designed with simplicity and extensibility in mind - hoping it would be useful to people experimenting with new Prolog extensions or alternative logic programming languages.

Styla uses a few Scala goodies not available in Java:

• higher order functions, maps, folds, case classes etc.
• combinator parsers - "poor man's DCGs"
• Scala's elegant implicit conversions between lists, arrays, sequences etc.
• Scala's arbitrary length integers and decimals (with a natural syntax, in contrast to Java)
• Scala's """...""" strings - for regexps and to embed Prolog code directly in Scala classes
• a few IO abstractions available in Scala that view things like file operations as iterators - a natural match for the original Fluents of the Java-based Kernel Prolog from which Styla was derived

(Text taken from: http://groups.google.com/group/comp.lang.prolog/browse_thread/thread/4cd835d2c82fce02/505688d4b0be5528)

Answer 6

Scala is not a logic programming language, but you can indeed define DSLs for logic programming in Scala. Note that Scala borrows a lot of concepts from functional programming - it can and should be used in a functional style. Functional and logic programming are both declarative, but differ significantly. You can read more here.

Answer 7

The traditional answer to your question would outline that logic variables cannot be directly modeled in a language that assumes everything to be a value.

There is, however, a relatively new approach to map logic variables to functional constructs. In the concrete case the close-to-Prolog logic language Curry curry is translated to Haskell. What is very unusual in this approach is that logic variables are modeled with lazyness. For more, see KiCS2: A new compiler from Curry to Haskell. Maybe lazy val could be used to this end.

Answer 8

Just found a nice implementation of Prolog in Scala. Unfortunately I didn't have time to try it, so my impression is only based on looking at the source code that can be found here:

https://github.com/sonoisa/Prolog-in-Scala/blob/master/PrologInScalaSample.scala

The above points to a couple of test programs. The Prolog interpreter is written in Scala in such a way that Prolog clauses can be embedded as Scala objects written in Scala. I don't fully understand the magic behind it, here is a sample how the tak function is written:

tak('X, 'Y, 'Z, 'A) :- (
 'X =< 'Y, CUT, 'Z === 'A)
tak('X, 'Y, 'Z, 'A) :- (
 'X1 is 'X - 1,
 'Y1 is 'Y - 1,
 'Z1 is 'Z - 1,
 tak('X1, 'Y, 'Z, 'A1),
 tak('Y1, 'Z, 'X, 'A2),
 tak('Z1, 'X, 'Y, 'A3),
 tak('A1, 'A2, 'A3, 'A)
)

I guess it is doing backtracking via continuations and has its own implementation of a variable environment and unification.

If you look at the code, for example of unifyTerm, you will see that it makes heavily use of pattern matching, which puts Scala into a special position for implementing logic engines.

Best Regards

Answer 9

Pattern matching as such isn't directly useful for logic programming, as it doesn't unify variables.

Answer 10

You can also have a look at scampi (a constraint programming solver in Scala): https://bitbucket.org/pschaus/scampi/wiki/Home Jacop CP Solver also has a scala API.

Answer 11

I found this http://yieldprolog.sourceforge.net/ as a source for Prolog-like system implementation methods, not undocumented source code or cryptic libraries.

But I'm interested in Scala only a few days ago, so asked the same question on users.scala: https://users.scala-lang.org/t/yield-prolog-unification-and-coroutines-in-scala/4433

The thing should be available in language to implement unifying backtracking is generator functions which can return and retain computation in mid of function execution. The same effect can be may be achieved by using coroutines or green threads, which produce partial solutions in backtrack chaining.