5 ms·

Om is a novel, maximally-simple concatenative language

147 points by memorable 4y ago

jboynyc 4y ago
I found some context about this project in a comment by its creator: https://news.ycombinator.com/item?id=5098216 https://news.ycombinator.com/item?id=5098216
jp0d 4y ago
There isn't much activity on Github. The last release was nine years ago and all the code contributions are from a single person. https://github.com/sparist/Om https://github.com/sparist/Om
- brokenkebab2 4y ago
  How's this important for a project which is obviously an experiment in PLs field? You either interested in such things, or not, nothing else applies.
  - JasonFruit 4y ago
    I don't know, maybe someone wanted to try writing a program in it, which seems not irrelevant to programming languages. To most people, even an experimental programming language isn't just an objet d'art; it's more like an ornate tennis racket, and it doesn't look like this one will ever be strung.
    - jp0d 4y ago
      Thank you. Aptly written. Even if the idea is fantastic, if not much happens for years, it's almost safe to assume that the product is sort of dead. But it kind of depends! An old academic language like Standard ML might not get a lot of action on its repo (actually gets updated frequently), I'd still use it as it forms the basis of several successor languages.
    - canadianfella 4y ago
      > objet d'art Why french?
      - JasonFruit 4y ago
        That's a reasonable question, and one I asked myself. I considered some options: - "Piece of art" didn't communicate engagement with the item as art - "Work of art" is often used to mean a masterpiece - "Artwork" is a neologism of the sort I avoid Finally, "objet d'art" communicates appreciation as art, but not necessarily any artistic quality, and it's a phrase people use in this context. While we're asking irrelevant questions, why are the majority of your comments questions and criticisms of trivial matters of wording? Obviously, we agree that words are important, but it's equally important to engage with the intended meaning of those words.
      - chowells 4y ago
        Why do you think it's French? The term has developed a distinct meaning among speakers of English. It has slightly different connotations than alternative phrases, as the sibling comment points out. It may be derived from French, but it has a distinct meaning in English. You might as well ask why someone is using French when they say they're going to see a ballet. It's a feature of English (and really, most languages) that foreign words and phrases are often imported and given connotations distinct from both the meaning in the language of origin and from other words or phrases in English. Once that adoption is widely recognized, is it really not English?
    - rtepopbe 4y ago
      Just because it hasn't seen activity in awhile doesn't mean it can't be used at all. Sure, you're not going to want to start up a major project with a long-abandoned language experiment, but frankly it's not much of a step down from even an active language experiment. I suppose it's got a greater chance of being harder to get going, but so much of that depends on how it was built in the first place that simply being older isn't enough information make much of a guess on that either.
      - JasonFruit 4y ago
        The home page is careful to point out that it lacks a lot that would be needed to make it capable of doing interesting and useful things: > …the software is currently at a very early "proof of concept" stage, requiring the addition of many operations (such as basic number and file operations) and optimizations before it can be considered useful for any real-world purpose.
  - remram 4y ago
    The website mentions that it is "not complete" and that "the intent is to develop it into a full-featured language". This is pretty different from your characterization as a finished experiment.
- heynowheynow 4y ago
  Lack of activity means lack of activity. Code doesn't evaporate if the API hasn't broken promises like a javascript library does every other week.
brokenkebab2 4y ago
Interesting idea. Though maximally-simple claim doesn't look warranted to me. It feels more complex than most of Forth incarnations.
- colomon 4y ago
  Right? Its creator obviously knows Forth, but it feels like they've gone to extreme lengths to make it prefix rather than postfix, at the price of making it much more confusing than it needs to be? It's really not obvious to me that if they were both equally complete, there'd be any advantage at all to choosing this over Factor... (That said, I did a lot of Forth programming in the old days, and while I am utterly intrigued by Factor, I've never managed to write anything useful in it...)
  - astrobe_ 4y ago
    That happens too often with Forth. Someone gets interested, thinks it would be sooo awesome to add this and that "modern" feature, and then they end up with something that combines the disadvantages of Forth with the complications of what they've added. An oddity nobody wants to use, and yet another bit-roting carcass is some CVS. It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration [1] I think that Forth only works with people who've started with assembly programming. Someone who started with a high level language suffered that sort of brain damage that make them unable to feel complexity even when it coils around them and give them a hard time breathing. [1] https://www.cs.virginia.edu/~evans/cs655/readings/ewd498.html https://www.cs.virginia.edu/~evans/cs655/readings/ewd498.htm...
    - diffxx 4y ago
      > I think that Forth only works with people who've started with assembly programming. Someone who started with a high level language suffered that sort of brain damage that make them unable to feel complexity even when it coils around them and give them a hard time breathing. What I find interesting about Forth is that it is a language that is simultaneously a high level language and a low level language. It encourages the programmer to write high level programs but if they need to write low level assembly routines for maximal performance, they can (though they may need to write their own Forth interpreter to do so). I believe that the viral spread of c and unix is possibly the worst thing that ever happened to computing. There is a quote attributed to a physician named Vincent Felitti in the context of addiction: it's hard to get enough of something that almost works. This is the story of c. It is neither a high level language nor a low level language and is thus the worst of both worlds. We've added a staggering amount of complexity to work around the limitations of c, which have also infected most of our other supposedly high level languages, e.g. java, go, rust, etc. To your point though, because we know no other way, we can't even see that much of this complexity is largely unnecessary. Much of this goes back to Gabriel's observations in the rise of worse is better: https://www.jwz.org/doc/worse-is-better.html https://www.jwz.org/doc/worse-is-better.html. What I think Gabriel doesn't fully articulate is that worse is better is an essential feature of market capitalism. The most profitable customers are addicts. Most of the time, you can't just sell them something that is complete garbage. The best thing to sell is something that is almost good enough and that the customer is not empowered to improve themselves. Then they have to keep coming back to you for updates. Why would you sell a customer a complete program that does exactly what it is meant to do and nothing else when you could sell them something incomplete that you can keep repeatedly selling back to them? This is the water that we swim in, and it sure seems to me that we're all having a hard time breathing.
jansan 4y ago
A "Hello World" code example would be worth more than 1000 words.
- thom 4y ago
  There’s an examples section way, way down the page. I do agree that language homepages should probably start with this, that’s how my brain works anyway.
- superdimwit 4y ago
  There’s a Hello World on the page
  - eternalban 4y ago
    No, that is not a program emitting to output stream "hello, world!" It emits "{Hello, world!}" which is like emitting "func main() { print("hello, world!" } }" A hello, world for this language would take "hello, world" as an operand to some operator that spits out strings. That example is not there.
    - xiphias2 4y ago
      If you read the description the language outputs programs. If it would be able to output any string, it wouldn't be concanative language anymore.
- deleted 4y ago
  [deleted]
Garlef 4y ago
Could someone explain this bit from the intro to me? > Recursion is very efficient in the Om language, due to (a) the "eager" evaluation model enabled by prefix concatenative syntax... How is the syntax of any relevance for the evaluation model? Once the AST is parsed, the syntax is gone and we're just left with pairs of 'operator' and 'operand'.
- Garlef 4y ago
  Another question about the syntax: Why are the curly braces also part of the syntax for operators? They are delimiters for the operands but also play some part in the definition of operators? Is this solving some problem or did the author just like curlies?
  - myco_logic 4y ago
    If you're talking about the curly braces after the backtick in the syntax diagram for operators, I think that's just a way to escape those special characters so you can use them in operator names. It would be the same as escaping a double quotation mark in a string literal with a backslash, i.e: "\""
    - Garlef 4y ago
      Merci. Thets also the explanation I came up with for myself. And I guess it allows for some trickery with unquoting.
- nine_k 4y ago
  The syntax allows to describe structures in a way that makes the evaluation model efficient, or even possible. Look at what lengths one has to go constructing a Y combinator when syntax does not allow to refer to the current expression to simply describe recursion.
  - deleted 4y ago
    [deleted]
garganzol 4y ago
Looks like an intriguing idea but it lacks examples except the "Hello world" at the bottom of the page. But it's not enough! More examples please.
guerrilla 4y ago
Looks like Forth but more complicated to me...
- apgwoz 4y ago
  It’s heavily inspired by Joy https://en.wikipedia.org/wiki/Joy_(programming_language) https://en.wikipedia.org/wiki/Joy_(programming_language) from the looks of it.
deleted 4y ago
[deleted]
carapace 4y ago
FWIW, I've been playing around with Joy (Manfred von Thun's concatinative language) and there's definitely "something there" IMO. For one thing, I've come around to the view that syntax is waaaay over-emphasized in our current languages. The way I like to put it is syntax is a MacGuffin, "an object, device, or event that is necessary to the plot and the motivation of the characters, but insignificant, unimportant, or irrelevant in itself." You have to have some syntax to write programs, but not nearly as much as we typically use. I haven't dug into Om yet, but Joy feels like the simplest useful language. (BrainF*ck is simpler but harder to use, Lisp and Forth are more complex.) For another, the concatinative systems seem to be simpler to reason about than Lambda Calculus-based systems (most current PLs.) What I mean is, these languages fulfill Backus' vision of FP systems wherein you can derive programs by doing algebraic manipulation of programs. (You can do this in any language, of course, but Joy et. al. seem to make it especially easy.) I suspect this has something to do with Category Theory (see http://conal.net/papers/compiling-to-categories/ http://conal.net/papers/compiling-to-categories/ ) All this to say, if you haven't already, do have a look at Concatinative languages.
- heynowheynow 4y ago
  Well, LISP too. Define, compose, and apply. Barely above a common language of math and mirroring many languages' parsed AST of equivalent constructs. People enjoy using simple things in a "worse is better"/paradox of choice way. Unfortunately, simple doesn't do threading, exceptions, side-effects, or C library linkage. Simple doesn't scale when you need a deploy button, a backup and restore button, firewall rules API, monitoring logic, or a scale-to-5000-stateless-nodes-behind-a-proxy supervisory service.
sparist 4y ago
Original author here. Didn’t expect my little hobby project to land on the front page of Hacker News. In the midst of a complete rewrite of the language which I unfortunately only get to nibble at here and there; will hopefully publish it soon.
- myco_logic 4y ago
  As a concatenative language lover/designer I just thought I'd put it out there how much of an inspiration Om has been to me, I absolutely adore your language! Om is one of the most beautiful programming languages I've ever seen, and surely one of the most unique too. Most other concatenative languages are Joy/Factor-esque stack languages, so to see an entirely different vision with your prefix notation is an absolute delight . Your panmorphic type system is also genius (the only other language I know of that has something similar is TCL). The way you treat whitespace separators in your syntax is also very clever, I love that it basically enables one to encode strings without a dedicated literal syntax element. Anyway, I just wanted to let you know how much I appreciate your design and implementation efforts. I hope your rewrite is going well, and I look very much forward to its eventual release...
- unsafecast 4y ago
  I'm glad to know you're still working on it! I thought the current Om was a finished experiment. By the way, your language has been a big inspiration for my own designs. Thanks!
asdfasdfasdfggg 4y ago
If hating on Lisp’s parentheses in your spare time is not providing enough joy for you, I present to you Om {with which you can complain about too many curlies}.
heynowheynow 4y ago
Perhaps I missed it, but I was hoping for currying and application.
mncharity 4y ago
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.
culi 4y ago
Surprised it doesn't show up on PLDB: https://pldb.com/index.html https://pldb.com/index.html
- culi 4y ago
  Edit: added it myself

147 points by memorable 4y ago

I found some context about this project in a comment by its creator: https://news.ycombinator.com/item?id=5098216 https://news.ycombinator.com/item?id=5098216

jp0d 4y ago

There isn't much activity on Github. The last release was nine years ago and all the code contributions are from a single person. https://github.com/sparist/Om https://github.com/sparist/Om

brokenkebab2 4y ago
How's this important for a project which is obviously an experiment in PLs field? You either interested in such things, or not, nothing else applies.
- JasonFruit 4y ago
  I don't know, maybe someone wanted to try writing a program in it, which seems not irrelevant to programming languages. To most people, even an experimental programming language isn't just an objet d'art; it's more like an ornate tennis racket, and it doesn't look like this one will ever be strung.
  - jp0d 4y ago
    Thank you. Aptly written. Even if the idea is fantastic, if not much happens for years, it's almost safe to assume that the product is sort of dead. But it kind of depends! An old academic language like Standard ML might not get a lot of action on its repo (actually gets updated frequently), I'd still use it as it forms the basis of several successor languages.
  - canadianfella 4y ago
    > objet d'art Why french?
    - JasonFruit 4y ago
      That's a reasonable question, and one I asked myself. I considered some options: - "Piece of art" didn't communicate engagement with the item as art - "Work of art" is often used to mean a masterpiece - "Artwork" is a neologism of the sort I avoid Finally, "objet d'art" communicates appreciation as art, but not necessarily any artistic quality, and it's a phrase people use in this context. While we're asking irrelevant questions, why are the majority of your comments questions and criticisms of trivial matters of wording? Obviously, we agree that words are important, but it's equally important to engage with the intended meaning of those words.
    - chowells 4y ago
      Why do you think it's French? The term has developed a distinct meaning among speakers of English. It has slightly different connotations than alternative phrases, as the sibling comment points out. It may be derived from French, but it has a distinct meaning in English. You might as well ask why someone is using French when they say they're going to see a ballet. It's a feature of English (and really, most languages) that foreign words and phrases are often imported and given connotations distinct from both the meaning in the language of origin and from other words or phrases in English. Once that adoption is widely recognized, is it really not English?
  - rtepopbe 4y ago
    Just because it hasn't seen activity in awhile doesn't mean it can't be used at all. Sure, you're not going to want to start up a major project with a long-abandoned language experiment, but frankly it's not much of a step down from even an active language experiment. I suppose it's got a greater chance of being harder to get going, but so much of that depends on how it was built in the first place that simply being older isn't enough information make much of a guess on that either.
    - JasonFruit 4y ago
      The home page is careful to point out that it lacks a lot that would be needed to make it capable of doing interesting and useful things: > …the software is currently at a very early "proof of concept" stage, requiring the addition of many operations (such as basic number and file operations) and optimizations before it can be considered useful for any real-world purpose.
- remram 4y ago
  The website mentions that it is "not complete" and that "the intent is to develop it into a full-featured language". This is pretty different from your characterization as a finished experiment.
heynowheynow 4y ago
Lack of activity means lack of activity. Code doesn't evaporate if the API hasn't broken promises like a javascript library does every other week.

brokenkebab2 4y ago

Interesting idea. Though maximally-simple claim doesn't look warranted to me. It feels more complex than most of Forth incarnations.

colomon 4y ago
Right? Its creator obviously knows Forth, but it feels like they've gone to extreme lengths to make it prefix rather than postfix, at the price of making it much more confusing than it needs to be? It's really not obvious to me that if they were both equally complete, there'd be any advantage at all to choosing this over Factor... (That said, I did a lot of Forth programming in the old days, and while I am utterly intrigued by Factor, I've never managed to write anything useful in it...)
- astrobe_ 4y ago
  That happens too often with Forth. Someone gets interested, thinks it would be sooo awesome to add this and that "modern" feature, and then they end up with something that combines the disadvantages of Forth with the complications of what they've added. An oddity nobody wants to use, and yet another bit-roting carcass is some CVS. It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration [1] I think that Forth only works with people who've started with assembly programming. Someone who started with a high level language suffered that sort of brain damage that make them unable to feel complexity even when it coils around them and give them a hard time breathing. [1] https://www.cs.virginia.edu/~evans/cs655/readings/ewd498.html https://www.cs.virginia.edu/~evans/cs655/readings/ewd498.htm...
  - diffxx 4y ago
    > I think that Forth only works with people who've started with assembly programming. Someone who started with a high level language suffered that sort of brain damage that make them unable to feel complexity even when it coils around them and give them a hard time breathing. What I find interesting about Forth is that it is a language that is simultaneously a high level language and a low level language. It encourages the programmer to write high level programs but if they need to write low level assembly routines for maximal performance, they can (though they may need to write their own Forth interpreter to do so). I believe that the viral spread of c and unix is possibly the worst thing that ever happened to computing. There is a quote attributed to a physician named Vincent Felitti in the context of addiction: it's hard to get enough of something that almost works. This is the story of c. It is neither a high level language nor a low level language and is thus the worst of both worlds. We've added a staggering amount of complexity to work around the limitations of c, which have also infected most of our other supposedly high level languages, e.g. java, go, rust, etc. To your point though, because we know no other way, we can't even see that much of this complexity is largely unnecessary. Much of this goes back to Gabriel's observations in the rise of worse is better: https://www.jwz.org/doc/worse-is-better.html https://www.jwz.org/doc/worse-is-better.html. What I think Gabriel doesn't fully articulate is that worse is better is an essential feature of market capitalism. The most profitable customers are addicts. Most of the time, you can't just sell them something that is complete garbage. The best thing to sell is something that is almost good enough and that the customer is not empowered to improve themselves. Then they have to keep coming back to you for updates. Why would you sell a customer a complete program that does exactly what it is meant to do and nothing else when you could sell them something incomplete that you can keep repeatedly selling back to them? This is the water that we swim in, and it sure seems to me that we're all having a hard time breathing.

jansan 4y ago

A "Hello World" code example would be worth more than 1000 words.

thom 4y ago
There’s an examples section way, way down the page. I do agree that language homepages should probably start with this, that’s how my brain works anyway.
superdimwit 4y ago
There’s a Hello World on the page
- eternalban 4y ago
  No, that is not a program emitting to output stream "hello, world!" It emits "{Hello, world!}" which is like emitting "func main() { print("hello, world!" } }" A hello, world for this language would take "hello, world" as an operand to some operator that spits out strings. That example is not there.
  - xiphias2 4y ago
    If you read the description the language outputs programs. If it would be able to output any string, it wouldn't be concanative language anymore.
deleted 4y ago
[deleted]

Garlef 4y ago

Could someone explain this bit from the intro to me? > Recursion is very efficient in the Om language, due to (a) the "eager" evaluation model enabled by prefix concatenative syntax... How is the syntax of any relevance for the evaluation model? Once the AST is parsed, the syntax is gone and we're just left with pairs of 'operator' and 'operand'.

Garlef 4y ago
Another question about the syntax: Why are the curly braces also part of the syntax for operators? They are delimiters for the operands but also play some part in the definition of operators? Is this solving some problem or did the author just like curlies?
- myco_logic 4y ago
  If you're talking about the curly braces after the backtick in the syntax diagram for operators, I think that's just a way to escape those special characters so you can use them in operator names. It would be the same as escaping a double quotation mark in a string literal with a backslash, i.e: "\""
  - Garlef 4y ago
    Merci. Thets also the explanation I came up with for myself. And I guess it allows for some trickery with unquoting.
nine_k 4y ago
The syntax allows to describe structures in a way that makes the evaluation model efficient, or even possible. Look at what lengths one has to go constructing a Y combinator when syntax does not allow to refer to the current expression to simply describe recursion.
- deleted 4y ago
  [deleted]

garganzol 4y ago

Looks like an intriguing idea but it lacks examples except the "Hello world" at the bottom of the page. But it's not enough! More examples please.

guerrilla 4y ago

Looks like Forth but more complicated to me...

apgwoz 4y ago
It’s heavily inspired by Joy https://en.wikipedia.org/wiki/Joy_(programming_language) https://en.wikipedia.org/wiki/Joy_(programming_language) from the looks of it.

deleted 4y ago

[deleted]

carapace 4y ago

FWIW, I've been playing around with Joy (Manfred von Thun's concatinative language) and there's definitely "something there" IMO. For one thing, I've come around to the view that syntax is waaaay over-emphasized in our current languages. The way I like to put it is syntax is a MacGuffin, "an object, device, or event that is necessary to the plot and the motivation of the characters, but insignificant, unimportant, or irrelevant in itself." You have to have some syntax to write programs, but not nearly as much as we typically use. I haven't dug into Om yet, but Joy feels like the simplest useful language. (BrainF*ck is simpler but harder to use, Lisp and Forth are more complex.) For another, the concatinative systems seem to be simpler to reason about than Lambda Calculus-based systems (most current PLs.) What I mean is, these languages fulfill Backus' vision of FP systems wherein you can derive programs by doing algebraic manipulation of programs. (You can do this in any language, of course, but Joy et. al. seem to make it especially easy.) I suspect this has something to do with Category Theory (see http://conal.net/papers/compiling-to-categories/ http://conal.net/papers/compiling-to-categories/ ) All this to say, if you haven't already, do have a look at Concatinative languages.

heynowheynow 4y ago
Well, LISP too. Define, compose, and apply. Barely above a common language of math and mirroring many languages' parsed AST of equivalent constructs. People enjoy using simple things in a "worse is better"/paradox of choice way. Unfortunately, simple doesn't do threading, exceptions, side-effects, or C library linkage. Simple doesn't scale when you need a deploy button, a backup and restore button, firewall rules API, monitoring logic, or a scale-to-5000-stateless-nodes-behind-a-proxy supervisory service.

sparist 4y ago

Original author here. Didn’t expect my little hobby project to land on the front page of Hacker News. In the midst of a complete rewrite of the language which I unfortunately only get to nibble at here and there; will hopefully publish it soon.

myco_logic 4y ago
As a concatenative language lover/designer I just thought I'd put it out there how much of an inspiration Om has been to me, I absolutely adore your language! Om is one of the most beautiful programming languages I've ever seen, and surely one of the most unique too. Most other concatenative languages are Joy/Factor-esque stack languages, so to see an entirely different vision with your prefix notation is an absolute delight . Your panmorphic type system is also genius (the only other language I know of that has something similar is TCL). The way you treat whitespace separators in your syntax is also very clever, I love that it basically enables one to encode strings without a dedicated literal syntax element. Anyway, I just wanted to let you know how much I appreciate your design and implementation efforts. I hope your rewrite is going well, and I look very much forward to its eventual release...
unsafecast 4y ago
I'm glad to know you're still working on it! I thought the current Om was a finished experiment. By the way, your language has been a big inspiration for my own designs. Thanks!

asdfasdfasdfggg 4y ago

If hating on Lisp’s parentheses in your spare time is not providing enough joy for you, I present to you Om {with which you can complain about too many curlies}.

heynowheynow 4y ago

Perhaps I missed it, but I was hoping for currying and application.

mncharity 4y ago

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.

culi 4y ago

Surprised it doesn't show up on PLDB: https://pldb.com/index.html https://pldb.com/index.html

culi 4y ago
Edit: added it myself