Lambda the Ultimate

Sorry, but I have read "LtU is blog not forum!" after I have made the post. This work is my own research (though based on several years of learning other programming languages and studying compilers design theory) and is intended to be discussed rather than to inform. May be this topic should not be on LtU but my friends adviced this resource, and there are already plenty of comments.

In the COBOL days of computing science, one of the holy grails people were looking for was exactly what you propose: Programming languages which mimic natural languages by employing an extensible syntax.

I don't know a lot of these approaches, but there must be a ton of research from the sixties/seventies on it. Other than that, I can tell you you'll need an extensible parser and probably need to limit the production rules to some form. Plus, as stated by others, you'll need some disambiguation rules.

Lastly, of course it's a stupid idea; I therefore recommend you follow it through. Stupid ideas are always nice. ;-)

The bad part of it, as you can gather from history, it has been tried before and didn't work out -wasn't accepted as viable- then. I see no reason why your compiler would generate more than a little interest at best. But then "Who Cares?"

You are absolutely right, this is yet another attempt to find the Holy Grails of programming languages design. But failure of previous attempts does not mean that my attempt will fail too, does it?

I have been studying history of programming languages for some time and have come to conclusion that all attempts to create similar language suffered from following flaws:

1) Overcomplexity. Designers of the languages introduce very flexible means of syntax customization but interface to these means is either hard to learn or unusable at all. They design the syntax customization facilities bottom-up - first extension points and low-level functions to parser and then language constructs to these extensions - but it is needed to build them top-down - first language constructs (simple and convenient) and then parser extensions implementing them. First language as such should be thought through, and rich theory and smart parser generation tools will help to implement the idea.

Also nobody used the most obvious idea to borrow notation from other areas of activity (for example, in maths we write "a+b", using "a" and "b" as placeholders for actual values), or even from natural language itself: we get used to write in documents: "`Class <class name> inherits <other class name>` means..." - so why no to write the same way in programs?

2) Poor positioning in the market. Usually designers of languages with customizable syntax position their products as proof of concept only ("wow, these things also can be done with a computer!") and never as new industrial tools. At least I had such impression. And of course they get what they want.

Also the designers don't promote their languages in the market at all; they build them as for new, unoccupied niche of applications. A programming language is not only syntax and semantics but also its infrastructure - libraries, community, corporations support etc. And the language is hardly to be preferred by programmers if it has poor infrastructure, even if it is excellently designed.

I'm positioning my language as - no more, no less - new industry standard programming language, as replacement for C++, Java, C# etc. Yes, it is very ambitious goal (may be too ambitious) but I have a trick in reserve: I'm not going to develop my language's infrastructure from scratch and compete with industry-adopted standards. I'll just borrow them. I'm going to make C++ a first target for my compiler and use Qt as a part of standard library. Or at least MSIL and .NET.

And, who knows, may be my attempt would be accepted as viable. ^_^

Extensible syntax is nice, but it's still just syntax. Presumably the other details are just or more important.

Here are a few of issues to think about:

- How do you allow partial application? e.g. (+ 1) in Haskell

- How do you treat a syntactic form as a function? This is really just a special case of partial application with zero parameters, but for example, how do you write 'map points (_x)'? A problem with completely unstructured syntax is that it lacks structure. You'll probably want to introduce a few special forms to handle this kind of manipulation.

- Have you thought about handling deeper forms of customizable syntax, such as constructs with binders? How would you introduce a 'lambda' construct, for example?

I have been thinking of this language for a while. In fact I have published it here when the design has become seeming consistent to me. There are much issues I have thought through but I just don't know how to state them well.

As for issues mentioned by you:

- Functions in my language are first-class objects. And the function declaration without a body is the reference to the function. Yes, the resultant code may be very long so I introduced function aliases:

`time between {t0} and {t1}` (1) (dt)
...

or, in XML-like instance of the language:

<func>
  <syntax>time between <arg>t0</arg> and <arg>t1</arg></syntax>
  <alias>(1)</alias>
  <alias>(dt)</alias>
  ...

They are just syntactic sugar for:

(1) := `time between {t0} and {t1}`
(dt) := `time between {t0} and {t1}`

- I think partial application decreases readability. Also it can be implemented via mentioned mechanisms. So I didn't introduce special syntax for currying. May be it would be good to make all functions automatically curried but, again, I don't think it would help maintainability of programs.

- All functions you declare are actually closures - inside function's body everything is accessible what is outside of it.

...And you have caught me on lambdas. It seemed to me that anonymous functions (for example, functions with special-form declarations like `anonymous({x}, {y}, {z})`) with macros and regexps are enough but with them constructs like (x, y) => x + y are unimplementable.

Fundamental problem is that I relied on fact that body of a function is always sharply defined (with indentation in "simple" form I usually write in, with <body> ... </body> in XML form) but for lambdas it is not always true. Operator `({args}) => {func}` with accurately adjusted prioriry could help in this case but the problem is that in func the parser does not know about args.

Thanks, I go out to spend more time on research.

The problem is much more fundamental. When I designed the language I have cheated: constructs are allowed which may have expressions which are not known for parser yet. For example, there is a built-in function (in pseudo-code):

`{f1}\n\n{f2}\n\n{f3}\n\n...`
  where f1, f2, f3 are functions
  :
  ...

It executes f1, f2, f3, ... in unspecified order. But in following code:

print(x + y)  -- (1)

x := 10  -- (2)

y := 20  -- (3)

The order must be (2)-(3) then (1) because in (1) the parser does not know yet about x and y.

I thought that a cheat when parser may boldly skip parts of source code until it encounters "\n\n" and defer parsing of separate expressions until all their subexpressions will be known, that this cheat would be enough. But lambdas have caught me because there is no such cheat which is also general enough.

Agreed with that and have already taken those into account.

In the COBOL days of computing science ...

I like your snarky comments.

SQL with its 300+X keywords is among the biggest languages in use and another example of the mentioned design principles. I guess that's mostly the effect of not being able to write functions in SQL directly, so every possibility had to be foreseen, specified and standardized in advance.

Isn't this precisely how the world, the plants, the animals and finally us humans have been planned by the great designer according to creation scientists relying on the undeniable truths of the bible? There we have our scientific reference.

The Maude language has an extensible mixfix parser which handles a lot of the meta-syntactic notational ideas described here. It also includes annotations for operators to indicate idempotency, associativity, reflexivity, and the like, both for the parsing purpose and to guide the evaluation strategy for the operator.

The issue is that the obvious semantics has lousy algebraic properties, properties that I think Maude's parser would need to be able to find a decent evaluation strategy.

Clearly there's some distance between contexts. Maybe awareness of this achievement there will be helpful to him.

Thanks for the reference. At least I have found some interesting ideas. For example, I was afraid that absolute priorities are not suitable for large and complex programs, but if to use them properly they can become as usable as relative priorities. I should think of this.

I was thinking about ambiguities like "`min < x < max` vs. `((min < x) < max)`" for some time and come to conclusion that there is no way to distinguish such ambiguities without knowledge of types. So parsing techniques considering types should be used.

But I'm rather unfamiliar with such techniques so I do it with enumerative technique: parse input expressions with GLR-like parser and reject those parsings for which type checking fails.

The approach you describe seems to have a serious flaw: when the parse that the user "meant" to write has a type error, you will reject it. This could either result in a different parse being accepted (and accidentally changing the meaning of the program), or more likely cause parsing to fail.

How can you possibly give the user good messages for type errors if you reject any parse that had type errors?

Yes, error reporting is the weakest point of my design. But as far as I know, this problem (adequate error reporting) isn't completely solved for now, is it?

So the only way to discover optimal error reporting strategy is to try writing programs in my language. My intuition tells me that very good strategy will be to use that parse in which first error will be as far along the program as possible.

As regards the accidental changing the meaning of the program, yes, it is a problem, and there is no any adequate way to solve it. But, again, let's turn to practice! Just imagine such a program where one typo may change meaning of the whole program - can the programmer himself understand such a program better than a machine? And how much do programmers tend to write such ambiguous programs? How often do people write texts like "shi shi shi shi shi" (traditional chinese) or "kosil kosoy kosoy kosoy" (russian)? Quite the contrary, the everyone tends to speak unambiguously that everyone else could understand.

But, OK, the problem still may arise. But there is a strong type system in my language as a second line of defence. And it is very unlikely that the program with accidentally changed meaning would pass type-check. At least programmers tend to use type systems to defend theirselves from bugs, including mistakes like one under discussion.

As for operators precedence, you are right, I'm anchoring the priority of operator off of another one (the user can write in function declaration: "priority is higher than of `xxx`", "priority is lower than of `yyy`", "priority is the highest", "priority is the lowest"). In fact this is very poor choice which leads to much ambiguities and design problems... for developer of compiler. For programmers writing large and complex programs in my language this scheme will be at least more flexible than, for example, Haskell's "absolute priorities" scheme.

In other words, in theory "anchoring of priorities" scheme leads to very ambiguous systems of operators' precedence but in practice the programmer uses a small subset of operators in any program expression, and for this small subset operators' priorities may be defined precisely enough.

Also priority is not required to be defined for absolutely all functions. It must be defined only for functions which require it (such functions like "{x} + {y}", "{x} ? {y} : {z}" etc.).

And I guess then you'd generate an error if you have an expression where the relative priority of operators contained within it is... indeterminable (for lack of a better term)?

Yes. In the final program everything must be clearly defined.

You can get < to work by hacking it as a polyadic operator that is syntactic sugar for the conjunction of a sequence of comparison expressions. I'm sure I've seen this done somewhere. But I think you can do something more principled if you make the comparison operators have a result type with a richer semantics than Booleans.

As an aside, we probably don't want to tolerate incoherent expressions such as "2 > 1 < 3", since while we might reasonably claim that it is true, since 2 > 1 and 1 < 3, these expressions are nicer to work with the truth of the whole expression entails nontrivial relations between any two elements of the expression by transitivity, but of course no particular relation between x and y follows from "x > z < y". So I propose that such incoherent expressions should raise exceptions.

Here's a suggestion for a semantics for such expressions, which I'll call the expressions of the mixquality type. The denotation of such expressions is a 4-tuple, <v: Bool, c: Bool, l: Ord, r: Ord>, where v is the truth value of the expression, c is the coherence of the expression, and l and r are numbers or order values denoting the left and right extent of the expression.

Then any number n can be cast into a singleton mixquality with denotation <true, true, [[c]], [[c]]>, and if A and B are mixqualities with denotation <va, ca, la, ra> and <vb, cb, lb, rb>, then the mixquality A<B has denotation <va ∧ vb ∧ [[ra<lb]], ca ∧ cb ∧ (va → [[la <= ra]]) ∧ (vb → [[lb <= rb]]), la, rb>. The same pattern yields a semantics for the other comparison operators.

If we can show that this semantic of qualities is associative, then we are done. Some further points: (i) coherence should be inferable statically, (ii) this allows us to distinguish between safe uses of mixqualities, which raise exceptions when incoherent, and unsafe use where we do not, and (iii) you might like to have expressions of the form "0 < x, y, z < 1", which would need an extension of the semantics.

In your semantics, the expression "3 < x > y" is coherent if x and y happen to both have value 3. Rather than trying to deduce whether a "mixquality" is increasing or decreasing based on the end values (which doesn't work when they're equal), I think you should have a direction flag in your semantics.

I was sure I must have made a mistake or two in the above. So my above denotation of a mixquality isn't enough to determine the relation, which is morally right.

I think we can generalise to having mixqualities being one of {<, <=, =, >, >=, incoherent}.

I think you can lump < and ≤ together and likewise > and ≥. You're right, though, that you need to keep the = case separate. You could label the cases {>, =, <, incoherent} as {-\inf, 0, \inf, and NaN}, and then rule for combining them is addition (where -\inf + \inf = NaN).

Such parsing problem arises with any pairs of operators of the form `{x} a {y}` and `{x} a {y} b {z}`, regardless of types of x, y and z. And this is a particular case too, one can generalize the problem far more.

Agreed. The wider suggestion is to avoid trying to fix these cases by being clever with parsing rules, but by thinking of what the meaning of the expressions should be and using more informative types to support them.

There's no reason I can think of why this couldn't be supported by a language extension mechanism.

I prefer a staged semantics for this kind of thing. Rather than giving a single denotation for the expression which encodes both the meaning of the syntactic form and the value of the form applied to its arguments, I would have a value for the syntactic form which, when applied to proper arguments, produces a value of type Boolean.

Also, returning closer to topic, in response to the idea that this is just an instance of a more general pattern, can someone give an example of another instance of this pattern? The inequality chain shorthand seems to me to have some rather unique characteristics.

There's probably quite a few things that follow the syntactic pattern if not the semantic.

The only scenario I can envision that shares the behavior is something like a declarative workflow where the ops bind to the parameters instead of consume their results.

You are correct. I have fixed my post with this.

And, yes, currently I'm the only compiler for the language.

This is I think not a particularly novel idea. The main issue with it is that even library developers want to write (or even interface with) parsers. If extensible syntax is the nugget your language is built around, shouldn't that be easy/common?

Simple patterns are written easily:

`salary of {e}`
  where e is Employee
  :
  ...

Complex patterns are written with difficulty:

`direction of look of {character} in <image>{picture}</image>`
  parsing
  :
  ... -- Hard and intelligent code using
      -- artificial neural networks.

But they are still writable.

And the programmer even may write his own patterns of syntax description:

`{function name}({args}) = {expr};`
  parsing
  :
  function name := consume until "(";
  args := consume until ")";
  args := args.split(", ").map { |arg| declare variable arg; }
  consume " = ";
  body := parse next expression;
  consume ";"
  declare function (function name) with arguments (args) and body (body);
  -- ... or something like this.

From the looks of this design, you're imagining that each construct gets to decide where it ends. That means that e.g. if you have a function call form 'f(x,y,z)' and you encounter a use of it 'f(e,g,h)', the subform 'e' could hijack the parse and consume the subsequent commas, expressions and even closing parenthesis. This is ugly to me, since I think it's the job of the language to specify and enforce syntactic conventions that will allow independently written parsers to play nicely together.

But here's a more objective problem: do you intend to allow forward references? In many languages you can write something like this:

let
      x = ... y ...
      y = ... x ...

If we generalize to x and y as syntactic forms, how can the y declaration specify the parser that determines where the previous use of y ends?

As for "hijacking" - yes, and I have an example of the form with the similar problem: "(x, y, z) => x < y < z". When the "C# lambda" syntactic form consumes "=>" it then consumes "an expression". But it may consume both "x < y" and "x < y < z". And that's where GLR-like parsing comes in use: when function "parse next expression" is called the parser forks. And both alternatives are being parsed in each fork.

And the parser does not tell about errors only if exactly one fork had survived.

As regards

let
      x = ... y ...
      y = ... x ...

Let's again address to practice: computer parser can not be smarter than human one. So it is up to parsing procedure developer to apply restrictions to the syntactic form or he will not be able to write the parsing procedure. And yes, the developer should first unambiguously split the text into separate declarations and only then parse them.

My task here is only to give API to the parser and its symbol table which will be convenient enough.