10 ms·

Conjecture, both patterns you outline are the same phenomena, and stem from Pascal being a wonderful Algol canvas to create new languages from. That Pascal was

Conjecture, both patterns you outline are the same phenomena, and stem from Pascal being a wonderful Algol canvas to create new languages from. That Pascal was the LLVM of its day but with an added benefit that because of its simplicity, it could spread as a pure idea, being able to implement from a single mind, means that it would be used as the basis for language and system design. The only way it could be more useful is if Wirth had spec'd a stable s-expr syntax as well.

vidarh 6y ago
It was too early for that at the time, unfortunately. p-code was an attempt at making it machine independent (but maybe a serialisation / s-expression would have done better), but the performance loss was too great for it to get wide traction. Interestingly, one of Wirth's PhD students, Michael Franz, wrote his dissertation on Semantic Dictionary Encoding, a method that was reminiscent of lempel-ziv encoding an intermediate representation in a way that let the de-compressor / code-generator re-use templated generated code. Unfortunately at that point Java was underway (Franz thesis was published in '94) and Franz moved on to work on various code generation and verification for Java [I think, I haven't followed his newer work that closely] But it doesn't end there. One of Franz' PhD students at UC Irvine was Andreas Gal, who did his thesis on tracing just-in-time compilation and went on to do TraceMonkey, and became CTO of Mozilla. [I still think there's interesting stuff to be done with Franz' SDE work; I've periodically looked at it ever since I read it first time in '94, but have never had the time to devote to it, and keep hoping someone else will revisit it]
- sitkack 6y ago
  I was speaking metaphorically of Pascal being the LLVM of its day, more that it was a known base, portable, easy to explain and the first tool someone would reach for. Templated IR code that has been LZ compressed sounds excellent, Thumb++ or uop buffer engine. It sounds like from the post below, that the instructions could even be pathologically the uop or VLIW instruction form and the SDE will effectively discover the compact CISC for your specific workload. Why not push the decode engine into the instruction decoder? I found this awesome post that covers SDE, http://hokstad.com/semantic-dictionary-encoding http://hokstad.com/semantic-dictionary-encoding I think one way to explore this would be to implement compressed binary loaders, like done for demos etc, but target wasm, wrap it in a decompressor and have the wasm program decompress itself as it executed perhaps on a method by method basis.
  - vidarh 6y ago
    > I was speaking metaphorically of Pascal being the LLVM of its day, more that it was a known base, portable, easy to explain and the first tool someone would reach for. Yeah, I got that. My point was that they did actually try to take the next step as well, but it was too early for that part. > I found this awesome post that covers SDE, http://hokstad.com/semantic-dictionary-encoding http://hokstad.com/semantic-dictionary-encoding That's mine, in fact :) SDE doesn't necessarily "discover" an instruction-set per se, but certainly, the templates the decoder would put into the dictionary effectively does recover a lot of structure, and you'd be able to do simple stats and dependency analysis to identify constructs that could be turned into dedicated instructions, certainly. I also think e.g. Gal's work on tracing has a lot of potential to be combined with this to be used as a profiling/feedback stage to allow the decoder to make better code generation choices over time if you maintain enough information to map optimised traced sequences back to the template fragments they came from. > I think one way to explore this would be to implement compressed binary loaders, like done for demos etc, but target wasm, wrap it in a decompressor and have the wasm program decompress itself as it executed perhaps on a method by method basis. That's an interesting idea. It would save having to build the final native instruction emission stage while testing. In fact, it'd be possible to build tools that simply demonstrates round-tripping the s-expression syntax as a proof-of-concept.
    - sitkack 6y ago
      So glad I met you, :) > decoder to make better code generation choices Understand what you are saying, but there are lots of layers between the decoder and code generation and resulting uops. But if we are sending a compressed instruction stream, why not go up a level of abstraction send the IR, MIR, HLIR, s-expression, then s-expression with types, effects. Ok I am just gonna send the latex of the paper. ;) speaking of round tripping the s-expr syntax https://www.reddit.com/r/WebAssembly/comments/lil841/very_fast_compressiondecompression_with_lz4wasm/ https://www.reddit.com/r/WebAssembly/comments/lil841/very_fa...

vidarh 6y ago

It was too early for that at the time, unfortunately. p-code was an attempt at making it machine independent (but maybe a serialisation / s-expression would have done better), but the performance loss was too great for it to get wide traction. Interestingly, one of Wirth's PhD students, Michael Franz, wrote his dissertation on Semantic Dictionary Encoding, a method that was reminiscent of lempel-ziv encoding an intermediate representation in a way that let the de-compressor / code-generator re-use templated generated code. Unfortunately at that point Java was underway (Franz thesis was published in '94) and Franz moved on to work on various code generation and verification for Java [I think, I haven't followed his newer work that closely] But it doesn't end there. One of Franz' PhD students at UC Irvine was Andreas Gal, who did his thesis on tracing just-in-time compilation and went on to do TraceMonkey, and became CTO of Mozilla. [I still think there's interesting stuff to be done with Franz' SDE work; I've periodically looked at it ever since I read it first time in '94, but have never had the time to devote to it, and keep hoping someone else will revisit it]

sitkack 6y ago
I was speaking metaphorically of Pascal being the LLVM of its day, more that it was a known base, portable, easy to explain and the first tool someone would reach for. Templated IR code that has been LZ compressed sounds excellent, Thumb++ or uop buffer engine. It sounds like from the post below, that the instructions could even be pathologically the uop or VLIW instruction form and the SDE will effectively discover the compact CISC for your specific workload. Why not push the decode engine into the instruction decoder? I found this awesome post that covers SDE, http://hokstad.com/semantic-dictionary-encoding http://hokstad.com/semantic-dictionary-encoding I think one way to explore this would be to implement compressed binary loaders, like done for demos etc, but target wasm, wrap it in a decompressor and have the wasm program decompress itself as it executed perhaps on a method by method basis.
- vidarh 6y ago
  > I was speaking metaphorically of Pascal being the LLVM of its day, more that it was a known base, portable, easy to explain and the first tool someone would reach for. Yeah, I got that. My point was that they did actually try to take the next step as well, but it was too early for that part. > I found this awesome post that covers SDE, http://hokstad.com/semantic-dictionary-encoding http://hokstad.com/semantic-dictionary-encoding That's mine, in fact :) SDE doesn't necessarily "discover" an instruction-set per se, but certainly, the templates the decoder would put into the dictionary effectively does recover a lot of structure, and you'd be able to do simple stats and dependency analysis to identify constructs that could be turned into dedicated instructions, certainly. I also think e.g. Gal's work on tracing has a lot of potential to be combined with this to be used as a profiling/feedback stage to allow the decoder to make better code generation choices over time if you maintain enough information to map optimised traced sequences back to the template fragments they came from. > I think one way to explore this would be to implement compressed binary loaders, like done for demos etc, but target wasm, wrap it in a decompressor and have the wasm program decompress itself as it executed perhaps on a method by method basis. That's an interesting idea. It would save having to build the final native instruction emission stage while testing. In fact, it'd be possible to build tools that simply demonstrates round-tripping the s-expression syntax as a proof-of-concept.
  - sitkack 6y ago
    So glad I met you, :) > decoder to make better code generation choices Understand what you are saying, but there are lots of layers between the decoder and code generation and resulting uops. But if we are sending a compressed instruction stream, why not go up a level of abstraction send the IR, MIR, HLIR, s-expression, then s-expression with types, effects. Ok I am just gonna send the latex of the paper. ;) speaking of round tripping the s-expr syntax https://www.reddit.com/r/WebAssembly/comments/lil841/very_fast_compressiondecompression_with_lz4wasm/ https://www.reddit.com/r/WebAssembly/comments/lil841/very_fa...