Data Structures extension

So this is the culmination of about 6 weeks of work. Starting with JSON, then Collections, I have been working on extensions that provide new kinds of values for Inform 7. This work has reached its final form in the new Data Structures extension. Unlike the previous two, Data Structures also requires you to install two .i6t template files:

That’s a slight hassle, but brings the big advantage of not needing to manually deallocate values. Instead we can take advantage of Inform’s built in reference counting/garbage collection.

You can leave those files in the I6T folder even if you do not use Data Structures in some of your projects; the kinds will still be present in the Index, but as long as you don’t try to use them they will have no effect.

Checked phrases

This extension tries to be safe by default, so the return values of some phrases are Options or Results. These kinds wrap an optional return value; for Options you either will have a return value or none, for Results, either a return value or an error message. You must then check what is returned from these phrases and make sure you account for the possibility of failure. There are also unsafe “unchecked” phrases which you can use when you are sure that the phrase will be successful, but this is discouraged. In fact it will often be not only safer but also more performant to use the safe variations.

For example, you might think of checking if a map has a value and extracting it like this:

if fruit varieties has key "apple":
	let apple name be get key "apple" of fruit varieties unchecked;

But when you do this the code actually searches through the map twice: first to check if the key exists, and then to extract the value. It is better to just use the safe variant which returns an option:

let result be get key "apple" of fruit varieties;
if result is some let apple name be the value:
	...

And in fact you can combine these into one statement:

if get key "apple" of fruit varieties is some let apple name be the value:
	...

When a phrase may fail there is sometimes a phrase variant that lets you specify a backup value:

let apple name be get key "apple" of fruit varieties or "Royal Gala";

Anys

An any stores a value and its kind; the kind cannot be determined at compile time, but can be read at run time. These are useful for when you want to store multiple kinds of values in one list or map, or for when you don’t know what kind some data might be.

When play begins:
	let apple be "Royal Gala" as an any;
	if kind of apple is a text:
		say "[apple] is a text[line break]";
	if apple as a text is okay let apple name be the value:
		say "Apple variety: [apple name][line break]";
	let year be apple as a number or 2022;

Closures

A closure preserves the state of a phrase so that it can be resumed at a later time. They are still experimental, and do not yet support block value local variables.

When play begins:
	let C1 be a new closure number -> number;
	ignore the result of generate test closure with C1;
	say "Running:[line break][C1 applied to 10][line break]";
	say "Running:[line break][C1 applied to 100][line break]";

To decide what number is generate test closure with (C - closure number -> number):
	say "Closure setup[line break]";
	let N1 be 1;
	initialise C with parameter N2;
	say "Resumed closure[line break]";
	say "N1: [N1][line break]";
	increment N1;
	say "N2: [N2][line break]";
	update all local variables of C;
	decide on 20;

Couples

A couple is a 2-tuple, grouping two values of any kind. Couples are useful for when you need to return two values of different kinds from a phrase.

To decide what couple of person and number is the person evaluation:
	decide on yourself and 1234 as a couple;

When play begins:
	let result be the person evaluation;
	say "Person: [first value of result][line break]Evaluation: [second value of result][line break]";

Maps

Maps store key-value pairs. Each map has a set kind for its keys and another set kind for its values, but if you need to store heterogenous keys or values you can make a map using anys.

When play begins:
	let data be a map of text to any;
	set key "player" of data to yourself;
	set key "score" of data to 0;
	set key "action" of data to the jumping action;
	if get key "score" of data is some let score be the value:
		say "Starting score: [score][line break]";
	let temperature be get key "temp" of data or 23 as an any;

Nulls

Null values are occasionally useful; they are needed for parsing JSON, and can also be used for a promise that indicates when it is finished but has no actual resulting value.

Options

An optional value, either nothing, or a value of a specific kind.

When play begins:
	let O1 be "Hello" as an option;
	let O2 be a text none option;
	if O1 is some let message be the value:
		say "Message: [message][line break]";
	let second message be value of O2 or "Goodbye";

Promises

A promise represents a value which is yet to be determined, and holds a list of code hooks to run when it has been resolved. Promises are still somewhat experimental.

Jump promise is a person promise that varies.

When play begins:
	now jump promise is a new person promise;
	attach receive the jumper to jump promise;

To receive the jumper (P - person) (this is receive the jumper):
	say "[P] jumped!";

After jumping:
	ignore the result of resolve jump promise with the player;

Results

A result contains either a wrapped value or an error message text.

When play begins:
	let R1 be 1234 as a result;
	if R1 is okay let score be the value:
		say "Score: [score][line break]";
	let R2 be a number error result with message "Oops!";
	if R2 is okay let score be the value:
		say "Score: [score][line break]";
	otherwise if R2 is an error let  message be the error message:
		say "Error! [message][line break]";

Future work

I need to complete the unit tests for this extension, which will no doubt expose more bugs. Closures still need a lot of work, to support block value variables, and also to support more parameter options; unfortunately each number of parameters needs to be manually implemented. I will also work more on Promises: you should be able to add a closure as a promise handler, and I’ll also consider adding ways of combining promises (probably based on the JS Promise API.)

17 Likes

I’ve been wondering what you were up to. :) Nice.

2 Likes

Yeah, my weird questions were all to do with closures. This extension has a partial Quetzal parser as that seems to be the only introspection option Glulx has.

1 Like

Out of curisosity, besides the JSON extension, have you got other uses in mind, or was it mainly for the fun/technical challenge?

I can see how anys and maps could be useful for regular authors, and while the rest is very cool (I mean, closures!), I can’t find a situation where they would be really useful.

For the couple in particular: when I want to return multiple values, I usually just set some globals as additional “returned” values. (Or maybe they are useful when used with closures?)

I also find the syntax to unwrap options and results a bit clunky, but I concede it’s difficult to find a better one.

Maybe something like that:

let result be get key "apple" of fruit varieties;
if option result has a value of apple name:
    ...

But it’s less evident that we are declaring a new variable. So maybe put the word “let” at the begining, to mimick regular variable declaration?

let result be get key "apple" of fruit varieties;
if let apple name be the value of option result:
    ...

Anyway, I do find the work you did impressive.

if let would be similar to Swift.

Edit:
I’ve already adopted it for JSON unwrapping, I like it.

When play begins:
	let obj be parse "{'key':'value'}";
	if let value be obj => "key" as a text:
		say "value is a text: [value].";
	else:
		say "value is not a text.";
		
To decide which JSON reference is (json - JSON reference) => (key - text):
	decide on get key key of json;
	
To if let (V - nonexisting text variable) be (R - JSON reference) as a text begin -- end loop:
	(- if (
		JSON_Get_Type({R}) == (+ JSON string type +)  && 
		(({-lvalue-by-reference:V} = JSON_Read((+ JSON string type +), {R})), 1)
	) -).

Astonishing. I’ll probably spend weeks spotting more things I didn’t think were possible.

1 Like

I think options and results could be quite useful generally. While some kinds already have invalid states, such as nothing for objects, for a numerical kind there isn’t anything you can do, unless you set aside a value to be the invalid result, like -1. But then what if something changes and you want to be able to return a valid result of -1? And from other languages, I think results are useful for when you have a complex operation that could fail at multiple sub-levels/sub-functions. External files, parsing JSON or other formats, things like that are really suited to returning results.

Promises could maybe be useful for some games… maybe if you need to dynamically add things that happen after a potion is brewed then a promise could be useful. I’m not sure really to be honest, but I thought I’d add it as it really wasn’t very hard to implement, and then we can see later what uses it finds.

One issue with promises is that there’s no sort of await statement (though could it now be implemented with closures?), and the core loop of Inform is not async, so if your code stops then it just continues on with what it was doing, going through the turn sequence rules. So I have wondered whether it would be good to write an extension that overhauls the turn sequence rules to make it async/promise compatible.

That can work, but occasionally you’d be in a situation where you’d need to run such an algorithm twice before you consume the result of the first one. Couples are much better suited in that situation. Or if it’s a recursive algorithm!

Triples and other size tuples don’t seem to be possible in Inform 7, but you can put a couple inside of a couple. Or just use a map.

There already are several if let phrases… but the let is at the end because I think it flows better as English:

if (O - value of kind K option) is some let (V - nonexisting K variable) be the value:
if (R - value of kind K result) is ok/okay let (V - nonexisting K variable) be the value:
if (R - value result) is an/-- error let (V - nonexisting text variable) be the error message:

I already gave this example above, of putting a map get inside the option if let:

if get key "apple" of fruit varieties is some let apple name be the value:

But this would be so common that I’m thinking it would be better to have a shortcut phrase:

if fruit varieties has key "apple" let apple name be the value:
1 Like

Thanks for the answer!

Yeah, options/results are nice. I guess a workaround without them would be to return 2 values, a bool and another thing. A bool of false means None and we shouldn’t take the other value.

About returning multiple values with globals, I haven’t thought touroughly about it, but even with recursive algorithm, one could store the “returned” global into a local before calling the function again?

For 3-tuple and more, is it possible to use a list of anys, maybe?

Anyway, as I said, I’m having a hard time finding real situations where the features are necessary, but I guess this extension isn’t for regular use cases! :slightly_smiling_face:

There’s probably very little that this extension enables that was truly impossible before, but using these new kinds will be more expressive and often simpler. For example, there are work arounds for returning multiple values, but they can be quite convoluted and data could get desynced, whereas a couple is easy to use, can be freely passed between functions without worrying about whether it’s been overwritten, and ensures the two values remain together until the time that you deliberately extract them into separate variables.

The trade off is that this extension can’t be installed like most others, so I’d say that other extensions should only depend on it if it makes a huge difference. The JSON extension for example will make heavy use of anys and maps, and depending on this extension means authors won’t have to manually deallocate JSON values. We should really consider the first JSON release to be an unfinished prototype as I didn’t know this sort of extension was possible back then…

Or extensions could conditionally depend on this one, perhaps offering safe phrases returning options/results if this extension is included, and unsafe phrases if it isn’t.

The benefit of nested couples over a map or list of anys is that they can be type checked. Slightly faster performance too, but if performance actually matters then there would be other options to consider too. Tables are always a reasonable option!

3 Likes

I think a lot of what you’re doing here with Collections and Data Structures goes over my head but having messed around with Collections a little bit now I definitely appreciate these extra tools. I believe you saw my previous topic about Quantitative relations and that has been the main context I’ve been exploring Collections through and I really think these added data structures add something in that regard. Even in places where tables would work sufficiently which to my knowledge I could just be using tables for everything I want to use maps for, I think this approach is especially helpful for a more abstract/procedural approach to data where it is easier for me to outline rules for how to create these maps, how to assign initial values and then how to manipulate those values, where as with tables I believe you have to at least first specify how many rows and columns the table will be comprised of.

Another aspect I appreciate about this approach, just has to do with how I conceptualize it. Perhaps this is just myself but as evident by my question about Quantitative relations, it’s very easy for me to conceptualize maps as an extension of informs built in relations which as someone who a decent amount of this data structure stuff goes over my head, I find it pretty helpful.

So thanks for making this, I’m definitely excited to see how this grows.

3 Likes

Most of my biggest pain points with I7 (not unrelated to each other):

  • inability to dynamically build arbitrary data structures
  • inability to return more than one result from phrases and rules
  • inability to pass more than one argument to rules
  • tediously duplicating essentially the same code 'cause I7’s static typing wouldn’t let me abstract around it

Data Structures flat out fixes the first three and right now I’m guessing it’ll go about 3/4 of the way to fixing the fourth, much, much further than I’d imagined was remotely possible.

And I haven’t even played with closures yet.

4 Likes

Just pushed a small update, the main thing being adding these phrases:

if kind/type/-- of/-- (any) is (name of kind) let (nonexisting variable) be the value:
if (map) has key (key) let (nonexisting variable) be the value:

Also, you all might be interested to know that I tried doing this without the I6T replacement files. You can create a new kind within an extension by calling the appropriate {-...} commands and it will be listed in the index, but it won’t be recognised in any code that tries to use it. And despite Main.i6t suggesting that you can modify it with template replacements, nothing you can do seems to have any effect.

3 Likes

If I may ask: Where did you learn how to create your own data types? Did you just reverse engineer the template layer, or are there details in documentation somewhere?

1 Like

I slowly worked it out by reverse engineering the other kinds. I still don’t know what all the properties do; I’m not sure that the heap size estimate actually does anything for example, but it’s easy enough to include.

If anyone else ever wants to make a custom kind, I can explain the parts that I do know.

1 Like

Has anyone started using this yet? With the new Inform 7 on the way very soon I’ll probably shift to developing this for 10.1.0, and turning it into a “kit”, which hopefully will make it easier to install.

Also, there’s now some documentation of the kind specification format!

2 Likes

I’ve made a proposal document at the Inform evolution repository for including Anys, Couples, Maps, Nulls, Options, and Results in Basic Inform:

Closures and Promises are still too experimental, but I’d like to continue working on them. I might develop them as independent kits later on, and if they reach a level of stability I’m happy with then maybe I’ll propose to incorporate them in Inform.

2 Likes