Programmer som data (Autumn 2019)

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.

Kurset giver 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.

Learning activities

Forelæsninger og øvelser. Forelæsningerne giver et teoretisk fundament ved at gennemgå centrale begreber, teknikker og eksempler. Det forventes, at de studerende har læst den tekst, som forelæsningen bygger på, således at en god dialog kan gennemføres. De obligatoriske afleveringsopgaver skal sikre en aktiv forståelse af begreber og teknikker. Dette sikres gennem et mix af små og lidt større kodeopgaver samt mindre skriftlige besvarelser. Kurset anvender ikke større projektopgaver. Alle opgaver forventes besvaret i grupper af to.

Mandatory activities

I dette kursus skal de studerende gennemføre obligatoriske aktiviteter, som skal opfyldes for at blive indstillet til eksamen og evt. for at kunne aflevere skriftlig arbejde til eksamen.

Antal: Der stilles 10 ugeopgaver med en værdi af 2 point hver. En total af 20 points kan opnås. Du skal have 14 point for at gå til eksamen.

Hvornår: 1 opgave hver uge.

Deadlines: 1 uge per opgave.

Genaflevering: Det er muligt at genaflevere inden 2 uger efter første deadline. Det tager i snit en uge at rette en opgave, så der er op til en uge til at forbedre opgaven.

Dato for aflevering af obligatoriske opgaver vil fremgå af kursets side på LearnIT.

Den studerende får karakteren NA (ikke godkendt) ved den ordinære eksamen, hvis de obligatoriske aktiviteter ikke er godkendt, og den studerende bruger et eksamensforsøg.

Course literature

The course literature is published in the course page in LearnIT.

Ordinary exam

Exam type:
C: Submission of written work, external (7-trinsskala)
Exam variation:
C: Submission of written work

Time and date