3

I started development of simulator for simulation of distributed algorithms in language C. My work consist of creating simple language for algorithm description and simulator which takes the described algorithm and simulates it.

At first I decided how to represent distributed environment. This simulator will run on single machine so there was need to somehow simulate entities which create distributed environment and do some task according to provided algorithm. Every entity will be represented as data structure called Entity. This data structure will contain all data related to entity, for example state of the entity, local registers of the entity.

For representing topology and connections I want to use some library for graphs in C to represent topology as set of vertices and edges. This vertices and edges will certainly be part of Entity so it can get access it's neighbors for example when it is sending data to them.

Next step was to create simple language so user can easily describe the algorithm and simulate it.

For better depiction here is the example of algorithm flooding.

STATUS = INITIATOR, IDLE, DONE;
INIT = INITIATOR, IDLE;
TERM = DONE;
REGISTERS = ;

INITIATOR
  RANDOM
    begin
      SEND(x, NEIGHBORS);
      BECAME(DONE);
    end

IDLE
  RECEIVE(x)
    begin
      SEND(x, NEIGHBORS - SENDER)
      BECAME(DONE);
    end

At this stage I am working on specification for this language and I got stuck. I am not sure how to properly specify this language. It should be simple but when i for example want to implement command for sending message to another entity I must consider that targets may be various. Targets could be all neighbors or all neighbors except sender or maybe only sender or later in development it should by possible to declare specific target from all entities in environment.

At this point I have two options in mind.

First is using Flex and Bison to analyze and parse input. then gather all data needed and run threads and let them behave according to all possible behaviors in input file with algorithm.

Second option is not to use Flex and Bison and implement every command as C macro. User will use this macros to write input file with algorithm and this file will be linked to simulator with gcc compiler, so when user uses macro in wrong way the compiler will throw an error.

I would like to ask if someone was developing something similar or what kind of approach or technique to choose if exists. I want to implement it in C but maybe other language would be more better for this type of thing.

  • 1
    Have you looked at existing simulation systems? IBM's GPSS (General Purpose System Simulator, if I remember correctly from almost 40 years ago) is quite useful for this kind of thing. – John R. Strohm Mar 10 '17 at 17:53
2

Why would you use lowest-possible level language, C, for an involved task like this? Or, rather, several tasks?

If I needed results quickly and painlessly, I'd take a purpose-built tool, like Erlang or Elixir, to run a distributed system. Upsides: these are used in real distributed systems, allow for crazy amounts of parallelism even on a single box, and have tracing / diagnostic / introspection tools to actually watch what's happening.

Write Erlang functions that map more or less straightforwardly to the elements of your input language, and you can start playing with systems even without any parsers.

Should you want somehow more performance at the cost of a significantly less expressive, but still easy language, take a look at Go. It handles concurrency well out of the box.

Writing a parser in C also looks counter-productive to me. A higher-level language, like Python, or Ruby, or even Java or Haskell, helps do this faster and more conveniently. Defining a parser using e.p. pyparsing and compiling your input language into Elixir or Erlang should be pretty easy, and way easier than doing something comparable in C.

What the layered approach would help with is doing one small, well-defined thing at a time. (An attempt to do everything at once is certain a way to failure, you know.)

  • This is my masters' thesis. My supervisor chose C. I am not writing parser and lexer, for that purpose I want to use Flex and Bison. I am not happy with C for this project. Maybe I will try to bring it up during discussion that that something like python would be more better. I have never heard of Erlang but I took a look at it now and it is something that would ease pain a lot. – M.Puk Mar 10 '17 at 19:44
1

If you're not sure whether you should us a real parser generator, then you should use it. Only eschew the real parser generators like Flex and Bison if you are utterly positive you don't need them.

Every language you write like this grows. It's the nature of the task at hand. Your language will grow. When it grows, if you used C macros, you'll have to fit that growth into the general syntax of the C language. If it grows with Flex or Bison you have parser generators that are literally designed to help you with this sort of growth.

Also, if someone messes up a C macro, the error messages can be horrendous and incomprehensible.

Also, if you have a language grammar handy, you're one step closer to permitting solutions like a Python script which generates content in your language.

The only cases I would personally use the C macro style language would be:

  • If I needed to directly interact with the code (such as getting pointers to members and such), and for some reason could not use a more robust approach like reflection to expose those members
  • I was operating on an embedded machine where every single byte matters.

Also, I would only use it if I was positive that I was 100% okay with every user of my software having to compile code to use my simulator.

If you really want to take advantage of the power of the C preprocessor, there are full grammars which will do the preprocessor step for you and then let you use lexx/bison/antlr/flex to process the results.

  • Maybe using macros is not the right way. I think I will settle with Flex, Bison and C. But I am not sure if my use of Bison is correct. Entities in environment will behave according to their state. I want to use Bison to generate some structure which will store steps and arguments and these steps will point to some functions for example send and execute it. Another thing is that I did not specify any types in my language. And that may be a problem with C. I am designing language similar to one in book by Santoro about distributed algorithms. He use it as pseudo code. – M.Puk Mar 10 '17 at 18:05
  • @M.Puk There are many ways you can do it. My personal recommendation would be to only use grammars for "data," such as an abstract syntax tree (a very useful term to know!). You can use tools like Flex and bison to execute code directly (most grammar tutorials have a calculator example that does this), but it's so easy to get burned that way. I find it best to convert my language into just data, such a data describing the abstract commands to be executed. Then I have a separate step which looks at that abstract data and writes the objects which do the actual activities like sending. – Cort Ammon - Reinstate Monica Mar 10 '17 at 18:42
  • That path keeps me honest. It makes sure I really know what my language looks like when I'm coding it up. It is also very helpful because it guarantees that you have a layer where you can do conversions and manipulations. For example, you may have a simulator that uses the data to make runnable objects, and you might have a static analyzer that looks at the same data, looking for issues like deadlocks. As long as your language parses into "data" rather than directly into "actions" you'll save a load of pain. – Cort Ammon - Reinstate Monica Mar 10 '17 at 18:44
  • One thing that I have in mind is to construct state machine. In file there are states and every state has it's own behavior. For example Initiator entity is doing something different than Idle entity in file I provided in the question. My vision is to create state machine where state holds behavior. With this principle I think it would be lot easier to just check entity in which state it is and run corresponding behavior. And when the state changes it just start from beginning another behavior. So I think that I want to do what you have suggested. Build data not actions. – M.Puk Mar 10 '17 at 18:50
0

promela and spin if the point is to actually verify it. these are protocol simulation tools.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.