soodan sivut

Rust? AoC?

Jos Rust-ohjelmointikieli ei ole tuttu, niin siitä voi ottaa selkoa vaikka FAQ:sta tai muista dokkareista. Muinaista C-kieltä saa naputella töissä ihan riittämiin, joissain harrastehommissa tulee tunksuteltua C++:aa ja vaikka C++ vaan kasvaa ja kasvaa vähän mukavammaksi käyttää, sen C-legacy ei ole menossa mihinkään. Rust osuu sellaiseen itseä kiinnostavaan systeemiohjelmointikenttään, sillä kaikki tulkattavat kielet ovat sotkua, roskienkeruu on pelleille, dynaaminen tyypitys saa mistä tahansa isommasta softakokonaisuudesta lukukelvotonta ja niin edelleen. En kuitenkaan ole koskaan täysin tosissani.

Visualisaatio erään tehtävän algoritmin kulusta

Uuden opettelu on aina kuin lapsuuteen palaisi ja tärkeääkin jotta pysyisi tekniikassa kärryillä eikä ainakaan moderni webbidevaus innosta ollenkaan, ennemmin natiivikoodi siellä matalimmalla abstraktiotasolla ja kaikki missä tarttee hervottomasti perffiä, kuten tietokonegrafiikka.

Jotkut aukovat jouluna päätä, jotkut kalentereita, ja jotkut vielä popsivat sieltä suklaata. Advent of Code on sarja ohjelmointipähkinöitä joulukalenterin muodossa, jo vuodesta 2015. Puljasin ekat Pythonilla. 2016 sekä tänä vuonna rustasin Rustilla jotta noista helpoista tehtävistä oppisikin jotain.

Kisakoodaaminen ei välttämättä ole paras tapa opetella mitään ohjelmointikieltä, mutta tässä tapauksessa se lienee parempi tapa kuin olla koodaamatta lainkaan. Viime vuoden tehtävistä en muista paljon mitään, mutta käydään pieni katsaus tämänvuotisiin. Inputinlukeminen on copypastesaastaa, joka tehtävä oli niin pieni että skippasin Cargon ja koodi kääntyy rustc:llä manuaalisesti. Muutamalle piti antaa mm. -L $juttu/regex/target/release/deps kun parsi inputtia regex-cratella, jne. Inputinparsiminen on mahdotonta unwrap()-sotkua, koska kiinnosti vain keskittyä varsinaisen pulmadatan pyörittelyyn.

Omat ratkaisut löytyvät githubissa olevasta reposta. Pidemmittä puheitta katsotaanpa missä tehtävissä tuli opittua epsilonia enemmän. Vertaan välillä C++:aan, koska sitä sentään osaan ja sekin on semmoinen monimutkainen "lightweight abstraction language". Siellä sun täällä on varmaan pieniä vinoja tyyliseikkoja, jotka Clippyllä vielä myöhemmin korjailen harjoitukseksi. Näistä siis EI kuulu ottaa mallia. Kunhan auon päätäni ääneen itsekseni, sillä sen lisäksi että siten vaikuttaa kylähullulta, se oikeasti viisastaa.

1, iteraattoreilla alkuun

Jo ykköstehtävällä ("Inverse Captcha") voidaan vähän lämmitellä Rustin maukasta iteraattorisyntaksia. Ykköstehtävässä piti ratkaista "captcha", eli etsiä inputista (pitkä rivi numeroita) numeroparien summa. Inputti on syklinen, eli viimeinen ja ensimmäinen lasketaan peräkkäisiksi. Pari on kaksi samaa peräkkäin. 1122 sisältää parit 11 ja 22, kuten myös 1221. Koodia:

fn solve(input: &str, offset: usize) -> u32 {
    let a = input.chars();
    let b = input.chars().cycle().skip(offset);
    a.zip(b).map(
        |(i, j)| if i == j { i as u32 - '0' as u32 } else { 0 }).sum()
}

fn solve_a(input: &str) -> u32 {
    solve(input, 1)
}

fn solve_b(input: &str) -> u32 {
    solve(input, input.len() / 2)
}

B-kohdassa kunkin numeron pari löytyy ei suinkaan vierestä vaan kulkemalla puolimatkaa eteenpäin. Siksi solve() ottaa offsetin. Koodi käy läpi parit inputista siten, että toista on vähän shiftattu ja tämä toinen myös on syklinen, ettei loppuisi kesken. Mitä pareille tehdään onkin sitten selkeästi tuossa closuressa.

Nähdään, että nämä iteraattorien temppuoperaatiothan ovat ihan kuin jostain Pythonista (jota myös osaan), vaikka ohjelma käännetään, stringireferenssi on melkein kuin pointteri ja tyyppien kanssa ollaan tarkkana, enemmän kuten vaikka C++:ssa. Oikeastihan Rust ei ole mikään C++ on steroids, vaan se on saanut vaikutteita hirmu monesta kielestä. No, tästä lähin haluan kikkailla kaiken iteraattoreilla raakojen forlooppien sijaan ihan kikkailun vuoksi, jotta sen kikkailun oppisi kunnolla.

4, stringi.sort() ei käy

Nelostehtävä ("High-Entropy Passphrases") oli naurettavan simppeli, mutta siinä tuli vastaan ärsyttävä ominaisuus siitä, että vaikka stringi on tavallaan vektori merkkejä, sen sisältöä ei voi järjestää sellaisenaan koska se ei oikeasti ole vektori merkkejä eikä sitä mm. voi random-accessoida. Pitää kerätä merkit vektoriin, sortata, ja pyöräyttää vektorista stringi. Tämä käy onneksi helposti.

let sort_chars = |&s: &&str| -> String {
    let mut cs = s.chars().collect::<Vec<_>>();
    cs.sort();
    String::from_iter(cs.iter())
};

6, mukavat kokoelmat

Nelosessa sai luoda jo joukkoja eli set-tietorakenteita, vaikkakin vain simppeliin duplikaattien poistoon. Kutosessakin ("Memory Reallocation") kannatti käyttää ja no, aika helppoa importata use std::collections::HashSet ja sitten suunnilleen arvata miten setistä luetaan ja miten sinne lisätään alkioita. Korjataan vaan triviaalit käännösvirheet kun kääntäjä näyttää yllättävän selvästi, että hei, tuossa kohdassa tarvitaan referenssi eikä kokonaista objektia. Täähän on hauskaa.

7, jotain tyyppicoerciojuttujako

Seiskassa ("Recursive Circus") kirjoitin, että ns.children.iter().map(|name| *indices.get(name).unwrap()).collect() ja kääntäjä älähti, että hei, the trait `std::borrow::Borrow<std::string::String>` is not implemented for `&str`. En muista pitikö edes googlata, että tähän varmaan tarvitaan jostain syystä *indices.get::<str>(name) kun name taitaa olla String, indices-hashmappini kaipaa &str:ää, ja kääntäjä ei arvannut sopivaa muotoa get:stä niin piti pakottaa. En ees välittänyt vaan jatkoin menemään.

10, slicen mutatointi

Kympissä ("Knot Hash") annettiin vähän kummalliset taustaselitykset, jotka sitten sivuutettiin antamalla täsmälliset askeleet eräänlaisen "hash-algoritmin" ajamiseen. Yksi osa tästä sisälsi listan mahdollisesti syklisen alilistan alkioiden järjestyksen kääntämisen, ja funktionimi cycled_rev tiivistääkin homman suomenkielistä löpinää paremmin. (Vähän vaikuttaa siltä, että tuohon löytyisi jokin nätti analyyttinen ratkaisu tämän häröalgoritmin pyörittelyyn, mutta tein silti eksplisiittisesti sen kummemmin miettimättä.)

let (data, mirror) = buf.split_at_mut(data_len);
// cycle back to front, if any. wrap_part_len can be 0
data[0..wrap_part_len].copy_from_slice(&mirror[0..wrap_part_len]);
// update the end part of mirror
mirror[pos..pos + unwrap_part_len].copy_from_slice(&data[pos..pos + unwrap_part_len]);

Tuli vastaan ja taitaa tulla lisääkin vastaan se hauskuus, että Rustissahan ei saa pitää mihinkään yhtä useampaa "mutablea borrowta". Indeksikikkailun välttämiseksi kaksi ei-päällekkäistä osaa slicestä saadaan split_at_mut-funktiolla siten, että kääntäjä vielä on samaa mieltä siitä, että eihän noilla kahdella, joita nyt voi muokata samaan aikaan, pääse muokkaamaan mitään samaa. Taas on turvallista, mutta tässä haisee siltä, että perinteisen perffikkään taulukkomutatointikikkailun kanssa saattaa osua joskus ongelmiin. Taulukkoindeksointikin olisi hidasta ilman kikkailuja, kun jokainen accessi sisältää rajatarkistukset. Siis aina iteraattoreita?

14, closure-mut-mitähäh

Numero neljätoista ("Disk Defragmentation") käytti taas kympistä tuttuja "knot hasheja". Neljässätoista ilmeni jännittävä sudenkuoppa. On ruudukko kooltaan 128 kanttiinsa, ja testataan mille koordinaateille löytyy eräs ominaisuus. Testaamisella on sivuvaikutuksia ja se mutatoi erästä tietorakennetta. Loopataan läpi indeksit y:ltä, luodaan jokaiselle iteraattori joka suoltaa x-y-pareja, ja suodatetaan nämä:

let mut test_pos = |x, y| test_mark_cell(&map, &mut visited, x, y);
(0i32..128)
    .flat_map(|y| (0i32..128).map(move |x| (x, y)))
    .map(|(x, y)| test_pos(x, y))
    .filter(|&found| found)
    .count()

Funktio flat_map siis ottaa funktion (tässä closure) joka tuottaa listan, ja "avaa" listan yhden kerran. Joo, voisin yhdistää mapin ja filterin. Ylläoleva vastaa jotakuinkin tätä, joka oli aiemmin:

(0i32..128)
    .map(|y| (0i32..128)
         .map(|x| test_pos(x, y))
         .filter(|&found| found).count()
        ).sum()

Tehdään y-listan kunkin alkion sisään x-lista, katsotaan mitkä koordinaatit sopivat, lasketaan ne yhteen, ja lopulta summataan y-listasta tullut lista riveille mätsänneistä koordinaattilukumääristä. Tämä on vähän kömpelöä. Yritin flat_mapata jotakuinkin noin:

(0i32..128)
    .flat_map(|y| (0i32..128).map(|x| test_pos(x, y)))
    .filter(|&found| found)
    .count()

Noh, lifetime of `test_pos` is too short to guarantee its contents can be safely reborrowed ja `y` does not live long enough.

Muuttuja y siirtyy referenssinä tuolle sisemmälle closurelle vaikka siitä haluttaisiin tehdä kopio. Kokeillaan päästä eroon tästä vaivasta movettamalla, vähän kikkailemalla koska muutoin kääntäjä ulisee että closure ottaisi nuo mapit ja visitedit ympäristöstään ja olisi FnOnce:

let mut test_row = |y| {
    let v = &mut visited; // move a ref, not the whole visited (and y)
    let m = ↦ // similarly
    (0i32..128).map(move |x| test_mark_cell(m, v, x, y))
};
(0i32..128)
    .flat_map(test_row)
    .filter(|&found| found)
    .count()

Tässä nähdään sitten lifetimeongelma vähän tarkemmin. En vaan tajunnut virheilmoista yhtään mitään: cannot infer an appropriate lifetime for borrow expression due to conflicting requirements, missä borrow expression on &mut visited. Sitten jotain siitä, että tuon test_row-closuren pitää päästä visitediin käsiksi, eikä lifetime voi elää pidempään kuin closuren body. Konflikti tuli siitä, että lifetimen pitäisi myös olla validi count()-kutsun ajan note: ...so that a type/lifetime parameter is in scope here, missä here on se count()-kutsu. Jos ajan pelkästään filteriin asti ja otan countin pois, niin saan viimeisen noten tilalle ilahduttavan huomion, että:

note: ...so type `std::iter::Filter<std::iter::FlatMap<std::ops::Range<i32>,
std::iter::Map<std::ops::Range<i32>, [closure@14.rs:154:25: 154:60
m:&std::vec::Vec<(u64, u64)>, v:&mut [(u64, u64); 128], y:i32]>,
[closure@14.rs:151:24: 155:6 visited:&mut [(u64, u64); 128],
map:&std::vec::Vec<(u64, u64)>]>, [closure@14.rs:158:17: 158:31]>` of expression
is valid during the expression

Marvelous. No niin, nyt alkaa näyttää jo C++-kääntäjän templatemössöltä. Oi kun kotoisa olo. Se "type/lifetime parameter" lienee joku lifetime jonka kääntäjä tökkäsi tuonne johonkin väliin puolestani. Aika hienosti kyllä nuo kutsujen paluuarvojen tyypit ketjuttuvat. Tälläiset se kääntäjä varmaan optimoi oikein hienosti näkymättömiin ja iteraattoriloopeista tulee kuin käsin auki kirjoitettu innerlooppi. Tai sitten ei. Ei saa koskaan tietää. Tälläisissä tapauksissa se "lightweight" sanonnassa "lightweight abstraction language" tarkoittaa, että "joo joo kyllä se optimoituu kevyeksi, jos vaan kääntäjä sattuu tietämään mitä halusit".

No. Kuten irkissä (#rust-beginners) stephaneyfx selitti, ja niinkuin käy jälkiviisaasti tavallaan järkeenkin: test_row ei voi olla FnMut ja samalla jakaa muille noita mut-referenssejä visitediin, nääs tuo map-objekti joka sieltä laiskasti lähtee ulos sisältää closuren kontekstin, jossa se mut-reffi on. Ei voida taata, etteikö joku kutsuisi tätä test_rowia useampaan kertaan, saaden sieltä sitten rinnakkaisia mutable-reffejä, mikä on kiellettyä. Jos jotenkin voitaisiin taata, että flat_map pitäisi vain yhden paluuarvon closuresta hengissä kerrallaan, kaikki olisi tavallaan kunnossa, mutta minkäs teet.

Se ensiksi esitelty lopullinen muoto mihin päädyin joka flat_mappaa koordinaatit ja filtteröi sitten koordinaattiparit on joka tapauksessa siistimpi. Löytyi kumminkin pienoinen valaistuminen näistä Rustin omistajuustempuista.

Vissiinkin tässä tapahtuisi flat_mapin implementaatiodetskujen ansiosta niin, että ulommaisen rangen flatmappiobjekti tuottaisi sisältään closuren antamia mappiobjekteja laiskasti niin, että lopulta visitediin olisi useampi mutable borrow mikä ei tietenkään sovi. Nykyiselläänhän flat_map vaatii FnMut-funktion, jota kutsuu per iteraatio saadakseen iteraattorin, jonka tuottamat asiat flat_map lätkäisee peräjälkeen sen sijaan että saataisiin lista näistä iteraattoreista tai niiden tuottamista listoista. Vaikka flat_map olisi implementoitu esim. siten, että se ottaisi funktion joka tuottaisi uuden funktion (joka voisi olla FnOnce), ongelma silti säilyisi, sillä tuosta ulommasta funktiosta voisi ottaa taas ulos useamman funktion, joista kukin pitäisi tuota mut-reffiä...

Eikö ole jännittävää? Tämä osoittautui suunnilleen kiinnostavimmaksi opetukseksi tämänvuotisen kalenterin aikana.

15, iteraattorihauskaa

Päivä viisitoista ("Dueling Generators") sitten oli lyhyt eikä millään lailla vaikea. Silti täytyy pasteta sieltäkin koodia:

fn picky_matches_in_pairs(a0: u64, b0: u64, num: usize) -> usize {
    let a_gen = (0..).scan(a0, |a, _| { *a = *a * 16807 % 2147483647; Some(*a) })
        .filter(|a| a & 3 == 0);
    let b_gen = (0..).scan(b0, |b, _| { *b = *b * 48271 % 2147483647; Some(*b) })
        .filter(|b| b & 7 == 0);
    a_gen.zip(b_gen).take(num).filter(|&(a, b)| a & 0xffff == b & 0xffff).count()
}

fn main() {
    assert!(picky_matches_in_pairs(65, 8921, 5*1000*1000) == 309);

Tehtävässä oli kaksi tuollaista satunnaislukugeneraattoria, ja tehtävän kakkososassa A vielä päästää läpi vain neljällä jaolliset numerot, ja B kahdeksalla jaolliset. Iteraattorikikkailu ei tässä ole mitään luettavinta mahdollista (nuo kannattaisi ehkä jakaa osiin) mutta sen tekeminen oli hauskaa. Funktio siis hakee indeksejä, joilla generaattorien lukujen alimmat 16 bittiä ovat samat.

18, oi summatyypit

Päivän 18 tehtävä ("Duet") meni jo niin nätisti miten nätisti Rustilla voi mitään mennä. Tarina kertoo, että tässä täytyy koodata virtuaalimasiina, joka pyörittelee rekistereitä ympäriinsä, looppaa hyppykäskyillä, ja muka soittaa ääntä (ja kakkososassa oikesti kommunikoi toiselle). Viime vuonna oli joku melko lailla vastaava virtuaalimasiinatehtävä. Rustin summatyyppi-enumit ne vasta ovat poikaa ja match eli näppärämpi patternmatchaava switch-case pääsevät loistamaan:

type Reg = usize;
type Val = i64;

// some instructions can take either a register or an immediate value
#[derive(Debug)]
enum Arg {
    RegisterArg(Reg),
    ValueArg(Val)
}
use Arg::*;

#[derive(Debug)]
enum Instruction {
    Snd(Arg),
    Set(Reg, Arg),
    Add(Reg, Arg),
    Mul(Reg, Arg),
    Mod(Reg, Arg),
    Rcv(Reg),
    Jgz(Arg, Arg)
}
use Instruction::*;

fn execute_sound(machine: &mut SoundMachine, program: &[Instruction]) {
    match program[machine.pc] {
        Snd(RegisterArg(snd)) =>
            machine.last_snd = machine.regs[snd],
        Snd(ValueArg(snd)) =>
            machine.last_snd = snd,
        Set(dst, RegisterArg(src)) =>
            machine.regs[dst] = machine.regs[src],

        // (some content deleted for brevity)

        Rcv(reg) =>
            if machine.regs[reg] != 0 { machine.last_rcv = machine.last_snd },
        Jgz(ref cmp, ref off) => {
            let cmp = match *cmp {
                RegisterArg(reg) => machine.regs[reg],
                ValueArg(arg) => arg
            };
            let off = match *off {
                RegisterArg(reg) => machine.regs[reg],
                ValueArg(arg) => arg
            };
            if cmp > 0 {
                machine.pc = (machine.pc as Val + off) as usize;
                return;
            }
        }
    }

    machine.pc += 1;
}

Ai että. Nautin tästä. Ei muuta sanottavaa.

21, kunnon traitteja

Päivänä 21 ("Fractal Art") jäin melkein kaipaamaan C++:n templatemössöä. Siinä missä C++ perii C:n makrotunkin ja suunnilleen korvaa sen templateilla (kaikki kunnon C++-tyypit ovat sitä mieltä, että makroja tulee välttää henkeen ja vereen), Rustissa on sekä paljon C-makroja hienompi makrojärjestelmä että paljon C++-templateja rajoittuneempi vähän vastaava trait-mekanismi, joka ei itseasiassa vastaa templateja toiminnallisuudeltaan muuten kuin että sen perusteella voidaan kyllä generoida koodia.

Rustista ei löydy esim. perintää lainkaan, mutta se korvataan muilla käsitteillä, jossa traitit myös auttavat. Tässä on adventtikalenterin ainoa kohta, jossa jotain perinnän kaltaista meinasin kaivata, kunnes havaitsin että tarvitsen vain rajapinnan. Senkin havaitsin vasta jouluaaton jälkeen kun siivosin copypastesotkua.

Nyt mennään jo liian pitkälle, eli sitä koodia jo. Tehtävässä pyöriteltiin kahden, kolmen ja neljän yksikön kokoisia neliöitä dataa, joista kannatti tehdä geneerinen neliökalikkatyyppi:

pub trait Block: std::marker::Sized + PartialEq + Eq + Copy + Clone {
    const N: usize;
    type T;
    fn new() -> Self;
    fn row_mut(&mut self, i: usize) -> &mut [u8];
    fn row(&self, i: usize) -> &[u8];
    fn from_canvas(src: &[u8], x: usize, y: usize) -> Self { ... }
    fn parse(src: &[u8]) -> Self { ... }
    fn to_canvas(&self, dst: &mut [u8], x: usize, y: usize) { ... }
    fn transform<F>(&self, f: F) -> Self
        where F: Fn(usize, usize) -> (usize, usize) { ... }
    fn flip(&self) -> Self { ... }
    fn rotleft(&self) -> Self { ... }
    fn rotright(&self) -> Self { ... }
    fn rot180(&self) -> Self { ... }
}

Mennään mutkan kautta vrt. C++-templatet. Tässä on nyt käsitteellinen "yläluokka" eli rajapinta sellaiselle neliökalikalle. Traiteilla tehdään rajapintoja, joille voi olla defaultti-implementaatio (kohdissa "..." on oikeasti koodia, jätin pois). Rust-traititkin merkitään kolmiosuluilla, mutta ei anneta sen hämätä. C++-templateparametriksi saisi vakioluvun eli kalikan dimensiot (tässä N), mutta Rustissa sinne menee vain traitti. Eteenpäin, ja luodaan tähän traittiin sopivat struktityypit:

macro_rules! implement_block {
    ($name:ident, $n: expr) => {
#[derive(Debug, PartialEq, Eq, Copy, Clone)]
        pub struct $name([[u8; $n]; $n]);
        impl Block for $name {
            const N: usize = $n;
            type T = $name;
            fn new() -> Self { $name([[0; $n]; $n]) }
            fn row_mut(&mut self, i: usize) -> &mut [u8] { &mut self.0[i] }
            fn row(&self, i: usize) -> &[u8] { &self.0[i] }
        }
    };
}

implement_block!(Block2, 2);
implement_block!(Block3, 3);
implement_block!(Block4, 4);

Hyi makropurkkaa. Ja joku asiantuntija varmaan näkee selvästi että menen vähän metsään. Tästä tulee Block2, Block3 ja Block4 -tyypit, joilla on 2x2, 3x3 ja 4x4 taulukot u8-dataa. Kun taulukon koko eroaa enkä saanut pohjatraittiin puljattua edes näitä rivi-indeksointeja ([N; L] ei ole std::ops::Index), täytyi myös tuo kolmen funktion rajapinta yleisempään koodiin täyttää. Myös tuo const N on tässä joku ei edes montaa kuukautta vanha Rust-feature. C++-analogiani tähän olisi about noin:

typedef Block<2> Block2;
typedef Block<3> Block3;
typedef Block<4> Block4;

missä Block olisi luokka, joka suunnilleen vastaisi tuota ylläolevaa traittia. Ennen makropurkan tarkempaa selittelyä katsotaanpa miten tätä Block-traittia käytettäisiin. Koodissa on myöhemmin paljon temppuisampaakin käyttöä missä traittiparametrit menevät sikin sokin, mutta aloitetaan helposta:

pub fn apply_upscale<Src, Dst>(src: &Src, from: &Src, to: &Dst) -> Option<Dst>
where Src: Block, Dst: Block {
    if *src == *from
        || src.rotleft() == *from
        || src.rotright() == *from
        || src.rot180() == *from
        || src.flip() == *from
        || src.flip().rotleft() == *from
        || src.flip().rotright() == *from
        || src.flip().rot180() == *from {
        Some(to.clone())
    } else {
        None
    }
}

Tässä vaiheessa aloin miettimään jälkiviisaampana, että mitäs tapahtuikaan ja minkäslaisissa konteksteissa C++:ssa templatejuttuja kutsuttiinkaan traiteiksi. (Mietin myös, että ehkä näitä voisi suosiolla kopioida viittailun sijaan, kun ovat pieniä objekteja.) Joku tälläinen signature voisi toimia nätimmin, ehkä, en tiiä:

pub fn apply_upscale<Src, Dst>(src: &Block<Src>, from: &Block<Src>, to: &Block<Dst>)
-> Option<Block<Dst>>
where Src: BlockTrait, Dst: BlockTrait

missä tuo BlockTrait speksaisi lähinnä neliön dimensiot ja ehkä sisältäisi jotain muuta teknisten rajoitteiden vuoksi (vaikka fn new() -> Self; kun en saanut taulukkotyyppiä yleistettyä). C++:ssa nuo menisivät samassa järjestyksessä about näin (kuvitellaan, että joku vastaava Option löytyy):

template <class SrcBlock, class DstBlock>
Option<DstBlock> apply_upscale(SrcBlock &src, SrcBlock &from, DstBlock &to)

template <class Src, class Dst>
Option<Block<Dst>> apply_upscale(Block<Src> &src, Block<Src> &from, Block<Dst> &to)

Tai ajattelinkohan oikeasti jotain tälläistä:

template <class Src, class Dst>
Option<Dst::Block> apply_upscale(Src::Block &src, Src::Block &from, Dst::Block &to)

Meni jo pää solmuun. Nyt alkaa muistua mieleen, että joo, näähän täsmäävät joissain keisseissä C++:n tyyppitraitteihin, jotka siis ovat tietynlaisia "metatyyppejä", rajapintoja templatemetaohjelmointiin: niillä speksataan, mitä ominaisuuksia joltain tyypiltä löytyy koskematta siihen tyyppiin suoraan. Esimerkiksi siitä mitä tarkoitan käy vaikka char_traits.

Makrosotkulle optimaalisin muoto olisi vain sellainen, että implement_block! speksaisi vain luvun N ja ehkä sen taulukkotyypin jos [[u8; N]; N] ei geneerisöidy. En kuitenkaan saanut tätä pyöriteltyä.

Se sikin sokin -kohta muuten on tämä:

fn enhance_grid_cells<E>(canvas: &Vec<u8>, rules: &[Rule]) -> Vec<u8>
where E: Expansion {
    let w = (canvas.len() as f64).sqrt().ceil() as usize;
    let newsz = w / E::From::N * E::To::N;

    let mut ret = vec![b'?'; newsz * newsz];

    for gridy in 0..(w / E::From::N) {
        for gridx in 0..(w / E::From::N) {
            let original = E::From::from_canvas(canvas, E::From::N * gridx, E::From::N * gridy);
            // why no inference? expand(&original, rules) doesn't compile
            let enhanced = expand::<E>(&original, rules);
            enhanced.to_canvas(&mut ret, E::To::N * gridx, E::To::N * gridy);
        }
    }

    ret
}

Tässä Expansion on tuollainen välitraitti joka kertoo mistä koosta mihin kokoon tätä fraktaalia csi-suurennetaan. E::From ja E::To ovat esimerkiksi Block2 ja Block3, vaikka kävisi myös joku välitempputyyppi josta saataisiin Block<E::From> ja Block<E::To> kuten yllä selitelty, tai jopa BlockTraits<E::From>::Type jos keulii ilman päätä.

Palataan maan pinnalle. Rustin tapa pitää traitit pelkkinä interfaceina vaikuttaa hyvältä ihan yleisesti tämän tehtävän ulkopuoleltakin. Stroustruppikin on sitä mieltä, että rajapinnat voisivat olla pureja. Toisaalta vähän tekisi mieli keulia lisää traittien kanssa tässä, ja tästäkin Stroustrup varoittaa:

Be careful about the complexity of the templates you write or use; it is easy to get overenthusiastic and write template code that is too clever to be useful as maintainable production code.

24, geneerinen graafialgo

Jouluaaton pähkinässä ("Electromagnetic Moat") järjesteltiin dominopaloja ja optimijärjestyksen hakemisesta tulee verkko-ongelma. Dominopalan (tehtävässä "magneettisia komponentteja" eri voimakkuuksilla) päästä pitää aina siirtyä toiseen päähän ennen toiseen palikkaan menemistä, mikä tekee verkon solmuista epätavallisia. Joka tapauksessa päivän ekassa osassa tehtävänä oli hakea suurin voimakkuus jonka dominopaloista saa järjestettyä, ja toisessa osassa pisin ketju siten, että tasapelin tullessa voimakkain voittaa. Paloista (inputissani 57 kpl) muodostuu sen verran hassu verkko, että optimiratkaisun voi bruteforce-hakea läpi vaikka yleisessä tapauksessa olisi hirmuisen hankalaa.

Hakualgoritmi on molemmissa osissa samanlainen, ja vain polun paremmuuskriteeri eroaa. Kun koodini ensin esilaskee naapurustotiedon taulukkoon, itse rekursiivinen syvyyshakufunktio on "templatoitu" niin, että se ottaa sisäänsä jonkun score-funktion. Funktio toteuttaa sellaisen traitin, että se ottaa komponentin ja palauttaa jonkin score-tyypin. Scoretyypit pitää pystyä panemaan järjestykseen, sekä niitä täytyy voida lisätä toisiinsa niin, että summan tyyppi on tämä sama score.

Ekan osan voimakkuusmittafunktio on vain:

let strength_score = |c: &Component| c.a + c.b;

Nuo c.a ja c.b ovat "dominopalikan" eri puolien "voimakkuudet" (kokonaislukuja). Kakkostehtävässä hakusyvyys on pääkriteeri, eli jokaisesta komponentista tulee yksi score-mitta lisää. Koska tasapelit ratkaistaan silti voimakkuusmitalla, käytetään kokonaisscorena paria:

#[derive(Debug, Eq, PartialEq, Ord, PartialOrd)]
struct LengthStrength(usize, usize);

Näin hakufunktioksi tulee:

let longest_plus_strength_score = |c: &Component| LengthStrength(1, c.a + c.b);

Summaus täytyi tuolle parille määritellä itse, mikä on aika verbosea mutta tutun C++:n puolella näyttäisi vähintään yhtä kurjalta:

impl Add for LengthStrength {
    type Output = Self;
    fn add(self, other: Self) -> Self {
        LengthStrength(self.0 + other.0, self.1 + other.1)
    }
}

Varsinainen hakurekursio on sitten tälläinen, kun closure-funktioni ei suostunut kopioitumaan eli menee referenssinä:

fn dfs_level<Score, ScoreFn>(strewn: &[Component], ci: usize, in_port_a: bool,
                             conns: &[(ConnsList, ConnsList)],
                             visited: &mut [bool], score: &ScoreFn) -> Option<Score>
where Score: Ord + Add<Output = Score>, ScoreFn: Fn(&Component) -> Score {

Lopuksi

Tässähän on korkeintaan joitain satoja rivejä koodia tai pari tuhatta ja 25 erillistä ohjelmaa; kunnon ison softan puljaus vasta kunnolla mittaa ohjelmointikieltä. Tästä pääsee kumminkin alkuun. Ja kieli on joillekin vain työkalu jne, kunnon ohjelmoija puhuu mitä kieltä vaan ja keskittyy ongelmanratkaisuun. No, kunnon uteliaana insinörttinä minua(kin) vaivaa pahasti se Feynmanin esittelemä tauti työkalun kun työkalun kanssa. Pakkohan sitä on tutkia ja tunkata ja pakkohan sillä on leikkiä. Ja oikeastikin eri skillien osaaminen on tärkeää.

Kaikki parsiminen ja varsinkin regexien puljaaminen näyttää selvästi, miten monella lailla homma voi mennä pieleen. Voi kurjaa. Tästä Rustissa sinänsä tykkäänkin, kun joku muu kieli voisi vaikka vaan segfaultata tai tarjota hankalampia virheenkäsittelymenetelmiä; Rustissa mietitään jo väkisin ennemmin kuin myöhemmin, että mitä tehdään kun epäonnistuu. Floattien kanssa vasta onkin ärsyttävää mutta siitä voi olla kumpaakin mieltä. Redditissä sanottiin hyvin:

The thing is, after programming rust for a while, if I go back to another language I'm terrified of floats, because I know that it never really worked there the language just doesn't throw the problems in your face.

The absolute 100% killer best feature of rust for me is lack of UB

No, mitä enemmän töissä tarkistelee C:n speksiä UB:n varalta, sitä enemmän puntti tutisee ("ai tässäkin voi oikeasti käydä miten vaan") ja alkaa kiinnostaa Rustin opettelu enemmän, koska nimenomaan niihin tiettyihin tilanteisiin kieli vaikuttaisi tarjoavan apua.

Rustin safety-hommat jne ovat toki mainioita, mutta ne toimivat kulissien takana. Toisaalta aina kun Rustiin koskee niin hetken päästä töissä kerneliä C:llä tunksutellessa tulee vaan paha olo ja pakokauhu jos pitää suunnitella mitään monimutkaisempaa. Data raceja kaikkialla. KAIKKIALLA. Mitä vanhemmaksi tulee, sitä varmemmalta tuntuu että lähestulkoon kaikki maailman koodi toimii vähän niinkuin vahingossa, ja onneksi corner caseja ei vaan yleensä tapahdu. Rinnakkaisuuteen liittyviin juttuihin ei tarvinnut vielä näissä kalenterikoodeissa koskea, mikä on vähän harmi, sillä niiden tärkeydestä huomautellaan joka suunnasta. Kuitenkin ihan yhtä paljon ilahduttaa ihan syntaksin pienet asiat, joilla tehdään koodaamisesta vähän hauskempaa, ja vähän * paljon = paljon.

Esimerkiksi kaiken patternmatchausihanuuden kuten if let x:n tärkeyttä ei voi painottaa liiaksi. Olkoon an_option joku Option<Foo> ja sit:

if let Some(bar) = an_option {
    // yes, matched! bar is inside an_option
} else {
    // an_option is a None
}

Tai kuten tuolla ylhäällä päivälle 18, program on slice ("lainattu vakiokokotaulukko") Instruction-enumeja:

match program[machine.pc] {
    Snd(RegisterArg(snd)) =>
    ...

aw yiss mitä destructurointia. On näitä muissakin kielissä, mutta nyt on tässäkin ja tässä on muutakin kivaa.

Rust päättelee tyypit itse (type inference) aina kun voi. Siinä on sitten sama vaara kuin C++:n auto-keywordissa että kääntäjä kyllä tietää mitä tyyppejä kulkee mutta koodia lukeva ohjelmoija ei, eli välillä käytän mielelläni redundanttejakin tyyppiannotaatioita. Funktioiden parametreihin ja paluuarvoihin tyypit täytyy laittaa, ja jos tekee tarpeeksi pieniä funktioita, niin ne ovat helposti riittävä määrä tyyppejä, jotta koodi pysyy luettavana.

Väitin jo ylempänä, että iteraattoreita on maukasta käyttää. Vaatii toki vähän totuttelua riippuen mihin kieleen on tottunut, että oisko eksplisiittinen for-looppi kumminkin intuitiivisempi, mut löytyy ne iteraattorit ja vastaavia algoja C++:stakin, joita tätä nykyä voi jopa epäironisesti käyttää kun C++11 toi lambdat. Kun tehtävänä on muuntaa dataa toisen näköiseksi, map-filter-kikkailu on omasta mielestä nätimpää. Joku minimin, maksimin tai tietyn elementin etsiminenkin on jo kömpelöä perusforrailulla. Tässä toki käy helposti hätäilemään, että optimoiko se kääntäjä tuota nyt millään lailla järkevästi, näkikö abstraktiokerrosten lävitse.

Kun kotona harrastekoodaan, niin tutustun jatkossa Rustiin.