Can a solidity compiler be written in solidity? How much gas would it cost?
Since the EVM instruction set is Turing-complete, any conceivable program (computable function) can be implemented in the EVM instruction set itself and thus also in Solidity. Because of the current gas model, this might be really expensive, though. With progress in interpreters and a potential change in and of the EVM, the block gas limit (essential upper limit of how much can be done synchronously in a transaction) should increase in the future, but it might be still out of reach.
The question is: Why would someone write a Solidity compiler in Solidity?
Many compilers are self-hosted which means that they can compile themselves or a newer version of themselves. This is especially beneficial for general-purpose languages, because it removes an external dependency on another language and it also helps designing the language if you write a large project like a compiler in the language itself.
For special-purpose languages like Solidity, the above arguments are not too relevant, though. What is important for Solidity, is that the compilation can be either run on chain or at least verified on chain. This does not necessarily require the compiler to be written in Solidity. The advantage of verifying the compilation on the blockchain would be that source verification (checking that a given contract on the blockchain has a certain source code) does not have to be repeated by every user and you can just trust the blockchain to do it.
The latter is actually planned and can be done using interactive verification. The key idea there is that during the compilation, a transcript of the compilation run is generated and published (on e.g. swarm). Put simply, the transcript starts with the source code, has a lot of data in between and ends with the bytecode. If it is incorrect, you can point at a specific position inside the transcript and check that there was a mistake by just comparing some bytes. If nobody finds a mistake after some time, the system accepts the compilation as correct. The load (gas costs) of the blockchain is negligible in this mode of operation.
EVM is a practically infinite capacity universal computer model so I'm pretty sure it is possible. Btw an EVM interpreter and a Solidity compiler are two completely different questions but both should be possible. No idea about the gas cost though, probably a lot :) If you actually need this on the blockchain, you should make it possible to do the calculations in multiple transactions so that the block gas limit doesn't limit you.
Yes. Solidity is turing-complete, which means that, according to the Church-turing thesis, it is capable of computing every algorithm. Since a Solidity compiler is just an algorithm, Solidity is capable of compiling itself. In fact, it isn't even a hard problem - in order to write such a thing, you could just port the existing compilers to the Solidity syntax. The process of writing a compiler in the programming language that it compiles is a well known technique called bootstrapping.
So compilation is converting strings (the solidity code, that people can read) to bytecode (that computer can run). That is just a series of if statements. Which can be implemented in any Turing complete language. But in running this on the block chain would likely be prohibitively expensive.
If you look here you can see ChrisETH discuss a contract simulator written in solidity.
In theory, yes, though it would need to run on a private chain with a huge gas-limit, and for any practical purpose, you wouldn't actually want to do it.
See Vitalik's On Abstraction, though. With EVM 2.0 and WebAssembly we should be able to start moving some elements from the EVM up into smart contracts.
With suitable levels of sharding, the huge performance gap between local execution and blockchain execution of code should start to close. But obviously you're always going to have overhead such that you are going to want a very good reason to run code on the blockchain rather than locally.
Another difference is that running on the blockchain means you don't have conventional input/output or filesystem, which makes things like compilers a bit awkward.
But overall ... Turing-complete (caveat gas-limits), so YES!
Everyone is gonna say "theoretically, yes" – but for practical purposes the answer is a solid "no". It's a cool idea in theory, because (in theory) it would work, but it would be very expensive, and there's literally nothing to gain from doing it.
I think it sort of misunderstands what "programming on the blockchain" really is about.
Blockchain shines when it comes to transparency and keeping permanent records of things, there's no reason the entire blockchain (everyone mining ether) needs to compile your code, not to mention permanently save it. I don't need to trust anybody to do that! I just download the source code and compile it myself. I can completely trust my computer to compile source code correctly. Not to mention what if your source code doesn't compile correctly... oh man! Everyone has to run the whole thing again and store it all again.
What solidity is useful for is "contracts" – these might look more like an auction, gambling, voting, even something like a will. These are usually relatively simple "calculations", so while you might not trust someone else's computer to tally up your votes in an election, but you can trust the blockchain to do it!