Every Program There Is, Part One

re: Every Program There Is, Part One

PARTO — Sun, 23 Oct 2011 15:06:24 GMT

you genius bro, could you tell me how you design your mind set to under how computer work

re: Every Program There Is, Part One

pete.d — Wed, 28 Apr 2010 06:43:56 GMT

Is it just me, or do these recent articles have thematic similarity to topics found in Hofstadter's book "Gödel Escher Bach"? I feel like it's 25 years ago and I'm exploring recursive infinities all over again!

Or, wait…oh no! Am I _in_ a recursive infinity myself? Aaaaahhhh…

re: Every Program There Is, Part One

Todd — Tue, 27 Apr 2010 21:10:13 GMT

The program my boss told me to write?

What about a program that writes the program my boss told me to write? Would the effort I'd put into specifying the program be less than the effort of writing the program?

re: Every Program There Is, Part One

Joe — Tue, 27 Apr 2010 18:24:08 GMT

Sorry, didn't mean to steal your thunder! Thought you were going to move in a different direction with "Next time: addition causes ambiguity."

re: Every Program There Is, Part One

Steve — Tue, 27 Apr 2010 14:28:37 GMT

I feel like I'm back in Automata class.

Nice post!

re: Every Program There Is, Part One

Joe — Tue, 27 Apr 2010 06:31:43 GMT

>> If we could find a way to enumerate all members of this grammar we’d be in good shape.

Couldn't you enumerate over the number of productions? Ie:

Given: A grammar and a string representing a possible result of (n) productions

Desired: A list of strings containing all possible results of applying one further production

IEnumerable<string> GetProductions(Grammar G, string Input)
{
    return from nonTerm in G.FindNonTerminals(Input)
    // nonTerm: label and position of NonTerminal in Input
       from rule in G.GetRules(nonTerm.Label)
    // grammar rules having nonTerm.Label as their left hand side [ Rules in CFG: NT => (NT | T)* ]
       select G.ApplyProduction(Input, nonTerm, rule.Replacement); // string substitution of nonTerm.Label at nonTerm.Position with rule.Replacement in Input
}
IEnumerable<string> GetProductions(Grammar G, IEnumerable<string> Inputs)
{
return Inputs.SelectMany((input) => GetProductions(G, input));
}
IEnumerable<string> AllProductions(Grammar G, int Length)
{
if(Length == 0) return new string[] { G.StartSymbol };
return GetProductions(G, AllProductions(G, Length - 1));
}
IEnumerable<string> AllSentences(Grammar G, int Length)
{
return from value in AllProductions(G, Length) where G.IsTerminated(value);
}

For this grammar we would have:

n = 0: S

n = 1: { X } , { }

n = 2: { X X } , { { X } }, { { } }

...

You have prematurely anticipated my denouement, Commander. -- Eric

re: Every Program There Is, Part One

Eamon Nerbonne — Tue, 27 Apr 2010 06:21:28 GMT

Great twist on the last post, this! :-)

re: Every Program There Is, Part One

Lucas McCoy — Tue, 27 Apr 2010 00:58:46 GMT

The first example you gave: `{{}{{}}}` reminds me of a plugin I use every day (in Gedit).

It's called zen-coding, basically you type something like:

div#nameOfMyCalss>ul.nameOfMyId>li*5>a

and it turns it into this (not sure if this will show up since it's HTML so I'll replace <> with these {}):

{div class="nameOfMyClass"}

{ul id="nameOfMyId"}

{li}{/li}

{/ul}

{/div}

Anyway thats what it made me think of. Also after reading your post I now want to read through some of their code and see how they implemented it.

Awesome post BTW!

re: Every Program There Is, Part One

Bahbar2 — Mon, 26 Apr 2010 21:07:30 GMT

Err... you're mixing up nonterminals and terminals in the last part. You always end up with 7 _terminals_. Yeah, I'm not the one who swore.

re: Every Program There Is, Part One

Bahbar — Mon, 26 Apr 2010 21:04:20 GMT

@TheCPUWizard: Well, the "nothing" concept shows up quite often in BNFs. But since Eric called this CFG, I guess I'll let him define what's valid. That said, Eric, there are _3_ non-terminals, not 2. I'm done picking nits now. I swear.