14 votes

Programming Languages that are Both Interpretable and Compilable?

Posted by shx (edited )
Tags: programming languages

I've been thinking about the feasibility of defining a language spec that can both be compiled and interpreted lately. I first thought about it while writing code in crystal, which, for the unfamiliar, is a compiled language based heavily off the syntax of an interpreted language (ruby).

Here are a couple reasons I find the idea interesting:

  • It effectively neuters the interpreted/compiled language debates. Why just choose one, when both have such big upsides?
  • You could develop a program in the interpreter with the same playfulness as you get in a shell, and then compile it into a speedy 'lil thing!
  • It would be wonderful for metaprogramming! From my experience, languages usually define a little janked together syntax for compile-time execution. If the language had an interpreter for itself within the compiler, you could metaprogram and program in the exact same language.

I'm curious if any languages like this exist, or if you can think of more benefits.

Edit:
I just want to mention that my reference to 'feasibility' earlier is not born of disbelief - you can write a compiler or interpreter for any (to the best of my knowledge!) well defined formal grammar with enough effort. I suppose I left that word there to account for the fact that I might have unknown unknowns here.

25 comments

  1. [4]
    skybrian
    Link
    Many, perhaps most languages are partially compiled and partly interpreted. That is, there is both a compile-time transformation to a more convenient format for runtime, and there is a library...

    Many, perhaps most languages are partially compiled and partly interpreted. That is, there is both a compile-time transformation to a more convenient format for runtime, and there is a library that helps implement runtime behavior. (Even when compiling to machine code, it's possible to run the code on an emulator.)

    It might be better to think about it this way: which runtimes you want to support? What executable formats do you want your compiler to generate?

    To get the feel of an interpreter, you would want a fast enough compiler and to entirely hide the executable file from the user. Many interpreters have a read-eval-print loop, which would mean having an ability to modify the program in place. But many "compiled" languages support similar functionality using a debugger and hot-reload functionality. Alternately, a notebook-style interface is nice to have. Even for languages that don't really support in-place modification like Go, you can get pretty far with a fast compiler and a web interface that lets you compile and run a program by pressing a button.

    Personally, I think targeting Web Assembly would be fun and convenient. The repl.it project has some interesting infrastructure.

    Making a new language is a huge project; I've started many but never finished any to the point where they're useful.

    7 votes
    1. [3]
      shx
      Link Parent
      I appreciate all the detail you put in there - thanks so much! I'll revise my post though, as I'm not personally planning to create any languages. I have enough half baked projects to work through...

      I appreciate all the detail you put in there - thanks so much! I'll revise my post though, as I'm not personally planning to create any languages. I have enough half baked projects to work through as it is, haha.

      When you refer about many languages being compiled then interpreted - are you referring to something like the jvm/bytecode? If not, I'm not familiar with what you're describing!

      Once again, thanks a ton.

      3 votes
      1. skybrian
        Link Parent
        Bytecode is one example, but even with a tree-based interpreter, you could sort of think of the parser that builds the tree as a compiler.

        Bytecode is one example, but even with a tree-based interpreter, you could sort of think of the parser that builds the tree as a compiler.

        3 votes
      2. teaearlgraycold
        Link Parent
        I built a small toy just-in-time compiler that I can use as an example here. There are a few levels of the language in the compiler: Source Code: ++++++++++[>+++++++>++++++++++>+++>+<<<...

        I built a small toy just-in-time compiler that I can use as an example here.

        There are a few levels of the language in the compiler:

        1. Source Code:
        ++++++++++[>+++++++>++++++++++>+++>+<<<
<-]>++.>+.+++++++..+++.>++.<<++++++++++
+++++.>.+++.------.--------.>+.>.
        1. AST:
        /// BrainFuck AST node
pub enum ASTNode {
    /// Add to the current memory cell.
    Incr(u8),
    /// Remove from the current memory cell.
    Decr(u8),
    /// Shift the data pointer to the right.
    Next(usize),
    /// Shift the data pointer to the left.
    Prev(usize),
    /// Display the current memory cell as an ASCII character.
    Print,
    /// Read one character from stdin.
    Read,
    /// Loop over the contained instructions while the current memory cell is
    /// not zero.
    Loop(VecDeque<ASTNode>),
}

/// Container for a vector of ASTNodes.
pub struct AST {
    data: VecDeque<ASTNode>,
}
        1. Intermediate Language:

        This is what is either interpreted or compiled to x86-64

        /// BrainFuck instruction
pub enum Instr {
    /// Add to the current memory cell.
    Incr(u8),
    /// Remove from the current memory cell.
    Decr(u8),
    /// Shift the data pointer to the right.
    Next(usize),
    /// Shift the data pointer to the left.
    Prev(usize),
    /// Display the current memory cell as an ASCII character.
    Print,
    /// Read one character from stdin.
    Read,
    /// If the current memory cell is 0, jump forward by the contained offset.
    BeginLoop(usize),
    /// If the current memory cell is not 0, jump backward by the contained offset.
    EndLoop(usize),
}

pub struct Program {
    pub data: Vec<Instr>,
}
        1. x86-64

        Just a bunch of bytes.

        I believe the best definition of "compiling" is just translating from one language to another. In that sense, each transition in this chain is a compilation. The compiled intermediate language can subsequently be interpreted.

        The grammar of BrainFuck is very simple, so there isn't much difference between the ASTNode and the Instr structs. The only consequential difference is that all loops jumps are pre-calculated. Instead of keeping loops as VecDeques the beginning of a loop is a marker and offset to the end of the loop, and the end of a loop just points back to the beginning.

        This makes interpreting and compiling the intermediate language much easier. The interpreter doesn't need to keep track of a stack and the x86-64 translation just needs to inline the offsets into the jump instructions:

        // Jump to the end of the loop if equal.
// je    offset
bytes.push(0x0f);
bytes.push(0x84);
bytes.push(offset_bytes[0]);
bytes.push(offset_bytes[1]);
bytes.push(offset_bytes[2]);
bytes.push(offset_bytes[3]);
        2 votes
  2. [4]
    pvik
    Link
    I would suggest you take a peek into Common Lisp[1]. Most modern languages now-a-days have a REPL, however very few come close to the level of interactive development that CommonLisp allows....

    I would suggest you take a peek into Common Lisp[1].

    Most modern languages now-a-days have a REPL, however very few come close to the level of interactive development that CommonLisp allows.

    Common lisp also allows you to compile your code into a fasl binary format. (Some other fun stuff afforded by CommonLisp: If you have been working in a repl, you can even generate a fasl image of your REPL state, including all the defined variables, functions, packages, etc)

    Also, Crafting Interpreters is a great book if you want to learn the nitty-gritties of compilers/interpreters :)

    6 votes
    1. [2]
      skybrian
      (edited )
      Link Parent
      I'll add that Racket is a Lisp that's designed to make implementing new languages easy. Since I'm not a Lisp programmer, I haven't tried it myself, but I thought the Turnstile language was pretty...

      I'll add that Racket is a Lisp that's designed to make implementing new languages easy. Since I'm not a Lisp programmer, I haven't tried it myself, but I thought the Turnstile language was pretty cool since it lets you implement a static type system using macros.

      5 votes
      1. pvik
        Link Parent
        Of course! Scheme/Racket is great too. Racket has also gotten a lot faster recently with moving to a chez-scheme base! I hadn't heard of turnstile before, I will have to check it out! Shen is...

        Of course! Scheme/Racket is great too. Racket has also gotten a lot faster recently with moving to a chez-scheme base!

        I hadn't heard of turnstile before, I will have to check it out!

        Shen is another lisp that tries to tackle strong typing in a lisp environment.

        3 votes
    2. shx
      Link Parent
      Ooh, good point! I'm a mathematician at heart, so FP has always been alluring. I looked into fasl some more - seems that some implementations do indeed run it on bare metal, which is much better...

      Ooh, good point! I'm a mathematician at heart, so FP has always been alluring. I looked into fasl some more - seems that some implementations do indeed run it on bare metal, which is much better than the bytecode I was expecting.

      And thank you for the book suggestion - I suppose my question was misleading, because I don't intend to actually make this language, I was just wondering what the state of the art was (if any). Nonetheless, I've been learning more about formal grammars in my free time, and that looks like a lovely read.

      3 votes
  3. [2]
    joplin
    Link
    Swift has this ability. It ships with a REPL, and also has the advantage of being able to call into Cocoa (at least on macOS) for doing things like creating windows, alerts, etc.

    Swift has this ability. It ships with a REPL, and also has the advantage of being able to call into Cocoa (at least on macOS) for doing things like creating windows, alerts, etc.

    5 votes
    1. shx
      Link Parent
      Huh! I didn't know that. Swift is interesting, but I haven't given it much attention in the past. Thank you for sharing :)

      Huh! I didn't know that. Swift is interesting, but I haven't given it much attention in the past. Thank you for sharing :)

      2 votes
  4. [5]
    Staross
    (edited )
    Link
    Julia is compiled and people have written a interpreter for it (for debugging). That said Julia already has all the advantages you cite without the interpreter, because it's compiled just-in-time....

    Julia is compiled and people have written a interpreter for it (for debugging). That said Julia already has all the advantages you cite without the interpreter, because it's compiled just-in-time. When you first run a function in the REPL you can see it takes a bit of time because it gets compiled to machine code, while the subsequent calls are super fast.

    It's also great to play with and understand the different compilation stages, because you can interact and explore them in real time. Since it uses LLVM, there's even a C++ REPL.

    4 votes
    1. [4]
      entangledamplitude
      Link Parent
      Julia really hits a sweet spot! It also has nice meta programming affordances (being structurally very lisp like, and friendly to a functional style). Not to mention, clean Julia code compiles to...

      Julia really hits a sweet spot! It also has nice meta programming affordances (being structurally very lisp like, and friendly to a functional style). Not to mention, clean Julia code compiles to something that runs really fast.

      3 votes
      1. [3]
        Staross
        Link Parent
        I'm quite the Julia fanboy, I'm lucky that actually use it at work since a few years, I think I would have quit my job otherwise.

        I'm quite the Julia fanboy, I'm lucky that actually use it at work since a few years, I think I would have quit my job otherwise.

        2 votes
        1. [2]
          entangledamplitude
          Link Parent
          I’m very curious... what kind of stuff do you do, that you’ve been using Julia for the last few years? I had the good fortune to work with it for a few months (academic project), but these days...

          I’m very curious... what kind of stuff do you do, that you’ve been using Julia for the last few years? I had the good fortune to work with it for a few months (academic project), but these days I’m coding in Python and constantly wistful about Julia.

          1 vote
          1. Staross
            Link Parent
            R&D in bioinformatics. When I started working the company was coming out of the startup phase and was complete chaos, so I was able to do more or less what I wanted. So it became a thing that I'm...

            R&D in bioinformatics. When I started working the company was coming out of the startup phase and was complete chaos, so I was able to do more or less what I wanted. So it became a thing that I'm using Julia just because I did. It's also pretty clear that I'm able to do things that other people can't, so there hasn't been too many complains about it.

            1 vote
  5. [2]
    moriarty
    Link
    CERN had long ago written a C++ interpreter: CINT, later switched to Cling, which is used quite extensively in physics analyses in ROOT. Back when I used it, it had some hiccups, but I imagine...

    CERN had long ago written a C++ interpreter: CINT, later switched to Cling, which is used quite extensively in physics analyses in ROOT. Back when I used it, it had some hiccups, but I imagine it's in a much better state now.

    2 votes
    1. shx
      Link Parent
      Very cool! That's something I definitely hadn't heard about.

      Very cool! That's something I definitely hadn't heard about.

  6. [2]
    archevel
    (edited )
    Link
    I think you are mistaken in thinking that there is anything preventing this in existing languages. You can write a interpreter for C and you can make a compiler that takes Python or lisp as input...

    I think you are mistaken in thinking that there is anything preventing this in existing languages. You can write a interpreter for C and you can make a compiler that takes Python or lisp as input and outputs machine code. The hard part would be to a) keep it consistent with the regular behavior and b) making it performant (in case of compiling an interpreted language).

    The reason for this being true basically boils down to Turing completeness of languages. If I recall correctly there is a section about compiling a lisp in Structure and Interpretation of Computer Programs

    1 vote
    1. shx
      Link Parent
      Ah, I think the mistake is in my original post, rather than my understanding. Whoops - I guess I phrased things a little too fast and loose in my excitement. The reason I mentioned feasibility is...

      Ah, I think the mistake is in my original post, rather than my understanding. Whoops - I guess I phrased things a little too fast and loose in my excitement. The reason I mentioned feasibility is that I had a hunch this sort of project would be impractical to develop, due to what you mentioned - two massive codebases trying to adhere to a singular evolving standard! Haha, open source has enough problems as it is, even without a project that.. Demanding?

      Thanks for the link and the reply! I'll definitely check that out. (And I'll add a disclaimer to my original post tor reflect what I mentioned)

      2 votes
  7. Moonchild
    (edited )
    Link
    I answered a similar question on reddit a couple of months ago; I'll just quote part of that: Note, however, that there are still gradations of work done at compile-time vs run-time, and those are...

    I answered a similar question on reddit a couple of months ago; I'll just quote part of that:

    The distinction between 'interpreter' and 'compiler' is not well-defined. Can I call python a compiled language if, given a python file as input, I produce a file which is equivalent to a regular python binary, except that it's hardcoded to just run the python file I inputted? On the other hand, many programming languages that are 'obviously' statically compiled (go, c++, ...) have runtime reflection systems or runtime libraries that are always linked in. D can be effectively duck typed with jsvar. To drive this point home, consider: I can use sbcl to make a fully standalone native binary from lisp source. It doesn't call into the lisp interpreter at all, it's pure freestanding code, and you can even use it to make operating systems. But inside of this binary, you can call eval and dynamically construct new code.

    Note, however, that there are still gradations of work done at compile-time vs run-time, and those are still interesting to consider. For more on that, see this blog post. That is more relevant to your question, because it points out that how meaningful 'compilation' is depends on what language you're compiling.

    The main conflict seems to be between iteration speed (on the side of interpretation) and runtime speed (on the side of compilation), but I disagree with both of those. TCC can compile c stupidly fast, and go and d aren't far behind. Notably, those compilers are fast enough that you can meaningfully build a REPL on top of them. Meanwhile k (and k) is one of the fastest programming languages around, usually faster than c, and it's interpreted. Hotspot (the main java virtual machine) can be started with a -client or -server flag; those flags trade off startup time (and memory usage) with runtime performance. Without changing the type of implementation.

    1 vote
  8. 666
    Link
    Haskell, you generally compile it but it also comes with an interpreter + REPL called GHCi. Java (no, I'm not kidding), modern Java comes with JShell.

    Haskell, you generally compile it but it also comes with an interpreter + REPL called GHCi.

    Java (no, I'm not kidding), modern Java comes with JShell.

    1 vote
  9. [4]
    SkewedSideburn
    Link
    Do people actually do that? Honest question, I just hate using Python shell, it's so clumsy

    You could develop a program in the interpreter with the same playfulness as you get in a shell

    Do people actually do that? Honest question, I just hate using Python shell, it's so clumsy

    1. shx
      Link Parent
      I was referring to a unix shell - A habit of mine is to open an editor and terminal side by side, and write shell script in the editor while testing and prototyping each command in the adjacent...

      I was referring to a unix shell - A habit of mine is to open an editor and terminal side by side, and write shell script in the editor while testing and prototyping each command in the adjacent terminal.

      But haha, I totally agree. Writing programs in interpreters, like python, or even the browser js console, is a nightmare.

      1 vote
    2. [3]
      Comment deleted by author
      Link Parent
      1. ClearlyAlive
        Link Parent
        Why is SBCL “clumsy”? Is it due to the lack of built in in readline? I think most people use SBCL or another lisp through SLIME or SLY so don’t really need to worry about the lack of readline as...

        Why is SBCL “clumsy”? Is it due to the lack of built in in readline?

        I think most people use SBCL or another lisp through SLIME or SLY so don’t really need to worry about the lack of readline as SLIME offers it.

        1 vote
      2. pvik
        (edited )
        Link Parent
        I don't think anyone glorifies the sbcl shell itself. What people glorify is the interactive development capabilities that CommonLisp offer (and I think rightfully so), as /u/ClearlyAlive pointed...

        and people glorify that

        I don't think anyone glorifies the sbcl shell itself. What people glorify is the interactive development capabilities that CommonLisp offer (and I think rightfully so), as /u/ClearlyAlive pointed out, most often through something like SLIME or SLY.

        Even by adding readline (rlwrap sbcl), the debug capabilities and level of interactivity you get from a plain sbcl shell is far better that anything most modern languages offer. This is primarily because how CommonLisp was designed. Interactive development was not an after thought (as is with a lot of languages, which tack on a REPL), it is part of the philosophy of the language itself.
        Granted the learning curve for CommonLisp may be a little steeper, than say python and you may be put off by the parens, that is totally fine. However if you are going to compare it to something, I would suggest you give it a fair shot!

        Also, are you trying to compare the interactive development experience of CommonLisp (sbcl) with Python?