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!