4 ms·

The approach is an iterative deduction with strict call-conventions. In some cases I compile the rules as-is into a C-Program, but if the used memory is provabl

by maweki 5y ago

The approach is an iterative deduction with strict call-conventions. In some cases I compile the rules as-is into a C-Program, but if the used memory is provably bounded, I compile to a finite state machine + some registers. Had to ditch the extensional database for that. Not strictly necessary, as it turns out. You can read it here (https://doi.org/10.1007/978-3-030-68446-4_11 https://doi.org/10.1007/978-3-030-68446-4_11, behind paywall) or hit me up on researchgate for that paper. Or as a short overview: https://dbs.informatik.uni-halle.de/microlog/ https://dbs.informatik.uni-halle.de/microlog/ The main problem, which I claim to solve, is the handling of side-effects. For the microcontroller (or a robot) it is vitally important to not have side-effects or at least have them explicit for the developer and the language semantics. I believe this is where most approaches fail, that they model effectful input-gathering just as input-relations, but you need to control your input as well as your output in an interactive application.

YeGoblynQueenne 5y ago
Oh, so you publish in logic program synthesis then? Your field and mine (Inductive Logic Programming) are practically neighbours! :) The paper looks interesting, I'll have a look. (Although I guess your work is more on the "transformation" part of "logic-based program synthesis and transformation"). >> I believe this is where most approaches fail, that they model effectful input-gathering just as input-relations, but you need to control your input as well as your output in an interactive application. To be honest, I struggle a bit with the terminology here because I'm woefully behind with my knowledge of modern Datalog (I only need to use the bog-standard language from the '80s to achieve my goals). For example, I'm not sure what counts as input and output in Datalog parlance. I think "input" is your intensional and extensional definitions, then output is the ground facts derived from them? I'm interested in this also: >> Had to ditch the extensional database for that. Not strictly necessary, as it turns out. Is that explained in the paper?
- maweki 5y ago
  Usually (using differential dataflow, for example) you have input relations (EDB) and you have some output relations (subset of IDB). You would loop over the output relation using your host-language to call some effectful functions using the result (printing, in the simplest case). Only deducing facts without calling an external function with those facts is not useful for an interactive application. >>> Had to ditch the extensional database for that. Not strictly necessary, as it turns out. > Is that explained in the paper? Yeah, but only in short. Usually you would provide a database as input. But if you have a strict call-convention (call to external functions), you can use their result to load your data dynamically from "within" you logic program, instead of the facts just "being there" or "appear". This makes static analysis much easier and given a microcontroller is basically without storage, where would you load a database from anyways, that you wouldn't know beforehand?
  - YeGoblynQueenne 5y ago
    Well I'd like to know more about ditching the extensional database, although I kiind of see how it might work, if, for example, you're generating facts by calling external functions- maybe functions getting user input, or collecting data from sensors etc? Thinking of it further, an intensionally defined program is, in a sense, just a compressed version of an extensionally defined one (in older logic programming terminology, the intenstionally defined program is a "name" for the predicates it defines), and an intensionally defined program can still "work" if you change the facts it relies on. For example, if you have a program that defines family relations you can always apply it to different individuals, of a different family etc. So I can see how it might work- but I'd like to read more about it, because as you say storing an extensional datbase takes up space and that's always a consideration even outside of microcontrollers. But I have more questions so I'll make some time to read your paper.
    - maweki 5y ago
      You can always interpret the extensional predicate p/1 as a call to a function without arguments and set-valued return. That's basically just a LOAD-instruction. But then you're back at square one considering your static analysis. So I also limit throughput in that functions are not allowed to be set-valued (which is fine in microcontrollers, as there is no standard way to encode this in memory-limited C anyways), instead you are allowed to call this function again and again over time. As a function call is a side-effect, you get new values. I am looking forward to further correspondence.

by maweki 5y ago

YeGoblynQueenne 5y ago

Oh, so you publish in logic program synthesis then? Your field and mine (Inductive Logic Programming) are practically neighbours! :) The paper looks interesting, I'll have a look. (Although I guess your work is more on the "transformation" part of "logic-based program synthesis and transformation"). >> I believe this is where most approaches fail, that they model effectful input-gathering just as input-relations, but you need to control your input as well as your output in an interactive application. To be honest, I struggle a bit with the terminology here because I'm woefully behind with my knowledge of modern Datalog (I only need to use the bog-standard language from the '80s to achieve my goals). For example, I'm not sure what counts as input and output in Datalog parlance. I think "input" is your intensional and extensional definitions, then output is the ground facts derived from them? I'm interested in this also: >> Had to ditch the extensional database for that. Not strictly necessary, as it turns out. Is that explained in the paper?

maweki 5y ago
Usually (using differential dataflow, for example) you have input relations (EDB) and you have some output relations (subset of IDB). You would loop over the output relation using your host-language to call some effectful functions using the result (printing, in the simplest case). Only deducing facts without calling an external function with those facts is not useful for an interactive application. >>> Had to ditch the extensional database for that. Not strictly necessary, as it turns out. > Is that explained in the paper? Yeah, but only in short. Usually you would provide a database as input. But if you have a strict call-convention (call to external functions), you can use their result to load your data dynamically from "within" you logic program, instead of the facts just "being there" or "appear". This makes static analysis much easier and given a microcontroller is basically without storage, where would you load a database from anyways, that you wouldn't know beforehand?
- YeGoblynQueenne 5y ago
  Well I'd like to know more about ditching the extensional database, although I kiind of see how it might work, if, for example, you're generating facts by calling external functions- maybe functions getting user input, or collecting data from sensors etc? Thinking of it further, an intensionally defined program is, in a sense, just a compressed version of an extensionally defined one (in older logic programming terminology, the intenstionally defined program is a "name" for the predicates it defines), and an intensionally defined program can still "work" if you change the facts it relies on. For example, if you have a program that defines family relations you can always apply it to different individuals, of a different family etc. So I can see how it might work- but I'd like to read more about it, because as you say storing an extensional datbase takes up space and that's always a consideration even outside of microcontrollers. But I have more questions so I'll make some time to read your paper.
  - maweki 5y ago
    You can always interpret the extensional predicate p/1 as a call to a function without arguments and set-valued return. That's basically just a LOAD-instruction. But then you're back at square one considering your static analysis. So I also limit throughput in that functions are not allowed to be set-valued (which is fine in microcontrollers, as there is no standard way to encode this in memory-limited C anyways), instead you are allowed to call this function again and again over time. As a function call is a side-effect, you get new values. I am looking forward to further correspondence.