logo

drewdevault.com

[mirror] blog and personal website of Drew DeVault git clone https://hacktivis.me/git/mirror/drewdevault.com.git

Language-design-considerations.md (7017B)

    

  1. ---
  2. title: Breaking down a small language design proposal
  3. date: 2021-12-30
  4. ---
  6. <style>
  7. .redacted { background: black; color: black; }
  8. </style>
  10. We are developing a new systems programming language. The name is a secret, so
  11. we'll call it <span class="redacted">xxxx</span> instead. In <span
  12. class="redacted">xxxx</span>, we have a general requirement that all variables
  13. must be initialized. This is fine for the simple case, such as "let x: int =
  14. 10". But, it does not always work well. Let's say that you want to set aside a
  15. large buffer for I/O:
  17. ```hare
  18. let x: [1024]int = [0, 0, 0, 0, 0, // ...
  19. ```
  21. This can clearly get out of hand. To address this problem, we added the "..."
  22. operator:
  24. ```hare
  25. let x: [1024]int = [0...];
  26. let y: *[1024]int = alloc([0...]);
  27. ```
  29. This example demonstrates both *stack* allocation of a buffer and *heap*
  30. allocation of a buffer initialized with 1024 zeroes.[^static] This "..."
  31. operator neatly solves our problem. However, another problem occurs to me: what
  32. if you want to allocate a buffer of a variable size?
  34. [^static]: You can also use *static* allocation, which is not shown here.
  36. In addition to arrays, <span class="redacted">xxxx</span> supports slices, which
  37. stores a data pointer, a length, and a capacity. The data pointer refers to an
  38. array whose length is equal to or greater than "capacity", and whose values are
  39. initialized up to "length". We have additional built-ins, "append", "insert",
  40. and "delete", which can dynamically grow and shrink a slice.
  42. ```hare
  43. let x: []int = [];
  44. defer free(x);
  45. append(x, 1, 2, 3, 4, 5); // x = [1, 2, 3, 4, 5]
  46. delete(x[..2]);           // x = [3, 4, 5]
  47. insert(x[0], 1, 2);       // x = [1, 2, 3, 4, 5]
  48. ```
  50. You can also allocate a slice whose capacity is set to an arbitrary value, but
  51. whose length is only equal to the number of initializers you provide. This is
  52. done through a separate case in the "alloc" grammar:
  54. ```hare
  55. use types;
  57. let x: []int = alloc([1, 2, 3], 10);
  58. assert(len(x) == 3);
  59. assert((&x: *types::slice).capacity == 10);
  60. ```
  62. This is useful if you know how long the slice will eventually be, so that you
  63. can fill it with "append" without re-allocating (which could be costly
  64. otherwise). However, setting the capacity is not the same thing as setting the
  65. length: all of the items between the length and capacity are uninitialized. How
  66. do we zero-initialize a large buffer in the heap?
  68. Until recently, you simply couldn't. You had to use a rather bad
  69. work-around:
  71. ```hare
  72. use rt;
  74. let sz: size = 1024;
  75. let data: *[*]int = rt::malloc(sz * size(int)); // [*] is an array of undefined length
  76. let x: []int = data[..sz];
  77. ```
  79. This is obviously not great. We lose type safety, the initialization guarantee,
  80. and bounds checking, and we add a footgun (multiplying by the member type size),
  81. and it's simply not very pleasant to use. To address this, we added the
  82. following syntax:
  84. ```hare
  85. let sz: size = 1024;
  86. let x: []int = alloc([0...], sz);
  87. ```
  89. Much better! Arriving at this required untangling a lot of other problems that I
  90. haven't mentioned here, but this isn't the design I want to focus on for this
  91. post. Instead, there's a new question this suggests: what about appending a
  92. variable amount of data to a slice? I want to dig into this problem to explore
  93. some of the concerns we think about when working on the language design.
  95. The first idea I came up with was the following:
  97. ```hare
  98. let x: []int = [];
  99. append(x, [0...], 10);
  100. ```
  102. This would append ten zeroes to "x". This has a problem, though. Consider our
  103. earlier example of "append":
  105. ```hare
  106. append(x, 1, 2, 3);
  107. ```
  109. The grammar for this looks like the following:[^caveat]
  111. [^caveat]: Disregard the second case of "append-values"; it's not relevant here.
  113. ![A screenshot of the language spec showing the grammar for append expressions.](https://l.sr.ht/NinS.png)
  115. So, the proposed "append(x, \[0...\], 10)" expression is *parsed* like this:
  117.     slice-mutation-expression: append
  118.         object-selector: x
  119.         append-items:
  120.             [0...]
  121.             10
  123. In other words, it looks like "append the values \[0...\] and 10 to x". This
  124. doesn't make sense, but we don't know this until we get to the type checker.
  125. What it really means is "append ten zeroes to x", and we have to identify this
  126. case in the type checker through, essentially, heuristics. Not great! If we dig
  127. deeper into this we find even more edge cases, but I will spare you from the
  128. details.
  130. So, let's consider an alternative design:
  132. ```hare
  133. append(x, [1, 2, 3]);   // Previously append(x, 1, 2, 3);
  134. append(x, [0...], 10);  // New feature
  135. ```
  137. The grammar for this is much better:
  139. ![A screenshot of the revised grammar for this design.](https://l.sr.ht/s5qI.png)
  141. Now we can distinguish between these cases while parsing, so the first example
  142. is parsed as:
  144.     append-expression
  145.         object-selector: x
  146.         expression: [1, 2, 3]   // Items to append
  148. The second is parsed as:
  150.     append-expression
  151.         object-selector: x
  152.         expression: [0...]    // Items to append
  153.         expression: 10        // Desired length
  155. This is a big improvement, but it comes with one annoying problem. The most
  156. common case for append in regular use in <span class="redacted">xxxx</span> is
  157. appending a single item, and this case has worsened thanks to this change:
  159. ```hare
  160. append(x, [42]);  // Previously append(x, 42);
  161. ```
  163. In fact, appending several items at once is exceptionally uncommon: there are no
  164. examples of it in the standard library. We should try to avoid making the common
  165. case worse for the benefit of the uncommon case.
  167. A pattern we *do* see in the standard library is appending one slice to another,
  168. which is a use-case we've ignored up to this point. This use-case looks
  169. something like the following:
  171. ```hare
  172. append(x, y...);
  173. ```
  175. Why don't we lean into this a bit more?
  177. ```hare
  178. let x: []int = [];
  179. append(x, 42);              // x = [42]
  180. append(x, [1, 2, 3]...);    // x = [42, 1, 2, 3]
  181. append(x, [0...], 6);       // x = [42, 1, 2, 3, 0...]
  182. ```
  184. Using the `append(x, y...)` syntax to generally handle appending several items
  185. neatly solves all of our problems. We have arrived at design which:
  187. - Is versatile and utilitarian
  188. - Addresses the most common cases with a comfortable syntax
  189. - Is unambiguous at parse time without type heuristics
  191. I daresay that, in addition to fulfilling the desired new feature, we have
  192. improved the other cases as well. The final grammar for this is the following:
  194. ![Formal grammar showing the final state of the design proposal](https://l.sr.ht/2nF0.png)
  196. If you're curious to see more, I've extracted the relevant page of the
  197. specification for you to read: [download it here](https://l.sr.ht/eeta.pdf). I
  198. hope you found that interesting and insightful!
  200. *Note: Much of these details are subject to change, and we have future
  201. improvements planned which will affect these features &mdash; particularly with
  202. respect to handling allocation failures. Additionally, some of the code samples
  203. were simplified for illustrative purposes.*