Pages

03 September 2016

Arithmetic Types in Kitten

In order to motivate myself to work on my programming language, Kitten, I’ve decided to publish my notes on various aspects of the design as I figure them out. This is partly to solicit comments and drum up interest in the project, but mostly an exercise in ensuring my ideas are solid enough to explain clearly.

In these articles, “Kitten” will refer to the “ideal” language and the new work-in-progress compiler that approximates it.

Explicitness

In non-generic definitions, it should always be evident from the code what type of data you’re using. As such, the type of integer and floating-point literals can be specified with a type suffix: i8, i16, …, u8, …, f32, f64; the unadorned integer literal 1 is equivalent to 1i32, and the float literal 1.0 is equivalent to 1.0f64. I think signed 32-bit integers and 64-bit floats are reasonable defaults for common use cases.

In the future, we could relax this by allowing the suffix to be inferred, or by allowing the default suffix to be locally changed.

// Currently fails to typecheck; 3 could be deduced to mean 3i64.
(2i64 + 3)

// Currently not valid syntax; 2 and 3 could be defaulted to Int64.
assume (Int64)
(2 + 3)

Uniformity

Because overloading interacts rather poorly with type inference, it would be easiest for me to provide different operators for different types, such as + for integer addition and +. for floating-point addition, as in OCaml. I did this in the old compiler, and it wasn’t great for usability. I solve this through the use of traits—for each operator there is a single generic definition, with instances provided for all the common arithmetic types.

trait + <T> (T, T -> T)

instance + (Int32, Int32 -> Int32):
  _::kitten::add_int32

instance + (Float64, Float64 -> Float64):
  _::kitten::add_float64

Traits work like template specialisations in C++: if + is inferred to have the type Int32, Int32 -> Int32 at a given call site, then the compiler will emit a call to that particular instance; no generic code makes it into the final executable. And if no such instance exists, you’ll get a straightforward compilation error.

These traits will generally need to be inlined for performance reasons. Luckily, Kitten’s metadata system allows us to specify this easily enough:

about +:
  docs: """
    Adds two values of some type, producing a result of the same type.
    """
  inline: always

The about notation is a dumping ground for all metadata: documentation, examples, tests, operator precedence information, and optimization hints. The idea is that it’s better to have all of this information in a single structured format than to use some combination of magical comments, pragmas, attributes, and otherwise special syntax.

Safety

We want arithmetic operations to be safe, meaning that failure modes such as implicit overflow and trapping should be opt-in.

Therefore, we should provide an arbitrary-precision integer type (Int) as a sane default, as well as an array of signed and unsigned fixed-precision integer types in common sizes: Int8, Int16, Int32, Int64, and their UIntN counterparts.

Kitten has a permission system for reasoning about the permitted side effects of functions. Operations on fixed-precision integers (both signed and unsigned) are checked by default, requiring the +Fail permission to allow them to raise assertion failures in case of overflow.

instance + (Int32, Int32 -> Int32 +Fail) { … }

However, if most arithmetic operations can fail, then +Fail will proliferate through all the type signatures of calling code, which is a real drag, and might encourage people to use unchecked types more liberally than they should. We can solve this in two ways:

  • Make +Fail implicit in type signatures, and introduce a notation -Fail for removing it. This speaks to a more general notion of implicit permissions, which I think would be really valuable: it would let us introduce new implicit permissions in a backward-compatible way, allowing new code to opt out. For example, if we implicitly grant +Alloc to all functions, then they’re permitted to allocate memory on the heap—lists, closures, bignums, and so on. But for performance-critical code, you may want a static guarantee that your code performs no heap allocations, so you can opt out by specifying -Alloc.
  • Introduce a wrapper type, Checked<T>, which provides arithmetic operations that don’t require +Fail, but instead return an Optional<T> as the result. This would mean making the signatures of the arithmetic traits more general, or inlining the Optional into the representation of Checked.

Neither is unequivocally better, and they have different use cases, so I think it makes sense to provide both.

Modifiers

In addition to Checked<T>, Kitten provides wrapper types for different arithmetic modes:

  • Wrapped<T> is a T where overflow is defined to wrap modulo the range of T.
  • Unchecked<T> is a T where overflow is implementation-defined. I’m tempted to make this type require the +Unsafe permission, but that’s intended for operations that can violate memory safety, which Unchecked<T> cannot.
  • Saturating<T> is a T where overflow results in clamping to the range of T; this is useful in some signal-processing applications.

Platform Independence

All the basic arithmetic types should be provided on all platforms. That may require emulation in some cases, such as 64-bit arithmetic on a 32-bit processor. Implementations can provide additional platform-specific types such as Int128 or Float80.

SIMD operations are implemented on container-like types such as Vector4<Float32>; naïve-looking code such as:

vec { (* 2) } map

Should be lowered to the single instruction:

addps %xmm0, %xmm0

This is subtle, and I haven’t worked out all the details yet, but SIMD operations are important enough for performance-critical code that it seems worthwhile to consider them early on.

Licensing Problems

For arbitrary-precision types, I’m in a bit of a bind. I’m not equipped to write a native Kitten bignum library with performance on par with GMP, but because GMP is licensed under LGPL, it can’t be used freely. For instance, we can’t statically link it into generated executables, making distribution more difficult and negatively impacting performance.

TL;DR

  • Kitten has all the usual machine integer and float types that systems programmers love.
  • Literal types are explicit, with some sane defaults: signed Int32 and Float64.
  • Overflow is checked by default, with various type-system features for more control.
  • The standard library provides arbitrary-precision and SIMD operations.

36 comments:

  1. I think this is the best article today about the future technology. Thanks for taking your own time to discuss this topic, I feel happy about that curiosity has increased to learn more about this topic

    C and C++ Training Institute in chennai | C and C++ Training Institute in anna nagar | C and C++ Training Institute in omr | C and C++ Training Institute in porur | C and C++ Training Institute in tambaram | C and C++ Training Institute in velachery

    ReplyDelete
  2. I am a new user of this site, so here I saw several articles and posts published on this site, I am more interested in some of them, hope you will provide more information on these topics in your next articles.

    Business Analytics Course in Bangalore

    ReplyDelete
  3. I will very much appreciate the writer's choice for choosing this excellent article suitable for my topic. Here is a detailed description of the topic of the article that helped me the most.

    Data Analytics Course in Bangalore

    ReplyDelete
  4. Thanks, this is generally helpful.
    Still, I followed step-by-step your method in this Python Online Training
    Python Online Course

    ReplyDelete
  5. Attend The Data Analyst Course From ExcelR. Practical Data Analyst Course Sessions With Assured Placement Support From Experienced Faculty. ExcelR Offers The Data Analyst Course.
    Data Analyst Course

    ReplyDelete
  6. wonderful article contains lot of valuable information. Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article.
    This article resolved my all queries.good luck an best wishes to the team members.learn digital marketing use these following link
    Digital Marketing Course in Chennai

    ReplyDelete
  7. Thanks for sharing this in here. You are running a great blog, keep up this good work.
    Online degree courses
    Distance education

    ReplyDelete
  8. I want to leave a little comment to support and wish you the best of luck.we wish you the best of luck in all your blogging enedevors.
    data analytics courses in bangalore

    ReplyDelete
  9. i am glad to discover this page : i have to thank you for the time i spent on this especially great reading !! i really liked each part and also bookmarked you for new information on your site.
    best data science courses in bangalore

    ReplyDelete
  10. I am glad to discover this page. I have to thank you for the time I spent on this especially great reading !! I really liked each part and also bookmarked you for new information on your site.
    Data Science Training in Chennai

    ReplyDelete
  11. I want to leave a little comment to support and wish you the best of luck.we wish you the best of luck in all your blogging enedevors.
    data analytics courses in bangalore

    ReplyDelete
  12. Wonderful blog found to be very impressive to come across such an awesome blog. I should really appreciate the blogger for the efforts they have put in to develop such amazing content for all the curious readers who are very keen on being updated across every corner. Ultimately, this is an awesome experience for the readers. Anyways, thanks a lot and keep sharing the content in the future too.

    Digital Marketing Training in Bangalore

    ReplyDelete
  13. I found Habit to be a transparent site, a social hub that is a conglomerate of buyers and sellers willing to offer digital advice online at a decent cost.

    Artificial Intelligence Training in Bangalore

    ReplyDelete
  14. I really enjoyed reading your blog. It was very well written and easy to understand. Unlike other blogs that I have read which are actually not very good. Thank you so much!

    Data Science Training in Bangalore

    ReplyDelete
  15. The Extraordinary blog went amazed with the content that they have developed in a very descriptive manner. This type of content surely ensures the participants explore themselves. Hope you deliver the same near the future as well. Gratitude to the blogger for the efforts.

    Machine Learning Course in Bangalore

    ReplyDelete
  16. I am glad to discover this page. I have to thank you for the time I spent on this especially great reading !! I really liked each part and also bookmarked you for new information on your site.
    Data Science Course Syllabus

    ReplyDelete
  17. I want to leave a little comment to support and wish you the best of luck.we wish you the best of luck in all your blogging enedevors.
    data science course in jaipur

    ReplyDelete
  18. I am glad to discover this page. I have to thank you for the time I spent on this especially great reading !! I really liked each part and also bookmarked you for new information on your site.
    Data Science Training in Chennai

    ReplyDelete
  19. I want to leave a little comment to support and wish you the best of luck.we wish you the best of luck in all your blogging enedevors.
    data science course

    ReplyDelete
  20. this is really nice to read..informative post is very good to read..thanks a lot!
    data scientist training and placement in hyderabad

    ReplyDelete
  21. A good blog always contains new and exciting information, and reading it I feel like this blog really has all of these qualities that make it a blog.

    Artificial Intelligence Training in Bangalore

    ReplyDelete
  22. It is late to find this act. At least one should be familiar with the fact that such events exist. I agree with your blog and will come back to inspect it further in the future, so keep your performance going.

    Digital Marketing Training in Bangalore

    ReplyDelete
  23. I wanted to leave a little comment to support you and wish you the best of luck. We wish you the best of luck in all of your blogging endeavors.

    Data Science Training in Bangalore

    ReplyDelete
  24. I am more curious to take an interest in some of them. I hope you will provide more information on these topics in your next articles.

    Machine Learning Course in Bangalore

    ReplyDelete
  25. I want to leave a little comment to support and wish you the best of luck.we wish you the best of luck in all your blogging enedevors.
    business analytics courses

    ReplyDelete
  26. I am glad to discover this page. I have to thank you for the time I spent on this especially great reading !! I really liked each part and also bookmarked you for new information on your site.
    Data Science Course in Delhi

    ReplyDelete
  27. The article posted was very informative and useful. You people are doing a great job. Keep going.
    data science training

    ReplyDelete
  28. I am looking for and I love to post a comment that "The content of your post is awesome" Great work!ethical hacking course in patna

    ReplyDelete
  29. i am glad to discover this page : i have to thank you for the time i spent on this especially great reading !! i really liked each part and also bookmarked you for new information on your site.
    data analytics course in patna

    ReplyDelete
  30. I am overwhelmed by your post with such a beautiful subject. I usually visit their blogs and update myself through the information they contain, but today's blog would be most appreciated. Well done!

    Machine Learning Course in Bangalore

    ReplyDelete
  31. Great Information sharing .. I am very happy to read this article .. thanks for giving us go through info.Fantastic nice. I appreciate this post. data science course in delhi with placement

    ReplyDelete
  32. This post is good enough to make somebody understand this amazing thing, and I’m sure everyone will appreciate this interesting things. data science training institute in gurgaon

    ReplyDelete