Is anybody interested in a PROLOG interpreter written in Turbo Pascal, plus a couple of typeset articles which outline how it works internally?

When I found it I was wondering whether it could be usefully used to handle inference rules in a Delphi/FPC/Lazarus program, in the same way that MS use Prolog for some of their network configuration stuff. However it turns out that it is coded explicitly for Turbo Pascal with a garbage collector on top of the normal heap, which I think implies that porting it to FPC would need either a mark/release facility or multiple heaps which could be "thrown away" when no longer needed.

I was reminded of this by the discussion elsewhere on refcounted objects, which would obviously be another way to do it. Timothy Budd's book on Leda gives an interesting example of using the unification operation which underpins Prolog to process graph structures.

Reference counting is just another way to implement garbage collection, and is already available (for Interfaces). Wouldn't this be sufficient for the Prolog interpreter?

DoDi

Probably not in its current form, since it is implemented in a very Lisp-like fashion with lots of tiny cells in linked lists. If rewritten with coarser granularity then there's lots of ways of doing it, noting that in the general case rules and queries don't have to be textual.

In our previous episode, Mark Morgan Lloyd said:

I don't understand why interested people couldn't implement mark/release for the base TP compatible level of FPC ? What is so different between TP and FPC there?

Of course it wouldn't scale, but TP didn't scale further than 16MB anyway (64MB with 386 tricks).

Basically you only need an own heapmanager that allocates all allocations in-order from a 16MB block, and mark and release procedures that call that heapmanager and are declared in some unit preloaded wiht -Fa?

I was reminded of this by the discussion elsewhere on refcounted objects, which would obviously be another way to do it. Timothy Budd's book on Leda gives an interesting example of using the unification operation which underpins Prolog to process graph structures.

Prolog is an interpreter, and I assume its structures are movable. Native languages allocations usually aren't.

Just implemented it in the "tiny" heap manager (the heap manager used for i8086-msdos and perhaps in the future - the embedded targets). For the regular targets I'd suggest adding it as an unit that replaces the standard heap manager with the simple one, as described by Marco. You can even use the "tiny" heap manager sources (rtl/inc/tnyheaph.inc and rtl/inc/tinyheap.inc) in your unit. They might need some minor patching, but nothing too difficult.

Nikolay

I don't understand why interested people couldn't implement mark/release for the base TP compatible level of FPC ? What is so different between TP and FPC there?

Perhaps it's the effort to support it for multiple architectures?

DoDi

The main issue is that dynamic memory is used by the Prolog implementation in several different ways. The first way is that as rules are being entered, they go into memory and usually stay there. The second way is that as queries are evaluated a lot of temporary stuff (variable bindings etc.) is put into memory, this is all thrown away on completion. The third way is that during query evaluation, rules could potentially be added/deleted/changed which shouldn't be thrown away.

I think that in practice this could be handled by normal OO techniques, since these days the amount of (virtual) memory is significantly larger than typical embedded problems. If somebody wanted to e.g. process the entire collection of Wikipedia titles and categories as a set of rules then they should probably be using specialist tools.

Up to a point. A typical Prolog implementation acts as an interpreter since rules and queries are entered interactively, however the underlying unification algorithm can equally well be embedded in compiled code. Budd's example (chap 3 of ref below, pp 46, 49, 51ff) creates a representation of a graph, calls a Prolog-style unification function to return the edge(s) meeting certain criteria, and then goes on to use this to find in- and outdegree for each vertex, find cycles and so on. http://web.engr.oregonstate.edu/~budd/Books/leda/info/

Now I'm not necessarily saying that any of this is blindingly efficient compared with a proper set of algorithms. But from the POV of an engineer who wasn't brought up on this stuff I think that being aware of unification as (something analogous to) a design pattern might be useful, and I'll probably have a bash at some of this myself if I recognise a potential use case. Until then, I've got an example implementation if anybody else is interested.

In our previous episode, Mark Morgan Lloyd said:

How does this work in TP? Mark/release would remove all variables, not just the temprary ones. Or are the persistent and temporary orders not mixed, and is only the temporary part under mark/release?

(in case it wasn't clear, the problem is that mark/release either requires memory to be available as one contageous block. There is no guarantee that an existing block can be expanded later, so you need to allocate it up front (the 16MB above).

To work around it, in theory one could allocate a new heap on every mark (if free mem< a certain threshold), and maintain a linked list of blocks that are scanned through for mark/release operations, but that is (1) costly, so you would need to pace your mark/releases (2) you still need an upper limit.

If address space is large enough (read: 64-bit) you might only reserve relatively large blocks, regardless of much you use.

My point is more that if the prolog interpreter can move its allocations so that the program remains working

IOW if I do

mark

  new(persist);
  new (temp);

<---
release

can I run a routine at the <--- point that moves all persistent allocations from the block of mark..release to a new or existing, persistent heap?

Does it keep track of what is temp and what is persistent?

In our previous episode, Hans-Peter Diettrich said:

Afaik only if you try to optimize it it gets OS and arch specific.

In the current code, it doesn't attempt to change the rules. So according to discussion with the author a few years ago, provided that there was enough memory to evaluate the query everything could be thrown away once the results were returned. However it's been written with garbage collection which kicks in when available heap drops below a certain amount (this in itself is problematic on the general case), and which is intimately aware of TP's heap structure.

In practical terms, having a private heap for evaluations would probably be OK. Or redoing the entire thing as OO, in which case it becomes comparatively easy to work out what needs to be thrown away on completion: AIUI you're walking a tree and also growing/shrinking an environment of temporary bindings as you move away and towards the root.

Yes, I think the current code could be fairly easily modified for that sort of thing.

Does it keep track of what is temp and what is persistent?

The current code doesn't, it just GCs the whole thing.

I have a library done for other projects which supports memory management routines, where the memory allocations may belong to different classes of memory, and then you are able to free all memory belonging to one class with one single call.

That is, there are calls similar to C-malloc, calloc, realloc and free, but a class identifier is added to every call. And there is one additional freeall() call to free the entire memory class.

The routines outperform the normal ANSI C functions on certain systems. although they put a layer of management on top of the normal ANSI C functions
(because many calls to allocate little areas of memory result to one call of
the ANSI C function to allocate a large area and some internal management ...
I used this approach to make my XML parser faster than others ... and the freeall() call at the end of the parsing makes XML parsing safe; the working storage of the parser is freed, but the resulting DOM tree, for example
- if you use DOM - ,
is not ... it resides in a different memory class).

This is written in C, but it should of course be callable from FP as well; there are no architecture dependencies. It runs on Windows, OS/2, Linux and even on z/Arch mainframes (so does the XML parser).

Please contact me offline, if you are interested. Maybe you could use it with your PROLOG project, if you are able to "classify" the memory allocations
in the PROLOG code.

Kind regards

Bernd

Interesting, but this isn't something that I'll be immediately looking at thanks. In any case, I'd probably be focussing on the general case (see the examples I referenced earlier), and I think that the memory management for rules based on objects will be completely different from the case where rules are based on Lisp-type strings (i.e. each string is stored as a linked list of cells).

After rereading the thread I think that I confused mark/sweep and mark/release. Sorry for that :-(

DoDi