Newgrf Description Language (NDL)

[Eddi]

This is a higher level description language that works on top of the low level NFO

Be aware that this is highly WIP, and may change significantly in a short amount of time

The general idea of a high level language is to use descriptive names instead of byte values, to help newcomers to easily learn the language, and help experienced programmers reading their own code without too many comments, so they would not have to refer to the documentation for every single byte.

USAGE:
a) this compiler is a python program, in order to run python programs, you need the python interpreter from http://www.python.org/download/
a*) there is now a windows package containing an ndl.exe, this is an awfully big file, so i still recommend to use the python files
b) this compiler generates an .nfo file, so you need grfcodec to get a .grf file
c) i assume that you are familiar with command line interfaces
d) i assume a unix style console, windows console probably needs replacing / with \

1) put your .ndl file into the "sprites" subdirectory, together with the .pcx file containing the images
2) run the ndl compiler with the command line "python ndl.py sprites/file.ndl > sprites/file.nfo", this will create the .nfo file next to the .ndl file
2*) if you unpacked the windows executable, run "ndl.exe sprites/file.ndl > sprites/file.nfo" instead
3) run "grfcodec -e file.grf" to turn the .nfo file into a .grf file

LANGUAGE SPECIFICATION:
syntax is currently related to python syntax, this is purely out of lazyness, because python ships with a python parser, and this is highly likely to change (e.g. useful would be Pascal style case-statements with ranges (12..25))
especially this means that names are case-sensitive and indentation is relevant for blocks
i will not discuss about syntax, but i take alternative suggestions in form of an implementation of a parser that generates a compatible tree-structure
[Note: i dislike XML, so don't get your hopes up, you know who you are]

Update: Version 0.2
0.1: the language allows you to specify a GrfID (Action8), and change properties of train vehicles (Action0General, Action0Trains)
0.2: allow changing graphics for vehicles, support for loading stages (Action1/2/3 for trains)

check the exampleX.ndl files for detailed descriptions

currently planned features are:
functions&callbacks (VarAction2)
embedded NFO (for anything you think you can't specify in NDL properly)
vehicle names (Action4)

more features may come while i learn NFO myself

HOW YOU CAN HELP:
i could use someone who writes up a file like TTDTrains.py for the other vehicle types.
comments and suggestions are welcome

DISCLAIMER:
this may not be useful for anything, and i will not provide a decompiler

[Eddi]

Update: Version 0.2

Graphics replacements (Action1/2/3 support for trains)

[DaleStan]

Question: How do you use the same sprites for multiple vehicles, without using multiple identical action 1/real sprite groups?

[Eddi]

currently, you better don't attempt to do that

if i understand the documentation right, an action2 cannot refer back more than the last action1

i was trying to implement an action reordering system, that pushes action2s back immediately after the action1 that they refer to, but that needs an algorithm to reserve action2 ids over a longer time. (cf. lifetime analysis, register allocation) i'm thinking it is not a serious limitation atm, so it gets kinda pushed down the priority list.

PS: in the current implementation, you would probably get away with not declaring "Sprites" in one scope, and it will refer to the "Sprites" of the previous scope... but i would consider that an "undocumented feature", so better not rely on that staying around

[DaleStan]

currently, you better don't attempt to do that

if i understand the documentation right, an action2 cannot refer back more than the last action1

Correct. But actions 2 and 3 can refer to action 2s that appear before the most recent action 1, and also before the most recent action 3.

Only the 1->2 linking is "must immediately follow"[0]. The 2->2 and 2->3 linking is merely "must follow"; once an action 2 defines a cargo ID, that ID is valid for use by all following action 2s and 3s, regardless of how many intervening actions, of any sort, there are. Granted, it is possible for one of those intervening actions to redefine that ID, but no action can undefine a cargo ID.

Most commonly, this is used for rail vehicle livery overrides and for sharing the same rotors between multiple helicopters.

[0] Not quite the conventional definition of "immediately" here, but I'm hoping you can follow.

[Eddi]

it is possible for one of those intervening actions to redefine that ID

yes, that is exactly the problem, if you define an action2 too early, the id must not be overriden until the last action2/3 that use this id, but there is only a limited number of ids (256, if i am rightly informed), in conventional compiler building, this problem is called "register pressure"

Most commonly, this is used for rail vehicle livery overrides and for sharing the same rotors between multiple helicopters.

noted. like i said, this will be possible, but is not trivial to solve (or the trivial solution, in this case, define each id only once, would be unsatisfactory)

this is not a scientifically new problem, there are algorithms for this, they just need implementing (i.e. time)

PS: i now included a windows executable, i hope this works for someone... i can't test that very well

[Eddi]

one possible example of reusable action2-ids would be explicit global reservation:

Code: Select all

class GlobalRotor(Aircraft):
    # use "Aircraft" as base, so this object does not have
    # an ID and no action 0 or 3 can/will be generated
    # but feature can be properly decided
    Sprites = [whatever, you, like]
    StandardRotor = [action 2 comes here]
    ShinySparklingDeluxeRotorForRefitOption = [another action 2 comes here]
    # reserve this action 2 at this point, the ID given here may never be overridden anymore
    global StandardRotor
    global ShinySparklingDeluxeRotorForRefitOption

and later in the file appears this:

Code: Select all

class Helicopter(TTTWhateverAircraftVehicle):
   Sprites = [helicopter,sprites,go,here]
   Rotor = GlobalRotor.StandardRotor
   SelectSprites = [however you could describe using vehicle and rotor sprites]

the problem with this solution is that you have to locally decide at the "global" statement that the following variable will generate an action 2, currently there is no syntactical notation of variable types, the type "action 2" is decided when an identifier is recursively referred to by an action 3, and action 3 is decided by name ("SelectSprite")

[DaleStan]

Properly used, 256 IDs is way more than required. I think I could probably get away with 16 for most files.
I've only written one file where I thought I'd encountered the limit. I wanted a GRF that would display the value of any given byte in the vehicle structure (which requires 256 sprite sets), and at the time I didn't realize that an action 2 could access the previous definition of the ID that it defines, but a little jockeying got the requirement down to 33 IDs. Rewriting further could have reduced that to two. (But not while preserving my sanity.)

Unless you want your compiler to make that type of change, in which case you're doing something completely different than I had imagined, the ID pressure problem is simpler than the usual register pressure problem. You cannot save and restore cargo ID definitions the way you can for register values, so the cost/benefit calculation is conceptually simple: "Do I need this definition again?"

[Eddi]

Properly used, 256 IDs is way more than required.

yes, that is the issue to be solved, evaluating the kind of solutions for "proper", deciding which option offers the lowest effort/result ratio.

I think I could probably get away with 16 for most files.

for hand-optimised assembler code, that may be true, but for autogenerated compiler actions, that might not find the most efficient representation for temporary values, that could be more of a problem. but we'll hopefully see that.

But not while preserving my sanity.

that's where a compiler can help you, it does not require sanity

You cannot save and restore cargo ID definitions the way you can for register values.

correct, but i can opt to define it again at the required places (cf. inlining)

"Do I need this definition again?"

there are two ways to answer that question:
1) explicitly (using a "global" statement like above)
2) implicitly (by calculating references during analyis phase)

[Alberth]

Hai,

A few questions/remarks.

As I understand your project, your aim is a (very) high level specification, where the compiler figures out everything by itself.
From this idea, I don't understand your example2.ndl file. Why is 'Sprites' a list of single-tuple of real-sprite tuples? I would expect simply 4 or 8 real sprites (one for each side), and let the compiler figure out what to do wit them (ie isn't the 'single-tuple' something that the compiler should provide?).

The same holds for the question that DaleStan asked about duplicate use of real sprites. Given the fact that I am not interested in the contents of the nfo/grf file, the answer is (I think) that you should specify each wagon individually, and then the compiler will find duplicate sprites, and eliminate them.

The IntroductionDate is also not logical from your aim (this is a very weak point in my current implementation as well). As user ignorant of the grf/nfo files, I really don't care how the introduction date is measured. "january 1st, 1920" would be my idea of a date (just like "may 18th, 2018" rather than some big awkward number).

With respect to your limited number of Action2 ID's, If you move the Action3 to directly after the Action2, the ID becomes available again for re-use. I think this also holds for chains of Action2.
(a verification question to DaleStan: suppose I have an basic Action2 with ID 0, used by an variational Action2 with ID 1, which in turn gets used by another variational Action2 with ID 0. Finally, an Action3 that uses Action2 ID 0. I expect that the Action3 uses the last variational Action2 (with ID 0), while the variational Action2 with ID 1 is still using the first basic Action2. Would that be correct?)
If yes, one would need a very complicated chain to run out of ID's.

Last but not least, an addition you may want to add is to allow the user to specify what part of the available space (ID's and storage) can be used by the compiler (it needs to know the boundaries any way, you might as well make them dynamic). In that way, I can give some ID's and storage 'away' to the compiler, and keep some for myself to code the stuff that the compiler doesn't do.

[DaleStan]

Why is 'Sprites' a list of single-tuple of real-sprite tuples? I would expect simply 4 or 8 real sprites (one for each side), and let the compiler figure out what to do wit them

What about helicopter rotors? With (IIRC) 2 or 1+3n sprites.

With respect to your limited number of Action2 ID's, If you move the Action3 to directly after the Action2, the ID becomes available again for re-use.

Unless that ID is also used by a later action 2 or 3, in which case it's not available until after that one.

suppose I have an basic Action2 with ID 0, used by an variational Action2 with ID 1, which in turn gets used by another variational Action2 with ID 0. Finally, an Action3 that uses Action2 ID 0. I expect that the Action3 uses the last variational Action2 (with ID 0), while the variational Action2 with ID 1 is still using the first basic Action2. Would that be correct?

Yes.

[Alberth]

Why is 'Sprites' a list of single-tuple of real-sprite tuples? I would expect simply 4 or 8 real sprites (one for each side), and let the compiler figure out what to do wit them

What about helicopter rotors? With (IIRC) 2 or 1+3n sprites.

That would be a NDL compiler problem.

My point is that, as user ignorant of encoding, I just specify the sprites that I have at a logical point in the specification. Views of the wagon in the 'define views here' section, and helicopter rotors of the wagon in the 'define animations here' section (and a list would be a good solution for collecting the sprites). Everything after that is a compiler problem.

(And yes, one would normally encode all sprites in a single Action1. That is however thinking from encoding upwards (ie 'how to organize what the user specifies such that it is close to the encoding') rather than from "I want to make a new wagon and I don't care about its encoding" downwards that NDL aims for.)

With respect to your limited number of Action2 ID's, If you move the Action3 to directly after the Action2, the ID becomes available again for re-use.

Unless that ID is also used by a later action 2 or 3, in which case it's not available until after that one.

eh, yes, of course.

suppose I have an basic Action2 with ID 0, used by an variational Action2 with ID 1, which in turn gets used by another variational Action2 with ID 0. Finally, an Action3 that uses Action2 ID 0. I expect that the Action3 uses the last variational Action2 (with ID 0), while the variational Action2 with ID 1 is still using the first basic Action2. Would that be correct?

Yes.

great!

[Eddi]

Why is 'Sprites' a list of single-tuple of real-sprite tuples? I would expect simply 4 or 8 real sprites (one for each side), and let the compiler figure out what to do wit them (ie isn't the 'single-tuple' something that the compiler should provide?).

that's kind of a difficult issue, because i am kinda stretching it already with the automatic typing. if you leave out some more syntax elements, you are creating ambiguities that you cannot easily resolve (and especially not inform the programmer about possible errors (warnings)) (note that in the current implementation state, errors are totally non-descriptive and warnings are non-existent)

also the current limitation of only referring to the last action 1 is not really compatible with this, but that limitation will get lifted when i implement the action 2 renumbering. At that point it would be possible to let the coder specify individual spritegroups, which may then be combined into one action 1 if applicable, but that possibly causes more problems than it solves (from the analysis point of view)

The same holds for the question that DaleStan asked about duplicate use of real sprites. Given the fact that I am not interested in the contents of the nfo/grf file, the answer is (I think) that you should specify each wagon individually, and then the compiler will find duplicate sprites, and eliminate them.

that is kind of a very advanced optimisation, i wouldn't attempt that in the near future, but it might be a possibility. optimisations are a difficult topic, as there are different, usually concurring, optimisation goals. in regular compilers those are typically execution speed, register pressure (variable lifetime) and code size, usually you can only optimise for two of these.

The IntroductionDate is also not logical from your aim (this is a very weak point in my current implementation as well). As user ignorant of the grf/nfo files, I really don't care how the introduction date is measured. "january 1st, 1920" would be my idea of a date (just like "may 18th, 2018" rather than some big awkward number).

that one is quite trivial to solve, i can just introduce a DMY(18,5,2018) or YMD(2018,5,18) macro, shouldn't take much longer than 5 minutes (but not right now).

With respect to your limited number of Action2 ID's, If you move the Action3 to directly after the Action2, the ID becomes available again for re-use. I think this also holds for chains of Action2.
(a verification question to DaleStan: suppose I have an basic Action2 with ID 0, used by an variational Action2 with ID 1, which in turn gets used by another variational Action2 with ID 0. Finally, an Action3 that uses Action2 ID 0. I expect that the Action3 uses the last variational Action2 (with ID 0), while the variational Action2 with ID 1 is still using the first basic Action2. Would that be correct?)
If yes, one would need a very complicated chain to run out of ID's.

that is not the actual issue, the issue is the analysis step to find out a somewhat adequate action 2 chain, that needs a data structure that keeps track of which action 2 ids are mandatory to stay alive at each point of the "proto-NFO" structure (that is currently the "actions" list variable, but that might morph into a more advanced data structure later, especially when i need a notation of basic blocks to implement action 7/9 (i might need a little help about the subtle difference between those, later)

Last but not least, an addition you may want to add is to allow the user to specify what part of the available space (ID's and storage) can be used by the compiler (it needs to know the boundaries any way, you might as well make them dynamic). In that way, I can give some ID's and storage 'away' to the compiler, and keep some for myself to code the stuff that the compiler doesn't do.

i'm not entirely sure what you are suggesting here, if you mean embedded NFO, yes, there needs to be a notation about which ids to "export" to the "real program", which IDs you need internally, and which IDs you need to "import" from outside the NFO block. like always, there are several ways to achieve this, i haven't really decided about how to do that yet

[Eddi]

Hello,

I tried to write an answer to your last post but could not find the right wording, at least not for a public message.
That is why I send you this PM.

don't worry, i am not offended that easily

I get the impression that you are very busy with a lot of different things at the same time (language, coding, limitations, order of implementation, future optimisations).

that is, because some of these actions depend on each other, the structure of the language defines how you can scan the AST (abstract syntax tree) to make analysis steps. on the other hand, the limitations of the target language (NFO) impose requirements on the result of the analysations. these are opposing sides of the implementation, and while the second one is rather fixed, the first one is almost freely decidable, so fixing this one too eagerly might make the problem unnecessarily complex or even unsolveable. the order of implementation is rather fixed already, i wrote that down in the first post, and future optimisations you should always have in the back of your mind, a) to keep your implementation appropriately expandable, and b) to further refine the next tasks.

It may be useful to take a step back, and create some structure in the project, ie what do you expect from your users, what is the input language you aim for, how do you compile in the ideal situation (how many steps, what do you do in each step).

a common saying is: "forge an iron while it is hot." so "step back" might be the wrong way to approach certain problems.

i have studied the theory of compiler building for a few years now, this project is kind of an attempt to use that knowledge in a practical environment. so i know the (theoretical) structure of a compiler quite well, using theoretical knowledge in the praxis is always a little tricky.

a typical compiler looks like this:
[high level language] -parser, syntax analysis-> [abstract syntax tree] -semantical analysis-> [abstract semantic graph] -optimisations-> [intermediate language] - code generation -> [low level language]

you can chain several analysis and optimisation steps as needed

Once you have this structure, you can add new things at the right place in the project, and you can think about adding restrictions and order (post-poning one thing and doing another thing now) due to stuff like limited time/resources.

Business plan:
1. collect underpants
2. ???
3. profit

all right? great.

the above structure already influenced a lot of my decisions.
1st decision: syntax
syntax is irrelevant, if you have a proper abstract syntax tree, you can define any syntax that the users will like. that is not even limited to textual syntax, but could even be a point-and-click interface with a similar structure [but that would be a project on its own]
that is why i have put zero effort into the parser step, if you look into the ndl.py file, you will note that this step makes up a total of 1 line of code, because i reuse the fully implemented parser delivered with python.
the actual decision on syntax needs significant amount of feedback from users, also imaginable is supporting different syntaxes.

2nd decision: semantical analysis
this is the part with the highest initial amount of programming and development involved. in this part, you decide what the syntactical concepts are supposed to mean, you build up a definition table, do type analysis, lots of other stuff that you seem fit. the resulting graph has usually the same structure as the AST, but each node has additional attributes, like definition-use edges, calculated values of constant expressions, expected vs. calculated types. for this task, python provides the "compiler.ast" module, which defines data types and functions for iterating over the tree. also python allows the dynamic expansion of these data types by functions that i seem fit (e.g. the "eval" function that determine the value of constant expressions)

semantical analysis is done in the function "rec", it started out from the initial step of another project i did for university: walk.py (see attachment), that recursively walks [hence the name] through the AST and gives out a graphical representation

3rd decision: "spikes method"
the spikes method is a development model, where you don't focus on one single step, but rather one single feature, and provide a full "spike" to route that feature through all steps. that is, why there are already two releases. typically you choose features in order of increasing complexity, or features that build on each other. with the first feature you define the rough structure of each step, and with each consecutive feature you extend the ability of each step to handle the features.

4th decision: optimisations
as a result of decision 3, there are already rudimentary optimisations done that are relevant to the implemented features (e.g. all property settings get combined into one action0, all action2 are generated at the latest possible time before the action3), the result of this step is the "intermediate language" (i called that previously "proto-NFO"), which basically lists the NFO-actions in their byte representation
the emphasis of development will shift to this step in the later stages of development, when the semantical analysis of most features is done.

5th decision: code generation
once you have proto-NFO, this step is quite easy, in this step, you calculate the byte length, action2 ids and other stuff to finalise the NFO output

i hope i could communicate my kind of knowledge in a better way than before. it was apparently not done enough, or you wouldn't have raised this issue. thank you for doing so, constructive feedback is very welcome.

I really like your project and would like to see it succeed. I think we can learn a lot from each other projects.

Albert

thank you, learning is an important reason to do this project in the first place.

[Alberth]

I get the impression that you are very busy with a lot of different things at the same time (language, coding, limitations, order of implementation, future optimisations).

that is, because some of these actions depend on each other, the structure of the language defines how you can scan the AST (abstract syntax tree) to make analysis steps. on the other hand, the limitations of the target language (NFO) impose requirements on the result of the analysations. these are opposing sides of the implementation, and while the second one is rather fixed, the first one is almost freely decidable, so fixing this one too eagerly might make the problem unnecessarily complex or even unsolveable. the order of implementation is rather fixed already, i wrote that down in the first post, and future optimisations you should always have in the back of your mind, a) to keep your implementation appropriately expandable, and b) to further refine the next tasks.

Glad to hear that I got the wrong impression rather than you getting lost. (and no, I don't mind you replied here, I just wasn't sure what to do.)

In language design, I am used to first decide what the input language should look like, completely seperate from implementation concerns. That is, until I met you. Apparently, you have different ideas.

a common saying is: "forge an iron while it is hot." so "step back" might be the wrong way to approach certain problems.

Well, glad you consider things red-hot. I agree that sitting back would be not the right thing to do then, not to mention a potentially painful one with all those warm things around you.

i have studied the theory of compiler building for a few years now, this project is kind of an attempt to use that knowledge in a practical environment. so i know the (theoretical) structure of a compiler quite well, using theoretical knowledge in the praxis is always a little tricky.

Nah, just add the implementation details (and try not to get lost ).

a typical compiler looks like this:

No need to explain to me, I have been writing compilers and simulators for about 10 years already

the above structure already influenced a lot of my decisions.
1st decision: syntax
syntax is irrelevant, if you have a proper abstract syntax tree, you can define any syntax that the users will like.

Almost, structural changes w.r.t. your tree are always complicated.

2nd decision: semantical analysis
this is the part with the highest initial amount of programming and development involved. in this part.

That is kind of normal too in my experience.

3rd decision: "spikes method"
the spikes method is a development model, where you don't focus on one single step, but rather one single feature, and provide a full "spike" to route that feature through all steps. that is, why there are already two releases. typically you choose features in order of increasing complexity, or features that build on each other. with the first feature you define the rough structure of each step, and with each consecutive feature you extend the ability of each step to handle the features.

Ok. When I try this, I usually find that the last feature does not fit in what I have, and I should have done the entire design different. Let's hope that doesn't happen too often to you...

4th decision: optimisations
as a result of decision 3, there are already rudimentary optimisations done that are relevant to the implemented features (e.g. all property settings get combined into one action0, all action2 are generated at the latest possible time before the action3), the result of this step is the "intermediate language" (i called that previously "proto-NFO"), which basically lists the NFO-actions in their byte representation
the emphasis of development will shift to this step in the later stages of development, when the semantical analysis of most features is done.

I just moved from a list of bytes to a list of fields with values (and types). The final step is then deciding the size of each field, calculating byte length, etc like you do.
The Action6 support that I want made this necessary. I think it may also enable suff like computing the ID of Action2 later, so the user doesn't need to specify it, but I am not sure that is feasible.

5th decision: code generation
once you have proto-NFO, this step is quite easy, in this step, you calculate the byte length, action2 ids and other stuff to finalise the NFO output

Ehm, how do you insert these 'ids' into the byte representation?

i hope i could communicate my kind of knowledge in a better way than before. it was apparently not done enough, or you wouldn't have raised this issue. thank you for doing so, constructive feedback is very welcome.

Communication is always the most difficult thing, getting people aligned in ideas and approaches takes a long time....

[Eddi]

5th decision: code generation
once you have proto-NFO, this step is quite easy, in this step, you calculate the byte length, action2 ids and other stuff to finalise the NFO output

Ehm, how do you insert these 'ids' into the byte representation?

in the ASG, you have calculated definition-use edges, you drag those along unchanged into the proto-NFO, so instead of finalised IDs you have references within the data structure.

to resolve these references into IDs, you go backwards through the actions
when you get to an action 3, you look up the action 2 it references, if that has not had an ID assigned, you take the first free ID, assign that to the action 2, place the value into the action 3, and add it to the list of reserved IDs

when you get to an action 2 that has not had an ID assigned, you did something wrong while generating the actions, because that action is not used anywhere

when you get to a (var)action 2 that had an ID assigned, you remove that ID from the list of reserved IDs in case of varaction2, you go on like with the action 3