Re: [fpc-other] PROLOG written in Pascal
Marco van de Voort wrote: In our previous episode, Mark Morgan Lloyd said: 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 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? 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. 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. 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. -- Mark Morgan Lloyd markMLl .AT. telemetry.co .DOT. uk [Opinions above are the author's, not those of his employers or colleagues] ___ fpc-other maillist - fpc-other@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-other
Re: [fpc-other] PROLOG written in Pascal
In our previous episode, Hans-Peter Diettrich 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? > > Perhaps it's the effort to support it for multiple architectures? Afaik only if you try to optimize it it gets OS and arch specific. ___ fpc-other maillist - fpc-other@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-other
Re: [fpc-other] PROLOG written in Pascal
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? > > 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. 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? > 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. (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. > >> 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. > > 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 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? ___ fpc-other maillist - fpc-other@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-other
Re: [fpc-other] PROLOG written in Pascal
Marco van de Voort wrote: 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? 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. 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 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. 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. 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. 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? 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. -- Mark Morgan Lloyd markMLl .AT. telemetry.co .DOT. uk [Opinions above are the author's, not those of his employers or colleagues] ___ fpc-other maillist - fpc-other@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-other
Re: [fpc-other] PROLOG written in Pascal
Am 21.09.2014 13:57, schrieb Mark Morgan Lloyd: Marco van de Voort wrote: 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? 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. 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 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. 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 ___ fpc-other maillist - fpc-other@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-other
Re: [fpc-other] PROLOG written in Pascal
Bernd Oppolzer wrote: 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. 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). -- Mark Morgan Lloyd markMLl .AT. telemetry.co .DOT. uk [Opinions above are the author's, not those of his employers or colleagues] ___ fpc-other maillist - fpc-other@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-other
Re: [fpc-other] PROLOG written in Pascal
Marco van de Voort schrieb: In our previous episode, Hans-Peter Diettrich 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? Perhaps it's the effort to support it for multiple architectures? Afaik only if you try to optimize it it gets OS and arch specific. After rereading the thread I think that I confused mark/sweep and mark/release. Sorry for that :-( DoDi ___ fpc-other maillist - fpc-other@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-other
