Høst 1998
Beskjeder
Underviser SLI 5 - Symbolsk programmering II
Øvelser ved Asle Olufsen
Undervisningstid:
Pensum:
Annen litteratur
Undervisningsprogram
Anbefalte linker
Send post
Uke 35
Vi repeterer SLI 3. To vesentlige ting skal vi ha klare. Det ene er omgivelsesmodellen for beregninger i Scheme. Den kommer vi til å bruke en del i høst. Det andre er rekursjon. Repeter kapitlet med objekter og se spesielt på hvordan omgivelsene brukes.
Jeg har lagt ut den aller siste eksamensoppgaven i SLI 3.
Send meg en email slik at jeg får vite hvem det er som tar kurset og slik at vi kan lage en mailingliste for SLI5-spørsmål.
Uke 36 - strømmer
En strøm er det som er gitt ved ... i
1 2 3 4 ...
pi = 3.14159...
Vi viser hvordan vi kan fange det inn ved lambda-konstruksjoner. Det finnes mange alternative måter å implementere strømmer på. Asle Olufsen har lagd en som det er god grunn til å se nærmere på.
Første innleveringsoppgave - frist mandag 5 oktober
Dronningproblemet løst ved strømmer - oppgave 1209 i heftet.
Uke 37 - kontinuasjoner
Kontinuasjoner bruker vi når vi skal regne ut et stort regnestykke og må gjøre noe mellomregning før vi fortsetter med selve regnestykket. I Scheme han vi sette navn på kontinuasjoner med
call-with-current-continuation (eller call/cc)
Vanskeligheten for dere er for det første å se at vi bruker kontinuasjoner når vi regner store regnestykker. Deretter å se hva en slik kontinuasjon er - funksjon som til et svar av mellomregningen sier hvordan svaret skal behandles videre. Videre skal dere streve med å se hvordan dette kan brukes programmeringsmessig.
I utviklingen av scheme var bruken av kontinuasjoner et helt vesentlig valg. Andre språk har ikke noe tilsvarende. Mange av de mest interessante nye programmeringsmulighetene i scheme får en med kontinuasjoner.
Som en test på forståelsen gå skikkelig i gjennom eksempelet med korutiner.
Uke 38 - søking
Vi søker i et tilstandsrom der vi vandrer mellom tilstander. Et hovedproblem ved søking er organiseringen av alle nodene som vi ser skal undersøkes men er ennå ikke undersøkt. Ved ulike organiseringer får vi lett dybde først, bredde først, best først søk.
Vis hvordan du får kode for de enkle søkeprogrammene. For mer avanserte søkeprogrammer tenk på hva turingmannen må huske mens han er underveis i tilstandsrommet. Det er nesten alltid en avveining mellom å huske mye og det å ha liten administrasjon av hva som skal huskes.
Generaliseringer til søking i og-eller graf og til tomanns-spill.
A*-algoritme. Her er det flere pekere. Studentene i fjor arbeidet med den. Her er en annen peker.
I Prolog brukes dybde først søk. Dette gjør at noen søkealgoritmer får en veldig enkel prolog-kode.
I dette kapitlet skal du ha fått med
Uke 39 - patternmatching, unifikasjon
Vi lager scheme-program for patternmatching (mønsterpassing) og unifikasjon (samordning). Vi ser hvordan programmene bruker på en vesentlig måte at vi har et rigid underliggende skjelett og at mønstrene fås ved at en på noen steder i skjelettet hekter på variable.
Behandlingen av sirkularitet ved bruk av forekomstsjekk - og problemer med effektivitet av denne.
Prologprogram for unifikasjon.
Generalisering av mønstre ved bruk av joker-notasjon.
Uke 40 - repetisjon
Jeg regner med at dere bruker tiden denne uka på repetisjon og arbeidet med øvelsesoppgaven - bruk av strømmer til å løse dronnningproblemet. Det blir ingen regulære forelesninger, men jeg vil være tilgjengelig på kontoret mitt (B 225) i de oppsatte forelesningstidene. Så kom innom - med spørsmål, problemer eller bare en prat.
Uke 41 - utsatte beslutninger
Dette er et litt rotete kapittel. Vi tar for oss Prolog. Først ser vi på bruk av variable i programmeringsspråk. Vi har tre ulike bruk
I Prolog har vi den siste bruken. Dette gir nye muligheter til å behandle utsatte beslutninger. En elegant bruk av dette er i differenslister. Prøv å se hvordan dette kan sees som et eksempel på utsatte beslutninger.
Vi ser på hvordan en Prolog beregning foregår - vi lager et beregningstre der nodene blir dekorert med den aktuelle målstakken eller et OG-ELLER tre med et delmål ved hver node. Prøv å se hvordan CUT blir forstått i et slikt OG-ELLER tre. I Prolog er det rimelig å ha med to kontinuasjoner til hvert mål - den positive kontinuasjonen om målet nås og den negative kontinuasjonen om målet ikke nås.
Så viser vi hvordan sorteringsrutiner kan programmeres i Prolog.
Noen flere prolog linker
Dere har skjønt kapitlet når dere skjønner
Programmet for finn_alle skal være (i bruken lar vi X være en av de frie variablene i Y)
finn_alle(X,Y,-) :- !,Y,asserta(funnet(X)),fail.
finn_alle(-,-,L) :- saml([],L).
saml(L1,L2) :- retract(funnet(X)),!,saml([X|L1],L2).
saml(L,L).
Eksempel på bruk - anta at vi har i vår faktabase en rekke utsagn om insekter som insekt(flue), insekt(veps) , ....
Da vil finn_alle(X,insekt(X),L) gi svaret L=[flue,veps,...]
Andre innleveringsoppgave - frist mandag 2 november
Oppgave 1403 - 15 spillet
Om du får problemer løs 8 spillet som spilles i en 3x3 ramme.
Prøv ut med ulike søkemetoder - dybde først, bredde først, A* . Prøv ut med ulike heuristikker - for eksempel antall brikker på riktig plass eller sum av avstandene brikkene har fra riktig plass.
Som test prøv 8-spillet der vi starter med
1 2 3
8 5 6
4 7
og skal ende opp med
1 2 3
4 5 6
7 8
Om dette blir for lite å gjøre - løs dronningproblemet med søking.
Uke 42 - formelle språk
Før vi går løs på selve temaet vil jeg ta opp en ting som vi har behandlet, men ikke tilstrekkelig understreket - nemlig forskjellen mellom leksikalsk og dynamisk binding av variable i lisp. Scheme bruker alltid leksikalsk binding, men ser vi på omegnsmodellen og hvordan scheme beregner uttrykk kommer vi enkelt til dynamisk binding. Den viktige detaljen er følgende
Alle uttrykk får en verdi når de beregnes. Et lambda-uttrykk har som verdi tre informasjonsbiter
Vi bruker denne omegnen ved kall på lambda-uttrykket. Vi hopper fra den omegnen vi er i til omegnen som er i verdien for lambda-uttrykket.
Ved statisk binding er det ingen slik omegn som del av verdien, og kallet på lambda-uttrykket skjer i den omegnen vi er i.
Test ut hva som skjer med bankeksemplet om en har dynamisk binding.
Vi går så til temaet i kapitlet - formelle språk. Kapitlene viser for det første hva endelige tilstands språk, kontekstfrie språk og rekursive språk er - og hvordan en lager program som undersøker om en string er grammatikalsk. For det andre ser vi igjen hvordan en kan bruke Scheme eller Prolog til å lage abstrakte programmer uten å trenge gå i detalj om hvordan ting representeres. Et nytt eksempel på bruk av abstraksjonsbarrierer. Grammatikk programmene gir en oversiktlig og kompakt beskrivelse av teorien for formelle språk.
En liten feil : I programmet grammatikalsk side 234 mangler en anonym variabel
grammatikalsk(X) :- start(Lager),gramm(X,Lager,_).
Uke 43 - føringer
Føringer er den norske oversettelsen av constraints. Kapitlet tar for seg et langt og instruktivt eksempel på programmering med føringer. Vi ser på hvordan en kan gi anvisninger til 3 dimensjonal tolking av et 2 dimensjonalt bilde. Følgende bør dere få med
Vi kan tenke på constraint programming som en videreutvikling av Prolog. Der gir klausulene lokale krav og Prolog eksekveringen prøver å finne global løsning. Dette er videreutviklet i constraint programming som dere kan lese om her. En tutorial finnes også.
Uke 44 - læring
Også et større eksempel.
Vi repeterer kontinuasjoner.Tenk spesielt på hvordan en bruker kontinuasjoner ved et rekursivt program. Prøv med
(define (fakultet n) (if (= n 0) 1 (* n (fakultet (- n 1)))))
(fakultet 10)
Uke 45 - parallelle prosesser
Interessant kapittel med mye nytt stoff. Vi bruker dette for å få litt mer avstand til semantikken for lisp og prolog. Vi ser hvordan parallelitet kan innføres i scheme uten å måtte endre spesielt på språket. I prolog er det sekvensielle brukt på en mer vesentlig måte ved kontrollstrukturene. Vi lærer oss parlog for å si noe mer om hvordan prolog-programmer virker.
Bruk uka til å repetere prolog.
Uke 46 - Common Lisp
Den vesentlige forskjellen mellom Scheme og Common Lisp i verdiene til symboler. I Scheme har et symbol bare en verdi - uansett om symbolet står for et tall eller en funksjon eller noe annet. I Common Lisp har ethvert symbol (minst) 5 aspekter. Disse får du tilgang til ved
Se hvordan du først kan legge inn verdi og funksjoner ved å bruke SETQ og DEFUN. I Common Lisp finnes en svært generell konstruksjon SETF for å endre verdier.
I praksis er det en stor forskjell mellom det lille undervisningsspråket Scheme og det store programmeringsspråket Common Lisp.
Ellers regner vi gamle eksamensoppgaver. Her er den fra i fjor.