Exp-Log (a deductive system)

  • 40 Replies
  • 8058 Views
*

ivan.moony

  • Trusty Member
  • ************
  • Bishop
  • *
  • 1629
    • contrast-zone
Re: Exp-Log (a deductive system)
« Reply #30 on: August 29, 2021, 06:03:20 pm »
Semantic rhombus

The whole rhombus is defined by semantic rules. We give input. The task is to extract output. To compute output, we abduce from goals to input. Output is then in the way of this abduction. If there are many outputs, the one closest to goal is chosen. As an additional way to verify if input is correct, prior to extraction of output, we may try to deduce from facts to input.
Code: text
                    FACTS
                      _
                    _/ \_                      D ||      /\
                  _/ \_/ \_                    E ||     //\\
                _/ \_/ \_/ \_                  D ||    //||\\
              _/ \ / \ / \ / \_                U ||      ||
             /                 \               C ||      ||
          _         INPUT         _            T ||      ||
        _/  _   _   _   _   _   _  \_          I ||      ||
      _/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_        O ||      ||
    _/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_      N ||      ||
  _/ \ / \ / \ / \ / \ / \ / \ / \ / \ / \_      ||      ||
 /                                         \     ||      ||
                  SEMANTICS                      ||      ||
 \_                                       _/     ||      ||
   \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/       ||      ||
     \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/         ||      || A
       \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/           ||      || B
         \_                       _/             ||      || D
                    OUTPUT                       ||      || U
             \_               _/                 ||      || C
               \_/ \_/ \_/ \_/                   ||      || T
                 \_/ \_/ \_/                   \\||//    || I
                   \_/ \_/                      \\//     || O
                     \_/                         \/      || N
                       
                    GOALS

*

ivan.moony

  • Trusty Member
  • ************
  • Bishop
  • *
  • 1629
    • contrast-zone
Re: Exp-Log (a deductive system)
« Reply #31 on: December 09, 2021, 11:30:31 am »
Quote
introduction to intermezzo programming

[Intended audience]

Beginners in language parsing, term rewriting, and logic deduction

[Short description]
As an embodiment of general problem solving strategy related to term rewriting, Intermezzo aims to be a host for a variety of kinds of formal languages, exhibiting rule-based programming system. For each area of interest, one is able to define a custom domain specific language in a language oriented programming paradigm. Having clearly defined communication input and output forms, Intermezzo performs transition from input to output by additionally defining possibly Turing complete set of chaining production rules. This sort of arrangement also sheds light on Intermezzo from an angle of systems theory, thus broadening a possible range of use cases.

[References]
Wikipedia web site

link to the paper

Anyone cares for a review? It's some 30 min read, less if you skim it fastly?

*

infurl

  • Administrator
  • ***********
  • Eve
  • *
  • 1341
  • Humans will disappoint you.
    • Home Page
Re: Exp-Log (a deductive system)
« Reply #32 on: December 10, 2021, 01:03:05 am »
That is beautifully presented and a subject area where I have done a lot of work. Code generation is a very useful technique and after completing a number of major projects with it I thought it would be useful to develop a generator for code generators. It took a lot of effort on and off over many years to build such a thing but I finally achieved it and experimented with some non-trivial applications of the technology. However in the end it seemed to have been not worth the effort because it was much more efficient to apply the meta-programming techniques that it took to get it to work directly to the problems that I was trying to solve.

If you are planning to pursue it further you should think in terms of graphs rather than acyclic graphs. Higher levels have to be able to introspect and summarise elements that are generated at lower levels. In other words, there needs to be feedback in the process.

*

ivan.moony

  • Trusty Member
  • ************
  • Bishop
  • *
  • 1629
    • contrast-zone
Re: Exp-Log (a deductive system)
« Reply #33 on: December 10, 2021, 04:05:42 am »
That is beautifully presented and a subject area where I have done a lot of work. Code generation is a very useful technique and after completing a number of major projects with it I thought it would be useful to develop a generator for code generators. It took a lot of effort on and off over many years to build such a thing but I finally achieved it and experimented with some non-trivial applications of the technology. However in the end it seemed to have been not worth the effort because it was much more efficient to apply the meta-programming techniques that it took to get it to work directly to the problems that I was trying to solve.

Great to see someone is also interested in this subject. The current code generation industry state with LLVM and company is a bit clumsy by my opinion. They may got the backend right (all the optimization and machine stuff), but I think their frontend can be better.

Any chance we could be more informed about your project  soon?

If you are planning to pursue it further you should think in terms of graphs rather than acyclic graphs. Higher levels have to be able to introspect and summarise elements that are generated at lower levels. In other words, there needs to be feedback in the process.

I thought pattern matching introduces recursive graphs?
« Last Edit: December 10, 2021, 12:57:01 pm by ivan.moony »

*

ivan.moony

  • Trusty Member
  • ************
  • Bishop
  • *
  • 1629
    • contrast-zone
Re: Exp-Log (a deductive system)
« Reply #34 on: January 03, 2022, 11:34:24 am »
3.1. automata programming

[Automata theory](https://en.wikipedia.org/wiki/Automata_theory#Classes_of_automata) is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word automata (the plural of automaton) comes from the Greek word automatos, which means "self-acting, self-willed, self-moving". An automaton (Automata in plural) is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically.

There exists a whole variety of more or less general classes of automata. Being Turing complete, *Intermezzo* is capable of emulating any automata, and here we bring an example of input/output stateless automation. The property of being stateless means that the automation doesn't remember any state on each call to the automation. This means that if we want to deal with states, we have to pass the states with an input, and return the modified states with an output each time we run the automation. This way, the states are evolving on each cycle of running the automation until we reach a state of ending the automation operation.

The following example represents a number guessing game, and bases its operation on repetitive cycles, passing through operational states on each input/output cycle. On the first cycle, the example in output asks a user to imagine a number between 1 and 8, while the automation starts guessing what is imagined number. Each cycle is comprised of a binary search, asking if the imagined number is less than, greater than, or equal to guessed number. Finally, in four or less steps, the automation declares its victory when the user admits that the guessed number is equal to imagined number.

Code
(
    COMPOSITE
    (
        INPUT
       
        (
            ELEMENTARY
            TOP
            <{"input": "start"}>
        )
        (
            ELEMENTARY
            TOP
            <{"input": "less", "state": {"guess": "<Num>", "delta": "<Num>", "step": "<Num>"}}>
        )
        (
            ELEMENTARY
            TOP
            <{"input": "more", "state": {"guess": "<Num>", "delta": "<Num>", "step": "<Num>"}}>
        )
        (
            ELEMENTARY
            TOP
            <{"input": "equal", "state": {"guess": "<Num>", "delta": "<Num>", "step": "<Num>"}}>
        )
       
        (ELEMENTARY <Num> <1>)
        (ELEMENTARY <Num> <2>)
        (ELEMENTARY <Num> <3>)
        (ELEMENTARY <Num> <4>)
        (ELEMENTARY <Num> <5>)
        (ELEMENTARY <Num> <6>)
        (ELEMENTARY <Num> <7>)
        (ELEMENTARY <Num> <8>)
    )
    (
        CHAIN
       
        // init
        (
            ELEMENTARY
            <{"input": "start"}>
            <{"output": "Imagine a number between 1 and 8. Is it 8?", "state": {"guess": "8", "delta": "8", "step": "1"}}>
        )
       
        // less
        (
            EQUALIZE
            (ID (DOMAIN <Guess> <Num>) (DOMAIN <Delta> <Num>) (DOMAIN <Step> <Num>))
            (
                ELEMENTARY
                <{"input": "less", "state": {"guess": "<Guess>", "delta": "<Delta>", "step": "<Step>"}}>
                <{"output": "Is it <Guess> - <Delta> / 2?", "state": {"guess": "<Guess> - <Delta> / 2", "delta": "<Delta> / 2", "step": "<Step> + 1"}}>
        )
       
        // more
        (
            EQUALIZE
            (ID (DOMAIN <Guess> <Num>) (DOMAIN <Delta> <Num>) (DOMAIN <Step> <Num>))
            (
                ELEMENTARY
                <{"input": "more", "state": {"guess": "<Guess>", "delta": "<Delta>", "step": "<Step>"}}>
                <{"output": "Is it <Guess> + <Delta> / 2?", "state": {"guess": "<Guess> + <Delta> / 2", "delta": "<Delta> / 2", "step": "<Step> + 1"}}>
        )
       
        // equal
        (
            EQUALIZE
            (ID (DOMAIN <Step> <Num>))
            (
                ELEMENTARY
                <{"input": "equal", "state": {"guess": "<Num>", "delta": "<Num>", "step": "<Step>"}}>
                <{"output": "Got ya in <Step> steps!"}>
            )
        )
    )
    (
        OUTPUT
       
        (ELEMENTARY <1> <Num>)
        (ELEMENTARY <2> <Num>)
        (ELEMENTARY <3> <Num>)
        (ELEMENTARY <4> <Num>)
        (ELEMENTARY <5> <Num>)
        (ELEMENTARY <6> <Num>)
        (ELEMENTARY <7> <Num>)
        (ELEMENTARY <8> <Num>)
       
        (
            ELEMENTARY
            <{"output": "Imagine a number between <Num> and <Num>. Is it <Num>?", "state": {"guess": "<Num>", "delta": "<Num>", "step": "<Num>"}>
            BOT
        )
        (
            ELEMENTARY
            <{"output": "Is it <Num> - <Num> / 2?", "state": {"guess": "<Num>", "delta": "<Num>", "step": "<Num>"}>
            BOT
        )
        (
            ELEMENTARY
            <{"output": "Is it <Num> + <Num> / 2?", "state": {"guess": "<Num>", "delta": "<Num>", "step": "<Num>"}>
            BOT
        )
        (
            ELEMENTARY
            <{"output": "Got ya in <Num> steps!"}>
            BOT
        )
    )
)

The input/output process of guessing is using [JSON](https://en.wikipedia.org/wiki/JSON) format to exchange data between operation cycles. It is expected from an outer resource to calculate math expressions in JSON data prior to sending it to the next cycle (it is possible to implement these calculations as *Intermezzo* rules, but for a sake of simplicity of the example, we choose to leave out these definitions). Communicating between cycles, regarding to previous `output` question, we store to `input` property an arbitrary choice of `less`, `more`, or `equal` keywords, while `state` property from the previous output is copied to `state` property of the next input.
« Last Edit: January 03, 2022, 12:12:51 pm by ivan.moony »

*

ivan.moony

  • Trusty Member
  • ************
  • Bishop
  • *
  • 1629
    • contrast-zone
Re: Exp-Log (a deductive system)
« Reply #35 on: January 18, 2022, 10:48:35 am »
This whole automata emulation inside stateless environment is cumbersome. I want it to be simpler. States exist in real world, right? Why shouldn't then they be a part of the language?

I need to construct a stateful automata environment to embrace that stateless insides. Maybe I'll go for it in a direction of generalizing all three important automata classes (finite state, pushdown, and Turing machines) into a single automation parameterized kind.

But why wouldn't I use only Turing machine if it has greater expressive power than finite state and pushdown automata? Because pushdown is simpler to use than Turing, and finite state is simpler to use than pushdown. Turing machine is a necessary evil we should reach for only if we have to. Otherwise, those simpler kinds should be at disposition to easy up our work.

*

MagnusWootton

  • Starship Trooper
  • *******
  • 465
Re: Exp-Log (a deductive system)
« Reply #36 on: January 18, 2022, 06:44:26 pm »
I prefer ANNs or Direct hardware logic, to turing machines by a mile,  heaps simpler, also universal.


*

ivan.moony

  • Trusty Member
  • ************
  • Bishop
  • *
  • 1629
    • contrast-zone
Re: Exp-Log (a deductive system)
« Reply #37 on: January 18, 2022, 08:51:42 pm »
I prefer ANNs or Direct hardware logic, to turing machines by a mile,  heaps simpler, also universal.

Doesn't ANN resemble a stateless machine? You call ANN with some parameters, you get some result. No states remembered between cycles.

Edit:
What I like about Turing-like machines is that they are easy to formally describe and reason about. This provides a fruitful ground for algorithm synthesis. This is also a case with lambda calculus, though LC is a stateless and no-user-interaction-in-between-intended kind of a computation.
« Last Edit: January 18, 2022, 09:27:59 pm by ivan.moony »

*

ivan.moony

  • Trusty Member
  • ************
  • Bishop
  • *
  • 1629
    • contrast-zone
Re: Exp-Log (a deductive system)
« Reply #38 on: April 10, 2022, 10:40:28 pm »
Boy, was this a Gordian knot...

Quote
2.2.1. semantic rhombus

Semantics of *Canon* is contained within composing two kinds of rules: forward and backward rules. The semantics of these rules may be described by a vertically split rhombus representing a complex forward rule as a whole on the left, and a complex backward rule as a whole on the right side. Complex rules are consisted of other complex or simple rules. Simple rules are made of two sides simply linked without any internal structure.

Code: text
     ----------------------------------   ---------------------------------- 
    |                                  | |                                  |
    |     ||                      BACK | | FORE                      /\     |
    |     ||                           | |                          //\\    |
    |     ||                          /| |\                        //||\\   |
    |     ||                        / \| |/ \                        ||     |
    |     ||                      / \ /| |\ / \                      ||     |
    |     ||                    / \ / \| |/ \ / \                    ||     |
    |     ||                  /        | |        \                  ||     |
    |     ||                /  FORWARD | | BACKWARD \              B ||     |
    |     || F            /      RULES | | RULES      \            A ||     |
    |   D || O          /              | |              \          C || A   |
    |   E || R        / \ / \ / \ / \ /| |\ / \ / \ / \ / \        K || B   |
    |   D || W      / \ / \ / \ / \ / \| |/ \ / \ / \ / \ / \      W || D   |
    |   U || A    /                    | |                    \    A || U   |
    |   C || R          CHAINING RULES | | CHAINING RULES          R || C   |
    |   T || D    \                    | |                    /    D || T   |
    |   I ||        \ / \ / \ / \ / \ /| |\ / \ / \ / \ / \ /        || I   |
    |   O || R        \ / \ / \ / \ / \| |/ \ / \ / \ / \ /        R || O   |
    |   N || U          \              | |              /          U || N   |
    |     || L            \   BACKWARD | | FORWARD    /            L ||     |
    |     || E              \    RULES | | RULES    /              E ||     |
    |     ||                  \        | |        /                  ||     |
    |     ||                    \ / \ /| |\ / \ /                    ||     |
    |     ||                      \ / \| |/ \ /                      ||     |
    |     ||                        \ /| |\ /                        ||     |
    |   \\||//                        \| |/                          ||     |
    |    \\//                          | |                           ||     |
    |     \/                      FORE | | BACK                      ||     |
    |                                  | |                                  |
     ----------------------------------   ----------------------------------

The left side of the rhombus is depicting complex forward rule. It is containing arranged `forward rules`, `chaining rules`, and `backward rules`. The same side of rhombus is diverging branches from `BACK` node downwards, in a direction of forward rule, forming initial deduction tree. The same side of rhombus is also diverging branches from `FORE` node upwards, in a direction of backward rule, forming opposed abduction tree. The deduction and abduction branchings of the left side are required to be linked by the middle area of `chaining rules`, thus forming a complete inference system from `BACK` node to `FORE` node.

The right side of the rhombus is depicting complex backward rule. It is similar to the left side, only flipped upside-down.

*

ivan.moony

  • Trusty Member
  • ************
  • Bishop
  • *
  • 1629
    • contrast-zone
Re: Exp-Log (a deductive system)
« Reply #39 on: April 11, 2022, 05:59:47 pm »
Gordian knots! Gordian knots everywhere! Read all about it!

Well, just another checkpoint in my research. It is somewhat heavy read, but if you like theory about experimental programming languages, here's the link.

*

ivan.moony

  • Trusty Member
  • ************
  • Bishop
  • *
  • 1629
    • contrast-zone
Re: Exp-Log (a deductive system)
« Reply #40 on: May 11, 2022, 04:58:51 pm »
I'm organizing the future direction of the project. The decision is to make it capable of a planning as a problem solving manner. I expect it to be able to solve toy problems like "wolf, goat, cabbage", "monkey and banana", and "blocks world".
« Last Edit: May 12, 2022, 02:48:13 am by ivan.moony »

 


Users Online

80 Guests, 2 Users
Users active in past 15 minutes:
8pla.net, ivan.moony
[Trusty Member]

Most Online Today: 100. Most Online Ever: 2369 (November 21, 2020, 04:08:13 pm)

Articles