Lambda the Ultimate The Programming Languages Weblog - join today!

Home

FAQ

Feedback

Departments

Discussions

(new topic)

Language Evaluation

PL Courses

Research Papers

Design Docs

Quotations

Genealogical Diagrams

Members Join Now Login

logic/declarative

P# - Prolog compiler for .Net

Yet another PL targetting the .Net platform: P# is a compiler which facilitates interoperation between a concurrent superset of the Prolog programming language and C#. This enables Prolog to be used as a native implementation language for Microsoft's .NET platform. P# compiles a linear logic extension of Prolog to C# source code. How's the port of Mercury to .Net coming along? Posted to logic/declarative by Chris Rathman on 5/9/04; 9:27:49 PM Discuss (2 responses)

Spreadsheet structure discovery

"structure discovery" denotes the recovery of structure, such as the grouping of cells, that was intended by a spreadsheet's author but is not explicit in the spreadsheet. A curious paper - includes a brief into to Prolog - that suggests a possible future direction for spreadsheet-like languages with "intelligent" monitors. Posted to logic/declarative by andrew cooke on 5/7/04; 8:06:22 AM Discuss (2 responses)

miniKanren: A declarative applicative logic programming system

KANREN is a declarative logic programming system with first-class relations, embedded in a pure functional subset of Scheme. The system has a set-theoretical semantics, true unions, fair scheduling, first-class relations, lexically-scoped logical variables, depth-first and iterative deepening strategies. The system achieves high performance and expressivity without cuts. When you see who are the people behind this, you'll realize why you really must take a close look. Posted to logic/declarative by Ehud Lamm on 5/6/04; 2:58:22 AM Discuss (2 responses)

Prolog and Mercury Compared
A short high level comparison. Posted to logic/declarative by Ehud Lamm on 5/5/04; 12:24:56 AM Discuss (4 responses)

The Logic Programming Paradigm and Prolog

Another useful find from Apt's home page. This is a nice (but basic) tutorial on Prolog programming, and I guess most LtU readers are already familiar with the topics covered. There are some nice examples (including type assignment in TLC), and even a short discussion of high order and meta programming techniques in Prolog. Posted to logic/declarative by Ehud Lamm on 3/27/04; 4:40:26 AM Discuss (8 responses)

K.R. Apt: Principles of Constraint Programming

Apt's book Principles of Constraint Programming, Cambridge University Press (2003) sounds interesting, but I haven't read it. However, on Apt's web site you can find this very thorough set of slides (279 pp.) which are worth a look. Bear in mind, this is a large file to download (~2MB)! I have a vague recollection of seeing these slides before. If this is a second time these slides are mentioned here, I apologize. Posted to logic/declarative by Ehud Lamm on 3/26/04; 12:40:37 PM Discuss (1 response)

TCLP is a type checker for Prolog dialects

TCLP is a type checker for Prolog dialects. It is written in SICStus Prolog. Its goal is to statically trap programming errors like illegal arguments used in a call for a predicate or illegally built data structures with respect to a given typing for function symbols or predicates. TCLP is also capable of type inference for user predicates. Supported dialects include ISO-Prolog, GNU-Prolog, and SICStus Prolog. Posted to logic/declarative by Patrick Logan on 1/27/04; 6:23:16 AM Discuss

Learn Prolog Now!

Learn Prolog Now!. Patrick Blackburn, Johan Bos and Kristina Striegnitz We wanted to do two things with this course. First, we wanted to provide a text that was relatively self contained, a text that would permit someone with little or no knowledge of computing to pick up the basics of Prolog with the minimum of fuss. We also wanted the text to be clear enough to make it useful for self study. We believe that if you read the text, and do the associated exercises, you will gain a useful partial entry to the world of Prolog. Seems nice enough (via Keith). Posted to logic/declarative by Ehud Lamm on 1/11/04; 3:21:44 AM Discuss

Logic Programming in the Context of Multiparadigm Programming: The Oz Experience

Peter Van Roy mentioned this paper of which he is coauthor in the LtU recent discussion group thread on language design. This detailed paper (~50 pp.) provides a technical introdcution and survey of Oz. It is a bit too long for casual reading, but many of the sections can be read independently, if you are willing to miss out on some of the details. Some of the sections that should interest LtU readers are: (4) Concurrent logic programming; (7) The Oz exection model (esp. 7.4 - Computation spaces); and sections (8) and (9) that provide background for Oz project and language design approach. Posted to logic/declarative by Ehud Lamm on 12/7/03; 5:46:59 AM Discuss

1983-1993: The Wonder Years of Sequential Prolog Implementation

Peter directed me to this paper of his, in reply to a question following his very interesting post regarding the history of Prolog. If you are interested in how Prolog is implemented (WAM and the like), you should definitely read this paper. But even if the implementation details don't really interest you, the paper is worth a look, since it gives insights on the history of Prolog systems, and some useful clues about the semantics of Prolog. The discussion of tail call optimizations (called "last call optimization" in the paper) is interesting. From what I remember (it was a while ago that I checked) Prolog doesn't mandate this. Strange for a language so recursion oriented. Figure 1 showing the correspondence between logical and imperative concepts, is used in the presentation of the WAM, but is also a nice summary of the different semantic uses of the major Prolog constructs. Integrating constraint solving inside Prolog is also discussed. Posted to logic/declarative by Ehud Lamm on 10/24/03; 3:34:56 PM Discuss (1 response)

A Revolution in Logic?

I am not sure of the implications of this idea for programming languages. So I'll turn it over to LtU readers to inform me. Frege's formulation of first-order logic contains a fundamental error. It is manifested already in his formation rules. And this same virus has infected all the subsequent formulations and versions of first-order logic... The real ground floor of the edifice of logic... is Independence-Free (IF) first-order logic. Posted to Logic/Declerative by Patrick Logan on 10/13/03; 12:42:02 PM Discuss (5 responses)

A Tutorial on Proof Theoretic Foundations of Logic Programming

Bruscoli, Paola and Guglielmi, Alessio. A Tutorial on Proof Theoretic Foundations of Logic Programming. Invited tutorial at ICLP '03. Abstract logic programming is about designing logic programming languages via the proof theoretic notion of uniform provability. It allows the design of purely logical, very expressive logic programming languages, endowed with a rich meta theory. This tutorial intends to expose the main ideas of this discipline in the most direct and simple way. It seems there's no escaping Gentzen on LtU these days... This is a nice (but all too short) tutorial on the connection between logic programming and proof theory. Yes, Horn clauses are mentioned I am sure LP fans will not be amused by the fact that unification plays such a small role in this paper, but that's the way it is... Posted to Logic/Declerative by Ehud Lamm on 10/13/03; 3:54:59 AM Discuss

The SOUL Logic Meta Programming Tool

SOUL got a brief mention about a year ago in LtU. Given the recent discussion on relational logic and OO, this might be an interesting project to reintroduce. SOUL is short for Smalltalk Open Unification Language. SOUL is an open, reflective logic programming language written in VisualWorks 5i4 and ported to various other Smalltalk environments. The current implementation of SOUL also incorporates the ideas of another Logic Meta-Programming tool that was developed at the Programming Technology Lab (PROG): TyRuBa. More precisely, the current SOUL is extended with the quasiquoting facilities of TyRuBa. New developments in the area of Declarative Meta-Programming at PROG are now made using SOUL. An overview of the foundations of SOUL and TyRuBa and new changes to the language can be found in the documentation section. Posted to Logic/Declerative by Patrick Logan on 10/8/03; 5:23:26 PM Discuss

Why don't more people use Prolog?

Mark Watson asks on his blog why more people don't use Prolog. The ultimate high programmer productivity programming language (for some programming tasks) is Prolog. The link for this article is for a very high quality, free, LGPL licensed Prolog system that works well embedded in C/C++ applications, interactive experimentation, or turnkey pure-Prolog applications: Swi-Prolog. I started thinking more about Prolog yesterday when I posted to Slashdot (on Japan's new multi-year build a super smart robot project). Japan's 5th generation project was based on Prolog-like languages. Posted to Logic/Declerative by Patrick Logan on 9/3/03; 11:53:04 AM Discuss (14 responses)

Term rewriting system for code generation, and its termination analysis

A short talk presented on June 22, 2003 at the Eighteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2003). June 22-25, 2003. Ottawa, Canada. We describe an applicative order term re-writing system for code generation, and its application for efficient realizations of median filters as decision trees. We further describe a polynomial time termination analysis to prove termination of the median filter generating rules. The systems are implemented in the pure functional subset of Scheme. The full source code is available from this site. Of specific interest is the discussion on termination analysis. More info on the unification algorithm can be found here. Instead of discussing the details, let me make a more general observation. This example explores two interesting uses of linguistic abstraction: optimal code generation and termination analysis. Both "holy grails" for computer science and software engineering. Notice how these goals become more manageable by using the, ultimately linguistic, abstraction of term rewriting, itself a form of declerative programming. These issues are also related to discussions of languages that prohibit recursion and multi-stage programming. Posted to Logic/Declerative by Ehud Lamm on 8/4/03; 3:40:14 AM Discuss

Logic for Computer Science: Foundations of Automatic Theorem Proving

Jean Gallier makes available his complete out-of-print book. This book is designed primarily for computer scientists, and more generally, for mathematically inclined readers interested in the formalization of proofs, and the foundations of automatic theorem-proving. See also: Theorem Proving Haiku Theorem proving and sanity; Oh, my! What a delicate balance Posted to Logic/Declerative by Manuel Simoni on 6/19/03; 9:02:00 AM Discuss (2 responses)

A declarative debugger for Haskell 98

Buddha. Main link is directly to an example in the manual. Declarative languages should use declarative debuggers, no?! disclaimer: the project may include a bit of code i wrote once in the examples directory, but i hope that hasn't influenced my decision to post here! [Psst - people reading just the front page: don't forget to check discussions for other topics] Posted to Logic/Declerative by andrew cooke on 6/5/03; 4:17:00 PM Discuss (1 response)

Unification on Stateless Objects

I remember seeing a design for a language (never implemented) where constraints would determine the class... In other words, when the constraint store realizes your Rectangle has equal sides, the system makes it an instance of Square. Interesting idea. Includes a link to Easel (which doesn't implement unification - see main link). Meanwhile, on another mailing list, Oleg blows everyone away by implementing RefMonads in pure Haskell (nice twist in the next few emails in that thread, too). Posted to Logic/Declerative by andrew cooke on 6/4/03; 4:30:51 AM Discuss (1 response)

Tools for rules

The dust was thick on my copy of the 1985 Clocksin and Mellish classic, Programming Prolog. But Ted Neward, author of the forthcoming book Effective Enterprise Java, brought it all rushing back: expert systems, declarative rules engines, predicate calculus, backward- vs. forward-chaining evaluation. Jon Udell shares some thoughts about rule based programming in the internet age. Jon offers some related links on his weblog, while Phil Windley reflects on XSLT and declerative programming on his. Posted to Logic/Declerative by Ehud Lamm on 5/17/03; 10:29:18 AM Discuss (4 responses)

Book and Course in Constraint Programming and Reasoning
(via comp.lang.prolog) Course site related to a forthcoming Springer book. The site includes lecture slides, labs, and related links. Posted to Logic/Declerative by Ehud Lamm on 3/28/03; 1:14:19 PM Discuss (4 responses)

Logic/Object Oriented Fusion

A frequent question confronting attempts to meld Logic/Declarative and Object Oriented language design is Why? -- Why would OO be needed in the presence of a good system of modules? This collection of links is a starting point to find the answer: Logical Foundations for Declarative Object-Oriented Programming: This paper discusses attempts (and the rationale) in reasoning about Object Oriented programs written in a declarative style. The author's main reasoning is that structuring logic based programs around a set of objects allows reuse and aggregation of existing logical predicates as a way of managing complexity. In my mind, this doesn't really seem all that OO-ish, except for the inheritence. A module system could handle this behavior assuming it could inherit methods from a parent module and be used to dynamically dispatch to the correct predicate. State and message sending semantics are not implemented in this approach. Object Oriented First Order Logic: This paper deals with the unwieldy nature of First Order Logic (FOL), and reasons about the efficacy of using the Object Oriented paradigm to manage the complexity. While the notation looks reasonable, I could find no sample implementation so it's hard to say how useful it is in practice. Work is continuing on this project. FLORA: The Secret of Object-Oriented Logic Programming discusses an object-oriented extension to F-Logic notation, built on top of XSB. This has some fascinating ramifications, including the notion of structural inheritance and behavioral inheritance. Structural inheritance refers to inheritance of signatures (read "interfaces"), while Behavioral refers to implementation inheritance (read "subclassing"). They seem to have moved on to FLORA-2. What I do not find are good papers about whether the benefits of the OO structuring paradigm provide any improvement over a system of modules. I suspect that a strong module system, such as the PLT module system, would probably be sufficient on its own. Posted to Logic/Declerative by Brent Fulgham on 3/14/03; 4:58:37 PM Discuss (6 responses)

The O'Ciao Approach to OO Logic Programming

Angel Pineda and Francisco Bueno. The O'Ciao Approach to Object Oriented Logic Programming One thing you see periodically among the various logic languages (and specifically Prolog) is the implementation of an Object Oriented layer. The success of these efforts seem largely unused by most Prolog developers. LogTalk is perhaps the best-known and highest quality implementation of an "after market" OO system for Prolog. One thing most of these efforts share (in my biased opinion) is a somewhat unnatural feeling syntax, and a sort of ad-hoc approach to the language extension (much like Perl's OO notation). Another glum reality is that these extensions often add much overhead, harming performance and executable size. In contrast, this paper outlines modifications made to the Ciao Prolog system that seems to provide a better syntax while achieving good performance. Examples: Calling methods through the regular module system: X:goal 0.0939000 ms mod:goal 0.0003627 ms Calling methods using OO method dispatch: X:goal 0.0120500 ms obj:goal 0.0004570 ms The OO overhead is fairly insignificant. In general, the CLIPS group at the Technical University of Madrid (UPM) has quite a lot of interesting Logic/CLP related resources and is well worth a visit. Posted to Logic/Declerative by Brent Fulgham on 2/26/03; 4:48:55 PM Discuss (1 response)

Evolution of Indo-European Languages using ASP

Reconstructing the Evolutionary History of Indo-European Languages using Answer Set Programming. Esra Erdem, Vladimir Lifschitz, Luay Nakhleh, and Donald Ringe. PADL'03. The evolutionary history of languages can be modeled as a tree, called a phylogeny, where the leaves represent the extant languages, the internal vertices represent the ancestral languages, and the edges represent the genetic relations between the languages. Languages not only inherit characteristics from their ancestors but also sometimes borrow them from other languages. Such borrowings can be represented by additional non-tree edges. This paper addresses the problem of computing a small number of additional edges that turn a phylogeny into a "perfect phylogenetic network". To solve this problem, we use answer set programming, which represents a given computational problem as a logic program whose answer sets correspond to solutions. Using the answer set solver SMODELS, with some heuristics and optimization techniques, we have generated a few conjectures regarding the evolution of Indo-European languages. The talk presented a good introduction to answer-set programming. The answer-set logic programming is more general than Prolog's built-in Depth-First search. For one thing, the answer-set semantics admits more logical programs (because answer-set solvers find solutions where equivalent Prolog programs just loop). For another, the answer-set semantics makes it very easy to keep adding constraints. The generated conjectures have been subjected to validation by professional linguists. Three conjectures were validated -- one of which wasn't known before. -- Oleg. Posted to Logic/Declerative by Ehud Lamm on 2/17/03; 4:32:05 AM Discuss (1 response)

Answer set programming and plan generation

V. Lifschitz, "Answer set programming and plan generation," Artificial Intelligence, Vol. 138, 2002, pp. 39-54. The idea of answer set programming is to represent a given computational problem by a logic program whose answer sets correspond to solutions, and then use an answer set solver such as SMODELS or DLV to find the answer set to the progrm. This paper can serve as an introudction to answer set programming (ASP). Unfortunately the paper starts with formal definitions that are a bit tiresome to follow. If you haven't encountered ASP before, I suggest starting with the example in section 4. For a high level explanation of ASP, read this. Posted to Logic/Declerative by Ehud Lamm on 2/16/03; 2:18:35 AM Discuss

Constraint Logic Programming: A Survey

J. Jaffar and M. J. Maher. Constraint logic programming: A survey. Journal of Logic Programming, 19/20:503 -- 581, 1994. A comprehensive survey of CLP implementation and applications. Since this is quite a long paper at 84 pages, let me direct you to sections 1.1-1.2 for a useful discussion about the differences between logic programmming and constraint based programming and to sections 12 and 13 for a survey of interesting applications of CLP. These sections are worth reading even if you are not interested enough in the subject to slog through the more technical sections of the paper. Posted to Logic/Declerative by Ehud Lamm on 1/28/03; 10:39:15 AM Discuss

Oleg: Formalization of two Puzzles Involving Knowledge

A Haskell version of a classic puzzle by John McCarthy. The Haskell code is a straightforward encoding of the puzzle, using Haskell's functional programming facilities (including lists and comprehehnsions) to encode a brute force search. It is interesting to note that in a real sense this example shows how to embed logic programming in Haskell, without going to the trouble of embedding a full logic programming language. Posted to Logic/Declerative by Ehud Lamm on 1/27/03; 12:58:43 AM Discuss

Algebra of Logic Programming

Silvija Seres, Michael J. Spivey, C.A.R. Hoare. Algebra of Logic Programming. ICLP'99. November 1999. This is the sequel to the Embedding Prolog into Haskell paper. Three models or serarch strategies are analyzed: a stream model (standard), a matrix model (BFS) and a forest model (the general model). Several algerbraic laws are introduced, and can be proven using the standard techniques used by the functional programming community. Sections 6 and 7 require knowledge of some category theory (mainly monads and the notion of morphisms). Using this framework the authors show that the forest model is indeed more general than the other two models, and shows the morphisms from the forest monad to the stream and matrix monads. Posted to Logic/Declerative by Ehud Lamm on 1/6/03; 3:22:48 AM Discuss (1 response)

Parallel Programming with Logic Languages

Ciancarini, P. Parallel Programming with Logic Languages: a Survey. Comput. Lang., 17(4): 1992. On the negative side,we note that the languages that have abandoned Prolog as a sequential component require a different style of programming. Moreover,stream-based communications are very badly suited for expressing many-to-one interactions. More important,we found that the metaprogramming techniques are commonly used in system programming with logic languages,but they are often inefficient for real applications. A metainterpreter slows execution by a factor of one order of magnitude for each level of interpretation. So these languages are not suitable for serious system applications. Among the languages discussed in this survey are Aurora, Flat Concurrent Prolog, Parlog and DeltaProlog. There are extensive studies of Concurrent Prolog and parallel logic programming in general. This is a fairly short (~32 pp.) survey. The interaction between backtracking and concurrency is quite subtle. Consider this example (from the paper): a(X) :- X>=0 | body1 a(X) :- X<=0 | body2 How is a(0) evaluated? If these were Prolog clauses, if the chosen clause fails (i.e., a solution is not obtained) the other clause is later chosen by backtracking. Conversely, in parallel logic programming an arbitray clause may be chosen, and no backtracking is activated if a committed clause fails in the body. Posted to Logic/Declerative by Ehud Lamm on 12/29/02; 3:03:45 AM Discuss

Search and Imperative Programming

K. Apt, A. Schaerf, Search and Imperative Programming. Proceedings of POPL' 97, ACM, 1997 We augment the expressive power of imperative programming in order to make it a more attractive vehicle for problems that involve search. The proposed additions are limited yet powerful and are inspired by the logic programming paradigm. I came across this paper while looking for a paper by Griswold I wanted to mention here (I was looking for an online copy that doesn't require an ACM Digital Library subscription), and indeed this paper mentions several language features available in Icon. The proposal is basically for a form of goal directed evaluation: nondeterminism in the form of choice points and backtracing. Boolean expressions and statements are mixed, so that a false value indicates failure. The paper contains many code examples that show how the proposed language features help solve various programming problems. It may be interesting to compare the code in the paper with solutions based on other search techniques. Posted to Logic/Declerative by Ehud Lamm on 12/6/02; 3:21:27 PM Discuss (2 responses)

Use of Prolog for Developing a new Programming Language

Use of Prolog for Developing a new Programming Language. Joe Armstrong, Robert Virding and Mike Williams. The Practical Application of Prolog. April 1-3, 1992, London. This paper describes how Erlang was developed. The first implementation of Erlang was as a Prolog interpreter - this paper has the Prolog code for a simple meta-interpreter which was the basis for Erlang. This extremely cool paper shows how Erlang was originally developed on top of a meta-circular Prolog interpreter. Building meta-circular interpreters in Prolog is very easy (if you are into programming languages and don't know how to do this, look up some of the previous references available in the LtU archives). Since Erlang was concieved as a multi-tasking language ("concurrency oriented programming"), the interpreter was extended so that interpretation could be stopped and resumed. This simply required building up a list of subgoals to be evaluated. And this is basically all it took to start experimenting with baby-Erlang! Posted to Logic/Declerative by Ehud Lamm on 11/8/02; 5:55:46 AM Discuss (1 response)

Prolog and Natural-Language Analysis

From the introduction to the book: This book is an introduction to elementary computational linguistics from the point of view of logic programming. The connection between computational linguistics and logic programming has both formal and utilitarian aspects. On the formal side, we shall explore the restricted logical language of definite clauses as a means of expressing linguistic analyses and representations. On the utilitarian side, we shall introduce the logic-programming language Prolog, whose backbone is the definite-clause formalism, as a tool for implementing the basic components of natural-language-processing systems. Now available online. (The idea of parsing as deduction has been mentioned here before.) Posted to Logic/Declerative by Ken Shan on 10/8/02; 2:15:07 PM Discuss (7 responses)

TXL: Tree Transformation Language

Though TXL was mentioned here before, it received very little attention. I always found it interesting, so I decided to mention it again... The TXL programming language is a hybrid functional / rule-based language with unification, implied iteration and deep pattern match. A TXL program consists of an EBNf specifying the structures to be transformed, and a set of structured transformation rules, which are specified by example. The web site suggest several tasks that are appropriate for TXL. These include program analysis and language processing. The program transformation wiki has a nice summary page about TXL. Posted to Logic/Declerative by Ehud Lamm on 10/2/02; 10:58:17 AM Discuss (1 response)

Exploring NLP in Oz/Mozart

The homepage for a course on programming in Oz for computational linguistics. Oz is a multi-paradigm programming language supporting "declarative programming, object-oriented programming, constraint programming, and concurrency." Includes exercises with solutions together with tutorial and documentation references. A nice complement to the main Oz programming text "Concepts, techniques, and models of computer programming" which has some of the most interesting example programs you'll ever see. (Exploring NLP in Oz/Mozart, Torbjörn Lager, 2001) [LTU Posting, The Oz-Mozart Programming System, Author's Homepage ] Posted to Logic/Declerative by jon fernquest on 9/22/02; 2:37:47 AM Discuss (8 responses)

GNU Prolog

"...the novelty of the GNU Prolog compilation scheme is to translate a WAM file into a mini-assembly (MA) file... The corresponding MA code is mapped to the assembly language of the target machine. In order to simplify the writing (i.e. porting) of such translators the instruction set of MA must be simple... the MA language is based on 10 instructions, mainly to handle the control of Prolog and to call a C function ...built on previous systems developed at INRIA, namely wamcc for Prolog and clp(FD) for constraint solving on finite domains...(Quoted from: The GNU Prolog System and its Implementation, Daniel Diaz's Papers, Philippe Codognet's Papers) Now works under windows without Cygwin. For an extensive overview of Prolog see J.R. Fisher's online Prolog tutorial that rivals "The Art of Prolog" [Book Review, Code, Exercise Answers, Citations] in breadth and depth. There is also a Java GNU Prolog, apparently unrelated. Posted to Logic/Declerative by jon fernquest on 9/7/02; 1:12:27 AM Discuss

Embedding Prolog in Haskell

The distinctive merit of the declarative reading of logic programs is the validity of all the laws of reasoning supplied by the predicate calculus with equality.... This paper lists a number of common laws, and proves their validity for the standard (depth-first search) procedural reading of Prolog. They also hold for alternative search strategies, e.g. breadth-first search. Our proofs of the laws are based on the standard algebra of functional programming, after the strategies have been given a rather simple implementation in Haskell. Yet another embedded Prolog. What applications, if any, could these minimalistic, embedded logic programming systems have? Or do they only have academic and pedagogical importance? There are almost too many to list: In the Haskell Hugs98 distribution Roll Your Own in Scheme Schelog Microsoft Prolog (from comp.lang.prolog) embedded in Java Posted to Logic/Declerative by jon fernquest on 8/6/02; 3:05:42 AM Discuss (6 responses)

A Declarative Model for Simple Narratives

A DSL embedded in Prolog for programming narratives. A story consists of a setting and a sequence of episodes. Programs are written by declaring a world model in Prolog clauses. The AI Agent Oriented Programming paradigm provides the logical foundation for modelling human intentions and goal directed behavior as well as the temporal sequencing of events. This DSL might be useful for generating software design Use-Cases automatically given a model of user behavior in a given domain. Others have worked on programming narrative [Survey, Visual Programming with Multi-Perspective Story Agents, Narrative Intelligence], but this is the first open sourced work that I know of. Posted to Logic/Declerative by jon fernquest on 8/6/02; 2:59:44 AM Discuss (3 responses)

Prological Language Processing

A lightweight Prolog-based framework for developing language processors such as pre-processors, front-ends, evaluators, and tools for software modification and analysis. Eliminating dead let clauses from a program is used as a running example. Concise frontends and backends written in concise Prolog parse and unparse the source code of a language into a Prolog representation on which transformations are performed. The first transformation code given for the example is a concise 5 lines. (compare compiler example in the "Art of Prolog", ch 19 ). Higher order logic programming features such as a generic bottom-up traversal predicate allow for even higher levels of abstraction and conciseness. The dead let elimination example is reduced to 2 lines when this predicate is used. An optional soft type system extended with polymorphism is provided. The authors note that "without types the development of language processors gets very tedious. The resulting Prolog programs will just fail too often and too much development time is spent on debugging." The system was written with SWI-Prolog, but is not yet open-sourced. (see also: Formal Syntax and Semantics of Programming Languages: A Laboratory Based Approach Ken Slonneger and Barry L. Kurtz) Posted to Logic/Declerative by jon fernquest on 7/25/02; 12:54:11 AM Discuss (1 response)

The OpenNLP Grok Library
Jon Fernquest posted this link, so I guess you should read his comments. Posted to Logic/Declerative by Ehud Lamm on 7/6/02; 2:08:14 PM Discuss

SQL Limitations

Patrick Logan explains why he doesn't like SQL. As you all know I don't really like language comparisons (I am not the only one), and usually find discussions of language limitations rather boring. But Patrick raises some interesting issues that may interest others. By the way, I don't think the reason for SQL's success is that it was desgined by IBM. SQL (with some additions) survived much better than PL/I, for example, which was designed and promoted by IBM. But this really is not the most important part of Patrick's analysis Posted to Logic/Declerative by Ehud Lamm on 6/13/02; 9:10:00 AM Discuss (3 responses)

AP5: A declaritive language extension to Common Lisp
AP5 is an extension to Common Lisp (in the form of a package) to add a declaritive query based language. Similar to the goals (but not necessarily the implementation or reality) of Prolog and SQL, AP5 adds relations, operations on relations, consistency rules, automation rules and annotations. Posted to Logic/Declerative by Dan Moniz on 5/26/02; 9:56:18 AM Discuss (1 response)

Daniel Friedman: A Poorman's 'Roll Your Own' Logic System
This is this Schemer's view of Logic Programming Systems Related code can be found in Friedman's home page. Combining (maybe we should say embedding) logic programming with Scheme. Seems like a companion to the discussion of OOP in Scheme, mentioned here previously. Posted to Logic/Declerative by Ehud Lamm on 5/22/02; 10:23:10 AM Discuss (6 responses)

Sugar 2.0 tutorial

Don't know if hardware specification languages fall under the guise of programming languages for LtU, but it's always interesting to compare the formalness of these with the looseness of software programming languages. I suppose that the ultimate goal of computer science is to get software engineering up to the same level of rigor. Sugar is a language for the formal specification of hardware. It is used to describe properties that are required to hold of the design under verification. Sugar consists of four layers. The boolean layer is comprised of boolean expressions. The temporal layer consists of temporal properties which describe the relationships between boolean expressions over time. The verification layor consists of directives which describe how the temporal properties should be used by verification tools. Finally, the modeling layer provides a means to model behavior of design inputs, and to declare and give behavior to auxiliary signals and variables. I can't help but think that this has parallels with declarative programming languages and Design by Contract. Posted to Logic/Declerative by Chris Rathman on 5/14/02; 12:57:33 PM Discuss (4 responses)

Semantics-based Filtering: Logic Programming's Killer App?

Gopal Gupta, Hai-Feng Guo, Arthur Karshmer, Enrico Pontelli, Desh Ranjan, Bryan Milligan, N. Datta, O. El Khatib, M. Noamany, and X. Zhou. PADL02, LNCS 2257, pp. 82-100, 2002. The talk was dedicated to semantic filtering: a translation of a document from one formal notation to another while preserving its meaning. Examples are translating: code from Fortran to C; an image from an XWD to the TIFF formats; a database query to a query for a differently-structured database. In a simpler case, semantic filtering is porting, e.g., a C program from Unix to Windows. Thanks, Oleg! Posted to Logic/Declerative by Ehud Lamm on 2/20/02; 3:22:51 AM Discuss (4 responses)

The CSS debate rages on

Mark Pilgrim in a well reasoned argument in favor of using CSS instead of tables for web layout. The debate is not new, but some prominent web developers don't agree. Follow the links from Mark's essay. Let me try and give a language design point of view. Languages are abstraction tools. When you describe something at the appropriate abstraction level, it is easier for you to describe it efficiently and correctly and at the same time your description is easier to understand. Consider a simple for loop. Languages that provide this common looping structure allow the programmer to inform both the compiler and the human reader that the the number of iterations through the loop is known in advance, as opposed to the situation with while loops. This helps optimization, but also helps reading the code and proving it correct. [If you think I am wrong about this, chances are you are used to a language without this distinction, the most prominent example being C.] CSS is a domain specific (declerative) language. It focuses on presentation details. It may be a bad language - I am not analyzing its strengths and weaknesses. Most of the advantages attributed to CSS are the result of this fact. CSS eases maintenance? Of course. The language localizes the presentation details, and separates them from the actual content. It also allows you to specify presentation details using concepts that were deemed appropriate for this task. CSS helps tools understand your site (e.g., tools for the disabled)? Sure. In just the same way as a for loop easier for the compiler to reason about. One of the interesting characteristics of the web is the plethora of domain specific little languages. These languages can explain some of the success of cross-platform browsing, and the abundance of plugins and supporting tools. An important feature of many, if not all, of these languages is that they are easily embeddable inside one another. Indeed, even the specification of tables can be seen as a micro-language inside HTML. Remember: It is all about choosing the appropriate abstraction level. Posted to Logic/Declerative by Ehud Lamm on 2/17/02; 9:30:49 AM Discuss (2 responses)

Curry - A Truly Integrated Functional Logic Language

Curry combines in a seamless way features from functional programming (nested expressions, higher-order functions, lazy evaluation), logic programming (logical variables, partial data structures, built-in search), and concurrent programming (concurrent evaluation of expressions with synchronization on logical variables). Moreover, Curry provides additional features in comparison to the pure languages (compared to functional programming: search, computing with partial information; compared to logic programming: more efficient evaluation due to the deterministic and demand-driven evaluation of functions). Interesting, though it doesn't seem to have had much activity since 2000 or so. See also a discussion here of Mercury, another blend of the logic and functional paradigms. Posted to Logic/Declerative by Bryn Keller on 2/13/02; 4:25:26 PM Discuss

Higher-order transformation of logic programs

It has earlier been assumed that a compositional approach to algorithm design and program transformation is somehow unique to functional programming. With this talk we hope to demonstrate that some of the same techniques and results are applicable to logic programming as well. Presented at the Nottingham Workshop on Generic Programming. This paper uses notions like foldr and program tranformation in the context of Prolog programming (more precisely, Prolog embedded in Haskell). These provably correct transformations can, for example, reduce program run time by introducing an accumulator. Posted to Logic/Declerative by Ehud Lamm on 2/8/02; 8:27:18 AM Discuss

Complexity and expressive power of logic programming

E. Dantsin, T. Eiter, G. Gottlob, and A. Voronkov. Complexity and expressive power of logic programming. ACM Computing Surveys, 33(3):374-425, September 2001. This paper surveys various complexity and expressiveness results on different forms of logic programming. The main focus is on decidable forms of logic programming, in particular, propositional logic programming and datalog, but we also mention general logic programming with function symbols. Next to classical results on plain logic programming (pure Horn clause programs), more recent results on various important extensions of logic programming are surveyed. These include logic programming with different forms of negation, disjunctive logic programming, logic programming with equality, and constraint logic programming. Highly theoretical. The text is, however, largely self-contained and most concepts (e.g., complexity classes) are clearly defined. Like most survey papers this paper is long (~70 pages). The connections between complexity classes and different logics is well known. It is nice to see the connection made even stronger by studying logic programming. Posted to Logic/Declerative by Ehud Lamm on 2/7/02; 8:50:47 AM Discuss

DSLs: A Logical Approach

Making languages bear-able: For I am a bear of very little brain and long words confuse me. [Milne 1926] The premise of this subject is that computers should adapt to the ways of people, and not the other way around. Building DSLs using Prolog. The first lecture contains some motivating examples, and is worth checking out even if you are not a little language fanatic... Posted to Logic/Declerative by Ehud Lamm on 11/24/01; 3:37:43 AM Discuss (1 response)

CML2

CML2 is a configuration system, centered around a domain-specific minilanguage, that I originally wrote to replace the code that currently handles build-option selection for Linux kernels (that is, when you type `make config', `make menuconfig' or `make xconfig'). However, it is designed to be more generally useful for addressing complex configuration problems. CML2 is a little language (actually, a domain specific language!), and is based on ideas from constraint satisfaction. The language design is articulated in a paper that also talks about the experience of implementing CML2 in Python. Posted to Logic/Declerative by Ehud Lamm on 11/9/01; 2:52:51 AM Discuss

Dynamo- Dynamic Logic Programming

(via comp.lang.functional) Dynamo is a language for dynamic logic programming based on a dynamic interpretation of first order logic familiar from Dynamic Predicate Logic or DPL... ...Dynamo programs have a purely declarative dynamic semantics. There are no side effects, and no control features. Dynamo is pure dynamic logic. Because of this logical purity, weakest precondition reasoning for Dynamo is completely straightforward. This seems to be related to hypothetical reasoning languages we mentioned here a long time ago. I didn't really get into the theory, but the example programs on the site seem easy enough to understand... Ken, can you tell us more on this? Posted to Logic/Declerative by Ehud Lamm on 10/30/01; 1:08:22 PM Discuss (6 responses)

Lambda Prolog

What features does lambda Prolog have? polymorphic typing sound unification implicational and universal quantified queries modular programming abstract data types higher-order programming simply-typed lambda-terms unification of lambda-terms You may find this tutorial helpful, though you may prefer to look at some souce code. Much more detailed information can be found in a draft book about lProlog (the inroduction in chpater one is particularly helpful). Thanks to Oleg for pointing these out. Posted to Logic/Declerative by Ehud Lamm on 10/22/01; 9:39:34 AM Discuss (2 responses)

Higher-order logic programming in Prolog

(seen on comp.lang.prolog) This is yet another paper which tells logic programmers what functional programmers have known and practiced for a long time: "higher order" programming is the way to go. How is this paper different from some of the others? First, we point out that call/N is not the way to go, despite its recent popularity as the primitive to use for higher order logic programming. Second, we use standard Prolog rather than a new language. Third, we compare higher order programming with the skeletons and techniques approach. Fourth, we present solutions to some (slightly) more challenging programming tasks. The interaction between higher order programming and some of the unique features of logic programming is illustrated and some important programming techniques are discussed. Finally, we examine the efficiency issue. Posted to Logic/Declerative by Ehud Lamm on 10/16/01; 9:57:32 AM Discuss (1 response)

Typed Prolog

This comp.lang.prolog thread began with a question about Visual Prolog, but evolved into a more interesting discussion on Prolog semantics comparing Mercury and Prolog. The Mercury project document comparing the two languages is well worth reading: If the Prolog code is quite declarative and does not make use of Prolog's non-logical constructions, the job of converting it to Mercury will usually be quite straight forward. However, if the Prolog program makes extensive use of non-logical constructions, conversion may be very difficult, and a direct transliteration may be impossible. Mercury code typically has a very different style to most Prolog code. Posted to Logic/Declerative by Ehud Lamm on 8/13/01; 12:44:51 PM Discuss

Warren's Abstract Machine

In 1983 David H. D. Warren designed an abstract machine for the execution of Prolog consisting of a memory architecture and an instruction set. This design became known as the Warren Abstract Machine (WAM) and has become the de facto standard for implementing Prolog compilers. The book: Warren's Abstract Machine: A Tutorial Reconstruction and slides from lectures on the WAM, are available online. Essential if you are interested in how Prolog can be implemented. Posted to Logic/Declerative by Ehud Lamm on 8/1/01; 10:25:34 AM Discuss (5 responses)

Efficient Prolog: A Practical Guide
I found this link on comp.lang.prolog. Thought I'd archive it here. Posted to Logic/Declerative by Ehud Lamm on 7/8/01; 8:32:51 AM Discuss

Mercury Programming Language

Mercury is a Logic language that doubles as a Functional Programming language. The folks who wrote the language figured out how to blend the declarative syntax with a functional syntax, and managed to do it quite seamlessly. In working with the language, I do get the impression that the static type checking is very tight. If you can get the code to compile, it's close to being a guarantee of correctness. As with most of the languages I study, I used the shapes example to try to get a handle on the type and class mechanisms within the language (mercury version). I got some help from their mailing list along the way. The people on the list were quite helpful and seemed genuinely interested in sharing their appreciation for the language. Posted to Logic/Declerative by Chris Rathman on 4/25/01; 11:49:26 AM Discuss (9 responses)

Meta-interpretation
A book chapter discussing metacircular interpreters etc. Gives a nice survey, and some examples. Among other concepts dicussed is our old favorite, reflection. Seems the other chapters are interesting too, but I haven't read them yet to give an informed opinion. New LtU department! Posted to Logic/Declerative by Ehud Lamm on 4/25/01; 7:31:53 AM Discuss

Prolog Programming A First Course

The course for which these notes are designed is intended for undergraduate students who have some programming experience and may even have written a few programs in Prolog. They are not assumed to have had any formal course in either propositional or predicate logic. At the end of the course, the students should have enough familiarity with Prolog to be able to pursue any undergraduate course which makes use of Prolog I haven't read it all, but the negation as failure discussion seems good for beginners. The advanced features section is useful. These are things (like bagof) that are often overlooked in introductory courses, and are very important. Cuts on the other hand seem to be discussed in not much detail. That's a shame. The general discussion on Prolog and logic programming seems only to be a placeholder. Might be useful none the less. Posted to Logic/Declerative by Ehud Lamm on 2/13/01; 1:41:47 PM Discuss

Prolog tutorial
(via comp.lang.prolog) This seems like a nice tutorial on Prolog programming. It has many examples and seems quite extensive (even discussing NLP). The section on meta-circular interpreters is very nice. Posted to Logic/Declerative by Ehud Lamm on 2/11/01; 1:45:12 PM Discuss

Efficient tree searches in Logic Languages

I've been on the Mercury mailing list for a while, slowing trying to get acquanted with the language. The above post caught my eye since the author makes the claim that searches through XML documents can be done as efficiently in the logic languages as with pointer languages like C - O(1) for neighbors. I certainly think that Prolog (and by extension Mercury) provide some distinct capabilities when it comes to dealing with tree data structures. With XML documents being little more than tree structures - at least when viewed in the DOM manner, the logic languages seem to provide some potential for XML processing (though the author points out some problems with DOM and Logic Languages. My Prolog is rather rusty and I'm still not comfortable enuf with Mercury to comment on the question of efficiency. Be interesting to see if the claim holds up once the author publishes. Posted to Logic/Declerative by Chris Rathman on 12/25/00; 7:00:30 PM Discuss (2 responses)

Prolog Tutorial

Having finished the introduction to Prolog I posted earlier, I though I had a neat way of permuting lists. I was wrong (it had an infinite loop), but it was worth it to find this tutorial which included: perm([X|Y],Z) :- perm(Y,W), takeout(X,Z,W). perm([],[]). which is pretty neat, even if it only works one way (more details here). Anyone have a better implementation (apart from the built-in)? PS It contains much more than that - even some quite involved NLP stuff. Posted to Logic/Declerative by andrew cooke on 12/16/00; 11:07:17 AM Discuss

Logic Programming book

Logic, Programming and Prolog (2ed), by Ulf Nilsson and Jan Maluszynski. The book has been available for 10 years and has been used in a number of courses around the world. The text covers both theoretical aspects of logic programming as well as practical programming in Prolog, and extensions of the logic programming paradigm (e.g. equational logic programming, constraint logic programming, and query-answering in deductive databases). Posted to Logic/Declerative by Ehud Lamm on 12/5/00; 2:59:41 PM Discuss

(Text) Adventures in Prolog
This site shows how (amongst other things) to write text adventures in Prolog. From the little I know of Prolog that sounds like a very sensible thing to do, and it looks like a very friendly introduction. It also reminds me of the first game I played on my first computer (ah, an Oric-1...). Posted to Logic/Declerative by andrew cooke on 11/16/00; 9:45:58 AM Discuss