search

triska / simsttab

Simple timetabling engine for schools
https://www.metalevel.at/simsttab/
23 stars 12 forks source link

The code fails to run due to the discontiguous predicate definition lines #3

Open gabouelseoud opened 3 years ago

gabouelseoud commented 3 years ago

I describe the problem in this thread and the colleague who replied also failed to get the expected output. https://github.com/mthom/scryer-prolog/issues/1014#issue-960083343 I hope you can help us

flexoron commented 3 years ago

At the home-page there are 3 examples where you can try and go: https://www.metalevel.at/prolog/timetabling/

(Cut/Paste) Example 1 and 2 do work(but no timetable.txt has been written)

$ ../scryer-prolog/target/release/scryer-prolog simsttab.pl example1.pl OK! $ ../scryer-prolog/target/release/scryer-prolog simsttab.pl example2.pl OK!

Example 3 failed: $ ../scryer-prolog/target/release/scryer-prolog simsttab.pl example3.pl ?- requirements_variables(Rs, Vs),labeling([ff], Vs),print_classes(Rs). false. ?-

gabouelseoud commented 3 years ago

@flexoron Thank you very much. Until triska replies, you provided me with a very good starting point. I'll try to better understand the code to find out what the problem is. I really appreciate your precious support.

triska commented 3 years ago

I can reproduce this! There is definitely a mistake somewhere, the only question is where exactly!

Let's break it down. First, we see that the first goal by itself already fails:

?- requirements_variables(Rs, Vs).
false.

So, adding more goals (i.e., constraints), will fail "all the more".

One thing I noticed is that we "generalize away" the last goal in requirements_variables/2, then it succeeds. To generalize away a goal, we use *`()/1** fromlibrary(debug). This is similar to "commenting out" a goal, with the advantage that it also works for the *last* goal in a clause, which is followed by .. So, if we change the definition ofrequirements_variables/2` to:

requirements_variables(Rs, Vars) :-
        requirements(Rs),
        pairs_slots(Rs, Vars),
        slots_per_week(SPW),
        Max #= SPW - 1,
        Vars ins 0..Max,
        maplist(constrain_subject, Rs),
        classes(Classes),
        teachers(Teachers),
        rooms(Rooms),
        maplist(constrain_teacher(Rs), Teachers),
        maplist(constrain_class(Rs), Classes),
        * maplist(constrain_room(Rs), Rooms).

then it succeeds.

This all worked as expected in earlier versions of Scryer Prolog. Are you interested in trying git bisect on the Scryer repository to pinpoint the commit that caused this problem? Please try it with a version of Scryer Prolog from March 2020, since the latest commit to simsttab.pl is from that time and I am certain it worked back then. For instance, you could start at 54dce9b60eff2b2c2f940554f4f9952986e6f8c6 and then bisect your way to more recent versions!

flexoron commented 3 years ago

git bisect drives compiling into crates hell

For example: Compiling lexical-core-0.4.6 error[E0308]: mismatched types lexical-core-0.4.6/src/atof/algorithm/bigcomp.rs:243:55 let nlz = den.leading_zeros().wrapping_sub(wlz) & (u32::BITS - 1); -> expected usize, found u32

After fixing those and other errors in bigcomp.rs, bigint.rs and math.rs Next error:

Compiling markup5ever v0.8.1 error[E0603]: module export is private markup5ever-0.8.1/build.rs:92:14

[derive(Deserialize, Debug)] --> private module error (due to serde-1.0.127)

Cargo.toml dependency entry fixes this : serde = "1.0.123"

Finally it compiles but now I get this syntax error message, too $ ../scryer-prolog/target/release/scryer-prolog simsttab.pl reqs.pl caught: error(syntax_error(inconsistent_entry),use_module/1)

hmm...I'm not an rust expert but it looks like you need the rust environment of March 2020 as well when you reset to 54dce9b60eff2b2c2f940554f4f9952986e6f8c6

triska commented 3 years ago

Thank you a lot for looking into this!

At some point, Scryer did not yet support the discontiguous directive, this is a rather recent feature!

To prevent this syntax error, you can comment out the discontiguous directives in simsttab.pl, and then you must also ensure that all clauses in reqs.pl are actually contiguous. You can do this in Emacs by marking the hole buffer (C-x h) and then sorting all facts alphabetically with M-x sort-lines RET.

gabouelseoud commented 3 years ago

My point of view is that it is better to update simsttab to work correctly with the latest scryer version. You are quite a respected expert @triska. I think you can do it and this will assure us all to be able to make use of it, especially those who intend to use it as a block within a large code.

On Wed, 4 Aug 2021 at 23:56, Markus Triska @.***> wrote:

Thank you a lot for looking into this!

At some point, Scryer did not yet support the discontiguous directive, this is a rather recent feature!

To prevent this syntax error, you can comment out the discontiguous directives in simsttab.pl, and then you must also ensure that all clauses in reqs.pl are actually contiguous. You can do this in Emacs by marking the hole buffer (C-x h) and then sorting all facts alphabetically with M-x sort-lines RET.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/triska/simsttab/issues/3#issuecomment-893001137, or unsubscribe https://github.com/notifications/unsubscribe-auth/AIUQ7APVHN4NBBJROA3DUQTT3GZQDANCNFSM5BQXTGTQ . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&utm_campaign=notification-email .

-- =============================================== بسم الله الرحمن الرحيم الحمد لله رب العالمين و صلاة و سلاما على الحبيب محمد رسول الله و اﻷنبياء أجمعين May Allah's Peace and Prayers be upon prophet Mohammad and his fellow prophets, Amen. ================================================= اللهم ارحم والدي الحبيب و اجعله من الذين هم أحياء عند ربهم يرزقون..و بارك لي في والدتي و لا تحرمني منها أبدا https://www.facebook.com/abouelseoud.saleh https://www.facebook.com/abouelseoud.saleh ============================================== Gehan Abouelseoud Saleh Phd in Electrical Engineering Faculty of Engineering Alexandria University, Egypt =============================================================

May we all be a message of mercy and love from Allah to all His creatures.

إنه من أكثر الأمور إيلاما في هذه الدنيا ألا نجد ممن نحبهم من استشعار آلامنا و مشاركتنا همومنا ما نرجو و الأشد من ذلك ألما أن نجد أننا مثلهم

flexoron commented 3 years ago

this works, too: reqs.pl %room_alloc(r1, '1a', sjk, 0). %room_alloc(r1, '1a', sjk, 1). room_alloc(r1, '4c', mat, 0). room_alloc(r1, '4d', mat, 0).

the issue is with: room_alloc(r1, '1a', sjk, 0). room_alloc(r1, '1a', sjk, 1).

flexoron commented 3 years ago

this works, too: reqs.pl room_alloc(r1, '2a', sjk, 0). room_alloc(r1, '2a', sjk, 1). room_alloc(r1, '4c', mat, 0). room_alloc(r1, '4a', mat, 0).

the system does not like (to be:-) '1a'

gabouelseoud commented 3 years ago

The way I see it now, we are looking for a bug in the new scryer-prolog release. This is why I believe so: We have examples in the form of a set of constraints. older version of scryer-prolog successfully found variable values capable of satisfying all constraints. So it is a fact that solutions to these problems exist. However, the new scryer version fails to find these solutions. I believe that the kind of tests made by @flexoron can help some one who understands first order logic to find what constraints the new prolog fails to satisfy and guess the bug based on that. But for myself, I am new to logic. I hope @triska can help us guess what the bug is, so that it can be corrected.

On Thu, 5 Aug 2021 at 01:08, flexoron @.***> wrote:

this works, too: reqs.pl room_alloc(r1, '2a', sjk, 0). room_alloc(r1, '2a', sjk, 1). room_alloc(r1, '4c', mat, 0). room_alloc(r1, '4a', mat, 0).

the system does not like (to be:-) '1a'

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/triska/simsttab/issues/3#issuecomment-893032351, or unsubscribe https://github.com/notifications/unsubscribe-auth/AIUQ7AK5RSSFXLQPCGZZUWTT3HB7TANCNFSM5BQXTGTQ . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&utm_campaign=notification-email .

-- =============================================== بسم الله الرحمن الرحيم الحمد لله رب العالمين و صلاة و سلاما على الحبيب محمد رسول الله و اﻷنبياء أجمعين May Allah's Peace and Prayers be upon prophet Mohammad and his fellow prophets, Amen. ================================================= اللهم ارحم والدي الحبيب و اجعله من الذين هم أحياء عند ربهم يرزقون..و بارك لي في والدتي و لا تحرمني منها أبدا https://www.facebook.com/abouelseoud.saleh https://www.facebook.com/abouelseoud.saleh ============================================== Gehan Abouelseoud Saleh Phd in Electrical Engineering Faculty of Engineering Alexandria University, Egypt =============================================================

May we all be a message of mercy and love from Allah to all His creatures.

إنه من أكثر الأمور إيلاما في هذه الدنيا ألا نجد ممن نحبهم من استشعار آلامنا و مشاركتنا همومنا ما نرجو و الأشد من ذلك ألما أن نجد أننا مثلهم

gabouelseoud commented 3 years ago

I just tried modifying the reqs file as triska described, so that lines referring to the same predicate are together and I commented out the discontinguous (files are attached) and I run using an older version of scryer that I installed using the command: cargo install scryer-prolog (instead of cargo run --release). It now works. However, I am worried about not understanding why the new version fails. There is a bug in the new engine that makes it fail to find a solution where it exists, and unless we know what it is, we may be getting wrong results. (I changed from .pl to .txt to be able to attach the files here for you to review them) simsttab_old.txt reqs_new.txt

flexoron commented 3 years ago

@triska: sorting is not an option because when sorted both scryer versions do the job. I wonder how Example3 (https://www.metalevel.at/prolog/timetabling) works(it is not sorted)?

gabouelseoud commented 3 years ago

example 3 doesnot work with the new version and old version both. Sorting works for me only with the old version after commenting out discontinguous lines as in attached files in my previous message, NO, sorting doesn't work with the newer version, I get: Segmentation fault (core dumped) and before that huge memory consumption that ends in fault. (I am assuming you mean by sorting the modification I did for the reqs.pl file in my version reqs_new.pl in my previous message)

flexoron commented 3 years ago

example3.pl is cut/paste from www.metalevel.at/prolog/timetabling

Well, here it works if sorted with this command.

$ sort example3.pl > example3-sorted.pl

$ # discontinguous disabled $ ../scryer-prolog-old/target/release/scryer-prolog simsttab-old.pl example3-sorted.pl

$ # discontinguous enabled $ ../scryer-prolog-new/target/release/scryer-prolog simsttab-new.pl example3-sorted.pl

gabouelseoud commented 3 years ago

@flexoron No, I tried your version example3-sorted.pl and got exactly my same earlier results: old version works smoothly new version of scryer consumes a lot of memory and ends in segmentation fault. It appears that the newer version seeks a more (un-necessarily) memory-consuming route to solution. May be your computer has better memory resources than mine ;that's why you don't get segmentation fault. But at any event, this seems to be a bug since the old scryer finds the solution quite smoothly. I have 4 G ram

flexoron commented 3 years ago

yes, the new release version(without debug info) consumes twice as much memory. old version: 1.5G new version: 3.0G

flexoron commented 3 years ago

segfault: this is a scryer issue. Rust is designed to avoid segmentation faults because segmentation faults are programmer's fault(usually). Maybe triska gives a hint how to tell scryer's rust programmers about the issue. Maybe it is known already. Maybe it is caused intentionally.

triska commented 3 years ago

Yes, please report a segmentation fault in the Scryer Prolog repository, with a clear test case that exhibits the problem. No matter what else happens, Scryer definitely should not crash, so a crash is certainly a mistake in the implementation. If memory runs out, the system should throw an exception (resource_error) instead of crashing.

In addition, if everything works as expected if the facts are sorted, but then no longer works if the facts are in a different order, then this may be a mistake in the way the discontiguous directive is implemented. If we can construct a test case that exhibits this issue, we can likewise report it in the Scryer repository, in its own dedicated issue.

gabouelseoud commented 3 years ago

@triska: I reported the problem https://github.com/mthom/scryer-prolog/issues/1015

On Thu, 5 Aug 2021 at 19:56, Markus Triska @.***> wrote:

Yes, please report a segmentation fault in the Scryer Prolog repository, with a clear test case that exhibits the problem. No matter what else happens, Scryer definitely should not crash, so a crash is certainly a mistake in the implementation. If memory runs out, the system should throw an exception (resource_error) instead of crashing.

In addition, if everything works as expected if the facts are sorted, but then no longer works if the facts are in a different order, then this may be a mistake in the way the discontiguous directive is implemented. If we can construct a test case that exhibits this issue, we can likewise report it in the Scryer repository, in its own dedicated issue.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/triska/simsttab/issues/3#issuecomment-893666456, or unsubscribe https://github.com/notifications/unsubscribe-auth/AIUQ7AKI37OF5W4INONN6ULT3LGFPANCNFSM5BQXTGTQ . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&utm_campaign=notification-email .

-- =============================================== بسم الله الرحمن الرحيم الحمد لله رب العالمين و صلاة و سلاما على الحبيب محمد رسول الله و اﻷنبياء أجمعين May Allah's Peace and Prayers be upon prophet Mohammad and his fellow prophets, Amen. ================================================= اللهم ارحم والدي الحبيب و اجعله من الذين هم أحياء عند ربهم يرزقون..و بارك لي في والدتي و لا تحرمني منها أبدا https://www.facebook.com/abouelseoud.saleh https://www.facebook.com/abouelseoud.saleh ============================================== Gehan Abouelseoud Saleh Phd in Electrical Engineering Faculty of Engineering Alexandria University, Egypt =============================================================

May we all be a message of mercy and love from Allah to all His creatures.

إنه من أكثر الأمور إيلاما في هذه الدنيا ألا نجد ممن نحبهم من استشعار آلامنا و مشاركتنا همومنا ما نرجو و الأشد من ذلك ألما أن نجد أننا مثلهم

flexoron commented 3 years ago

When directives are defined in reqs.pl, it works. (and so does Example 3, unsorted).

$ cat reqs.pl

% Simplified: 1 teacher, 1 subject, 2 classes, 2 x 5 lessons, 2 free slots for both classes at Mon, 1 day off at Tue. % Hint: the configuration demands coupling for both classes due to 1 day off.

:- discontiguous(class_subject_teacher_times/4). :- discontiguous(coupling/4). :- discontiguous(class_freeslot/2). :- discontiguous(room_alloc/4).

slots_per_week(20). slots_per_day(4).

teacher_freeday(sjk1, 1).

class_subject_teacher_times('1a', sjk, sjk1, 5). coupling('1a', sjk, 0, 1). class_freeslot('1a', 0). class_freeslot('1a', 1). room_alloc(r1, '1a', sjk, 4).

class_subject_teacher_times('1b', sjk, sjk1, 5). coupling('1b', sjk, 0, 1). % shift coupling, try one of those: % coupling('1b', sjk, 1, 2). % coupling('1b', sjk, 2, 3). % coupling('1b', sjk, 3, 4). class_freeslot('1b', 2). class_freeslot('1b', 3). room_alloc(r1, '1b', sjk, 4).

gabouelseoud commented 3 years ago

@flexoron: Thank you very much. Yes, this works for me, too. However, again memory consumption is huge and it takes longer time to get to the solution. Something is wrong. Newer version should be an improvement. This is not the case. Older versions find the solution faster and using less memory. For me, this makes it unwise to use the new release version.

On Fri, 6 Aug 2021 at 15:45, flexoron @.***> wrote:

When directives are defined in reqs.pl, it works. (and so does Example 3).

$ cat reqs.pl (simplified: 1 teacher, 1 subject, 2 classes, 2 x 5 lessons, free slots for both classes at Mon, 1 day off at Tue).

:- discontiguous(class_subject_teacher_times/4). :- discontiguous(coupling/4). :- discontiguous(class_freeslot/2). :- discontiguous(room_alloc/4).

slots_per_week(20). slots_per_day(4).

teacher_freeday(sjk1, 1).

class_subject_teacher_times('1a', sjk, sjk1, 5). coupling('1a', sjk, 0, 1). class_freeslot('1a', 0). class_freeslot('1a', 1). room_alloc(r1, '1a', sjk, 4).

class_subject_teacher_times('1b', sjk, sjk1, 5). coupling('1b', sjk, 0, 1). class_freeslot('1b', 2). class_freeslot('1b', 3). room_alloc(r1, '1b', sjk, 4).

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/triska/simsttab/issues/3#issuecomment-894271789, or unsubscribe https://github.com/notifications/unsubscribe-auth/AIUQ7AJ3OUKYI5UK5ECTT5TT3PRRFANCNFSM5BQXTGTQ . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&utm_campaign=notification-email .

-- =============================================== بسم الله الرحمن الرحيم الحمد لله رب العالمين و صلاة و سلاما على الحبيب محمد رسول الله و اﻷنبياء أجمعين May Allah's Peace and Prayers be upon prophet Mohammad and his fellow prophets, Amen. ================================================= اللهم ارحم والدي الحبيب و اجعله من الذين هم أحياء عند ربهم يرزقون..و بارك لي في والدتي و لا تحرمني منها أبدا https://www.facebook.com/abouelseoud.saleh https://www.facebook.com/abouelseoud.saleh ============================================== Gehan Abouelseoud Saleh Phd in Electrical Engineering Faculty of Engineering Alexandria University, Egypt =============================================================

May we all be a message of mercy and love from Allah to all His creatures.

إنه من أكثر الأمور إيلاما في هذه الدنيا ألا نجد ممن نحبهم من استشعار آلامنا و مشاركتنا همومنا ما نرجو و الأشد من ذلك ألما أن نجد أننا مثلهم

flexoron commented 3 years ago

This application is new to me. ok?

Here on my system, scyrer stabilizes its memory after a while and stops consuming. The CPU temperature shows slow growth..

Anyway, my kiddy(1b) likes coupling requirement @triska coupling(C, S, L1, L2) For class C, lessons L1 and L2 of subject S are to be scheduled in direct succession.

If direct succession here means the last slot of a day and the first slot of the next day are coupled then the requirement is fulfilled. If coupling should be 2 slots of a day sequenced(a block) then simsttab.pl needs refinement.

With reqs.pl above: censor '1b', demand second coupling. coupling('1b', sjk, 0, 1). coupling('1b', sjk, 3, 4).

block(3,4) splits at times.

triska commented 3 years ago

Yes, you are right, well spotted!

Currently, coupling constraints are erroneously satisfied even if the coupling crosses a day boundary. This is obviously not what is intended with a coupling.

Let's please discuss this and possible solutions in a separate issue or pull request. Thank you a lot! Update: This is addressed via ad67f87da75ab1ff462af82d52fa02a1f1578460.

triska commented 3 years ago

Regarding separation of issues, I have a general comment: Please, in general, let's keep an issue to a single topic. We are currently facing 3 different issues:

Thank you a lot for looking into all these issues, these will improve Scryer Prolog and also simsttab!

flexoron commented 3 years ago

That's all well and good, but we need your help because it is your application which does not work as expected.

Where does the expectation come from? From simsttab's homepage, right?

So, please: Why does Example 3 work there (try it! ... go)

Semantics of coupling constraints: Yes this is a side-effect issue and is simsttab specific. Performance of Scryer Prolog: Example 3 answers quick. So it seems it runs on a powerhouse. Correctness of directives: Example 3 is unsorted so discontiguous directive seems to be declared somewhere? Where did you place the directives? (and if directives are not defined, why does it work there and not elsewhere?)

triska commented 2 years ago

With the rebis-dev branch of Scryer Prolog, this mostly works, except for one remaining issue: https://github.com/mthom/scryer-prolog/issues/1202

As a workaround until this issue is resolved, you can add the following directives at the start of example3.pl:

:- discontiguous(class_subject_teacher_times/4).
:- discontiguous(class_freeslot/2).
:- discontiguous(coupling/4).

The rebis-dev branch also entails significant performance improvements compared to master, I hope it works well for you!

gabouelseoud commented 2 years ago

Thank you very much for your reply. I guess this way my main problems are solved

On Wed, 12 Jan 2022 at 15:58, Markus Triska @.***> wrote:

With the rebis-dev branch of Scryer Prolog, this mostly works, except for one remaining issue: mthom/scryer-prolog#1202 https://github.com/mthom/scryer-prolog/issues/1202

As a workaround until this issue is resolved, you can add the following directives at the start of example3.pl:

:- discontiguous(class_subject_teacher_times/4). :- discontiguous(class_freeslot/2). :- discontiguous(coupling/4).

The rebis-dev branch also entails significant performance improvements compared to master, I hope it works well for you!

— Reply to this email directly, view it on GitHub https://github.com/triska/simsttab/issues/3#issuecomment-1011073126, or unsubscribe https://github.com/notifications/unsubscribe-auth/AIUQ7AMNACAIHO6TKQCJSOLUVWCJBANCNFSM5BQXTGTQ . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.

You are receiving this because you authored the thread.Message ID: @.***>

-- =============================================== بسم الله الرحمن الرحيم الحمد لله رب العالمين و صلاة و سلاما على الحبيب محمد رسول الله و اﻷنبياء أجمعين May Allah's Peace and Prayers be upon prophet Mohammad and his fellow prophets, Amen. ================================================= اللهم ارحم والدي الحبيب و اجعله من الذين هم أحياء عند ربهم يرزقون..و بارك لي في والدتي و لا تحرمني منها أبدا https://www.facebook.com/abouelseoud.saleh https://www.facebook.com/abouelseoud.saleh ============================================== Gehan Abouelseoud Saleh Phd in Electrical Engineering Faculty of Engineering Alexandria University, Egypt =============================================================

May we all be a message of mercy and love from Allah to all His creatures.

إنه من أكثر الأمور إيلاما في هذه الدنيا ألا نجد ممن نحبهم من استشعار آلامنا و مشاركتنا همومنا ما نرجو و الأشد من ذلك ألما أن نجد أننا مثلهم