What speed to expect doing logic on graphs represented by maps
I want to write something resembling an editor for a graph database. I'm wondering if Curry will be fast enough. The data defining the graph would resemble the following: type Address = Int data Graph = Graph { address :: Map String Address content :: Map Address String -- `address` and `content` are inverses children :: Map Label (Set Address) parents :: Map Label (Set Address) } I would define rules such as: descendent :: Graph -> Index -> Index descendent g i -- If j is i's child, then j is i's descendent. | Set.member j $ Map.lookup i $ children g = j descendent g i -- If j is i's descendent and k is j's child, then k is i's descendent. | descendent g i j & (Set.member k $ Map.lookup k $ children g) = k I'll use hash maps unless their space requirements stop me. I'm hoping the resulting code will quickly (say, in under a second) answer queries over a few million nodes, along the lines of "the descendents of X and Y, minus any descendents of Z or W". If an unbounded number of generations proves computationally difficult, I would not be bothered by needing to impose depth limits, ala "the first two generations of descendents of X and Y, minus the first seven generations of descendents of Z or W". The graph would be sparse: with an average number of children well under five, and few cycles. Is this kind of performance a reasonable thing to expect from Curry? If so, using which compiler? If not, can you recommend another language? I know Haskell, and prefer it immensely to any other language. I am reluctant to write a full application in a pure logic language like Mercury, but I will if need be. -- Jeff Brown | Jeffrey Benjamin Brown Website <https://msu.edu/~brown202/> | Facebook <https://www.facebook.com/mejeff.younotjeff> | LinkedIn <https://www.linkedin.com/in/jeffreybenjaminbrown>(spammy, so I often miss messages here) | Github <https://github.com/jeffreybenjaminbrown>
Hi Jeff, I can't answer your primary question, but regarding other candidate languages/systems for your problem I'd recommend you have a look at ConceptBase. (conceptbase.sourceforge.net) From what you described it sounds like a good fit. Cheers /Felix On Mon, Nov 12, 2018 at 5:40 PM Jeffrey Brown <jeffbrown.the@gmail.com> wrote:
I want to write something resembling an editor for a graph database. I'm wondering if Curry will be fast enough.
The data defining the graph would resemble the following:
type Address = Int data Graph = Graph { address :: Map String Address content :: Map Address String -- `address` and `content` are inverses children :: Map Label (Set Address) parents :: Map Label (Set Address) }
I would define rules such as:
descendent :: Graph -> Index -> Index descendent g i -- If j is i's child, then j is i's descendent. | Set.member j $ Map.lookup i $ children g = j descendent g i -- If j is i's descendent and k is j's child, then k is i's descendent. | descendent g i j & (Set.member k $ Map.lookup k $ children g) = k
I'll use hash maps unless their space requirements stop me.
I'm hoping the resulting code will quickly (say, in under a second) answer queries over a few million nodes, along the lines of "the descendents of X and Y, minus any descendents of Z or W". If an unbounded number of generations proves computationally difficult, I would not be bothered by needing to impose depth limits, ala "the first two generations of descendents of X and Y, minus the first seven generations of descendents of Z or W".
The graph would be sparse: with an average number of children well under five, and few cycles.
Is this kind of performance a reasonable thing to expect from Curry? If so, using which compiler? If not, can you recommend another language?
I know Haskell, and prefer it immensely to any other language. I am reluctant to write a full application in a pure logic language like Mercury, but I will if need be.
-- Jeff Brown | Jeffrey Benjamin Brown Website <https://msu.edu/~brown202/> | Facebook <https://www.facebook.com/mejeff.younotjeff> | LinkedIn <https://www.linkedin.com/in/jeffreybenjaminbrown>(spammy, so I often miss messages here) | Github <https://github.com/jeffreybenjaminbrown>
_______________________________________________ curry mailing list -- curry@lists.rwth-aachen.de To unsubscribe send an email to curry-leave@lists.rwth-aachen.de https://lists.rwth-aachen.de/postorius/lists/curry.lists.rwth-aachen.de
-- Felix Holmgren / Holmgren Interstellar tel: +46 704 452 469
My Curry-related questions herein are brief. *# Curry-related questions* What I described is not exactly my target project, but if what I described is fast, the target project will be, too. I guess my main question isn't about the precise speed details, but whether a good implementation in Curry will do logic on maps at roughly the same speed as a good implementation in another language. (If it's slower by a constant factor of 10 that's fine, but if it slows down faster than another implementation that's a big deal.) One contender, Mercury, requires a programmer to specify whether each argument is an input or an output, and what kind of result (deterministic or not, single or multiple value, committed choice or not ...) it provides. It looks like a pain -- but also like it might allow the compiled code to be a lot faster. *# What I'm aiming for* ConceptBase looks powerful, and indeed similar to what I'm trying to do. Thanks, Felix! But I'm afraid it's too heavyweight. I want something only slightly more complex than a knowledge graph: One where relationships can involve any number of members, rather than exactly two, and in which those members can themselves be relationships. That might already sound hard to use, but I found a parsing trick that makes it friendly. One designs a label (a "template" for relationships) by writing something like "If _ then _". One then instantiates the template by writing, say, "#If smoke #then fire". It can be ordinary natural language, but extended with one extra symbol, #, which lets the computer understand how relationships nest. Details on the # syntax can be found here[3]. I am inspired by Semantic Synchrony (SmSn), a graph database with an Emacs front end. (Here's a brief video[1] about SmSn.) SmSn lets two people join their knowledge bases. I hope to make the same thing possible with these more general relationships. For that to happen it has to be simple, so I've tried to find the simplest possible implementation that permits general nested n-ary relationships. A graph-based implementation of the type system that it requires is sketched here[2]. When I wrote that I knew about graphs but had forgotten about logic languages. A logic languages would let it be easier to understand, easier to extend, more powerful, safer ... A map-based implementation designed for a logic language can be found here[4] -- but it's just the types, with no associated procedures. [1] https://www.youtube.com/watch?v=R2vX2oZmUUM&t=2s [2] https://github.com/JeffreyBenjaminBrown/digraphs-with-text/blob/master/intro... [3] https://github.com/JeffreyBenjaminBrown/digraphs-with-text/blob/master/Hash/... [4] https://github.com/JeffreyBenjaminBrown/rslt-mercury/blob/master/rslt.m On Tue, Nov 13, 2018 at 3:12 AM Felix Holmgren <felix.holmgren@gmail.com> wrote:
Hi Jeff,
I can't answer your primary question, but regarding other candidate languages/systems for your problem I'd recommend you have a look at ConceptBase. (conceptbase.sourceforge.net) From what you described it sounds like a good fit.
Cheers /Felix
On Mon, Nov 12, 2018 at 5:40 PM Jeffrey Brown <jeffbrown.the@gmail.com> wrote:
I want to write something resembling an editor for a graph database. I'm wondering if Curry will be fast enough.
The data defining the graph would resemble the following:
type Address = Int data Graph = Graph { address :: Map String Address content :: Map Address String -- `address` and `content` are inverses children :: Map Label (Set Address) parents :: Map Label (Set Address) }
I would define rules such as:
descendent :: Graph -> Index -> Index descendent g i -- If j is i's child, then j is i's descendent. | Set.member j $ Map.lookup i $ children g = j descendent g i -- If j is i's descendent and k is j's child, then k is i's descendent. | descendent g i j & (Set.member k $ Map.lookup k $ children g) = k
I'll use hash maps unless their space requirements stop me.
I'm hoping the resulting code will quickly (say, in under a second) answer queries over a few million nodes, along the lines of "the descendents of X and Y, minus any descendents of Z or W". If an unbounded number of generations proves computationally difficult, I would not be bothered by needing to impose depth limits, ala "the first two generations of descendents of X and Y, minus the first seven generations of descendents of Z or W".
The graph would be sparse: with an average number of children well under five, and few cycles.
Is this kind of performance a reasonable thing to expect from Curry? If so, using which compiler? If not, can you recommend another language?
I know Haskell, and prefer it immensely to any other language. I am reluctant to write a full application in a pure logic language like Mercury, but I will if need be.
-- Jeff Brown | Jeffrey Benjamin Brown Website <https://msu.edu/~brown202/> | Facebook <https://www.facebook.com/mejeff.younotjeff> | LinkedIn <https://www.linkedin.com/in/jeffreybenjaminbrown>(spammy, so I often miss messages here) | Github <https://github.com/jeffreybenjaminbrown> _______________________________________________ curry mailing list -- curry@lists.rwth-aachen.de To unsubscribe send an email to curry-leave@lists.rwth-aachen.de https://lists.rwth-aachen.de/postorius/lists/curry.lists.rwth-aachen.de
-- Felix Holmgren / Holmgren Interstellar tel: +46 704 452 469 _______________________________________________ curry mailing list -- curry@lists.rwth-aachen.de To unsubscribe send an email to curry-leave@lists.rwth-aachen.de https://lists.rwth-aachen.de/postorius/lists/curry.lists.rwth-aachen.de
-- Jeff Brown | Jeffrey Benjamin Brown Website <https://msu.edu/~brown202/> | Facebook <https://www.facebook.com/mejeff.younotjeff> | LinkedIn <https://www.linkedin.com/in/jeffreybenjaminbrown>(spammy, so I often miss messages here) | Github <https://github.com/jeffreybenjaminbrown>
On 11/12/18 5:40 PM, Jeffrey Brown wrote:
Is this kind of performance a reasonable thing to expect from Curry? If so, using which compiler? If not, can you recommend another language?
Hi Jeff, here are some general remarks about the performance of Curry. Since Curry combines functional and logic programming, you cannot expect to be faster than purely functional or purely logic languages. Although the combination might have its costs, one can try a pay-per-view implementation so that you pay only if you use the features. For instance, if non-determinism is not used, the KiCS2 implementation, which compiles Curry to Haskell, is almost as fast as Haskell. The only price are additional arguments for each function which are passed around. However, if you heavily use non-determinism, the KiCS2 implementation, which also implements breadth-first search and iterative deepening (beyond depth-first search as in Prolog), become less efficient than a backtracking-based Prolog implementation (like PAKCS), but this is incomplete as Prolog. In contrast to Mercury, high performance is not our main goal. I see no principle problems to achieve it with clever analysis tools, but this requires more implementation efforts. Nevertheless, our current implementations are sufficient for us to develop applications with Curry, but maybe not the ones you have in mind. Best regards, Michael
participants (3)
-
Felix Holmgren -
Jeffrey Brown -
Michael Hanus