Taal, Wiskunde, Logica: Voorjaar 2008
Algemene informatie over het college
Zie
hier.
Het relevante citaat:
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 woensdagen van 11 tot 12.45, in KNG80, zaal 131.
Collegedata zijn: 23 april, 7 mei, 14 mei, 21 mei, 28 mei, 4 juni, 11 juni,
18 juni. Afsluitend schriftelijk tentamen op 25 juni.
Practicum-info
Bij het college hoort een computer-practicum. De practicumsessies vinden
plaats in KNG80, zaal 113 CL, op vrijdagochtend, van 9.00 tot 12.45.
Docent
Jan van Eijck, per email bereikbaar op dit adres.
Practicum assistent
Arno Bastenhof, per email bereikbaar op dit adres.
Huiswerk
Het huiswerk zal bestaan uit leesopdrachten, opgaven uit het boek, en
opdrachten die achter de computer moeten worden uitgevoerd.
Het huiswerk dient per email te worden ingeleverd by
Arno Bastenhof, met een
cc naar Jan van Eijck.
De deadlines staan bij elke opgave aangegeven. De deadlines zijn strikt.
College-overzicht
Slides Hoorcolleges
Slides van de hoorcolleges zullen hieronder verschijnen.
Week 17
-
Hoorcollege 23/04/08: Wat is functioneel programmeren?
- Slides van het college op 23/04/08:
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 28 april, 12 uur 's middags.
- Leesopdracht: hoofdstuk 1 en 2 van Partee, ter Meulen en Wall
lezen, en een lijst maken van alles wat je niet begrijpt.
Wie het boek nog niet heeft kan ook de eerste twee hoofdstukken van
Logica voor alfa's en informatici lezen: zie de link
hieronder.
Week 18: geen college, geen practicum.
Week 19
Week 20
- Hoorcollege 14/05/08: meer over programmeren in Haskell:
werken met lijsten.
- Slides van het hoorcollege van 14/05/08:
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 19 mei, 12 uur 's middags.
- Lees-opdracht: hoofdstukken 3 en 4 van Partee, ter Meulen en Wall
lezen, en een lijst maken van alles wat je niet begrijpt.
Week 21
- Hoorcollege 21/05/08 is helaas vervallen: de docent kon Utrecht
niet bereiken wegens een storing bij de NS.
- Slides van het hoorcollege van 21/05/08 (dat niet is doorgegaan):
LAG.pdf.
We komen hier nog op terug.
- De Haskell code horend bij dit college:
LAG.hs.
- Practicum-opdrachten:
week4opdr.html.
- Huiswerk: schriftelijk verslag van de practicumopdrachten inleveren
per email. Deadline: maandag 26 mei, 12 uur 's middags.
- Lees-opdracht: hoofdstuk 16 (kernbegrippen uit formele taaltheorie)
van Partee, ter Meulen en Wall
lezen, en een lijst maken van alles wat je niet begrijpt. Bekijk ook
de appendix over de Chomsky hierarchie (appendix E-I).
Week 22
- Hoorcollege 28/05/08: Bomen en boombewerkingen.
- Slides van het hoorcollege van 28/05/08:
Trees.pdf.
- De Haskell code horend bij dit college:
Trees.hs.
- Practicum-opdrachten:
week5opdr.html.
- Huiswerk: schriftelijk verslag van de practicumopdrachten inleveren
per email. Deadline: maandag 2 juni, 12 uur 's middags.
- Lees-opdracht: hoofdstuk 17 (eindige automaten, reguliere talen en type
3 grammatica's) van Partee, ter Meulen en Wall
lezen, en een lijst maken van alles wat je niet begrijpt.
Week 23
- Hoorcollege 4/06/08: Vorm en Inhoud.
- Slides van het hoorcollege van 4/06/08:
FormContent.pdf.
- De Haskell code horend bij dit college:
FormContent.hs.
- Practicum-opdrachten:
week6opdr.html.
- Haskell code horend bij de practicum-opdrachten:
Week6.hs.
- Huiswerk: schriftelijk verslag van de practicumopdrachten inleveren
per email. Deadline: maandag 9 juni, 12 uur 's middags.
- Lees-opdracht: Paragrafen uit hoofdstukken 6 en 7
(6.1, 6.2, 6.3, 6.4, 7.1, 7.2, 7.3) van Partee, ter Meulen en Wall
bestuderen. Probeer het verband te leggen met wat in de college-slides
wordt behandeld.
Week 24
- Hoorcollege 11/06/08: Propositie- en predikaatlogica.
- Slides van het hoorcollege:
Logic.pdf.
- De Haskell code horend bij het college:
Logic.hs.
- Practicum-opdrachten:
week7opdr.html.
- Huiswerk: schriftelijk verslag van de practicumopdrachten inleveren
per email. Deadline: maandag 16 juni, 12 uur 's middags.
- Leesopdracht: Hoofdstuk 14 uit Partee, ter Meulen en Wall
(het hoofdstuk over gegeneraliseerde kwantoren). Probeer het verband
te zien met de slides van het college over Vorm en inhoud
(FormContent.pdf).
Week 25
- Kort proeftentamen: ProefTentamen.pdf.
- Uitwerking van het proeftentamen:
ProefTentamenUitw.pdf.
- Gelegenheid tot vragen stellen over de hele stof.
- De onbeslisbaarheid van het stopprobleem in
dichtvorm:
Stop de lus.
- Als er tijd is: kort hoorcollege op 18/06/08 over
gegeneraliseerde kwantoren
- Slides bij hoorcollege 18/06/08: GQ.pdf.
- In plaats van computerpracticum deze week werkcollege "oefenen voor het
schriftelijk tentamen".
- Practicum-opdrachten: week8opdr.html.
- Huiswerk: schriftelijk verslag van de practicumopdrachten inleveren
per email. Deadline: maandag 23 juni, 12 uur 's middags.
- Let op: zaalwijziging. Oefensessie
9.00-12.45 op vrijdag 20 juni in zaal KNG80 031 (dus niet
in KNG80 113 CL).
Week 26
Cursusevaluatie
Het online-evaluatieformulier is
hier te vinden.
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 leerboek in het Nederlands 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: Wat moet je doen als je het boek van Partee, ter Meulen en Wall
nog niet binnen hebt?
- Antwoord: een groot deel van de stof in dat boek wordt ook behandeld
in Logica voor alfa's en informatici: zie de link hierboven.
- 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 4.
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.