Jump to content

straight_stewie

Member
 View Profile  See their activity

  • Posts

    2,705

  • Joined

  • Last visited

 Content Type 

Blog Entries posted by straight_stewie

  1. straight_stewie
    An L-System is a description of a formal grammar in which all tokens in the input are concurrently transformed by their respective productions. Conversely, a Chomsky Grammar is a description of a formal grammar in which all tokens in the input are sequentially transformed by their respective productions.
     
    For example, in the context-free grammar:
    A ---> B
    B ---> AB
     
    With axiom "A" the L-System produces this tree.        While the Chomsky grammar produces this tree.

     
     
     
    If we get our output by concatenating the leaf nodes of each tree into a string, the L-System produces the output "BAB", while the Chomsky Grammar produces the output "BAB". Since "BAB" is equivalent to "BAB", the two grammars produce the same output. However, the Chomsky grammar takes one more iteration over the input to produce it's output.
     
    This last statement is an interesting discovery: if the complexity of the L-System is O(1) and the complexity of the Chomsky Grammar is O(n) then, for large inputs, the L-System will produce the same result much faster. If this is true, that would mean that most programs which transform their input stand to gain significant performance improvements by defining them as L-Systems rather than as Chomsky Grammars. Which leads to the importance of finding a proof for the conjecture:
     
    L-Systems and Chomsky Grammars define precisely equivalent grammars.
     
    As a simple example of their equivalence let's consider a program which takes two inputs, a string A and a character B. The task of the program is to find if the character B exists in the string A. The program is to output a boolean value of true if it finds the character, otherwise it is to output a boolean value of false. As an example, let's run our program with the inputs A="ABDEF" and B='F'. The program could then be defined as the context-free grammar:
     
    F ---> true
     
    The L-System then produces this graph:                 While the Chomsky Grammar produces this graph:

     
    It is immediately apparent that the two produce the same output. It is also immediately apparent that the Chomsky grammar again has a complexity of O(n) while the L-System has a complexity of O(1). In this concrete example, the Chomsky Grammar takes nearly four times as many iterations to produce the same output that the L-System produces in one iteration.
     
    Let us now consider a similar program. This time with two inputs, a string A and a string B. The task of the program is to find if the string B exists in the string A. If the program finds the string B in the string A it is to output a boolean value of true. Otherwise, if the program does not find the string B in the string A, it is to output a boolean value of false. Let us run this program with the example inputs A="ABCDEF" and B="DEF" . This program cannot be defined by a simple context-free grammar. Instead, it's definition requires a right-context-sensitive grammar:
     
    D > E ---> x
    x > F ---> true
     
    The L-System then produces this graph:                 While the Chomsky Grammar produces this graph.

     
    What we can gleam from this is that the L-System is again faster. This time, however, the L-Systems complexity is related to the number of non-terminal productions, while the Chomsky Grammars complexity is still related to the size of the axiom. Of course, this reduces the advantage of the L-System as the length of the match string B approaches the length of the string A. However, this can be solved with a left-right-context-sensitive grammar for the same problem:
     
    D < E > F ---> true
     
    The L-System then yields the graph:                         While the Chomsky Grammar yields the graph:

     
     
    While it may appear at first glance that the L-Systems complexity is back to being constant, it's actual complexity is O(n/2) where n is the length of the match string B. The complexity of the Chomsky Grammar is still O(n) where n is the number of characters in the input string A.
     
    Interestingly, in each example, the L-System produces a faster solution. Which leads to the conjecture:
     
    L-Systems and Chomsky Grammars define the same family of grammars. Additionally, for every problem solvable by defining a grammar, there exists a grammar for which the L-System has a smaller complexity than the equivalent Chomsky Grammar.
     
    At first thought, that conjecture may not mean much. Both L-Systems and Chomsky grammars must look at each token in the input. However, by the very definition of L-Systems, each input token can be transformed concurrently. On the other side of the same coin, the definition of Chomsky Grammars states that the tokens cannot be transformed concurrently. As a result, L-Systems not only have an advantage over Chomsky Grammars in that they have a lower complexity, L-Systems also have an advantage over Chomsky Grammars in that they are parallelizable and Chomsky Grammars are not.
  2. straight_stewie
    This will be a very short blog post, but I hope that it helps someone.

    I've noticed that many people learning C++ struggle with understanding pointers, references, variables, and the const keyword. So I plan to write a few charts and some words that can be used as a sort of reference to help. I will not try to go above and beyond in explaining what pointers, references, and const are, as there are already many resources that do wonderful jobs of that.
     
    General Rules
    There is really only one rule I want to touch on here. There are generally two styles of declaring pointers and references in C++
    Put the asterisk by the type, or put the asterisk by the variable name. int* x; int *x; Many people prefer the second one. They claim that when you are declaring multiple variables in one line, it prevents you from accidentally declaring a pointer to a variable of type, and a variable of a type.
    int* x, y; // x is a pointer to an int, and y is an int int *x, *y; // x and y are pointers to ints. Of course, consistency is key when it comes to readability. So the same rule should apply in all situations. There is generally no good way to make easily readable complex parameter declarations if you adopt the second style shown above. But clearly, you should adopt the second style shown above to prevent errors. Well, I believe that right to left readability is of utmost importance to writing good C++, and so the rule that I use to make everything consistent is: Don't declare multiple variables in one statement.
    int x, y; // bad. // good int x; int y; But what is right to left readability and why do I believe it is so important to write code in such a way that it is maintained?
     
    Right to Left Readability
    Right to left readability is a simple principle, and it helps one understand pointers, references, and const statements so greatly that I believe developers should make it a habit to write code that matches this principle. Ostensibly, the rule says that I should be able to read a parameter declaration or the left side of an assignment from right to left and end up with a valid English sentence that says what the declaration or assignment is doing. Some examples:
    int a;
    a is an int
    int* a;
    a is a pointer to an int
    int &a;
    a is a reference to an int
    Notice the algorithm I'm using to read the declarations here: First, read the name of the variable. Then, insert a verb, in this case, some form of "is a". Then state whether it is a pointer, a reference, or nothing, and then state the type.
     
    One level of const
    const int a; a is an int that is const const int* a; a is a pointer to an int that is const const int &a; a is a reference to an int that is const Notice that we've added a new form of is: "that is". In this case we use "that is" to refer to the int, and not the reference or the pointer. For example, the pointer can be changed, but the integer that the pointer references cannot.
     
    One level of const, redux
    int const a; a is a const int. int* const a; a is a const pointer to an int int& const a; a is a const reference to an int. (notice that this is nonsense, all references are const in this way; meaning that the reference cannot be changed once assigned.) Here, we've introduced yet another verb: to. In this case, const means that the variable, whether it be a pointer, a reference, or an object cannot be changed. So, int* const a is a pointer to an int and that pointer cannot be changed. Also notice that const int a and int const a are identical.
     
    Two levels of const
    const int* const a; a is a const pointer to an int that is const This means that a is a pointer that cannot be changed and that it points to an integer that cannot be changed. const int& const a; a is a const reference to an int that is const a is a const reference to an int that is const Please notice that this is nonsense. All references are const in the sense that the reference cannot be changed. However, in this case, the object that a refers to also cannot be changed. And that's all there is to it. It's really not that complicated, once you learn the appropriate way to write it out and read it right to left. Just incase my hurried formatting above wasn't easy enough to read, here is a chart below. I will leave out invalid entries, such as const references.
     
    Full Chart
    int a; a is an int. int* a; a is a pointer to an int int& a; a is a reference to an int int const a; a is a const int. a cannot be changed int* const a; a is a const pointer to an int the pointer to a cannot be changed const int a; a is an int that is const a cannot be changed const int* a; a is a pointer to an int that is const the pointer can be changed, but the int pointed to cannot be changed through a. const int& a; a is a reference to an int that is const. the int that is referenced cannot be changed const int* const a; a is a const pointer to an int that is const. the pointer cannot be changed, and neither can the int that is pointed to.
  3. straight_stewie
    Lately I've been working on a light temporal sampling algorithm that might be able to avoid some aliasing by adjusting the sampling rate. I usually do things like this strictly in MatLab, because it makes it overwhelmingly easy to build and run these kind of simulations, and then explore the results in potentially interactive graphs. But there are a few problems with that approach:
    The MatLab IDE is overwhelmingly slow to startup and to compile and run programs on every machine I have ever run it on. MatLab, while somewhat popular in certain fields, is rather esoteric in that I couldn't share my code widely and expect people to readily understand what it does. MatLab is rather expensive, at $149 USD initial cost for the "Home" version, $45 USD for additional "toolboxes" (which are just libraries), and a $100 USD yearly fee if you want updates.  
    So I set out to find a cheaper alternative, with a much wider user base, that includes similar tools and libraries, and is built on a widely known language. Of course, I turned to Python. Problems with the open source community having multiple, disjoint, and sometimes incompatible solutions to the same problems aside, I happened to stumble upon Anaconda and it's repository, an IDE called Spyder (which openly seeks to be similar to MatLab), a group of visualization libraries organized under the PyViz group, and a light and fast IDE for quick experiments; VS Code.

    Well, after retouching my Python skills after years of neglect (version 3.6 was on the horizon the last time I used Python), I installed VS Code and started working on some personal project. Today, while installing Conda to get ready to set up a full environment to replace MatLab, I started reading through their repository listings. In their table of libraries, they have a column for "License". So, after years of refusing to care about license agreements, I did what any person who's waiting on something to install would do: I started reading.

    The BSD 3-clause license
     
    The license, which has the text:
    Is a rather common open source license agreement which would allow users of the product to freely distribute it provided that some conditions are met:
    Any distribution of source code must also share your license Any distribution of an executable must also contain the BSD 3-clause. You cannot claim that the creators of the product endorse your product.  
    Well, I have a few gripes with this. And some of these gripes are common across many licenses. I'm not sure of the best way to go about stating them, so I'll just list them below.
    If you want your code to be actually useful, don't demand that users of your library maintain a list of license agreements for what's presumably sharable software. The second clause is ambiguous. Does it mean "Your binaries must contain metadata that describes this license", or does it mean that, upon running the executable, a reasonable attempt has been made to inform the user that they are using the product under this license? That ambiguity alone is enough to merit it's own gripe. If the first, what is the point? Very few people go around downloading executables and then reading the binary files associated with them. This is a useless requirement. If the latter, that's just conceited. If you expect someone who uses your code in their product to go around advertising you, you will surely be saddened when you find that no useful products use your code. The third clause is kind of a weird one. Clauses one and two are all about how you are required to give the creators of the software credit in your application. But the third clause is all about how the creators of the software don't want anything to do with your application. Presumably, what this actually means is "If your product is popular and agreed with, I want to be tied to it. But if, on the other hand, your product is a matter of public contention, I would like to be able to distance myself from it."  
    Which brings me to the major point of this post:
    Sharable software shouldn't be restricted in use. Don't force your users into some ethical contract hidden behind notions of "freely sharing" useful applications.

    For your reference, this is, in my opinion, the only useful license to use on projects that you wish to be usable by others. It is a modified version of the MIT License:
     
×