Fleeting Thoughts (CS Edition)

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 5497
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: Fleeting Thoughts (CS Edition)

Postby Thesh » Mon Oct 28, 2013 11:02 am UTC

After reading this, I decided to write my own stream cipher, just for the fun of it.

Spoiler:
Here's the breakdown of the components.
Internal state:

Code: Select all

typedef struct sc_state {
   uint32_t pos;
   uint32_t keystream;
   uint32_t key[64];
   uint32_t counter[32];
   uint32_t state[32];
} sc_state;


Constants:

Code: Select all

static const uint32_t r1[] = {
   13, 21,  1, 19, 29, 13, 15, 31,
    7, 23, 25, 19,  1, 17, 23,  5,
   31, 23,  3,  7, 13, 29, 21, 19,
   11, 15, 27,  7, 29,  7, 21, 27
};
static const uint32_t r2[] = {
   29, 25,  3, 15, 11,  3,  5, 15,
   11,  1, 19, 27, 21,  5, 31, 11,
   19,  1, 23,  1, 13, 15,  7,  5,
   21, 19, 11, 31, 19,  1, 13,  1
};
static const uint32_t e1 = 0xb7e15162;
static const uint32_t e2 = 0x8aed2a6a;
static const uint32_t pi[] = {
   0x243F6A88, 0x85A308D3, 0x13198A2E, 0x03707344,
   0xA4093822, 0x299F31D0, 0x082EFA98, 0xEC4E6C89,
   0x452821E6, 0x38D01377, 0xBE5466CF, 0x34E90C6C,
   0xC0AC29B7, 0xC97C50DD, 0x3F84D5B5, 0xB5470917,
   0x9216D5D9, 0x8979FB1B, 0xD1310BA6, 0x98DFB5AC,
   0x2FFD72DB, 0xD01ADFB7, 0xB8E1AFED, 0x6A267E96,
   0xBA7C9045, 0xF12C7F99, 0x24A19947, 0xB3916CF7,
   0x0801F2E2, 0x858EFC16, 0x636920D8, 0x71574E69
};


r1 and r2 are taken from the fractional portion of the square root of two (when represented as binary). I divided it into four bit pieces, eliminated any that were equal to the previous, and appended a 1 to make it a five-bit odd number. These are used for the rotation schedule. These are probably less than ideal, but chosen because I don't want to spend too much time on it.

e1 and e2 are the first and second 32 bits, respectively, of the fractional portion of e.
pi is the fractional portion of pi.

Mixing function:

Code: Select all

static void sc_mix(sc_state *state) {
   uint32_t i, prev;
   
   prev = state->state[31];

   for (i=0; i<31; i+=2) {
      state->state[i] ^= prev;
      state->state[i+1] += state->state[i];
      prev = state->state[i+1] = rotl(state->state[i+1],r1[i+1]);
   }
   prev ^= e1;

   for (i=0; i<31; i+=2) {
      state->state[i] += prev;
      state->state[i] = rotl(state->state[i],r1[i]);
      prev = state->state[i+1] ^= state->state[i];
   }
}


This is a pretty basic addition, rotation and xor function. It can be considered to have 32 rounds. It's chosen to be simple, but it's far from ideal. In a perfect world, the mixing would make every output bit dependent on every input bit, but this does not accomplish this. It's good enough for my purposes, however. The constant e1 serves two purposes: 1) it makes sure that even if the state is zero, after an iteration it will not be zero (it will be various rotations of e after one call to mix, but it will start looking fairly random after another call) and 2) it makes it so that I alternate between xor and addition, while swapping the order make sure that every word in the state has both an xor and

Code: Select all

static uint32_t sc_hash_state(sc_state *state) {
   uint32_t i, x = e2;
   
   for (i=0; i<31; i+=2) {
      x += state->state[i];
      x = rotl(x,r2[i]);
      x ^= state->state[i+1];
      x = rotl(x,r2[i+1]);
   }

   return x;
}

This is a one pass addition, rotation, and xor function. This can be considered 16 rounds, and does two rotations per round, as opposed to one like the previous function. The goal is simply to make sure the output depends on the entire state in a way that makes it difficult to determine the state.

Initialization:

Code: Select all

extern sc_state * sc_init(const uint32_t *key, size_t key_length, const uint32_t *iv, size_t iv_length) {
   size_t i;
   sc_state *state = (sc_state*)malloc(sizeof(sc_state));
   memcpy(state->state, pi, sizeof(pi));

   if (key_length > 32) key_length = 32;

   for (i=0; i<iv_length; i++) {
      state->state[0] ^= iv[i];
      sc_mix(state);
   }

   for (i=0; i<32; i++) {
      state->counter[i] = sc_hash_state(state);
      sc_mix(state);
   }

   for (i=0; i<key_length; i++) {
      state->key[i] = key[i];
      state->state[0] ^= key[i];
      sc_mix(state);
   }

   for (i = key_length; i<64; i++) {
      state->key[i] = sc_hash_state(state);
      sc_mix(state);
   }
   state->pos = 4;

   return state;
}

So, we use the array containing pi to initialize the state, this gets it nice and random looking, makes it harder to find keys or initialization vectors that result in a weak state. The key length is restricted to 1024 bits, the IV length is not restricted. The first thing we do Is mix the IV into the state by xoring it to the first element, and then running the mix function; the IV should never be reused, and this makes it so that the keystream is never repeated.

The next thing we do is initialize a 1024 bit counter from the state using the hash function, with a call to mix for every call to the hash. The counter is there to guarantee that the keystream has a period of at least 1024 bits.

The next step serves two purposes: it stretches the length of the key to 2048 bits, and it makes the state dependent on the key; up until this point, you can assume anyone knows the state. We mix the key in just like we did the IV, and we copy the key to a larger key array. Once the entire key has been mixed in, we use the hash function to append to the key.

This brings us to the final part of the function:

Code: Select all

static uint32_t sc_keystream_get(sc_state *state) {
   uint32_t i = 0;
   while((state->counter[i] += 1) == 0) i++;


   for (i=0; i<32; i++) {
      state->state[i] ^= state->counter[i];
   }
   
   sc_mix(state);

   for (i=0; i<32; i++) {
      state->state[i] ^= state->key[i];
   }

   sc_mix(state);

   for (i=0; i<32; i++) {
      state->state[i] ^= state->key[i+32];
   }

   return sc_hash_state(state);
}


The first thing we do is increment the counter; since this is a known value, we don't have to worry about timing attacks. If the counter was dependent on the key, a timing attack could possibly leak information about the key.

Next, the counter is XORd to the state, and the mix function is called. The next step is to XOR the first half of the key, and mix again. By XORing the key every time, we make it so that even if the attacker knows the state at one point, they cannot compute past or future outputs. We then XOR the second half of the key for further guarantee that the operation cannot be reversed by an attacker (after all, if the key is known, the mix function is bijective). We can now compute the hash and output it as four bytes of our keystream


I did some tests for randomness using ent and it appears as random as /dev/urandom, so that's a good sign. I provide no guarantees on the security of this algorithm, in fact I am not even happy with the mix function and rotation constants, but it was just a fun project to show how you can make a simple, efficient stream cipher that can evade anyone who hasn't spent a good deal of time studying cryptanalysis.

Source, if you are interested.
sc.tar.gz
(1.4 KiB) Downloaded 291 times
Honesty replaced by greed, they gave us the reason to fight and bleed
They try to torch our faith and hope, spit at our presence and detest our goals

User avatar
ahammel
My Little Cabbage
Posts: 2135
Joined: Mon Jan 30, 2012 12:46 am UTC
Location: Vancouver BC
Contact:

Re: Fleeting Thoughts (CS Edition)

Postby ahammel » Thu Nov 14, 2013 3:19 am UTC

So, string distance algorithms.

I'm trying to implement an extension of Damerau-Levenshtein distance where moving your hand to the wrong position on the keyboard counts as one operation:

Code: Select all

(dl-distance "test" "rwar")
=> 4
(bad-hand-position-distance "test" "rwar")
=> 1
Probably not worth it for the particular application I'm thinking of, but has anybody come across an implementation of such an algorithm?
He/Him/His/Alex
God damn these electric sex pants!

mr-mitch
Posts: 477
Joined: Sun Jul 05, 2009 6:56 pm UTC

Re: Fleeting Thoughts (CS Edition)

Postby mr-mitch » Thu Nov 14, 2013 6:28 am UTC

ahammel wrote:So, string distance algorithms.

I'm trying to implement an extension of Damerau-Levenshtein distance where moving your hand to the wrong position on the keyboard counts as one operation:

Code: Select all

(dl-distance "test" "rwar")
=> 4
(bad-hand-position-distance "test" "rwar")
=> 1
Probably not worth it for the particular application I'm thinking of, but has anybody come across an implementation of such an algorithm?


What if the distance changes? For example, "test", "rwat"?

User avatar
somehow
Posts: 99
Joined: Wed Aug 14, 2013 8:31 pm UTC

Re: Fleeting Thoughts (CS Edition)

Postby somehow » Thu Nov 14, 2013 2:17 pm UTC

You could look at how wrong it is in the normal sense from each possible hand-position shift, and take the minimum of those. So in this case: if you look at "test"/"rwat" from the normal hand position you get 3 (every letter but the final 't' has been replaced by another); if you look at "test"/"rwat" from the shift-one-to-the-left hand position you get 1 (given the hand-position shift, only the final 't' is wrong) plus 1 for the shift itself; etc.

I don't know if that matches what you want, ahammel, but it's an idea.
Xenomortis wrote:O(n2) takes on new meaning when trying to find pairs of socks in the morning.

User avatar
ahammel
My Little Cabbage
Posts: 2135
Joined: Mon Jan 30, 2012 12:46 am UTC
Location: Vancouver BC
Contact:

Re: Fleeting Thoughts (CS Edition)

Postby ahammel » Thu Nov 14, 2013 3:30 pm UTC

All the Damerau-Levenshtein edits are still legal, so (distance "test" "rwat") would be 2: one hand position shift and one substitution (or, equivalently, two hand position shifts). An added layer of complexity would be to allow, for instance, the left hand to be in the wrong position but the right hand in the correct one, so that (distance "hall" "gakk") is 1.
He/Him/His/Alex
God damn these electric sex pants!

mr-mitch
Posts: 477
Joined: Sun Jul 05, 2009 6:56 pm UTC

Re: Fleeting Thoughts (CS Edition)

Postby mr-mitch » Thu Nov 14, 2013 3:59 pm UTC

Ah, I understand now.

In that case, it would be just like edit distance, except for each cell in the table you store the edit distance for each (so far valid) offset.

User avatar
3rdtry
Posts: 152
Joined: Sat Feb 16, 2013 1:46 pm UTC

Re: Fleeting Thoughts (CS Edition)

Postby 3rdtry » Wed Nov 27, 2013 2:11 pm UTC

I'm glad this thread has reached page 2. And it only took 9 months!

Breakfast
Posts: 117
Joined: Tue Jun 16, 2009 7:34 pm UTC
Location: Coming to a table near you

Re: Fleeting Thoughts (CS Edition)

Postby Breakfast » Fri Jan 10, 2014 6:22 pm UTC

3rdtry wrote:I'm glad this thread has reached page 2. And it only took 9 months!

And since it's been about two months since that post...

I recently worked on an algorithm for a cyclic object graph traversal at work and after some intense thinking and overly complex solutions I came up with something that's pretty simple and lets me use the strategy pattern to plug in different operations to perform on the graph. Now that I've solved the problem on my own and feel pretty good about myself, are there any algorithms around that would have made my life a lot simpler?

User avatar
Jplus
Posts: 1692
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

Re: Fleeting Thoughts (CS Edition)

Postby Jplus » Sat Jan 11, 2014 5:20 pm UTC

There might. What exactly do you mean by "cyclic object graph traversal"?
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

Breakfast
Posts: 117
Joined: Tue Jun 16, 2009 7:34 pm UTC
Location: Coming to a table near you

Re: Fleeting Thoughts (CS Edition)

Postby Breakfast » Sun Jan 12, 2014 2:05 pm UTC

Jplus wrote:There might. What exactly do you mean by "cyclic object graph traversal"?

I mean walking a graph that has cycles (and not infinitely recursing around the cycles). The object part of it was that it was made up of a bunch of instantiated classes that needed to be ordered and operated on. Nodes could have multiple parents and couldn't be operated on until all their parents had been. Looking at it now, a topological sort might have done it.

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: Fleeting Thoughts (CS Edition)

Postby korona » Sun Jan 12, 2014 6:13 pm UTC

If you have a DAG then topological sorting will do the trick. If you have a graph with a (directed) cycle the problem has no solution. (?)
Depth first search is the most commonly used graph traversal algorithm.

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Fleeting Thoughts (CS Edition)

Postby troyp » Sun Jan 12, 2014 10:29 pm UTC

korona wrote:If you have a DAG then topological sorting will do the trick. If you have a graph with a (directed) cycle the problem has no solution. (?)

But the problem is almost identical to topological sort. It's just instead of terminating when you find a loop you ignore the loop-closing edge and continue.
Depth first search is the most commonly used graph traversal algorithm.

Yeah, a modified DFS that marks visited nodes to avoid closing loops seems like the simplest solution (if I'm understanding the problem correctly).

User avatar
somehow
Posts: 99
Joined: Wed Aug 14, 2013 8:31 pm UTC

Re: Fleeting Thoughts (CS Edition)

Postby somehow » Mon Jan 13, 2014 12:52 am UTC

That's what I thought, at first, but the way the problem is stated doesn't even really apply to cyclic graphs. That is, in a cyclic graph it's impossible to give an ordering of the nodes in which no node is visited until all of its parents have been visited, which is what Breakfast appears to want. ("Nodes could have multiple parents and couldn't be operated on until all their parents had been.") Or am I misunderstanding the problem?
Xenomortis wrote:O(n2) takes on new meaning when trying to find pairs of socks in the morning.

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Fleeting Thoughts (CS Edition)

Postby troyp » Mon Jan 13, 2014 7:01 am UTC

That's certainly true taking it literally, but to me it seemed clear that the "parents first" rule wasn't meant to apply to the cycle_noden->cycle_node1 relation. Ie. when the algorithm doesn't follow an edge (because it would create a loop), it also doesn't count that edge as a parent relation.

Mind you, saying that makes me realise that the algorithm wouldn't have the parent information when it needs it. (Plus it doesn't explicitly deal with multiple parents.)

Let's see...
  • Get rid of cycles using a strongly connected component algorithm. Each SCC can be ordered internally however you like. The resulting graph (merging each SCC into a single node) is acyclic.
  • Let root_nodes = the set of nodes with only outgoing edges. Insert a new node ROOT with each element of root_nodes as a child. Every element should now be reachable from ROOT
  • Now perform DFS starting at ROOT and list the nodes in the appropriate order (I think reverse postorder will give the "all parents before a child" property). This is the final traversal order.
How does that sound?

Breakfast
Posts: 117
Joined: Tue Jun 16, 2009 7:34 pm UTC
Location: Coming to a table near you

Re: Fleeting Thoughts (CS Edition)

Postby Breakfast » Mon Jan 13, 2014 1:11 pm UTC

I'm sorry the problem hasn't been stated clearly enough. Written words and all that... The big problem I was having was dealing with things like this:
a
/ \
b d
\ /
c

Where a, b, c, and d are objects and the edges are properties that let you go from one to another. I'm actually using parent information in my algorithm (b and d know that they have a parent a, and c knows that it can have a parent b, or d, or both [in the diagram, both]).

Here's mine:
Spoiler:
  1. Start at a
  2. a is the root so perform operation on a
  3. Discover a's properties b and d
  4. Walk to b (or d)
  5. Discover b's properties a and c
  6. a is marked as a parent so it isn't walked to
  7. b has only one parent which was walked to get here, perform operation on b
  8. Walk to c
  9. Discover c's properties b and d
  10. b and d are both marked as parent so they aren't walked to
  11. c has two parents, only one of which has been visited, so defer c's operation until later
  12. Recurse back to b
  13. Recurse back to a
  14. Walk to d
  15. Discover d's properties a and c
  16. a is marked as a parent so it isn't walked to
  17. d has only one parent which was walked to get here, perform operation on d
  18. Walk to c
  19. Discover c's properties b and d
  20. b and d are both marked as parent so they aren't walked to
  21. c has two parents and has now been visited twice, perform operation on c
  22. Recurse back to d
  23. Recurse back to a
  24. Done

User avatar
headprogrammingczar
Posts: 3072
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

Re: Fleeting Thoughts (CS Edition)

Postby headprogrammingczar » Mon Jan 13, 2014 10:16 pm UTC

Code: Select all

  a
 / \
b   d
 \  /
  c


You can use code tags for ascii art. Also, you can probably simplify your algorithm by doing a breadth-first traversal with some kind of deduping in the queue. It would then be something like:

Spoiler:
1. Process A
2. Push B, D
3. Process B
4. Push C
5. Process D
6. Push C (it's already in the queue, so this is a no-op)
7. Process C
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you

Breakfast
Posts: 117
Joined: Tue Jun 16, 2009 7:34 pm UTC
Location: Coming to a table near you

Re: Fleeting Thoughts (CS Edition)

Postby Breakfast » Tue Jan 14, 2014 12:45 pm UTC

Thanks for the tip on the ascii art. I've been a member for a while but read more than post.

What you're describing is essentially what I'm doing if you replace breadth-first with depth-first (...and the queue with a dictionary that holds Ids for nodes and parent counts*). I just wanted to be overly specific when describing what was going on to [hopefully] clear up the problem statement.

*I picked a dictionary because the example I gave wasn't the only case. I thought the bookkeeping would be easier in cases where a node had more two or more parents.

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Fleeting Thoughts (CS Edition)

Postby troyp » Wed Jan 15, 2014 10:42 pm UTC

Breakfast, I think your solution's doing a reverse postorder DFS (similar to mine, but omitting/replacing some stuff that's apparently not necessary). Also, it actually is implementing a topological sort. I didn't mention it before because I was a little fuzzy on the definition of a topological sort, but looking it up it's just imposing a parents-before-children condition on a DAG traversal, so a reverse postorder traversal will be a valid implementation of topological sort.

Are we actually talking about an undirected graph? With the talk of parents and children, I'd assumed a directed graph, but an undirected graph makes things simpler. If it's undirected, headprogrammingczar's BFS-based suggestion should be equivalent but a little simpler (I think). In the general case of a directed graph, it won't always work, though.

aside regarding ASCII diagrams: what you can also do in a simple case like this is use unicode spaces (eg. en-spaces). You can have them at the start of a line, or several in a row. You'll still have a proportional font, so for more complicated things you still need code blocks, but for a diamond diagram, it's probably good enough:
  A
 /  \
B   C
 \  /
  D

Breakfast
Posts: 117
Joined: Tue Jun 16, 2009 7:34 pm UTC
Location: Coming to a table near you

Re: Fleeting Thoughts (CS Edition)

Postby Breakfast » Thu Jan 16, 2014 12:52 am UTC

Troyp, I was a bit unsure of what constituted a topological sort as well. Whether it could be used as a blanket term with different implementations.

I'm willing to talk about directed, undirected... anything really. Both are interesting problems. The graph I was presented with always had two edges between parent and child. There's a directed edge from parent to child and vis versa. I disallowed the child-parent edge to be traversed in my implementation so as not to cause loops.

Aside from topological sorts does anyone know any other solutions? How about any other variations on the problem? One I've heard is that you would get all of the nodes over a network, not necessarily in order, and you'd have to reconstruct the graph before traversal.

User avatar
ahammel
My Little Cabbage
Posts: 2135
Joined: Mon Jan 30, 2012 12:46 am UTC
Location: Vancouver BC
Contact:

Re: Fleeting Thoughts (CS Edition)

Postby ahammel » Thu Apr 17, 2014 7:11 pm UTC

Given two regular expressions, is the question of whether there exists a string that matches both decideable in general?
He/Him/His/Alex
God damn these electric sex pants!

EvanED
Posts: 4324
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Fleeting Thoughts (CS Edition)

Postby EvanED » Thu Apr 17, 2014 7:35 pm UTC

ahammel wrote:Given two regular expressions, is the question of whether there exists a string that matches both decideable in general?
Yes, unless you mean non-regular regular expressions. :-)

Actually it's really easy: convert them to a FA (there are at least three very different algorithms for this process), determinize if necessary, and compute the intersection automaton. Doing the same without an FA conversion may not be possible.

User avatar
Xanthir
My HERO!!!
Posts: 5213
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Fleeting Thoughts (CS Edition)

Postby Xanthir » Fri Apr 18, 2014 6:35 am UTC

As Evan alludes to, though, for the non-regular regular expressions you're less likely to be able to determine it. The use of backrefs pushes regexes into PDA territory (or context-free languages, equivalently), which aren't closed under intersection (and once you lose that property, it's unlikely (impossible?) to be regained). The use of lookaheads/lookbehinds pushes them further, into context-sensitive languages. I don't recall if perl-compatible regexes are actually turing-complete or not.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

EvanED
Posts: 4324
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Fleeting Thoughts (CS Edition)

Postby EvanED » Fri Apr 18, 2014 1:31 pm UTC

Xanthir wrote:As Evan alludes to, though, for the non-regular regular expressions you're less likely to be able to determine it. The use of backrefs pushes regexes into PDA territory (or context-free languages, equivalently),...
Actually it's not that, because PDAs can't recognize {ww | w ∈ Σ*} which can be trivially done via the regex (.*)\1 (substitute your favorite syntax). But I also don't know of any PCRE that can recognize {wwR | w ∈ Σ*} (though maybe there's some way to get it), so at least as I see "backrefs" regex+backrefs don't define a strict superset of CFLs either. I have no idea what that class is.

The use of lookaheads/lookbehinds pushes them further, into context-sensitive languages.
I'm not a PCRE expert, but if the lookahead/behind amounts are always finite, it actually shouldn't affect the language class. E.g. regex+finite lookahead would still be Regular. :-)

User avatar
Xanthir
My HERO!!!
Posts: 5213
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Fleeting Thoughts (CS Edition)

Postby Xanthir » Fri Apr 18, 2014 5:01 pm UTC

EvanED wrote:
Xanthir wrote:As Evan alludes to, though, for the non-regular regular expressions you're less likely to be able to determine it. The use of backrefs pushes regexes into PDA territory (or context-free languages, equivalently),...

Actually it's not that, because PDAs can't recognize {ww | w ∈ Σ*} which can be trivially done via the regex (.*)\1 (substitute your favorite syntax).


Oh right, sorry, it pushes it into non-deterministic pushdowns. That's the context-free languages.

But I also don't know of any PCRE that can recognize {wwR | w ∈ Σ*} (though maybe there's some way to get it), so at least as I see "backrefs" regex+backrefs don't define a strict superset of CFLs either. I have no idea what that class is.

Where R is an arbitrary finite integer? Easy: /(.*)\1+/

The use of lookaheads/lookbehinds pushes them further, into context-sensitive languages.
I'm not a PCRE expert, but if the lookahead/behind amounts are always finite, it actually shouldn't affect the language class. E.g. regex+finite lookahead would still be Regular. :-)

They're not always finite. You can use star in a lookahead group (and capture it!).
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
ahammel
My Little Cabbage
Posts: 2135
Joined: Mon Jan 30, 2012 12:46 am UTC
Location: Vancouver BC
Contact:

Re: Fleeting Thoughts (CS Edition)

Postby ahammel » Fri Apr 18, 2014 5:21 pm UTC

EvanED wrote:
ahammel wrote:Given two regular expressions, is the question of whether there exists a string that matches both decideable in general?
Yes, unless you mean non-regular regular expressions. :-)

Actually it's really easy: convert them to a FA (there are at least three very different algorithms for this process), determinize if necessary, and compute the intersection automaton. Doing the same without an FA conversion may not be possible.
Cool. The regexes I'm using don't have back-references, so I can use that strategy. There's even a library for it (the author seems to think that regexes with back-references require a Turing machine to recognize). An app I'm working on won't work correctly unless a bunch of regular expressions are mutually exclusive, so it would be pretty neat to be able to formally verify that.

I ran across this this fascinating write-up while looking into the back-references problem. The upshot is that regular expression engines that permit back-references tend to use backtracking even when it's not strictly necessary. The result is that it's easy to come up with a simple regex that takes forever to match even a very short string:

Code: Select all

# re_killer.py
import re
import timeit


def match_killer_re(n):
    """Match the regular expression a?^n a^n against the string a^n.

    The ^ above represents repetition, e.g.: a?^2 a^2 == "a?a?aa"

    """
    regex = ("a?" * n) + ("a" * n)
    string = "a" * n
    re.match(regex, string)


if __name__ == '__main__':
    for n in range(20,31):
        runtime = timeit.timeit(
                "match_killer_re({})".format(n),
                setup="from __main__ import match_killer_re",
                number=1)
        print("matched 'a?^{n} a^{n}' to 'a^{n}' "
              "in {time:<6.4} seconds".format(n=n, time=runtime))


Code: Select all

┌─────[alex@asimov] (re_killer)
└─╼ python re_killer.py
matched 'a?^20 a^20' to 'a^20' in 0.2302 seconds
matched 'a?^21 a^21' to 'a^21' in 0.4759 seconds
matched 'a?^22 a^22' to 'a^22' in 0.9611 seconds
matched 'a?^23 a^23' to 'a^23' in 1.967  seconds
matched 'a?^24 a^24' to 'a^24' in 3.908  seconds
matched 'a?^25 a^25' to 'a^25' in 8.436  seconds
matched 'a?^26 a^26' to 'a^26' in 16.68  seconds
matched 'a?^27 a^27' to 'a^27' in 33.65  seconds
matched 'a?^28 a^28' to 'a^28' in 68.55  seconds
matched 'a?^29 a^29' to 'a^29' in 136.8  seconds
matched 'a?^30 a^30' to 'a^30' in 279.6  seconds
He/Him/His/Alex
God damn these electric sex pants!

EvanED
Posts: 4324
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Fleeting Thoughts (CS Edition)

Postby EvanED » Fri Apr 18, 2014 6:37 pm UTC

Xanthir wrote:
EvanED wrote:
Xanthir wrote:As Evan alludes to, though, for the non-regular regular expressions you're less likely to be able to determine it. The use of backrefs pushes regexes into PDA territory (or context-free languages, equivalently),...

Actually it's not that, because PDAs can't recognize {ww | w ∈ Σ*} which can be trivially done via the regex (.*)\1 (substitute your favorite syntax).

Oh right, sorry, it pushes it into non-deterministic pushdowns. That's the context-free languages.
... no. The language (.*)\1 isn't context-free. (And pretty much universally, "PDA" means non-deterministic and you need to say "DPDA" or something for the less-powerful deterministic counterpart.)

Spoiler:
ww.png


But I also don't know of any PCRE that can recognize {wwR | w ∈ Σ*} (though maybe there's some way to get it), so at least as I see "backrefs" regex+backrefs don't define a strict superset of CFLs either. I have no idea what that class is.

Where R is an arbitrary finite integer?
No, where wR is the reverse of w. (So wwR are the even-length palindromes.)

They're not always finite. You can use star in a lookahead group (and capture it!).
Fair enough. :-)

ahammel wrote:There's even a library for it[/url] (the author seems to think that regexes with back-references require a Turing machine to recognize).
I suspect it's dobale with a linearly-bounded automaton (corresponds to context-sensitive languages) but I haven't thought about it enough to say I'm sure, and may not know enough about backrefs to be able to think about it enough. :-)

User avatar
mister_m
Posts: 34
Joined: Fri Feb 04, 2011 2:51 am UTC

Re: Fleeting Thoughts (CS Edition)

Postby mister_m » Sat Feb 14, 2015 5:11 am UTC

Trying to teach myself some Scala/FP. Going through some exercises on foldr/foldl currently. Reasoning about these becomes a little easier if you are able to answer "what is the last argument this function recieves?".

For instance, reversing a list using foldLeft becomes pretty simple if you understand how foldLeft actually works. Also, tracing out the execution of a fold(l|r) with a smallish list is also helpful

User avatar
Wildcard
Candlestick!
Posts: 251
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

Re: Fleeting Thoughts (CS Edition)

Postby Wildcard » Thu May 21, 2015 7:52 am UTC

I wonder if the reason there are relatively few people studying CS or programming (relative to the need for skilled professionals in these fields) is because it's so hard to get set up to make the code actually do stuff on your own computer?
Spoiler:
I got Java working at least to the extent of "Hello World"; C++ is theoretically installed and IDE set up but "Hello World" is giving me trouble; and "Mozart-Oz", which I want to set up to work my way through my copy of "Concepts, Techniques and Models of Computer Programming", is just one big pain in the a**. (On Mac OS 10.7.4, BTW.) I finally escaped the pain that is Aquamacs and found TextWrangler, which is going great so far, but now I need to figure out making Mozart-Oz run in command line and actually do stuff.
And another fleeting thought: I swear, I had more fun and less trouble when I was like eleven years old...messing around with the algebra and quadratics I was learning at the time, using "Chipmunk Basic" on an ancient Mac, than I have now trying to play around with some simple exercises in graph theory or number theory using an actual production coding language. :/

Any success stories from the Von Roy and Haridi book? I like the overall approach but the pain of trying to get Mozart-Oz to actually simply run correctly on my computer has turned me off a bit....

(I like this thread and I feel it should continue! : )
There's no such thing as a funny sig.

User avatar
WanderingLinguist
Posts: 230
Joined: Tue May 22, 2012 5:14 pm UTC
Location: Seoul
Contact:

Re: Fleeting Thoughts (CS Edition)

Postby WanderingLinguist » Thu May 21, 2015 8:48 am UTC

Wildcard wrote:I wonder if the reason there are relatively few people studying CS or programming (relative to the need for skilled professionals in these fields) is because it's so hard to get set up to make the code actually do stuff on your own computer?


I haven't had a problem with that, but then again, I have a Mac, so Python is included by default, and for C/C++/Objective-C/Swift, you just need to install Xcode from the app store and you're good to go.

My only use for Java has been Android app development, and back in the Eclipse days, it was a pain in the neck to get it set up, but now that they've switched to Android Studio, the setup is a breeze.

I suspect things might be trickier on Windows though? I don't know; it's been years since I've used Windows for anything other than IE.

Edit:

Wildcard wrote:And another fleeting thought: I swear, I had more fun and less trouble when I was like eleven years old...messing around with the algebra and quadratics I was learning at the time, using "Chipmunk Basic" on an ancient Mac, than I have now trying to play around with some simple exercises in graph theory or number theory using an actual production coding language. :/


Well, production languages do require more background knowledge and more effort at the start to build something. But when you get further into a project, it's worth it in the other benefits they bring to the table. I suspect it may be an unavoidable tradeoff, but I'd love to be proved wrong.

User avatar
Xenomortis
Not actually a special flower.
Posts: 1396
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: Fleeting Thoughts (CS Edition)

Postby Xenomortis » Thu May 21, 2015 9:02 am UTC

Wildcard wrote:I wonder if the reason there are relatively few people studying CS or programming (relative to the need for skilled professionals in these fields) is because it's so hard to get set up to make the code actually do stuff on your own computer?[spoiler]I got Java working at least to the extent of "Hello World"; C++ is theoretically installed and IDE set up but "Hello World" is giving me trouble

Python is pretty good for this. You just need the interpreter and a text editor - although good text editors don't come standard with Windows.
*nix systems in general are easier for programming too - versatile editors and compilers often come as standard.

IDE's are useful, but tend to be a bit heavy for when you're starting out - when you're learning the basics, you largely just want "source file -> compiler -> executable", not "solution + projects -> build...".

Wildcard wrote:"Mozart-Oz", which I want to set up to work my way through my copy of "Concepts, Techniques and Models of Computer Programming", is just one big pain in the a**.

https://github.com/mozart/mozart2 wrote:In order to build Mozart 2, you need the following tools on your computer:

git and Subversion to grab the source code
java >= 1.6.0
gcc >= 4.7.1 on Windows, Linux and Mac OS < 10.8; or clang >= 3.1 on Mac OS >= 10.8
cmake >= 2.8.6
Boost >= 1.53.0 (with development files)
Tcl/Tk 8.5 or 8.6 (with development files)
emacs

That's a lost cause as far as I'm concerned for someone just starting out...
Image

User avatar
Xanthir
My HERO!!!
Posts: 5213
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Fleeting Thoughts (CS Edition)

Postby Xanthir » Thu May 21, 2015 2:50 pm UTC

This is part of why JS is so wonderful. If you have a working computer, you've already got everything you need - a browser. If you're feeling fancy, an external text editor, but there are plenty of web IDEs that work just fine.

One of my most exciting moments was seeing the development and adoption of the <canvas> element, because it meant I could finally do the playing-around-with-graphics that I'd always wanted to do as a kid, but had such a terrible time getting to work in C++/Java/etc.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Flumble
Yes Man
Posts: 1944
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Fleeting Thoughts (CS Edition)

Postby Flumble » Thu May 21, 2015 6:12 pm UTC

I'm almost entirely with you, Xanthir. The only difference being that I was (am) more familiar with GameMaker, so, after the initial excitement, I went back to prototyping in GM. (It's just that bit quicker to set up and I've grown into it.)

Also file handling is still horrible in the browser. I now have a large friendly button to disable CORS.

User avatar
Wildcard
Candlestick!
Posts: 251
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

Re: Fleeting Thoughts (CS Edition)

Postby Wildcard » Fri May 22, 2015 5:47 am UTC

Xenomortis wrote:IDE's are useful, but tend to be a bit heavy for when you're starting out - when you're learning the basics, you largely just want "source file -> compiler -> executable", not "solution + projects -> build...".
Could you expand on that?? My understanding of IDEs is limited, but I thought that they basically just let you compile and execute the code from within the same application, instead of requiring you to go to the command line, and that they often include syntax highlighting and code autocompletion. What's the thing about "solution + projects -> build" ??

More concretely, if I want to develop a working knowledge of Java, say enough to work through "The Introduction to Algorithms" by Cormen (which I also have) and try out the algorithms, learning Java as I go...do you think an IDE (I've installed NetBeans) would give me more trouble than assistance? Should I stick with a text editor? (I have TextWrangler.) And if so, how do I compile and run the Java source files on my Mac?

I think I might like the text editor approach, but from what I've read about Java, actually using it for any real apps is going to involve learning to use the already existing libraries of code. I don't see how I would do that in a text editor and it seems like easy use of libraries would be a standard benefit of an IDE....

Xenomortis wrote:
Wildcard wrote:"Mozart-Oz", which I want to set up to work my way through my copy of "Concepts, Techniques and Models of Computer Programming", is just one big pain in the a**.

https://github.com/mozart/mozart2 wrote:In order to build Mozart 2, you need the following tools on your computer:

git and Subversion to grab the source code
java >= 1.6.0
gcc >= 4.7.1 on Windows, Linux and Mac OS < 10.8; or clang >= 3.1 on Mac OS >= 10.8
cmake >= 2.8.6
Boost >= 1.53.0 (with development files)
Tcl/Tk 8.5 or 8.6 (with development files)
emacs

That's a lost cause as far as I'm concerned for someone just starting out...

You would think. Actually, I found a pre-built file here but it requires Aquamacs. I finally got it all installed and got it to work, except for two severe annoyances: (1) I can't stand Aquamacs as it seems I would have to learn all basic keyboard shortcuts from scratch, to say nothing of how badly it gets on with my preference for Dvorak, and (2) The very first code example in my book, using the command (or class method or whatever) called "Browse", doesn't work on my install. I can't get the browser to show up, period. I can get "show" to work, which is almost equivalent, but it makes me wonder how many other features described in my book will be broken on this install.

I guess that's more than a fleeting thought. Here's one, though:

If I had read as many examples of full-fledged source code as I have read puzzle books and math books, I would probably be able to hack alien computers from my laptop like Jeff Goldblum.
There's no such thing as a funny sig.

EvanED
Posts: 4324
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Fleeting Thoughts (CS Edition)

Postby EvanED » Fri May 22, 2015 6:44 am UTC

Wildcard wrote:
Xenomortis wrote:IDE's are useful, but tend to be a bit heavy for when you're starting out - when you're learning the basics, you largely just want "source file -> compiler -> executable", not "solution + projects -> build...".
Could you expand on that?? My understanding of IDEs is limited, but I thought that they basically just let you compile and execute the code from within the same application, instead of requiring you to go to the command line, and that they often include syntax highlighting and code autocompletion. What's the thing about "solution + projects -> build" ??
Things aren't quiite that simple because you can often invoke your build scripts from within any reasonable programming text editor. So you don't necessarily need to "change to the command line." There is extra stuff to learn in the non-IDE route -- especially if you're unfamiliar with the command line.

There is one way in which I agree with Xenomortis, which is dealing with a single file. In IDEs, you usually can't just write and compile just one file: you have to create a whole project first. Depending on your IDE and how you divide things, you might not be able to have two projects open at the same time in the same IDE instance, as apposed to editors that usually let you switch between multiple files (a la tabs) and compile them independently.

Even at a high level this is a bit annoying -- I have VS projects called "cpp scratch" and "cs scratch" for instance if I want to just try a quick compile of something.

I'm not sure which way the cost-benefit goes. I suspect, though, that the benefits of using an IDE would outweigh that cost for most people, often by a wide margin.

User avatar
Xenomortis
Not actually a special flower.
Posts: 1396
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: Fleeting Thoughts (CS Edition)

Postby Xenomortis » Fri May 22, 2015 8:53 am UTC

EvanED wrote:There is one way in which I agree with Xenomortis, which is dealing with a single file. In IDEs, you usually can't just write and compile just one file: you have to create a whole project first. Depending on your IDE and how you divide things, you might not be able to have two projects open at the same time in the same IDE instance, as apposed to editors that usually let you switch between multiple files (a la tabs) and compile them independently.

That's where I was coming from. When you start out, it's often with "create a text file called helloworld.cpp..." or something like that.
But if you were to open Visual Studio, you're going to be asked "What sort of project would you like to create?" and you think "What's a project? What's the difference between Console and Win32? And what's C++.NET?"
Spoiler:
And then when you finally get your code file you're going to think "what's this #include "stdafx.h" and why do I get an error when I delete that line?

Unless you're following a tutorial/book tailored for the IDE you're using, confusion will befall you.

That said, IDEs are useful.
It's sometimes even worth waiting for VS to load to test something small in my scratch projects instead of using gvim+gcc.
Although I think that's largely because debugging is so much easier in VS.
Image

EvanED
Posts: 4324
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Fleeting Thoughts (CS Edition)

Postby EvanED » Fri May 22, 2015 3:07 pm UTC

Xenomortis wrote:Unless you're following a tutorial/book tailored for the IDE you're using, confusion will befall you.
Well, but that's true of compilers at the command line too. In fact, I'd say it's worse... at least you have a chance of bumbling into the right answer just playing around with the IDE.

User avatar
Jplus
Posts: 1692
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

Re: Fleeting Thoughts (CS Edition)

Postby Jplus » Sat May 23, 2015 8:06 am UTC

Sorry for starting a quote pyramid, just trying to help... :)

Wildcard wrote:
Xenomortis wrote:IDE's are useful, but tend to be a bit heavy for when you're starting out - when you're learning the basics, you largely just want "source file -> compiler -> executable", not "solution + projects -> build...".
Could you expand on that?? My understanding of IDEs is limited, but I thought that they basically just let you compile and execute the code from within the same application, instead of requiring you to go to the command line, and that they often include syntax highlighting and code autocompletion. What's the thing about "solution + projects -> build" ??
IDEs want to be your integrated development environment; they try to do everything for you, including editing, version control, building, testing, debugging, profiling and possibly even shipping. If you have prior experience with most of those things, then you'll probably enjoy having a single application that can do all of it and reduce the amount of work that you need to do by yourself. However, if you are new to (production) programming, an IDE tends to be a huge mountain of buttons, panels, menus and pre-fabricated source code of which you have no idea what they are good for. When I started programming, learning to use an IDE seemed like a daunting task that would distract me from the actual programming.

Command line tools have all these options as well, and they are harder to find. But for a beginner, that can be a blessing: you don't see the options you don't need (yet) unless you type them yourself. I was glad that all I needed to know about GCC was

Code: Select all

g++ mysinglesourcefile.cpp
./a.out

Looks much simpler than an IDE, right?

More concretely, if I want to develop a working knowledge of Java, say enough to work through "The Introduction to Algorithms" by Cormen (which I also have) and try out the algorithms, learning Java as I go...do you think an IDE (I've installed NetBeans) would give me more trouble than assistance? Should I stick with a text editor? (I have TextWrangler.)
Well, you seem to be in trouble now. I can't judge whether that is because of NetBeans, or because you simply didn't find a good tutorial yet that tells you what to do. What I do know about trying out algorithms from a study book, is that it never requires you to do anything more complex than writing a single source file and compiling and running it straight away. In any case, editor + terminal should be sufficient for this purpose.

As for editors, TextWrangler is great, also for non-sourcecode plain text editing. For programming, I prefer TextMate because it is a bit more IDE-like in terms of autocompletion and stuff like that, while still not trying to do everything for you.

For IDEs, you could try using a JetBrains product instead, because those are quite nice. In addition, they are free for students.
And if so, how do I compile and run the Java source files on my Mac?
In the terminal:

Code: Select all

javac yoursinglefileprogram.java
java yoursinglefileprogram

If Java is not available in your terminal, download the JDK here.

I think I might like the text editor approach, but from what I've read about Java, actually using it for any real apps is going to involve learning to use the already existing libraries of code. I don't see how I would do that in a text editor and it seems like easy use of libraries would be a standard benefit of an IDE....
Well, you're not developing apps yet. You can always switch back to using an IDE when you have more experience. Just my two cents.
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

User avatar
Wildcard
Candlestick!
Posts: 251
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

Re: Fleeting Thoughts (CS Edition)

Postby Wildcard » Mon May 25, 2015 7:28 am UTC

EvanED, Xenomortis, JPlus (and others) wrote:a lot of very helpful advice
Thanks very much everyone! I finally realized that my main problem was just not starting, so I have done that now. :)

I found a proper tutorial—I happened to remember that a Lynda.com sign in is a perquisite of one of my side jobs. There's a good tutorial there that covers the basics of Java, using Eclipse, so I got Eclipse and I've been following along. Going great so far!

I also made some simple java programs in Text Wrangler and successfully compiled and ran them from the command line, first with a script (if you google "java textwrangler script compile and run" without quotes it will show up) and later directly on the command line without a script. That was helpful because it de-mystified the source code and made it very clear that what I actually wrote into the source code was the only text needed to compile and run the program successfully, i.e., there wasn't any IDE "helping" by putting a bunch of "include" lines and whatever to make my code actually operate. It's not so clear within an IDE that your code is actually functional by itself. The IDE is like a crutch and (if you're just beginning) it can make you wonder if your code can "walk" without the help.

So I plan to use both Eclipse and TextWrangler and change back and forth. I like the way I can learn syntax in the IDE, but I also want to make sure that I learn the syntax, not just depend on the IDE to know it for me.

Incidentally, I have more background with programming than I mentioned—many years ago I wrote extensive scripts using bash and perl while working as a software tester, and also coded some if/then input-output policy objects with an in-house markup language. I also wrote some simple C programs YEARS ago and also played a very minor role in the programming of my team's F.I.R.S.T. robot in high school. (We made it to nationals! :) ) Plus of course playing with Chipmunk Basic as a kid, and the old Omega tank game. (That's still my favorite game for learning programming....) So I'm not REALLY a beginner. I just haven't kept up practice in any of the languages I used, and I never formally studied anything about them until now. (Jeez, I didn't mean to post my whole resume, sorry....)

So again, thanks very much for the help!

And to keep it on topic, a fleeting thought:

Everything has an algorithm: going to the laundromat, starting a Fortune 500 company, putting your shoes on, going to the moon.... But most people use very inefficient algorithms, and for some things people use incorrect algorithms that will simply never reach the target state. Like this algorithm for getting rich:
Cake wrote:...an old man sits collecting stamps in a room all filled with Chinese lamps. He saves what others throw away; he says that he'll be rich someday....
:)
There's no such thing as a funny sig.

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Fleeting Thoughts (CS Edition)

Postby troyp » Mon May 25, 2015 4:29 pm UTC

Personally, I can't understand how people tolerate IDEs. I mean, sure, I understand using them for debugging. That's what they're good for. But writing code? You get stuff like prettier autocompletion that's configured out of the box, but in exchange you have to write code without a decent text editor. When I've used an IDE it's always a huge chore to write anything, and when I get serious I have to set autoreversion and switch to Emacs to do my real coding.

Maybe when you're managing a large project IDEs become more useful, but I still can't see why you wouldn't switch to editor for editing. Unless you've got something like Eclim that lets you get real editing inside your IDE.

Any success stories from the Von Roy and Haridi book? I like the overall approach but the pain of trying to get Mozart-Oz to actually simply run correctly on my computer has turned me off a bit...

Actually, I found a pre-built file here but it requires Aquamacs. I finally got it all installed and got it to work, except for two severe annoyances: (1) I can't stand Aquamacs as it seems I would have to learn all basic keyboard shortcuts from scratch, to say nothing of how badly it gets on with my preference for Dvorak, and (2) The very first code example in my book, using the command (or class method or whatever) called "Browse", doesn't work on my install. I can't get the browser to show up, period. I can get "show" to work, which is almost equivalent, but it makes me wonder how many other features described in my book will be broken on this install.

I've read bits of CTM and done Peter Van Roy's EdX course. I enjoyed it, especially the bit on dataflow variables. I'd certainly recommend it, although not as highly as SICP. You need Emacs because it's the only development environment for Oz (you'll find that's sometimes the case with teaching and research languages). If you really wanted to, you could probably use another editor and run ozc from the command line, but you'd have no syntax highlighting, autoindentation, etc, etc.

(1) What shortcuts were you used to that didn't work in Aquamacs? If you want the C-c, C-v, C-x bindings for copy/paste/cut, you need to activate CUA mode, but other common shortcuts should work.

(2)Note that {Show ...} prints to the standard output, whereas {Browse ...} brings up the graphical browser. So if the latter doesn't work, your graphical browser isn't working. From memory, I think you need to choose "Oz -> Show/hide -> Emulator" from the menu to get the browser to appear. At worst, if you can't get the browser to work, you always replace calls to {Browse} with {Show}.

User avatar
Sizik
Posts: 1156
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Fleeting Thoughts (CS Edition)

Postby Sizik » Mon May 25, 2015 5:29 pm UTC

troyp wrote:Personally, I can't understand how people tolerate IDEs. I mean, sure, I understand using them for debugging. That's what they're good for. But writing code? You get stuff like prettier autocompletion that's configured out of the box, but in exchange you have to write code without a decent text editor. When I've used an IDE it's always a huge chore to write anything, and when I get serious I have to set autoreversion and switch to Emacs to do my real coding.

Maybe when you're managing a large project IDEs become more useful, but I still can't see why you wouldn't switch to editor for editing. Unless you've got something like Eclim that lets you get real editing inside your IDE.


I'm curious, what features make a text editor "decent"?
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 6 guests