3 ms·

Has anyone seen use of a concatenative language, to build vocabulary for broader programming language implementation? So vocabulary for linkage and PICs and sta

Has anyone seen use of a concatenative language, to build vocabulary for broader programming language implementation? So vocabulary for linkage and PICs and stacks and gc and threads and so much else. Not merely "I have this language, so I'll implement and tool it in itself", but moonshot "here's a vocabulary to start implementing other languages... all other languages". Aspiring to implement a C, a V8, an OCaml, and more. Perhaps with bootstrap aids on the side, like a Z3 prover. Sort of like a lisp machine approach, with an integrated commonality from low-level bit twiddling to OS to AI. But with a Racket or Poplog flavor of scaffolding language-like platforms on which to stand. Something like a forth bootstrap, but which doesn't stall out having reached forth, but keeps going, describing a richer and richer space of computation. Has anyone seen anything remotely like that?

downvotetruth 4y ago
> describing a richer and richer space of computation So, changing the compiler from targeting a stack / finite state machine (no register allocation - see zero address format) to registers (NP complete to allocate the registers)? Alternatively, changing the available static / compiled features of a language is usually offered with compiler flags or keywords. Concatenative languages are already Turing complete up the restrictions on functions as such to being total.
- thechao 4y ago
  Why would using registers make it NP complete? Is there a reason concatenative languages aren't (naturally) primal chordal graphs? I mean other than the conservative approximation being to assume it is not?
  - downvotetruth 4y ago
    Why would using registers make it NP complete? If there are no registers to allocate, then there is no Core Register Allocation (NP complete) problem. Is there a reason concatenative languages aren't (naturally) primal chordal graphs? "Naturally" is not distinctive, but concatenative languages can be compiled to registers & induce the Core Register Allocation problem that was proven NP complete by use of primal chordal graphs.
klyrs 4y ago
Well, there is LLVM. Of course, LLIR isn't concatenative, but if you wrote a LLIR interpreter in your language of choice, you could at least compile a ton of other languages into your language of choice. Which isn't exactly what you're looking for, but you said remotely...
- mncharity 4y ago
  Nod. VAST[1] for LLVM MLIR was mentioned in recent discussion[2]. Hmm, so perhaps with a "degree of absorption" axis, from say idiomatic-reimplementation to might-as-well-be-a-shell-call, with also transliterated-port and c-library-api, perhaps one key threshold might be sufficiently-digested-to-permit-refactoring? Puzzlement. With the pain of dealing with LLIR on one end, to an imaginary scraping of LLVM to a non-C++ knowledge representation sufficient for emitting native implementations... I'm unclear on the space's cost/benefit transitions. Or consider large-scale code analysis and refactoring tooling - perhaps having that should be a bootstrap target, a unit of absorption is app repo, and a key threshold is ability to refactor source? Or not repo, but arbitrary scale. So Language Server Protocol blended with dynamic loading and calling convention? Smalltalkish "live" image environment with piles of mutating forked repos? That sort of cross-checks - ask a "programmer apprentice" ai, err, or simply a programming team, "I'd like capabilities foo with characteristics bar", a set of forked repos might be an unremarkable outcome. So that might suggest a language bootstrap target of ffi plus refactoring-LSP client? FFI is an unremarkable bootstrap target, and a refactoring-LSP client gives control over both sides, so maybe next, how to move code across the line? AST scraping and transliteration? Polyglot direct memory access to data types? Suggesting as targets maybe high-end "can exercise and analyze compiler output" ffi, and rich AST tooling? Language implementation, with its specs and test suites, can be a nice context for such work. Which might bring us back around to an emphasis on early implementation of other languages, but with maybe an increased focus on interoperation with existing implementations? Control of config, build, and linkage, might also need emphasis? Hmm, fun, tnx! [1] https://github.com/trailofbits/vast https://github.com/trailofbits/vast [2] https://news.ycombinator.com/item?id=33387149 https://news.ycombinator.com/item?id=33387149

downvotetruth 4y ago

> describing a richer and richer space of computation So, changing the compiler from targeting a stack / finite state machine (no register allocation - see zero address format) to registers (NP complete to allocate the registers)? Alternatively, changing the available static / compiled features of a language is usually offered with compiler flags or keywords. Concatenative languages are already Turing complete up the restrictions on functions as such to being total.

thechao 4y ago
Why would using registers make it NP complete? Is there a reason concatenative languages aren't (naturally) primal chordal graphs? I mean other than the conservative approximation being to assume it is not?
- downvotetruth 4y ago
  Why would using registers make it NP complete? If there are no registers to allocate, then there is no Core Register Allocation (NP complete) problem. Is there a reason concatenative languages aren't (naturally) primal chordal graphs? "Naturally" is not distinctive, but concatenative languages can be compiled to registers & induce the Core Register Allocation problem that was proven NP complete by use of primal chordal graphs.

klyrs 4y ago

Well, there is LLVM. Of course, LLIR isn't concatenative, but if you wrote a LLIR interpreter in your language of choice, you could at least compile a ton of other languages into your language of choice. Which isn't exactly what you're looking for, but you said remotely...

mncharity 4y ago
Nod. VAST[1] for LLVM MLIR was mentioned in recent discussion[2]. Hmm, so perhaps with a "degree of absorption" axis, from say idiomatic-reimplementation to might-as-well-be-a-shell-call, with also transliterated-port and c-library-api, perhaps one key threshold might be sufficiently-digested-to-permit-refactoring? Puzzlement. With the pain of dealing with LLIR on one end, to an imaginary scraping of LLVM to a non-C++ knowledge representation sufficient for emitting native implementations... I'm unclear on the space's cost/benefit transitions. Or consider large-scale code analysis and refactoring tooling - perhaps having that should be a bootstrap target, a unit of absorption is app repo, and a key threshold is ability to refactor source? Or not repo, but arbitrary scale. So Language Server Protocol blended with dynamic loading and calling convention? Smalltalkish "live" image environment with piles of mutating forked repos? That sort of cross-checks - ask a "programmer apprentice" ai, err, or simply a programming team, "I'd like capabilities foo with characteristics bar", a set of forked repos might be an unremarkable outcome. So that might suggest a language bootstrap target of ffi plus refactoring-LSP client? FFI is an unremarkable bootstrap target, and a refactoring-LSP client gives control over both sides, so maybe next, how to move code across the line? AST scraping and transliteration? Polyglot direct memory access to data types? Suggesting as targets maybe high-end "can exercise and analyze compiler output" ffi, and rich AST tooling? Language implementation, with its specs and test suites, can be a nice context for such work. Which might bring us back around to an emphasis on early implementation of other languages, but with maybe an increased focus on interoperation with existing implementations? Control of config, build, and linkage, might also need emphasis? Hmm, fun, tnx! [1] https://github.com/trailofbits/vast https://github.com/trailofbits/vast [2] https://news.ycombinator.com/item?id=33387149 https://news.ycombinator.com/item?id=33387149