| --- Log opened Sat Nov 18 00:00:12 2006 |
| 00:05 | <@Vornicus> | items = File(item_file).readlines; set = File(index_file).reject { |line| line =~ /^#/ }.map { |line| items[line.to_i] } |
| 00:05 | <@Vornicus> | even better. |
| 00:06 | < MyCatOwnz> | What language is that? It looks vaguely functional and OO-ish. |
| 00:06 | <@Vornicus> | Ruby |
| 00:07 | <@Vornicus> | I probably got a bit of it wrong though |
| 00:07 | < MyCatOwnz> | Oh, sweet. |
| 00:07 | < MyCatOwnz> | Wonder why we use the term "language" for computer programming, anyway? |
| 00:07 | < MyCatOwnz> | Wouldn't "notation" be more accurate? |
| 00:07 | <@Reiver> | Ruby allows semicolons and braces? |
| 00:08 | <@Reiver> | No, because it's a language, not a symbol set. |
| 00:08 | <@Reiver> | It's just a language which has a tendancy to have very arcane and verbose phrases. |
| 00:08 | <@Vornicus> | Yes. |
| 00:08 | <@Vornicus> | In fact Ruby is the only language I know that uses all the standard ascii symbols for /something/ |
| 00:09 | <@Reiver> | ! |
| 00:09 | <@Reiver> | What about ~? |
| 00:09 | <@Vornicus> | ~ is bitnot and is also used in =~ and !~, which are used primarily as regex matching. |
| 00:10 | < MyCatOwnz> | And \? Also, ¬? |
| 00:10 | < MyCatOwnz> | `';:, too? |
| 00:10 | <@Vornicus> | \ is common in many languages to say "this statement doesn't end at the end of this line" and also to say "this character should not be taken literally" |
| 00:11 | <@Vornicus> | the "not" symbol is not standard ascii |
| 00:11 | <@Vornicus> | ` is used to delimit system calls; `foo` acts as a string that holds the stdout result of calling "foo" from the shell. |
| 00:11 | <@Vornicus> | ' is used for strings that you don't want to interpolate. |
| 00:12 | <@Vornicus> | ; delimits statements. |
| 00:12 | <@Vornicus> | : is used as the second operand in the ternary choice operator: a?b:c returns b if a is true and c otherwise. |
| 00:13 | <@Vornicus> | Come on, ask me about some hard ones. |
| 00:14 | < MyCatOwnz> | £? ^_^ |
| 00:14 | <@Vornicus> | also not a standard ascii symbol |
| 00:14 | < MyCatOwnz> | Hence the sarcy smiley. |
| 00:14 | < MyCatOwnz> | Underscore? |
| 00:15 | <@Reiver> | ^ ? |
| 00:15 | <@Reiver> | $ @ |
| 00:16 | <@Vornicus> | _ is common in names; in addition, you can use _ as a grouping delimiter in numbers: 1_000_000 == 1000000 |
| 00:16 | <@Reiver> | ...nice |
| 00:16 | <@Vornicus> | $ and @ are used as "warts" for variables: foo is local, @foo is instance, @@foo is class, and $foo is global. |
| 00:17 | <@Reiver> | ^ |
| 00:18 | <@Vornicus> | ^ is, as usual, bitwise xor. |
| 00:18 | <@Reiver> | Right |
| 00:18 | <@Reiver> | Hm |
| 00:19 | <@Reiver> | & will be obvious, but syntax makes me curious |
| 00:19 | <@Vornicus> | ? can be used in names sometimes; also it denotes "the ascii value of the next character"; also it is the first operand in the ternary operator. !!???!!??:!?? is valid syntax, and returns "true" |
| 00:19 | <@Reiver> | # - comments? |
| 00:19 | <@Reiver> | ...What |
| 00:19 | <@Vornicus> | :D |
| 00:20 | <@Reiver> | a?b:c parsed. |
| 00:20 | <@Reiver> | That thing |
| 00:20 | <@Reiver> | Not so much. |
| 00:20 | <@Vornicus> | :D |
| 00:20 | <@Vornicus> | Okay, ! is logical not, right |
| 00:20 | <@Reiver> | Right |
| 00:20 | <@Vornicus> | and ?? is "the ascii value of ?" |
| 00:20 | <@Vornicus> | so !!?? is "not not the ascii value of ?", which is "true" |
| 00:20 | <@Vornicus> | then !!?? is again "true", and !?? is "false" |
| 00:21 | <@Vornicus> | so true?true:false returns true... |
| 00:21 | <@Vornicus> | so therefore !!???!!??:!?? returns true. |
| 00:21 | <@Vornicus> | irb(main):002:0> !!???!!??:!?? |
| 00:21 | <@Vornicus> | => true |
| 00:21 | <@Vornicus> | # is used as comments and also to refer to methods that classes possess without calling them. |
| 00:21 | <@Reiver> | How sneakily verbose. |
| 00:22 | < MyCatOwnz> | Commas? |
| 00:22 | <@Vornicus> | & is bitwise and; && is logical and; &block is "pull a block passed to this method into this variable" |
| 00:22 | <@Vornicus> | , is used, of course, to delimit lists. |
| 00:22 | <@Vornicus> | [2, 3, 5] |
| 00:23 | < MyCatOwnz> | Sorry, what were backticks '`' again? |
| 00:23 | <@Vornicus> | ` is used for system calls. |
| 00:23 | | Janus [~Cerulean@Nightstar-10302.columbus.res.rr.com] has joined #Code |
| 00:23 | < MyCatOwnz> | Ah, yes. |
| 00:24 | < MyCatOwnz> | I presume they came up with different uses for '' and ""? |
| 00:24 | <@Vornicus> | '' and "" are strings without interpolation and strings /with/ interpolation. |
| 00:25 | <@Vornicus> | "" strings may contain a thing like "#{foo}" and it will execute the code inside the {} and place its return value into the string. |
| 00:28 | | Ev3 [~-@87.72.36.ns-26407] has joined #Code |
| 00:36 | <@Vornicus> | (which, by the way, is another use for #) |
| 00:38 | <@McMartin> | The more I see of Ruby, the less I understand its appeal. |
| 00:38 | <@Vornicus> | Idunno. it just seems to make sense to me |
| 00:39 | | * McMartin has added "The language is LL(1)" to the list of Reasons He Likes Python. |
| 00:39 | <@Vornicus> | heh |
| 00:40 | <@Reiver> | LL(1)? |
| 00:40 | < MyCatOwnz> | IIRC, doesn't that mean it can be parsed by a push-down automaton? |
| 00:43 | < MyCatOwnz> | Equivalently it means that it's a context-free language. Like C is, but C++ isn't. |
| 00:44 | <@Vornicus> | LL(1) means that it's really easy to write a parser for it. |
| 00:45 | < MyCatOwnz> | Vornicus: that's what I said! ;) |
| 00:48 | <@McMartin> | LR(k) is "can be parsed by a Push-down automaton" |
| 00:49 | <@McMartin> | LL(1) is much, much, much more restrictive. |
| 00:49 | <@McMartin> | Also note that C++, despite not being parsable by a PDA, is parsable via Recursive Descent, which is what LL(k) generally uses. |
| 00:49 | <@McMartin> | C++ is not LL(k) though. |
| 00:50 | <@McMartin> | (LL(1) means that, on one token of lookahead, you know what the next statement is going to be. LR(1) means that on 1 token of lookahead you know what the last statement was.) |
| 00:50 | <@McMartin> | (LALR is LR, but with some simplifying assumptions that break things that don't come up often.) |
| 00:51 | < MyCatOwnz> | Ohhhh, oops. Thinking of the wrong thing entierly. I was thinking of type0/1/2/3 languages. |
| 00:52 | <@McMartin> | All of these are, IIRC, Type 1. |
| 00:52 | <@McMartin> | Except C++, which is Type 2, or Type 3 if you allow unlimited template expansion. |
| 00:52 | | * Reiver wonders vaugely what Types are. |
| 00:52 | < MyCatOwnz> | Type 2, considering that most people don't like their compiles to take more than, say, twenty minutes for a single file =) |
| 00:53 | < MyCatOwnz> | Reiver: type 0 = finite state machine parsable |
| 00:53 | < MyCatOwnz> | Reiver: type 1 = stack machine parsable |
| 00:53 | <@McMartin> | Reiver: Type 0 is regular expressions (without backreferences). Type 1 is CFGs. Type 3 is Turing-decidable. |
| 00:53 | <@McMartin> | TYpe 2 is everything else~ |
| 00:53 | < MyCatOwnz> | Reiver: type 3 = Turing machine |
| 00:53 | < MyCatOwnz> | Reiver: type 2 = like a Turing machine, but with a finite amount of memory. |
| 00:54 | < MyCatOwnz> | We normally like to think of our computers as being Turing machines, but actually they're all type 2's rather than type 3. |
| 00:54 | < MyCatOwnz> | Since, y'know, no one has ever actually gotten around to building an infinite DIMM yet. |
| 00:54 | <@McMartin> | We code as if they were Type 3, generally. |
| 00:55 | <@McMartin> | As I understand LBAs, they assume the memory is a linear function of the size of the input. |
| 00:55 | < MyCatOwnz> | McMartin: and then we cross our fingers and hope we don't run out of swapfile space =) |
| 00:55 | <@Reiver> | Are we ever proven wrong, with the exception of bugs?~ |
| 00:55 | <@McMartin> | Resource exhaustion, Reiver, not bugs. |
| 00:55 | < MyCatOwnz> | McMartin: yes, they do. |
| 00:55 | <@McMartin> | I guess you can say "1 GB per byte of input! It's still LBA!" |
| 00:55 | <@McMartin> | But then the verification community gets sad. |
| 00:55 | < MyCatOwnz> | Yep. |
| 00:56 | <@Vornicus> | ...madness |
| 00:56 | <@McMartin> | This is also, idly, why you don't see much mention of Type 2. |
| 00:56 | < MyCatOwnz> | OTOH, you could sort-of-justify it by saying that the amount of computing resources anyone will be willing to buy is proportional to the amount of data they have to process =) |
| 00:56 | <@McMartin> | Not really |
| 00:57 | <@McMartin> | People run polynomial and even EXPTIME algos all the time. |
| 00:57 | <@McMartin> | Just for smaller ns. |
| 00:57 | < MyCatOwnz> | Aye, true. |
| 00:57 | <@McMartin> | Also, I didn't learn it as type 0/1/2/3, I learned it as "regular/context-free/context-sensitive/recursively enumerable" |
| 00:57 | <@McMartin> | But "context-sensitive" is very fuzzily defined. |
| 00:57 | <@McMartin> | And usually doesn't mean "LBAs accept them", though they do. |
| 00:58 | <@McMartin> | It's usually something more restricted, like "CFGs + Intersection" |
| 00:58 | < MyCatOwnz> | CFG is Context Free Grammar, right? |
| 00:58 | <@McMartin> | Yes. |
| 00:59 | <@McMartin> | CFL is Context-Free Language. |
| 01:00 | < MyCatOwnz> | Sorry, what's the distinction between CFLs and CFGs, please? |
| 01:00 | < MyCatOwnz> | I'm halfway through reading "The New Turing Omnibus" but I'm not a very attentive reader =) |
| 01:06 | <@McMartin> | There isn't much of a difference. |
| 01:06 | <@McMartin> | If challenged to provide one, I would hazard that the the CFL is the set of all strings the CFG accepts or can generate. |
| 01:06 | <@McMartin> | So, say, C is a CFL, but it has a CFG. |
| 01:07 | <@McMartin> | Well, actually, I'm not positive C is a CFL. |
| 01:07 | <@McMartin> | The set of all balanced parenthesis strings is a CFL. |
| 01:07 | <@McMartin> | And various CFGs will recognize it. |
| 01:07 | | * MyCatOwnz nods. |
| 01:07 | <@McMartin> | This is pointless hairsplitting, though. |
| 01:08 | <@McMartin> | And I'm a grad student in compilers, so I say this with great authority! |
| 01:08 | <@McMartin> | Possibly not a hell of a lot of justification, but hey |
| 01:08 | < MyCatOwnz> | So, a CFG is a ruleset, a CFL is the set of all strings that satisfies the CFG. |
| 01:08 | < MyCatOwnz> | s/the CFG/some CFG |
| 01:09 | <@McMartin> | Well, I mean, a grammar and a language are different things, but they end up being more or less equivalent in practice |
| 01:10 | < MyCatOwnz> | I suppose it could become important in the case where you, say, try to work out whether you can write a grammar for a type 0/1/2/3 using a type 0/1/2/3 :) |
| 01:10 | < MyCatOwnz> | As in, "can we specify the entire set of CFGs in another CFG?" |
| 01:10 | <@McMartin> | Yeah, it's called "yacc's grammar" |
| 01:11 | <@McMartin> | ... actually, traditional CFG grammar might even be regular |
| 01:14 | <@Vornicus> | BNF! |
| 01:14 | <@McMartin> | Yeah. |
| 01:15 | <@McMartin> | {ID} :- {ID}+ |
| 01:15 | <@McMartin> | And ID names are regular expressions |
| 01:15 | < MyCatOwnz> | o_O |
| 01:16 | <@McMartin> | Usually ([a-zA-Z0-9]+) | (<[a-zA-Z0-9]+>) |
| 01:16 | <@McMartin> | And then one or more of the pattern I gave above. |
| 01:16 | <@McMartin> | So, Type 1 languages can be specified by a Type 0 language. |
| 01:16 | < MyCatOwnz> | So, here's the thing. BNF is type 0, we can use it to specify C's grammar, which is type 2. |
| 01:17 | < MyCatOwnz> | Er, type 1. |
| 01:17 | <@McMartin> | Yes. |
| 01:17 | < MyCatOwnz> | Or is it type 2? I'm not sure. |
| 01:17 | <@McMartin> | I'm assuming here it's type 1. |
| 01:17 | < MyCatOwnz> | It does have nested function calls and the like, which I don't think a push-down machine can do 'cuz it can't backtrack on its tape. |
| 01:17 | | * Vornicus wonders how complicated the original C++ preprocessor was |
| 01:17 | < MyCatOwnz> | Vornicus: a huge mess, probably. |
| 01:18 | <@Vornicus> | Well, yes |
| 01:18 | <@McMartin> | Um? Nested expressions in a CFG is easy |
| 01:19 | <@McMartin> | It's what CFGs are, in a sense, for |
| 01:19 | < MyCatOwnz> | No, wait, C doesn't have any form of recursion. What am I thinking? C is type 1, you're right. |
| 01:19 | <@McMartin> | You can do recursion in a CFG. |
| 01:19 | < MyCatOwnz> | Sorry, I just mixed up the C compiler with the C programs. Oopsie. |
| 01:19 | <@McMartin> | Anything with infix algebra has recursion. |
| 01:20 | <@McMartin> | In the expr :- expr + expr | expr - expr | expr * expr | ( expr ) sense |
| 01:20 | <@McMartin> | The mere fact that there's an expr :- ( expr ) production means it's at least type 1 |
| 01:20 | < MyCatOwnz> | McMartin: yes, but you can't send the compiler (not counting that the preprocessor is Turing-complete) into an infinite loop, handily. |
| 01:20 | <@McMartin> | As it happens, Java is absolutely Type 1, because the CFG for it is published in the language spec. |
| 01:20 | <@McMartin> | Which is right here next to me. |
| 01:20 | < MyCatOwnz> | I mean, you can't send the compiler into any form of recursion whatsoever. So yeah, C is type 1, obviously. |
| 01:21 | <@ToxicFrog> | ...umm. |
| 01:21 | <@ToxicFrog> | The compiler will by definition recurse if it's recursive-descent. |
| 01:22 | <@ToxicFrog> | I think you mean you can't make it livelock unless the compiler itself is broken. |
| 01:22 | <@McMartin> | Yeah. Having a possibly-recursive call-stack is why you need a PDA in the first place. |
| 01:22 | < MyCatOwnz> | How do you get the C compiler to recurse? |
| 01:22 | <@ToxicFrog> | That's how it works. |
| 01:23 | | * Vornicus points out that it's rather the right way to do it. |
| 01:23 | <@ToxicFrog> | And how recursive-descent compilers work in general, just like it says on the box. |
| 01:23 | < MyCatOwnz> | ...what am I missing here? |
| 01:23 | <@Vornicus> | YOu're conflating recursion with livelock. |
| 01:23 | <@McMartin> | You get a C compiler to recurse by parsing any arithment expression at all. |
| 01:24 | <@Reiver> | 'conflate'? |
| 01:24 | <@McMartin> | parse_expr() will be called recursively several times when parsing the expression ((1+2)*(3+4)). |
| 01:24 | <@McMartin> | Also, the Java grammar. http://java.sun.com/docs/books/jls/third_edition/html/syntax.html#18.1 |
| 01:24 | <@Vornicus> | to mix together, generally wrongly |
| 01:24 | <@ToxicFrog> | Reiver: "consider equivalent to each other", roughly |
| 01:24 | < MyCatOwnz> | Vornicus: k. |
| 01:24 | <@ToxicFrog> | With connotations of incorrectness. |
| 01:24 | <@Reiver> | Vorn: ...How amusing |
| 01:25 | <@ToxicFrog> | And yeah, recursion != livelock. |
| 01:25 | <@Reiver> | I'd mentally parsed it as a blending of 'conflict' and 'confuse'. |
| 01:25 | <@Vornicus> | ...interestingly enough, that actually works. :) |
| 01:25 | <@Reiver> | ...And then it means to mix together, generally wrongly... <g> |
| 01:26 | < MyCatOwnz> | Okay, I'm using completely wrong terminology. You can't get a C compiler to recursively parse the same piece of code twice? Would that be the right way to phrase it? |
| 01:26 | <@McMartin> | That's an implementation detail. |
| 01:26 | < MyCatOwnz> | As in, the C compiler will never (unlike the C++ compiler) be tricked into trying to do: expr1 = something + expr2; expr2 = something + expr1; |
| 01:26 | <@McMartin> | It isn't necessary to use anything other than a push-down automaton to parse it. Probably. If I'm right about it being Type 1. |
| 01:27 | < MyCatOwnz> | Whereas you can trick the C++ compiler into doing that using template instantiation. |
| 01:27 | <@ToxicFrog> | I think what you mean is "you can't get the C compiler to infinitely loop parsing the same expression over and over again on any input" |
| 01:27 | <@ToxicFrog> | (left-recursive grammars for the lose) |
| 01:27 | < MyCatOwnz> | ToxicFrog: better'n I could've said it myself! I should know, I tried to about five times in a row =) |
| 01:27 | <@ToxicFrog> | And as far as I know this is in fact the case, barring actual implementation errors in the compiler. |
| 01:27 | <@McMartin> | (LALR parsers eat Left recursion just fine, thanks) |
| 01:28 | <@McMartin> | (In fact, they often prefer it) |
| 01:28 | <@ToxicFrog> | (point, but I've been working almost exclusively with LL parsers for the past year and a half) |
| 01:28 | <@McMartin> | (And with good reason. About the only place it stings is forcing left-associativity, which kinda needs left-recursion to specify right) |
| 01:28 | <@McMartin> | (And even there I solve it by not restricting myself to expr-trees with two children) |
| 01:29 | <@McMartin> | (My precedence_read() function is made of love and spiders *at the same time*) |
| 01:29 | < MyCatOwnz> | Wait, question. |
| 01:29 | <@McMartin> | (And I don't have it handy to show off just now. Some other time, perhaps) |
| 01:29 | < MyCatOwnz> | An LL(1) should be type 1, right? |
| 01:29 | <@ToxicFrog> | (remind me to ask you about it sometime) |
| 01:30 | <@McMartin> | Yes, LL(1) is a subset of type 1. |
| 01:30 | <@ToxicFrog> | Subset of type 1. |
| 01:30 | < MyCatOwnz> | Are all LL(k)'s subsets of type 1? |
| 01:30 | <@McMartin> | Yup. |
| 01:30 | <@ToxicFrog> | Yes. |
| 01:30 | <@McMartin> | As are all LALR(k)s and LR(k)s. |
| 01:30 | <@McMartin> | I believe but am not positive that LR(k) is the entirety of Type 1 languages. |
| 01:31 | <@McMartin> | In actual practice, you will only see LL(1), LL(k), and LALR(1). |
| 01:31 | <@McMartin> | Or, uh, non-type 1. |
| 01:33 | <@ToxicFrog> | MCO: also, it occurs to me that the phrase you were looking for earlier is "infinite recursion" |
| 01:33 | < MyCatOwnz> | ToxicFrog: I did use that at one point. |
| 01:34 | < MyCatOwnz> | "02:20 < MyCatOwnz> McMartin: yes, but you can't send the compiler (not counting that the preprocessor is Turing-complete) into an infinite loop, handily." |
| 01:36 | <@ToxicFrog> | Aah. I missed that. |
| 01:36 | <@ToxicFrog> | However, you then changed what you were saying to "any kind of recursion", which was confusing. |
| 01:36 | <@McMartin> | Also, it's worth pointing out that past Type 1, the distinctions that count are P, NP, PSPACE, EXPTIME, EXPSPACE. |
| 01:36 | <@McMartin> | And usually subdivisions within P. |
| 01:36 | <@McMartin> | But Type 1 recognition is O(n^3). |
| 01:37 | <@McMartin> | And Type 0 recognition is, if memory serves, actually O(n). |
| 01:37 | < MyCatOwnz> | McMartin: it is? |
| 01:37 | < MyCatOwnz> | McMartin: if T1 recognition is cubic, why the heck is a C compiler so fast? |
| 01:38 | <@ToxicFrog> | ...only compared to a C++ compiler. |
| 01:38 | <@McMartin> | Also, cubic is (a) worst-case, even with backtracking, and (b) cubic isn't that bad. |
| 01:38 | < MyCatOwnz> | ToxicFrog: I'm not sure if the C++ compiler even counts, given that it's easy to make it take O(infinity) |
| 01:39 | <@McMartin> | Cubic in depth of the parse tree means n is never going to get larger than, like, six. |
| 01:39 | <@McMartin> | Parsing LL(k) with a predictive parser is O(n). |
| 01:39 | < MyCatOwnz> | Oh, aight. |
| 01:39 | <@Vornicus> | Cubic is the speed of matrix multiplication |
| 01:40 | <@Vornicus> | And computers do a shitton of that. |
| 01:40 | < GeoTube> | a metric shitton! |
| 01:41 | < MyCatOwnz> | Vornicus: oh. I thought we had fancy-schmancy methods of quick matrix multiplication for taking advantage of special cases? |
| 01:41 | <@Vornicus> | Well, sure, there's special cases, but the general case is very common. |
| 01:42 | <@McMartin> | Unlike parsing, where the special cases are the only one anyone cares about. |
| 01:42 | < MyCatOwnz> | McMartin: so if I want to make a C compiler take hours, I can do so by handing it, say, an entire program laid out as a single expression? |
| 01:42 | <@McMartin> | Even then it might not work. |
| 01:43 | < MyCatOwnz> | Uhoh. Does it approach O(n) for unbalenced parse trees or something? |
| 01:43 | <@McMartin> | Pardon me, consulting with stuff |
| 01:43 | <@McMartin> | It has to do with the grammar's nature itself |
| 01:43 | <@Vornicus> | O(n) means that it takes a length of time proportional to the number of tokens, period. |
| 01:44 | <@McMartin> | Right. |
| 01:44 | < MyCatOwnz> | Vornicus: I've learnt big-O notation already :P. I was just asking if C parsing got a lot faster for any particular special cases. |
| 01:44 | <@McMartin> | Anything that's LL(k) for any k -- and I think C counts -- can be at least theoretically parsed in O(n) time. |
| 01:45 | <@McMartin> | gcc 4.0 tends to choke on switch statements with thousands of cases, but that's because of internal resource exhaustion. |
| 01:45 | <@McMartin> | Right, OK. |
| 01:45 | <@McMartin> | You have an input string of n terminals. |
| 01:45 | <@McMartin> | Every substring of this string has its own possible nonterminal that you could reduce to. |
| 01:45 | <@McMartin> | This grammar is, of course, obviously ambiguous as Hell. |
| 01:46 | <@McMartin> | But there's O(i^2) possible reductions at each step i, and checking for available reductions is also O(n). |
| 01:46 | <@McMartin> | So that comes out to n^3 in the end. |
| 01:48 | < MyCatOwnz> | Makes sense. |
| 01:52 | < MyCatOwnz> | And that's the upper bound for the entire set of type 1 languages, right? |
| 01:54 | <@McMartin> | Yes. |
| 01:55 | | Vornicus [~vorn@Nightstar-18307.slkc.qwest.net] has quit [Quit: ] |
| 01:57 | < MyCatOwnz> | I presume type 2's must have an upper bound of either exptime or infinity, I'm not sure which. |
| 02:00 | < MyCatOwnz> | You should be able to determine whether or not a type 2 halts within exponential time, since it'll have to either halt or repeat a symbol, some time between the zeroeth tick and the ((size ofalphabet)^(number of symbols))th, right? |
| 02:00 | <@McMartin> | Yes, LBAs will always eventually terminate, because infinite loops can be detected. |
| 02:00 | <@McMartin> | Only a finite number of possible memory/register configurations. |
| 02:00 | <@McMartin> | Once one repeats, the answer is NO. |
| 02:00 | <@McMartin> | Assuming you have a recognizer. |
| 02:00 | <@McMartin> | If it's a rejector, then the answer is YES. |
| 02:01 | <@McMartin> | (you have to not only have the same memory contents, you also need to have the head pointed at the same location, and the control automaton needs to be in the same state.) |
| 02:03 | < MyCatOwnz> | You could lump the processor's state in and define it as a part of the memory. |
| 02:03 | <@McMartin> | Probably, but that makes the description of how the machine works way less elegant~ |
| 02:06 | < MyCatOwnz> | Kinda. It'd work conceptually if you think of the processor as being vaguely like a FSM with a looping tape (carrying its state), wherein every full loop of the processor's tape is counted as one operation on the main tape. |
| 02:09 | <@McMartin> | Yeah, but Turing machines and PDAs are both defined as "an FSM plus X" |
| 02:10 | <@McMartin> | It's nice to have the LBA be the same |
| 02:10 | <@McMartin> | Mathematics tends to be a little light on implementation details, of course~ |
| 02:10 | < MyCatOwnz> | Heh. |
| 02:11 | <@McMartin> | Dinner, however, I must admit, would be Fairly Awesome about now. |
| 02:11 | < MyCatOwnz> | Mmmm, iono if a looping tape for the processor's state would be at all neccessary. |
| 02:11 | < MyCatOwnz> | I think you might be able to get some completely different language set by that method, though. |
| 02:12 | <@McMartin> | Hmm. Yes. That's a potentially self-modifying stored-program computer. |
| 02:12 | <@McMartin> | On the other hand, there's no limit to the number of states in the control automaton, normally. |
| 02:13 | < MyCatOwnz> | I was thinking of a vaguely fucked version of an FSM or a PDA... |
| 02:13 | <@McMartin> | (Also, the claim that all "Type 3" languages accepted by computers are secretly Type 2 isn't true. Anything that's, say, O(n^2) space requirements would be Type 3.) |
| 02:14 | <@McMartin> | (You can just fake it with an LBA for sufficiently small n.) |
| 02:14 | < MyCatOwnz> | McMartin: I'm not sure that I understand that statement, or at least not the reasons for it. |
| 02:14 | < MyCatOwnz> | Oh, nevermind. Thanks for the elaboration. ^_^ |
| 02:14 | <@McMartin> | A linear bounded automaton is, well, linearly bounded. |
| 02:15 | <@McMartin> | Something quadratic space is not really linearly bounded. |
| 02:15 | < MyCatOwnz> | Yeah. I should've just shut up 'cause you explained the part I wasn't sure on in the very next line of text. >< |
| 02:15 | <@McMartin> | And now, zomg dinnar. |
| 02:15 | < MyCatOwnz> | Bon appetit! |
| 02:23 | | Chalcedon is now known as ChalcyCleaning |
| 02:33 | | MyCatOwnz [~mycatownz@Nightstar-379.dsl.in-addr.zen.co.uk] has quit [Quit: Maybe I'm really asleep and this is all a biscuit.] |
| 02:49 | | Chalcy [~Chalceon@Nightstar-869.bitstream.orcon.net.nz] has joined #code |
| 02:49 | | mode/#code [+o Chalcy] by ChanServ |
| 02:51 | | ChalcyCleaning [~Chalceon@Nightstar-869.bitstream.orcon.net.nz] has quit [Ping Timeout] |
| 02:51 | | ChalcyGone [~Chalceon@Nightstar-869.bitstream.orcon.net.nz] has joined #code |
| 02:52 | | Chalcy [~Chalceon@Nightstar-869.bitstream.orcon.net.nz] has quit [Ping Timeout] |
| 03:00 | | ChalcyGone is now known as ChalcyCleaning |
| 03:11 | | Vornicus-Latens is now known as Vornicus |
| 03:13 | | Janus [~Cerulean@Nightstar-10302.columbus.res.rr.com] has quit [Quit: Jouets de Dieu, jouets de jouets, et les jouets de me, fait naître Clairvoire.] |
| 03:51 | | Stephenie [Safyra@Nightstar-4370.ok.ok.cox.net] has quit [Ping Timeout] |
| 03:56 | | Stephenie [Safyra@Nightstar-4370.ok.ok.cox.net] has joined #code |
| 03:58 | | Janus [~Cerulean@Nightstar-10302.columbus.res.rr.com] has joined #code |
| 04:04 | <@McMartin> | I still can't believe NSIS has as one of its features "A lovely coding experience with elements of PHP and assembly" |
| 04:06 | <@Raif> | What has this? |
| 04:06 | <@ToxicFrog> | NSIS. |
| 04:06 | <@ToxicFrog> | Nullsoft Scriptable Installer System. |
| 04:06 | <@Raif> | ahh. |
| 04:06 | | * Raif idly shakes a fist at Nullsoft. |
| 04:06 | | ChalcyCleaning is now known as ChalcyOut |
| 04:07 | <@ToxicFrog> | It would be a lovely means for creating windows installers, except for the almost complete lack of useful documentation and the programming language that can only be described as the bastard offspring of MC68K ASM and PHP, as the docs say. |
| 04:07 | <@Raif> | Though I do kinda wonder how they integrated PHP with assembly. |
| 04:07 | <@McMartin> | No real variables~ |
| 04:07 | <@ToxicFrog> | So far, the only way I've found of actually using it effectively is "take someone else's script and modify it" |
| 04:07 | <@McMartin> | TF: The sad thing is, it's still best of breed. |
| 04:08 | | * McMartin has written a fair amount of NSIS code of varying messiness for the UQM installers |
| 04:08 | <@ToxicFrog> | Yeah. |
| 04:08 | <@ToxicFrog> | I mean, the alternatives are...MSI, InstallShield, or roll-your-own. |
| 04:08 | <@McMartin> | Which is at least good enough to let you specify a package directory for pre-downloaded data, and net-install anything you don't have (or for which the MD5 sums don't match) |
| 04:08 | <@Raif> | ... |
| 04:08 | <@Raif> | Maybe I should write a new installer base. |
| 04:09 | <@Raif> | One that sucks not. |
| 04:09 | <@McMartin> | There's also the cygwin installer! |
| 04:09 | <@Raif> | Don't get my started on cygwin. |
| 04:09 | <@ToxicFrog> | McM: wait, you can pervert that for your own purposes? |
| 04:09 | <@McMartin> | Well, I can't. |
| 04:09 | <@ToxicFrog> | Because that would be really handy. |
| 04:09 | <@McMartin> | I can barely install cygwin with the damned thing. |
| 04:09 | <@ToxicFrog> | o.O |
| 04:09 | | * ToxicFrog has never had any problems with it |
| 04:10 | <@McMartin> | NSIS has sufficient automation that if all you want to do is mimic InstallShield/MSI, all you have to do is drag a bunch of files into NIS Edit. |
| 04:10 | | * Raif wonders what's so hard about installer technologies... at least on windows. |
| 04:10 | <@Raif> | It's basically registry keys and file copying. |
| 04:10 | <@McMartin> | That part's easy with everything. |
| 04:10 | <@ToxicFrog> | NISEdit? |
| 04:11 | <@McMartin> | If you want a selective web installer, or one that self-verifies to your spec... |
| 04:11 | <@ToxicFrog> | And, yeah, the cygwin installer is open source, but it's really not designed as a general installer platform. |
| 04:11 | <@McMartin> | TF: Their recommended script editing environment. |
| 04:11 | <@ToxicFrog> | It exists specifically to install Cygwin, and is thus a case of roll-your-own perpetrated by the Cygwin team. |
| 04:11 | <@McMartin> | Which has a wizard in which you fill in a couple of dialog boxes and it gives you a script that works out of the box. |
| 04:11 | <@ToxicFrog> | ...oh. |
| 04:11 | <@ToxicFrog> | Is this a recent development? |
| 04:12 | <@McMartin> | No, the UQM installers have been based on it since 0.3 |
| 04:12 | | * ToxicFrog cannot recall seeing such a thing when he did brutal combat with NSIS last summer |
| 04:12 | <@McMartin> | So, uh, 2003? |
| 04:12 | <@McMartin> | Latest version is from 2005. |
| 04:12 | <@ToxicFrog> | ...... |
| 04:12 | | * ToxicFrog vomits black bile from the eye sockets |
| 04:12 | <@McMartin> | Sable's installer just involved drag-and-dropping into NIS Edit's wizard. |
| 04:12 | < Stephenie> | o_O |
| 04:13 | <@ToxicFrog> | Hours I spend struggling with that thrice-bedamned language! |
| 04:13 | <@ToxicFrog> | Days! |
| 04:13 | <@McMartin> | http://nsis.sourceforge.net/HM_NIS_Edit -- which is linked right off of the download page. |
| 04:14 | <@McMartin> | NSIS actually ships with NSISdl these days, too. |
| 04:14 | <@ToxicFrog> | NSISdl? |
| 04:15 | <@McMartin> | The extension that lets you do web installs. |
| 04:15 | <@McMartin> | Which UQM requires, since a minimal install is 13M and a maximal one is ~500M. |
| 04:15 | <@ToxicFrog> | Aah. |
| 04:15 | | * ToxicFrog foams at the brain |
| 04:15 | <@ToxicFrog> | At least I now know what I'm putting the Spellcast installer together with, if it needs an installer. |
| 04:16 | <@ToxicFrog> | It doesn't use registry entries or anything, so it should be able to just get by with a tarball. |
| 04:16 | <@McMartin> | Yeah |
| 04:16 | <@McMartin> | NSIS automatically handles the registry entries required for showing up in Add/Remove programs. |
| 04:17 | | Thaqui [~Thaqui@Nightstar-23226.jetbuster.co.nz] has quit [Ping Timeout] |
| 04:19 | <@ToxicFrog> | I prefer being able to just delete the game directory and have it not leave registry entries lying around, personally. |
| 04:19 | <@ToxicFrog> | What with windows not having a proper package manager to rely on. |
| 04:20 | <@Raif> | No, it shall forever rely on the crutch of The Registry |
| 04:20 | <@Raif> | Actually "The Registry" sounds like one of those monolithic projects from the daily WTF. |
| 04:21 | <@ToxicFrog> | Well, The Registry is actually a useful idea in theory, and GNOME even implements something similar, the GConf database. |
| 04:22 | <@ToxicFrog> | The problem is that in addition to being used for stuff like application-specific configuration data, it's also used - as you said - as a crutch to half-ass stuff that should not be half-assed. |
| 04:22 | | ChalcyOut [~Chalceon@Nightstar-869.bitstream.orcon.net.nz] has quit [Ping Timeout] |
| 04:23 | | Chalcedon [~Chalceon@Nightstar-869.bitstream.orcon.net.nz] has joined #code |
| 04:23 | | mode/#code [+o Chalcedon] by ChanServ |
| 04:27 | <@Reiver> | What's it /do/, idly? |
| 04:27 | <@ToxicFrog> | Which, NSIS or the registry? |
| 04:27 | <@Reiver> | Registry. |
| 04:27 | <@Reiver> | Or more to the point |
| 04:27 | <@Reiver> | What was it /meant/ to do? |
| 04:28 | <@ToxicFrog> | It stores heirarchical key-value pairs. |
| 04:28 | <@Reiver> | I've not really delved into the theory of Windows, I more tend to be dealing with the explosions with a shovel afterwards. |
| 04:28 | <@ToxicFrog> | Keys are strings, values are strings, or raw data, or whatever the hell else you want to store. |
| 04:28 | <@Reiver> | OK. |
| 04:28 | <@Reiver> | Why? |
| 04:28 | <@McMartin> | So, it's /etc. |
| 04:29 | <@McMartin> | And in Win9x, also often all the user's dotfiles. |
| 04:29 | <@ToxicFrog> | McM: in NToids, too. |
| 04:29 | <@McMartin> | (In Win2k on, those go in Documents and Settings\User\Application Data) |
| 04:29 | <@ToxicFrog> | Not in my experience. |
| 04:29 | <@ToxicFrog> | Actual /data/ like save files goes there, yes. |
| 04:29 | <@ToxicFrog> | But configuration stuff is still stored in the registry. |
| 04:30 | <@McMartin> | You still see .inis. |
| 04:30 | <@ToxicFrog> | Under HKEY_LOCAL_MACHINE for system-specific configuration and HKEY_CURRENT_USER for user-specific. |
| 04:30 | | * McMartin nods |
| 04:30 | <@McMartin> | Ugh. OK, feel awful, heading hoome |
| 04:30 | <@McMartin> | home, even |
| 04:31 | <@ToxicFrog> | Anyways, Reiv, that's the basic idea. It's /etc with a consistent format and API. |
| 04:33 | | Thaqui [~Thaqui@124.197.36.ns-12825] has joined #code |
| 04:35 | | Chalcedon [~Chalceon@Nightstar-869.bitstream.orcon.net.nz] has quit [Ping Timeout] |
| 04:36 | <@Raif> | The problem with the registry is that pretty much everything you install takes a shit in it and forgets to clean up after itself when it gets uninstalled. |
| 04:37 | <@Raif> | Eventually, the more "clever" programs will modify OS configuration settings, particularly ones that Ought Not Be Messed With, and your Windows install will end up in a strange frankenstate. |
| 04:38 | <@Raif> | This is why windows experiences such rapid bitrot. |
| 04:38 | <@ToxicFrog> | Tes. |
| 04:38 | <@ToxicFrog> | *Yes. |
| 04:39 | <@ToxicFrog> | For added fun, if you delete something in a way it wasn't intended to be deleted (for example, it provides an uninstaller but you delete it by hand), this pretty much guarantees the registry entries don't get cleaned up. |
| 04:40 | <@ToxicFrog> | Some things will also accept the contents of the registry to be the gospel truth, so you end up with programs refusing to install because a previous, now long gone install left parts of itself in the registry. |
| 04:41 | <@ToxicFrog> | The way the add-remove programs part works is this, AIUI: |
| 04:41 | <@ToxicFrog> | - program installers are expected to provide their own uninstallers, and create special keys in the registry pointing to these uninstallers |
| 04:42 | <@ToxicFrog> | - Add/Remove programs goes through these keys and creates one entry for each key, and when the entry is selected it invokes the program pointed to by that key |
| 04:42 | <@ToxicFrog> | - no checks are made to see if the files referred to by the key still exist, and if they don't, or if the uninstaller forgets to remove the uninstall key itself, those keys are in the list and the registry until deleted by hand |
| 04:43 | <@ToxicFrog> | slwwp now |
| 05:05 | | Janus [~Cerulean@Nightstar-10302.columbus.res.rr.com] has quit [Quit: Jouets de Dieu, jouets de jouets, et les jouets de me, fait naître Clairvoire.] |
| 05:41 | | Thaqui [~Thaqui@124.197.36.ns-12825] has quit [Client exited] |
| 07:08 | | EvilDarkLord is now known as Jo}{n |
| 07:23 | | You're now known as TheWatcher |
| 08:08 | | AnnoDomini [~fark.off@Nightstar-29875.neoplus.adsl.tpnet.pl] has joined #Code |
| 08:31 | | Vornicus is now known as Vornicus-Latens |
| 09:30 | | You're now known as TheWatcher[afk] |
| 10:50 | | Jo}{n is now known as EvildarkLord |
| 10:50 | | EvildarkLord is now known as EvilDarkLord |
| 11:06 | | You're now known as TheWatcher |
| 11:19 | | You're now known as TheWatcher[afk] |
| 11:32 | | You're now known as TheWatcher |
| 12:46 | | AnnoDomini [~fark.off@Nightstar-29875.neoplus.adsl.tpnet.pl] has quit [Ping Timeout] |
| 12:52 | | AnnoDomini [~fark.off@Nightstar-29288.neoplus.adsl.tpnet.pl] has joined #Code |
| 13:54 | | Reiver is now known as ReivZzz |
| 14:12 | | Ev3 [~-@87.72.36.ns-26407] has quit [Ping Timeout] |
| 17:26 | | Ev3 [~-@87.72.36.ns-26407] has joined #Code |
| 17:29 | | AnnoDomini [~fark.off@Nightstar-29288.neoplus.adsl.tpnet.pl] has quit [Quit: Back promptly.] |
| 17:31 | | You're now known as TheWatcher[afk] |
| 17:32 | | AnnoDomini [~fark.off@Nightstar-29288.neoplus.adsl.tpnet.pl] has joined #Code |
| 17:56 | | EvilDarkLord [althalas@Nightstar-17046.a80-186-184-83.elisa-laajakaista.fi] has quit [Ping Timeout] |
| 18:01 | | Vornicus-Latens is now known as Vornicus |
| 18:05 | | EvilDarkLord [althalas@Nightstar-17046.a80-186-184-83.elisa-laajakaista.fi] has joined #code |
| 18:26 | | EvilDarkLord [althalas@Nightstar-17046.a80-186-184-83.elisa-laajakaista.fi] has quit [Ping Timeout] |
| 18:28 | | EvilDarkLord [althalas@Nightstar-17046.a80-186-184-83.elisa-laajakaista.fi] has joined #code |
| 18:39 | | Ev3 [~-@87.72.36.ns-26407] has quit [Ping Timeout] |
| 18:42 | | You're now known as TheWatcher |
| 18:53 | | * ToxicFrog gets the Join Game window working. |
| 18:54 | <@ToxicFrog> | ...wait, no I haven't, I forgot about player name. |
| 18:54 | <@ToxicFrog> | ;.; |
| 18:55 | <@Vornicus> | What game, what language? |
| 18:59 | <@ToxicFrog> | Spellcast, Lua, GTK+ |
| 19:01 | <@Vornicus> | aha |
| 19:01 | <@ToxicFrog> | I also accidentally deleted the About box code while shuffling things around, which wouldn't be a problem if I'd remembered to check it into svn ;.; |
| 19:02 | <@Vornicus> | heh |
| 19:04 | <@ToxicFrog> | ...hmm. GTKFrame doesn't implement pack_start_defaults. |
| 19:04 | <@ToxicFrog> | ;.; |
| 19:14 | | * ToxicFrog eyes UIJoinGame::Create^ClearWidget() |
| 19:14 | <@ToxicFrog> | Upvalues are not allowed to behave like that, dammit! |
| 19:15 | <@ToxicFrog> | Aughfljfsahsiyhhgkngfj |
| 19:18 | <@Vornicus> | ...heh |
| 19:18 | <@ToxicFrog> | So. The function is invoked as ClearWidget(this) |
| 19:18 | <@ToxicFrog> | this is userdata:0x98648e8 |
| 19:19 | <@ToxicFrog> | cleared is an upvalue with value table:0x983e2a0 |
| 19:19 | <@ToxicFrog> | cleared[this] is false. |
| 19:19 | <@ToxicFrog> | Just before it returns, it goes cleared[this] = true |
| 19:19 | <@ToxicFrog> | And then prints that, and yes, it is true. |
| 19:19 | <@ToxicFrog> | When the function gets called next it's false again. |
| 19:21 | < GeoTube> | maybe the variables are only kept temporary? |
| 19:21 | <@ToxicFrog> | That's not how upvalues or tables work. |
| 19:22 | < GeoTube> | right, just trying to help :/ |
| 19:27 | | Janus [~Cerulean@Nightstar-10302.columbus.res.rr.com] has joined #CODE |
| 19:28 | <@ToxicFrog> | ....oh you bastards. |
| 19:28 | <@ToxicFrog> | It's not passing in the actual userdata, it's passing in a table wrapped around it stuffed full of metamethods, including a custom __tostring. |
| 19:28 | <@ToxicFrog> | And this table is constructed on the fly so it's different every time, but it looks the same. |
| 19:29 | <@ToxicFrog> | So you can't use it as a table index and expect to be able to find it again. |
| 19:42 | <@ToxicFrog> | Behold! http://www.funkyhorror.net/toxicfrog/projects/spellcast/sc3_main.png http://www.funkyhorror.net/toxicfrog/projects/spellcast/sc3_join.png |
| 19:54 | <@ToxicFrog> | ...err |
| 19:54 | <@ToxicFrog> | http://www.funkyhorror.net/toxicfrog/projects/spellcast/screenshots/sc3_main.png |
| 19:54 | <@ToxicFrog> | http://www.funkyhorror.net/toxicfrog/projects/spellcast/screenshots/sc3_join.png |
| 19:54 | < GeoTube> | nice. |
| 19:55 | <@ToxicFrog> | This comprises perhaps 30% of the client and 0% of the server, not counting libsurtr itself~ |
| 19:56 | < GeoTube> | make sure you add anti-packet editing features <_< |
| 19:57 | | * ToxicFrog eyebrows |
| 19:57 | | * GeoTube eyebrows back |
| 19:58 | | AnnoDomini is now known as Saurivir |
| 19:58 | | EvilDarkLord is now known as Martivir |
| 20:16 | | Janus is now known as Jan[din] |
| 20:59 | | Jan[din] [~Cerulean@Nightstar-10302.columbus.res.rr.com] has quit [Quit: Jouets de Dieu, jouets de jouets, et les jouets de me, fait naître Clairvoire.] |
| 21:25 | | MyCatOwnz [~mycatownz@Nightstar-379.dsl.in-addr.zen.co.uk] has joined #code |
| 22:48 | | Janus [~Cerulean@Nightstar-10302.columbus.res.rr.com] has joined #code |
| 22:56 | | MyCatOwnz [~mycatownz@Nightstar-379.dsl.in-addr.zen.co.uk] has quit [Connection reset by peer] |
| 22:58 | | MyCatOwnz [~mycatownz@Nightstar-379.dsl.in-addr.zen.co.uk] has joined #code |
| 23:09 | | MyCatOwnz [~mycatownz@Nightstar-379.dsl.in-addr.zen.co.uk] has quit [Quit: Reboot, for the sake of another shoe.] |
| 23:17 | | MyCatOwnz [~mycatownz@Nightstar-379.dsl.in-addr.zen.co.uk] has joined #code |
| 23:52 | | MyCatOwnz is now known as MyCatGames |
| --- Log closed Sun Nov 19 00:00:12 2006 |