blog | oilshell.org

Diffuclties in Shell Implementation

Since coming back, I've been slogging through the shell.

I made a "complete pass" over the front end, fixing various problems and polishing error messages.

I also touched the runtime. It reminded me that I haven't written much about the shell-runtime.

I don't think I will do that, because silly problems drop out of hat. I would rather work on the Oil language. (I've also been working on the OSH-to-Oil translator.

But here is a list of difficult issues.

Implemented

The Core of the Project: Statically Parsing Shell

• Lexer Modes are really the solution. The lexer is the foundation.
• Recursive Descent
• Pratt parsing

Static parsing. However see below about alias.

Here Docs and the LST

There is a small exception to the LST invariant, but the overall principle holds.

I wrote this arena invariant test.

Word Evaluation

I just fixed a bug with this, and it reminded me how complicated it was.

• splitting and globbing , but "reframing"

• word is composed of word_part

• word part evaluates to part_value

• part_vals get reframed into frames

• then unquoted ones get split

  • splitting involves an explicit state machine that creates spans

  • IFS chars vs. IFS whitespace

    IFS=': '

    argv.py 'a : b : c :' argv.py 'a : b : c '

Consistency between Static and Dynamic Variants of the Same Language

• [[ ]] vs [ ]

• $'foo\n' vs echo -e 'foo\n'

  • the silly \c escape

• $(( )) vs expr (not in shell, but I implemented it for toybox)

  • it got me into the precedence climbing thing

Corrolary: find is a dynamic expression language, and we should have a statically-parsed variant of it!

Advertise: looking for someone to implement find/xargs

TODO: better terms than static and dynamic.

String Operations with Quadratic Time

${a ## }

Good thing: Oil no longer depends on Python's regex implementation. Only libc's.

These string ops are deprecated, and I will provide more powerful ones in Oil.

File Desciprotrs

Back to FD bug. OSH Runs Real Shell Programs

It happened asgain! Twice!! Why didn't I think of it?

It required two fixes for two bugs.

• the fd juggling code had to make sure that it iddn't. This fixed one bug.
• removing 'import cgi'. This fixed a second bug that somehow wasn't fixed by the fd juggling.

Unimplemented

Printing Good Error Messages

• LST makes it easy for many cases.

• However other cases are hard:

  • builtins, because they happen after word expansion
    • (the first word is a good bet I guess)
  • alias expansion

• lesson: use tokens everywhere, e.g. for redirects. TODO: for arithmetic.

Alias Requires feedback

It makes parsing undecidable. See this parsing shell paper.

However it depends on how you define the problem.

• recursion
• iteration with trailing space!

Job Control

Not going to solve this

Need some kind of TLA+ formalism.

Looking at all the global variables in bash/dash etc. makes my eyes glaze over. That might be my own issue.

Oil is all abou testing. I'm having trouble imaginging how I would test this.

Interactive Completion

This is the last use case for the parser.

• Execution
• Translation -- prompted LST
• Completion. I believe most shells duplicate some of their parser.

Signals and EINTR

The shell still needs another pass over this. I will probably throw out Python's implementation and make my own.

However, I like the fact that you can git clone Oil and run bin/osh and get started roughly. So it's not clear exactly how this will play out.

Speculative

Writing Two Interpreters and a Compiler Is Hard

I'm still on the first one. What about Scala-LMS? Can I do something there?

• PyPy
• Scala LMS
• Futamura projections

Oil is a project of DSLs.

• I still want to combine shell, awk, and make.

Good and Bad Design Decisions

Very happy with (this should be a separate blog post)

• re2c and lexer modes, as mentioned
• ASDL -- I continue to update the schema, and this 100-line file is really the "source of truth" or backbone to the interpreter.
• Unified ID space throughout the shell. It is very easy to reason about. You can imagine modelling this with types, but I believe it would be a mistake.
  • id and kind
  • used for lexer, AST nodes, and execution. Bytecodes too.
• spec tests
• release process

Unknown:

• OPy. This is still the riskiest part of the project, but I think it will pay off.
  • Explain knuth thing! Everybody is surprised by this!
  • Nick from RC!

Glad I changed:

• Exceptions over return codes. Recursive descent parsers and recursive evaluators almost require exceptions!
  • I made a note that one reason bytecode interpreters are attractive is that they simplify error handling!
  • However I'm still concentrating ont he semantics of shell, and writing an abstract, high-level interpreter is useful. I want exceptions.

I used return codes because I thought I would translate.

However if you know anything about compiling exceptions to control flow, let me know!

I'm learning about control flow graphs, the EmScriptem algorithm, WebAssembly, etc.

Appendix A: Shell Parser Implementations

• Oil (2016)
• explainshell (2014 ? earlier
• mvdan (2016)
• shellcheck (started 2012)
• parsing shell in OCaml, the paper (2016)

I haven't

Multiple invention!