Programmer som data (Autumn 2024)

Abstract

Kursets formål er at give en dybere praktisk og teoretisk forståelse for implementation af programmeringssprog, herunder især maskinmodellen bag Java, C# og F#. Kursusemnerne omfatter leksikalsk analyse, grammatikker, syntaksanalyse, abstrakt syntaks, stakmaskiner, virtuelle maskiner, mellemkodesprog (inklusive JVM og .NET CLI), og continuations. Endvidere implementering af fortolkere, typeinferens, oversættere for en delmængde af C og for en delmængde af SML, garbage collectors, og kodegenerering for virtuelle maskiner og maskinkode (fx x86).

Description

Kursets formål er at give en dybere praktisk og teoretisk forståelse for implementation af programmeringssprog og dermed fundamentet for mange essentielle værktøjer som anvendes til software udvikling.

Emner: 

• Leksikalsk analyse, regulære udtryk, endelige tilstandsmaskiner, ikke-deterministiske og deterministiske tilstandsmaskiner, lexer-generatorer. 
  
• Syntaksanalyse, top-ned versus bund-op, LL versus LR, parser-generatorer. 
  
• Stakmaskiner, evaluering af udtryk, Postscript, mellemkode for en simpel stakmaskine. 
  
• Oversættelse af en delmængde af C (*p, &x, pointer-aritmetik, arrays, arr[i]) til stakmaskinkode. 
  
• Typetjek, typeinferens, statisk typede sprog, dynamisk typede sprog. 
  
• Maskinmodellen bag Java, C#, F# (stak, hob, spildopsamling), og oversættelse fra kildetekst til stakmaskinkode. 
  
• Mellemkodesprogene i Java Virtual Machine og Common Language Infrastructure (.NET, Mono), og deres implementation med generering af registermaskinkode på køretid. 
  
• Spildopsamlingsteknikker (garbage collection). 
  
• Funktionsprogrammering med F#, abstrakt syntaks som konkret syntaks. 
  
• Continuations, exceptions, og en fortolker for en delmængde af Icon. 

Formal prerequisites

Betydelig programmeringserfaring og solid beherskelse af Java og C#, samt kendskab til F# eller Standard ML. Erfaring med programmers tids- og pladsforbrug. Det er en fordel sideløbende at følge kurset Operativsystemer og C.

Intended learning outcomes

Efter kurset skal den studerende være i stand til:

• Analysere og forklare tidsforbrug og pladsforbrug for et program skrevet i Java, C#, C og et dynamisk programmeringssprog, baseret på en forståelse af hvordan sprogene er implementeret, herunder hvilken rolle lageradministration og spildopsamling spiller; og kunne bruge denne forståelse til at vurdere fordele og ulemper ved at anvende en given sprogkonstruktion i en given situation (fx objekttype versus værditype i C#).
• Benytte værktøjer til effektiv genkendelse af regulære udtryk, til leksikalsk analyse og til syntaksanalyse; kunne forklare begrænsningerne i disse værktøjer med brug af relevante teoretiske begreber; samt kunne vælge de mest relevante værktøjer til løsning af en foreliggende genkendelsesopgave.
• Designe repræsentationer af abstrakt syntaks for et givet problem, i et funktionelt såvel som et objektorienteret sprog; kunne benytte værktøjer til at opbygge abstrakt syntaks ud fra tekstuelle inddata; og kunne benytte rekursion til analyse og transformation af abstrakt syntaks, for eksempel typeanalyse, oversættelse, eller reduktion af logiske eller aritmetiske udtryk.
• Sammenligne udtrykskraft og effektivitet for forskellige programmeringssprog (især Java, C#, C og dynamisk typede sprog), og forklare hvordan deres egenskaber følger af designbeslutninger og implementationsteknikker bag sprogene.
• Vise hvordan et program både kan anskues som aktiv skaber af dynamisk opførsel (programkørsler) og som passive data der kan analyseres, transformeres eller genereres af andre programmer.
• Kunne forklare hvordan et givet nyt programmeringssprog forholder sig til kendte sprog.

Ordinary exam