6
$\begingroup$

This is a difficult question to get across because I don't think there is an established term for what I'm asking about. In the title I've called it "ways" of executing statements, but I mean something specific.

Background

Imperative languages typically have statements which "do something when they are executed". If the language's semantics are defined operationally then a specification might look something like this:

  • An if statement has an expression and a sub-statement. When an if statement is executed, the expression is evaluated, and if its result is truthy then the sub-statement is executed; otherwise nothing happens.
  • A while statement has an expression and a sub-statement. When a while statement is executed, the expression is evaluated, and if its result is truthy then the sub-statement is executed and then the while statement is executed again; otherwise, nothing happens.
  • A return statement has an expression. When a return statement is executed, the expression is evaluated, and the statement completes abruptly by causing the enclosing function to return with the expression's result.
  • ...

A full specification for a typical language like this must list, for each kind of statement, what happens "when that statement is executed".

My language MJr is not quite like that. There are two different ways of executing a statement ─ they can be "executed normally", or they can be "reset". In particular, the specification defines not just "when an X statement is executed" but also "when an X statement is reset". This is defined for every statement in the language; I'll try to simplify and omit irrelevant details:

  • A convchain statement has [...] and a boolean flag at runtime. When a convchain statement is executed normally, if the flag is false then the flag is set to true and [...]; otherwise [...]. When a convchain statement is reset, the flag is set to false.
  • A @limit statement has an expression and a sub-statement, and a counter at runtime. When a @limit statement is executed normally, if the counter is greater than zero then the sub-statement is executed normally, and the counter is decremented if the sub-statement succeeds; otherwise [...]. When a @limit statement is reset, the expression is evaluated and its result is assigned to the counter, and the sub-statement is reset.
  • A sequence statement has a list of sub-statements. When a sequence statement is executed normally, each sub-statement is reset, then each sub-statement in turn is repeatedly executed normally until it does not succeed. When a sequence statement is reset, nothing happens.
  • A markov statement has a list of sub-statements. When a markov statement is executed normally, each sub-statement is reset, then repeatedly the sub-statements are executed normally, in turn starting from the first sub-statement, until one succeeds; this ends when no sub-statement succeeds. When a markov statement is reset, nothing happens.
  • ...

The exact details don't matter for this question; what matters is that there are two verbs, "execute normally" and "reset", and the semantics of the language define both "when S is executed normally" and "when S is reset", for each statement S. Both are things done at runtime and are part of the program's observable behaviour.

The timing of when each statement is "executed normally" or "reset" is determined by control-flow statements like sequence and markov, which each invoke both behaviours of their sub-statements when they are executed normally.

This is quite different from typical imperative languages, which only define one verb for executing a statement. A more concrete way of thinking about this might be that an interpreter for the language would have an execute() method and a reset() method for each statement node in the AST, where a typical language would only have one execute() method on each statement node. (In the interpreter for MarkovJunior, which MJr is based on, these methods are named Go() and Reset().) However, this question is not specifically about interpreters.

The question

What other languages (if any) have operational semantics with multiple "verbs" for executing statements, such that the language defines each verb for each kind of statement? I am interested in languages like this whether or not it has actually been spelled out in a formal specification.

$\endgroup$
11
  • 2
    $\begingroup$ I’m a little bit confused by what this second “reset” operation does and how/when it is invoked. As-written, I think it is sort of difficult to pin down what does/does not meet your criteria. For example, some languages use abstract interpretation to implement some sort of code analysis, and in some sense, this does interpret the same code two different ways. However, I suspect it would not meet your criteria. Could you edit the question to clarify what constitutes “different ways” of execution? $\endgroup$
    – Alexis King
    Commented Jul 31, 2023 at 21:13
  • $\begingroup$ @AlexisKing Abstract interpretation would be another way of implementing the same semantics for the statements, as opposed to the statements having different semantics depending on the way they are executed. That is, abstract interpretation is an implementation detail, not a part of the language's semantics. $\endgroup$
    – kaya3
    Commented Jul 31, 2023 at 22:11
  • $\begingroup$ Regarding "how/when it is invoked", I had hoped that the sentence "e.g. for some kinds of statement, execute() could call reset() on some child statements" got the point across without getting bogged down by details about MJr specifically, but I will edit to include a concrete example of that. I'm worried it will make the question too long, though. $\endgroup$
    – kaya3
    Commented Jul 31, 2023 at 22:11
  • 1
    $\begingroup$ Perhaps a more useful comparison would be Esterel. Reduction in Esterel relies on performing a kind of dataflow analysis at runtime! See this paper for the details, specifically the Can metafunction. Does this count as interpreting the same statements in different ways? $\endgroup$
    – Alexis King
    Commented Jul 31, 2023 at 22:15
  • 3
    $\begingroup$ Your edit helps a little bit, but all your examples are still about an implementation of your programming language, which seems less helpful than discussing the language itself. After all, one could certainly write an implementation of an interpreter with two different functions for interpreting something. Can you provide examples in terms of the semantics itself rather than a particular interpreter implementation? (This should also, ideally, avoid restricting the question to interpreters rather than both interpreters and compilers.) $\endgroup$
    – Alexis King
    Commented Jul 31, 2023 at 22:45

5 Answers 5

10
$\begingroup$

In continuation-based operational semantics we sometimes keep around two continuations, called the success and failure continuation. One is activated upon normal completion and the other when "failure" occurs (whatever that means in a specific context).

A good reference is John Reynold's Theories of programming languages. Specifically, Section 5.8. discusses how having two continuations accommodates failures. (And I can highly recommend the book to anyone who dabbles in PL design and implementation.)

This idea can naturally be generalized: keep around multiple continuations and activate whichever is appropriate at a given moment.

$\endgroup$
4
  • $\begingroup$ If I understand correctly, this is more like there being two kinds of results from executing a statement (e.g. the distinction between "completing normally" and "completing abruptly" in Java), rather than two different ways of executing the statement. $\endgroup$
    – kaya3
    Commented Aug 1, 2023 at 23:19
  • $\begingroup$ Not necessarily. Which continuation fires may depend on circumstances, such as those described by the OP. In any case, the OP is looking for similar ideas and techniques, so I thought it worthwhile mentioning having several continuations. $\endgroup$ Commented Aug 1, 2023 at 23:24
  • $\begingroup$ Ah, you are the OP :-) $\endgroup$ Commented Aug 1, 2023 at 23:26
  • $\begingroup$ :D I appreciate your answer, just wanted to make sure I understand it correctly - I think it's a related idea, but not the exact same thing. $\endgroup$
    – kaya3
    Commented Aug 1, 2023 at 23:27
6
$\begingroup$

Context-oriented programming

I think that Context-oriented programming is a possible way to name what you describe.

Depending on the environment surrounding the code being executed, it can act differently. This is something that already exist in a lot of programs. For example in OpenGL you can change the current transformation matrix and the same code that draws from (0,0) to (0,1) will render as a vertical or horizontal line.

The linked article is a way to build applications where this is done in a systematic way. The difference is that you are writing a programming language where the primitives (or maybe user-defined functions?) are context-dependent.

Signal/Lustre/Esterel

In Lustre and similar programming languages, you can define a flow x as follows:

x = 0 -> (((pre x) + 1) mod 4)

x is defined as the flow that is initially 0, then the previous (pre) value of x, plus one, modulo 4. At runtime it represents the following infinite sequence of values:

0 1 2 3 0 1 2 3 0 1 2 3 ...

Typically the code is compiled as two functions: init and step. The first is the projection of all expressions on the left-hand side of arrows, the step is the general case, the right-hand side. So in a way, the arrow is executed differently depending on the context. There was an extension where the arrow accepted a list of signals that can reset it at runtime, something like:

x ->*(R) Y

Depending on the value taken by R at a given execution cycle, the arrow evaluates to either one of its branches.

$\endgroup$
4
$\begingroup$

This seems a bit broad. I'm not sure which are the ones you wanted.

Malbolge

(Not serious.)

The closest thing I could think of is Malbolge. Instructions are changed to another instruction using a predefined mapping table after execution, to deliberately make it difficult to program in this language, forming some internal state. The instruction could also be modified using its address, like how you would modify the internal state.

Static variables

In many languages, static variables in functions are initialized on the first time the definition is reached, forming an internal state about whether it was initialized. I didn't test which languages could let you revert them to the uninitialized state, though.

QBasic DATA

In QBasic and perhaps some other Basic dialects, DATA is not a statement to be executed along with other statements, but a marker of data that could be READ anywhere into variables, using a data pointer independent of the instruction pointer. You could use RESTORE to move the data pointer, effectively making already read data like unread.

sizeof

In C and C++, the parameter of sizeof is not evaluated, or we could say it's a different way evaluating the parameter.

This actually reflected a problem, that for a multi-pass compiler or interpreter, the different passes could easily become different methods in the implementation, but usually without observable effects to the user of the language. In JavaScript, variable declarations would create a variable in the local scope on the first pass, and initialize the variable on the second pass, so the variable is already created but with the value undefined before reaching the declaration, making it an example with observable effects.

Valence in APL and Jelly

In APL and many variants, functions (or atoms in Jelly) could be monadic or dyadic (unary or binary in common terms). Using a user defined function as a monadic or dyadic function, may cause some functions called in the definition to also change to monadic or dyadic. I don't know how the interpreter is implemented, but quite a lot of the documentation would need to have a monadic and a dyadic part under each entry. (Though the official documentation of Dyalog APL split them into different entries instead.) The same applies to variants like J.

In Jelly, it instead changes how the definition would be parsed. For example, +׶5Ç where is called as a monadic is 50 = (5 + 5) × 5, and +׶5ç where is called as a dyadic is 30 = 5 + (5 × 5). Unfortunately, it seems to decide the arity by the first call, and doesn't make both versions available in the same program.

await

The parameter to await is somewhat like a statement, and is usually actually a complex object that you could do other things on it.

Is it actually something special?

In your example, if you add an appropriate constructor, the construction in the same language as your interpreter already works like a statement in the interpreted language. Is there something it cannot be done this way?

Maxima

Based on the comments from OP, I think the closest thing is in Maxima, where 1/2; returns 1/2 with some fancy format, and 1/2,numer; returns 0.5. ,numer at the end of a statement is applied to all the parameters before evaluation, instead of the result, if 1/2 was a more complicated expression.

I'm not sure this qualifies, as it is only defined as a special parameter to a special function ev in the documentation. Because, if you have the feature to do things differently, why make it a special case in the interpreter and not make it more general?

Inverse

In J, many operators could be repeated by a negative number of times like (operator ^: _1), where _1 means -1.

Again, I don't think this too special. It's not too different from how some high precision libraries make a**b % c a special case with different computation routines. It's definable in some languages without a language feature.

$\endgroup$
4
  • $\begingroup$ To narrow it down: (1) I don't know much about Malbolge; it sounds potentially relevant, but replacing statements at runtime still leaves each actual statement as having only one "way" to execute. (2) These are declarations, not statements, and simply having state doesn't mean there is more than "way" to execute it; in every execution, it's like if(!isInitialised) { intiialise(); } return value;. (3) Again, sounds like just state, not multiple "ways" to execute the same statement. (4) Interesting example; I suppose "do nothing" is in a trivial sense a different way to execute it. $\endgroup$
    – kaya3
    Commented Jul 31, 2023 at 21:48
  • $\begingroup$ (5) I am not sure from reading your explanation, but if an interpreter would naturally give every statement executeMonadic() and executeDyadic() methods with their own definitions, then this would be an example. (6) I don't see how this is related. (7) I wouldn't consider the constructor of an AST node to be part of the execution of the program, since the constructor is called during parsing, not execution. If the constructor did have some observable effect for some or all statements, which was part of the language's semantics, that would be very strange but it would count. $\endgroup$
    – kaya3
    Commented Jul 31, 2023 at 21:54
  • $\begingroup$ @kaya3-supportthestrike So, I think, you specifically want each statement to have multiple methods with observable effect in execution in the interpreter's language? I think most modern languages aims to be extensible, so that if a few methods are automatically supported, someone may want to support more user-defined methods, making it better to just implement one method with a parameter choosing between the ways. Are such cases automatically disqualified? Are you looking for the edge cases that are specifically not extensible? $\endgroup$
    – user23013
    Commented Jul 31, 2023 at 23:12
  • $\begingroup$ @kaya3-supportthestrike If sizeof is a borderline example, I think many people would want to make the short circuit behavior of logical operators extensible in a new language, making users able to define a sizeof-like thing by themselves. Does that make it a better example because it supports more different behaviors, or worse example because the different ways are unified into one way? $\endgroup$
    – user23013
    Commented Jul 31, 2023 at 23:13
2
$\begingroup$
  1. Every language. The expression a + b maps to a different machine instruction depending on whether a and b are unsigned integers, signed integers, reals, complex numbers...

  2. OOP. The same instruction animal -> make_sound() may print meow is the animal is of class Cat, but moo if it is of class Cow.

  3. For a less trivial application, consider automatic differentiation: the same function containing a sequence of arithmetic operations and control flow, for instance (pseudocode)

function f(x)
  y = x;
  while x < 1
     y = y*x
  end
  return y
end

can be "reinterpreted", using different techniques and different languages, to return the derivative dy/dx as well as y.

$\endgroup$
6
  • $\begingroup$ Your point 1. is not what this question is about at all, because each occurrence of a + b has only one meaning (either that meaning is determined at compile-time in a statically typed language, or the meaning includes "check the types, if they are ints then do int arithmetic, ..." at runtime in a dynamic language). But point 2 is a very good one. I think this answer would be improved by removing point 1. $\endgroup$
    – kaya3
    Commented Aug 17, 2023 at 16:23
  • $\begingroup$ Likewise your point about OOP, the expression animal -> make_sound() has only one meaning in the language's semantics, which is to dispatch the method based on the object's class at runtime. $\endgroup$
    – kaya3
    Commented Aug 17, 2023 at 16:24
  • $\begingroup$ @kaya3 I have added another point between 1 and 2. I still think 1 counts. The same line of code a+b could map to different operations even in the same program when executed multiple times. $\endgroup$ Commented Aug 17, 2023 at 16:25
  • $\begingroup$ No, because a dynamically dispatched + operator in a dynamic language still only has one meaning: it is dynamically dispatched based on the values' types at runtime. $\endgroup$
    – kaya3
    Commented Aug 17, 2023 at 16:25
  • $\begingroup$ Then I am failing to see what in your language is fundamentally different from this pattern. Could you make an example of a feature that cannot be implemented by changing types adequately? $\endgroup$ Commented Aug 17, 2023 at 16:27
-1
$\begingroup$

This can be done in any interpreted language that allows you to modify the parser at runtime.

I've seen someone present something like this in a Youtube video in Perl years ago, but failed to find the video.

$\endgroup$
2
  • $\begingroup$ Do you mean Perl is such a language (that allows you to modify the parser at runtime), or that the video presented such a language where the interpreter was implemented in Perl? With so few details it's hard to make sense of your answer. $\endgroup$
    – kaya3
    Commented Jul 31, 2023 at 19:19
  • $\begingroup$ The video presented a library in an early version of Perl 6 that changed all sorts of execution semantics. I haven't checked if such modifications can still be done in current versions of Perl. $\endgroup$
    – feldentm
    Commented Jul 31, 2023 at 19:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .