Sustav za simboličko računanje u Haskellu

master's thesis

• Author: Vitomir Čanadi
• Mentor: Vedran Čačić (mentor)
• Committee member: Vedran Čačić (predsjednik povjerenstva)
• Committee member: Ivica Nakić (član povjerenstva)
• Committee member: Luka Grubišić (član povjerenstva)
• Committee member: Bojan Basrak (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2017-07-19, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Cilj diplomskog rada bio je implementirati sustav za simbolicko računanje (CAS) u programskom jeziku Haskell. Iz perspektive CAS-a, ova implementacija ima osnovnu funkcionalnost pojednostavljivanja izraza, te dodatnu funkcionalnost rješavanja sustava linearnih jednadžbi. Iskoristili smo Haskellov način definiranja tipova (Algebraic data types) kako bismo jednostavno implementirali osnovni tip T (term). Zbog visoke razine apstrakcije koju Haskell pruža, omogućeno nam je lako definiranje funkcija poput tmap ili tFoldMap (analogije Haskell funkcija fmap i foldMap, samo nad termima). Preko takvih funkcija prirodno se mogu opisati korisne funkcije i upiti nad termom. Funkcije poput djelovanja nekom funkcijom na svaki čvor terma, ili ispitivanja postojanja čvora tipa Add dvije razine ispod korijena terma. Osim funkcionalnosti vezanih za CAS, kod se sastoji od funkcija koje služe kao definicije za teorijski dio rada. Sva svojstva koja se koriste u definicijama i dokazima teorema, a moguće ih je opisati u Haskell kodu, implementirana su unutar koda. Prednost takvog pristupa je uvid u korektnu definiciju pojedinog svojstva. Za to smo iskoristili Haskellov jezični prevoditelj. Na primjer, svojstvo isNormalFor, koje prima term i vraća Bool vrijednost, se koristi kao dio definicije nekih drugih, složenijih svojstava. Ako u nekom trenutku odlučimo promijeniti tip tog svojstva tako da prima dva terma, jezični prevoditelj nam ne dopušta da napravimo grešku prilikom takve izmjene a da pritom korektno ne izmijenimo primjenu tog svojstva na svakom drugom mjestu gdje se ono pojavljuje. Svojstva koja je moguće definirati u kodu, su dosta ograničena zbog nemogućnosti opisa univerzalnog kvantifikatora nad beskonačnim skupovima, međutim takva mana se ublažava dodavanjem sustava za testiranje (QuickCheck)

Abstract (english)

Goal of this graduate thesis was implementation of computer algebra system (CAS) in Haskell programming language. From CAS point of view, this implementation contains basic functionality for term simplification, and extra functionality for solving systems of linear equations. We used Haskell’s way of defining data types (Algebraic data types) so we could simply implement our main data type T (term). Because of high level of abstraction, which Haskell enables, we can define functions like tmap or tFoldMap (analogies of Haskell’s fmap and foldMap, but on data type T). With such functions we can naturally describe useful functions and queries on the T data type. Functions like applying some function on each node of a given term, or querying the existence of a Add-type node two levels below the root. Beside the functionality for CAS, code contains functions which serve as definitions for theoretical part of the thesis. All properties which are used in definitions and theorem proofs, and are possible to define in Haskell, are defined in the code. Advantage of such approach is insight in correct property definition. We used Haskell’s compiler for such purpose. For example, isNormal property of type T \(\to\) Bool, is used as part of some other, more complex properties. If we decide to change the type of this property to T \(\to\) T \(\to\) Bool, compiler won’t let us do that unless we accordingly updated all other properties which depend on it. Properties defined in code are quite limited because there is no way to define universal quantification over infinite sets, but we handle this flaw by implementing tests for such properties with QuickCheck.

• Keywords: sustav za simbolicko računanje; CAS; Haskell
• Keywords (english): computer algebra system; CAS; Haskell
• Language: croatian
• URN:NBN: urn:nbn:hr:217:899874
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2017-12-21 13:44:14