Matija Pretnar: Odstopajoči obhodi / Quirky traversals

Datum objave: 11. 4. 2018
Seminar za temelje matematike in teoretično računalništvo
Četrtek, 12. 4. 2018, od 11h do 13h, 3.07 na Jadranski 21
Povzetek: Izraze programskega jezika običajno predstavimo z induktivnim tipom, v katerem naštejemo vse njihove možne konstruktorje. Izkaže se, da se precej funkcij na takem tipu obnaša čisto rutinsko. Na primer, množica prostih spremenljivk aritmetičnega izraza je skoraj vedno unija prostih spremenljivk podizrazov (razen če je izraz sam spremenljivka). A kljub temu moramo v definiciji funkcije obravnavati čisto vse primere, kar hitro postane nadležno.

Na seminarju bom predstavil način, na katerega lahko take funkcije definiramo s čimmanj odvečne kode.

 

Abstract: Programming language terms are usually represented with an inductive type that lists all their possible constructors. It turns out that most functions on such a type are routine. For example, the set of free variables in a given arithmetic expression is almost always the union of free variables in subterms (except if the expression itself is a variable). Still, we must treat every single case in the function definition, and this quickly becomes annoying.

At the seminar, I will present a way in which we can define such functions with as little boilerplate as possible.