Lambda the Ultimate

Yeah, I'm beginning to think I'm making this too complicated and should just define this as sugar.

If I were actually doing this in a textual language, though, I think this still leaves open the parsing question. Because I would like the de-sugaring stage to operate on the parse graph, not the lexeme sequence. So there is still the question of how (if there is a way) to get normal parsers to parse to non-tree graphs.

Then this desugaring could be viewed as the way of "tree-ifying" the graph.

But as I mentioned in another reply, in my actually application I already have the parse graph.

Because I would like the de-sugaring stage to operate on the parse graph, not the lexeme sequence.

To help clarify, let's define what we mean by "parsing", "parse graph" (I assume you mean something like abstract syntax tree) and "sugaring".

Normally when we say parse, we mean reading text and converting it into an abstract syntax tree. Once that is done, there is no more "parsing" to be done; the syntactic structure is laid bare.

By "syntactic sugar", we usually mean two syntactic forms whose semantics are identical. You may or may not want to give them the same abstract syntax representation, probably depending on how different the forms are.

If none of this makes sense, or we are not on the same page with the terminology, I would recommend a good compiler book, such as Appel's Tiger Book.

So there is still the question of how (if there is a way) to get normal parsers to parse to non-tree graphs.

This isn't that different from the normal situation. Even though called trees, and represented as trees, semantically ASTs are really arbitrary graphs by virtue of reference. By this I mean, use of identifiers that are defined elsewhere in the tree or that identify an ancestor node (recursion).

• Sorry, indeed I should have used "AST" instead of "parse graph."
• I agree that the sugared and de-sugared form of an expression are semantically identical, but I don't think that is enough to define "sugar." Perhaps you were not aiming for an all-inclusive definition but rather just highlighting this one aspect of sugar. I would attempt to define sugar as syntax
  • that is part of the language but not part of some smaller subset of the language identified as its "kernel"
  • that is transformable ("de-sugarable") to the kernel
  • whose semantics are defined indirectly, via this transformation, rather than directly, as the semantics for the syntax of the kernel are.
• The de-sugaring transformation could operate on the program text, but my preference would be for it to operate on the AST, in which case the sugared and de-sugared form of an expression would not have the same AST, but I admit that this is just based on my preference.
• I see what you mean about ASTs for normal languages implicitly having multiple edges go to the same identifier vertex by virtue of reference. But my ASTs have multiple explicit edges to the same identifier vertex, and I wonder whether a parser designed for normal languages can handle that. Maybe that difference between explicit and implicit edges is really not so significant.
• Clearly I need to educate myself on this stuff some more, so I've ordered the "Tiger Book" on your recommendation. Couldn't decide between the C, Java, and ML versions, but, although I find functional languages more interesting, I eventually chose the Java version since it was a lot cheaper ($5 used!) :-).

my preference would be for it to operate on the AST, in which case the sugared and de-sugared form of an expression would not have the same AST

As I said previously, I don't think this is a problem; you just add another case that has to be processed further down the compiler chain.

But my ASTs have multiple explicit edges to the same identifier vertex, and I wonder whether a parser designed for normal languages can handle that.

I'm a bit confused by your use of parser again here. As I mentioned before, once you get to AST, the parsing is done. If you mean just processing the AST to the next step of the compilation, then the normal technique of traversing the AST to transform it still works.

You probably have to do a little more work to make the traversal work correctly, since you have an explicit unrestricted graph, instead of a proper tree.

If you step back for a moment and rethink your AST representation a bit, you might be able to get the best of both worlds, by using symbolic references rather than "pointers" for identifiers.

The Tiger Book will probably do the trick for you in this regard.

This may clarify why it seemed I was referring to parsing once parsing was done:

Instead of

But my ASTs have multiple explicit edges to the same identifier vertex, and I wonder whether a parser designed for normal languages can handle that.

In other words I was imagining the data flow as

• program text
• -- lexer -->
• lexeme sequence
• -- parser -->
• ASG
• -- de-sugarer -->
• AST

But my ASGs have multiple explicit edges to the same identifier vertex, and I wonder whether a parser designed for normal languages can generate that.

Think about a simpler case. Take

a < b && b < c

Let's say that becomes an AST representation like:

(logical-and 
  (exp-list 
    [(comparison "<" 
      (id "a")
      (id "b"))
     (comparison "<" 
      (id "b")
      (id "c"))]))

I now have two references to (id "b"). This is normally done with a symbol table at this point.

But let's say instead I decide to convert my (id "b") reference to a pointer to the value of "b". I now have the very situation you refer to: multiple explicit references to the same node.

All of this falls just fine into the normal techniques for parsing and compilation.

bdenckla:
So there is still the question of how (if there is a way) to get normal parsers to parse to non-tree graphs.

At the syntactic level, "a < b < c" can still be represented as a tree.

class CompExpr extends Expr {
   Expr first;
   List<(CompOp, Expr)> rest;
}

term: a < b <= c > d

structure:
  CompExpr {
     first = "a"
     list = [
        (LT, "b"),
        (LE, "c"),
        (GT, "d")
     ]
  }

This structure is amenable to folding. To construct it, all you have to do is parse it like a list operator.

Expr -> ... | CompExpr | ...
CompOp -> "<" | ">" | "<=" | ...

CompExpr -> Expr CompOp Expr
   {
     $$ = new CompExpr();
     $$.first = $1;
     $$.rest = new List();
     $$.rest.add(($2, $3));
   }
CompExpr -> CompExpr CompOp Expr
   {
     $1.rest.add(($2, $3));
     $$ = $1;
   }

This is different from a binary operator in that you're explicitly handling contiguous operators. The semantics of your operator require this. For example, addition could be defined as a list operator. It doesn't need to be because "a+b+c" isn't different from "(a+b)+c" or "a+(b+c)", and so it is more elegantly dealt with as a binary operator. However, your operator doesn't have those properties and so you've got to parse multiple entries all in a row.

Converting the form after the parse (i.e. in AST form) could be problematic because you lose a little information when you go to AST form. If your initial parse simply treats "<" like a regular binary operator:

term 1: a < b < c
term 2: (a < b) < c

Both terms translate to the same AST (if "<" is a left-associative binary operator). However, I'd think that term 2 should be disallowed. You would be able to distinguish between the two terms if your AST contains information about parens, but I think this is more complicated than getting the parse right in the first place.

Thanks for your reply, Scott, this helps me reframe my problem in terms of "what class of grammars does my language belong to" and the answer looks like "not CFGs."

Without knowing it, I think I was already moving in this direction when, right after making my original post, I drew a parse "tree" for my a < b < c example and found that it was not a tree (b has two parents (both <'s)!). Are sentences in CFGs always representable as trees? I should review CFGs and hopefully find the answer in the process.

Also your reply helps me reframe my problem not just in terms of diverging from CFGs (which, as you point out, is common), but in terms of diverging from CFGs in a way other languages normally don't, and therefore having to push some functionality that is normally handling by parsing into external logic.

I should mention, in case it is relevant, that the context for this question, i.e. my application, is not implementing a language that allows a < b < c. Rather I just thought that was a good, simple example.

In fact my application is a graphical language. This has the advantage of "already being parsed," i.e. it is graphical in the sense of already being a graph.

I am trying to make a denotational semantics for this language and am a little stuck on not knowing how to proceed with this relativel novel (i.e. non-tree) grammar.

Side note: one interesting feature of this language is, not only can you use the same identifier in two different expressions, in fact you *must* do so if it appears in two different expressions, i.e. identifiers can only appear once. I think this is interesting from the perspective of eliminating a class of errors in traditional languages where the user intends to refer to the same identifier but chooses another. Usually the other identifier is undefined, or of the wrong type, so this will be caught (assuming a language that requires definition before use and is statically typed!) but sometimes the user is not so lucky and chooses a valid, but incorrect identifier.

this helps me reframe my problem in terms of "what class of grammars does my language belong to" and the answer looks like "not CFGs."

Unfortunately, unless I have horribly misunderstood your problem, Scott is way off base, and you don't need a more powerful grammar than CFG.

In fact, I can't think of a grammar that isn't LINEAR (i.e. recognizable with regular expressions) for the form a op b op c, whether it is fixed ternary or extensible to the right. (Unless you have REALLY weird rules for contants and identifiers)

To make this clear: let ID be the regular expression for identifiers/constants, then the grammar:

S -> ID A
A -> op ID A?

will do the trick. (Hopefully, this is obviously linear, if a bit of an abuse of grammar notation.)

If you give us a more concrete example of your actual problem, perhaps we can offer better advice.

[fixed small error]

Perhaps; a clarification is in order.

You are probably correct in that what the original poster wanted to do could be done in a CFG. I won't attempt to prove or disprove that.

My essential point is that what he wants to do might be more easily implemented as a standalone function, rather than as rules given to YACC or some other similar tool. If what the original poster wants is one simple case for one simple operator, than explicit rules in the grammar is the best way to go--if for no other reason than the fact that such tools will tell you if you introduce any ambiguities.

However, I got the impression that the original poster wants to be able to parse sequences of terms/operators in some arbitrary ways (perhaps even dynamically!). In which case, use of external (to the parser generator) logic is probably a better way to go. Doing so, of course, does allow you to escape the bounds of a linear grammar; whether or not you choose to take advantage is up to you.

At any rate, sorry for any confusion.

I agree that the grammar is can be described via regexp, e.g. what you gave, or

ID (op ID)*

a + b * c

a (+ b) (* c)

My concern is that "parsing via regexp" (if that is a meaningful concept) would parse
a + b * c
as
a (+ b) (* c)

My example assumed a single operator, so this is a different case.

I think once you work through the first few chapters of the Tiger Book, you will probably have enough food for thought to rethink and reformulate your language so that existing compiler technologies will do the trick.

In particular, Appel does a good job of showing how to break down the language features into the different steps of the compilation process. I think that will help here.

I will give you the benefit of the doubt and assume you meant your use of the word "abuse" to be more playful in tone than your text communicated.

I've found other responders to my post to be wonderfully more open minded about my question.

I admit that I have revealed hardly any of the details of the context of my question, i.e. my application. As such, others have witheld judgement on whether it is a "good idea" and instead answered my question with the implicit caveat, "Assuming this is really what you want to do, ..." Others have actually asked for more details of my application (which I admit I have yet to provide, partially because I fear they will be a distraction.)

But instead of witholding judgement and addressing the issues narrowly, or asking for more information, you launch into a discussion of the advisability of what I want to do, assuming, it seems, I am designing a general-purpose programming language, e.g. with Bool data types, ordered comparisons on those Bool data types, and a '*' operator with standard meaning.

Probably my examples like a < b < c and a + b * c misled you into this assumption, but I would have thought that with the frequent use of 'op' instead of <, +, and *, and the general abstract tone of the discussion, you might have assumed less about my application.

Now, moving away from meta-discussion...

Consider that within the mathematical domain, I believe the a < b < c is standard, not viewed as an abuse at all. How do you know I'm not writing a language designed to reflect the conventions of that particular user community? (I'm not, but that is beside the point.)

I agree that people get far too caught up with syntax, and I should try not to fail into that trap. CS education, with its emphasis on parsing in compiler design classes, reinforces this, which is why the only language-relevant class I ever took was just on semantics, not compiler design, although as you can see from my ignorance on certain issues, that decision was not without its impact! Probably I would have forgotten a lot of it even had I taken the class, though :-).

One of the questions I am trying to answer, though, is how do I present a denotational semantics in a language that does not have normal syntax. In other words I got involved in syntax because it was frustrating my attempt to make a semantics.

I'm beginning to think that traditionally, semantics are presented (albeit implicitly) as operating on trees, which represents an implicit assumption about the abstract syntax of the language.

Also, and not surprisingly, traditional parsers assume the abstract syntax is a tree, but although that topic is interesting (and that's mainly what we've been talking about so far on this thread), as I've mentioned it is not really "my problem" because in my application I do not need to parse, i.e. what the user gives me is already a graph.

So back to semantics, I need the "meaning functions" of my semantics to operate on non-tree types, and I'm not sure (a) how to do that (b) once I do that will it be a denotational semantics, i.e. have the well-established well-definedness that den. sem. on trees have and (c) even if it is still well-defined, will, people accept it as such, i.e. how do I convince them it is a "real" den. sem. not something like a den. sem. that I cooked up ad hoc.

The abuse arises because formally a < b < c has to be considered as a separate relation, where _<_<_ = {(a,b,c) | a < b and b < c}. A generalization can be defined inductively by <_n = {(a₁,..,a_n) | <_n-1(a₁,..,a_n-1) and a_n-1 < a_n} for integer n > 2 and <₂ = <. That _<_<_ and _<_ share '<' is the abuse.

I will give you the benefit of the doubt and assume you meant your use of the word "abuse" to be more playful in tone than your text communicated.

"Abuse of notation" is mathematical jargon. It means a notation whose semantics is understood by the reader yet is formally undefined or ambiguous.

But instead of witholding judgement and addressing the issues narrowly, or asking for more information, you launch into a discussion of the advisability of what I want to do

Yeah, so? I have strong opinions. Don't be so thin-skinned.

I believe the a < b < c is standard, not viewed as an abuse at all.

It is absolutely viewed as an abuse. It is a standard abuse.

I'm beginning to think that traditionally, semantics are presented (albeit implicitly) as operating on trees

Yes.

So back to semantics, I need the "meaning functions" of my semantics to operate on non-tree types

You need to assign semantics to graphs, then? The standard way is to a define it as a graph morphism.

A more general way is to generate the category of paths from the graph, and define the semantics as a functor to some other category. So you interpret a node as an object and a path as a morphism.

I need the "meaning functions" of my semantics to operate on non-tree types, and I'm not sure (a) how to do that (b) once I do that will it be a denotational semantics, i.e. have the well-established well-definedness that den. sem. on trees have and (c) even if it is still well-defined, will, people accept it as such, i.e. how do I convince them it is a "real" den. sem. not something like a den. sem. that I cooked up ad hoc.

I don't really understand what you are saying, but inasmuch as denotational semantics is compositional, if you are dealing with non-tree structures, a categorical semantics will give you the same advantages.

BTW, many denotational semantics in PLT are not based on trees (algebraic). For example, a lambda-term is not a tree, but a kind of graph, and that's why a denotational semantics has to thread an environment through.

• You have defined all of your entities extensionally (i.e. you assume a set and extract members from it). How do you build these sets?
• Your definition for f makes it sound like every f maps all unbound inputs to all unbound outputs. If this is not so, how do you select a relavent subset of inputs and outputs for a given f? How does f know its arity (the size of the tuples it consumes and returns)?
• I'm not clear how the assignments in C are different from the f-mappings in B
• If all that is going on here is that you start with a set of inputs and a set of outputs, and you end up with a set of correspondences between inputs and outputs, why not build a simpler system that does just that?

• These sets are built from the ASG; not sure how to indicate that.
• The f for a given block only maps that block's inports to that block's outports. The top-level f that is the meaning of the diagram maps the diagram's unbound outports to its unbound inports. Note the somewhat counterintuitive switch at this top level: inputs are outports and outputs are inports.
• The assignments that C gives rise to via the semantic (sub)function Sc are of the simple form identifier1 = identifier2. The assignments that B gives rise to via the semantic (sub)function Sb are of the form tuple1 = function tuple2. Does that help clarify?
• Not sure how to address your last question; hopefully the answers to the above 3 questions will help.

Here's a more complicated example diagram, which may help illustrate the "real" use of this language, which is to do a generalized form of function composition (i.e. hooking up blocks/functions f and g in arbitrary ways).

I don't have access to my code generator at the moment, but I'm pretty confident that the code it would generate for the new example would be something like

diagram (u1,u2) = (y1,y2,y3) where

(b1, b2) = f (a1, a2)
d = g c
a1 = u1
a2 = u2
y1 = b1
y2 = b2
y3 = d
c = b1

I think I begin to see the problem: the meaning of a block is either underspecified or overspecified.

If all that matters for the meaning of the graph is the path-terminating nodes, then you don't need any information about the blocks, just treat them as opaque nodes.

If you do care about the internals of the blocks, you need to add some information to them to make it possible to evaluate them consistently. For example, in one case the block sequence b1 b2 a1 a2 f evaluates to (b1, b2) = f (a1, a2), but in another the sequence d g c evaluates to d = g c.

There simply isn't enough info in your definition or the diagrams to predict this, so you would have to add some knowledge of block evaluation rules to your system, for example as valency info in the functions, or by some explicit block building grammar.

Perhaps a source of this confusion is the idea that the user can just plop nodes into a block. They can't. They use blocks whole. Is this the notion of opacity you were referring to?

Spatial order (e.g. left-to-right or up-to-down) is irrelevant in this language. So there is no notion of a "block sequence" like "b1 b2 a1 a2 f" in which order matters. There is just a block tuple of (f, {a1, a2}, {b1, b2}).

In the diagrams and the semantics, I claim that there is enough info to know how to evaluate a block, except for the problem of establishing an order in the set-to-tuple conversion (I mention this problem in the semantics with respect to leaving the T functions undefined).

But leaving that problem aside, in the diagram,

• any node with an incoming arrow is known to be an inport
• any node with an outgoing arrow is known to be an outport
• and any node with neither is known to be a function.
• a node with both is disallowed by the grammar (which I admit I have not really specified). In the semantics this could be disallowed by saying that a diagram's connections, C, (its set of inport/outport pairs) are over disjoint sets, i.e. an inport is never an outport and vice versa.

I claim that there is enough info to know how to evaluate a block, except for the problem of establishing an order in the set-to-tuple conversion

That's kind of like claiming you have car that runs well, except it has no engine. ;-)

You NEED to provide some structure to block to be able to evaluate them, whether by function valencies, ordering or labelling of elements, or some other mechanism.

Once you solve this problem, there is nothing here that looks unusual compared to any compostional language.

You NEED to provide some structure to block to be able to evaluate them, whether by function valencies, ordering or labelling of elements, or some other mechanism.

The elements of the inport and outport sets are already labelled, e.g. "a1", "a2", "b1", "b2".

So perhaps this is too important to leave implicit, but let's assume that each block has info about how, based on these symbols, it should order its inports and outports into tuples.

Or instead of thinking of blocks as containing functions, can we just say that they contain expressions with free symbols corresponding to their inport symbols and assignments to symbols corresponding to their outport symbols? That way we get away from the whole ordering thing. Then, in the end if the users wants to turn the diagram into a function, the user must supply the ordering.

Where can I find out more about the compositional languages to which you refer?

Where can I find out more about the compositional languages

I'm using compostional as a plain adjective here; I'm not referring to some exotic class of languages.

I just mean "languages where larger units are understood in terms of smaller units that make them up".

This covers most interesting languages and grammars.

A more general way is to generate the category of paths from the graph, and define the semantics as a functor to some other category. So you interpret a node as an object and a path as a morphism.

There seems to be a vacuum between multiple introductions to category theory and the papers that really use it. Any suggestions on teaching myself advanced category theory in 12 easy steps? :-)

There seems to be a vacuum between multiple introductions to category theory and the papers that really use it.

I've been studying CT (in my spare time, on and off) for the better part of a decade, and I still those moments of frustration when I get flummoxed by a particular application I see in a paper.

So I know exactly what you mean. ;-)

One observation that I have is that one of the great powers of CT is that it makes it easy to express very general, multi-level mathematical relationships. The catch is that it can be very difficult to understand how this general relationship applies in a particular case.

Generally, to really get these particular cases, you need a fair background in some other, more specific algebraic field. (e.g. group theory, algebraic topology, set theory). One part of my strategy to understand CT has involved learning about these various fields and then coming back to papers and books to see what more I understand.

(Most of the fields are interesting in their own right, too)

The advice I would give someone who had limited time for mathematical exploration would be to choose some field that they know a lot about (or want to) and learn how to represent it thoroughly in CT terms.

This helps to give intuitions about the meaning and utility of various CT constructs "under fire".

An obvious candidate for most people with some mathematical background (and a pretty good start for CS apps) is set theory.

Lawvere and Rosebrugh gives a fairly thorough account of set theory in CT. Its probably a good start for someone with a set theory background.

Lawvere and Schanuel is similar but for people with more modest mathematical backgrounds. (Still good if you want a more basic level of intuition.)

Another strategy I employ is to collect CT textbooks. ;-) Reading different accounts and presentations of the same material is useful both as review and as fresh perspectives on the ideas. You never know what simple distinction is going to "flip the light switch" for you.

Actually, this advice holds for PLT or any other mathematical field as well.

If you want a text that is intro but will take you up into some pretty hairy CS-related areas, I would recommend Barr and Wells (special order only)

I will consider one of the former books. I am currently entangled in Chapter 1 of Presheaf Models for Concurrency (sorry about OT).

Who said that a<b<c must be equivalent to either (a<b)<c or a<(b<c)? In Python it's neither, it's 'a<b and b<c', and it works fine. It doesn't depend on types, it's just a parsing issue. What is the problem?

Can someone (maybe Qrczak?) fixed the previous post?

Needs to have < changed to &lt;.

Fixed, thanks.

Who said that a<b<c must be equivalent to either (a<b)<c or a<(b<c)?

The standard rules for infix operator symbols.

In Python it's neither, it's 'a<b and b<c', and it works fine.

I presume they special-cased <. You're right that a particular case like this can be made unambiguous in a particular language. I was thinking about mathematics, where the standard rules are assumed to hold without exception. (Knowing you, Marcin, you will quibble that a < b < c is clearly an exception, so the standard rules are not assumed to hold without exception, but I assert that both hold simultaneously, thus there is a contradiction, and hence ambiguity.)

Anyway, the poster was asking about a general mechanism for doing this for infix operators, presumably only relational (and similar) ones, since otherwise you don't want to eliminate the ability to parenthesize subterms. And to identify a relational operator you need to look at the type.

P.S. If you don't think special cases are confusing, please explain to us all why you tripped over the special-casing of < in HTML.

The standard, unspoken rule in mathematics is that a<b<c ≡ a<b and b<c. It's not ambiguous. Both do not hold simultaneously--a<b<c does not mean (a<b)<c. You seem to be insisting a<b<c must be equivalent to either (a<b)<c or a<(b<c) in PLs because of "standard rules" even though the supposed standard obviously doesn't hold in mathematics. I don't see why you insist on calling it "abuse of notation" when all high-school educated people understand the notation and so do a few PLs. IMO, more PLs should accept it.

Sorry, but it took me a really long to time to think that I understood that. ;-)

I'm not sure that there isn't a simpler language in there trying to get out, but here are some thoughts:

you have to use b = f a as a block
So why not bracket that expression or give "=" a higher operator precedence.

the abstract and concrete syntaxes are the same thing

You want Lisp or Scheme then. ;-)

variables only appear once in the abstract syntax graph, so a single vertex must be able to be the argument to more than one operator (have multiple incoming edges).

I'm starting to wonder if what you really want is unification.

CTM has a good explanation of this feature.

Sorry, I accidentally posted my reply as a fresh thread, so see above.

A block diagram, concrete syntax.

The same diagram, abstract syntax graph.

I need to be able to apply the 'A' operator to b2 specifically, not the whole output of the block, which is (b1, b2).

Now I know I'm confused. ;-)

You may have found Frank, well, frank, but his advice is good. Drop all thought of this as a syntax problem, and work out exactly what your semantics are.

Find a semantic description for one of the class of languages you are working on, if you need help getting started.

I think that hoping to find out what the semantics is by working through the syntax is not going to work. You'd be better to define the semantics and then figure out a good syntax (or graph representation, if you prefer) after the fact.

I claim I already know what the semantics of my language are. I just need to put them into as-standard-as-possible form. I think the denotational semantics would be most appropriate, since I already know the language has a fairly natural mapping to Haskell, i.e. my "compiler" (Haskell generator) really doesn't have to do much.

But I am having some difficulty figuring out what the "meaning functions" would look like, because (at least this is my claim) the standard form in which semantics are presented makes some assumptions about the syntax being defined. In particular, it assumes single reference to identifiers/a tree-shaped syntax graph.

I guess I'm repeating myself. Hopefully the links I posted to the diagrams will help me express myself.

I claim I already know what the semantics of my language are.

Well, do share. ;-) I wasn't able to say for sure what the semantics were based on the diagrams.

Using Haskell as my language to define meaning, the meaning of such a diagram is a function

diagram [tuple of unbound outports] = [tuple of unbound inports] where

[dump all assignments in the ASG here]

For example, the meaning of this diagram (which has this ASG) is

diagram (u1,u2) = (y1,y2) where

(b1, b2) = f (a1, a2)
a1 = u1
a2 = u2
y1 = b1
y2 = b2

the meaning of such a diagram

OK. Let's see if I get this.

You have a block of registers (we'll call them) that evaluate from right to left.

The program has three steps:
1) load values from external references into the input registers
2) evaluate the block with those values. The result ends up in the output registers of the block
3) store the results to external references.

That sounds likes assembly language. ;-)

I don't really see a problem for normal methods here. If your block of registers is fixed, then your "f" procedure simply needs to know which registers to get its parameters from, and which to store its result in.

If the problem is that you don't know when your values will be bound, you need something like dataflow variables with unification. See CTM mentioned earlier.

If the problem is that you don't know when your values will be bound, you need something like dataflow variables with unification. See CTM mentioned earlier.

Is not knowing when your values will be bound the same as needing laziness?

If so, that is the case in my language, since blocks can be hooked up with feedback.

I have duly ordered a copy of CTM, although the price was nothing near the $5 bargain price I found for the "Tiger" book.

BTW, I think I put too much semantics into my ASG, here's a new version of the ASG for my standard diagram with this concrete syntax (I guess I do have a somewhat separate concrete and abstract syntax after all).

Is not knowing when your values will be bound the same as needing laziness?

For what I mean, no. To given an example: an uninitialized pointer is unbound. An initialized pointer is bound. To dereference an initialized pointer is to evaluate it. (More or less.)

With laziness, typically your variable is bound (it refers to a valid expression), but you don't know when or if it will be evaluated.

If you won't know until later what expression a variable will be bound to, you probably want dataflow variables.

I have duly ordered a copy of CTM, although the price was nothing near the $5 bargain price I found for the "Tiger" book.

A worthwhile addition to any PL enthusiast's library. I was a skeptic about the whole multiparadigm thing way back when, but this book is so well done it changed my mind.

Though there were relatively few brand new things I learned from reading it, those few things were of high value, and the presentation of material I was already familiar with was fresh enough to give me a new perspective on it.