Binary Structure CalculusRecently, 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:

`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.