17

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://web.archive.org/web/20100214144956/https://www.csupomona.edu/~jrfisher/www/prolog_tutorial/2_15.html

Alex R
  • 11,364
  • 15
  • 100
  • 180

11 Answers11

12

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.

Daniel C. Sobral
  • 295,120
  • 86
  • 501
  • 681
  • While reading up on some of this stuff, I also found a curious statement (on scala-lang.org I think), that the "for comprehension" is good for solving puzzles -- something Prolog is also good at. I wonder if a "for comprehension" can be used as a (perhaps poor, but demonstrably working) substitute for a logic engine? – Alex R Apr 18 '10 at 21:20
  • Hmm, I can't help but wondering if there is a suitable monad implementing a backtracking search. That would be effectively encoding a (weak) logic engine as monadic operations, and might be the coolest possible abuse of the for-comprehension ever. – Dave Griffith May 30 '12 at 22:12
  • 3
    @DaveGriffith Doesn't sound at all abusive to me. Parser combinators do all of that: for-comprehensions with backtracking. – Daniel C. Sobral May 31 '12 at 03:30
  • 1
    In the functional approach, you can indeed do state space search typically using for comprehensions and streams with recursion. Logic programming handles that on an even higher level of abstraction. – thSoft May 11 '13 at 21:19
6

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.

Tom Schrijvers
  • 61
  • 1
  • 1
5

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

false
  • 10,264
  • 13
  • 101
  • 209
5

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.

Ross Judson
  • 1,132
  • 5
  • 11
  • This looks very promising, but all those parenthesis get in the way! :-) – Alex R May 20 '10 at 03:01
  • Thanks for the reference. This logic programming DSL has been ported to so many languages including those based on JVM. – m33lky Aug 22 '16 at 15:53
5

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.

fedesilva
  • 1,532
  • 13
  • 12
4

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)

3

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

3

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.

thSoft
  • 21,755
  • 5
  • 88
  • 103
1

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

Don Stewart
  • 137,316
  • 36
  • 365
  • 468
1

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.

pschaus
  • 11
  • 1
0

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.

Dmitry Ponyatov
  • 348
  • 1
  • 11