Kirjoittaja: Weggo
Kirjoitettu: 11.07.2012 – 11.07.2012
Tagit: algoritmit, ohjelmointitavat, koodi näytille, vinkki
Innostuin käännösaikaisesta koodin tuottamisesta (template metaprogramming) ja tein pienen koodipätkän, joka laskee Fibonaccin lukuja ja alkulukuja ohjelman kääntämisen aikana.
Käännösaikanen koodi on Turing-täydellinen, joten sillä on mahdollista kirjoittaa laskennallisesti monimutkaisempiakin algoritmeja.
Käännösaikaisen koodin tuottaminen on hieman mutkikkaampaa, sillä kaikki arvot ovat muuttumattomia(=immutable). Tämän takia ainoa tapa arvojen muuttamiselle on rekursiivisesti toimivat algoritmit, jotka ottavat template-parametreja ja syöttävät ne uudestaan samaan algoritmiin(=rekursio). Rekursio loppuu, kun template-struktuurin spesialisaatio luodaan tämän normaalin template-struktuurin sijaan.
Ohjelman käännösaikaiset algoritmit käyttävät rekursiota, ja muokkaavat tarvittavia parametreja jokaisen 'instanssin' aikana. Fibonacci-algoritmi laskee Fibonaccin luvut sen määritellyn algoritmin mukaan. Alkuluku-algoritmi laskee suurimman alkuluvun annetun parametrin arvoa edeltävän luvun sisällä.
#include <iostream>
using namespace std;
// kertoma-algoritmi; huomaa: ei toimi suurilla luvuilla
template<size_t N>
struct factorial
{
enum {VAL = N * factorial<N - 1>::VAL};
};
template<>
struct factorial<0>
{
enum {VAL = 1};
};
// jos N+1 on alkuluku, VAL = N+1, muutoin VAL = 2
template<size_t N>
struct prime_check
{
enum {VAL = 2 + ((2 * factorial<N>::VAL) % (N + 1))};
};
// algoritmi alkuluvun löytämiselle
template<size_t N, size_t N1 = 0, size_t C = 0, size_t C1 = prime_check<C>::VAL>
struct prime
{
enum {VAL = prime<N - 1, N1 + 1, C1, prime_check<N1>::VAL>::VAL};
};
template<size_t N, size_t N1, size_t C>
struct prime<N, N1, C, 2>
{
enum {VAL = prime<N - 1, N1 + 1, C, prime_check<N1>::VAL>::VAL};
};
template<size_t N1, size_t C, size_t C1>
struct prime<0, N1, C, C1>
{
enum {VAL = C};
};
template<size_t N1, size_t C>
struct prime<0, N1, C, 2>
{
enum {VAL = C};
};
// fibonacci-algoritmi
template<size_t N>
struct fibonacci
{
enum {VAL = fibonacci<N - 1>::VAL + fibonacci<N - 2>::VAL};
};
template<>
struct fibonacci<1>
{
enum {VAL = 1};
};
template<>
struct fibonacci<0>
{
enum {VAL = 0};
};
int main()
{
const size_t input = 13;
cout << prime<input>::VAL << endl;
cout << fibonacci<input>::VAL << endl;
cin.get();
return 0;
}Käännösaikaisen koodin tuottaminen on ihan mielenkiintoinen ja kiinnostava aihe.
Itse pidän PL/I:n esikääntäjästä, koska se käyttää ohjelmointikielen omaa rajoitettua syntaksia.
Esim. PL/I:n esikääntäjän avulla fibonacci lausekkeen lisääminen, mikä luo halutun kokoisen taulukon ja täyttää sen fibonaccin luvuilla:
%fibonacci: proc (n, table) statement;
dcl n fixed;
dcl table char;
dcl (i, f1, f2, f3) fixed;
dcl nums char;
f1 = 1; f2 = 0;
nums = '0';
do i = 1 to n;
f3 = f1 + f2;
f1 = f2;
f2 = f3;
nums = nums || ',' || f3;
end;
ans('dcl ' || table || ' (0:' || n || ') fixed bin init (' || nums || ');') skip;
%end fibonacci;
%act fibonacci;Käyttö ohjelmassa:
fibonacci n(20) table(fib);
tuossa siis n-parametri on taulukon yläindeksi ja table-parametri on haluttu nimi taulukolle.
jalski kirjoitti:
Itse pidän PL/I:n esikääntäjästä, koska se käyttää ohjelmointikielen omaa rajoitettua syntaksia.
Kätevää, mutta kuten sanoit, kohtuu rajoitettua. Luulisin että mainitsemasi esikääntäjä pätee vain käännösaikaisten laskujen laskemiseen, kun taas C++ käsittelee pääasiassa käännösaikana määriteltyjä tyyppejä template:n avulla. C++ hyväksyy kuitenkin arvoja template määrittelyihin, jolloin template:ja voidaan käyttää moneen muuhunkin epäsuorasti.
Weggo kirjoitti:
Kätevää, mutta kuten sanoit, kohtuu rajoitettua.
Tuolla rajoitetulla tarkoitin siis lähinnä sitä, että se ei tue PL/I-kielen täyttä syntaksia vaan osaa siitä... ;-)
Nojoo, eihän käännösaikana pystykään esim. varaamaan muistia dynaamisesti/käyttämään IO toimintoja. Mutta epäilen että PL/I-kielen käännösaikana käytettävä syntaksi ei kuitenkaan tue mitään 'laskuja' ihmeellisempiä asioita. Mielenkiintoista kuitenkin että tässä PL/I-kielessä on selvä tuki käännösaikaisille algoritmeille.
C++11:n constexpr-ominaisuuden avulla tämä esimerkkikoodi olisi paljon lyhyempi. Kannattaa tutustua siihen, kunhan saa käsiinsä tarpeeksi uuden kääntäjän, joka tukee sitä.
Myöhempään Weggon kommenttiin lisäisin, että joissakin kielissä käännösaikanakin voi suorittaa ihan mielivaltaisia koodia siten, että koko kieli on käytössä ilman rajoituksia. Sellaisen ominaisuuden sisältävät kielet taitavat kuitenkin olla aika harvinaisia ja eksoottisia.
Pekka Karjalainen kirjoitti:
C++11:n constexpr-ominaisuuden avulla tämä esimerkkikoodi olisi paljon lyhyempi.
Kyse on käännösaikaisen koodin tuottamisen esittelystä, ei laskujen laskemisesta käännösaikana.