JohnnyBigert.se
 startsida    |     om mig    |     tjänster    |     gratis C++-tips    |     forskning    |     kontakt     ||   blogg
Smarta
C++-tips
 
 
Behöver ni experthjälp
inom C++?
 
 

Läsvärt om datalogi

Här hittar du intressanta onlineartiklar inom datalogi. Det finns massor av bra läsning på nätet, och artiklarna här gav iallafall mig en aha-upplevelse.

Det nyaste tipsen hittar du i min blogg Developer's Dilemma. Jag är alltid på jakt efter bra läsning, så har du en artikel att rekommendera eller känner till en sida med samma tema, hör av dig!

Artiklar:

9. Bok: Pattern-oriented software analysis, del 1

Pattern-oriented software analysis - A system of patterns (bok av av F. Buschmann m.fl., 1996, ISBN 0-471-95869-7, 476 sidor) tar upp en hel del designmönster som man inte sett i "Design Patterns" av Gamma m.fl. (även arkitekturella mönster och idiom). Några exempel: Model-View-Controller, Presentation-Abstraction-Control, Layers, Blackboard, Reflection och Microkernel. Läs kort introduktion till dessa mönster här.

Pattern-oriented software analyis

Varje kapitel kunde ha varit hälften så långt. Bortser man från det så finns det mycket bra information att hämta. Rekommenderas till: mjukvaruarkitekter (obligatorisk läsning). Omdöme: bra.

(28 december 2009)

8. Bok: The new Turing omnibus

The new Turing omnibus (bok av A.K. Dewdney, 1993, ISBN 0805071660, 480 sidor) är 66 korta kaptitel som beskriver det mesta i gränslandet datalogi/matematik (dvs en hel del Turing, NP, algoritmer, datorgrafik, logik osv.). Mina favoritkapitel:

The new Turing omnibus
  • Kapitel 8: Vad är slump? Om du får en binär sträng av mig, kan du avgöra hur mycket slump det är i den? Kan du skriva ett kort dataprogram som matar ut strängen?
  • Kapitel 19: Skapa en 3D-modell från bara linjer. Används i datorseende.
  • Kapitel 33: Kan man lösa svåra datalogiska problem snabbare med en "analog dator" (t.ex. av okokt spaghetti, spikar, gummisnoddar, plexiglas och sånt)? Kan man visa att P=NP mha såpbubblor?
  • Kapitel 61: Om du vill hitta en sträng i ett dokument, kan du göra det utan att titta på varje bokstav i dokumentet? Strängsökning i sub-linjär tid (originalartikel)?

Jag tycker boken är skriven på ett lättillgängligt sätt och ger en intressant överblick. Rekommenderas till: de som gillar datalogi/matematik. Omdöme: ganska bra.

(4 oktober 2009)


7. Modellbaserad testning

Modellbaserad testning (model-based testing) är ett intressant sätt att automatisera urvalet av testfall. En modell (t.ex. en tillståndsmaskin) beskriver det externa beteendet hos din mjukvara. Ett program väljer sedan vägar genom din tillståndsmaskin och täcker den enligt några kriterier. Dessa kriterier kan t.ex. vara att "testningen är klar när man besökt alla tillstånd och alla tillståndsövergångar minst en gång".

Harry Robinson på Google ger en omfattande presentation av modellbaserad testning (156 slides!). Han visar även exempel på buggar man hittat (i Windows klocka) och buggar man inte kan hitta med modellbaserad testning. Se presentationen här: http://model.based.testing.googlepages.com/starwest-2006-mbt-tutorial.pdf

(4 oktober 2009)

6. Double-checked locking är inte trådsäker

Double-checked locking är en optimeringsteknik för att minimera trådlåsning när låsning bara borde behövas en gång. Detta är användbart för t.ex. initialiseringskod som bara behöver köras en gång.

Scott Meyers and Andrei Alexandrescu, två av de stora namnen inom C++, förklarar varför double-checked locking inte går att göra trådsäker i t.ex. C++! För mig var detta en överaskning, eftersom många fortfarande använder denna teknik. Läs artikeln här: http://www.aristeia.com/Papers/DDJ_Jul_Aug_2004_revised.pdf

(4 oktober 2009)

5. Spelprogrammering

En vanlig vanföreställning om spelprogrammering verkar vara att optimering är allt och att man därför måste vara bra på att skriva assemblerkod. Därför var det uppfriskande att hitta denna PowerPoint-presentation.

Presentationen beskriver utvecklingen av spelmotorn Unreal som används i spelet Gears of War. Det handlar om att bygga komplexa system under svåra realtidskrav. Tiotusentals objekt kan vara aktiva samtidigt och interagera med varandra. Allt medan bilden uppdateras 60 gånger per sekund!

Författaren beskriver hur sunda programmeringsprinciper och produktivitet är lika viktiga som prestanda. Två bra citat är "We will gladly sacrifice 10% of our performance for 10% higher productivity" och "We never use assembly language".

För att få bättre produktivitet föreslår han en ny typ av språk med stora influenser av Haskell (som är ett funktionellt språk). Språket ska t.ex. kunna uttrycka: "Detta är en funktion som tar en vektor med n element och en vektor med index som är mindre än n." Man kan därmed fånga upp felaktiga vektoråtkomster som står för de flesta runtimefelen. Läs mer på http://www.cs.princeton.edu/~dpw/popl/06/Tim-POPL.ppt

(13 augusti 2009)

4. Inputs of death

Artikel om ett riktigt coolt verktyg som matar ut konkreta indata som kraschar ditt program. Med statisk kodanalys letar programmet efter instruktioner som stoppar programkörningen, såsom division med noll och avreferering av null-pekare.

De har kört verktyget på öppen källkod för att visa att det skalar. Några exempel är filtreringen av IP-paket i FreeBSD- och Linux-kärnan, flera filsystem och koden för reguljära uttryck i Apache och PHP. De verkar hitta fel i de flesta system. Ett exempel på skadligt indata var det reguljära uttrycket

[^[\0^\0]\*-?]{\0

Nu är det förstås inte antalet vinkelparenteser som är intressant, utan att utmatningen är så väldigt exakt. "Precis detta ska du mata in för att krascha ditt program" är budskapet.

Min fråga efter att ha läst artkeln är: När blir detta något man kan köpa eller ladda ner? Den enda nackdelen jag ser är namnet på verktyget: EXE. Hur googlar man på något sådant?! :) Läs detaljerna här: http://www.stanford.edu/~engler/exe-ccs-06.pdf

(18 juli 2009)

3. SICP som föreläsning på video

"Structure and interpretation of computer programs" (av Abelson och Sussman, förkortad SICP) är en klassisk datalogibok. På datalinjen på KTH lika fruktad som hyllad. SICP beskriver många intressanta datalogiska koncept såsom rekursion, lambda calculus, beräkningsströmmar och den metacirkulära evaluatorn. Programspråket som används är Scheme, som är ett funktionell programspråk (en Lisp-dialekt, så det blir många parenteser :). Jag tror att alla som läser SICP (och orkar med alla parenteser) kommer att se på programmering med nya ögon.

För dig som skulle vilja läsa SICP men inte ids finns det hopp. Följ länken så kan du se hela bokens innehåll som videoinspelade föreläsningar (ca 20 timmar)!
http://groups.csail.mit.edu/mac/classes/6.001/abelson-sussman-lectures/

(18 juli 2009)

2. Enkelt men avslöjande programmeringstest

Intressant test av fallenhet för programmering för studenter som aldrig programmerat: Testet bestod av 30 frågor som går ut på att svara på vad a och b har för värden efter några tilldelningar såsom

a = 20; b = 10; a = b;

Man berättade dock aldrig för studenterna vad '=' betyder!

Eftersom man inte gav några instruktioner hade olika elever olika tolkning av '=', t.ex. att 'a = b' betyder att a byter värde till a + b. De som var konsekventa genom alla frågorna (dvs de som hela tiden använde samma tolkning av '=') visade sig senare ha bäst resultat på programmeringskurserna! De som var inkonsekventa eller inte lämnade några svar hade genomgående dåliga resultat på programmeringskurserna. Slutsatsen blir att det är bra att ha ett systematiskt tänkande när man programmerar.

Systematiska fel är lätta att rätta till. Jämför t.ex. skytte: om alla dina skott sitter inom en femkrona uppe i högra hörnet kan du ju alltid sikta mera nedåt och vänster. Det är dock oklart om detta test fungerar på en erfaren programmerare, eller vad motsvarigheten skulle vara. Vad skulle du säga om du fick 30 st tilldelningar som anställningsprov? :) Läs allt om testet på http://www.cs.mdx.ac.uk/research/PhDArea/saeed/paper1.pdf

(17 juli 2009)

1. Analogi mellan Garbage collection och Transactional memory

Huvudobservationen i denna artikel är att "Transactional memory (TM) is to shared-memory concurrency as garbage collection (GC) is to memory management." Artikeln tar ett stort antal påståenden om GC, byter ut ord som har med minneshantering att göra mot ord som handlar om parallellism och hittar slående likheter.

Den mest intressanta delen är vad man kan förutspå om framtiden hos TM genom att titta på vad GC gått igenom. Till exempel trodde de flesta att man måste ha hårdvarustöd för att implementera GC. Många tror nu att samma sak gäller för TM... Läs hela analogin på http://www.cs.washington.edu/homes/djg/papers/analogy_oopsla07.pdf

(14 juli 2009)

Intresserad av att förbättra dig som programmerare?

 
© Johnny Bigert Data | De la Gardies gränd 22, 135 63 Tyresö | 076-782 74 00
johnny@johnnybigert.se | www.johnnybigert.se