COMP90048 问题求解

研讨会将部分通过提问来强化讲座中的材料您可以将其应用于小型编程任务。
为了充分利用每个研讨会,您应该阅读并尝试研讨会前的练习。我们鼓励您提出问题,
讨论并积极参与研讨会。你投入的越多研讨会,你会从中得到更多。讲习班练习将通过Grok提供,因此可以即使您不在澳大利亚,也要承担。的示例解决方案每套讲习班练习也将通过Grok提供。大多数编程问题都有不止一个正确答案;你的即使答案和样本溶液不同,也可能是正确的。Lecture 0
Subject Introduction
OMP90048 Declarative ProgrammingSubject

1. Introduction

Welcome to Declarative ProgrammingContact information is available from the LMS.There will be two pre-recorded one-hour lectures per week, plus one liveone-hour practical meeting for questions, discussion, and demonstrations.There will be eleven one-hour workshops (labs), starting in week 2.You should have already been allocated a workshop. Please check yourpersonal timetable after the lecture.COMP90048 Declarative Programming Lecture 0 – 1 / 16Subject IntroductionGrokWe use Grok to provide added self-paced instructional material, exercises,and self-assessment for both Haskell and Prolog.You can access Grok by following the link from the subject LMS page.If you are unable to access Grok or find that it is not working correctly,please emailfrom your university email account and explain the problem.If you have questions regarding the Grok lessons or exercises, please post amessage to the subject LMS discussion forum.COMP90048 Declarative Programming Lecture 0 – 2 / 16Subject Introduction

2.Workshops

The workshops will reinforce the material from lectures, partly by askingyou to apply it to small scale programming tasks.To get the most out of each workshop, you should read and attempt theexercises before your workshop. You are encouraged to ask questions,discuss, and actively engage in workshops. The more you put intoworkshops, the more you will get out of them.Workshop exercises will be available through Grok, so they can beundertaken even if you are not present in Australia. Sample solutions foreach set of workshop exercises will also be available through Grok.Most programming questions have more than one correct answer; youranswer may be correct even if it differs from the sample solution.NOTEIf your laptop can access the building’s wireless network, you will be ableto use Grok, giving you access to Prolog and Haskell. If your laptopcannot access the building’s wireless network, then you will be able to testyour Haskell or Prolog code if you install the implementations of thoselanguages on your machine yourself. For both languages this is typicallyfast andsimple.
COMP90048 Declarative Programming Lecture 0 – 3 / 16SubjectIntroduction

3.Resources

The lecture notes contain copies of the slides presented in lectures, plussome additional material.All subject materials (lecture notes, workshop exercises, projectspecifications etc) will be available online through the LMS.The recommended text (which is available online)isBryan O’Sullivan, John Goerzen and Don Stewart: Real world Haskell.Other recommended resources are listed on the LMS.COMP90048 Declarative Programming Lecture 0 – 4 / 16Subject Introduction
Academic IntegrityAll assessment for this subject is individual; what you submit forassessment must be your work and your work alone.It is important to distinguish project work (which is assessed) fromtutorials and other unassessed exercises.We are well aware that there are many online sources of material forsubjects like this one; you are encouraged to learn from any online sources,and from other students, but do not submit for assessment anything thatis not your work alone.Do not provide or show your project work to any other student.Do not store your project work in a public Github or other repository.We use sophisticated software to find code that is similar to othersubmissions this year or in past years. Students who submit anotherperson’s work as their own or provide their work for another student tosubmit in whole or in part will be subject to disciplinary action.COMP90048 Declarative Programming Lecture 0 – 5 / 16Subject IntroductionHow to succeedDeclarative programming is substantially different from imperativeprogramming.Even after you can understand declarative code, it can take a while beforeyou can master writing your own.If you have been writing imperative code all your programming life, you willprobably try to write imperative code even in a declarative language. Thisoften does not work, and when it does work, it usually does not work well.Writing declarative code requires a different mindset, which takes a whileto acquire.This is why attending the workshops, and practicing, practicing andpracticing some more are essential for passing the subject.COMP90048 Declarative Programming Lecture 0 – 6 / 16SubjectIntroductionSources ofhelpDuring contact hours:Ask me during or after a lecture (not before).Ask the demonstrator in your workshop.Outside contact hours:The LMS discussion board (preferred: everyone can see it)Email (if not of interest to everyone)Attend my consultation hours (see LMS for schedule)Email to schedule an appointmentSubject announcements will be made on the LMS.Please monitor the LMS for announcements, and the discussion forum fordetailed information. Read the discussion forumbefore asking questions;questions that have already been answered will not be answered again.COMP90048 Declarative Programming Lecture0 – 7 / 16Subject IntroductionObjectivesOn completion of this subject, students should be able to:apply declarative programming techniques;write medium size programs in a declarative language;write programs in which different components use different languages;select appropriate languages for each component task in a project.These objectives are not all of equal weight; we will spend almost all ofour time on the first two objectives.COMP90048 Declarative Programming Lecture 0 – 8 / 16Subject IntroductionContentIntroduction to logic programming and PrologIntroduction to constraint programmingIntroduction to functional programming andHaskellDeclarative programming techniquesTools for declarative programming, such as debuggersInterfacing to imperative language codeThis subject will teach you Haskell and Prolog, with an emphasis onHaskell.For logistical reasons, we will begin with Prolog.COMP90048 Declarative Programming Lecture 0 – 9 / 16Subject Introduction
Why Declarative ProgrammingDeclarative programming languages are quite different from imperative andobject oriented languages.They give you a different perspective: a focus on what is to be done,rather than how.They work at a higher level of abstraction.They make it easier to use some powerful programming techniques.Their clean semantics means you can do things with declarativeprograms that you can’t do with conventional programs.The ultimate objective of this subject is to widen your horizons and thusto make you better programmers, and not just when using declarativeprogramming languages.COMP90048 Declarative Programming Lecture 0 – 10 / 16Subject IntroductionImperative vs logic vs functional programmingImperative languages are based on commands, in the form of instructionsand statements.Commands are executed.Commands have an effect, such as to update the computation state,andlater code may depend on this update.Logic programming languages are based on finding values that satisfy a setof constraints.Constraints may have multiple solutions or none at all.Constraints do not have an effect.Functional languages are based on evaluating expressions.Expressions are evaluated.Expressions do not have an effect.COMP90048 Declarative Programming Lecture 0 – 11 / 16SubjectIntroductionSide effectsCode is said to have a side effect if, in addition to producing a value, italso modifies some state orhas an observable interaction with callingfunctions or the outside world. For example, a function mightmodify a global or a staticvariable,modify one of its arguments,raise an exception (e.g. divide by zero),write data to a display, file or network,read data from akeyboard, mouse, file or network, orcall othersideeffectingfunctions.NOTEReading from a file is a side effect because it moves the current position inthe file being read, so that the next read from that file will get somethingelse.
COMP90048 Declarative Programming Lecture 0 – 12 /16SubjectIntroductionAn example: destructive updateIn imperative languages, the natural way to insert a new entry into a tableis to modify the table in place: a side-effect. This effectively destroys theold table.In declarative languages, you would instead create a new version of thetable, but the old version (without the new entry) would still be there.The price is that the language implementation has to work harder torecover memory and to ensure efficiency.The benefit is that you don’t need to worry what other code will beaffected by the change. It also allows you to keep previous versions, forpurposes of comparison, or for implementing undo.The immutability of data structures also makes parallel programmingmuch easier. Some people think that programming the dozens of coresthat CPUs will have in future is the killer application of COMP90048 Declarative Programming Lecture 1 – 12 / 20Introduction to Logic ProgrammingDisjunctionGoals can be combined with disjunction (or) as well as conjunction (and).Disjunction is written “;” and used as an infix operator. Conjunction(“,”) has higher precedence (binds tighter) than disjunction, butparentheses can be used to achieve the desired precedence.Who are the children of Queen Elizabeth or Princess Diana??- parent(queen_elizabeth, X) ; parent(princess_diana,
COMP90048 Declarative Programming Lecture 1 – 13 / 20Introduction to Logic ProgrammingNegationNegation in Prolog is written “+” and used as a prefix operator. Negationhas higher (tighter) precedence than both conjunction and disjunction. Besure to leave a space between the + and an open parenthesis.Who are the parents of Prince William other than Prince Charles?- parent(X, prince_william), + X = prince_charles.X = princess_diana.prince_charles to referto Barack Obama, and the predicate symbol parent to refer to the notion“succeeded by as US President”. However, any programmer using thisinterpretation, or pretty much any interpretation other than the obviousone, would be guilty of using a horribly misleading programming style.Terms using non-meaningful names such as f(g, h) do not lead readersto expect a particular interpretation, so these can have many differentnon-misleading interpretations.COMP90048 Declarative Programming Lecture 3 – 1 / 21Logic and ResolutionTwo views of predicatesAs the name implies, the main focus of the predicate calculus is onpredicates.You can think of a predicate with n arguments in two equivalent ways.You can view the predicate as a function from all possiblecombinations of n terms to a truth value (i.e. true or false).You can view the predicate as a set of tuples of n terms. Every tuplein this set is implicitly mapped to true, while every tuple not in thisset is implicitly mapped to false.The task of a predicate definition is to define the mapping in the firstview, or equivalently, to define the set of tuples in the secondview.COMP90048 Declarative Programming Lecture 3 – 2 / 21Logic and ResolutionThe meaning of clausesThe meaning of the clausegrandparent(A, C) :- parent(A, B), parent(B, C).is: for all the terms that A and C may stand for, A is a grandparent of C ifthere is a term B such that A is a parent of B and B is a parent of C.In mathematical notation:?A?C : grandparent(A,C)← ?B : parent(A,B) ∧ parent(B,C)The variables appearing in the head are universally quantified over theentire clause, while variables appearing only in the body are existentiallyquantified over the body.NOTE is “forall”, the universal quantifier, while ? is “there exists”, theexistential quantifier. The sign ∧ denotes the logical “and” operation,while the sign ∨ denotes the logical “or” operation, and the sign ? denotesthe logical “not” operation.COMP90048 Declarative Programming Lecture 3 – 3 / 21Logic and ResolutionThe meaning of predicate definitionsA predicate is defined by a finite number of clauses, each of which is in theform of an implication. A fact such as parent(queen_elizabeth,prince_charles) represents this implication:AB : parent(A,B)←
(A = queen_elizabeth ∧ B = prince_charles)To represent the meaning of the predicate, create a disjunction of thebodies of all the clauses:?A?B : parent(A,B)←(A = queen_elizabeth ∧ B = prince_charles) ∨(A = prince_philip ∧ B = prince_charles) ∨(A = prince_charles ∧ B = prince_william) ∨(A = prince_charles ∧ B = prince_harry) ∨(A = princess_diana ∧ B = prince_william) ∨(A = princess_diana ∧ B = prince_harry)NOTEObviously, this definition of the parent relationship is the correct one onlyif you restrict the universe of discourse to this small set of people.COMP90048 Declarative Programming Lecture 3 – 4 / 21Logic and Resolution
The closed world assumptionTo implement the closed world assumption, we only need to make theimplication arrow go both ways (if and only if):(A = queen_elizabeth ∧ B = prince_charles) ∨(A = prince_philip ∧ B = prince_charles) ∨(A = prince_charles ∧ B = prince_william) ∨(A = prince_charles ∧ B = prince_harry) ∨(A = princess_diana ∧ B = prince_william) ∨(A = princess_diana ∧ B = prince_harry)This means that A is not a parent of B unless they are one of the listedcases.Adding the reverse implication this way creates the Clark completion ofthe program.COMP90048 Declarative Programming Lecture 3 – 5 / 21Logic and ResolutionSemantics of logic programsA logic program P consists of a set of predicate definitions. The semanticsof this program (its meaning) is the set of its logical consequences asground atomic formulas.A ground atomic formula a is a logical consequence of a program P if Pmakes a true.A negated ground atomic formula ?a, written in Prolog as +a, is alogicalconsequence of P if a is not a logical consequence of P.For most logic programs, the set of ground atomic formulas it entails isinfinite (as is the set it does not entail). As logicians, we do not worryabout this any more than a mathematician worries that there are aninfinite number of solutions to a + b = c.COMP90048 Declarative Programming Lecture 3 – 6 / 21Logic and ResolutionFinding the semantics
WX:codehelp

评论

暂无评论