[curry] Re: What speed to expect doing logic on graphs represented by maps

From: Jeffrey Brown <jeffbrown.the_at_gmail.com>
Date: Tue, 13 Nov 2018 11:30:16 -0500

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/introduction/Minimal_Types.hs
[3]
https://github.com/JeffreyBenjaminBrown/digraphs-with-text/blob/master/Hash/the-hash-language.md
[4] https://github.com/JeffreyBenjaminBrown/rslt-mercury/blob/master/rslt.m

On Tue, Nov 13, 2018 at 3:12 AM Felix Holmgren <felix.holmgren_at_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_at_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_at_lists.rwth-aachen.de
>> To unsubscribe send an email to curry-leave_at_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_at_lists.rwth-aachen.de
> To unsubscribe send an email to curry-leave_at_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>



_______________________________________________
curry mailing list -- curry_at_lists.rwth-aachen.de
To unsubscribe send an email to curry-leave_at_lists.rwth-aachen.de
https://lists.rwth-aachen.de/postorius/lists/curry.lists.rwth-aachen.de
Received on Mon Nov 19 2018 - 17:42:51 CET

This archive was generated by hypermail 2.3.0 : Mon Nov 18 2019 - 07:15:09 CET