Building Blocks For MetaProgramming Code Synthesis

[Josh SternModerator]

Building blocks for robotic/drone planning algorithms is an area that would be fruitful for this sort of metaprogramming development.

Generalization of hard & soft-hard realtime control loops would be one key block.

Generalization of collision avoidance.
Sensor interpretation/control.
Force control
Locomotion
…

Meta-synthesis should have a goal of generating nearly identical code for alternative embedded devices and VR simulators.

[Josh SternModerator]

Briefly thoughts on architectural/structural building blocks.

Hoare Logic – can be built up incrementally.

Inside of { Blocks of Code } there is some sequence of primitive steps executed in usually 1, but possibly some finite number of threads.

Focus on the Hoare Logic meaning of each single primitve statement. What changes? Might include subsets of the folowing

1) Specific bits/bytes
2) Semantic interpretations of “The Information That X” in some language connected to some local set of bytes
3) Stuff that a compiler optimizes against or might as costs – including multiple forms of time cost
4) Operating system stuff
5) Library stuff
6) These sorts of things in other processes or on other machines

How do you build up a high level language of that from low level parts. Hard to say without trying. The effort should be organized as a team effort that expects many rapid iterations in the beginning as new “must haves” get added and old versions get improved by refactoring. But it’s clearly something that is doable on a needs basis, while never being 100% complete

There must be induction steps that allow the effect of the next statement to modify the context of the above things built up by the earlier part of the block. Function calls can happen within blocks, so function/procedure wrapping around blocks happens at the same time.

At a higher level of MetaProgramming we link high level pattern statements to methods of providing specific implementations satisfying the partial specs. The implementation includes generated/analyzed source or IL code. I think of these statements as somewhat like the style of Prolog constraint satisfaction without matching in details or limitations of that framework.

If we don’t allow high level designs/plans based on semantic intents & connections to byte representations, then the search is like blind evolution. Our contrasting goals is to write in a high level semantic language & view the generated source as one example of a nice, satisfying implementation of what we said we wanted to produce.

Edit: Note – the reason for including all dimensions of optimization that we care about is not to score 86 vs. 85 on a speed test. The goal is to have machines produce reams of high quality code, unattended & often uninspected while being subject to rigorous automatically generated testing of various types. If the optimization is sometimes something that matters – esp if the otherwise dumb machine can be off by a factor of 100 or 1000 – then it needs to be represented as a substrate of programmer common sense. Don’t get hung up on whether 86 or 85 or more correct for the specifics.

[Josh SternModerator]

Requirements for Semantics, as opposed to a high level language that uses semantics…i.e. define precise digital forms for semantic distinctions, events involving them, & subset distinctions. Manipulating & understanding these for people is to be facilitated by additional high level languages. The list below is roughly about a “Unified Domain Modeling Assembly Language”

1) Should mostly all in the digital realm, while including the potential for well described external sensing. The latter is an extra class of open ended features that makes it “real” in some philosophical & practical ways.

2) Should eventually include bidirectional links to natural language, but that should not be necessary for getting started or basic programming.

3) Should be easy to create & compare precise digital reprentations of various info contained in UML style presentations. We are less interested here in the parts of UML that relate to source code implementation & more interested in the parts that related to domain models.

4) Elsewhere on my blog I’ve highlighted work that has been done on creating executable versions of AbstractStateMachine language, matching it to execution engines & proof theory. While also highlighting the need for modeling timing interactions and physical measurements in the representation. There is GT work on developing that further. For example – what is a good simulation of 2 people on a teeter-totter juggling & throwing 8 balls back and forth at the same time – you need quantities, independent machines, & timing for some spec designs. But the spec doesn’t *have to be* a picture of what either person looks like.

5) Concretely – things similar to config files/JSON should be available as unique atoms. Also, multidimensional arrays & collections over atoms/numbers/strings. These things only matter as formulae. Any advanced math should be constructed, rather than primitive.

6) Different representations of time should be included. These span real world time, event times, sequences/plans, hypothetical & fictional constructs, etc.

The text above should make it clear that the Domain Modeling Assembly Language is an open ended-project. But we can tightly measure progress an adequacy.

For 1 specific software program or module, it should be the case that all statements about correct semantic behavior for just that code can be expressed in terms of constructs in the semantic language and links between those terms & the terms of the software/hardware world that offer tight representative mappings. Some other forms of correctness are general practice for the software/hardware.

For sets of many programs, we can assess whether the assembly language works well for all of them.

Take note of celebrated victory over egghead point: we are not solving the undecidable problem of reasoning about termination of a Turing machine. We are saying “My good machine will do these things & my good system will build it using blocks that terminate. I don’t give a hoot about trying to understand your third party code mess.”

Note that it is perfectly fine to say that the domain model of some particular piece of code is an algorithm that runs on bits, or doubles, or bigNums, etc. That domain model says what we care about. It doesn’t include array index counters, or other software elements that are implementation & not part of the domain model specification. It should be a kind of lemma that we can always find all of the domain info in the software, somewhere, once the input has been read (and it therefore becomes part of the lifetime-of-code-states.

For metaprogramming development, we need new language levels that allow easy, quick, & efficient construction of the assembly language specs & links to software targets. That level is judged along the lines of overall development productivity/quality.

[Josh SternModerator]

With advanced tech, we can create an advanced separation of concerns:

In the Information Flow concern, bits of information are gathered from many different sources/places, at different time points in real time & execution time, and combined at different points – some info, for example, is used to form requests/lookups/menus for other info.

In the Platform Concern, we have various combos of hardware, software, network topology, etc that adapt in various ways to what is provided by different software users.

In the Algorithm Concern, we have different advanced ways for efficiently performing different tasks in a sequential way

Programming by & for regular humans, makes ubiquitous use of implicit theorems about where a given type of concern is “calm” in the sense that no intermediate updates are occuring. The form of these lemmas is like:

Any Update To Concern X would, in std practice, do the following:
a) Include some of these essential X declarations (via headers or other appropriate mechanisms)
b) Not violate these information hiding/protection regimes in the code
c) Either make global variables (frown!) or include local variables in the current function arguments..

The absence of the above implies either calm or an exceptional code smell condition. The latter is caught by general inspection.

Algorithmic development doesn’t need to use the same forms as humans, but there is a need for parallel mechanisms that cut down on the multidimensional reasoning involved at each given step of progress in implementing the global goals & sub-goals of the program.

In the Style/Presentation Concern, we have different ways of showing surface behavior for different audiences & different platforms.

In the Storage & Security Concerns, we have issues with where bits of not currently active infrastructure & user data reside and what controls safe & authorized access. In the related…

User Identity & Privacy & Authorization concern we have issues with how do we identify & matchup & save only the right info & guard it and authorize access from different points, in different ways over time.

In the Domain Model Concern, we have the representation & use of special knowledge, formula, modeling needs etc for particular domains of focus, representation, work, etc. More sharing across apps would be great…

There are probably some other bits worth mentioning. But its clear that gaining the ability to individually specify these parts & generically combine them in pro software would bring a lot of efficiency & power & quality with a lot less time required on new implementations to get to the basic entry level of a pro app.

Edit: Each separation of concern can often be looked at as having a goal stack to complete. Reverse chaining (e.g. like a Prolog program search) can be a helpful metaphor for the processes of satisfying goals by completing sub-goals. But because we have separation of concerns, each concern does not have the foresight or ability to describe the global search process for the realized sequence of programmatic execution in a sequence of computational states. Some choices about what needs to happen first will, for example, be determed by sub-goals of arranging our info in order to utilize a particular set of pre-existing library routines. Some goals may require veto of proposed routes that other plans would choose to pursue first. In order to build a global plan, constructed out of elemental steps, we have to construct a way of filtering the elemental steps that are available from the POV of each concern. Many of the filter reactions are a NoOp, so we might again consider using signals/slots to schedule the consults at the points where there is plausible interest. The planning should try to work with sets of required and potentially permitted elemental actions, described parametricaly, and then proposed sequences of those described with proposed instantiated types and transformations of types/info.

[Josh SternModerator]

Elsewhere on the blog, I’ve recommended the work being done on using Abstract Machine Models (ASM) as domain models which can be used for describing, reasoning, about, checking, and meta-programming with partial specs. One of the important additions they have added is the concept of independently threaded machines that have some kind of coordination constraints described in terms of choice of a partially (or totally) ordered timeline of intervals [start,end] and constraints on the temporal coordination of the otherwise independent machines.

Today I suggest that a further help is adding the relationship that a particular state or transition can be recursively described as implementated by other abstract machines, and that we should be an aspect-oriented Hoarse logic that encompasses the effects of the subordinate machines on the top level pre-run and post-run states.

Note that a finitely bounded set of recursions is just convenient, but highly desirable syntactic/cognitive/visualization sugar. While a description of recursion bounded by a computated stopping condition is a more powerful element.

An important application of these techniques is the ability to include VR models of domain actors and ASM models of multiple compute nodes and sensors all together in a temporally and causally connected large model. Any compute node, for example, may include internal representations of some information about some parts of the VR model that it uses for computation. Aspect-oriented perspective allows us to isolate updates to those elements, keeping them organized in a way that is separate from other overhead/bookeeping involved in running computers and algorithms. Representational state, might include a list of relational predicates of the form [The information that R(x1,x2,…,[time1,time2]) ]. In other words, “The information that…” is our linguistic way of referring to that aspect of the computation. It is causally updated by both sensor readings and perhaps the performance of compute actions that we “are sure” will effect a given change…e.g. the output or graphics routine returned without error.

[Josh SternModerator]

The Erlang language fell into mafia disfavor and suffered from lack of practical applications. But the syntax for distributed algorithms is worth glancing at for inspiration regarding the purely algorithmic aspects of distributed coordination.

Spawning Workers in Erlang.

The emphasis there is on workers named by integers. One might also consider lists of symbolic names with an easy syntax for that.

[Author]

Posts