Transcription
Logic ProgrammingIntroductionMichael GeneserethComputer Science DepartmentStanford UniversityLecture will begin at 1:35 PDT.
Logic Programming (Spoiler Alert)Logic Programming is a style of programming based onSymbolic Logic.Logic Program is a collection of sentences encoded in thelanguage of Symbolic Logic.Logic Programming Language is a specific language forwriting such programs.Logic Programming System is a computer system thatmanages the creation, modification, and execution of logicprograms.
Imperative ProgrammingInputsInterpreterOutputs
Declarative ProgrammingA triangle is a polygonwith 3 sides.e mc2InputsInterpreterOutputs
Runnable SpecificationsSpecificationWhat we believe about the application areaWhat we want to know or to achieve in application areaWith no arbitrary decisionsWith no concern for internal processing detailsRunnableCan be directly interpretedCan be compiled into traditional programs
Runnable SpecificationsA logic programis arunnable specification.
Specialized LanguagesA triangle is a polygonwith 3 sides.
Logic as a Specification LanguageLanguageDeclarative language Highly expressiveOther declarative languages exist but statements in most ofthose languages can be translated to logical form.InterpreterAutomated Reasoners capable of drawing conclusionsCan take advantage of domain-dependent reasonersbut are also capable domain-independent reasoning
Benefits
Programming EaseEasier to create and modify than traditional programsProgrammers can get by with little or no knowledge of thecapabilities of systems executing those programs.Less work. The specification is the program; no need tomake choices about data structures and algorithms.Easier to learn logic programming than traditionalprogramming. Think spreadsheets.Oddly, expert computer programmers often have moretrouble with logic programming than novices.
AgilityAbility to respond to changing circumstances or goals
VersatilityAbility to be used for multiple purposesSample ProgramA person X is the grandparent of a person Z if and only ifthere is a person Y such that X is the parent of Y and Y is theparent of Z.UsesDetermine whether Art is the grandparent of Cal.Determine all of the grandchildren of Art.Compute the grandparents of Cal.Compute all grandparent-grandchildren pairs.
McCarthy’s Example of Versatility
McCarthy’s Example of Versatility
Successes
EngineeringCircuit:xPremises:o (x y) ( x osisTest Generationa z ob x ys (o z) ( o z)c a b
Deductive Databasesq(X) :- p(X,Y) p(X,Z) Y! Zg(X,Z) :- p(X,Y) p(Y,Z)illegal :- p(X,Y) a,b)AnswersNo1fica1ons
Data ntegration EngineSupplier 1Supplier 2Supplier 3Supplier 4Manufacturer 1Manufacturer 2SatisfactionRatingsMarketplaceDataProduct analysis18
Constraint Satisfaction
mples/programsheets/demonstration.html
Business Rules
Computational LawComputational Law is that branch of legal informaticsconcerned with the mechanization of legal reasoning.Automated Compliance ManagementLegal analysis of specific casesPlanning for compliance in specific casesAnalysis of regulations for overlap, consistency, portico/demonstration.html
General Game Playing
General Game es/nineboard/demonstration.html
Non-Successes
Natural Language Processing
Theorem Proving
Japan’s Fifth Generation Project
History
LGP-30
IBM 360
Assembly Language
Higher Level Languages
John McCarthyThe main advantage we expectthe advice taker to have is thatits behavior will be improvablemerely by making statements toit, telling it about its environment and what iswanted from it.- John McCarthy1958
Ed FeigenbaumThe potential use of computers by peopleto accomplish tasks can be “onedimensionalized” into a spectrumrepresenting the nature of the instructionthat must be given the computer to do itsjob. Call it the what-to-how spectrum.At one extreme of the spectrum, the usersupplies his intelligence to instruct themachine with precision exactly how todo his job step-by-step. . At the otherend of the spectrum is the user with hisreal problem. . He aspires tocommunicate what he wants done .without having to lay out in detail allnecessary subgoals for adequateperformance.- Ed Feigenbaum 1974
Alain Colmerauer and Bob Kowalski
This course
Types of Logic ProgrammingTypes of Logic Programming:Database ProgrammingClassical Logic ProgrammingDynamic Logic ProgrammingConstraint SystemsAnswer Set ProgrammingInductive Logic Programming (i.e. Progol)Languages:DatalogPrologEpilogGologProgol
ScheduleMar 29 Introduction31 DatasetsApr 571214QueriesExamplesQuery EvaluationQuery Optimization19212628View DefinitionsQuery OptimizationSimple ExamplesLists, Sets, TreesMay351012Action DefinitionsDynamic SystemsDatabase ionsProject ReportsProject ReportsProject Reports
Mathematical BackgroundSets{a, b, c} {b, c, d} {a, b, c, d}a {a, b, c}{a, b, c} {a, b, c, d}Functions and Relationsf(a, b) cr(a, b, c)
Programming BackgroundCS 106 or equivalent
TeamsComposition3 people each (2 or 4 okay with good reason)Names:Pansy DivisionThe PumamenTeam CamembertMighty BourgeoisieGreedy BastardsRed Hot Chili Peppers/*v*\X Æ A-12Michael Genesereth
GradesNumerical Score10% for each of Assignments 1, 2, 3, 4,550% for the Term ProjectReported GradeBased on numerical score (see above)*No* curve - independent of number of studentsSatisfactory 70% and aboveExtra CreditAdded to score before determining Reported GradeDiscretionary
TextbookSeries Editors: Ronald J. Brachman, Jacobs Technion-Cornell Institute at Cornell TechFrancesca Rossi, AI Ethics Global Leader, IBM Research AIPeter Stone, University of Texas at AustinGENESERETH CHAUDHRISeries ISSN: 1939-4608Introduction to Logic ProgrammingMichael Genesereth, Stanford UniversityVinay K. Chaudhri, Stanford University“In a world where Deep Learning and Python are the talk of the day, this book is aremarkable development. It introduces the reader to the fundamentals of traditional LogicProgramming and makes clear the benefits of using the technology to create runnablespecifications for complex systems.” – Son Cao Tran, Professor in Computer Science, New MexicoState University“Excellent introduction to the fundamentals of Logic Programming. The book is well-writtenand well-structured. Concepts are explained clearly and the gradually increasing complexity ofexercises makes it so that one can understand easy notions quickly before moving on to moredifficult ideas.” – George Younger, student, Stanford UniversityINTRODUCTION TO LOGIC PROGRAMMING“This is a book for the 21st century: presenting an elegant and innovative perspective on logicprogramming. Unlike other texts, it takes datasets as a fundamental notion, thereby bridgingthe gap between programming languages and knowledge representation languages; and ittreats updates on an equal footing with datasets, leading to a sound and practical treatment ofaction and change.” – Bob Kowalski, Professor Emeritus, Imperial College LondonAbout SYNTHESISstore.morganclaypool.comMORGAN & CLAYPOOLThis volume is a printed version of a work that appears in the SynthesisDigital Library of Engineering and Computer Science. Synthesisbooks provide concise, original presentations of important research anddevelopment topics, published quickly, in digital and print formats.Ronald J. Brachman, Francesca Rossi, and Peter Stone, Series Editors
http://cs151.stanford.edu
Series Editors: Ronald J. Brachman, Jacobs Technion-Cornell Institute at Cornell Tech Francesca Rossi, AI Ethics Global Leader, IBM Research AI Peter Stone, University of Texas at Austin Introduction to Logic Programming Michael Genesereth, Stanford University Vinay K. Chaudhri, Stanford University "!is is a book for the 21st century: presenting an elegant and innovative perspective on logic
