Stabel

View Ticket
Login
2021-09-01
04:29
Add array literals and a few builtins. [ccf0c23cc5] [839b5c7d9a] check-in: 7aabb3c813 user: robin.hansen tags: trunk
2021-08-16
12:35 Ticket [839b5c7d9a] 0.3.0: Arrays status still Open with 4 other changes artifact: 97fcb4f2d9 user: robin.hansen
2021-08-13
11:01 New ticket [839b5c7d9a]. artifact: 354dfb73a2 user: robin.hansen

Ticket UUID: 839b5c7d9a5a145d43ee107e963dd2addc268d82
Title: 0.3.0: Arrays
Status: Open Type: Language_Proposal
Severity: Important System: Compiler
Resolution: None Modified: 2021-08-16 12:35:45
User Comments:
robin.hansen added on 2021-08-13 11:01:04:

The following document outlines the language proposal process: Language Proposals

Arrays

Stabel should, like most other languages, have a built-in sequential data structure with dedicated syntax. In many functional programming languages, it's not uncommon to use a linked list for this purpose, but I think that is a bad default for several reasons. The most important of which is efficiency.

Instead, Stabel will use an immutable array as its builtin sequential data structure. There will be literal syntax for constructing arrays, and a module in the standard library for manipulating such a structure using wasm intrinsics for efficiency.

Arrays will be a suitable foundation for other data structures such as Strings, Finger trees (deques), Array mapped tries and others.

Goals

  • Implement literal syntax for constructing an Array type with generic contents
  • Use dedicated web assembly instructions so that manipulating an Array structure is as fast as possible

Non-goals

  • Implement other data structures. These will be the target of later language proposals
  • Implement functions which perform operations unfit for an Array, like adding/removing an element to/at the front.

Description

An Array is an immutable data structure containing a sequential list of elements. An Array may contain elements of different types, in which case the element type is a union of all those types.

The literal syntax for an array will look like the following:

	def: sample-func
	type: -- Int{}
	: Int{ 1 2 3 }

In the function implementation, prefixing an array literal with the element type is optional because of type inference. This particular functionality might be more useful in a later release when we support multiple integer types like Int8, Int64, etc.

In the type signature, prefixing an empty literal with a type name is mandatory for obvious reasons.

Any function that requires no type to be on the stack, and which returns exactly one type, can be used as a literal (integer literals are conceptually functions that matches this requirement). That means the following code will produce the array { 1 2 3 }:

	def: magic-number
	type: -- Int
	: 2
	def: sample-array
	type: -- Int{}
	: { 1 magic-number 3 }

Limitations

For unions, it will not be possible to specify multiple arrays as members. As in, the following code will be a compile error:

	defunion: Sample a b
	: Array a
	: Array b

As will

	defunion: Sample
	: Array Int
	: Array Person

The same will be made true of generic structs if those aren't already caught by the type checker.

The reason is really quite simple, and that is that there isn't a reliable way to differantiate between two arrays (or generic structs) in all cases. Imagine if a multi function is passed an empty array at runtime, which branch of the multi-function should be taken? It's undecidable.

Functions in standard library

The following functions will be added to an array module in the std library:

  • singleton: create an array with the passed in argument as it's only member
  • push: copy the array and add the provided argument at the end of the new copy.
  • append: concatenate two arrays together
  • slice: create a new array containing a subset of the elements from the original array.
  • get: get an element by index
  • set: set an element by index
  • fold-left: iterate over the elements of the array from left to right, calling a function per element to build up an accumulated value
  • fold-right: same as fold-left, but elements are iterated from right to left
  • map: create a new array where all elements of the original array have been transformed by a mapping function.
  • filter: create a new array where only the elements of the original array which passes the provided predicate function are kept.
  • create: creates a new array of a given size, where the provided function decides what the contents should be. * =: check if two arrays are equal

Templates

Stabel doesn't support local variables, and so we need a way to construct semi-literal arrays. I propose a template syntax which lets the user easily create an inline function which builds up the wanted array. It would look like:

	def: sample
	type: -- [ -- Int{} ]
	: { 1 2 3 $ 5 6 7 }

An array literal with one or more dollar signs is considered an array template. The template returns an inline function which constructs the final array, and takes as arguments the number of dollar signs contained within the template. To execute the template, you use simply use !

	def: sample
	type: -- Int{}
	: 4 { 1 2 3 $ 5 6 7 } !


robin.hansen added on 2021-08-16 12:35:45:
After careful consideration, templates will not be part of the 0.3.0 release, though it might be implemented later.

This is both to reduce development time to get this feature out, but also because I'm not entirely sure if it makes sense in this language. It might increase writeability at the expense of readability.