Programming in Tabled Prolog (very) DRAFT

1 (original) (raw)

Next: Contents

David S. Warren

Department of Computer Science SUNY @ Stony Brook Stony Brook, NY 11794-4400, U.S.A.

July 31, 1999

• Contents
• Background and Motivation
• Introduction to Prolog
  • Prolog as a Procedural Programming Language
    * Assign-once Variables
    * Nondeterminism
    * Prolog execution as the execution of multiple machines
    * Executing Programs in XSB
    * The Scheduling of Machine Execution in Prolog
  • Grammars in Prolog
  • Prolog as a Database Query Langauge
  • Deductive Databases
  • Summary
• Tabling and Datalog Programming
  • XSB tabled execution as the execution of concurrent machines
  • More on Transitive Closure
  • Other Datalog Examples
  • Some Simple Graph Problems
  • Genome Examples
  • Inferring When to Table
    * On the Complexity of Tabled Datalog Programs
  • Datalog Optimization in XSB
• Grammars
  • An Expression Grammar
  • Representing the Input String as Facts
  • Mixing Tabled and Prolog Evaluation
  • So What Kind of Parser is it?
  • Building Parse Trees
  • Computing First Sets of Grammars
  • Linear Parsing of LL(k) and LR(k) Grammars
  • Parsing of Context Sensitive Grammars
• Automata Theory in XSB
  • Finite State Machines
    * Intersection of FSM's
    * Epsilon-free FSM's
    * Deterministic FSM's
    * Complements of FSM's
    * Minimization of FSM's
    * Regular Expressions
  • Push-Down Automata
• Dynamic Programming in XSB
  • The Knap-Sack Problem
  • Sequence Comparisons
  • ??
• HiLog Programming
  • Generic Programs
  • Object Centered Programming in XSB with HiLog
• Debugging Tabled Programs
• Aggregation
  • Min, Max, Sum, Count, Avg
  • BagReduce and BagPO
  • Recursive Aggregation
    * Shortest Path
    * Reasoning with Uncertainty: Annotated Logic
    * Longest Path
  • Scheduling Issues
  • Stratified Aggregation
• Negation in XSB
  • Stratified Negation
  • Approximate Reasoning
  • General Negation
• Meta-Programming
  • Meta-Interpreters in XSB
    * A Metainterpreter for Disjunctive Logic Programs
    * A Metainterpreter for Explicit Negation
  • Abstract Interpretation
    * AI of a Simple Nested Procedural Language
• XSB Modules
• Handling Large Fact Files
  • Compiling Fact Files
  • Dynamically Loaded Fact Files
  • Indexing Static Program Clauses
  • Bibliographic Notes
• Table Builtins
• XSB System Facilities
• Bibliography
• About this document ...

David S. Warren
1999-07-31