Kilpkonnagraafika interpretaator

Soovituslik töömaht: üks kuni kaks nädalat
Töövorm: individuaalne
Keeled: Idris2, Haskell, OCaml või kokkuleppel mõni muu funktsionaalne programmeerimiskeel

Eesmärk

Selles ülesandes koostad väikese kilpkonnagraafika keele ja selle interpretaatori. Kilpkonn asub tasandil, vaatab kindlas suunas ning võib liikudes joonistada sirglõike. Interpretaator ei joonista ise ekraanile, vaid teisendab programmi joonist kirjeldavaks andmestruktuuriks.

kilpkonnaprogramm -> sirglõikude loend -> SVG-fail

Ülesanne harjutab algebralisi andmetüüpe, mustrisobitamist, rekursiooni, oleku eksplitsiitset edastamist ning puhta funktsionaalse tuuma eraldamist sisendist ja väljundist.

1. Keele käsud

Realiseeri vähemalt järgmised käsud:

Forward d -- liigu d ühikut kilpkonna praeguses suunas;
Turn a -- pööra a kraadi vastupäeva;
PenUp -- tõsta pliiats üles;
PenDown -- pane pliiats alla;
Repeat n p -- täida programmi p järjest n korda.

Programm on käskude järjend. Idris2-s võib lähtepunktiks võtta näiteks järgmised tüübid:

data Command
  = Forward Double
  | Turn Double
  | PenUp
  | PenDown
  | Repeat Nat (List Command)

Program : Type
Program = List Command

Täpselt neid tüübinimesid ega konstruktorite nimesid ei pea kasutama, kuid kõik eespool kirjeldatud võimalused peavad olema olemas.

2. Semantika

Kilpkonna olek sisaldab vähemalt:

asukohta (x, y);
suunda kraadides;
infot selle kohta, kas pliiats on all.

Algolekus:

asub kilpkonn punktis (0, 0);
vaatab positiivse x-telje suunas ehk tema suund on 0 kraadi;
on pliiats all.

Kasutame matemaatilist koordinaatsüsteemi: x kasvab paremale ja y üles. Positiivne pöördenurk tähendab vastupäeva pööramist. Nurka ei ole kohustuslik vahemikku 0 kuni 360 normaliseerida.

Käsu Forward d uus asukoht on:

x' = x + d * cos(a * pi / 180)
y' = y + d * sin(a * pi / 180)

Kui pliiats on all, lisatakse joonisele sirglõik vanast punktist uude punkti. Kui pliiats on üleval, muutub ainult kilpkonna asukoht. Negatiivset pikkust käsitletakse tagurpidi liikumisena.

Repeat 0 p ei tee midagi. Repeat n p korral täidetakse terve p esimest korda tekkinud lõppolekust, seejärel järgmine kord uuest lõppolekust ja nii edasi. Sirglõikude järjekord tulemuses peab vastama nende joonistamise järjekorrale.

3. Joonise esitus

Joonis peab olema eraldi andmestruktuur, mitte kohe SVG-tekst. Minimaalne esitus on sirglõikude loend:

record Point where
  constructor MkPoint
  x : Double
  y : Double

record Segment where
  constructor MkSegment
  start : Point
  end : Point

Drawing : Type
Drawing = List Segment

Kui loominguline laiendus kasutab näiteks värvi või joone paksust, lisa vastav info olekusse ja sirglõigu tüüpi.

4. Interpretaator

Interpretaatori tuum peab olema puhas: sama programm ja sama algolek annavad alati sama tulemuse. Failide lugemine ja kirjutamine paiguta eraldi funktsioonidesse.

Soovituslik liides Idris2-s on:

execute : Command -> TurtleState -> (TurtleState, Drawing)

runProgram : Program -> TurtleState -> (TurtleState, Drawing)

draw : Program -> Drawing

Võid kasutada teistsugust liidest, kui selles on selgelt eristatavad kilpkonna olek, programmi täitmine ja tekkinud joonis.

Jälgi eriti seda, et kahe järjestikuse käsu joonised ühendataks õiges järjekorras. Lahendus ei tohi kasutada globaalset muudetavat olekut.

5. Kohustuslikud näited

Koosta oma keeles vähemalt järgmised programmid:

ruut küljepikkusega 100;
katkendlik joon või kujund, mis näitab nii PenUp kui ka PenDown mõju;
funktsioon polygon, mis koostab etteantud külgede arvu ja küljepikkusega korrapärase hulknurga programmi;
enda loodud joonis, mille programmis kasutatakse rekursiooni või parameetrilist programmi koostavat funktsiooni.

polygon peab töötama vähemalt kõigi n >= 3 korral. Juhtumite n < 3 käitumine tuleb ise valida ja dokumenteerida.

Genereeri kõigi nelja näite kohta SVG-fail. SVG loomise väike Idris2 näide on lisas 1.

6. Loominguline laiendus

Lisa keelele või programmide koostamise vahenditele vähemalt üks omal valikul võimalus. Näiteks:

joone värvi või paksuse muutmine;
kilpkonna oleku salvestamine ja taastamine;
liikumine otse etteantud punkti;
joonise pööramine, nihutamine või skaleerimine;
tingimuslik või sümmeetriline programmikonstruktsioon;
parameetriline fraktal või muu rekursiivne mustrigeneraator.

Laiendus peab mõjutama sinu loodud joonist. Kirjelda lühidalt laienduse semantikat, sealhulgas vähemalt üht piirjuhtu. Parsimise laiendamine ei ole selles töös nõutud ega lähe üksi loomingulise laiendusena arvesse.

7. Testimine

Kirjuta vähemalt kuus automaatset testi. Testi interpretaatori andmestruktuure ja tulemusi, mitte genereeritud SVG-teksti. Testide hulgas peavad olema vähemalt:

tühi programm;
edasiliikumine all oleva pliiatsiga;
edasiliikumine üleval oleva pliiatsiga;
pööramine ja sellele järgnev liikumine;
Repeat 0;
pesastatud või mitut käsku sisaldav Repeat.

Ujukomaarvude võrdlemisel kasuta ligikaudset võrdsust, näiteks tolerantsi 10^-6, mitte tingimata täpset võrdsust.

8. Esitamine

Esita:

kogu lähtekood;
automaatsed testid ja nende käivitamise juhis;
nelja kohustusliku näite SVG-failid;
lühike käivitamise juhis.

Lahenduse sisuline osa peaks jääma nii lühikeseks, et suudad kõigi funktsioonide käitumist täpselt selgitada. Graafikateegi, aknahalduse või üldise tekstiparseri ehitamine ei ole ülesande eesmärk.

9. AI kasutamine ja kaitsmine

AI-vahendite kasutamine on selle ülesande juures lubatud. Vastutad siiski kogu esitatud lahenduse eest: pead oskama selgitada andmetüüpe, käsu täitmise samme, rekursiooni ning testide oodatavaid tulemusi.

Kaitsmisel võidakse paluda:

täita üks lühike programm käsitsi samm-sammult;
selgitada ühe testi vajalikkust;
teha olemasolevas lahenduses väike muudatus, näiteks lisada üks lihtne käsk või muuta algolekut.

Lisa 1. Väike SVG-faili generaator Idris2-s

Järgmine iseseisev programm teisendab sirglõikude loendi SVG-tekstiks ja kirjutab selle faili drawing.svg. Näide pöörab y-koordinaadi märgi ümber, sest SVG-s kasvab y vaikimisi allapoole, kuid ülesandes kasutatud matemaatilises koordinaatsüsteemis ülespoole.

module Main

import System.File

record Point where
  constructor MkPoint
  x : Double
  y : Double

record Segment where
  constructor MkSegment
  start : Point
  end : Point

segmentSvg : Segment -> String
segmentSvg (MkSegment (MkPoint x1 y1) (MkPoint x2 y2)) =
  "  <line x1=\"" ++ show x1 ++
  "\" y1=\"" ++ show (-y1) ++
  "\" x2=\"" ++ show x2 ++
  "\" y2=\"" ++ show (-y2) ++
  "\" />\n"

renderSvg : List Segment -> String
renderSvg segments =
  "<svg xmlns=\"http://www.w3.org/2000/svg\" " ++
  "viewBox=\"-20 -120 140 140\">\n" ++
  "<g fill=\"none\" stroke=\"black\" stroke-width=\"2\">\n" ++
  concat (map segmentSvg segments) ++
  "</g>\n</svg>\n"

square : List Segment
square =
  [ MkSegment (MkPoint 0 0) (MkPoint 100 0)
  , MkSegment (MkPoint 100 0) (MkPoint 100 100)
  , MkSegment (MkPoint 100 100) (MkPoint 0 100)
  , MkSegment (MkPoint 0 100) (MkPoint 0 0)
  ]

main : IO ()
main = do
  result <- writeFile "drawing.svg" (renderSvg square)
  case result of
    Left err => putStrLn ("Viga: " ++ show err)
    Right () => putStrLn "Kirjutasin faili drawing.svg"

Käivita programm käsuga:

idris2 --exec main WriteSvg.idr

Seejärel ava drawing.svg veebibrauseris. Näite viewBox sobib antud ruudule. Oma jooniste puhul muuda selle nelja arvu või lisa soovi korral joonise piirdekasti automaatne arvutamine. Ülesande lahenduses asenda square oma interpretaatori tagastatud joonisega. Kui lisad värvi või joone paksuse, lisa vastavad SVG-atribuudid funktsioonis segmentSvg.

Funktsionaalprogrammeerimine 2026/27 sügis