• 2 Posts
  • 32 Comments
Joined 1 year ago
cake
Cake day: June 14th, 2023

help-circle

  • Other way around, actually; C was one of several languages proposed to model UNIX without having to write assembly on every line, and has steadily increased in abstraction. Today, C is specified relative to a high-level abstract machine and doesn’t really resemble any modern processing units’ capabilities.

    Incidentally, coming to understand this is precisely what the OP meme is about.
















  • Your code looked alright. Working in C is a risky chore. You’re early in your journey and I think it’s good to get a taste of many of the traditional techniques before turning towards newer fancier algorithms.

    “Haskell and OCaml”, hm? The two concepts you need to internalize are katamorphisms and paramorphisms. You may have heard of “recursion schemes”; these two schemes are the ones available on any tree. Fundamentally, most of a compiler is tree-to-tree transformations (nanopasses), and they are expressible as one of two forms:

    • Katamorphism: The leaves of each node are transformed before the branch (bottom-up)
    • Paramorphism: The leaves are transformed after/during the branch transformation (top-down)

    If you look again at my AST builder builder, you’ll see .run() and .walk() methods, implementing the recursion for any katamorphism or paramorphism respectively. In Haskell, these are called Traversable types. This is a pun in Monte, where .run() is also the default method; the syntax makes it easy to perform a katamorphism by passing a tree-traversing object directly to the AST.

    Your types are alright, but you’ll want to pass a generic parameter through them, turning them into a valid Functor in Haskell or a generic module in OCaml. This is a basic defense against the “AST Decoration Problem”, AKA the “AST Typing Problem”. As you add features to your compiler, you’ll realize why these are necessary.