Programming Languages

1167 readers

1 users here now

Hello!

This is the current Lemmy equivalent of https://www.reddit.com/r/ProgrammingLanguages/.

The content and rules are the same here as they are over there. Taken directly from the /r/ProgrammingLanguages overview:

This community is dedicated to the theory, design and implementation of programming languages.

Be nice to each other. Flame wars and rants are not welcomed. Please also put some effort into your post.

This isn't the right place to ask questions such as "What language should I use for X", "what language should I learn", and "what's your favorite language". Such questions should be posted in /c/learn_programming or /c/programming.

This is the right place for posts like the following:

"Check out this new language I've been working on!"
"Here's a blog post on how I implemented static type checking into this compiler"
"I want to write a compiler, where do I start?"
"How does the Java compiler work? How does it handle forward declarations/imports/targeting multiple platforms/?"
"How should I test my compiler? How are other compilers and interpreters like gcc, Java, and python tested?"
"What are the pros/cons of ?"
"Compare and contrast vs. "
"Confused about the semantics of this language"
"Proceedings from PLDI / OOPSLA / ICFP / "

See /r/ProgrammingLanguages for specific examples

Related online communities

founded 1 year ago

MODERATORS

armchair_progamer@programming.dev

Compiling higher order functions with GADTs (injuly.in)

submitted 6 months ago by armchair_progamer@programming.dev to c/programming_languages@programming.dev

1 comments fedilink hide all child comments

Implementing first class functions in a bytecode interpreter is trivial.

But how do compilers that generate machine code (or lower to C, or SSA) implement higher order functions? Back in 2021, I found an answer when contributing closures to the Pallene compiler.

Today I was researching something loosely related, and found yet another neat trick called defunctionalization in this paper.

Defunctionalization is a transform -- a way to re-write the original program without using higher order functions such that it can be trivially compiled to a flat IR in subsequent compiler passes.

The paper uses an OCaml example, and I'll be porting the same program to Haskell. Our implementation will assume that the language being compiled supports GADTs, though it's certainly possible to defunctionalize without them.

you are viewing a single comment's thread
view the rest of the comments

[–] ChubakPDP11@programming.dev 1 points 6 months ago* (last edited 6 months ago)

I think by 'GADTs' you mean an AST (could be mistaken). In that case, it would not be a bytecode interpreter, it would be a tree walker. In most languages, an AST is translated down to bytecode, and passed to a VM execution engine. How this engine deals with closures is highly compliant on the architecture of the AST.

First, keep this in mind: A closure is just a closure at the higher-level. Job of the AST is to translate it down to ta more abstract form, thus, a closure would most probably be inlined. Otherwise, it will be a global subroutine defined somewhere on the stack. It never makes sense not to inline closures, unless that closure is a 'hotzone', e.g. frequently used, in whcih case you should most obviously define as a subroutine, and if possible, JIT.

A VM lke NekoVM has a higher-order, terse IR with which you can handle closures like you do in JS.

Don't conflate higher-order constructs with intermediate representations. If you are interested to see a VM development in progress, star my RuppVM. Still early though. But i tend to work on it actively.

Thanks.