Turing Tarpit

I went back to my original compiler, and I was actually surprised at how good it is. At least, in theory, not in practice. There are a number of simple mistakes in the source, which are mostly attributable to writers block.

I've been looking at targeting GHC core, for no particular reason. It doesn't seem to make a lot of sense. GHC core mostly seems to be desugared Haskell source, so if you're going to target anything, then you'll end up targeting the least of all moving targets, which is plain Haskell source code.

 Thing is... There is no native exception support in Haskell. So you'ld need to bypass common evaluation by either wrapping everything up in a Monad, or emitting continuations with continuations for exceptions and regular evaluation.

Maddening really, stuck in the Turing tarpit.

Lexing

I've been looking at recent implementation of the Kernel language, a Lisp derivative, hoping to find better scanner support. The good new, some of them solved the problem and even implement a REPL on top of the lexer; the bad news, what murky implementations. Maybe there isn't anything better, but, wow, hopeless.

What I call a reader, seems to be called a port. Then it's pure unadulterated C. I thought of reading files to a wide character array for unbounded access, but that makes a REPL impossible. Maybe I'll just read stuff line by line, that could work.

Yeah, the latter should work. I'll mark the start of a lexing operation, and flush up to a certain point in case of success, or rewind otherwise.

Basically, the C code should look like:

token_t* read_token(reader_t* rdr) {
    if (tok= alt_0(rdr)) return tok;
    if (tok = alt_1(rdr)) return tok;
    return null;
}

I.e., lexing tries to recognize decreasingly complex alternatives written like this:

token_t* alt_n(reader_t* rdr) {
    token_t* tok;
    // start scanning
    reader_mark(rdr);
    // try an alternative
    if (reader_look(rdr) == L'c') {
        ...
        // flush all recognized input
        reader_flush(rdr);
        // return the recognized token
        return tok;
    } else if ( ... ) {
        ...
    } else {
        return null;
    }
}

Could work. Bit of a problem on how to handle EOL exactly, REPL demands that the next line is read lazily, but that's about it.

Wow

I haven't done a lot since a year. Oops. Here's the source code of the old -not even wrong- compiler.

Rubbish^3

Cubic rubbish. As stated, I've been looking at doing a reimplementation in C, as an interpreter, and, for the last few months, have mostly been doing other stuff. Like games, or watching movies.

Now I am coding, I am engineering a lexer implementation, and please ignore the last post since it is, well, rubbish. Since I want Unicode support, I've been reading up on C wide characters, and assume for the moment that wide characters are Unicode characters. All nice and dandy.

Now writing a lexer for Unicode most likely means writing a hand coded lexer since the state space for automatically generated scanning automata usually explodes. Also nice and dandy, I've written various small toy languages in my life, and hand coding a lexer shouldn't be that hard.

Rubbish, hand coding a lexer is hard. In the past, I have never written lexers for floating point literals, and floating point scanning breaks the usual one or two symbols lookahead invariant. Moreover, I've often written lexers in functional languages, usually employing my own set of parser combinators meanwhile employing the benefits of functional transparency, curried functions, closures, and garbage collection giving me arbitrary lookahead. With the prime benefit that every step one would advance automagically would be undone for each failure to recognize (part of) a token. Now, I need primitives to back up to a recognized portion of the input in case some alternative fails.

So, stuff I needed to consider when writing a lexer in C: no parser combinators, no curried applications, no referential transparency, no (automatic) state handling, no garbage collection, can't use lexer generators, can't automagically rewind portions of the input.

So I have been looking at other interpreters with hand coded lexers, and what do I find for GCC, Lua, and Python? Rubbish. Okay, be nice: Elaborate rubbish.

I have no clue how people managed to write programs in the past. Except for rubbish.

Large C Projects

I am rewriting the project in C. I am going a bit slow, and am mostly making the usual decisions of where to place what abstraction. Embarrassingly, that's not an easy thing for C. The default seems to be to place all headers in an include directory, and all sources separate. Lousy, I want more and better.

A minimal include directory for external usage, directories for header files for different architectures, for utilities and different stages of the compiler, for testing. And a testing framework. That's what I need.

Now where is an Internet guide to setting up C projects?

Handwritten Scanners and C Streams

Writing a scanner is simple, at least it ought to be. Lexing usualy involves writing down the regular expressions and coding them using a tool like Flex or handwriting them. Usually, it is recommended to use lexing tools though there are sometimes reasons not to use them. The latter reasons normally being portability, context aware lexing of mixed languages, lexing very large files, Unicode, building reentrant scanners, and sometimes speed. GCC for example has a handwritten lexer.

Since regular expressions correspond to finite deterministic automata, LL(1) parsing should normally be enough, and C streams -which allow one byte lookahead- should do the trick. Given lexing tools, that is.

When handwriting a lexer for more complex expressions, stuff gets bizar. What to do with 3.14e+a? Is it a floating point number lacking digits in the exponent, an error, or is it a floating point number followed by an identifier 'e'? In this case, one would really like to have more lookahead than 1, but that is not guaranteed when using C streams.

First: Two random thoughts, and requirements, on lexing I want to share, for no particular reason.

Most programming examples for handwritten lexers use 'get' -get a token- and 'push' -push back a token to the stream- as primitives; I prefer to use 'look' -look at the token- and 'skip' -remove/go to the next token- because it is cleaner and doesn't modify the input source.[1]

One requirement on scanners is usually that a lexer should read (just) enough of the input stream to recognize one token and present that to the parser. The reason: very large files. Despite everything, reading a total source code file for the lexing phase is a not done, and I'll abide to this one rule for no other reason than that the Gods of programming determined it should be so.

Now: The current question of witing a scanner in C.

I am stuck with this question: Can you write a lexer which doesn't put back tokens? And if so, how?


And the answer is: Of course, you can. Most lexing problems reduce to finite deterministic automata, and you can use the state space of the automaton to 'remember' the characters read. But it won't be reentrant since the current state of the scanner consists also of the memorized characters. This is probably why C has pushback streams though that helps little while recognizing complex regular expressions.

The best manner to model a handwritten scanner, I think, is therefor to look at it as some kind of Mealy machine, or some kind of push automaton. It recognizes characters until it gobbled up enough to determine it has recognized enough, emits that character, and saves the scanned but unused characters in its state together with 'meta' state information about what state it should be in given the already read characters.

And presto, we have a design. My lexer should have the following minimal space: position information, a meta state encoding the current recognized token and the state of having recognized a number of characters ahead, characters read, and number of characters to emit. Though the last could be seen as a part of the meta state.

For people who want to know more: Read the Dragon book. This is all information which I reverse engineered from thinking about it, but it should be known and written down in compiler books, though the peculiar interaction of lexing and C streams might not be.

[1] I am guessing at this. But I think the historic rationale is that in very resource minimal environments, it is best to have basically one primitive 'get' and never do any push back; i.e., it saves one call. But I have the feeling that 'look' and 'skip' are academically nicer. Unsure about this.

Unicode Decisions

Strings are peculiar things these days. Since I am now aiming at a high-level language with a fast interpreter, I need to solve what to do with character encodings and string representations.

The best I can think of for now is that characters should be represented internally as wide characters and strings as multibyte sequences.

Which breaks binding to C, since normal characters are much larger than C expects. Unless I think of something smart I'll do this representation anyway, which also means that I'll need a handwritten lexer and parser since tables explode with wide character entries...

No libffi, no lex, no yacc. No libffi also implies glue code or no cheap manner of reusing C libraries. Hmm.... Whatever?