Skip to content

An experiment of high level code optimization

License

Notifications You must be signed in to change notification settings

xushanthu-2014/SHLL

 
 

Repository files navigation

SHLL: Staged High Level Language

This language explores staging in Rust, but also leave space for transpilation.

It adds high-level generics and codegen to Rust.

See rust-lang/examples/main_02.rs for example.

When it comes to abstraction, even Rust and C++ claim they provide zero-cost abstraction, but they also have their problems.

  • Interpreted languages like Python is slow
  • template in C++ and Rust is fastest, but with weird syntax and incomplete features compared to the language itself
  • Generics(in Java) doesn't provide much runtime performance benefit. Even with help of JIT it's hard to optimize at higher level than method
  • OOP polymorphism involves calling dynamic dispatched methods, which involves a runtime cost
  • codegen requires an external tool, and writing such tool involves much work
  • macros(in Rust/Scala/C) is hard to debug, and limited to decorate a function/struct(or text replacement in C)
  • lisp is powerful in metaprogramming, but it's an interpreter language

The ideal solution is the SHLL language, which specialize code into low level languages:

  • Write declarative/high level code, and then the optimizer will optimize it into imperative code.

To sum up: make the language simple yet expressive, and produces fast low-level code

Syntax

Frontend

Same as rust

Optimization

Then AST gets passed through multiple optimization phrases, while maintaining the same semantics.

Current optimization phrases:

  • Specialization and inlining
  • Flow analysis
  • Dead code elimination

Specialization

  • Constant evaluation Unless the function is too big, inlining does not perform

  • Loop unrolling

  • Zig's comptime, like rust macros but supports comptime inspection and is to replace templates

Flow analysis

Graph-based(and effects and contexts):

  • build a graph of data flow
  • build a graph of control flow
  • Falliblity: The effect of a section of code failing to complete and evaluate to its expected value (in Rust, think Result)
  • Multiplicity: The effect of a section of code being evaluated multiple times, yielding many values or operating over many values (in Rust, think Iterator)
  • Asynchrony: The effect of a section of code yielding control when it cannot immediately progress, to allow other sections of code to progress instead (in Rust, think Future)
  • Pureness: The effect of a function having no side effects
  • Safeness(sorry to toss you in): The effect of a section of code being unsafe, to use unsafe { } to suppress. And many other types of safeness
  • Deprecation
  • Some Rust ideas: Ref, MutRef

Readings https://boats.gitlab.io/blog/post/the-problem-of-effects/ https://internals.rust-lang.org/t/can-we-make-a-rusty-effect-system/11697

Dead code elimination

  • use graph-based data flow to eliminate dead code
  • combine data flow and control flow to eliminate dead code

Backend

Then AST gets transpiled into a low level language, which is either Rust for performance or natively scala. FFI is not an issue as we compile at source code level

The language aims to experiment simple syntax, maximum runtime performance. Compile time is not a concern, as we maintain the same semantics between phrases, some optimization can be disabled for fast compilation, or even use interpretation mode.

References

Struct is (partly) similar to GoLang and Zig Similar to Zig's comptime system, but aims to do more than Zig with less and simpler code. https://kristoff.it/blog/what-is-zig-comptime/

About

An experiment of high level code optimization

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • Rust 99.9%
  • Shell 0.1%