verdi_neruda

Verdi Neruda - Meta-interpreter collection for Prolog.
Release 1.0

Copyright (c) 2010 Victor Lagerkvist. All Rights Reserved. Verdi Neruda is free software. You can redistribute it and/or modify it under the terms of the simplified BSD license.

CONTENTS

  1. License

  2. About

  3. Verdi Neruda web site

  4. Installation and running

  5. Examples

  6. Authors

  7. LICENSE

Copyright 2010 Victor Lagerkvist. All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

  1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

  2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ``AS IS’’ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

The views and conclusions contained in the software and documentation are those of the authors and should not be interpreted as representing official policies, either expressed or implied, of the copyright holders.

  1. ABOUT

Verdi Neruda is a meta-interpreter collection for Prolog. Or, to be more precise, for a Prolog like language. Or, to be pedantically precise to the point that you are annoying people, it’s not really a meta-interpreter collection at all since the interpreters themselves aren’t interpreting the language that they are written in. Let’s just say that it is a collection of interpreters for a logic programming language very much like pure Prolog with negation as finite failure.

Verdi Neruda is written entirely in Logtalk and compatible with most major Prolog systems. The name is sadly not a subtle wordplay or an acronym, but was generated by a computer with the help of a soundex algorithm. The purpose of the interpreter suite was to compare top-down methods to bottom-up methods and how resolution tree search rules affected performance and completeness. In the top-down family we find such interpreters as the long-time standing champion depth-first, its slow but orderly brother breadth-first and the youngster iterative deepening. A best-first framework can be found a stone throw away. With it it’s possible to define interpreters that use greedy best-first search as well as A* search.

In the bottom-up camp we find an interpreter that uses a semi naive fixpoint construction. Since bottom-up interpreters by their very nature are not goal oriented a transformation technique called magic transformation is used on logic programs before any inferences are made. This technique allows the interpreter to only generate the facts that a top-down interpreter would have used on the same logic program.

A shell akin to a Prolog top loop is also included. It has commands both for proving goals with an interpreter of choice and for benchmarking logical inferences. If Verdi Neruda is run with a Prolog system that supports statistics/2 it’s possible to obtain statistics such as CPU-time as well.

  1. VERDI NERUDA WEB SITE

Visit the Verdi Neruda GitHub www-page at:

http://joelbyte.github.com/verdi-neruda/

  1. INSTALLATION AND RUNNING

Verdi Neruda requires Logtalk 2.40.0 or a later version.

To use the snapshot of Verdi Neruda bundled with Logtalk:

  • Start Logtalk.

  • Type {verdi_neruda(loader)}. (Including .).

To use the latest version of Verdi Neruda, fetch the latest source code, either as an archive or from the git repository, extract it to a directory of your choice, and:

  • Start Logtalk from that directory.

  • Type {loader}. (Including .). If everything went according to the plan you should be greeted by the welcoming message. If you replace the bundled version with the new one, you can use in alternative the steps above.

  1. EXAMPLES

Follow the previous instructions to get everything up and running. First we’re going to run some predefined programs in the included databases. Begin by typing databases. from the shell - this should print a list of the currently loaded databases. The demo database demodb should be included in the list. Next type listing(demodb). to print the contents of the database. The output should look something like:

append([],A,A) if
    true.
append([A|B],C,[A|D]) if
    append(B,C,D).
.
.
.

Which means that the append/3 program is loaded and ready for action. Next we need to decide which interpreter to use. Fortunately the shell does not leave much to the imagination - as might be expected, the interpreters. command prints the currently loaded interpreters. The list should look like:

dfs_interpreter
bfs_interpreter
iddfs_interpreter(A)
bup_interpreter
a_star_interpreter(A)

The variables means that the interpreters are parametric objects and that additional information is needed in order to run them. The iddfs-interpreter needs to know the increment and the A*-interpreter needs to know what weight should be used when calculating the cost of nodes. To start with let’s use the dfs-interpreter and do something exciting, namely appending two lists!

prove(dfs_interpreter, append([a,b], [c,d], Xs), demodb).

The prove command takes three arguments. The first is a interpreter, the second the goal that shall be proved and the last the database that the clauses are derived from.

To accomplish the same thing with the iddfs-interpreter with an increment of 1 we need only type

prove(iddfs_interpreter(1), append([a,b], [c,d], Xs), demodb).

The shell also has support for counting logical inferences. To compare the dfs- and iddfs-interpreter with the append program we could write:

benchmark(dfs_interpreter, append([a,b,c,d],[e,f], Xs), demodb).  ->
dfs_interpreter inferences: 5

benchmark(iddfs_interpreter(1), append([a,b,c,d],[e,f], Xs), demodb).
-> iddfs_interpreter(1) inferences: 15

For more information regarding the built in shell commands consult the ‘help.’ command.

  1. AUTHORS

The bulk of Verdi Neruda was written by Victor Lagerkvist during his bachelor thesis at Linköping university in the spring of 2010. Paulo Moura also helped a great deal during the later stages of development, especially with regards to compatibility between various Prolog systems.