What's This Model of Computing Called?

Hello!

A few days ago, I came up with an idea for a model of computing. Assuming it's nothing new, I'm wondering what it's called, or if it even has a name. I'll describe it here, in the hope that someone will recognise it.

What, as a black box, is a program? It's something that takes a sequence of symbols (a character string) as input, makes some faint whirring sounds for a while, and hopefully gives a sequence of symbols as output when it halts (if it halts).

What's inside the black box? Well, it depends on the black box, obviously. But, in general, whatever it is, it can be described by an attributed grammar (assuming it's not a 'magic' box). According to this view, the program is a language. The input, if valid, would be a sentence of that language, and the output would be an expression of the semantics of that sentence. (Of course, that just means that the input and output sentences mean the same thing, but hopefully the output sentence is more readable, as it were.)

Without attributes, the grammar would be just an ordinary, everyday, context-free grammar. It could be expressed in BNF (or something similar). The processing of the input would be a matter of parsing the input string according to the grammar. For such parsing, I had recursive descent with full back-tracking in mind, where alternatives in a production are tried in the order in which they're specified. There would be no output, though, except perhaps when a bell or horn sounds to indicate acceptance or rejection of the input as a sentence.

Now to bring in the attributes, which are synthesized. Each nonterminal symbol in the grammar may have an attribute, which represents the output produced by the program represented by that symbol. The value of that attribute would be expressed as a string. But here's the idea I had: use this model of computing to compute the attribute strings themselves!

The idea is that a parser for each nonterminal symbol may return, as its output, a string. That string represents the value of that symbol's attribute. Such strings, along with literal strings, can then be concatenated into one string, which may itself be processed by a parser specified by a nonterminal symbol. The resulting string is then returned as the output.

If, when computing an attribute string, the specified parser rejects the concatenated input string, then the next alternative is tried instead. If there are no further alternatives, then the input string is rejected, even though it would have been produced by the (unattributed) context-free grammar. So, these attributed grammars aren't, in general, context-free grammars.

Here's an annotated example of such a grammar (with C/C++-style comments). In this case, it happens to be a grammar that, as a program, evaluates SKI combinatorial logic expressions (which means that this model of computing is Turing-complete, which is nice).

[Start of grammar.]

<expression> ::=
	<function>[f] <arg-list>[l] : <application> f l |
	<function>[f] : f ;

<arg-list> ::=
	<argument>[x] <arg-list>[l] : x l |
	<argument>[x] : x ;

/* Each subscript (appearing in square brackets) is a local, 'temporary' name for the attribute value of the subscripted nonterminal. The colon in each alternative marks the beginning of the attribute string definition for that alternative. In the second alternative of the first production rule, the resulting string is the same as the string returned, as output, by the <function> parser. In the first, a string is produced by concatenating the strings returned by <function> and <arg-list>, and then given to the <application> parser as input. The output returned by <application> is then returned as the output from the <expression> parser.

Oh, and I stuck semicolons at the ends of production rules, too. */

<argument> ::=
	<subexpression>[e] : '(' e ')' |
	<combinator>[f] : f ;

/* In <argument>, literal strings are included in the first alternative's attribute definition. Without being able to include literal strings, it would be impossible to have symbols in the output that aren't in the input. */

<subexpression> ::=
	'(' <expression>[e] ')' : e ;

/* <subexpression> removes the surrounding pair of parentheses, returning an evaluated expression as a result. Assuming the input is a <subexpression>, that is. */

<combinator> ::=
	'S' : 'S' |
	'K' : 'K' |
	'I' : 'I' ;

<function> ::=
	<subexpression>[e] : e |
	<combinator>[f] : f ;

/* Without the attributes, that would be the end of the grammar (other than for specifying what the start symbol is). */

<application> ::=
	<comb-app>[f] <arg-list>[l] : <expression> f l |
	<comb-app>[f] : <expression> f |
	<closure>[f] : f |
	<combinator>[f] : f ;

<comb-app> ::=
	<S-app>[f] : f |
	<K-app>[f] : f |
	<I-app>[f] : f ;

<closure> ::=
	<S-close>[f] : f |
	<K-close>[f] : f ;

<S-app> ::=
	'S' <argument>[f] <argument>[g] <argument>[x] :
		f x '(' g x ')' ;

<S-close> ::=
	'S' <argument>[f] <argument>[g] : 'S' f g |
	'S' <argument>[f] : 'S' f ;

<K-app> ::=
	'K' <argument>[x] <argument> : x ;

<K-close> ::=
	'K' <argument>[x] : 'K' x ;

<I-app> ::=
	'I' <argument>[x] : x ;

<expression>.

/* <expression> is the start symbol. */

[End of grammar.]

Anyway, does anyone recognise this (kind of) model of computing? Is it just term rewriting systems in thin disguise? (I'm only vaguely acquainted with rewrite systems.) Obviously, it's an example of attributed grammars with only synthesized attributes, so I already know what most of it is. It's really only the idea of recursively applying this model to synthesize those attributes that I suppose I'm asking about.

:-)

Simon

.

Relevant Pages

  • Re: need simple parsing ability
    ... > sometimes a short string followed by an integer, ... Here's a pyparsing solution. ... then to the parse actions attached to the ... different bits of the grammar. ...
    (comp.lang.python)
  • Re: design a Condition class
    ... of grammars in pyparsing. ... # parse input string ... The resulting grammar expressions are fairly readable. ... by another word group of alphabetic characters, ...
    (comp.lang.python)
  • Re: Would this qualify as a "recursive descent parser"?
    ... It seems to me that for any given grammar there's a basic difference ... between a recognizer and a parser for that grammar: ... Accordingly, merely counting parentheses wouldn't qualify as a parser, ... position within the string to be parsed. ...
    (comp.programming)
  • Re: An argument for the redundancy of truth
    ... settle where I suggested, it ought to settle - as the grammar of ... If you KNEW what a grammar was, THEN YOU WOULD KNOW this already, ... The purpose of a grammar is to define some structure on a string. ... AND EVERY GRAMMAR DETERMINES those truth-values. ...
    (sci.logic)
  • Re: Definition of Production
    ... rule to input string, ... `production' == `production rule'. ... Grammar productions are defined formally in Waite & Goos, ... of finite V strings, including the empty string). ...
    (comp.compilers)