Deklaratív programozás

2. Prolog kis házi feladat

2005. március 18.

A kis házi feladat beadása nem kötelező.

A feladat

Számlétrának nevezzük az alábbi tömör Prolog kifejezéseket (ahol A, B és S számok, to és step operátorok):

A;
A to B: csak akkor számlétra, ha A <= B (javítva; régebben itt ``<'' volt)
A to B step S: csak akkor számlétra, ha S != 0 és (B - A) / S >= 0.

Minden számlétra egy véges számtani sorozatot definiál:

A: az egyelemű (A) számtani sorozat
A to B: a lehető leghosszabb (A, A + 1, A + 2, ...) számtani sorozat, melynek nincs B-nél nagyobb eleme;
A to B step S: a lehető leghosszabb (A, A + S, A + 2S, ...) számtani sorozat, melynek nincs B-nél nagyobb eleme, ha S pozitív, illetve B-nél kisebb eleme, ha S negatív.

Azt mondjuk, hogy egy X szám a számlétra tagja, ha X a számlétra által meghatározott sorozat egyik eleme.

Megírandó egy program Prolog nyelven, amely tartalmazza az enumerate/2 eljárást, melynek jelentése a következő:

% enumerate(+L,?X) pontosan akkor igaz, ha X tagja az L listában található
% valamelyik számlétrának. Feltételezhető, hogy L tömör Prolog-kifejezés,
% X pedig vagy behelyettesítetlen, vagy egy szám. A hívásnak L-ben balról
% jobbra haladva, egy számlétrán belül pedig A-ból B felé
% haladva kell felsorolnia az összes megoldást, esetleg ugyanazt az
% X-et többször is. Az L listának lehet olyan eleme is, amely nem számlétra,
% ezeket az elemeket figyelmen kívül kell hagyni (és a részhívásnak meg kell
% hiúsulnia).

A to és step operátorokat a program elején definiálni kell. Célszerű 400-nál kisebb precedencia-számokat választani. Ehhez segítség: például a beépített + és * operátorokat így definiálták:

:- op(500, fx, '+').
:- op(500, yfx, '+').
:- op(400, yfx, '*').

A to és a step közül a step precedencia-száma legyen nagyobb, vagyis az alábbi hívás sikeres legyen:

:- (1 to 3) step 2 == 1 to 3 step 2.

Egy példamegoldás (khf-pl2.pl), amely csak a számlétrák operátor nélküli alakját kezeli:

enumerate([H|_], H) :- number(H).
enumerate([_|T], X) :- enumerate(T, X).

A jobbrekurzív eljárások kevesebb memóriát igényelnek, mint az egyéb rekurzív eljárások, ezért a feladat megoldása során jobbrekurzív eljárások írása ajánlott, ám ez nem kötelező, a pontozásba nem számít bele.

Példák

| ?- enumerate([42],X).
X = 42 ? ;
no

| ?- enumerate([42,43,gyok(ketto),42],X).
X = 42 ? ;
X = 43 ? ;
X = 42 ? ;
no

| ?- enumerate([1 to 8 step 3, 1.5, 3.5 to 2 step -1.4, 4 to 6, 9 to 8], X).
X = 1 ? ;
X = 4 ? ;
X = 7 ? ;
X = 1.5 ? ;
X = 3.5 ? ;
X = 2.1 ? ;
X = 4 ? ;
X = 5 ? ;
X = 6 ? ;
no

Otthoni tesztkörnyezet

A fejlesztés közbeni tesztelésre a SICStus Prolog vagy az SWI-Prolog ajánlott. Hasznos lehet még az alábbi segédprogram (teszt2.pl):

:- consult('khf-pl2').
:- findall(X, enumerate([42],X), L),
   E=[42],
   print(L==E), nl, L==E.
:- findall(X, enumerate([42,43,gyok(ketto),42],X), L),
   E=[42,43,42],
   print(L==E), nl, L==E.
:- findall(X,
     enumerate([1 to 8 step 3, 1.5, 3.5 to 2 step -1.4, 4 to 6, 9 to 8], X),
     L),
   E=[1,4,7,1.5,3.5,2.1,4,5,6],
   print(L==E), nl, L==E.

Ha ezt a programot a környezet hiba nélkül betölti (pl. a sicstus -l teszt2.pl vagy a

swipl -s
teszt2.pl

parancs hatására), akkor a khf-pl2.pl-ben nincs szintaktikai hiba, és a teszt2.pl-ben leírt három teszteset is hibátlanul fut le.

Tudnivalók a beadásról

A programot az Elektronikus Tanársegéd segítségével Weben keresztül lehet beadni, a HF beadás menüpont alatt. Ez az második Prolog kis házi feladat, ezért khf-pl2.pl néven kell beküldeni a megoldást. A névben meg kell különböztetni a kis- és nagybetűket. A (márc. 30-án módosított!) beadási határidő 2005. április 6., szerda 24:00.

A vizsgaosztályzat megállapításakor a határidőre beadott, helyesen megoldott kis házi feladatért plusz 1 pont jár (a 100 pontból).