I made a similar proposal at #32620, but I decided to close this issue it as this need not be integrated in the Go compiler itself, a pre-processor can do this as well. I would first implement such a pre-processor, and once it has proven its utility and has become widely popular, it could be considered to integrate it with the compiler itself.

The Rust compiler incorporates a Rust interpreter: https://github.com/rust-lang/miri

Having a Turing complete interpreter in the compiler is a headache because the compiler would have to solve the halting problem to see if your program even compiles. In other words, it's easy to write loops in such an interpreter that might seriously slow down compilation or even cause it to go into an eternal loop. A macro preprocessor would be nice to have for Go, but for the reasons I mentioned, it should not be Turing complete.

I would first implement such a pre-processor, and once it has proven its utility and has become widely popular

Compile time code execution / macros / etc. are available in a plenty of languages and their pros/cons are well known. So, IMO, writing a pre-processor to track its utility is not required.

If CTFE/Macros are available in Go, they are guaranteed to be used by plenty of people. A pre-processor comes not even close to a proper compile time code execution or macro system.

But afaict, because they slow down the compile times, and do not follow the simplicity and design goals of Go, so most likely this proposal won't be accepted.

Having a Turing complete interpreter in the compiler is a headache because the compiler would have to solve the halting problem to see if your program even compiles. In other words, it's easy to write loops in such an interpreter that might seriously slow down compilation or even cause it to go into an eternal loop.

Not really, no. It is very easy problem to solve. For eg., for compile-time code, the Nim compiler tracks the number of iterations of loops (easy to implement), and sets an upperbound on them. If the iterations cross the threshold, the compiler gives an error that the loop iterations are too many. For complex programs, which might require more iterations, it provides --maxLoopIterationsVM:N | set max iterations for all VM loops to change the upper bound.

But anyways, this proposal is for adding a compile-time "language" (Choose a compile time language. Possibly GO, Python, Java, NodeJS or ???), which is a bad idea for a variety of reasons.

What this proposal describes is a language that is very different from Go. Go, like any language, supports generating code using a separate code generator, and Go programmers use that routinely via //go:generate. It's very unlikely that Go would change to add an entire new language that is executed by the compiler. It's even more unlikely that that language would be one as powerful, and as different from Go, as Python.

An integrated compile-time language makes a compiler essentially programmable; there's no question that this would be very powerful. In a similar vain, at a time it was fashionable to make programming languages customizable, from the simple ability to define the precedence of operators (see e.g., Prolog), to the more complex of controlling evaluation of operands, etc.

While such languages can make it much easier to solve certain problems, they also make it much harder to understand what is going on because the programming language can be changed. A reader will effectively have to learn a new language before they can read the code.

Your proposal description is sufficiently high-level and the examples don't show the meta-language, so it's unclear to me how flexible an approach you are envisioning. But clearly you want to analyze format strings at compile time, so there's plenty of power here that could lead to programs that are extremely hard to understand. For instance, the meta-language could modify format strings and thus making it almost impossible to determine what a program is doing w/o actually performing the compile-time computation in one's head. This leads to code that may be easy to write but hard to read for anybody else but the writer (and it will be hard to read for the writer as well after enough time has passed).

In short, I believe any such attempt would significantly reduce Go's readability, yet readability is one of the top priorities for Go, so we're not going to easily compromise on that.

This proposal is incomplete in that it doesn't explain the compile time language. If it did, the additional complexity added to Go, as discussed above, would mean that we will not adopt it. Based on emoji voting, this proposal does not have strong support. Therefore, this is a likely decline. Leaving open for four weeks for final comments.

Compile time language is about making code much more readable, efficient, robust and maintainable. It can greatly simplify many complex problems. Let's assume the meta language is GO so that it's simple for everyone to use. Let's assume that #xxxx( ) calls this go function and passes the parsed data between the parenthesis. The only thing to learn is calling the compiler API's such as inserting code and using compile time reflection.

Go generate or writting a pre-processor are a waste of time in resolving many problems. If they worked well for compile time logic, then how would you propose fixing the CPU overhead in the compiler.

This feature does not change the GO language. It just allows insertion of GO code. Most meta language programs won't be more than a hundred lines. Of all the concerns, "abuse" is the only legitimate concern but that is true with other features (solved using standards and best practices).

If you doubt this works, then ask yourself why the CPU overhead in scanner.go has never been addressed. The answer is it's painful without compile time logic. E.g. the following is code from func scanComment() processing for // comments:

s.next() // ignore the //
for s.ch != '\n' && s.ch >= 0 {
    if s.ch == '\r' {
        numCR++
    }
    s.next()
}

CPU usage could be reduced by over 50% (as much as 90%) for parsing but do you want to code it correctly when it looks so nasty? Do you want to repeat this everywhere this everywhere it occurs?

s.next() // ignore the //
for s.findNext( &[256]byte{0:1, '\n':1, '\r':1, 128:1, --- repeat to 255 --- } ) && s.ch != '\n' {
    if s.ch == '\r' {
        numCR++
    }
}

With compile time language, this would look like:

s.next() // ignore the //
for s.#findNext( "\u0000\r\n" ) && s.ch != '\n' {
    if s.ch == '\r' {
        numCR++
    }
}

#findNext( ) is the compile time function which is passed positional arg 1 "\u0000\r\n" and no keyword parms. It produces the findNext call that you would have coded by hand.

func #findNext(args) {
    goCode = "findNext( &[256]byte{ "
    for i:=0; i < len(args.1); {
        r, w = utf8.DecodeRune(s.src[s.rdOffset:])
        if w == 1 {     
            if r == utf8.RuneError {
                 error("illegal UTF-8 encoding")
            } else {
                 goCode += args.1[i] + ":1, "
            }
        }
        i += w
    }
    for i:=128; i<256; I++ { // process all runes
          goCode+= i  + ":1, "
    }
    goCode += "})"
    ast.insert(*,goCode)
}

#findNext adds a runtime call to Func findNext( ) which is a slightly modified version of the func next( ) from scanner.go. Replace the function prototype. A return true is needed where a character is found and return false when EOF is reached. The CPU reduction comes from the for loop skipping characters that are not used.

func (s *Scanner) findNext(charTable [256]byte) {
    for ; s.rdOffset < len(s.src) && charTable[s.src[s.rdOffset]] == 0; s.rdOffset++ {
}

This feature offers great benefits to all GO developers with a minor amount of change. Most developer's do not have experience with this type of feature so they don't understand how this changes the design of their code. It will take time to change the mindset.

@jonperryman I'm not sure I understand your example - can you elaborate more how I would get the 50% (or even 90%) reduction of CPU usage in scanner.go (or even just scanComment)? I'd definitively be interested in making scanning faster, even at the expense of (localized) ugly code.

Languages such as Go and C strongly encourage a byte processing mentality. C get's around some of this inefficiency by providing multi-byte functions (e.g. memcmp, strcmp, memcpy, strcpy). It does not provide functions such as indexAny() because it is very inefficient without a compile time language. 

You can do bandaid fixes to make scanner.go faster but to make it a speed demon, you will need a different mindset and do a rewrite. To make this easy to understand, lets discuss the small piece of code from scanComment that searches for \n as the end of the // comment.

for s.ch != '\n' && s.ch >= 0 {                                   <===
    if s.ch == '\r' {                                             <===
        numCR++
    }
    s.next()                                                      <===
}

func (s *Scanner) next() {
	if s.rdOffset < len(s.src) {
		s.offset = s.rdOffset                                     <===
		if s.ch == '\n' {                                         <===
			s.lineOffset = s.offset
			s.file.AddLine(s.offset)
		}
		r, w := rune(s.src[s.rdOffset]), 1                        <===
		switch {
		case r == 0:                                              <===
			s.error(s.offset, "illegal character NUL")
		case r >= utf8.RuneSelf:                                  <===
			// not ASCII
			r, w = utf8.DecodeRune(s.src[s.rdOffset:])
			if r == utf8.RuneError && w == 1 {
				s.error(s.offset, "illegal UTF-8 encoding")
			} else if r == bom && s.offset > 0 {
				s.error(s.offset, "illegal byte order mark")
			}
		}
		s.rdOffset += w                                          <===
		s.ch = r                                                 <===
	} else {
		s.offset = len(s.src)
		if s.ch == '\n' {
			s.lineOffset = s.offset
			s.file.AddLine(s.offset)
		}
		s.ch = -1 // eof
	}
}

Notice the statements with "<===" that are executed for each character. These statements don't do anything useful except for /r, /n, 0 and all runes because they are more than 1 byte. To efficiently execute these statements only for those characters, we need to pass a character translation array with the characters of interest on the next( ) function call.

s.next( &[256]byte{0:1, '\n':1, '\r':1, 128:1, --- repeat to 255 --- } )

This is a constant array that must be passed by reference (&) so avoid the overhead of copying the array at each call to next(). The array size must be 256 because a character value can be 0 to 255. We index into this array using each value of each character in the src. Each value in the array defaults to 0 and 0, \n and \r are set to a value of 1 (translation value).
In addition, each rune start byte (128 to 255) is set to a value of 1 (translation value).

func (s *Scanner) next(translationTable *[256]byte) {
    for ; s.rdOffset < len(s.src) && translationTable[s.src[s.rdOffset]] == 0; s.rdOffset++ {
    }

The next( ) function is modified to accept the translation table by reference from the caller. A tight "for loop" loop through the source until there's no more data or the translation value is not 0 (found a character of interest). The compiler should optimize the "for loop" to be very fast because it's so small.

UTF8 is designed to be fast by having all bytes of a rune look like a rune (>127). Since comments are not interested in rune characters, they actually don't need to be included in translation table unless you want rune validation which probably isn't important.

As for other parts of scanner.go, they need the same changes but are convoluted. They should be made readable for clarity and maintenance.

To further improve maintainability and reduce CPU, the GOTO statement should be modified to allow GOTO DEPENDING ON where it supports multiple labels and the label is selected using a variable that contains an index. By specifying the index to a label for each character used in the translation table, you avoid the overhead for IF and CASE statements. The maintainability is improved by reducing repetition.

Also note that other modules need these changes (e.g. xml and json parsing).

Both C and Go provide functions equivalent to indexAny, strpbrk and strings.IndexAny respectively.

Go's IndexAny even dynamically builds a bitset for ASCII-only sets of characters, which'd take less memory than an array of 256 bytes.

I don't think indexAny is a particularly convincing example of why a compile-time language would be useful. If you're searching a constant set of characters, you could just do a one-time conversion to a fast data-structure once at program-startup time, and then repeatedly query using that data structure.

@jonperryman Thanks for the detailed explanations, appreciated. I like to make a few observations specifically to your example (and somewhat unrelated to this issue):

1. go/scanner is not used by the compiler. It's used by gofmt and other tools, though. It is also one of the oldest pieces of Go code there is. It could probably use a refresh. But read on.

2. The compiler uses cmd/compile/internal/syntax (scanner.go) which is much newer, and more efficient (and which is that refresh). Coincidentally, I just improved its performance slightly last week.

3. I agree that things such as comment parsing could be faster. I believe gcc (and others) even use vector instructions to efficiently skip over unused source text such as comments, and possibly collect large strings more efficiently. That said, comment parsing is probably not where the time goes.

4. It may be possible to speed up individual scan functions, such as for comments by 50%, but I'm skeptical that scanning overall can be made 50% faster; and certainly not 90% (but I'd be happy to be proven otherwise). That said, let's assume the scanner runs twice as fast. Since scanning is a very small part of overall compile time (I'm guessing < 5%), that would improve compilation speed by 2.5% at the very best. While this would be nice to have, bigger gains can be gotten elsewhere.

5. The real kicker is the big switch in the scanner, which is probably not translated efficiently. I suspect to really get to a super-efficient scanner, one might want to employ a highly optimizing lexer generator that produces a state machine. That said, note that moving away from lex and yacc (as originally used in Go), made parsing faster... The compiler's parser can process in the order of 1M to 1.5M lines/s on a modern machine - that's parsing and scanning. It's not the bottleneck in the compiler.

6. Regarding your suggestion of using a character translation array: If it's all but looking for NUL's, CR's, and chars > 127, using a short sequence of comparisons is more efficient than a lookup table on modern processors: unless that table happens to always reside in L0 cache (which is almost impossible to control), memory accesses are going to kill performance.

Then there's also the bigger issue of how C/C++ deals with large pieces of software compared to Go: Because C/C++ uses include files, an enormous amount of source text is consumed in each compilation, vastly more than for an equivalent Go program (because Go has proper imports). Thus, super fast scanning is much more important for C/C++ than for Go.

In summary, I don't think special use cases such as scanning/parsing are a good reason for extending Go itself by some sort of compile-time language. In fact, those special use cases led to specialized code generators such as yacc, antlr, coco/r, etc. which can do a much better job.

It looks like what you want is something like constexpr in C++.
Such a construct in Go would sort of be done by adding a new directive //go:constexpr, which does not need a full-fledged CTFE or macro system.

There was further discussion but no change in consensus. The costs of this proposal remain unaddressed. Closing.