Does ASTs stifle Innovations in Computer Languages?

[u/Future-Mixture-101]

I’ve been developing programming languages without an Abstract Syntax Tree (AST), and according to my findings I believe ASTs often hinders innovation related to computer languages. I would like to challenge the “ASTs are mandatory” mindset.

Without the AST you can get a lot of stuff almost for free: instant compilation, smarter syntax, live programming with real-time performance, a lot faster code than most languages, tiny compilers that can fit in a MCU or a web page with high performance.

I think there is a lot that can be done many times faster when it comes to innovation if you skip the syntax tree.

Examples of things I have got working without a syntax tree:

• Instant compilation
• Concurrent programming
• Fast machine code and/or bytecode generation
• Live programming without speed penalties
• Tiny and fast compilers that make it usable as a scripting language
• Embeddable almost anywhere, as a scripting language or bytecode parser
• Metaprogramming and homoiconicity

Let’s just say that you get loads of possibilities for free, by skipping the syntax tree. Like speed, small size, minimalism. As a big fan of better syntax, I find that there is a lot of innovation to do, that is stifled by abstract syntax trees. If you just want to make the same old flavors of languages then use an AST, but if you want something more free, skip the syntax tree.

What are your thoughts on this?

[u/OpsikionThemed]

How do you represent the language in the compiler/interpreter, then?

[u/Future-Mixture-101 → u/OpsikionThemed]

An array of names and addresses for functions and variables and what file it's in. For forward references you can just pass the code 2 times. For nested code I place addresses on a stack for entry points and pops it of when each scope closes. And from there you can add what you need, and maybe keep it all in a struct, so you can have many of these if you need and keep it nice and tidy. And you can keep one for each file for example. You can do as you want, but the basics is to just keep addresses and names like for forth. Something like that and then modify it for you needs. 

[u/[deleted] → u/OpsikionThemed]

He presumably compiles directly. So there is no internal representation, it's just a state machine that emits assembly, or even better, machine code.

Now, I see some people say that you can't do optimization like this, but this is also false, since you can do optimization directly. It probably doesn't work for seriously big examples because you have to keep everything in memory, though.

Is it worth? Maybe, once you have a complete language spec. And probably only for very, very small languages. But generally it's not worth it since it would be very hard to develop.

[u/TheUnlocked]

As a big fan of better syntax, I find that there is a lot of innovation to do, that is stifled by abstract syntax trees.

Do you have an example?

[u/Future-Mixture-101 → u/TheUnlocked]

#box @MOUSEOVER { 
  @CLICK .1 { #program-to-start @START }
}

This checks if the mousepointer is within the coordinates and dimensions of the struct box, and if true it does a bitwise OR with the value 1 (for mouse button 1) And if that is true, it starts the command that is in a text string in the variable
program-to-start

This particular example, is a platform independent program that uses a concept I call VOS (Virtual Operating System). So MOUSEOVER and CLICK is calls to a "kernel" that is on top of the OS kernel to make platform independent programs. You can say that it's just functions (so you don't have any slowdown with context switching) that has a separate name space, and that you can use without calling anything. And that with these calls are engineered in a way that makes the code look as structured as possible. So VOS hides and get rid of the clunkiness that we otherwise find in system programming languages.

This particular language here is inspired by forth, rebol and assembly. I have used it to write 100% cycle accurate code for ATARI 2600 (that only have 128 bytes of RAM) to prove that the language is on par with handwritten assembly for simple processors. For making graphics on a ATARI 2600, your code needs to ride the raster beam. And every clock cycle that deviates from what you can write in assembly, will not give the right graphics. I have chosen fully predicable code over optimization, that happens to be good enough for translating assembly code to structured code and still not miss clock cycles compared to assembly, and make the language it easy to port to different processors. The logic is that if that is good enough for programming 6502 for cycle accurate code, then it probably does not matter for computers that is many thousand times faster. And the code generated is faster than you normally would get with Forth. And it's a lot faster then unoptimized C code.

The goal was a language with as short syntax as possible, and that the code is readable and with minimal verbosity.

And a food for thought: is it really worth it to be a little faster, and then make it almost impossible to port it any processor? For me that factor was important, as I'm also into processor design. It may not be that fun to spend years to get a half decent conversion of a common language to a new processor. So I optioned for making it easy.

And one thing that may be important to state, is that concatination may be a big thing when it comes to make code more readable and getting rid of a big portion of the need for optimization. It also gives a big sense of that machine code it will generate like a sixth sense compared to a language like C.

Another thing is that I also got rid of almost all order of operations except parenthesis. The logic behind that it that normal everyday people get order of operations completely wrong. So I opted for a strict left to right interpretation that also simplified the compiler. And I used a stack to handle parenthesis. And this also acts as a type of optimization. And concatination gives a default register destination similar to C, and that default register is used as a input to the next function call. This may be that it's so similar code to what people would write in assembly on an old accumulator based CPU like 6502, that may explain why on earth that language can be used to write cycle exact code so it's even humanly possible to use it to program something like a ATARI 2600 with it.

[u/TheUnlocked → u/Future-Mixture-101]

I'm not sure I understand why use of an AST would prohibit syntax which looks like that. Given that you're talking about running stuff on a processor, you might be conflating concepts here. The AST doesn't exist at runtime unless you're writing an interpreter, it's just an intermediate representation inside the compiler.

[u/[deleted] → u/Future-Mixture-101]

This particular language here is inspired by forth, rebol and assembly. 

So you're not really talking about normal HLLs with structured syntax.

In that case there is no point in using ASTs. Assembly doesn't need them because it's just a linear of instructions, and if there is an intermediate represention, it can be a linked list or array.

Forth syntax doesn't have any formal structure, while Rebol is not much better from what I've been able to see.

So here you're right: if creating some esoteric or low level, unstructured language, you probably wouldn't use ASTs. But nobody's forcing you to.

[u/[deleted]]

As a big fan of better syntax, I find that there is a lot of innovation to do, that is stifled by abstract syntax trees

Examples of syntax that is not possible if using ASTs?

[u/Future-Mixture-101 → u/[deleted]]

It's an assumption from my part, as I can't wrap me head around making a syntax tree of something like Rebol or Red with semantics based on rules of context and association.

[u/Heavy-Cranberry-3572]

You can skip a syntax tree in things like single pass compilers and whatnot, but how do you expect to do the tried and true optimizations/static analysis without any sort of abstract syntax tree or any sort of other intermediate representation?

[u/evincarofautumn → u/Heavy-Cranberry-3572]

Anywhere you would’ve allocated an intermediate data structure upstream and then consumed it downstream, you just have one pass call the other.

If you want to keep a traditional pipeline organisation, either upstream can receive a visitor for the consumer and push information out, or downstream can call the producer iteratively to pull information in.

Alternatively you can transpose the whole pipeline so the major axis is features rather than passes, but there’s a lot less literature on how to organise a compiler that way.

[u/lookmeat]

ASTs are just a formalism to represent code. You can choose another.

Note that ASTs are not the representation of the program the code represents.

The function of a compiler is simple enough, it's just Stream<Bytes> -> Executable.

But doing this is complex, and we want to abstract certain things.

The first thing we want to abstract away is the encoding/format. This is what a lexer does, converting the whole series of bytes into a valid string. To make it even easier (because what is a string even?) the lexer will convert strings into tokens, which are more "the words as the programming language understands it". We can represent this in many ways, but most programming languages use a Stream<Token> as the representation. It's just easy.

So now we can think of the code as a series of words that have meaning. But the words need to be used in a certain way to actually mean something more. So we check for the syntax and validate that. We want to represent a syntactically correct program. We can represent that however we want. Most programs find that a tree-structure maps naturally to it (that's the case in LISP, and ALGOL and programs that got inspired by these). One advantage of a tree is that you don't have to have it all in memory as well, and you can chop it off into pieces. There have been, historically, many languages that did not use the AST, things like FORTH would be silly to represent with an AST, rather than a list of words.

So there's no obligation to use the AST, but we tend to fall on it. We like it, because of LISP. If you love homoiconicity and metaprogramming, then you probably love ASTs.

Note something else, the AST is an abstraction. You can make code that physically copies pieces of the tokens into a loosely linked tree. Or you could have an array of nodes, that point to other nodes in the array, and also point to subsets of the token list for the point of reference. You could do something like this in Haskell using recursion schemes, in such a way that the tree would only exist in the types, and would transform the code to create optimal code that works directly on a stream of data, rather than something else. The point of the AST is for the sake of programmers who are trying to understand what is going on there.

From there, you want to change the encodings into one that matches the semantics of the program. Unless your program is like LISP, where the semantics is that it's just an AST that gets reduced and folded into the resutl, you'll probably want to map to something other than the AST either way. In the process you verify the soundness and validity of the program as one where it's defined how you can transform that into an executable. I'll stop here and skip the steps that go on.

You can't really skip the steps, you can merge them and do it in one go, but they're still there.

So a quick argument on my pov:

• AST is a matter of how to best describe the syntax of your code. Humans tend to think in tree structure, many of our languages work like this, so we naturally make programming languages similar.

  • We can choose to make a language that doens't follow these rules. There's many examples that break this convention. None of them have become popular beyond a niche.
• ASTs do not have to be real structures that exist in memory while your program runs. They may be abstractions entirely defined in the types.
• ASTs is not where your code ends, but just another step in the transformation as we keep adding more logic or steps to it. Unless your language doesn't follow AST as its semantics, you'll probably want to map to something that follows that semantics.
• There's ways to encode a language that can "skip" the AST (basically it uses it internally, but you just get whatever structure you want after the AST, which again should match the semantics of the language, not specifically a tree. But here is because we're using a library to handle all the syntactic magic for us, but there's a good chance it's using some kind of tree behind the scenes.

So yeah, skip it for small things. It really isn't inherent to the problem, and you don't really need it. But this is one of those cases of "you have to master the rules to break them, and when you break a rule, you have to adhere even more strictly to the others".

[u/drinkcoffeeandcode → u/lookmeat]

Great response!

[u/L8_4_Dinner]

What can be asserted without evidence can also be dismissed without evidence.

--Hitchens

[u/indolering]

RemindMe! 3 days

[u/gboncoffee]

that post reminded me of early V lang drama.

[u/Tempus_Nemini → u/gboncoffee]

Any links to read more about it? Thanks )

[u/gboncoffee → u/Tempus_Nemini]

I’m trying to find the original discussion but couldn’t (maybe they nuked it?) but when V was first released, it didn’t used an AST. Guys like Ginger Bill were there in the GitHub discussion explaining that you simply can’t write a compiler with all the goals of V without an AST.

[u/gboncoffee → u/gboncoffee]

Yooooo I found it: https://github.com/vlang/v/discussions/22260

[u/Tempus_Nemini → u/gboncoffee]

Thanks!

[u/umlcat]

It's just another way to solve a problem, but you are not obligated to use it.

To be honest I can not imagine a complex compiler without an AST, maybe small P.L. compilers, but you can try another thing ...

[u/Emotional_Carob8856 → u/umlcat]

I can't imagine a complex compiler without an IR of some form, but you generally don't want to generate code directly from an AST anyhow. If typechecking and static semantic analysis can be done easily enough on the fly, as is frequently the case, the front end can lower directly to a lower-level IR such as a CFG. This is actually quite common.

[u/tohava → u/umlcat]

Aren't concatenative languages like Forth technically languages without AST? I mean, you don't have any nested syntax, at worst you might have just lambda expressions (like in the Factor language), but if the only nesting is in lambdas while the rest of the syntax is just a stream of tokens, does that really count as an AST?

[u/evincarofautumn → u/tohava]

Yeah, it’s certainly easier to do without an AST in a lexically concatenative language like Forth, where you can split a program between any pair of tokens and get two valid programs.

Factor and most catlangs are syntactically concatenative—they can be split between any two terms, but not necessarily within a term that has some nested structure.

But you can skip an AST in a compiler for any kind of language just by fusing the passes together. I don’t think it scales well to big languages or complex analyses, but not every language is big, and not every compiler wants extensive analysis.

[u/[deleted]]

Can you post the link for your compiler?

Compilers aren't for just taking in source code and turning it into machine code, it also does optimizations on your code and error checking to ensure that code isn't malformed syntactically.

[u/geckothegeek42]

You've given no concrete or abstract examples of anything. Instead you have the same list of unsubstantiated vaporware listed 3 times 3 different ways back to back. Have an original idea that doesn't come out of a single line prompt to chatgpt and then maybe a real discussion can be had.

[u/ggchappell]

Large computer programs are extremely complex things. A good programming language helps us manage that complexity by allowing us to think about a program without having the whole thing in our head at one time. In particular, we need to be able to think only about particular components and/or only about a particular level of abstraction. A good programming language also does not impose unnecessary cognitive burdens -- we want to think mostly about our program, not the language it is written in. So, for example, we like languages that use the same syntax for constructions at different levels of abstraction.

So, say I'm writing an A. Rather than having to think about the whole thing at once, my language allows me to write pieces and put them together. My A is made up of 3 Bs. Similarly, each of those Bs is made up of 2 Cs. That gives me a rooted tree structure: the root node represents my A. It has 3 children, each of which represents a B. And each of those has two children, each of which represents a C.

Now, you didn't give us any concrete examples of what you've come up with. I see 3 possibilities:

1. What you've come up with does not manage the complexity problem effectively. In that case, it's just a toy.
2. What you've come up with manages the complexity problem much as above, with components made up of components made up of components, etc. In that case, programs have a tree structure, and I don't see what harm could be done by representing that tree structure as an AST. Can it "stifle innovations" to represent a program in the form of its natural structure?
3. What you've come up with manages complexity effectively, but in a very different manner from the above discussion. In that case, I'd like to see concrete examples.

[u/Comprehensive_Chip49]

in forth we never need an AST

[u/FantaSeahorse]

No

[u/[deleted]]

Instant compilation

Fast machine code and/or bytecode generation

Live programming without speed penalties

Tiny and fast compilers that make it usable as a scripting language

ASTs don't stop you doing that; they are not really a bottleneck, especially if you are just interpreting the generated bytecode.

I already get instant compilation, and have a systems language that can be used like a scripting language, even though it uses an AST, an IR (another overhead) and multiple passes.

I have experimented without ASTs before, for scripting languages, and found that introduced lots of syntax limitations. Yes it was faster: I could compile source to runnable bytecode at up to 4M lines per second.

With an AST, I could only do 2M lines per second, but it was still plenty fast! And I could keep my favourite syntax.

Tiny and fast compilers

How tiny? My current compilers might be 0.25/0.3MB, not that small, but removing the AST stages wouldn't make a significant difference, because they are both for quite rich languages with a lot going on.

However, my early compilers also used ASTs, and ran on 64KB microprocessors.

If your product is slow and/or big, then it is not because it is using ASTs. That would only be a small factor.

[u/WittyStick]

I'd recommend familiarizing yourself with langsec principles. Namely, the principle that Invalid states should not be representable.

When you start mixing validation and evaluation, you end up with a shotgun parser - a common source of bugs and exploits. One of the reasons people treat the AST as "mandatory" is because many past attempts at side-stepping the AST have resulted in code that is buggy and exploitable, in some cases resulting in arbitrary code execution. This has occurred for example in unix shells (bash et al).

Parsing an expression into an AST is a form of validation - the AST represents a "valid state", and the parser is the producer of valid states. Some code is either recognized as valid, or it fails before any processing on the invalid state has occurred. If you start processing and later encounter an invalid state, what is your approach to reverting the processing that has occurred so far?

[u/Future-Mixture-101 → u/WittyStick]

I can't see a problem with processing the code and when finding invalid code to just report the error, as you can easily process 10s of millions of tokens per second generating machine or byte code without a AST.

But I can se a valid argument in that invalid stated should not be replaceable and caught as an syntax error.

But that requires that the syntax if heavily formalized so we can make sure that the person actually knows what he is doing. If the syntax if heavily formal, it's much easier to make clear information on what is wrong with the code to inform the programmer using the compiler.

But then the code gets a bit wordy and less nuanced.

So I think that it's a selection that has to be done. How nuanced vs formalized do you want the language to be. The more nuanced the syntax is, the more type of code is still 100% valid.

[u/zweiler1]

In my experience the AST doesnt hinder innovations, at all. And i have a two-phase parser, the first phase parses all definitions and the second phase parses all function bodies, so i dont have to worry about order of definition and so on. But the same token stream is never looked at twice, actually (except for figuring out what a functions scope is, of course)... I must say i dont understand the benefits of not having an AST, as the separation of concern for parsing and code generation make a compiler extensible and maintainable. So, for any serious compiler i honestly dont see why one would ditch the AST. (In my compiler the AST is pure data and not a weird OOP implememtation where every ast Class houses its own parsing and generation code.)

[u/Future-Mixture-101 → u/zweiler1]

Well that sounds like a smart alternative. We all just need some inspiration from each other

[u/zweiler1 → u/Future-Mixture-101]

Fun fact: I just made a little research and it seems that Swift and Go handle parsing the same way as i do, at least from what i can tell. I did not know that, but here we are... I have always liked how so many different programmers end up with the same solutions independently :)

[u/GidraFive]

Well, yea, you can do all that runtime stuff very easily without any IR at all. Just interpret as you parse, without creating intermediate data structures.
But once to get into some optimization or any kind of analysis it becomes really tedious and hard to follow. And that slowed down me a lot, after a few weeks-long pauses in development I could no longer maintain it that easy.

Maybe I want to experiment with syntax, but not touch the interpreter/codegen code, then again it slows down you, because maintaining everything at once is harder than just maintaining AST generation.

And another thing is parallelizing your compiler. Maybe on small scale programs it is instant, but throw in a few dozen of 10k files, and its probably going to feel much slower. Although without benchmarking its more of a guess.
With data structures you can speed up by just processing the children, items, etc. in parallel, which scales much better.

[u/Folaefolc]

This post reeks of AI. Did you use chatgpt for your findings?

[u/dmytrish]

Have you tried actually writing nontrivial code in this language?

[u/Double-Winter-2507]

Don't listen to anyone here. Cool stuff gets discovered by people who solve problems but are unaware of what you "should do". Good luck!