Out of Space στο τελευταίο test case της πρώτης άσκησης σε Prolog

Question

Ενώ το πρόγραμμά μου τρέχει αρκετά καλά στον υπολογιστή, στον grader το τελευταίο test case μου βγάζει Out of Space. Θεωρητικά το πρόγραμμά μου δημιουργεί δυο λίστες μεγέθους n και τις διατρέχει, οπότε νομίζω ότι δεν θα έπρεπε να έχει πρόβλημα με την μνήμη. Μήπως ξέρετε τι θα μπορούσε να πηγαίνει λαθος;

Answer 1

Το πρόβλημα οφειλόταν στο γεγονός ότι χρησιμοποιούσες κάποια κατηγορήματα που ενώ θα μπορούσαν να είναι ντετερμινιστικά (και πραγματικά επέστρεφαν μοναδική απάντηση), άφηναν πολλά branch points ανοιχτά. Για παράδειγμα (παραφράζω λίγο δικό σου κώδικα):

running_sum([X], [X]).
running_sum([X1, X2 | T], Result) :-
  R is X1 + X2,
  running_sum([R | T], Partial),
  append([X1], Partial, Result).

Το παραπάνω υπολογίζει σωστά το running sum σε μία μη κενή λίστα ακεραίων:

?- running_sum([1, 1, 1, 1, 1], Result).
Result = [1, 2, 3, 4, 5] ;
false.

Αν όμως θέλεις να το γράψεις καλύτερα, ώστε να χρειάζεται λιγότερη μνήμη, να είναι tail-recursive και επίσης ντετερμινιστικό:

running_sum(L, Result) :- running_sum(0, L, Result).

running_sum(R, L, Result) :-
  ( L = [] ->
      Result = []
  ; L = [H | T] ->
      NewR is R + H,
      Result = [NewR | Partial],
      running_sum(NewR, T, Partial)
  ).