S-Expression Query Language

  • 19 Replies
  • 780 Views
*

ivan.moony

  • Trusty Member
  • *********
  • Terminator
  • *
  • 948
    • Structured Type System
S-Expression Query Language
« on: March 15, 2018, 06:42:55 pm »
Binary Structure Calculus

Recently, I was exploring some s-expression notation known from LISP breed of languages. LISP languages are usually used for AI (a part of OpenCog is based on it). What I was trying to achieve is having an algebra of duality. For example, we define summation function and automatically derive difference function. Or we define multiply function and automatically derive division function. Or we define emergence, and conclude consequence from specifying cause, or conclude cause from specifying consequence. In general, we define a function, and we could query it in both directions, from parameters to result, or from result to parameters. I believe it has something to do with a million dollar prized P = NP? question.

All of this should nicely fit with math, logic, knowledge base querying, theorem proving, and it could find a use in any science field, I believe.

This is syntax in BNF notation - this is the whole language, there is nothing else:
Code: [Select]
start ::= e    //s-expression

e ::= a        // atom
    | a e      // sequencing
    | (e)      // grouping
   
a ::= c        // constant
    | {q}      // query

q ::= a q      // querying to the right of a
    | q a      // querying to the left of a
    | ?        // return query result
    | !        // return query complement
    | (q)      // grouping

These are seven semantic rules expressed in a kind of Sequent Calculus:


        constant c ϵ Γ   
    ────────────────────── (1)
            Γ ⊢ c       


        Γ ⊢ c1     Γ ⊢ c2
    ───────────────────────── (2)
            Γ ⊢ c1 c2       



    ───────────────────────── (3)
        Γ, {σ} ⊢ Σ(σ) → Γ


        Σ(c σ) → c c1     Σ(c σ) → c c2     ...
    ─────────────────────────────────────────────── (4)
             (Σ(σ) → c1) ∧ (Σ(σ) → c2) ∧ ...


        Σ(σ c) → c1 c     Σ(σ c) → c2 c     ...
    ─────────────────────────────────────────────── (5)
             (Σ(σ) → c1) ∨ (Σ(σ) → c2) ∨ ...


        Σ(?) → σ
    ──────────────── (6)
            σ


           Σ(!) → σ   
    ─────────────────────── (7)
        complement of σ



Rules 1-2 are sequence introducing rules. Rules 3-7 are sequence query mechanism. (3) is converting a query to intermediate sigma form. (4) and (5) are sigma tree traversal inference. (6) and (7) are converting terminal sigma form to usable end result.

Basically, Binary Structure Calculus is a syntax of s-expressions plus syntax of querying over s-expressions. Query can simply be {x ?} for reaching element right to matched x, or {? x} for reaching element left to matched x. Of course, queries can be nested to reach complex structure elements. And that's all there is, and it seems enough.

You'll be surprised how expressive this combination might be. More about it soon, I'm preparing a whitepaper.
« Last Edit: April 11, 2018, 04:55:50 pm by ivan.moony »
Dream big. The bigger the dream is, the more beautiful place the world becomes.

*

infurl

  • Trusty Member
  • *******
  • Starship Trooper
  • *
  • 481
  • Humans will disappoint you.
    • Home Page
Re: Binary Structure Calculus
« Reply #1 on: March 15, 2018, 09:02:08 pm »
That's very interesting work. It looks like unification and logical resolution operations and could be used for the same things such as knowledge representation and theorem proving but maybe what you are developing is more powerful. I'm looking forward to finding out more about it.

For reference, this is what I'm talking about.

Given rules:
Code: [Select]
(equal ?x ?x)
(<=> (equal ?x ?y) (equal ?y ?x))
(<=> (and (equal ?x ?y) (equal ?y ?z)) (equal ?x ?z))
(not (parent ?x ?x))
(not (grandparent ?x ?x))
(<=> (or (father ?x ?y) (mother ?x ?y)) (parent ?x ?y))
(<=> (or (grandfather ?x ?y) (grandmother ?x ?y)) (grandparent ?x ?y))
(<=> (and (parent ?x ?y) (mother ?y ?z)) (grandmother ?x ?z))
(<=> (and (parent ?x ?y) (father ?y ?z)) (grandfather ?x ?z))

and facts:
Code: [Select]
(father carol robert)
(mother carol alice)
(father alice bill)
(mother alice mary)
(father robert tom)
(mother robert sally)

solve:
Code: [Select]
(grandparent carol ?z)
which yields (bill mary sally tom) as possible values for z.

*

LOCKSUIT

  • Emerged from nothing
  • Trusty Member
  • ***********
  • Eve
  • *
  • 1456
  • First it wiggles, then it is rewarded.
    • Enter Lair
Re: Binary Structure Calculus
« Reply #2 on: March 15, 2018, 09:05:23 pm »
But are those millennium prizes even real? I mean there's probably hogs online with toneeees of proposals. Can you really discover the answer and get the money legitimately still?
Emergent

*

ivan.moony

  • Trusty Member
  • *********
  • Terminator
  • *
  • 948
    • Structured Type System
Re: Binary Structure Calculus
« Reply #3 on: March 15, 2018, 09:44:42 pm »
(Rules for millennium prizes at Clay Institute)

In short, to get the millennium prize, you have to first publish your work in some significant science magazine. Then you have to wait two years. If in a meanwhile some serious scientific work is built on top of your paper, and your paper gets cited a lot of times, the prize is yours (but if your work is significantly influenced by some other author, the author also gets a share). It is the world who accepts or rejects your solution, Clay Institute just observes and responds. Right now, I think there are around a hundred proofs reported for both P = NP or P != NP. Neither one got the prize yet. It is a real mess out there and I'd rather stay out of it if I can. But if anyone else builds her work on top of mine, I'd appreciate a reference to any of my my papers (one so far on the subject).
Dream big. The bigger the dream is, the more beautiful place the world becomes.

*

LOCKSUIT

  • Emerged from nothing
  • Trusty Member
  • ***********
  • Eve
  • *
  • 1456
  • First it wiggles, then it is rewarded.
    • Enter Lair
Re: Binary Structure Calculus
« Reply #4 on: March 15, 2018, 10:26:41 pm »
I think I just solved the NP problem..........I instantly realized the answer to a NP question on the wiki page in polynomial time. I'm NOT telling yous how just yet haha! That was fast!                                                   ?

It said above it:
There are many important NP problems that people don't know how to solve in a way that is faster than testing every possible answer. Here are some examples:

EDIT: This is the easiest thing everrrrrrrrrrrrrrrr
Emergent

*

ivan.moony

  • Trusty Member
  • *********
  • Terminator
  • *
  • 948
    • Structured Type System
Re: Binary Structure Calculus
« Reply #5 on: April 03, 2018, 04:38:34 pm »
I just updated semantic section of the top post. I had problems with this one, but I think I got it right this time.

I think that semantics expressed in Sequent Calculus are that thing that divide theories with "calculus" epithet and theories with "language" epithet. This way expressed semantics are not of much use except they can be verified for correctness in some proof verifying tools. The other use of these kind of expressed semantics is possible understanding from some genius reader. You know how things seem complicated when you don't know them yet, and simple when you realize how they work? That is why I have to write an explanation in a natural language to pair it with Sequent Calculus definition, so that formal Sequent Calculus definition could be understood by an average reader like me.

I'm still working on bidirectional examples, and things look cool for now. I expect things like automatic getting math integral formulas from specifying math derivative formulas, and similar kinds of perversions. Will post it here, hopefully, if I live long enough.

[I'm still not satisfied with the calculus name, thinking about "S-Expression Query Language" (SEQL)]
« Last Edit: April 03, 2018, 05:12:27 pm by ivan.moony »
Dream big. The bigger the dream is, the more beautiful place the world becomes.

*

ivan.moony

  • Trusty Member
  • *********
  • Terminator
  • *
  • 948
    • Structured Type System
Re: Binary Structure Calculus
« Reply #6 on: April 04, 2018, 04:41:06 pm »
As a teaser, I bring a few examples of integer numbers and basic operation on them. Note that this is mathematical-like definition, and it is complete in a sense that we don't need any external dependencies to outer datat ypes and operators.

This is how integer constants are formed:
Code: [Select]
// integer definition
(
    Int {
        Zero |
        (One {Int})
    }
)
0 = Zero, 1 = One (Zero), 2 = One (One (Zero)), ...

Code: [Select]
// increment and decrement by one
{
    Use (
        {Int}
        (x {Int})
    ) in (
        ((++ {x}) {One {x}})
        ((-- {One {x}}) {x})
    )
}

Code: [Select]
// addition and subtraction
{
    Use (
        (x {Int})
        (y {Int})
        {
            Use (
                (incremented {Int})
                (decremented {Int})
            ) in (
                Loop {incremented} {decremented} {
                    iff {{decremented} in Zero}
                        {Loop {++{incremented}} {--{decremented}}}
                        {incremented}
                }
            )
        }
    ) in (
        (
            ({x} + {y})
            {Loop {x} {y}}
        )
        (
            ({x} - {y})
            {(? + {y}) {x}}
        )
    )
}
Plus operation is defined in terms of looped incrementation. Minus operation is defined in terms of plus operation. It reads: "x - y = what plus y gives x?"

Code: [Select]
// multiplication and division
{
    Use (
        {Int}
        (x {Int})
        (y {Int})
        {
            Use (
                (step {Int})
                (accumulator {Int})
                (decremented {Int})
            ) in (
                Step {step} Loop {accumulator} {decremented} {
                    iff {{decremented} in Zero}
                        {Loop {{accumulator} + {step}} {--{decremented}}}
                        {accumulator}
                }
            )
        }
    ) in (
        (
            ({x} * {y})
            {Step {x} Loop {Zero} {y}}
        )
        (
            ({x} / {y})
            {(? * {y}) {x}}
        )
    )
}
Multiply operation is defined in terms of looped addition. Divide operation is defined in terms of multiply operation. It reads: "x / y = what times y gives x?"

Implementation of the language will be a bit tricky, but I think it is possible.
Dream big. The bigger the dream is, the more beautiful place the world becomes.

*

ivan.moony

  • Trusty Member
  • *********
  • Terminator
  • *
  • 948
    • Structured Type System
Re: Binary Structure Calculus
« Reply #7 on: April 11, 2018, 04:55:24 pm »
This is a quote from the paper I'm writing:
Quote
This is the essence of extracting, for example a function parameters from a function result: we substitute the whole expression, just to extract pieces from it. For this process to be functional, we need to define all the calculations in terms of our metatheoretical framework. Only then, since we don't use external, hard coded definitions, but only definitions in a form of queryable s-expressions, we are covering a complete range of computable expressions. Once calculated, we are able to extract any fragment from a process of possible construction of any expression, thus reducing the problem only to pattern matching. However, low level implementation will be a bit of challenge to grapple with, regarding to recursive functions, but the implementation is possible, as long as we restrict the number of possible recursions to a finite number.
« Last Edit: April 11, 2018, 06:16:28 pm by ivan.moony »
Dream big. The bigger the dream is, the more beautiful place the world becomes.

*

infurl

  • Trusty Member
  • *******
  • Starship Trooper
  • *
  • 481
  • Humans will disappoint you.
    • Home Page
Re: S-Expression Query Language
« Reply #8 on: April 11, 2018, 10:44:13 pm »
Ivan I frequently use the technique that you're describing in C applications. You can use macros to implement the S-expression queries that you're describing. It is a very powerful technique which can save a lot of maintenance effort. Generic term for it is X-macro.

https://en.wikipedia.org/wiki/X_Macro

Here's an example from a program that I wrote last week.

Code: [Select]
#define mKeyWords                               \
mKeyWord(Aliases,        "aliases")             \
mKeyWord(Amount,         "amount")              \
mKeyWord(Badges,         "badges")              \
mKeyWord(CalendarModel,  "calendarmodel")       \
mKeyWord(Claims,         "claims")              \
mKeyWord(DataType,       "datatype")            \
mKeyWord(DataValue,      "datavalue")           \
mKeyWord(Descriptions,   "descriptions")        \
mKeyWord(Hash,           "hash")                \
mKeyWord(Id,             "id")                  \
mKeyWord(Labels,         "labels")              \
mKeyWord(Language,       "language")            \
mKeyWord(LastRevId,      "lastrevid")           \
mKeyWord(LowerBound,     "lowerBound")          \
mKeyWord(MainSnak,       "mainsnak")            \
mKeyWord(Modified,       "modified")            \
mKeyWord(Property,       "property")            \
mKeyWord(Qualifiers,     "qualifiers")          \
mKeyWord(QualifiersOrder,"qualifiers-order")    \
mKeyWord(Rank,           "rank")                \
mKeyWord(References,     "references")          \
mKeyWord(Site,           "site")                \
mKeyWord(SiteLinks,      "sitelinks")           \
mKeyWord(SnakType,       "snaktype")            \
mKeyWord(SnaksOrder,     "snaks-order")         \
mKeyWord(Time,           "time")                \
mKeyWord(Title,          "title")               \
mKeyWord(Type,           "type")                \
mKeyWord(Unit,           "unit")                \
mKeyWord(UpperBound,     "upperBound")          \
mKeyWord(Value,          "value")               \

static const char* gKeyWords[] =
{
    #define mKeyWord(Symbol,String) String,
    mKeyWords
    #undef mKeyWord
};

enum tKeyWordIndex
{
    #define mKeyWord(Symbol,String) k##Symbol##KeyWordIndex,
    mKeyWords
    #undef mKeyWord
};

enum tKeyWord
{
    #define mKeyWord(Symbol,String) k##Symbol##KeyWord = (-1 - k##Symbol##KeyWordIndex),
    mKeyWords
    #undef mKeyWord
};

#define kKeyWordLimit (sizeof(gKeyWords) / sizeof(char*))


*

ivan.moony

  • Trusty Member
  • *********
  • Terminator
  • *
  • 948
    • Structured Type System
Re: S-Expression Query Language
« Reply #9 on: April 12, 2018, 12:06:01 am »
Yes, X-macros are somewhat like what I'm talking about. If I'm correct, we just need to define every operation by a macro, and the pattern match does the job of extracting the information, parameters to result, or result to parameters. It is really not a big deal, once we realize it. The trick is that we shouldn't use any built in function, not even increment by one. Once we have them all defined in terms of macros, the whole new world opens, from parameters <- [query] -> result relation, to assumption <- [logic proof] -> conclusion relation. Simple, isn't it? The only question is how expressive the macro system is.

I'm sure there are tons of similar material out there, but unless a possible use is recognized, we can't really do much with it just because we don't see the real potential. We just don't know how to use it. Unfortunately, when I threw a look at macros back in 1996., I didn't realize what they could do. I got a similar thing by myself a few months ago, but now it looks promising, and I wish I had someone to explain it to me some twenty years ago.

Still, I want to implement the engine in Javascript and apply it to crowdsourced online knowledge mining to see how far it can go.
Dream big. The bigger the dream is, the more beautiful place the world becomes.

*

infurl

  • Trusty Member
  • *******
  • Starship Trooper
  • *
  • 481
  • Humans will disappoint you.
    • Home Page
Re: S-Expression Query Language
« Reply #10 on: April 12, 2018, 12:30:11 am »
The only question is how expressive the macro system is... I'm sure there are tons of similar material out there, but unless a possible use is recognized, we can't really do much with it just because we don't see the real potential. We just don't know how to use it.

Well you see, here's the thing. X-macros are just a way of implementing a simple relational database at compile time in a C program, for code generation. Relational databases are a well known concept with lots of applications and if you've used an enterprise grade RDBMS like Oracle or PostgreSQL then you might have some idea of their real power. (I should point out that SQL/Server, MySql and MS-Access are just toy implementations of SQL not worth wasting your time with, although apparently a lot of people do. Haha, fools.)

So I have many gigabytes of data comprising different kinds of knowledge bases aligned and stored in my database server, and I use SQL to extract the information and recombine it in different ways to generate the code for my artificial intelligence software. I'm still ramping up my builds as I add more knowledge sources, but we're already talking about millions of lines of code in a very high-level language of my own design, which ultimately compiles down to C and machine code. I like to think that I'm doing AI on an industrial scale. :D

*

ivan.moony

  • Trusty Member
  • *********
  • Terminator
  • *
  • 948
    • Structured Type System
Re: S-Expression Query Language
« Reply #11 on: April 12, 2018, 01:56:10 pm »
The only question is how expressive the macro system is... I'm sure there are tons of similar material out there, but unless a possible use is recognized, we can't really do much with it just because we don't see the real potential. We just don't know how to use it.

Well you see, here's the thing. X-macros are just a way of implementing a simple relational database at compile time in a C program, for code generation. Relational databases are a well known concept with lots of applications and if you've used an enterprise grade RDBMS like Oracle or PostgreSQL then you might have some idea of their real power. (I should point out that SQL/Server, MySql and MS-Access are just toy implementations of SQL not worth wasting your time with, although apparently a lot of people do.
I didn't work with such advanced database tools. What, for example we can do with those?

(I have a kind of relational algebra in mind for a future use of my language. I want to classify all the data in ontology manner, powered by relational algebra defined in a functional paradigm.)

Haha, fools.)
Please don't...

So I have many gigabytes of data comprising different kinds of knowledge bases aligned and stored in my database server, and I use SQL to extract the information and recombine it in different ways to generate the code for my artificial intelligence software. I'm still ramping up my builds as I add more knowledge sources, but we're already talking about millions of lines of code in a very high-level language of my own design, which ultimately compiles down to C and machine code. I like to think that I'm doing AI on an industrial scale. :D
Sounds like a big project.
« Last Edit: April 12, 2018, 02:27:59 pm by ivan.moony »
Dream big. The bigger the dream is, the more beautiful place the world becomes.

*

spydaz

  • Trusty Member
  • ****
  • Electric Dreamer
  • *
  • 131
Re: S-Expression Query Language
« Reply #12 on: April 12, 2018, 04:39:37 pm »
These entanglements can be tricky!

But it all seems relational;

It depends on how you capture and store the data: database type is actually irrelevant - As an XML file can become a database; dealing with database size can be an issue! but by creating DataMarts (subsets of data) this problem can be addressed.

If the data has no actual meaning full structure it has no real use. just means that your a hoarder of data!

in the data collection process entanglements should be considered; Propositions (statements) can be handled with propositional logic calculus - Right too for the right job.... There is no need to re-invent the wheel. to do MATH with words. the propositional calculus enables for this ... Managing, Subject Predicate Object relationships.......calculating the entanglements... the calculus is very Boolean!

I have written some papers -- recently i have found my papers even being cited! lol (so happy) ....I believe releasing papers or another attempt at Vanity! just like releasing a record!.... And now just having a GitHUB! / YOUTUBE is enough to satisfy and prove to the community that you know what you know.... papers are actually becoming a dated art form ...... most papers are fake and cannot be reproduced. when you have 100 dissertations to read over the summer and mark them you don't have time to check every project for validity! this is life lots of fakes get through! (Experience talking)...


*

ivan.moony

  • Trusty Member
  • *********
  • Terminator
  • *
  • 948
    • Structured Type System
Re: S-Expression Query Language
« Reply #13 on: April 12, 2018, 06:35:14 pm »
If we put data entanglements right, then all the calculations could be done by simply querying data structures. I believe the same thing happens when you're constructing a processor with its assembler. And I'm trying to extract a higher level version of it. It has to be able to do anything that a human mind can conceive (in a sense of reconstructing a thought process).
Dream big. The bigger the dream is, the more beautiful place the world becomes.

*

spydaz

  • Trusty Member
  • ****
  • Electric Dreamer
  • *
  • 131
Re: S-Expression Query Language
« Reply #14 on: April 12, 2018, 09:48:31 pm »
If we put data entanglements right, then all the calculations could be done by simply querying data structures. I believe the same thing happens when you're constructing a processor with its assembler. And I'm trying to extract a higher level version of it. It has to be able to do anything that a human mind can conceive (in a sense of reconstructing a thought process).

Recently i wrote a token-izer program and now understand the importance of parsing a language with a simple syntax a lot can be achieved. Coding wise i found that "Extension methods helped" .... (.NET) ... For me removing invalid Tokens has become a Great TOOL... With this Project As each method to read the syntax the ability to chain all the commands into a Long Calculation can be easily achieved....
It will be an interesting read....
I like infuls Usage of the syntax!!!
Thinking along these lines is the way forward to great solving many NLP Extraction and entanglement logic for words.