3 ms·

Is there such a thing as a language that compiles to a value rather than an executable program? I've done a really hacky version of something this where a user

Is there such a thing as a language that compiles to a value rather than an executable program? I've done a really hacky version of something this where a user would input a succinct, high-level description of a sequence of colored lighting, and my program would parse* that and build the tedious, low-level JSON representation of that sequence for yet another program to perform. Is there a fancy or unfancy name for that? *Ok really it was a little bit of munging and then eval.

nostrademons 10y ago
Well, at some level every language compiles to a value rather than an executable program - the parse tree of a source module is a data structure describing the program, and the executable is a sequence of bytes that is interpreted by the processor. There's a continuum between this and what we think of as a "value" in programming terms (eg. an int or a string), but the boundary is fuzzy. It was pretty common at Google to write DSLs that compiled to a protobuf that'd be loaded into the server as configuration, for example. CUDA compiles programs into a buffer that is then sent to the GPU. HTML compiles into the DOM, which is a value that can be manipulated with Javascript.
khedoros 10y ago
Consider a run-length encoded image. One possible implementation is to have a command, a length value, then a sequence of 1 or more pixels. A "run" command's sequence would just be the color to repeat, while a "dump" command's sequence would be a number of pixels to output directly into the image. In a sense, that's a piece of source code that would "compile" into an image, if you take a loose interpretation of what it means to "compile". For other examples that may count, LaTeX and Postscript are both Turing-complete languages, usually compiled into a typeset document and a vector graphic image, respectively. You might call them Domain-Specific Languages, in general (the DSL mentioned by the sibling comment).
tikhonj 10y ago
Sure. I would describe that as a domain-specific language (DSL), although not all domain-specific languages look like that. DSLs that don't encode any computation are sometimes described as "configuration" languages, but I'm not sure that term is particularly well-defined. Domain-specific languages are one of the most powerful yet underused techniques in programming—especially if the language can be embedded inside a rich, general-purpose language. We get to bear all the abstractive capability of language at our domain while also having general programming language techniques at our disposal (static analysis, optimization, type checking... etc). If we're really doing a good job we can even make sure our DSL is easy to reason about and has good semantics, using the theoretical tools developed to analyze general-purpose programs. One neat trick is that a lot of tools that are difficult to use on general-purpose languages like automatic verification or program synthesis can become far easier to apply and more practical when working with a small DSL. A lot of tools in this vein would be a multi-year research project to implement for a language like C but only a multi-week project for sufficiently constrained, well-behaved DSLs. And if you're designing your DSL, you can design it in tandem with this tooling, making the problem even more tractable.
happyslobro 10y ago
Macros in C, and template metaprogramming in C++? Some crazy people are writing their software entirely as C++ metaprograms and using the compiler to execute it. Presumably, the compiler's output is a very short `main` function that just prints the constant value that the compiler calculated. There was an example of this on HN a while ago, where a guy wrote a Game of Life implementation entirely with C++ templates (https://news.ycombinator.com/item?id=8597443 https://news.ycombinator.com/item?id=8597443). Successive generations were nested templates. Compile times became prohibitive after a few generations. The whole thing started to read sort of like Haskell.
chriswarbo 10y ago
The language in the article is just such a thing! The difference is essentially between statements (AKA instructions) and expressions (AKA values). Statements are executed one after another to produce effects(/actions). That is "imperative" programming. In contrast, expressions represent values, and we evaluate(/reduce/simplify) them over and over. Sometimes they reach a "normal form" (i.e. a "final result"), other times they may end up in a loop. This may be called "value-oriented programming", and pure functional programming is one example. The language in the article is similarly "value-oriented", although it isn't "pure" since it allows effects in its expressions, which requires careful choice of which order to evaluate things in. In Haskell, for example, "programs" are just expressions representing some sort of value. It just-so-happens that when a Haskell program is 'executed', what actually happens is we look for a value called "main", we evaluate it to get a value, and that value just-so-happens to have the type "imperative program" (technically it's called "IO a"). That "imperative program" value is then handed over to an interpreter to be executed. Well, conceptually at least; those tasks are actually interleaved so the code is executed "on demand", and the whole thing can get smushed together by an aggressive compiler. Still, it sounds very much like your two-stage language.

nostrademons 10y ago

Well, at some level every language compiles to a value rather than an executable program - the parse tree of a source module is a data structure describing the program, and the executable is a sequence of bytes that is interpreted by the processor. There's a continuum between this and what we think of as a "value" in programming terms (eg. an int or a string), but the boundary is fuzzy. It was pretty common at Google to write DSLs that compiled to a protobuf that'd be loaded into the server as configuration, for example. CUDA compiles programs into a buffer that is then sent to the GPU. HTML compiles into the DOM, which is a value that can be manipulated with Javascript.

khedoros 10y ago

Consider a run-length encoded image. One possible implementation is to have a command, a length value, then a sequence of 1 or more pixels. A "run" command's sequence would just be the color to repeat, while a "dump" command's sequence would be a number of pixels to output directly into the image. In a sense, that's a piece of source code that would "compile" into an image, if you take a loose interpretation of what it means to "compile". For other examples that may count, LaTeX and Postscript are both Turing-complete languages, usually compiled into a typeset document and a vector graphic image, respectively. You might call them Domain-Specific Languages, in general (the DSL mentioned by the sibling comment).

tikhonj 10y ago

Sure. I would describe that as a domain-specific language (DSL), although not all domain-specific languages look like that. DSLs that don't encode any computation are sometimes described as "configuration" languages, but I'm not sure that term is particularly well-defined. Domain-specific languages are one of the most powerful yet underused techniques in programming—especially if the language can be embedded inside a rich, general-purpose language. We get to bear all the abstractive capability of language at our domain while also having general programming language techniques at our disposal (static analysis, optimization, type checking... etc). If we're really doing a good job we can even make sure our DSL is easy to reason about and has good semantics, using the theoretical tools developed to analyze general-purpose programs. One neat trick is that a lot of tools that are difficult to use on general-purpose languages like automatic verification or program synthesis can become far easier to apply and more practical when working with a small DSL. A lot of tools in this vein would be a multi-year research project to implement for a language like C but only a multi-week project for sufficiently constrained, well-behaved DSLs. And if you're designing your DSL, you can design it in tandem with this tooling, making the problem even more tractable.

happyslobro 10y ago

Macros in C, and template metaprogramming in C++? Some crazy people are writing their software entirely as C++ metaprograms and using the compiler to execute it. Presumably, the compiler's output is a very short `main` function that just prints the constant value that the compiler calculated. There was an example of this on HN a while ago, where a guy wrote a Game of Life implementation entirely with C++ templates (https://news.ycombinator.com/item?id=8597443 https://news.ycombinator.com/item?id=8597443). Successive generations were nested templates. Compile times became prohibitive after a few generations. The whole thing started to read sort of like Haskell.

chriswarbo 10y ago

The language in the article is just such a thing! The difference is essentially between statements (AKA instructions) and expressions (AKA values). Statements are executed one after another to produce effects(/actions). That is "imperative" programming. In contrast, expressions represent values, and we evaluate(/reduce/simplify) them over and over. Sometimes they reach a "normal form" (i.e. a "final result"), other times they may end up in a loop. This may be called "value-oriented programming", and pure functional programming is one example. The language in the article is similarly "value-oriented", although it isn't "pure" since it allows effects in its expressions, which requires careful choice of which order to evaluate things in. In Haskell, for example, "programs" are just expressions representing some sort of value. It just-so-happens that when a Haskell program is 'executed', what actually happens is we look for a value called "main", we evaluate it to get a value, and that value just-so-happens to have the type "imperative program" (technically it's called "IO a"). That "imperative program" value is then handed over to an interpreter to be executed. Well, conceptually at least; those tasks are actually interleaved so the code is executed "on demand", and the whole thing can get smushed together by an aggressive compiler. Still, it sounds very much like your two-stage language.