Prolog: add intro text for lists exercises

author: Timotej Lazar <timotej.lazar@fri.uni-lj.si> 2016-03-10 15:55:58 +0100
committer: Timotej Lazar <timotej.lazar@fri.uni-lj.si> 2016-03-10 15:55:58 +0100
commit: 8bbd19d74c1be8f19888556be1894482abb1b7d5 (patch)
tree: 01cd6e1eeaafaaebff1a3baba8feb4c8777d905f /prolog
parent: 0cb99edad42fb4e383599dd56dc8db12bf8d40cc (diff)
5 files changed, 398 insertions, 3 deletions
diff --git a/prolog/intro_sl.html b/prolog/intro_sl.html
index 921f9d7..8a99152 100644
--- a/prolog/intro_sl.html
+++ b/prolog/intro_sl.html
@@ -1,6 +1,6 @@
 <!DOCTYPE html>
 <html lang="sl">
-  <head>
+<head>
   <meta charset="utf-8" />
   <title>CodeQ: Prolog</title>
   <link rel="stylesheet" type="text/css" href="style.css" />
diff --git a/prolog/problems/family_relations/intro_sl.html b/prolog/problems/family_relations/intro_sl.html
index ce3fb50..fe0476b 100644
--- a/prolog/problems/family_relations/intro_sl.html
+++ b/prolog/problems/family_relations/intro_sl.html
@@ -1,10 +1,9 @@
 <!DOCTYPE html>
 <html lang="sl">
-  <head>
+<head>
   <meta charset="utf-8" />
   <title>Prolog: družinske relacije</title>
   <link rel="stylesheet" type="text/css" href="../style.css" />
-  </style>
 </head>
 <body>
 
diff --git a/prolog/problems/lists/intro_sl.html b/prolog/problems/lists/intro_sl.html
new file mode 100644
index 0000000..2b59f5b
--- /dev/null
+++ b/prolog/problems/lists/intro_sl.html
@@ -0,0 +1,326 @@
+<!DOCTYPE html>
+<html lang="sl">
+<head>
+    <meta charset="utf-8" />
+	<title>Prolog: seznami</title>
+    <link rel="stylesheet" type="text/css" href="../style.css" />
+</head>
+<body>
+
+<h1>Prolog: seznami</h1>
+<p>
+Seznami so verjetno daleč najbolj pomembna podatkovna struktura v prologu.
+Poleg tega so tudi zelo primerni za začetni, pa vseeno precej resen, skok v
+svet rekurzije, kar bomo z veseljem izkoristili! Vendar pa operacije na
+seznamih, ki jih boš implementiral danes, niso tu samo za vajo. Kasneje jih
+bomo veliko uporabljali, saj s seznami lahko naredimo res marsikaj.
+</p>
+
+<h2>Kako izgledajo seznami v prologu?</h2>
+<p>
+Torej, kako sezname v prologu zapišemo, predstavimo? Tole je primer seznama:
+</p>
+<pre>
+?- L = [a,b,c].
+</pre>
+
+<p>
+Kot vidiš, je zapis preprost in očiten. Med oglate oklepaje enostavno naštejemo
+elemente seznama, ki jih med seboj ločimo z vejico. 
+</p>
+
+<p>
+Naslednje vprašanje. Kaj so lahko elementi seznama, morajo morda biti istega
+tipa? Hmm, tipi v prologu, s tem se ne bomo ukvarjali danes, ampak v enem izmed
+kasnejših poglavij. Da ne zavlačujem: v prologovih seznamih lahko skupaj
+shranjuješ karkoli. Karkoli. Skratka, tole je povsem legalno:
+</p>
+<pre>
+?- L = [a, 3, 3.14, [], [a,b,c], sin(a), parent(tina,william)].
+</pre>
+
+<p>
+V ta seznam sem torej stlačil atom (konstanto) <code>a</code>, število
+<code>3</code>, število v plavajoči vejici <code>3.14</code>, prazen seznam
+<code>[]</code>, seznam <code>[a,b,c]</code>, strukturo <code>sin(a)</code> in
+strukturo (tako je, to ni predikat!) <code>parent(tina, william)</code>. Saj
+sem rekel, da je v seznamu lahko karkoli. Nič posebnega, boš dejal, to lahko
+tudi v kakšnem drugem jeziku, npr. v pythonu. Drži, drži, kaj pa tole:
+</p>
+<pre>
+?- L = [a,b,c,X,Y,Z].
+</pre>
+
+<p>
+Samo malo, kaj nismo z veliko začetnico označevali spremenljivk? Smo. Kako pa
+prolog ve, kakšne vrednosti imajo? Ne ve. In so vseeno lahko v seznamu, ne da
+bi poznali njihove vrednosti? Tako je! In ko morda kasneje dobijo neko
+vrednost? Bo ta v seznamu.
+</p>
+
+<p>
+Dobro, kako pa do posameznih elementov dostopam, ko jih potrebujem? Jih lahko
+naslavljam po indeksu (mestu v seznamu)? Lahko pišem <code>L[3]</code>? Ne. Ne,
+res ne? Res ne. Poglejmo še malo, kako so seznami predstavljeni interno, in boš
+razumel, zakaj ne. Vse reči v prologu so interno predstavljene z drevesi in to
+velja tudi za sezname. Seznam je v resnici struktura (to se boš učil kasneje),
+katere ime je simbol pika (<code>.</code>), sprejme pa dva argumenta: prvi
+element seznama in seznam(!) preostalih elementov. Tako je, seznam je definiran
+rekurzivno! Prazen seznam je posebnost in mu pripada simbol <code>[]</code>.
+</p>
+
+<p>
+Seznam <code>[a,b,c]</code> je interno v resnici
+<code>.(a, .(b, .(c, [])))</code>; tako ga lahko tudi zapišeš (opomba: novejše
+verzije SWI-Prologa in tudi <span class="codeq">CodeQ</span> namesto
+<code>.</code> uporabljajo <code>[|]</code>).
+Za ljudi je ta zapis precej štorast, zato obstaja alternativni zapis z oglatimi
+oklepaji, ki smo ga spoznali na začetku. A v resnici je ta zapis samo
+sintaktični sladkorček in se interno prevede v zapis s piko, prikazan na
+spodnji sliki.
+</p>
+
+<figure>
+    <img src="list.svg" />
+    <figcaption>Struktura seznama <code>[a,b,c]</code></figcaption>
+</figure>
+
+<p>
+Skratka, seznam je v resnici izrojeno drevo, po katerem se moramo sprehoditi do
+iskanega elementa. Lahko si ga predstavljamo kot vrsto ljudi: dostop imamo le
+do prvega človeka v vrsti, do ostalih pa pridemo tako, da prvega „obdelamo“ in
+ga vzamemo iz vrste. In tako naprej, dokler ne najdemo iskanega elementa ali
+dokler ni seznam prazen. Nekoliko štorasto morda, a zdaj razumeš, zakaj je
+tako.
+</p>
+
+<p>
+Prolog ima vgrajen še en sintaktični sladkorček za lažji zapis takšnega dostopa
+do elementov seznama. To je zapis z navpičnico, ki ga bomo neprestano
+uporabljali.
+</p>
+<pre>
+?- L = [a,b,c], L = [Head|Tail].
+</pre>
+
+<p>
+Kaj smo zapisali? V prvem delu konjunkcije (pred vejico) smo spremenljivki
+<code>L</code> „priredili“ seznam <code>[a,b,c]</code>, v drugem delu pa smo
+seznam „razbili“ na dva dela z navpičnico: na prvi element in na preostanek,
+oboje pa shranili v spremenljivki <code>Head</code> in <code>Tail</code>.
+Tako je, prvemu elementu seznama bomo rekli glava (<code>Head</code>),
+preostanku seznama pa rep (<code>Tail</code>).
+Spremenljivkama seveda lahko damo poljubno ime, velikokrat pa bomo uporabljali
+kar <code>H</code> in <code>T</code>. Če prologu zgornje vprašanje zastavimo,
+dobimo pričakovan odgovor:
+</p>
+<pre>
+?- L = [a,b,c], L = [Head|Tail].
+Head = a, Tail = [b,c].
+</pre>
+
+<p>
+Kot vidiš, imaš enostaven dostop do prvega elementa in do preostanka seznama.
+Pravzaprav celo nekoliko več, na začetku namreč lahko pišeš poljubno število
+glav, ločenih z vejico. Poskusi tole:
+</p>
+<pre>
+?- L = [a,b,c], L = [H1,H2|T].
+H1 = a, H2 = b, T = [c].
+</pre>
+
+<p>
+Zelo pomembno: glava seznama je <em>element</em> seznama in je lahko
+<em>poljubnega tipa</em> (saj si videl, da so elementi seznama lahko karkoli),
+medtem ko je rep seznama <em>vedno</em> seznam, pa četudi prazen! To bo v tem
+sklopu verjetno ena najbolj pogostih napak, dokler se ne navadiš.
+</p>
+
+<p>
+Prejle sem rekel, da z navpičnico seznam razbijemo. Ampak kot se spomniš, v
+prologu reči večinoma delujejo v vse mogoče smeri. In razbijanje je ravno
+nasprotno od sestavljanja. Primer:
+</p>
+<pre>
+?- NewElement = d, L = [a,b,c], L1 = [NewElement|L].
+L1 = [d,a,b,c].
+</pre>
+
+<p>
+Aha, sedaj sem element vstavil! Tako je, na zapis <code>[H|T]</code> glej kot
+na primerjanje vzorcev (<em>pattern matching</em>). Ali tudi na ostale zapise
+seznamov, npr. <code>[H]</code> in <code>[X,Y,Z]</code>, ki ne pomenita drugega
+kot seznam z enim oz. tremi elementi. Tako je, seznam z enim elementom je
+preprosto <code>[H]</code>, ne potrebuješ pisati <code>[H|[]]</code> – to je
+grdo (a seveda tudi deluje in pomeni enako).
+</p>
+
+<p>
+Če si opazil, sem zgoraj uporabil novo spremenljivko <code>L1</code> ob
+dodajanju elementa v seznam <code>L</code>. Zakaj? Sem s tem naredil nov
+seznam? Zakaj?
+</p>
+
+<p>
+Tako je. Spomnimo se, da je prolog logični jezik. Če bi napisal
+<code>L = [NewElement|L]</code>, kaj bi s tem logično povedal? Prolog bi
+vprašal oz. mu naročil, da lahko naredi levo in desno stran enačaja enako
+(spomni se, operator <code>=</code> pomeni unifikacijo). Torej nek
+<code>L</code> bi moral postati enak samemu sebi s tem, da bi imel na začetku
+še en element.
+Ali seznam s tremi elementi (recimo, da so trije v <code>L</code>) bi moral
+postati enak seznamu s štirimi elementi. Mislim, da prologov odgovor poznaš.
+„No!“ (In to zelo glasen ne.) Na to se spomni kasneje, ko bomo imeli opravka z
+aritmetiko: spremenljivki, ki ima vrednost 3 ne moreš kar prišteti ena, ker 3
+logično ni enako 4.
+</p>
+
+<p>
+Zato je potrebno uvesti novo spremenljivko, ki naredi nov seznam (zgoraj je to
+<code>L1</code>). Pa ni to pomnilniško potratno. Je, vendar za to skrbi
+prologov <em>garbage collector</em>.
+</p>
+
+<p>
+Zanimivost: prolog je bil eden izmed prvih jezikov (tam v sedemdesetih letih),
+ki je imel samodejni garbage collector. Takrat je bil pomnilnik izredno
+dragocena reč in je bilo praktično bogokletno pomisliti na to, da bi za nadzor
+nad porabo skrbel računalnik sam, to je bilo prepuščeno programerju. A pri
+prologu seveda ni šlo drugače, preprosto zaradi zasnove jezika. 
+</p>
+
+<p>Kratek pregled pomembnih reči:</p>
+<ul>
+    <li>v seznamih je lahko karkoli;</li>
+    <li>dostopaš vedno do glave seznama (ali več glav), do repa se moraš
+	(rekurzivno) prebiti;</li>
+    <li>na zapis <code>[H|T]</code> glej kot na primerjanje vzorcev;</li>
+	<li>ne razmišljaj o porabi pomnilnika, za to skrbi garbage collection;</li>
+	<li>glava seznama je poljubnega tipa, medtem, ko je rep seznama vedno seznam.</li>
+</ul>
+
+<h2>Kako programiramo s seznami?</h2>
+<p>
+Najbolje, da eno nalogo sprogramiramo skupaj. Naloga naj bo naslednja: predikat
+<code>insert/3</code> naj vstavi element <code>X</code> na poljubno mesto v
+seznam <code>L</code> in vrne nov seznam <code>L1</code> z vstavljenim
+elementom. Eno za drugo (z vračanjem) naj vrne vse možne rešitve – torej
+element vstavljen na vse različne načine. Primer:
+</p>
+<pre>
+?- insert(a, [1,2,3], L1).
+L1 = [a,1,2,3] ;
+L1 = [1,a,2,3] ;
+L1 = [1,2,a,3] ;
+L1 = [1,2,3,a] ;
+false.
+</pre>
+
+<p>
+Prav, kako začeti? Dostop imam le do začetka seznama, do ostalih mest se moram
+prebiti. To mi je nekako namig glede strategije: ali vstavim takoj (na trenutni
+začetek) ali pa vstavim nekam v rep. In rekurzivno vse skupaj ponovim – oziroma
+ponovi kar prolog sam.
+</p>
+
+<p>
+Vstavljanje na začetek je preprosto in to bo kar moj robni primer:
+</p>
+<pre>
+insert(X, L, L1) :-  % procent je oznaka za vrstični komentar v prologu
+    L1 = [X|L].      % L1 izgleda kot vzorec: X na prvem mestu, rep je pa cel seznam L
+</pre>
+
+<p>
+Izkoristil sem navpičnico za sestavljanje večjega seznama, prav kot smo to
+počeli prej. Sedaj pa poglejmo kako bi vstavil v rep. Hja, prvi element bom dal
+(začasno!) stran, vstavil v rep (pustil rekurziji, da se sama odloči kam) in,
+ko od rekurzije dobim odgovor (v rep vstavljen element), dokončam rešitev tako,
+da dam prvi element nazaj na svoje mesto.
+</p>
+<pre>
+insert(X, L, L1) :-
+    L = [H|T],         % L „razbijem“ na glavo in rep
+    insert(X, T, NT),  % vstavi X nekam v rep (rekurzija)
+    L1 = [H|NT].       % predpostavim, da je rekurzija vstavila X v rep in sestavim končno rešitev
+</pre>
+
+<p>
+Logično zgornje pravilo preberem takole: če je <code>L</code> sestavljen iz
+glave <code>H</code> in repa <code>T</code> in hkrati predpostavim, da je
+<code>NT</code> seznam <code>T</code> (rep) z vstavljenim elementom
+<code>X</code> (kamorkoli) in je hkrati <code>L1</code> sestavljen iz glave
+<code>H</code> ter repa <code>NT</code> (ki vsebuje <code>X</code>, glej
+predpostavko prej), potem je <code>L1</code> seznam <code>L</code> z
+vstavljenim elementom <code>X</code>. Logično! 😊
+</p>
+
+<p>
+Kaj mi je omogočilo uporabo rekurzije? Problem vstavljanja mora z vsako uporabo
+rekurzije obvezno biti manjši. In kaj je „manjši“ z vidika seznamov? Seveda,
+krajši seznam! In rep je vedno vsaj za en element krajši od celotnega seznama –
+za glavo (ali več njih) krajši! In še drugi pogoj: rekurzija se mora nekoč
+ustaviti. Tudi to drži: prej sem napisal robni pogoj, ko se element enkrat
+vstavi, bo rekurzije konec. Kdaj se bo to zgodilo, se odloči prolog sam – z
+vsako zahtevo po novi rešitvi, bo malce drugače, dokler se vse rešitve ne
+izčrpajo. Takrat bo prolog v bistvu toliko časa trgal glave stran, da bo ostal
+s praznim seznamo, ko ne bo več mogel ničesar odtrgati. Poskusi tole in boš
+razumel:
+</p>
+<pre>
+?- L = [], L = [H|T].
+false.
+</pre>
+
+<p>
+Seveda, rekli smo, da je <code>L</code> prazen seznam in hkrati ga hotel
+razbiti na glavo in rep. A glava mora biti element, tega pa nimamo. Zato
+razstavljanje ne uspe in prolog reče „ne“.
+</p>
+
+<p>
+Zgornji program sem za lažje razumevanje napisal na zelo dolg (in grd) način.
+Od zdaj bomo programirali takole:
+</p>
+<pre>
+insert(X, L, [X|L]).
+insert(X, [H|T], [H|NT]):-
+    insert(X, T, NT).
+</pre>
+
+<p>
+Pomen je enak kot prej, le zapis je veliko krajši. Vse operatorje
+<code>=</code> (unifikacija) sem zamenjal z implicitno uporabo kar v argumentih
+predikata – temu pogovorno rečem kar programiranje v glavi stavka. Spomnite se,
+da gre za primerjanje vzorcev. Tako je, argumenti, ki jih predikat ob klicu
+dobi, se prilagodijo (unifikacija) na način kot so zapisani argumenti v glavi
+stavka. Na primer: če pokličem predikat <code>insert/3</code> s klicem
+<code>insert(a, [1,2,3], L1)</code> in se aktivira njegov rekurzivni stavek
+(drugi), se ob klicu zgodi naslednja prilagoditev:
+</p>
+<pre>
+insert(a, [1,2,3], L1) = insert(X, [H|T], [H|NT])
+</pre>
+<p>
+kar pomeni:
+</p>
+<pre>
+X = a,
+[H|T] = [1,2,3] (kar dalje pomeni: H = 1 in T = [2,3]),
+[H|NT] = L1     (oz. dalje, ker vemo, da je H = 1: L1 = [1|NT]).
+</pre>
+
+<p>
+Tako je, <code>NT</code> ostane za zdaj spremenljivka brez določene vrednosti.
+Saj se spomniš, da je to dovoljeno? No, tukaj bo prišlo prav, ker bo to kasneje
+verjetno izračunala rekurzija.
+</p>
+
+<p>
+Za konec: kakšen smisel ima vstavljanje na vsa možna mesta? Boš videl, naloga
+morda deluje tudi v kakšno nepričakovano „smer“. In tole bi morebiti znalo
+priti prav tudi pri kakšni kombinatorični nalogi kasneje.
+</p>
+
+</body>
+</html>
diff --git a/prolog/problems/lists/list.svg b/prolog/problems/lists/list.svg
new file mode 100644
index 0000000..31d73b2
--- /dev/null
+++ b/prolog/problems/lists/list.svg
@@ -0,0 +1,65 @@
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
+ "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
+<!-- Generated by graphviz version 2.38.0 (20140413.2041)
+ -->
+<!-- Title: %3 Pages: 1 -->
+<svg width="206pt" height="206pt"
+ viewBox="0.00 0.00 206.00 206.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
+<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 202)">
+<title>%3</title>
+<polygon fill="white" stroke="none" points="-4,4 -4,-202 202,-202 202,4 -4,4"/>
+<!-- cons0 -->
+<g id="node1" class="node"><title>cons0</title>
+<text text-anchor="middle" x="63" y="-176.3" font-family="sans" font-size="14.00">·</text>
+</g>
+<!-- cons1 -->
+<g id="node2" class="node"><title>cons1</title>
+<text text-anchor="middle" x="99" y="-122.3" font-family="sans" font-size="14.00">·</text>
+</g>
+<!-- cons0&#45;&#45;cons1 -->
+<g id="edge2" class="edge"><title>cons0&#45;&#45;cons1</title>
+<path fill="none" stroke="black" d="M74.7877,-161.973C78.7249,-156.286 83.1141,-149.946 87.0625,-144.243"/>
+</g>
+<!-- a -->
+<g id="node5" class="node"><title>a</title>
+<text text-anchor="middle" x="27" y="-122.3" font-family="sans" font-size="14.00">a</text>
+</g>
+<!-- cons0&#45;&#45;a -->
+<g id="edge1" class="edge"><title>cons0&#45;&#45;a</title>
+<path fill="none" stroke="black" d="M51.2123,-161.973C47.2751,-156.286 42.8859,-149.946 38.9375,-144.243"/>
+</g>
+<!-- cons2 -->
+<g id="node3" class="node"><title>cons2</title>
+<text text-anchor="middle" x="135" y="-68.3" font-family="sans" font-size="14.00">·</text>
+</g>
+<!-- cons1&#45;&#45;cons2 -->
+<g id="edge4" class="edge"><title>cons1&#45;&#45;cons2</title>
+<path fill="none" stroke="black" d="M110.788,-107.973C114.725,-102.286 119.114,-95.9464 123.063,-90.243"/>
+</g>
+<!-- b -->
+<g id="node6" class="node"><title>b</title>
+<text text-anchor="middle" x="63" y="-68.3" font-family="sans" font-size="14.00">b</text>
+</g>
+<!-- cons1&#45;&#45;b -->
+<g id="edge3" class="edge"><title>cons1&#45;&#45;b</title>
+<path fill="none" stroke="black" d="M87.2123,-107.973C83.2751,-102.286 78.8859,-95.9464 74.9375,-90.243"/>
+</g>
+<!-- empty -->
+<g id="node4" class="node"><title>empty</title>
+<text text-anchor="middle" x="171" y="-14.3" font-family="sans" font-size="14.00">[ ]</text>
+</g>
+<!-- cons2&#45;&#45;empty -->
+<g id="edge6" class="edge"><title>cons2&#45;&#45;empty</title>
+<path fill="none" stroke="black" d="M146.788,-53.9733C150.725,-48.2862 155.114,-41.9464 159.063,-36.243"/>
+</g>
+<!-- c -->
+<g id="node7" class="node"><title>c</title>
+<text text-anchor="middle" x="99" y="-14.3" font-family="sans" font-size="14.00">c</text>
+</g>
+<!-- cons2&#45;&#45;c -->
+<g id="edge5" class="edge"><title>cons2&#45;&#45;c</title>
+<path fill="none" stroke="black" d="M123.212,-53.9733C119.275,-48.2862 114.886,-41.9464 110.937,-36.243"/>
+</g>
+</g>
+</svg>
diff --git a/prolog/problems/lists/sl.py b/prolog/problems/lists/sl.py
index 9b29fff..0c8dd67 100644
--- a/prolog/problems/lists/sl.py
+++ b/prolog/problems/lists/sl.py
@@ -1,2 +1,7 @@
 name = 'Seznami'
 description = 'Delo s seznami, poudarek na rekurziji.'
+description = '''\
+<p>
+<a target="_blank" href="[%@resource intro_sl.html%]">Seznami</a>
+– osnovne operacije s poudarkom na rekurziji.
+</p>'''
author	Timotej Lazar <timotej.lazar@fri.uni-lj.si>	2016-03-10 15:55:58 +0100
committer	Timotej Lazar <timotej.lazar@fri.uni-lj.si>	2016-03-10 15:55:58 +0100
commit	8bbd19d74c1be8f19888556be1894482abb1b7d5 (patch)
tree	01cd6e1eeaafaaebff1a3baba8feb4c8777d905f /prolog
parent	0cb99edad42fb4e383599dd56dc8db12bf8d40cc (diff)