How to define a formal language for describing procedural activities

I do not have a formal computer science background here so I am looking for pointers.

How would you advice I go about describing a formal way to describe procedures like cooking recipes, manufacturing process, driving to a location etc.

Given the fact that these types of process does feel like algorithms, but they feel more open ended than normal algorithm represented by programming languages. For example a cooking recipes does not have to be 100% identical to result into the same dish. Also describing a step in a cooking recipe could be expressed in various ways since natural language is being used.

This same process can be made for manufacturing process, driving to a location etc.

What concepts or tools should I be looking at if I want to achieve this kind of things?

Would DSL? Do the job? Or would DSL be too restrictive? Because I am thinking how can one encode the various near infinity steps/procedures involved in an activity like cooking or manufacturing.

Pointers would be appreciated

Your question is very broad and has possibly hundreds of answers depending on the interpretation. The fact you tagged it with "formal-languages" and "formal-grammars" suggests you are actually asking "how the syntax of a language describing this kind of stuff should look like". Sometimes, reading your question I feel you are actually asking "what kind of computational power should a language employ for encoding these processes."

Let's try to consider several aspects and draw a conclusion. If you are willing to describe some process (cooking/manufacturing/etc) you need to figure the most important elements to formalize and how they interact with each other; therefore depending on the purpose of the formalization the language will have to comply.

If you are willing to formalize for the sake of explaining the context to somebody else (man or machine) the formalism will be descriptional. In the case of a human-readable (but still formal) description, even XML could be a suitable candidate (depending on your requirements). In case, a machine-readable formal description was of interest for inference making and ontology (encoded in Description Logic with some set of axioms DL) could do.

If you are willing to verify the description satisfies several properties, the formalism will require the logic and the inference engine for doing so MC.

If you are willing to encode and run the description, the language will require several sub-languages that not only allow to declare the elements of the discussion but also how they interact. I'm thinking to the C language, where nothing is encoded and you have to describe the world through structures and functions. Or Java, where the same is accomplished through classes.

I think enough elements have been exposed, the short answer is: it depends on what you are interested in formalizing and what you want to achieve once the formalization is complete.

For example, suppose you want to grow virtual artificial plants, the most common way to go is employing L-systems, (L-systems). As you can see such formalism points out what can be described, how it can be done, the syntax for doing so, and eventually provides a computational procedure for doing it.

Hence, you should first decide precisely what you want to formalize, decide the restrictions of the formalization, and only then start pondering the actual grammar.

With respect to your question about DSL, let's consider this assertion: "Domain specific languages (DSLs) are languages whose syntax and notation are customized for a specific problem domain" taken from "A survey of grammatical inference in software engineering" by Andrew Stevenson and James R. Cordy. L-systems' grammar is a DSL, but their most unrestricted version can compute anything. So there are DSLs that can achieve any kind of computation and therefore are never "not enough". The same is true for Latex. Latex Is Turing Complete

I hope the example sheds some light on your doubts.

~ Tl;dr.. ~

What you are referring to is an algorithm. No more - no less - a stepped and detailed description of a process, the follow-through of which will lead to the intended result. This answer comes in two parts. The first focuses mainly on the structure. It's follow-through results in a human readable algorithm. The second deals with turning said algorithm into an efficient input data structure for any parser program. Finally, I describe a few tools to help you out with this process.

As Chaos mentioned in his or her answer, this question could be interpreted in many different ways. This is largely because of two missing pieces of info. One is the amount of granularity needed, although the line about DSL, which originally overlooked. The other is the end use . You mentioned encoding, but that is a very general term. For this reason I tried to answer the question from multiple angles and perspectives. Also, I try to do this all in a tutorial-like, step-by-step fashion to demonstrate the underlying concept of the algorithms.

                        ~~~ INTERPRETATION 1 ~~~



There is already a convention for listing processes such as cooking a certain dish. This is the ordered list. Whatever you choose as the final syntax, the ordered list should be the architecture. It provides readabilaty for people, and is the most efficient structure for any parser. It will let you use a one-way design as well as a stream for data transfer, as opposed to:

• scan-all
• then evaluate-all
• then-send-results

type design where each job must finish before the next can begin. This flow has advantages in certain situations, but being forced into it because of the input data structure is never ideal.

THE STRUCTURE

The purpose of an ordered list is just as it sounds, to describe processes that need to be broken down into steps, and where each of these steps needs to be completed in the correct order.

Another term for writing out an ordered list would be defining an algorithm. When we discussed algorithms in computer science class, our homework was to define an algorithm for hard-boiling an egg. To be correct, it had to be detailed enough that someone who didn't know what a boiled egg was could do it perfectly in one try, just by following the steps exactly.

The only difference between the two would be extra detail. A perfect algorithm has no extras. This is because they each achieve the same purpose, but they do so in different environments.

An algorithm is designed for computers. Computers could care less about a context. In programming, context is just an abstraction that people use to understand software and for a reference point from which to develop it.

Ordered lists, on the other hand, are usually meant for human consumption. When in code, they are just another abstraction. the actual data isn't in any particular order; usually it is randomly placed in the most efficient bytes in memory at runtime.

-- PROCEDURE FOR CREATING AN ORDERED LIST --

In order to write (or type) out an ordered list, you can follow these steps. For efficiency in making my point, I will list them using an ordered list.

1. Write out a paragraph that describes your procedure in a chronological fashion (i.e. along a timeline; first step first, last step last.) *~~* The more detail the better. Use a sentence or two to describe each step (again, in order of occurrence.) You can include another sentence or two after these that provide extra detail about the step, as I have done here. To demonstrate this, I will add a double-hyphen before the 'extra' in each of thes steps.The extra detail is not necessary, but it often increases the quality of the end result. As a side note, the end result may (should) feel a bit like you are over-explaining, especially if you are describing a "mainstream" process to which most people have at least a bit exposure. This is how it should be. You should never assume that everyone already knows something, especially on the internet. Remember, you are writing for those who do not.

2. Next, break your paragraph(s) up into small chunks by putting an empty line just before the start of each step. The end result should be a vertically aligned column of text 'chunks.' *~~* They should look like paragraphs, although they are not. While paragraphs group ideas, these are grouping steps, and any related info. In fact, step one above contains two paragraphs. I purposely left out the empty line between them, so as not to confuse the concepts.

3. Add numbers, in order from 1 to n (n being the total number of steps) at the very beginning of each step. *~~* That's it for this step. You can put any type of numbers you want, but this is more in the domain of step...

4. Now, all that is left is formatting. The implementation of this step depends on the context. That is, your reason for listing out the process will determine how the end result should look. *~~* For example, since I am writing this for a SE post, I have to format it according the guidelines of SE's flavor of markdown. Although markdown is technically a standard (I think?) Online implementations vary from one website to the next. Reddit, for instance, has a similar but different set of rules. If there are no rules in a given context, then it is entirely up to you. However, one rule always applies. Be consistent. Whatever you do, do it throughout. If you are typing, which is really the first (and probably the most important) formatting decision, and you decide to add bold-text step markers, be sure to add them to every step. Small changes to the styling will draw the reader's attention away from the content, making your writing harder to follow. This leads me to...

5. Go back over your list and check for, spelling, grammar, and punctuation errors, readability, exclusion of important info, inclusion of extra info that takes away more than it adds, and finally, consistency. *~~* The importance of this last one is often underrated. In fact, I see it all the time when editing on SE. Just being consist with styling, along with things such as spellings (when referring to this network, I might write SE in one spot and se in another) or use of backticks  on a specific word or phrase. These little things can destroy your credibility in the eyes of a reader without him or her even realizing it. Once this happens, the reader is not going to take any of your advice seriously. This defeats the entire purpose of writing it out in the first place.

And that is it for the general structure. This may seem basic and feel like it is common-knowledge, but that is because it works so well. The only way to further standardize it would be to add a syntax so that a computer can understand it as well. In fact, this is what the next section is all about is about.

                        ~~~  INTERPRETATION 2  ~~~


I guess this is really an extension of the first interpretation, although the first assumes that the desired solution looks at the question without consideration of parseability , and this looks at the question from more of a programmer's perspective.

The first perspective also assumes that you were looking for a general solution, whereas this answer is a bit more specific, as it builds on the first. It doesnt change much of what has been written thus far. Believe it or not, that overly verbose mess above is close to parseable if it is tweaked correctly.

Therefore, I will use it as an example for the next section.

ADDING PARSE-ABLE SYNTAX TO EACH STEP

At this point, your algorithm likely looks pretty polished... to human readers. The one above is (intentionally) a bit verbose However, if an average computer were to parse it, it would probably see the same thing you've seen if you've tried to read encrypted data.. a jumbled mess.

If parseability is your goal, this is not going to work.

Luckily, this is not as big of a problem as it looks. In fact, in some situations, a documented like the one above need not be changed. Thanks to a couple clever tools and a bit of foresight, we design the parser around the data structure just as easily (if not more so) as the alternative. In fact we wont even need to design the parser, because one of our tools is a parser generator (see below).

RECOMMENDATION: FLEX & BISON

You also mentioned tools. I know of two tools that are invaluable for this purpose. These are Flex and Bison. Both of these let you define a syntax (more precisely, a set of rules) as input. Once they are given this input, both can parse any document to check whether or not it complies to the syntax rules you have given.

Technically, Bison doesn't parse anything. Instead, it writes a parser program that does the parsing. This is were it gets the name parser generator.

They are both maintained by GNU, and so they are free software (a.k.a. open-source.)

The learning curve is not trivial,but it isn't horribly steep either. Any time you have a tool as flexible as these two, there will be some learning involved. They each have their own syntax for defining the input files.

EXAMPLE USE CASE

To demonstrate how bison can be used to solve your problem, I will give you an example use case. This is actually an account of how it helped (and is still helping) me through a predicament which was/is in some ways similar to yours.

I recently was in a situation where, like you, I needed to define a real world entities. Although, instead of actions, I was trying to do this for digital files.

A few weeks ago at work, I was tasked with designing a 'Swiss army knife' style tool for working with config files.One requirement was that the design needed to be centered around a home-grown file parser. Furthermore, it required the ability to be configured on the fly (in other words, it didn't need only parse one single syntax; the syntax had to be programmable).

For the next week or so, I found myself looking a lot at the concept of syntax. I was trying to visualize an abstraction loose enough that it would fit any syntax. I was stuck there for longer than I would like to admit.

By luck, I stumbled across Bison and Flex in a video. It provided the abstraction that I was looking for.

Now I will demonstrate how you can solve your issue with their help. one can easily set up a workflow, using either of these tools, to efficiently achieve not only an acceptable syntax, but also a parser written solely to parse this syntax. You can even build in rules to interact with whatever comes after the parser. Sort of like including the interface as well!

As I said before, we do not need to do much to the ordered list from the first part of this answer. This is because we can easily tell the parser to ignore most of it. This is one reason why the 'chunks' were so overly verbose.

To do this, just

• Be sure to include the *~~* after the minimum amount required in each step.
• It can be any set of symbols, just as long as it will never show up naturally.
• Be sure to use a consistent descriptor for the numbers, or whatever you choose to use, at the start of each step.
• The same rules apply as above.
• Include an extra step at the end that contains only the word 'end'.
• Include an extra instance of the *~~* descriptor at the very top of the file.
• The top *~~* and the 'end' step will be required syntax for all subsequent lists of this type. you can even use them in your programs to detect this file type.
• Now you need only write a rule stating that any text appearing between *~~* and 'number' should be ignored.

This is easy to do, as the rules are written using regex. Now the fluff will be treated the same as comments in a programming language. At this point, you only need to worry about the structure of the First sentence or two in each step. The only thing left to do
is lay out the structure which these sentences need to follow. This will be domain specific, but fairly simple. The linked resources describe in detail how to create the templates.

* NOTE:*

Because of the extreme versatility of Flex and Bison, it is very hard for me to explain them within the scope of a SE answer. While I will keep editing in rounds until I have done so, I have also provided links to a few video tutorials below. Programs like this are easier to grasp with a quick tutorial. The first refers to Lex and Yakk. These are predecessors to Flex and Bison. The latter are front end wrappers to the former, so the functionality is more or less the same.

Hopefully, my experience from above showed you that the biggest hurdle in defining a syntax is figuring out how to define define a syntax. You cant just say "it's yaml" or "It will be like Typescript, but with Java typechecking." What terms do you use? What needs to be where?

These problems are layered. Each is just a symptom of another. As my coworker said, it is just like an onion. You just keep peeling away at the layers, crying the entire time.

That is what makes these tools so valuable. They give you a convenient abstraction.

Another convenient analogy: Think of you problem as a puzzle. What you are after (if you are, indeed, referring to )Although it is a bit different for each tool.

Flex is known as a lexigraphic analyzer. Put simply, it takes the rules that you give it and analyzes any input against those checks.

Bison is a parser generator. It will output a fully functional file parser that follows your constraints. You tell it what the parser should expect, and it will return a parser. You can then add this parser to your own prograns, or do whatever you want with it (so long as it complies with the GNU GPL... XD).

• Unfinished. I am editing now. Aug 3 at 0:08
• Still not finished. The content is mostly all here now, But I still need to proofread/ edit once more after giving my eyes a break. 1st post on this site, so I wanted to make it special. I've been at it for hours! Aug 3 at 6:00