20.500.12556/RUL-186768 Implementacije vezanih spremenljivk v programskih jezikih delo diplomskega seminarja Implementations of bound variables in programming languages Pri implementaciji programskih jezikov programe pogosto predstavljamo z abstraktnimi sintaksnimi drevesi. Pri tej strukturi moramo biti posebej pozorni na predstavitev vezanih spremenljivk. Postopka preimenovanja spremenljivk in substitucije sta nagnjena k napakam. Naivne implementacije so pogosto neučinkovite. V delu je problem vezanih spremenljivk obravnavan na lambda računu, ki je preprost programski jezik funkcij. Predstavljeni so trije standardni pristopi k implementaciji vezanih spremenljivk: naivni pristop, de Bruijnovi indeksi in abstraktna sintaksa višjega reda. Predstavljena je tudi knjižnica Bindlib za OCaml, ki omogoča preprosto, varno in učinkovito delo z vezanimi spremenljivkami. Na koncu je opisana predstavitev vezanih spremenljivk programskega jezika Millet, ki služi kot osnova za razvoj prototipnih programskih jezikov. Implementacija vezanih spremenljivk v Milletu je izvedena z uporabo knjižnice Bindlib. Razlike v učinkovitosti predstavitev vezanih spremenljivk so prikazane z eksperimentom, v katerem merimo čas izvajanja štirih pristopov. When implementing programming languages, we usually represent computer programs as abstract syntax trees. With this representation we need to be especially careful when representing bound variables, because the implementations of variable renaming and substitution are error-prone. Naive implementations can result in poor performance. In this work, this problem is explored using the lambda calculus, which is a simple programming language of functions. Three representations of bound variables are presented: the naive approach, de Bruijn indices, and higher-order abstract syntax. The OCaml library Bindlib is also presented, as it makes working with bound variables simple, safe and efficient. Finally, the use of the Bindlib library is demonstrated with the example of the Millet programming language, which is used as a base when prototyping programming languages. The differences in the efficiency of bound variable representations are demonstrated by an experiment in which we measure the execution time of four implementations of the lambda calculus. programski jeziki vezane spremenljivke OCaml programming languages bound variables OCaml true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2026-09-05 08:15:22 2026-09-05 08:15:30 2026-09-07 10:45:27 0000-00-00 00:00:00 2026 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004.43 162680 290144003 23906.pdf 23906.pdf 1 CD94BECAF3EA3FCAB385D3AA33E4193B d6c17e911118f542b1cb58bd26d628b921c592f540acdeb74285dd5d02983b47 363dfd3a-a8f1-11f1-8bc5-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=246139 Fakulteta za matematiko in fiziko 0 0 0