Samenvatting Concepten van programmeertalen

-
ISBN-10 9491465996 ISBN-13 9789491465994
772 Flashcards en notities
17 Studenten
  • Deze samenvatting

  • +380.000 andere samenvattingen

  • Een unieke studietool

  • Een oefentool voor deze samenvatting

  • Studiecoaching met filmpjes

Onthoud sneller, leer beter. Wetenschappelijk bewezen.

Dit is de samenvatting van het boek "Concepten van programmeertalen". De auteur(s) van het boek is/zijn M Witsiers Voglet Arnold van der Leer Maria Wienbröker Kampermann. Het ISBN van dit boek is 9789491465994 of 9491465996. Deze samenvatting is geschreven door studenten die effectief studeren met de studietool van Study Smart With Chris.

PREMIUM samenvattingen zijn gecontroleerd op kwaliteit en speciaal geselecteerd om je leerdoelen nog sneller te kunnen bereiken!

Samenvatting - Concepten van programmeertalen

  • 1 Waarden en typen

  • Cardinaliteit (van een verzameling of type S)

    Aantal elementen van S.

    In het tekstboek genoteerd als #S.

    [T2.2]

  • Geef een beschrijving van het begrip waarde
    Een waarde is elke entiteit die tijdens een berekening kan ontstaan
  • Cartesisch product (van twee verzamelingen)

    Verzameling van geordende paren, waarbij het eerste element van elk paar uit de eerste verzameling komt en het tweede element uit de tweede verzameling.

    [C1.3.1]

  • Geef een beschrijving van het begrip type
    Een type is een verzameling van waarden met bijbehorende operaties
  • Conditionele expressie

    Expressie die meer deelexpressies bevat, waarvan er - afhankelijk van de uitkomst van een of meer voorwaarden - slechts één berekend wordt en waarvan het resultaat tevens de waarde van de hele expressie vormt.

    [T2.6.4]

  • Geef een beschrijving van het begrip statische typering
    Bij statische typering heeft elke variabele en daarmee elke expressie een vast type dat zonder het programma uit te voeren gecontroleerd kan worden (gedeclareerde type)
  • Construction

    Expressie die uit componentwaarden een samengestelde waarde maakt.

    Ook: constructie, aggregate.

    [T2.6.2]

     

  • Geef een beschrijving van het begrip samengesteld type
    Een samengesteld type is een type waarvan de waarden samengesteld zijn, zoals bijvoorbeeld tuples, structures, records, arrays, algabraric types, discriminated records, objects, unions, strings, trees, ists, etc.
  • Discreet type

    Type waarvan de waarden een 1-op-1-relatie hebben met (een deelverzameling van) de verzameling gehele getallen.

    [T.2.2.3]

  • In welke 4 structureringsconcepten kunnen we samengestelde typen onderverdelen?
    - cartesisch product (tupels en records
    - mappings (arrays)
    - disjoint unions (algabraic types, discriminated records en objects)
    - recursive types(trees, lists)
  • Discriminated record

    Implementatie van disjuncte vereniging in talen als Pascal en Ada.

    Ook: discriminant.

    [T2.3.3]

  • Geef een beschrijving van het begrip dynamische typering
    Bij dynamische typering kan het type van de variabele gedurende de uitvoering van het programma veranderen (actuele type). Typecontrole vindt plaats tijdens de verwerking. Bijvoorbeeld in Javascript a="tekst", a=10.
  • Disjuncte vereniging (van twee verzamelingen)

    Verzameling waarden waarin elke waarde óf uit de ene óf uit de andere verzameling is gekozen en waarin elke waarde voorzien is van een tag (discriminant), die aangeeft uit welke verzameling de waarde is gekozen.

    Ook: disjoint union

    [T2.3.3]

  • Geef een beschrijving van het begrip standaard type
    De types die standaard in een programmeertaal aanwezig zijn
  • Dynamische typering

    Mechanisme waarbij alleen de waarden (en dus niet de variabelen) vaste typen bezitten en waarbij de typecontrole plaatsvindt tijdens de verwerking van het programma.

    [T2.5.1]

  • Geef en beschrijving van het begrip discreet type
    Bij een discreet primitief type hebben de waarden een 1 op 1 relatie met een bereik van integers
  • Eerste-klaswaarde

    Waarde die in een bepaalde taal centraal staat en waarop (vrijwel) alle soorten operaties die in de taal mogelijk zijn, zijn toegestaan.

    Ook: first-class value

    [T2.5.3]

  • Geef een beschrijving van het cartesisch product
    SxT heeft als waardenverzameling tweetallen, met een eerste element van type S en een tweede element van type Y (aanwezig in Haskell in de vorm van tupels , in Java als klassetype)

    In de verzamelingenleer is het cartesisch product of de productverzameling van twee verzamelingen de verzameling van alle koppels of geordende paren (a,b) waarvan a uit de eerste en b uit de tweede verzameling komt. Het cartesisch product van twee verzamelingen A en B wordt genoteerd als  AxB.Voorbeeld A={1,2} en B={3,4,5}, dan is AxB={(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)}
  • Statische typering
    Mechanisme waarbij elke variabele of parameter een vast, door de programmeur gekozen type heeft en waarbij de typecontrole op grond van de programmatekst mogelijk is en al tijdens de vertaalfase plaatsvindt.
    [T2.5.1]
  • Enumeration type

    Type, waarvan de (namen van) waarden expliciet zijn opgesomd.

    Ook: opsommingstype

    [T2.2.2]

  • Geef een beschrijving van het begrip recursief type
    Een recursief type is een type die gedefinieerd wordt in termen van zichzelf
  • Expressie

    Programmafragment dat geëvalueerd kan worden en daarbij een waarde oplevert.

    [T2.6]

  • Geef een beschrijving van het begrip disjuncte vereniging
    S+T heeft als waardenverzameling de waarden van S en T, waarbij te onderscheiden is uit welk van de twee verzamelingen de waarden afkomstig is (aanwezig in Haskell als datatype, in Java aanwezig als interfacetype met voor ieder component van de vereniging een klasse die de interface implementeert.
  • Geef een beschrijving van het begrip cartesisch product
    <TODO>
  • Waarde
    Elke entiteit die tijdens de uitvoering van een programma of berekening kan worden uitgerekend of opgeslagen, opgenomen kan worden in gegevensstructuur, meegegeven kan worden als parameter, resultaat is van een functieaanroep, enzovoort. Anders gezegd: elke entiteit die tijdens een berekening kan bestaan .
    Ook: value
    [T2.1]
  • Functie f: S -> T

    Voorschrift dat bij elke waarde x uit S (het domein van de functie) precies één waarde uit T (het bereik) oplevert.

    Ook: mapping

    [T2.3.2]

  • Geef een beschrijving van het begrip functieruimte
    S->T heeft als waardenverzameling de funties van S naar T (in Haskell aanwezig als functies, in Java alleen aanwezig in de vorm van arrays)
  • Functieaanroep

    Expressie verkregen door een functieabstractie toe te passen op een of meer actuele parameters.

    Ook: function call

    [T2.6.3]

  • Geef een beschrijving van het begrip  type-equivalentie
    Bij naamequivalentie zijn 2 tpen gelijk als ze dezelfde naam hebben. Bij structuurequivalentie zijn 2 typen gelijk als ze dezelfde structuur(verzameling waarden) hebben. Java maakt gebruik van naamequivalentie.
  • Geef een beschrijving van het begrip type-equivalentie
    <TODO>
  • Functie(abstractie)

    Implementatie van een (wiskundige) functie door middel van een algoritme dat voor elke waarde uit het domein (het argument) de bijbehorende functiewaarde (het resultaat) berekent.

    [T2.3.2]

  • Geef een beschrijving van het begrip structurele equivalentie
    Bij structuurequivalentie zijn 2 typen gelijk als ze dezelfde structuur(verzameling waarden) hebben
  • Functieruimte (S -> T)

    Verzameling van alle afbeeldingen f: S -> T waarvoor geldt dat als x tot S behoort, f(x) tot T behoort.

    [T2.3.2]

  • Geef een beschrijving van het begrip  naamequivalentie
    Bij naamequivalentie zijn 2 typen gelijk als ze dezelfde naam hebben.
  • Homogeen (van lijst of tupel)

    Een tupel heet homogeen als alle componenten van de tupel uit dezelfde verzameling gekozen worden.

    [T2.3.1]

    Een lijst heet homogeen als alle elementen uit de lijst van hetzelfde type zijn.

    [T2.4.1]

  • Geef een beschrijving van het begrip constructie

    Een constructie is een expressie die een composite waarde van zijn component waarden construeert. Bijvoorbeeld het volgende Java object constructie:
    new Date(today.m, size(today.m)).
    Een Java constructie is een call naar een operatie, die constructor genoemd wordt. het effect van een constructor aanroep is om een nieuw object aan te maken van een bepaalde klasse, de constructor zelf wordt gedefinieerd als deel van de klasse zelf.
  • Infix-notatie

    Notatiewijze waarbij een (binaire) operator tussen zijn operanden wordt geschreven (in tegenstelling tot prefix en postfix).

    [T2.6.3]

  • Geef een beschrijving van het begrip functieaanroep
    Een functieaanroep berekent een resultaat door een functieprocedure toe te passen op 1 of meer argumenten
  • Letterlijke waarde

    Speciale vorm van een expressie die gebruikt wordt om waarden van standaardtypen aan te duiden.

    Ook: literal

    [T2.6.1]

  • Geef een beschrijving van het begrip conditionele expressie
    Een conditionele expressie berekent een waarde die afhangt van een conditie. Het heeft 2 of meer subexpressie, waarbij er exact 1 uitgekozen wordt om geevalueert te worden
  • Lexicografische ordening

    Ordening van lijsten waarbij het eerste element bepalend is, tenzij het eerste element gelijk is; in dat geval beslist het tweede element, tenzij dat ook gelijk is, enzovoort. Als een van de twee lijsten een beginstuk is van de andere, dan is de lengte bepalend.

    [T2.4.2]

  • Geef van de verschillende soorten typen voorbeelden in de talen Jave en Haskell
    Haskell 
    -  primitieve typen -> Int, Integer, Float, Double, Char
    - andere typen -> Bool, Rational
    samengestelde waarden: lijsten, tupels, dataconstructies
    - Haskell kent geen deelintervaltype
    - Een opsommingstype (enumeration type) is in Haskell geen primitief type, maar kan wel gecreerd worden met behulp van constructiefuncties zonder parameter

    Java
    -  primitieve type -> byte, short, int, long, char, float, double en boolean
    - samengestelde waarden (arrays, objecten) 
    - Java kent geen deelintervaltype, maar kan wel worden gecreerd met behulp van een klasse van type enum
  • Lijstcomprehensie

    Notatie waarmee een lijst wordt opgebouwd door een expressie te evalueren in een omgeving, waarbij een variabele alle waarden van een lijst doorloopt.

    [T2.6.5]

  • Noem de 4 structureringsconcepten met behulp waarvan we samengestelde typen kunnen karakteriseren en herken de verschillende samengestelde typen uit Java en Haskell
    1. cartesische producten: bijvoorbeeld een set van ale paren van (x,y), SxT={(x,y)|xeS,yeT}. Bijvoorbeeld S={u,v} en T={a,b,c} dan is SxT={(u,a),(u,b),(u,c),(v,a),(v,b),(v,c)}. De kardinaliteit is 2x3=6
    2. mappings: S->T staat voor alle mappings van S naar T. De kardinaliteit van S->T is #(S->T)=(#T)^(#S)
    3. disjoint unions: Hierbij wordt een waarde gekozen van 1 of meerdere (meestal verschillende) sets. S+T. #(S+T)=#S+#T
    4. recursieve typen: Is een type die gedefinieerd wordt in termen van zichzelf. 2 Gebruikelijke recurcieve typen zijn lists (een sequence van waarden) en strings (een sequence van karaketers).
  • Naamequivalentie

    Vorm van type-equivalentie, waarbij twee typen alleen equivalent zijn als ze op dezelfde plaats gedefinieerd zijn.

    [T2.5.2]

  • Geef de formules waarmee de verschillende kardinaliteiten van de verschillende samengestelde typen kunnen worden berekend en pas deze toe

    Cartesisch product: S x T: 
    - Cardinaliteit: #(S x T) = #S x #T 

    Disjuncte vereniging: S + T
    Cardinaliteit: #(S + T) = #S + #T

    Functieruimte: S -> T
    Cardinaliteit: #(S -> T) = #T^#S
  • Postfix-notatie

    Notatiewijze waarbij een operator achter zijn operanden wordt geschreven (in tegenstelling tot infix en prefix).

    [T2.6.3]

  • Geef de manieren waarop in verschillende talen strings zijn gedefinieerd en geef aan welke consequenties een dergelijke keuze heeft voor de manier waarop we operaties op strings aan de taal kunnen toevoegen
    1. Strings als primitieve waarde classificeren: ML gebruikt deze manier. De basis string operatie moet dan ingebouwd zijn; ze kunnen dan niet gedefinieerd worden in de taal zelf
    2. Strings behandelen als een array van karakters: ADA gebruikt deze manier. Hierdoor zijn alle gebruikelijke operaties die gelden voor een array ook toe te passen op strings. Consequentie is dat een sring hierdoor een fixed lenght krijgt
    3. Strings als pointers naar arrays van karakters behandelen: C en C++ gebruiken deze manier
    4. Strings als lijst van karakters behandelen: Haskell en Prolog gebruiken deze manier. Hierdoor komen alle gebruikeleijke list operaties ook toegankleijk voor strings
    5. Strings als objecten te behandelen: Wordt in een objectgeorienteerde taal gebruikt, bijv, Java. Op deze manier kun je strings gebruiken met methoden die alle benodigde operaties heeften niet het nadeel van het behandelen van strings als speciale cases van list of arrays.
  • Prefix-notatie

    Notatiewijze waarbij een operator voor zijn operanden wordt geschreven (in tegenstelling tot infix en postfix).

    [T2.6.3]

  • Leg het verschil uit tussen statisch en dynamisch getypeerde programmeertalen en geef enkele relevante voorbeelden van beide klassen van talen en geef de voor en nadelen van beide benaderingen
    Statisch getypeerd
    - Elke variabele expressie heeft een fixed type. hierdoor kunnen de types gecontroleerd worden gedurende compilatie. De meeste high-level talen zijn statisch getypeerd, bijvoorbeeld C++

    Dynamisch getypeerd
    - Waarden hebben een fixed type, maar variabelen en expressies hebben dit niet. Elke keer dat er een operand berekend wordt, kan het een waarde van een verschillend type zijn. Dus de operand meot gecontroleerd worden op type nadat ze berekend worden, maar voordat de operatie uitgevoerd wordt, dus tijdens run-time. Talen: Smalltalk, Lisp, Prolog, Perl en Python

    Voor en nadelen
    - Static typing is efficienter. Dynamische typing heeft veel run-time type checks nodig, die het programma vertraagd tijdens excecutie. Static typing heeft alleen compile-time checks nodig. Dynamic typing heeft het nodig dat alle waarden getagged worden en dit heeft strage space nodig. Static typing heeft dit niet nodig.
    - Static typing is veiliger. De compiler kan verifieren dat het programma geen type errors heeft. Dynamic typing heeft dit niet. Type errors zorgen voor veel programma fouten.
    - Dynamic typing is flexibeler, dat nodig is voor sommige applicaties, waarbij het type van data niet op voorhand bekend is.
Lees volledige samenvatting
Deze samenvatting. +380.000 andere samenvattingen. Een unieke studietool. Een oefentool voor deze samenvatting. Studiecoaching met filmpjes.

Laatst toegevoegde flashcards

Statische typering
Mechanisme waarbij elke variabele of parameter een vast, door de programmeur gekozen type heeft en waarbij de typecontrole op grond van de programmatekst mogelijk is en al tijdens de vertaalfase plaatsvindt.
[T2.5.1]
Waarde
Elke entiteit die tijdens de uitvoering van een programma of berekening kan worden uitgerekend of opgeslagen, opgenomen kan worden in gegevensstructuur, meegegeven kan worden als parameter, resultaat is van een functieaanroep, enzovoort. Anders gezegd: elke entiteit die tijdens een berekening kan bestaan .
Ook: value
[T2.1]
Gegeven is de volgende monitor in (pseudo-)Java voor een begrensde buffer die gebruikmaakt van de conditievariabelen nonfull en nonempty en van synchronized-clausules.public class QueueMonitor {private class MessageBuffer {int size, front, rear; Message[] items; }public int capacity;private MessageBuffer buffer = new MessageBuffer();private Signal nonfull; private Signal nonempty;public QueueMonitor(int capacity) { // we don't use items[0] buffer.items = new Message[capacity + 1];this.capacity = capacity; nonfull = new Signal(); nonempty = new Signal(); } public synchronized void sendmessage(Message newitem) { while (buffer.size == capacity) // buffer full nonfull.sig_wait(); buffer.size = buffer.size + 1; buffer.rear = buffer.rear % capacity + 1; buffer.items[buffer.rear] = newitem; nonempty.sig_signal();}public synchronized Message receivemessage() { while (buffer.size == 0) // buffer empty nonempty.sig_wait();buffer.size = buffer.size - 1;Message olditem = buffer.items[buffer.front]; buffer.front = buffer.front % capacity + 1; nonfull.sig_signal(); return olditem; } { // initialisation of buffer buffer.size = 0; buffer.front = 1; buffer.rear = 0; } }a Waarmee is communicatie geïmplementeerd in QueueMonitor?b Waarmee is wederzijdse uitsluiting geïmplementeerd in QueueMonitor?
a Communicatie is geïmplementeerd met de conditievariabelen nonfull en nonempty.
b Wederzijdse uitsluiting is geïmplementeerd met de synchronizedclausules.
Gegeven zijn de volgende klassen Queue en Box in Java:public class Queue {private char[] elems;private int length, front, rear;public Queue(int capacity) {  elems = new char[capacity];}public void add(char newelem) { // add element to the rear of the queue ... }public int remove() { // remove and return the front element of this queue ... }{ length = 0; front = 0; rear = 0; }}public class Box {private T object;public void save(T object) { this.object = object; }public T getObject() { return object; }public String toString() { return "Box: " + object; }}a In de twee klassen wordt parametrisatie toegepast. Leg uit wat het verschil in parametrisatie is tussen de twee klassen.b Is er in de klasse Box sprake van een vorm van polymorfisme? Verklaar uw antwoord.
 a De klasse Queue is geparametriseerd met betrekking tot de waarde van de variabele capacity. Er is sprake van één klasse, ongeacht de waarde van capacity. De klasse Box is een generieke klasse die geparametriseerd is met betrekking tot het type object dat in een box wordt opgeslagen. Instanties van klasse Box kunnen voor verschillende waarden van de klasseparameter T worden geïnstantieerd.
b Nee, er is geen sprake van polymorfisme. Er kunnen, zoals in a al gezegd, verschillende instanties van type Box worden gemaakt, maar elke keer betreft het een instantie van een monomorf type, bijvoorbeeld Box, Box, enzovoort.
In deze opgave moet u het cartesisch product modelleren in Java en in Haskell en conclusies trekken ten aanzien van de uitbreidbaarheid daarvan in beide talen.Als voorbeeld nemen we personen die in eerste instantie een naam en een leeftijd als eigenschap hebben. Van personen willen we weten of ze meerderjarig (ouder dan 17 jaar) zijn.8a Implementeer in Java het cartesisch product voor de klasse Persoon en geef deze klasse een methode isMeerderjarig.8b Implementeer in Haskell het type Persoon en definieer een functie isMeerderjarig. Geef ook het type van de functie.8c Breid nu zowel in Java als in Haskell het cartesisch product uit door personen ook een adres als eigenschap te geven. Geef aan welke wijzigingen in beide talen moeten plaatsvinden.8d Welke conclusie kunt u uit 8c trekken?

8a Het cartesisch product modelleren we in Java met behulp van een klassetype met voor elke eigenschap een attribuut:
class Persoon {
String naam;
int leeftijd;
boolean isMeerderjarig() {
return leeftijd > 17;
}
}


8b Het cartesisch product modelleren we in Haskell met een typedefinitie voor een tweetupel:
type Persoon = (String, Int)
isMeerderjarig :: Persoon -> Bool
isMeerderjarig (_, leeftijd) | leeftijd > 17 = True
                                               | otherwise = False

8c Om in Java het cartesisch product uit te breiden is het voldoende om een attribuut adres van type String toe te voegen. De methode isMeerderjarig hoeft niet aangepast te worden.
Om in Haskell het cartesisch product uit te breiden moeten we het type Persoon veranderen in een drietupel waarin ook een string voor het adres is opgenomen. Daarnaast moet de definitie van de methode isMeerderjarig veranderd worden. Het patroon dat gebruikt wordt voor de parameter moet drie elementen bevatten in plaats van twee.

8d De conclusie is afhankelijk van de gegeven implementatie voor 8a, 8b en 8c. Belangrijk is dat uw conclusie overeenstemt met het voorgaande. In onze implementatie is uitbreiding makkelijker in Java omdat er slechts een attribuut toegevoegd moet worden. In Haskell moet ook de functie aangepast worden aan de wijziging.
Waarom zijn de meeste scripttalen dynamisch getypeerd?


Scripttalen worden gebruikt om subsystemen, die in verschillende talen zijn geprogrammeerd, met elkaar te laten werken. Als onderdeel daarvan moet allerlei data van verschillende typen verwerkt worden. Scripts kunnen sneller geschreven worden als het type van de variabelen en parameters niet van tevoren gedeclareerd hoeven te worden.
Is er bij Prolog sprake van veranderbare of onveranderbare variabelen?Motiveer kort uw antwoord.

Een variabele in Prolog is een onveranderbare variabele. De variabele, waarvan de
naam begint met een hoofdletter, staat voor een vaste maar onbekende waarde van
een willekeurig type.
We geven hier een voorbeeld uit het tekstboek waar de variabele P staat voor
venus, earth, mars, enzovoort:
?– planet(P).
Wat is het essentiële kenmerk van het logische programmeerparadigma?

Logisch programmeren is gebaseerd op de gedachte dat we programma’s kunnen
ontwerpen door beweringen over een probleem te noteren in logische formules.
Vervolgens zijn die formules zodanig te interpreteren, dat de oplossing voor het
beschreven probleem automatisch kan worden afgeleid.
Alternatief antwoord: Een logisch programma bestaat uit een specificatie van
relaties waarvan bepaald kan worden voor welke waarden van de parameters deze
geldig zijn.
Gegeven is het volgende programmafragment in Java:private int x = 0;public void verhoogX() {for (int i = 0; i < 10000000; i++) {x = x + 1;}}Leg uit waarom in het geval van parallel programmeren er sprake kan zijnvan een race condition bij de uitvoering van de gegeven code.Aanwijzing: Schets voor de uitleg een scenario met daarin twee threads.Verander de Java-code zo dat de race condition opgeheven is.

In de for-lus gebeurt het ophogen van de waarde van x in drie stappen: eerst wordt
de waarde van x uit het geheugen gelezen, dan wordt de waarde verhoogd en
tenslotte wordt de verhoogde waarde teruggeplaatst in het geheugen.
Stel, twee threads voeren de for-lus tegelijk uit. Het volgende scenario is mogelijk:
Thread 1: leest x, waarde x in het geheugen is 7
Thread 1: verhoogd x, waarde is nu 8
Thread 2: leest x, waarde x in het geheugen is 7
Thread 1: schrijft de waarde van x, waarde x in het geheugen is nu 8
Thread 2: verhoogd x, waarde is nu 8
Thread 2: schrijft de waarde van x, waarde x in het geheugen is nu 8.
Voeren de twee threads de for-lus achter elkaar uit, dan is de waarde van x na
afloop 9. Er is dus een verschil in uitkomst.
 Voor de methode verhoogX kunnen we een synchronized-clausule gebruiken:
private int x = 0;
public synchronized void verhoogX() {
for (int i = 0; i < 10000000; i++) {
x = x + 1;
}
}
NB Het is niet mogelijk om een synchronized-opdracht (blok-opdracht) te
gebruiken waarbij we op attribuut x synchroniseren. Het attribuut x is namelijk
geen object maar een primitief type.
Wat is een race condition.

Een race condition treedt op wanneer twee of meer processen of threads in staat
zijn om tegelijk een gemeenschappelijke variabele te veranderen waardoor het
resultaat onverwacht kan zijn.