Friday, October 20, 2017

Thoughts on how to find alternate algebra-like systems

It seems like there probably exists a category of systems which exhibit some of the most interesting and useful aspects of algebra, and yet are very dissimilar in other aspects. It’s probably a good starting point for seeking them out to consider what is arbitrary and what is significant in the operation of extant algebraic systems—in other words what is their ‘essence’, and what are their incidental aspects.

My understanding is that their main utility lies in their providing a systematic means of exploring alternate, equivalent representations of values. They let us take two representations which each evaluate to the same thing, and gives us a set of rules for transforming only the representations while the value stays the same (I call these transformations ‘ortho-semantic’ operations since they do not affect the meaning/evaluation of representations—they are orthogonal to semantics). By shifting representations around in this way, while maintaining consistent relations between them, we can discover new patterns and relationships which we would never otherwise have expected to exist.

One especially common/important goal of carrying out these transformations is to find a pair of equivalent representations, one of which consists only of a single atomic representational element whose value is unknown, while the other representation may be more complex, but readily evaluated—i.e. ‘solving for’ some unknown variable. This may generalize to something like: representations may include ‘placeholder’ elements which cannot be evaluated in isolation; however, when equivalent representations are put into some kind of correspondence (e.g. like being placed on either side of an equals sign in traditional algebra), applying sequences of ortho-semantic operations to the representations may put the system into a state in which the correct evaluation for a ‘placeholder’ element is unambiguously revealed.

My suspicion is that some of the specific features of algebra as we know it are accidental outgrowths of the historical fact that we had to do these representation transformations by writing symbols on paper. Especially given our familiarity with written language, this would bias us to a sequential, symbolic representation.  However, (what I claim are) the essential characteristics of algebra—i.e. the capability of systematically transforming equivalent representations without changing their value/meaning—do not depend intrinsically on symbol sequences.

And the kicker is: the ortho-semantic operations in the various algebras we use all depend on the notions of inverse and identity, since the two together provide a simple means of moving a symbol (or group of symbols) from one representation to its equivalent; and transforming the representations in that manner is of the essence if your machinery for carrying out and recording the transformations consists entirely in symbols drawn on paper via pencil by a human. That’s my central thesis here: we have assumed identity/inverses are part of the essence of systems that behave like algebras—but maybe they aren’t as necessary as they seem.

In the way mathematics has presently generalized specific algebraic systems into an abstract theory, inverse and identities play a very central role. I wonder two main things: 1) Could specific, alternate algebra-like systems be developed which have similar or greater power than traditional algebras, yet do not depend on inverses/identity? 2) Could a generalized mathematical theory be developed which deals more directly with what I claim is at the heart of algebra’s operation (systematically transforming equivalent representations without changing meaning/value), rather than focusing on a particular implementation of that behavior which happens to require inverses and identities? I know many will say that the rich theory around algebra is a sort of proof that it’s the ‘correct’ track—and I would counter that there’s plenty of space in the realm of pure mathematics for more such rich theories. One could also point to uses of abstract algebra in the physical sciences as a kind of proof of the same thing, but if I’m not mistaken it’s often the case already that the ground is covered by alternate theories as well, e.g. Category-theoretic formulations, so I don’t think of success of pre-existing systems as proof of any kind of ultimate correctness.

I think any algebra-like system must have these parts (and only these parts?):
  • A syntax (i.e. a definition of allowed symbols and how they may be arranged into statements; doesn’t actually have to be symbol sequences though, any consistent representation whose rules may be stated is fine).
  • A semantics: a mapping of syntactically valid statements into some other domain of ‘values’. For the system to work well it should be the case that the semantics frequently maps multiple unique syntactic statements to the same value.
  • A set of ortho-semantic operations, describing the ways in which one may convert sets of statements into equivalent sets of statements (equivalent in that the semantics would map the statements to the same values).

—maybe the general theory of these systems would use those ‘parts’ as its central terms?

One thing that occurs to me is that it’s not necessarily necessary to isolate single variables (i.e. ‘solve for’ single variables) in order to discover unknown values in other algebra-like systems. It’s necessary in algebra because if you had something like this: x + y + z = a + b + c, where x, y, and z are unknown and a, b, and c are known, it’s ambiguous which variable maps to which since addition is commutative. It’s possible that in alternate, algebra-like systems, you could perform some ortho-semantic operation which causes a number of representational parts to align unambiguously and have their meaning revealed through correspondence to the ‘partner representation’ (I would call each side of an equation one of the ‘partner representations’ in traditional algebra systems).

My best guess is that any alternate, algebra-like systems which are constructed will exist only in software, and would be very inconvenient to try drawing on paper (or at least the set of these is much larger and less explored, so we’re more likely to find something there). It could be that the ortho-semantic operations are much more complex, also, so that it’s not simple to state exactly what it does in any way than reading the algorithm that does it. So, a user of one of these alternate algebra-like systems would probably press buttons corresponding to the ortho-semantic operations in order to shift the representations around and investigate relationships.


Another mostly unrelated idea:

Why is it that we mathematically represent physical laws with equations? Generally speaking, what we’re attempting to document are how states of physical systems evolve in time after some operation occurs; so wouldn’t it make more sense to use a representation like

[state 1] {static collision} [state 2]

—where two states are related by an operation? If we were to develop an algebra-like system around this, every operation would have its own set of ortho-semantic operations (kind of like the different rules that exist if you relate two algebraic expressions by ‘<‘ or ‘>’ instead of ‘=’). Sounds like a lot of work, but it may be that there’s a more general system which can be used to automatically give sets of ortho-operations for particular physical operations (like ‘static collision’ in this example). 

Actually though, I don’t think this would work… —looking at a more concrete example:

[mass: 5, elasticity: 0.1, position: {0,0,0}, velocity: {0,0,0}], 
[mass: 8, elasticity: 0.25, position: {10,0,0}, velocity: {-2,0,0}]

{static collision} 

[mass: 5, elasticity: 0.1, position: {0,0,0}, velocity: {-3,0,0}], 
[mass: 8, elasticity: 0.25, position: {0.234,0.43,0}, velocity: {0.5,0,0}]

It is interesting though that scientific laws aren’t generally in the imperative form, like if I have a physical system in state X and do BLAH to it, Y will be the resulting state; my guess is that we use equivalence relations instead because it’s our only means of ‘doing theory’, by encoding results in equations and then looking for new relations by applying ortho-semantic operations to algebraic representations. However, that probably shapes our view of science quite a bit, in a very Sapir-Whorf manner.

Saturday, May 27, 2017

Reflections on "Toward a Noncomputational Cognitive Neuroscience"

Note on where this came from: I was bored one afternoon and one of my friends posted this paper ("Toward a Noncomputational Cognitive Neuroscience") on Facebook. I have nothing against it, I just wanted to do some writing and analysis since it had been a while, and this happened to show up. I do feel like my tone ended up being overly harsh, and I guess it did annoy me a little, but it also had some interesting ideas and who knows how off I am—so please do check it out on your own if you're curious.

Since the 'computational' is such an exceedingly far-reaching category, I keep an eye out for things which fundamentally can't be included in it. I only know of one subject totally outside its bounds: immediate conscious experience, all the qualia currently present—the subject matter of phenomenology.

Unfortunately, "Toward a Noncomputational Cognitive Neuroscience," doesn't seem to supply any new instances of the non-computational. Its central argument appears to be a straw man (but mine may in part be too, so make sure to check out [0]): it takes overly restrictive definitions of computation and information processing and then demonstrates how its alternate approach does not fall under said restrictive definitions. Yes, contemporary artificial neural nets don’t adjust their connection weights, transfer functions etc., while operating (i.e. after training), and a dynamical systems analysis of a system which does this is qualitatively different from one which does not—but computation has no intrinsic limits that would prevent someone from architecting such a neural net, even using the paper's narrow definition of computation which requires rules to be operating on representations. 

The paper's view on the difference between simplified and realistic nets is most concisely stated here:

"It is the processing of representations that qualifies simplified nets as computational. In realistic nets, however, it is not the representations that are changed; it is the self-organizing process that changes via chemical modulation. Indeed, it no longer makes sense to talk of 'representations.'"

Why would a computation which changes its own rules no longer be a computation? Such computations are at the very heart of computation theory! Additionally, the sense in which the system is no longer operating on representations can only be superficial, since at some level of interpretation, representations are still obviously a component of cognition. The difference is just that they emerge at a higher level, rather than being explicitly defined things which the base system explicitly operates on.

The separate argument about digital computers being classical, non-chaotic dynamical systems also falls flat, in my opinion. The sense in which computers are classical systems is superficial: if I can write a program for it which, at the appropriate level of interpretation, is nonlinear and chaotic—what does it matter if the substrate is classical? If you insist on only modeling the state space of the substrate, rather than something higher level, sure, it’s always classical—but what do you gain by doing that?

The bit on connecting Freud back to the super abstract dynamical systems stuff was a pretty neat idea I thought. Would be interesting to see if there’s a good fit with any ideas of, e.g., William James or Jung.

On the other hand, I suspect the paper's attempt to incorporate the ideas of Derrida et al is part of a flawed justification for considering its notion of the noncomputational to be more significant than it really is.

"Out of that intersection of ‘self’ and ‘other’ the dynamic whole evolves in its spontaneous, unexpectedly bifurcating manner. So the brain does not compute; it permits and supports ‘participation’ between self and other in the evolving whole."

I read that, and many other arguments from the paper, as being circumlocutions avoiding saying, “the system is bottom-up, not top-down.”

"The outside is not represented inside but participates on the inside as a constraint on a self-organizing process."

As far as I can tell, this usage of ‘to participate’ is just refers to something which: 'can’t be modeled top-down', and 'is one among other things involved.' Seems like it's largely, indirectly saying that cognition is emergent—and, erroneously, claiming that you can't create emergent, chaotic systems in classical computers:

"Computation as understood by the tradition is not performed by chaotic systems. Computer computation is not sensitively dependent on initial conditions."

And yet it is capable of executing programs which are.


[0] To be fair though the sense in which it is a straw man is only this: it doesn't say anything significant about computation in general, only about a special restricted Computation which it is interested in (and which I'm sure many other academics are interested in as well). The reason I take issue with it (it addition to the clickbaitiness of 'Noncomputational') is because the paper also comes with the suggestion of a paradigm shift for Cognitive Neuroscience—but this special Computation it's found a negation of isn't sufficient to constitute a paradigm shift. Anyway, considering that, much of my review may itself be a straw man. Oh well.

Saturday, July 18, 2015

The Subtle Narrowness of Human Concepts

Note: the first part was mostly just messing around with writing, and the second part is a much more direct statement of the ideas which the first is founded on.

Understanding is partially and significantly a generative capacity; and, being able to generate instances of our generic grasping, we feel ourselves to have some ambiguous command of reality. To look upon a house and consequently feel it recreated in the center of one’s self is surely a more profound act of possession than any deed could confer; but to extract from multiple unplanned viewings that which makes a house a house, and turn it around, and freely and fluidly construct never-constructed new variations, in that same most personal inner chamber—perhaps no form of ownership could be more complete. But what is the true value of this ability? In offering even a superlative commendation of the human capacity to know, one inevitably compares its worth against those of its contenders; an act of measurement, always comparative, necessarily precedes our praise. It seems, however, that we are too apt to mistake beating all contenders as furnishing proof of transcendent superiority, when really, as far as we know, the match was rather local and our champion would be devastated outside his hometown. There is a negative and a positive side to considering the situation thusly. The ostensibly negative side is that understanding begins to look more like our various other capacities—like, for example, the one which allows us to determine with our noses whether a shirt is unclean or not. The positive side is that we may attribute to reality—which, if we aren’t solidly a part of, what are we?—a dazzlingly less bounded potential, to say nothing of the general merits of taking a more realist stock of things.


For most of my life I'd assumed that human concepts were this limitless sort of thing capable of making fundamental connections to what's going on in the universe at some deep level. In more recent years I've come to consider them as almost like another sense: they are symbolic patterns consistently formed when we are exposed to certain stimuli (like our experience of smells consistently reappearing when exposed to similar molecules). Our conceptual faculty augments the pure pattern-correspondence of our more primitive senses in that the patterns can be associated with other internal patterns, and in that we can generate new patterns purely from existing patterns (using logical and analogical processes), which at some future time may be usefully associated with some never-encountered external stimulus. This is of course extremely useful—but we really must be falling into what should be an obvious trap of anthropocentrism in ascribing to them much more than that.

Thursday, June 11, 2015

Improving Idea Representation and Debate

Note: you can skip the prelude by scrolling past the screenshot.

No category of invention has ever been more influential than that of concept representation schemes, which claims such notable alumni as natural language and mathematics.

Concepts have deeply symbiotic relationships with their representations; our inklings are pitiful, delicate agoraphobes without some formal carapace to curl inside of. And, once linked, the two inevitably fuse; discerning a point of separation becomes an endless task: their boundary expands into infinite, alluring detail whose completion always appears near.

Further, our choices of formalization accrete in layers, each developing its own character, without ever fully concealing its origin.

Some representations excel at distinguishing multitudes and attaching to them, separately, myriad, manifold impressions; others have no memory for names, but are remarkably intuitive with relationships. There are factions, and contests: there are those who would have it that rigor stably supports life, and those who claim it the first sign of death. Others plead vociferously, and vaguely, for a kind of harmony. 

It was said, in a representation long forgotten, that, "no two forms possess intrinsic merit disparity; the worth of a form exists only in relation to a thought,"—but then! There arose a structure so impossibly well-balanced, so gloriously lacking in error, so frustratingly perfect, that psychotic murmurs of, "messiah," crying whispers of "divinity," and hopeless exhalations of, "God" filled the once heathen mound of abstract rabble. The one true form emerged:
The text in this screenshot is unfortunately misleading—each node should have a single sentence, plain, statement of some 'claim'—a 'proposition,' if you prefer.

Actually, no—my mistake—that's just a screenshot of a project I started nearly a year ago. Ah, well, I guess I'll just talk about it instead.

Natural language has many virtues. Formal mathematical languages also have many virtues—in fact, in a certain sense, it may even be said that they are the more virtuous of the two. Unfortunately, however, even if that is the case, in some sense, it is irrelevant: people have to actually use the language, and nobody has the time for something much more formal than natural language—not even mathematicians!

So, the idea here is to add just the smallest amount of structure to natural language: one must break their overall idea into the separate claims one desires to make—then state those claims with whatever level of formality you'd like. Furthermore, arrange your various claims so that some are supporting others; the supporting claims will be rendered as children in a hierarchy.

Once you have represented some idea, or hypothesis, in this manner, you may do a number of things with it: you can re-use its parts to state new ideas, you may share their parts or whole (though they'll be subject to rating at this point), you can request that a whole 'hypothesis' be critiqued—or, you can put it up for public debate, in the CRUCIBLE (or private debate, not in the crucible, is also fine).

The debate system emphasis the constructive qualities of argumentation: two competing hypotheses are reconciled into one improved hypothesis, with individual claims having been treated individually.

It's possible that a more refined taxonomy of rhetorical devices could be sequestered from conventional expository essay structure than just claims/justification. For instance, why not have 'alternate phrasings' or 'examples' or 'empirical evidence' be node types in the hierarchy of one's hypothesis?

Using such a system, one could represent: political arguments, business decisions, philosophical or scientific ideas—you name it!

Sunday, June 7, 2015

How to Make View-Independent Program Models

In Part 1 of this two part series, I made an argument that the standard way of structuring program authoring tools involves a peculiar and unnecessary model/view coupling that makes a number of problems in the programming tools domain more difficult than they need to be. Here I'll be describing a simple, general way of constructing generic 'program models,' which have much in common with ASTs, but improve on them in a couple of critical ways. I'll be referring to this method as the 'path formulation' of program models.

Why this structure?

Short answer: because it's simple and general, and bears a very close relation to the essential activity in high-level program construction.

The 'path formulation,' a particular way of creating program models, comes from asking the question, "what are we really doing when writing source code?" and finding the answer, "selecting and configuring abstractions provided by a programming language." In that case, writing source code is just one way of doing a more general and essential activity: selecting and configuring abstract 'language constructs.' Here's a short dialogue illustrating the point a bit more.

So, let's say your programming language provides an abstract language construct called 'function_declaration'; it is comprised of a few parts: a 'name,' a 'return_type,' and an 'argument_list.' A configuration for this construct would be a particular 'name,' 'return_type,' and 'argument_list.' What makes it 'abstract' is that none of these entities are tied to a representation. In other words, while it has become reflex to think of these sorts of constructs in terms of character sequences, here we intentionally leave open the question of how they should look.

Making Program Models using the Path Formulation

The idea behind the path formulation is: if you have a model of a programming language in the form of a graph, then individual program models are just paths through the graph.

Here's a high-level, three step recipe for making these language/program models:

(1) Represent your programming language 'abstractly,' using a formal grammar that has no lexical section (now called an 'abstract grammar'): its fundamental units are the fundamental units from your language in the abstract, rather than character sequences. Only consider which abstractions your language should include and the rules for composing them; worry about how to represent them visually elsewhere. For example, we can say that a 'class' is made up of a 'name,' a set of 'variables,' and a set of 'methods,' without any assumptions about how these things are going to look. (I talk about this in the first part, too.)

(2) Convert your abstract grammar into a graph, which will serve as the 'model' for your language. (I have some Java code that will do this for ANTLR grammars, btw, which I can clean up and share on Github if there's interest.)

(3) Represent individual programs as specific paths through the language graph.

So, if your grammar contains a subsection like this ('class_reference' is for inheritance, indicating a parent class):

: class+
: name
           : etc. etc. etc.

Your graph-based language model will have a subsection like this (black nodes are 'language constructs,' orange nodes are 'language atoms'):

And a particular program in your language, consisting of one simple class might look like this:

These paths could be represented by just listing the edges taken—though of course you have to number the edges:

Taking that approach, the model of our simple program looks like this:

 (2 2 0 1 3 0 0 3)

If we would like a little structure in our model representation, we can distinguish between 'language constructs' and 'language atoms' (black nodes and orange nodes), by using opening and closing parentheses to mark the start and end of language constructs.

(2 (2 0 1 (0... 1... 2... 3) 0 0 3))

Note: the ellipses are where we followed some hypothetical edges in 'function declaration.'

Language constructs are just composite abstractions, made up of more than one part; language atoms cannot be broken into smaller units. Actually, 'language constructs' and 'atoms' have a relationship that mirrors S-expressions in Lisp, so it's no surprise that the notation for program models resembles Lisp (here, however, we aren't tied to using this as the visual interface for the programmer).

Using Insight from the Language Model

A big advantage of the path formulation of program models is that it maintains a strong connection between elements of a user's program, and the programming language itself (since programs are paths in the language graph). This connection can be taken advantage of by programming tools to guide programmers in using the language.

As an example, let's say a programmer has just selected a 'class' construct (maybe by typing out the keyword 'class'—or in some new way); the program model now contains a node for that 'class' construct, and the editor, just by examining the 'class' node in the language model, knows all the legal options for proceeding, because each option corresponds to an edge going out of the 'class' node:

To make this as concrete as possible, I'll show one possible UI that takes advantage of this connection to the language graph. Keep in mind, though: you could still render it like a traditional text editor, using the UI contemporary IDEs use for 'auto complete' to display alternatives. It's like automatic auto complete for all aspects of the language—at the least, this would be tremendously useful to new users of a language.

In this hypothetical editor, the UI is split into two main sections: the top is our document, which is just a rendering of the program model; and the bottom contains controls for selecting and configuring language constructs.

Let's say we've just instantiated a class definition by supplying all the necessary parameters; it has the name 'InputHandler,' and our editor has 'collapsed' it, so we just see the name and type:

Since our editor is following along in the language graph, it knows we're back in the 'program' node, from which point we can begin specifying either a class or an interface. Let's say we select 'class.' Our editor now looks like this:

Notice the whole 'class' construct and the 'name' section have red borders; this is to indicate that 'class' hasn't been fully instantiated: it still has 'free' parameters that must be bound to something (in this case 'name' must be bound to something). Also notice that in the bottom section, the options appearing in the grid are just the neighbors of the 'class' node in the language graph. 

I imagine that in using a system like this, the cells in the bottom area would map to keys on your keyboard: this way you could accomplish a task like creating the skeleton of a new method declaration with a single keystroke. Something along these lines would also be much better than text editors for programming with virtual/augmented reality systems and mobile devices. Anyway, this UI is a just a quick sketch of one possible approach. The document region could also be something like this (in that video, I'm rendering the AST in manner identical to how I'm suggesting we render program models).


It's been a long time since we laid down the character sequence and parsing-based architecture of program authoring tools, and contemporary work on programming languages is deeply invested in that established approach. It seems like the program model approach could be an improvement—but who knows what lethal oversights might still be lurking. What's especially needed at this point is a concrete implementation. I'm working on it, slowly, in my free time—but my hope is that others will read the ideas here, and if the they prove to be generally interesting after all, expand and solidify them into serious tools that will improve the experience of programming for the upcoming years. If you'd like to hire me to work on something related, I can be contacted at 'westoncb[at google's mail service]' (or even if you just want to talk about it—though the comment section is probably best for that).



Identifiers etc.
Let's take a look at the abstract program graph one last time:

Notice that 'class reference' and 'name' are language atoms, but these things need structure of their own, so where does that come from? First I'll point out the reason we don't include identifiers in the language definition is that they are mnemonics for humans, not part of the abstract structure of a language; all the language needs is a unique identifier, so we just generate a random one. As for the mnemonic, maybe it should be a string, maybe something else—accordingly we leave it outside of the language spec. In the program model, we just attach the random ID (discussed earlier, too) which can be associated to some representation specified by the programmer (probably totally without their notice, by just typing in their editor as always). A program model with IDs might look like:

(2 (3 (#49843345) 0 0 (#95728745) 0  1 (... ... ... 3) 4))

There's an external file that maps these IDs to representations (often it's just a string) for editors to use.

The following section discusses how to handle the 'class reference' node and others like it.

Referencing the Program Model
There is an aspect of programming languages that isn't captured by the 'abstract grammar' that I've described so far. The abstract grammar only allows us to describe 'free' language constructs which, when supplied with specific parameters, are 'instantiated'; program models contain only instantiated language constructs. However, the 'abstract grammar' should describe the full capabilities of the language, and programming languages always contain mechanisms for referencing already instantiated language constructs: e.g., I have instantiated a 'function_declaration,' which had its 'name' parameter bound to the value 'testFunction'; other parts of my program should be able to reference this specific, instantiated 'function_declaration' by using it's 'name,' 'testFunction,' as a reference.

To be honest, I'm very curious to hear other people's ideas on how to go about doing this, though I do have an approach that seems like it would work well: extend the notation of our 'abstract grammar' (which is just some variation of BNF at the moment) to express 'queries' on program models: i.e. "select all the nodes from the program model of type 'class'." More concretely, let's say our 'class' construct is defined as follows:

: name

(The 'class_reference?' component is used to reference a parent class.)

'class_reference' would be defined in our grammar as follows (except using some appropriate notation, not English):

           : "select nodes on program model of type 'class' in same 'package'"

So, in order to instantiate a 'class_reference' the programmer would have to select a node from the program model that meets the criteria in the query. Ideally, the programmer's IDE would parse the query, run it on the program model, and offer up a selection of valid nodes. Present IDEs do this sort of thing of course, but including the necessary information in a unified, abstract language specification would be beneficial.

Why Programming Languages Use Only One 'View,' and How to Fix That

(note 1: This is the first of a two part series; part two is here: How to Make View-Independent Program Models)

(note 2: In the interest of a little more context/concreteness: here's a video of an editor I made that works by rendering a tree-based program model as described in the article (this just uses an AST, though, not a 'pure' model): Tiled Text)


It's pretty well acknowledged that the reason source languages exist is that they are better interfaces for program creation than, say, typing and reading machine code. And yet, it's kind of weird to call them 'user interfaces'—probably because they are each comprised partly of the concrete interface to some external text editor and partly of an abstract specification, this combination being a more nebulous construct than we're accustomed to labeling 'user interface.' At the same time, however, even if its form differs from our typical user interfaces, its function matches well: programmers use a text editor and programming language features as their interface to program creation.

User interfaces are something we've learned a lot about since the original architecture for program authoring software was laid down (which determines that programs will arrive in the form of character sequences and then be parsed into something more useful). Among these things learned is a useful way of analysing systems into 'models' and representations of those models, called 'views'. Furthermore, probably the strongest reason for an architecture to adopt a model/view split is that the software will require multiple representations of one model. This is very much the case for program authoring tools: for instance, source code and machine code could be generated as two representations from a pure program model (which I describe how to build here)—and we could far more easily allow multiple source views.

There are a few points I've come to believe are true which have led to a new perspective on program creation systems:

(Note: I'm going to use 'machine code' as catchall for any kind of target/output language in any kind of interpreter/compiler.)

(1) The only reason we have source languages (as opposed to machine code) is because they are better interfaces for human programmers.

(2) Program source and machine code are two representations of one abstract thing. This common 'abstract thing' is much like the models in MVC systems; accordingly, I call it a 'program model' here.

(3) ASTs are an approximation to this 'program model,' but they are biased towards one potential representation: source code.

(4) It's possible to construct generic program models, which are better at capturing the essential properties of programming languages (including, e.g., 'type' information), and which are not tied to any particular representation.

The more I think about 'program models,' the more our treatment of program source code seems bizarre. Why aren't the models of computer programs prior to their source code representations? Shouldn't program models be the basis for generating program views? Shouldn't we store models on disk and build views when using our programming tools? Shouldn't we pass models around the internet instead of views?

This more symmetric relation of the various views of a language to a single generic model, as in the image, seems more natural:

Among the many benefits we could expect to arise from structuring things this way:

  • Swappable views for programming languages (think, e.g., personally configurable 'syntactic sugar,' but on a much grander scale—definitely edging in on the realm of meat and potatoes. A primitive example: you check a box in your editor,  and now your Python-like language is rendered with curly braces instead of just tabs. A little more complex: instead of 'new Color(20, 30, 50);'—your editor renders a color picker).
  • Experimenting with UI concepts for program construction would be far less costly.
  • No need for parsing at all.
  • Dead simple for tools to give feedback on what's possible to do within your language, significantly reducing the learning curve of using a new language. (More on this in Part 2.)
  • More diverse, interesting textual representations are possible since you don't have to parse.
  • Program models could be much simpler than source code (aside from LISP: my particular formulation ends up looking like this:  (2 (3 0 0 0 1 (0 3) 4))), hence they are easier to manipulate via algorithms.

Program Views on Generic Models

The editor 'Moonchild' has some examples of the sorts of 'node views' I'm imagining in the section below. 

So, assuming we now have a generic program model (I describe how to actually build these in part two: How to Make View-Independent Program Models), what would it look like to build views based on such a model? There is a powerful, natural approach to this, which is for programming tools to mimic web browsers, whose displays are built up using algorithms on DOM trees. Our 'program model' is very similar to a DOM tree: first, it's a tree, and second, it contains the abstract structure and content of the thing to render, but doesn't say how to render it. The modern web is ample evidence that this kind of structure works well as the basis for rendering complex, diverse, text-centric layouts, with varied interaction styles.

It's probably not hard to see that we could use this structure to build visual representations of programs that exactly mirror the look of present day, pure text source code—so if 100% text is preferred, that's absolutely possible. But imagine, now that it's built on a structure that matches the web, how we could evolve pieces of our document into rich, interactive elements, when desired.

What I mean to propose here isn't that we use one view or another, though; rather, only that we maintain a more direct correspondence between elements in the visual display of our programs, and their backing models (as in the image). This is in strong contrast to the unfortunately indirect relationship found in most modern programming systems, which is necessarily mediated by parsing. For example, with this more direct relationship, just by placing your cursor somewhere in the document your programming tool knows which node in your program's model you are considering interacting with. The node might have an "on click" script attached—it might expand its visual representation, pushing the views for other nodes to the side, or shrinking nodes whose types are irrelevant to what you're interacting with.

Again though: I don't know what the better interface is, just that this opens up our freedom to explore. In our current systems, the only time we experiment with alternate views is when designing whole new programming languages; using generic program models, we can keep every other aspect of the language and just change how it's rendered for programmers.

The Difference Between ASTs and 'Program Models'

While ASTs are a sort of approximation to program models, It's probably more accurate to call them models of program source, than of programs themselves. Well, what if we model 'programs themselves' instead of 'program source'? After all, modeling program source does imply that unhealthy dependence on one view; can't we consider 'language constructs' in the abstract, separate from a visual representation? We can!

It's very common to use formal grammars to generate software for building ASTs out of program source. These grammars define the set of abstractions (i.e. 'language constructs') available to the programmers of a given language—but they do so in terms of a textual representation of these abstractions. However, if our grammars were to not bottom out in a 'lexical section,' i.e. without describing the decomposition of abstractions into character sequences—we could more directly address the 'essence' of our programming language, handling representation later.

More important than the actual act of omitting the lexical section, though, is the different way of thinking about grammars when you aren't tied to characters as the 'atoms' of your language. What would your primitive types be if not characters? Well, why not the abstract primitive types of your language?

Here's an example of the difference: let's consider how a simple function call is represented in an AST first, then in a generic program model. Here's our function call:

doCoolThing(intVar, boolVar);

And this is what it might look like as represented by an AST:

Now, as represented by a generic program model:
Notice how in the AST the function name and both arguments all appear to be the same kind of thing? That's because in the model of the source code, they are all the same thing: they're all character sequences following the rules for identifiers. In the program model, the node types relate to meaningful types within the programming language—it's not talking about character sequences at all. This makes it a much more useful model for programming systems to work with: it's a structure that relates more closely to meaning within a programming language.

The long numbers you see in the program model diagram are IDs used to associate certain nodes with arbitrary, external representations. If you'd like, there's no reason this representation couldn't just be a sequence of characters—but now it could be interchanged with any number of other things, without changing the rest of the language.

The next half of this essay: How to Make View-Independent Program Models

You might also check out: A Short Dialogue on How Crazy Human Programmers Are

Some more examples of editors that operate on models instead of text, but aren't visual languages: LamduUnisonJetBrains MPSeco

Friday, June 5, 2015

A Short Dialogue on How Crazy Human Programmers Are

This was initially part of my explanation for why people should be interested in 'syntax free' programming, but I decided to separate it. Here is the original essay.

Aliens have landed on earth. One of their computer scientists has been speaking with one of our own. They understand each for the most part, at high levels of abstraction—but they find plenty of discrepancies in the details. Now the alien is trying to grok how our programming tools work:

Alien: I understand that you have added abstractions over your 'machine code' because people find it unmanageable to build systems in a binary alphabet—but I don't see how your programmers interact with the abstractions, how they specify which they would like to use.

Human: Okay, I think I see what you mean. Well, whenever we write programs, it is in a particular 'programming language'; this language contains a set of abstractions which a programmer is free to choose from and use how they'd like. Each language assigns names to its abstractions; so the programmer types the abstraction's name in order to use it.

Alien: Alright. Maybe I do understand then—it's not so different at home: we don't usually type out the name, but we might say it out loud, or reach our hand toward it, if we see it on the 'program construct' list. I'm curious, though, after you have typed the name of an abstraction, how does this update the 'machine code' for the program you're building?

Human: Well, it's not usually just one name that has been typed, but there's a whole 'document'—just like we talked about for email, or academic papers. This document is then 'parsed,' which is a way of converting the document into a 'model': a form suitable for a running program to interact with—the program being a 'compiler' in this case. So, once the document is parsed—if it was well-formed—the compiler uses the resulting model as a basis for generating machine code.

Alien: I understand what you mean by 'parsing'—we have something similar, too. But this seems strange to me that you would involve something as complex as inferring semantics through syntax in order to update the model of your program. You mean to tell me that in order to change a single part of a program's model, you must use a document editor, find the part of the document that corresponds the part of the model you want to change, recall from memory all of the abstractions available, type out the replacement abstraction's name one character at a time, and re-parse the changed document!? Just to change one thing in the model!? You guys must be much better programmers than us after all; that would be far too difficult for us: we need to see which abstractions are valid to use at different times, and when we replace one, or add a new one—or anything like that—the program's model is updated directly, which lets our software give feedback on how to proceed.

Human (grinning and slicking hair back, then shrugging): well, it's not too hard: we've gotten really good at automating parsing, and our programming tools have document editors built in. But yeah... I guess we are pretty good!

(In case it's not obvious: the aliens were the better programmers.)