Re: Is Prolog a good language for generating semi-random, constrained solutions?

On 25/03/2014, at 15:43, Alan Baljeu <[email protected]> wrote:

>> We only have a brought id of your latest ninja code :-) I think that
> 
>> Prolog adds two things to tackle the case where naive generate-and-test
>> proves to be too slow: constraints and easy integration of DSLs.
>> Constraints provide a neat way to merge testing inside the generator,
>> such that it is executed as early as possible. In a sense, I guess we
>> can see that as a form of `aspect programming'. Instead of
>> 
>>    generate, test
>> 
>> you  get
>> 
>>    set_constraints, generate, test
>> 
>> where test can also become empty. In addition constraints allow to
>> reason about the domains of variables and avoid brute force generate and
>> test. DSLs allow you to express your problem natively and generate the
>> dirty stuff in the generate routine automatically, or do simple things
>> such as goal reordering to reduce backtracking.
> 
> 
> 
> I completely endorse this approach.
> 
>>  Cheers --- Jan
> 
>> P.s.    When I was in Vienna, Markus and I chatted briefly about the
>>    idea to have a Prolog thread `fork', i.e., a call that creates
>>    a new thread as a copy of the running one.  This would require
>>    some restrictions, i.e., we cannot fork if Prolog is called
>>    from C in an arbitrary way.  Is that worth investigating at
>>    some point?
> 
> Can you have it sync-up?  It shouldn't matter to C if Prolog forks off a thread and then closes it before returning to caller.
> Or, you could return to caller but only the first thread ; all others terminate.  I think this construct is useful:
> 
> first_to_complete(List of Callables) is semidet.

That's is called "competitive or-parallelism" in Logtalk. It's supported when using SWI-Prolog, XSB, or YAP as the back-end compilers. I think Jan did already did something similar in one of the SWI-Prolog libraries. The idea of competitive or-parallelism is a powerful one, specially when combined with other search, constraints, and forms of parallelism. Follows a reference to a paper (with examples) about competitive or-parallelism in Logtalk:

@inproceedings{pmoura09a,
	author = {Paulo Moura and Ricardo Rocha and Sara C. Madeira},
	title = "{High Level Thread-Based Competitive Or-Parallelism in Logtalk}",
	booktitle = {Proceedings of the Eleventh International Symposium on Practical Aspects of Declarative Languages},
	editor = "Andy Gill and Terrance Swift",
	series = "Lecture Notes in Computer Science",
	volume = "5418",
	month = jan,
	year = {2009},
	pages = {107--121},
	publisher = "Springer-Verlag",
	address = "Berlin Heidelberg"
}

Cheers,

Paulo

-----------------------------------------------------------------
Paulo Moura
Logtalk developer

Email: <mailto:[email protected]>
Web:   <http://logtalk.org/>
-----------------------------------------------------------------