Taal, Wiskunde, Logica: Voorjaar 2009

Algemene informatie over het college

Natuurlijke talen vertonen een rijke verscheidenheid aan patronen. De taalwetenschap zoekt naar onderliggende wetmatigheden waaraan taalpatronen gehoorzamen. Wat voor instrumenten hebben taalgebruikers om met eindige middelen oneindige verzamelingen van uitdrukkingen te maken die aan bepaalde patroonkenmerken voldoen? Zijn er verschillen in de complexiteit van patronen die we in talen aantreffen, en hoe kunnen we die complexiteit meten? Welke rekenvermogens heeft ons verwerkingssysteem nodig om met taalpatronen om te gaan? In deze cursus maakt de student kennis met een aantal methoden uit de wiskunde en de logica die van belang zijn om dit soort vragen op een zinvolle manier aan te pakken. Kennis van basisbegrippen uit de verzamelingenleer en de algebra wordt in een taalkundige context geplaatst. Vervolgens komen aan de orde: logica en deductieve systemen, de Chomsky hiërarchie van formele grammatica's en de bijhorende automaten. In de werkcolleges verwerft de student de vaardigheid om theoretische kennis om te zetten in kleine werkende grammaticafragmenten.

Cursusdoelen:

De student verwerft grondige kennis van de formele concepten en technieken die nodig zijn voor verdere taalwetenschappelijke studie (kernbegrippen uit de verzamelingenleer, grafen en bomen, relaties en functies, logica en formele afleidingssystemen, formele grammatica's en automaten). Daarnaast verwerft de student de vaardigheid om die theoretische kennis in de praktijk te brengen, in de vorm van concrete analyses op verschillende niveau's van grammaticale organisatie.

Hoorcolleges

Hoorcollege op dinsdagen van 15.15 tot 17.00, in D23, zaal 104. Collegedata zijn: 21 april, 28 april, 12 mei, 19 mei, 26 mei, 2 juni, 9 juni, 16 juni. Afsluitend schriftelijk tentamen op 23 juni.

Practicum-info

Bij het college hoort een computer-practicum. De practicumsessies vinden plaats in KNG80, zaal 013 CL, op donderdagochtend, van 9.00 tot 12.45.

Docent

Jan van Eijck, per email bereikbaar op dit adres.

Practicum assistenten:

Arno Bastenhof (eerste twee weken) en Martijn van Steenbergen (hele cursus).

Huiswerk

Het huiswerk zal bestaan uit leesopdrachten, opgaven uit een leerboek, en opdrachten die achter de computer moeten worden uitgevoerd. Het huiswerk dient per email te worden ingeleverd by Arno Bastenhof (eerste twee weken) en Martijn van Steenbergen (hele cursus), met een cc naar Jan van Eijck. De deadlines staan bij elke opgave aangegeven. De deadlines zijn strikt.

Nota bene: vanaf nu het huiswerk per email inleveren bij Martijn, met een cc naar Jan.

College-overzicht

• Slides met het college-overzicht: Overzicht.pdf.

Slides Hoorcolleges

Slides van de hoorcolleges zullen hieronder verschijnen.

Week 17

• Hoorcollege 21/04/09: Wat is functioneel programmeren?
• Slides van het college op 21/04/09: GSWH.pdf.
• De Haskell code horend bij dit college: GSWH.hs.
• Practicumopdrachten: haskellOpdr.html.
• Haskell code bij een van de opdrachten: typen.hs.
• Huiswerk: schriftelijk verslag van de practicumopdrachten inleveren per email. Deadline: maandag 27 april, 12 uur 's middags.
• Leesopdracht: hoofdstuk 1 van Doets en van Eijck, The Haskell Road to Logic, Maths and Programming lezen (hier te vinden), en een lijst maken van alles wat je niet begrijpt.

Week 18

• Hoorcollege 28/04/09: Gastcollege dr. Joost Zwarts.
• Slides van het college op 28/04/09: TWL Gastcollege.pdf.
• Deze week geen practicum vanwege koninginnedag.
• Leesopdracht: hoofdstuk 2 van Van Eijck en Unger, Computational Semantics and Functional Programming lezen, en een lijst maken van alles wat je niet begrijpt. Zie hier voor de pdf versie van het boek.

Week 19

• 05/05/09: geen hoorcollege.
• Practicum-opdrachten deze week: lijstOpdr.html.
• Huiswerk: schriftelijk verslag van de practicumopdrachten inleveren per email. Deadline: maandag 11 mei, 12 uur 's middags.
• Model-uitwerkingen van het huiswerk: Prac2.hs.

Week 20

• Hoorcollege 12/05/09: meer over programmeren in Haskell: werken met lijsten.
• Slides van het hoorcollege van 12/05/09: WWL.pdf.
• De Haskell code horend bij dit college: WWL.hs.
• Practicum-opdrachten: week3opdr.html.
• Huiswerk: schriftelijk verslag van de practicumopdrachten inleveren per email. Deadline: maandag 18 mei, 12 uur 's middags.
• Lees-opdracht: nogmaals hoofdstuk 2 van Van Eijck en Unger, Computational Semantics and Functional Programming lezen, en een lijst maken van alles wat je niet begrijpt. Zie hier voor de pdf versie van het boek.

Week 21

• Hoorcollege 17/05/09: vervolg Werken met lijsten.
• Geen practicum deze week vanwege hemelvaart. Wel alvast de practicumopdrachten voor volgende week. Let op: dit zijn herhalingsoefeningen: Opgaven.html.
• Huiswerk: deze week geen deadline. De volgende deadline is op 1 juni.

Week 22

• Hoorcollege 26/05/09: Talen en Grammatica's.
• Slides bij het hoorcollege: LAG.pdf.
• Bijbehorende Haskell code: LAG.hs.
• Practicum: herhalingsoefeningen, Opgaven.html.
• Huiswerk: deadline voor inleveren practicum oefeningen op 1 juni.

Week 23

• Hoorcollege 2/06/09: Bomen en Boombewerkingen.
• Slides bij het hoorcollege: Trees.pdf.
• Bijbehorende Haskell code: Trees.hs.
• Practicum: prac5opdr.html.
• Huiswerk: deadline voor inleveren practicum oefeningen op 8 juni.

Week 24

• Hoorcollege 9/06/09: Logica.
• Slides bij het hoorcollege: Logic.pdf.
• Bijbehorende Haskell code: Logic.hs.
• Practicum: prac6opdr.html.
• Huiswerk: deadline voor inleveren practicum oefeningen op 15 juni.

Week 25

• Hoorcollege 16/06/09: Logica vervolg.
• Proeftentamen: zie hier.
• Uitwerking proeftentamen: zie hier.
• Practicum: prac7opdr.html.
• Huiswerk: deadline voor inleveren practicum oefeningen op 23 juni.
• Let op: huiswerk deze week emailen naar Jan van Eijck, of uitgeprint meebrengen naar het laatste college.

Week 26

• Dinsdag 23/06/09: Afsluitend schriftelijk tentamen. Het tentamen is van 15.15 tot 17.00 in de gebruikelijke collegezaal: zaal 104, Drift 23.
• Het tentamen: Tentamen.pdf.
• Uitwerkingen van de antwoorden: TentamenUitw.pdf.

Cursusevaluatie

Het evaluatieformulier vind je hier. Vriendelijk verzoek: Zouden jullie alsjeblieft allemaal zo snel mogelijk de vragenlijst in willen vullen?

Achtergrondmateriaal

• Over logica, wiskunde en (functioneel) programmeren: Doets en van Eijck, The Haskell Road to Logic, Maths and Programming , zie hier.
• Het eerste hoofdstuk van dit boek is een beknopt Haskell tutorial. Zie hier.
• Een algemene inleiding logica die net is verschenen bij de Open Universiteit: Van Benthem, Van Ditmarsch en Van Eijck, Logica in actie, zie logica-in-actie en http://www.spinoza.ou.nl/johan-van-benthem/logica-in-actie/downloads/LIA_eBook.pdf
• Een leerboek over wiskunde en logica voor taalkundigen: Van Eijck en Thijsse, Logica voor alfa's en informatici, zie lai.pdf of lai.ps.
• Een manuscript over computationele semantiek: Van Eijck en Unger, Computational Semantics and Functional Programming , zie hier.

Veelgestelde vragen

• Vraag: In Haskell, is [Char] = String = [a] of betekenen ze alledrie iets anders? En hoe zit dat met a en Char?
• Antwoord: String is inderdaad een afkorting voor [Char], een lijst van Chars. Maar a en Char zijn verschillend: a staat voor een willekeurig type (een zogenaamd abstract type), terwijl Char een zogenaamd concreet type is. [a], tenslotte, staat voor een lijst van dingen van type a. Dit is dus verschillend van [Char].
• Vraag: Ik heb problemen met het installeren van Hugs. Is het juiste adres om te downloaden wel http://cvs.haskell.org/Hugs/pages/downloading.htm?
• Antwoord: Dit is inderdaad de correcte downloading pagina, maar let op: je moet binnen deze pagina nog wel de versie kiezen die bij je systeem past. Als een van de verpakte distributies bij je systeem past neem je die, en dan zou alles in principe zo moeten werken. Anders kun je nog altijd een source distributie downloaden, maar dan zul je zelf moeten compileren.
• Vraag: Ik weet nog niet goed hoe je in Haskell functies moet schrijven en dat moet steeds, in de opdrachten voor de tweede week. Is er ergens online een guideline of hebben jullie wat richtlijnen voor hoe ik aan de slag moet?
• Antwoord: In de college-slides staan voorbeelden van Haskell functies. Dit is werkende Haskell code, dus als je je functies zo schrijft gaat het goed. Je zou ook nog eens kunnen kijken in dit tutorial, in sectie 1.4, vanaf +1.4.2 (pagina 14). Of het online boek over computationele semantiek, cs.pdf, hoofdstuk 3.

  Veel van de opdrachten gaan over lijsten. Een lijst is:

  • de lege lijst []; of
  • het resultaat van het op kop plaatsen van een 'element' x op een reeds bestaande lijst xs; (x : xs) (waarbij geen element in xs een ander type heeft dan dat van x).
  Omdat niets anders een lijst is kunnen we met de twee gevallen [] en (x:xs) alle mogelijke lijstvormen afdekken. Soms is het nuttig om te kunnen praten over lijsten met precies een element. Die hebben de vorm [x].

  Merk op: [3] is eigenlijk een afkorting voor (3:[]), en [1,2,3] is eigenlijk een afkorting voor (1:(2:(3:[]))).

• Vraag: Ik vind het lastig om steeds alle Haskell programma's uit de opdrachten twee keer te moeten opschrijven: eerst als programma, en dan als tekstbestand met commentaar. Is daar een oplossing voor?
• Antwoord: Er zijn verschillende oplossingen. De eenvoudigste mogelijkheid is om je bestand Antwoorden.hs te noemen, en dan het commentaar te schrijven als Haskell commentaar. Haskell commentaar begint met -- en loopt dan door tot het eind van de regel, of het begint met {- en loopt dan door tot -}. Een andere mogelijkheid is het schrijven van literate Haskell. Een literate Haskell file heeft de extensie .lhs, en volgt een omgekeerde conventie: alles is commentaar, behalve de tekst die tussen

  \begin{code} 

  en

  \end{code} 

  staat.
• Vraag: Als p een eigenschap is, dan is niet p ook een eigenschap. Bestaat er een algemene manier om uit eigenschappen (functies van type a -> Bool) nieuwe eigenschappen te maken?
• Antwoord: Eigenschappen hebben inderdaad logische structuur. De eigenschap niet p kun je gemakkelijk maken met behulp van de not functie. In Haskell heeft not het type Bool -> Bool. De functie neemt een waarheidswaarde en draait die om. Dus als we eerst p toepassen en daarna not krijgen we precies wat we moeten hebben. De ene functie na de andere toepassen heet compositie, en in Haskell drukt f . g uit dat je f moet toepassen na g. Dus: not . p geeft de negatie van eigenschap p. Het valt gemakkelijk na te gaan dat not . p hetzelfde type heeft als p. Een andere manier om de negatie van p te krijgen is met behulp van \ x -> not (p x). Andere logische operaties op eigenschappen zijn conjunctie en disjunctie. Als intelligent en aantrekkelijk eigenschappen zijn, dan zijn intelligent en aantrekkelijk en intelligent of aantrekkelijk ook eigenschappen. In Haskell gaat dat zo: als p en q eigenschappen zijn, dan is \ x -> p x && q x hun conjunctie, en \ x -> p x || q x hun disjunctie. Probeer maar uit.