Post by @jamey@toot.cat

I had an idea, again. oh dear

I think I could rebuild my old C-to-Rust translator, Corrode, except this time instead of only taking C it would accept any language with a tree-sitter grammar; and instead of only producing Rust it would let you construct any text you want; and instead of trying to be fully automatic and one-size-fits-all it would be interactive and help you write your own rewrite rules to fit your specific source code

using tree-sitter means that, unlike both Corrode and c2rust, you don't have to run the source through the C pre-processor first, so you can preserve comments and also decide how you want each macro translated

purely syntax-directed translation doesn't get you 100% of the way to a correct C to Rust translation, but it covers almost all the most boring parts of a manual translation. and maybe a little extra logic would fit cleanly to help with things like control flow, or C's terrifying arithmetic type promotion rules

while thinking about this I realized you could also build a simple syntax-directed compiler to assembly language the same way, and being interactive might make it a great tool for teaching part of an intro to compilers

so… that seems neat?

3 Boosts

0 Likes

a very weeny construct 💀

@pho4cexa@tiny.tilde.website 54 min. ago

@jamey i really want to say something intellectually encouraging here but all i got is
YESS!! DO ITTTT!!!

what's the best way for your friends to cheer you on, towards work on this idea?

Verity :transHaskell::verifiedtransfem:

@monoidmusician@tech.lgbt 3 hr. ago

@jamey i also had an idea about a language to convert from JSON to HTML

functioning like my applicative parsers, but as a stack that combined structured input/parsing plus state/locals plus structured output

i was gonna call it Conversation:

https://github.com/MonoidMusician/blog/blob/main/PureScript/src/Conversions/Conversation.purs

the control flow of the parser is the datatype; you wouldn't need to parse, construct some data, and then traverse that data to print it

and there would be dedicated support for phases, like, “first traverse it and assemble a map of IDs to objects, from the list of objects with their IDs as fields”

idk, i just think the idea of a souped-up regex+jq-esque language that has dedicated pattern matching and output constructing forms could be nice. maybe even applicable to your tree sitter idea

View

Jamey Sharp

@jamey@toot.cat 3 hr. ago

@monoidmusician ooh, Conversation does sound nifty! that reminds me that I've been trying to figure out for several years what a language would look like where control flow is treated like a regular language plus recursion (so, a context-free language), and data flow is over types satisfying semiring laws so you can efficiently handle the limited non-determinism in parsing. in that context I'd think of what you're describing as transducers, which I feel are a tool sorely lacking in our current toolbox. I feel like there are huge missed opportunities from all these great regex engines and parser generators being limited to merely string matching

Verity :transHaskell::verifiedtransfem:

@monoidmusician@tech.lgbt 12 hr. ago

@jamey

it would accept any language with a tree-sitter grammar

... a bit later ...

don't have to run the source through the C pre-processor first

oh no, that really is the compromise position, isn't it? the distance from unpreprocessed C to standard C is about the same order of magnitude of C to any other standard language

Jamey Sharp

@jamey@toot.cat 11 hr. ago

@monoidmusician I think I agree with your characterization but I'm not quite sure what you mean 😅

for my purposes, I think the key point is that what people actually program in is C+cpp, and my goal in partially automating translation projects is to preserve author intent as much as possible, so the language people are actually writing in is the closest to that, and running the preprocessor first was always a hack

I think it's super interesting that tree-sitter can get away with parsing source that hasn't been run through cpp partly because people usually write macros to be valid expressions or statements, but mostly because it has to accept bad syntax and try to recover and keep parsing anyway, because that's part of the IDE use case for it

medium rare bird

@migratory@jorts.horse 8 hr. ago

@jamey @monoidmusician from what I've seen tree-sitter's handling of C macros is incomplete in frustrating ways--C preprocessor macros don't always expand to entire or single syntax nodes, which tree-sitter-c doesn't handle in its full generality; see https://github.com/tree-sitter/tree-sitter-c/issues/108 for example

GitHub

Handling of preprocessor macros is not general enough · Issue #108 · tree-sitter/tree-sitter-c

While looking into how one could tackle zeek/tree-sitter-zeek#6 I looked into this grammar for inspiration and noticed that it has similar issues. In C or C++ preprocessor macros can appear around ...

Jamey Sharp

@jamey@toot.cat 3 hr. ago

@migratory @monoidmusician yeah, I knew it couldn't be perfect, though it's nice to see concrete examples.

my hypothesis is that by making this an interactive tool that supports a person during a translation project, rather than trying to completely automate the project, these cases won't be a big deal because the person can choose how to handle them.

from that perspective the most important property is that tree-sitter recovers soon after these error parses and they don't affect nearby input. and since that's the same requirement for good syntax highlighting on a source file that's being actively edited, I'm hopeful that tree-sitter can do that well.

also I think it's interesting that all of the examples in that issue can probably be fixed with small local rewrites, so there might be a usable workflow involving first editing the C source to be easier to translate, which I think is likely to be a good plan in a lot of cases anyway.

Verity :transHaskell::verifiedtransfem:

@monoidmusician@tech.lgbt 11 hr. ago

@jamey well, there's kind of an arbitrary long distance from unpreprocessed source to semantic C, the languages don't retain many structural similarities (other than basic lexical syntax and balanced braces i guess?).

and i agree with you that there's important information, semantic information, in the comments and choice of macros and such that would be beneficial to a translation. but to get at that information you have to parse a dialect of some-language-with-balanced-braces, it's hard to even call it (machine-recognizable) C anymore

the other approach would be using a preprocessor that has really strict provenance, so you end up with standard-semantic-C tagged with all of the preprocessor information that was in the source: how it got to B from A. but that sounds like more work, less of a clear interface ...

Jamey Sharp

@jamey@toot.cat 11 hr. ago

@monoidmusician I've been under the impression that libclang, which is used by c2rust, tracks macro provenance in the way you're describing, but I think it was hard to use correctly

Verity :transHaskell::verifiedtransfem:

@monoidmusician@tech.lgbt 11 hr. ago

@jamey like, template haskell has the “generates code” problem, but it doesn't have the “you can walk all over the keyword, operator, and positional syntax of the language you are targeting that makes meaningful parsing and semantic analysis impossible before running the preprocessor”

1+ more replies

dch :flantifa: :flan_hacker:

@dch@bsd.network 12 hr. ago

@jamey a code whisperer tool sounds incredible

Jamey Sharp

@jamey@toot.cat 12 hr. ago

@dch I feel like my description brought up images in your head and I'd love to hear about them. 😁 I'm not quite sure what "code whisperer" means here

dch :flantifa: :flan_hacker:

@dch@bsd.network 11 hr. ago

@jamey lol 3 things came to mind, all before breakfast and coffee, so bear with me.

This sounds a bit like magic - take code in 1 language, output stuff in another language. Clearly where there is substantial overlap in semantics and behaviour this might go quite a way, but from say C -> erlang I wonder what the result might be.

Using this as a pipe tool in the command line, particularly for small snippets, would be very interesting. I spend a lot of time staring angrily at C code and trying to understand what the compiler / resulting output is actually doing. Having something that can turn it into a more verbose, structured form could be really useful.

And having it as a popup in an editor could also be neat, like an LSP extension.

All in all this sounds like it would whisper code secrets to the discerning user.

Jamey Sharp

@jamey@toot.cat 11 hr. ago

@dch Absolutely true that pure syntax-directed translation will work better for some pairs of languages than for others. I'm curious about between, say, OCaml and Erlang

1 more reply

[object Object]

@zzt@mas.to 12 hr. ago

@jamey that sounds cool! kind of like a language workbench whose base language is a tree sitter data structure

Jamey Sharp

@jamey@toot.cat 12 hr. ago

@zzt it sounds like "language workbench" is a phrase I might wish to know more about. got anything in particular you'd recommend looking at?

the closest comparisons I had come up with were maybe "jq but for arbitrary languages and interactive", or the ast-grep scan command but for the case where you want to rewrite everything, not just replace a few bits here and there

[object Object]

@zzt@mas.to 12 hr. ago

@jamey oh definitely! the classic open source example is Racket, which is a Scheme variant with a flexible reader that allows you to switch to arbitrary grammars (via the #lang form at the top of a file). those grammars get read into s-expression ASTs, then expanded into Racket base language forms. it even has IDE support for syntax highlighting and completion for those languages: https://racket-lang.org/

another example is JetBrains MPS, which introduced me to the concept. it seems to no longer be under active development, but there’s some cool concepts there: https://en.wikipedia.org/wiki/JetBrains_MPS

the language workbench idea is active in my mind because I’m currently working on an emacs language workbench, which expands on the Racket concept with sublanguages (the reader and syntax highlighting can switch mid-program), assembly output, and a REPL that can switch languages

JetBrains MPS

JetBrains Meta Programming System - a domain specific language design tool.

Racket

Jamey Sharp

@jamey@toot.cat 12 hr. ago

@zzt oh! Racket is one of those things I've meant to dig into for years and never quite got around to

I like that tree-sitter has support for nested sublanguages but I haven't managed to grasp how it does that yet. I feel like that's important for dealing with things people write in practice, so I think it's cool that you're doing that too

1 more reply

[object Object]

@zzt@mas.to 12 hr. ago

@jamey I have some scattered notes on here for my implementation that might be somewhat coherent, and I hope to release it fairly soon! I’ve got the major functional pieces complete except for the REPL, but there’s a lot of API I want to build on top

1 more reply