Kategoriarkiv: Datalogi

Backus og Chomsky

backus-syntax
Udsnit af den artikel, hvor Backus første gang foreslår en udgave af det, vi i dag kalder kontekstfrie grammatikker.

Når man skal beskrive syntaksen af programmeringssprog, bruger man normalt kontekstfrie grammatikker. Denne model skyldes John Backus, der var datalog og matematiker og ansat som forsker ved IBM, og Noam Chomsky, der var (og er) teoretisk lingvist ved MIT. Backus’ indsigt blev brugt til at beskrive syntaksen af ALGOL 60 – og skal jeg nævne en tredje person i denne forbindelse, må det være Peter Naur, der var redaktør på ALGOL 60-rapporten.

Det er interessant at Backus og Chomsky får deres ideer samtidig, nemlig i første halvdel af 1950’erne. I lærebøger om formel sprogteori har jeg aldrig set nævnt om Backus var inspireret af Chomsky – eller omvendt (omend jeg ikke kan lade være at bemærke, at Chomskys teori om syntaks er langt mere generel). De to mænd er endda født i samme by i USA, nemlig Philadelphia, med fire års mellemrum. Om de nogensinde nåede at møde hinanden, ved jeg ikke.

Af en artikel af Stephen Wolfram fremgår det at de to amerikanere får deres ideer uafhængigt af hinanden.

På den anden side står der dette i en nekrolog fra 2007:

Among his library at the time were the works of the modern philosopher and theorist Noam Chomsky, who studied the evolution of the human intellect and of written and spoken language in parallel. Chomsky was developing a symbolic syntax with which to frame his concepts of languages within languages, in the study of how sociology affects grammar. Backus borrowed some of Chomsky’s concepts, including the idea that a symbology could represent a computer language…even one that didn’t yet exist.

Men Backus sagde selv (ifølge et citat fra bogen Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists)

There’s a strange confusion here. I swore that the idea for studying syntax came from Emil Post because I had taken a course with Martin Davis at the Lamb Estate… So I thought if you want to describe something, just do what Post did. Martin Davis me he did not teach the course until long afterward… So I don’t know how to account for it. I didn’t know anything about Chomsky. I was a very ignorant person.

Martin Davis mener at Richard Goldberg, der arbejdede sammen med John Backus på Fortran-projektet og oprindelig var filosof fra Harvard, kan have omtalt Chomskys arbejde for Backus. Så hvor meget Backus kendte til Chomskys arbejde, får vi aldrig at vide nu.

Men her er det faktisk interessant, at de kontekstfrie grammatikker første gang blev foreslået i det 4. århundrede før vor tidsregning af den indiske matematiker Pāṇini (al lighed med italiensk bagværk er tilfældig). Pāṇini var interesseret i at forstå strukturen af sanskrit, som er det sprog, man dengang talte i hans del af Indien og som hinduismens hellige skrifter er forfattet på. Om Backus eller Chomsky kendte hans arbejde, ved jeg ikke.

flattr this!

På H.C. Andersens slot

foto 1

foto2

foto 5-1

I dag har jeg været i København for endnu engang at præsentere mit science slam fra april i år – den lille historie med flyttekassen om Mars Climate Orbiter, britiske pundsekunder og antallet af linjer i Dostojevskijs Idioten.

I sin tid blev jeg inviteret af Det Obelske Familiefond, som står bag en masse store donationer. Jeg spurgte om jeg kunne rejse på 1. klasse med tog, og det kunne jeg.

Denne eftermiddag i H.C. Andersen Slottet i Tivoli i København blev kaldt en inspirationsdag og den skulle promovere fonden i København. Hele maskineriet var kørt i stilling. Der var en stor delegation fra Aalborg til stede; bl.a. dekanerne Eskild Holm Nielsen fra tek-nat, Hanne Katrine Krogstrup fra samf og rektor himself var der.

Stéphanie Surrugue fra TV2 var konferencier – hun havde faktisk set min science slam-video på YouTube og sagde at hun syntes godt om den. Så dét.

Inspirationsdagens helt store fokus  var på sundhedsvæsenet. Vi fik to oplæg om nye erfaringer med telemedicin, men også sundhedsminister Nick Hækkerup var der; han talte om det psykiatriske behandlingssystem. Hans pointe var ikke specielt politisk, men faktisk vigtig – at der er nogle meget uheldige tabuer om psykisk sygdom, som ikke findes om fysisk sygdom, og at det stadig er udbredt at tænke på psykisk sygdom som noget kronisk. Nu håber jeg bare han vil leve op til den fine hensigt i sin politik over for psykiatrien.

Der var en (nok lige lovlig lang) præsentation af Tivoli-garden, og så kom nogle af garderne selv og spillede. Efter kun 170 år vil dette københavnske musikkorps for børn nu gøre noget hidtil uhørt – de vil optage piger (!!), og begrundelsen er ikke ligestilling, men at der i vore dage simpelthen er flest piger, der spiller de instrumenter som indgår i Tivoligarden. Og nej, det var ikke satire.

Det mest interessante indslag var dog dagens sidste, en beretning fra Frank Mugisha fra menneskerettighedsorganisationen SMUG, der kæmper for LGBT-rettigheder i Uganda. Frank Mugisha er en meget modig mand i et land hvor homofobien er en stor og konkret trussel mod bøsser, lesbiske og trans- og interkønnede; hans ven og kollega David Kato blev myrdet men Frank tog over efter David. Som Frank sagde: Jeg har ingen bodyguards til at passe på mig; det der beskytter nu er at jeg er en offentlig person der hele tiden er i medierne. Sammen med Frank var Helle Jacobsen fra Amnestys sekretariat; det var også et godt gensyn – vi var begge ret overraskede over at møde hinanden netop ved denne lejlighed. Jeg har gennem snart en del år haft et godt samarbejde med Helle i forbindelse med vores kampagnearbejde i Amnesty Aalborg. SMUG har fået 3 millioner kroner til sit arbejde af Obel, og det er rigtig godt for denne vigtige kamp for menneskerettigheder. Og i en sidebemærkning fik jeg at vide at Frank Mugisha faktisk er blandt de 17 mennesker, der er på shortlist til Nobels Fredspris!

Hvordan gik mit eget indslag egentlig? Jeg tror såmænd det gik som det skulle; der var da nogle der lo undervejs på passende steder. På tirsdag holder jeg det for fjerde og sidste gang, denne gang for Ungdommens Naturvidenskabelige Forening (hvis der kun kommer én tilhører ligesom sidst, er det godt at det ikke er ny-forberedt).

Stephania Surrugue stillede undervejs et par spørgsmål til alle, der havde et indslag, og mig spurgte hun om hvorfor det dog nu var nødvendigt for forskere at bruge humor i formidlingen, sådan som vi ender med at gøre i science slam. Min egen forklaring er at forskning – og ikke mindst naturvidenskabelig forskning – er fyldt med paradokser og overraskelser, og dette er da også virkemidlerne i god humor.  Afstanden er ikke så stor, som nogen tror. Og derudover er der ikke nogen modsætning mellem at være seriøs og at anvende humor.

flattr this!

Bevisets stilling

Et godt bevis skal kunne overbevise andre.
Et godt bevis skal kunne overbevise andre.

Når jeg underviser, skal de studerende lave opgaver, hvor de skal udføre matematiske ræsonnementer. For de allerfleste er det første gang, de selv skal prøve at konstruere og skrive et matematisk bevis, og de allerfleste er meget usikre på hvordan man gør. Er det, vi har skrevet, godt nok? spørger de mig. Faktisk rører de ved noget helt centralt, nemlig hvad et matematisk bevis er og hvilken rolle det har.

Leslie Lamport skriver i sin artikel How To Write A 21st Century Proof om hvordan man kan lave bedre matematiske beviser. Han skelner mellem beviser i det 21. århundrede og beviser i stilen fra det 17. århundrede, hvor sidstnævnte beviser simpelthen er “prosa med  formler”.  Lamports påstand er dels at mange matematiske beviser stadig lever i det 17. århundrede, dels at der er mange ukorrekte beviser i den matematiske litteratur.

Formodentlig har han ret i begge påstande. Der er masser af beviser i artikler og bøger, som er sværere at forstå end de burde være. Typisk har beviserne en uklar struktur. Jeg har selv begået sådanne beviser, og min fornemmelse er at vi skriver rodede beviser fordi vi først og fremmest skriver beviserne til os selv.

Når vi bevæger os uden for den del af matematisk logik, der hedder bevisteori (et område, jeg selv har haft en del kontakt med, men ikke kan påstå at kende godt), er der ikke nogen klare kriterier for hvad et korrekt bevis egentlig er.

Et klart og samtidig uformelt krav er at et matematisk bevis skal overbevise læseren. Netop derfor må beviset ikke være “privat”; amatører udi matematikken har gennem årene forsøgt at løse åbne problemer, og deres “beviser” har altid overbevist dem selv – og oftest kun dem selv.

Derfor siger jeg ofte til de studerende, der spørger mig, at et godt bevis er et, der kan læses og accepteres af en anden. Denne anden  kan enten være en anden studerende eller den studerende selv, der genlæser beviset på et senere tidspunkt.

Men jeg prøver også at gøre det klart for studerende, at et bevis ikke er “magi”. Mange tror at et bevis er udtryk for en særlig og genial indsigt. Sådan er det selvfølgelig af og til, men  i mange områder af teoretisk datalogi, som studerende møder, kan beviserne udformes ud fra en meget præcis opskrift. Dette gælder f.eks. for beviser for uafgørbarhed ved reduktion. Og uanset hvad: De fleste (måske alle) matematiske beviser kan gives en klar struktur. Når man skal kontrollere gyldigheden af et bevis, består arbejdet typisk i at undersøge om dets struktur er fornuftig.

Så måske skal vi gøre særlig meget for at få dette næste-algoritmiske aspekt af matematiske beviser gjort klart for de studerende, vi underviser.

Lamport og mange andre – her specielt Per Martin-Löf og traditionen fra intuitionistisk typeteori – har hver især og sammen arbejdet på at finde en måde at konstruere og strukturere beviser, således at det også kan tjekkes automatisk om et bevis er gyldigt. Vi må kunne lade os inspirere af alle disse gode anstrengelser i vores undervisning, også selv om vi måske ikke bruger Lamports TLA+-system eller bevisassistenter som Coq eller Isabelle.

flattr this!

Nedslag i datalogiens idéhistorie

I går aftes holdt jeg et foredrag i Ungdommens Naturvidenskabelige Forening om ACMs A.M. Turing Award, også kendt som Turing-prisen. Ud over arrangørgruppen kom der desværre kun én tilhører. Det er træls at have brugt en hel del tid på at forberede et foredrag, som næsten ingen mennesker gider høre. I håbet om at der er mere end én derude, der har lyst til se hvad jeg har lavet, får I her mine slides at se.

flattr this!

Hamming it up?

Richard Hamming

For tiden bruger jeg tid på at forberede et foredrag om Turing-prisen, officielt kaldet The A.M. Turing Award. Turing-prisen uddeles af ACM og er derfor en datalogi-pris, der måske bedst svarer til Nobelpriserne eller til Fields-medaljen. Men igennem tiden har mange af modtagerne af Turing-prisen været matematikere – også dette års modtager Leslie Lamport er oprindelig matematiker. Det samme gælder selvfølgelig for Alan Turing selv. På denne måde er historien om Turing på én gang et kongerække-agtigt bud på datalogiens historie og et strejftog i en bestemt del af den anvendte matematiks nyere historie.

En af de mere farverige modtagere af Turing-prisen er Richard W. Hamming, der er grundlæggeren af teorien om fejlkorrigende koder og derved i høj grad også en vigtig bidragyder til det 20. århundredes matematik. På det seneste har jeg hæftet mig ved Hammings opfattelse af faget matematik. Han stod for en meget anvendelsesorienteret tilgang til matematik, men han var samtidig velbevandret i det sædvanlige aksiomatiske grundlag.

En berømt udtalelse fra Hamming er hans retoriske spørgsmål om forskellen på Lebesgue-integralet og Riemann-integralet egentlig har nogen fysisk betydning, specielt da om det ville betyde noget for om et fly ville kunne lette eller ej. For hvis dét var tilfældet, ville han ikke ud at flyve i sådan et fly!

Og på et tidspunkt besluttede han sig for at indstille sin forskerkarriere for at koncentrere sig om undervisning. I denne periode af sit liv skrev han en del bøger, og de var præget af hans forsøg på et opgør med den præsentation, mange af os er vokset op med – den stil, der hedder definition/sætning/bevis/eksempel. I min gymnasietid var det endnu denne stil, der dominerede matematikundervisningen – mange på min alder husker Kristensen og Rindungs bøger, der reelt havde definition/sætning/bevis/eksempel som fast disposition. Senere kom der nogle såkaldt “alternative fremstillinger”, der prøvede at få den matematiske proces ind, men på nogle måder bare var en kunstigt sødet udgave af Kristensen og Rindung.

Hamming skriver et sted:

  1. We live in an age of exponential growth in knowledge, and it is increasingly futile to teach only polished theorems and proofs. We must abandon the guided tour through the art gallery of mathematics, and instead teach how to create the mathematics we need. In my opinion, there is no long-term practical alternative.
  2. The way mathematics is currently taught it is exceedingly dull. In the calculus book we are currently using on my campus, I found no single problem whose answer I felt the student would care about! The problems in the text have the dignity of solving a crossword puzzle – hard to be sure, but the result is of no significance in life. Probability and statistics have easily understood problems whose results are surprising, important and interesting in themselves.

Som en del andre mennesker endte Hamming med at være “for meget” for nogle mennesker – lidt på samme måde som en kursusholder i matematikkens didaktik, jeg havde for mange år siden; også han havde nogle interessante ideer om matematikundervisning (og en Hamming-agtig, omend noget mere elementær tvivl på nytten ved trappefunktions-definitionen af integration), men endte med at være en lidt isoleret størrelse på grund af sin fremfærd.

En af hans kolleger fra Bell Labs sagde om Hamming:

He is very hard to work with,…because he does a lot of broadcasting and not a lot of listening.

Men her vil jeg hæfte mig ved det meget mere positive: Hamming er en tidlig fortaler for en opdagende tilgang til matematikundervisning, hvor hovedvægten er på hvordan metoderne i matematik anvendes til at konstruere begreber og bevise resultater. Sagt med nyere begreber er Hamming fortaler for at præsentere context of discovery snarere end context of justification. Jeg har nu fået fat i hans elementære lærebog Methods of Mathematics, og den er et spændende bekendtskab. Jeg får den muligvis kætterske tanke, at nogen burde oversætte dele af Hammings bog til dansk og forsøgsvis prøve dem af i gymnasieregi.

flattr this!

På vej hjem

IMG_3661.JPG

I skrivende stund er jeg på vej hjem fra Rom. Jeg nåede lige akkurat at få første session med til hovedkonferencen CONCUR og at få frokost og en sidste ladning italiensk is; og nå ja, jeg fik da også omsider hilst på Helle Hvid Hansen, der er en af de danskere inden for teoretisk datalogi, der har haft hele sin akademiske løbebane uden for landets grænser.

Derefter gik det ellers hjemover.

Det er spændende at være til akademiske konferencer. Samtidig må jeg også erkende at jeg altid har syntes at det også er mere end almindeligt mentalt udmattende.

Der er foredrag to timer i træk, og mod slutningen af sådan en session er det ofte svært at holde sig koncentreret. Og vi ved alle godt at det mest spændende næsten altid sker i pauserne.

Og så er der også det med publikationskravet. I datalogi (men ikke i fysik eller matematik) er konferencer gået hen og blevet den vigtigste publikationskilde – vigtigere end tidsskrifter. Vi sender ind til konferencer for at præsentere færdigt arbejde uden knaster. Derfor bliver mange konferencepræsentationer og –artikler meget polerede.

Jeg talte med en af mine britiske kolleger om muligheden for at finde et andet format, der måske kan fremme diskussionslysten – alt for ofte er det som om de gode, afsøgende diskussioner skal standses af hensyn til tidsplanen. Gad vide om vi skulle give konferencer en anden status og gøre dem mere “afsøgende”?

flattr this!

Søndag i en romersk kælder

IMG_3647.JPG
I dag var det tid til møde i forskernetværket BETTY nede i kælderen til Grand Hotel Palatino. Vi begyndte kl. 9 og skulle efter planen slutte kl. 17. Fordi jeg var ordstyrer i den første session, var jeg meget opmærksom på at ingen skulle gå over tiden; og da den sidste foredragsholder var med at være færdig – og det var faktisk mig selv – kunne jeg til min store undren konstatere at vi, selv med de spørgsmål, der kom fra salen, var færdig et kvarter tidligere end planlagt. En anden gang vil jeg måske ikke være så striks.

Senere begyndte folk at tage sig bedre tid. Det suverænt længste foredrag var desværre også det mindst interessante – næsten en hel time blev brugt på at foreslå at vi skulle bruge vore teorier på at analysere den software, der bliver brugt til omstilling af telefonforbindelser. Det var meget velment, men det hele kunne være overstået på måske et kvarter. Et andet foredrag tegnede anderledes interessant, men jeg blev bekymret da jeg så at der var 111 slides i præsentationen (!!) – heldigvis var det kun nogle ganske få, der blev gennemgået.

Til sidst var det desværre lykkedes os at gå over tiden og slutte noget senere end 17.00. Når man har siddet og lyttet vældig længe. begynder tankerne desværre at vandre de forkerte steder hen.

Når man er sammen med kolleger fra mange lande, hvor mange af dem bor i et andet land end deres oprindelsesland, kommer man også tit til at snakke om netop dét i pauserne. En af mine italienske kolleger fra Danmark er for nylig flyttet fra København til Odense, hvor han er blevet ansat på Syddansk Universitet. Det har hjulpet ham til at blive meget bedre til dansk, sagde han (og det passer!), for på Fyn er man ikke så nøjeregnende med om udlændinge altid udtaler alle ord helt korrekt – forklarede han mig på dansk.

flattr this!

Tilbage til Rom

foto

I dag er jeg tilbage i Rom; i morgen skal jeg deltage i et heldagsmøde i forskernetværket BETTY og på mandag er jeg med til workshoppen BEAT. Den første udgave af BEAT var også i Rom i januar 2013 (og jeg var formand for programkomiteen) men dengang sneede jeg inde i München på vej herned. Endnu et godt argument for at holde den slags i de varme måneder af året; hernede er der 30 grader.

Jeg har genset nogle af de steder, jeg så med familien på vores sommerferie hernede i sidste måned, og især gjorde det et stort indtryk på mig at gense Pantheons store kuppel. Der blev også tid til penne all’arrabbiata og en stor portion italiensk is lige i nærheden; denne del af Rom med de snævre gader og små restauranter er måske meget turistpræget, men stadig et besøg værd.

Bagefter tog jeg tilbage til hotellet for at mødes med to af mine kolleger, som besøgte mig i Aalborg for en lille måneds tid siden. Endnu engang opdagede jeg noget velkendt: Dels at det godt at gense mine kolleger fra udlandet, dels at man forbløffende hurtigt kan glemme hvad man havde skrevet. Det tog mig mere end en time at blive i stand til at forklare hvad der egentlig var hovedtankerne i de grundige forstadier til et manuskript, jeg havde skrevet på dengang.

Jeg er i det hele taget glad for at møde mine kolleger fra rundt om i Europa, der har beslægtede forskningsinteresser. Ellers kan jeg tit føle mig isoleret midt i den selvindeholdte begejstring, der findes for bestemte andre emner i gruppen på mit institut. Hvis der sprang en bombe på mit kontor, ville der ikke længere være nogen i Aalborg, der interesserede sig for behavioural types (“adfærdstyper” lyder for meget som psykologi).

På tirsdag begynder CONCUR-konferencen, som er årsagen til at BETTY og BEAT er at finde i Rom i år. Men der begynder jo også et nyt semester i den nye uge, og jeg har hverken tid eller råd til at være væk fra Aalborg så længe. Så på tirsdag rejser jeg hjem igen til nye udfordringer – det bliver også spændende at komme i gang med at undervise igen.

flattr this!

Universitetets stenalder og guldalder

I dag var jeg blevet indbudt til at holde et lille oplæg ved et møde på Institut for matematiske fag. Lige nu oplever matematikuddannelserne på Aalborg Universitet en stor tilstrømning af studerende. Da jeg selv var studerende der, var årgangene små – da der to efter mig startede et hold på næsten 30 studerende, talte man meget om den store tilstrømning. En af dem var forresten Søren Højsgaard, som i dag er institutleder på matematik. Men i år er der optaget tæt på 90 studerende på uddannelserne i matematik, matematik-økonomi og matematik-teknik. Dét er rigtig mange.

På Institut for datalogi er det nogle år siden, vi selv oplevede at få store hold af studerende (og i år bliver der optaget 252 studerende i alt på de uddannelser, vi tager os af – det er mere end en fordobling siden 2009), og matematikerne ville gerne høre mit bud på hvad vi oplevede og om der mon var nogle erfaringer, de kunne lære af.

Ovenfor kan I se de slides, jeg havde med.

Det blev en rigtig god mulighed for mig til at tænke tilbage på alle de forandringer, vi har oplevet i de seneste 30 år. Mange af ændringerne skyldes alt det, masseuniversitetet har ført med sig, men noget andet skyldes også at vi er blevet mere og mere lukket om os selv – det hænger selvfølgelig også til dels sammen med at institutterne nu skal være pseudo-selvforvaltende. Men ikke kun. Der er også tale om en regulær mentalitetsændring hos alle involverede, og årsagerne til den er mange og komplicerede at afdække.

Vi fik en god diskussion af de udfordringer, også Institut for matematiske fag nu står over for, og interessant nok endte jeg endnu engang med at snakke om flipped classroom. Det var et emne, der fik tankerne og spørgsmålene frem. Endnu engang fik jeg røbet at det tager meget mere end 10 minutter at producere 10 minutters undervisningsvideo – men først i dag lykkedes det mig at forklare hvorfor det er sådan. Analogen er den velredigerede tekst: det tager meget mere end 10 minutter at skrive en god tekst, som kan læses med udbytte på 10 minutter.

flattr this!

Fra gymnasiet til universitetet

For to år siden begyndte dumpeprocenterne at vokse alarmerende i nogle af fagene på vores bacheloruddannelser i datalogi og software. Gad vide om der er tale om en sammenhæng mellem hvordan de studerende klarer sig i disse fag? Gad vide om der er tale om studerende, der har klaret sig dårligt i gymnasiet?

På institutmødet i dag præsenterede jeg de resultater, vi har fundet. Undersøgelsen har jeg foretaget sammen med Mikkel Meyer Andersen fra Institut for matematiske fag. Mikkel stod for det store arbejde med at lave selve dataanalyserne, og han har også datalogi som sit andet fag og kender derfor også noget til den uddannelse, undersøgelsen omhandler.

Karaktergennemsnittet er signifikant lavere hvis man har et matematikgennemsnit fra gymnasiet under 4. Karaktergennemsnittet hos dem, der udebliver fra en eller flere eksaminer i disse fag er signifikant lavere og risikoen for at dumpe i et eller flere af de fire fag er signifikant højere.

Resultaterne affødte en del kommentarer fra mine kolleger. Det skortede især ikke på hurtige løsningsforslag. Nogle foreslog at matematikkurserne på første studieår skulle laves om. Nogle foreslog at der skulle være særlige sommerkurser. Andre spekulerede på om sammenhængen mon var af generel natur eller kun gjaldt for de fire kurser, vi her havde fat i.

Diskussionen afslørede dog også noget andet: Vi, der underviser på universitet, ved simpelthen alt for lidt om matematikpensum på ungdomsuddannelserne.

Det eneste, vi kan se, er at der er en korrelation mellem matematikkaraktererne fra  ungdomsuddannelserne og nogle bestemte fag på universitetet. Men det er også vigtigt i sig selv.

Jeg tør ikke pege på nogen enkel løsning, for først skal vi forstå årsagerne meget bedre. Selv vil jeg foreslå to tiltag.

  • For det første at vi laver yderligere undersøgelser for at se om problemet også forekommer for andre fag end de fire fag, vi har undersøgt.
  • For det andet at vi laver nogle kvalitative interviews, der kan afdække de studerendes motivation for at studere på de datalogiske uddannelser.

 

flattr this!