Help us understand the problem. What is going on with this article?

Higher Order Programming in Prolog

More than 1 year has passed since last update.

Prolog is traditionally associated with Horn Clauses and therefore with first order logic. But already Hilbert & Ackermann introduced second order logic in their 1928 booklet about mathematical logic. In first order logic variables only range over individuals. In second order logic variables can also range over functions.

As it happens there exist also extension to Prolog, even ISO Prolog, that allow second order and higher order programming. It started with a predicate apply/2 which can be defined as follows. This can be also used to implement map/3 that applies a closure to a list:

apply(Closure, Arguments) :-
    Closure =.. [Functor|Arguments1],
    append(Arguments1, Arguments, Arguments2),
    Call =.. [Functor|Arguments2],
    Call.

map(_, [], []).
map(Closure, [Elem|List], [Elem2|List2]) :- 
    apply(Closure, [Elem, Elem2]),
    map(Closure, List, List2).

Higher order functors such as map/3 might replace loops in Prolog programs. The family of such functors might also include predicates such as fold/4, scan/4, include/3, exclude/3, etc.. Here is an example run that computes the square of a list of numbers:

sqr(X, Y) :- Y is X*X.

?- map(sqr, [1,2,3], X).
X = [1, 4, 9]

Back in 1996 it then transpired in a discussion involving Richard A. O'Keefe and others that call/n might be the better solution than apply/2. call/n has the advantage that it allows better currying of closures. There are now also lambda libraries available based on call/n that allow producing annoymous closures on the fly.

call/n made it into the ISO core standard. We have recently used call/n to enhance our aggregates library. Aggregates are a welcome alternative to loops since they are usually implemented failure driven, and don't need to materialize a list. They are already rooted in the ISO core standard predicate bagof/3 which can do grouping:

?- bagof(1, member(X,[the,brown,fox,jumps,over,the,brown,fox]), L).
X = brown,
L = [1, 1] ;
X = fox,
L = [1, 1] ;
X = jumps,
L = [1] ;
X = over,
L = [1] ;
X = the,
L = [1, 1]

The difference between bagof/3 and aggregates is that aggregates will not simply return a list of solution, but perform some aggregate function on the solutions before returning the aggregated result instead. This works best for aggregate arguments that do not involve variables, since aggregate values will be copied:

?- use_module(library(advanced/aggregate)).

?- aggregate(count, member(X,[the,brown,fox,jumps,over,the,brown,fox]), N).
X = brown,
N = 2 ;
X = fox,
N = 2 ;
X = jumps,
N = 1 ;
X = over,
N = 1 ;
X = the,
N = 2

We have recently introduced parameterized aggregate functions into our aggregate library. Such higher order aggregate functions are for example known from Java parellel streams. We opted for the following new aggregate functions that take a closure parameter. These aggregate functions were implemented by means of call/n under the hood:

  • first(Closure, Value):
    The aggregate function returns the least value according
    to the linear order predicate Closure.
  • last(Closure, Value):
    The aggregate function returns the greatest value according
    to the linear order predicate Closure.
  • reduce(Identity, Closure, Value):
    The aggregate function returns the value sum according
    to the accumulator predicate Closure.

The Prolog facts hofstadter/1 illustrates the working of the custom aggregate functions. The custom aggregate functions first/2 and last/2 are parameterized by an order closure. When choosing lexical ordering we get:

hofstadter(escher).
hofstadter(goedel).
hofstadter(bach).

?- aggregate(first(@<,X), hofstadter(X), Y).
Y = bach

aggregate(last(@<,X), hofstadter(X), Y).
Y = goedel

The custom aggregate function reduce/3 is parameterized by an identity value and an accumulator closure. The accumulator closure should take two arguments and return the result in its third argument. When choosing atom concat we get:

aggregate(reduce('',atom_concat,X), hofstadter(X), Y).
Y = eschergoedelbach

These new aggregates are also already available in our upcoming tabling. We will release Jekejeke Prolog 1.4.0 in a few days. They can have interesting applications in optimization. Last but not least they provide potential for parallelization as the Java parallel streams already show. We will explore these possibility in further upcoming releases.

Discussion about call/n from 1996 - Richard A. O'Keefe et al.
http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/naish.html

Open Source: Module "aggregate"
https://github.com/jburse/jekejeke-devel/blob/master/jekrun/headless/jekpro/frequent/advanced/aggregate.p

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした