Purifying Prolog, Monads?

Appeared in Volume 9/1, February 1996

dsmith@borg.cs.waikato.ac.nz
Don Smith
29th May 1995

Has anyone tried to apply the ideas of monads and single-threading from functional programming to LP?

tarau@cs.sfu.ca
Paul Tarau
1st June 1995

Actually, some effort has recently been put into monadic constructs in LP and on a cleaner handling of state information. Have a look at the paper:
ftp://clement.info.umoncton.ca:/pub/OtherPapers/LPwithMonads.ps.gz

A more recent paper, with an emphasis on a clean and efficient handling of state information, can be found at:
ftp://clement.info.umoncton.ca:/pub/BinPrologPapers
in the file:
TR.95.2-HiddenAccumultorsAndLinImpl.tar.gz

Here is the abstract:

Backtrackable State with Linear Assumptions, Continuations and Hidden Accumulator Grammars
Paul Tarau, Veronica Dahl, Andrew Fall

A set of executable specifications and efficient implementations of backtrackable state persisting over the current AND-continuation is investigated.

At specification level, our primitive operations are linear and intuitionistic implications, having as a consequent the current continuation. On top of them, we introduce a form of hypothetical assumptions which use no explicit quantifiers and have an easy and efficient implementation on top of logic programming systems featuring backtrackable destructive assignment, and global variables.

A variant of Extended DCGs handling multiple streams without the need of a preprocessing technique, Hidden Accumulator Grammars (HAGs), are specified in terms of linear assumptions. For HAGs, efficiency comparable to that of preprocessing techniques is obtained through a WAM-level implementation of backtrackable destructive assignment, supporting non-deterministic execution based on value-trailing, while collapsing to a form of in-place update in the case of deterministic execution.

When more precise information about the location where linear assumptions are be used is available, either HAGs (or a continuation based representation multi-headed clauses) is used to avoid a performance penalty due to dynamic implementation.

The techniques described in the paper are portable to alternative LP languages like Life, Lolli and LambdaProlog.