# I'm learning to code (again)!

**URL:** <https://boards.straightdope.com/t/im-learning-to-code-again/334411>\
**Category:** Miscellaneous and Personal Stuff I Must Share\
**Created:** [December 6, 2005, 9:19pm UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411 "2005-12-06T21:19:13Z")\
**Posts on this page:** 12\
**Page:** 2

<div class="post-metadata">

**Author:** ![Capt.Ridley\_s\_Shooting\_Party](https://avatars.discourse-cdn.com/v4/letter/c/cc9497/32.png) [@Capt.Ridley\_s\_Shooting\_Party](https://boards.straightdope.com/u/Capt.Ridley_s_Shooting_Party)\
**Post date:** [December 7, 2005, 6:17pm UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/21 "2005-12-07T18:17:08Z")

</div>

Solve this problem:

Given an arbitrary string, decide whether or not the string conforms to the grammar: A = "a"B, A = "  
", B = "b"AC, B = "  
", C = "c  
", C = "  
" where A is your start state and where "  
" is the null terminator for strings.

Some examples of strings accepted by this grammar: "  
", "a  
", "abac  
". You should be able to do this using what you already know using switch statements.

---

<div class="post-metadata">

**Author:** ![Capt.Ridley\_s\_Shooting\_Party](https://avatars.discourse-cdn.com/v4/letter/c/cc9497/32.png) [@Capt.Ridley\_s\_Shooting\_Party](https://boards.straightdope.com/u/Capt.Ridley_s_Shooting_Party)\
**Post date:** [December 7, 2005, 6:18pm UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/22 "2005-12-07T18:18:21Z")

</div>

:smack: The last example should be "abab  
".

---

<div class="post-metadata">

**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\
**Post date:** [December 7, 2005, 10:01pm UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/23 "2005-12-07T22:01:48Z")

</div>

Write a program that, given any program as an input, can determine whether that program halts or not.

😉

---

<div class="post-metadata">

**Author:** ![Derleth](https://avatars.discourse-cdn.com/v4/letter/d/b9e5f3/32.png) [@Derleth](https://boards.straightdope.com/u/Derleth)\
**Post date:** [December 7, 2005, 10:46pm UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/24 "2005-12-07T22:46:20Z")

</div>

> [@Shalmanese](#):
>
> Gah, I don’t know why people insist on using fibonacci to demonstrate recursion. Nobody but a braindead monkey would EVER write fibonacci the pure recursive manner due to it being godawful slow (assuming your not programming in a pure functional language :D). There are so much better examples to demonstrate recursion to a beginner.

Uh, have you ever profiled recursive code, or looked at the generated machine language? It’s common for gcc, at least, to not only transform recursive code into iterative where it’s possible (tail-call elimination) but to partially unroll the resulting loop as well. It’s just as fast as the iterative solution, and a compiler not smart enough to perform those optimizations isn’t worth having.

All conformant Scheme implemenations _must_ perform that optimization, which has the nice property of obviating the need for Common Lisp-style GO statements. (Yes, CL is a Lisp with goto. Be afraid. Be very afraid. ;))

A trivial little project is to create your own [CipherSaber](http://ciphersaber.gurus.com/). It gets a bit more complex when you try to make it secure and you have to hook into OS-specific APIs. (For example, how do you prevent someone on the same machine from reading your key when the program’s RAM is swapped to disk? How do you prevent someone from reading your key over your shoulder?)

It could be fun to implement an interpreter (or compiler) for a minilanguage. A trivial Forth implementation shouldn’t present problems for anyone with an understanding of stacks, but a Forth implementation that allows the user to define his own words is a bit more complex. (It requires a second stack, to begin with.) I don’t know if there is an implementation of [yacc](http://en.wikipedia.org/wiki/Yacc) or [bison](http://www.gnu.org/software/bison/) that outputs C++ code, but you can hand-code a recursive-descent compiler without too many problems. Jack Crenshaw’s [_Let’s Build a Compiler_](http://compilers.iecc.com/crenshaw/) is a good introductory text on that, without being too simple for someone in your position. (For starters, you need to translate Pascal to C++ and m68k assembly to x86, if you decide to go that route. For extra credit, you might code a Pascal compiler with a C++ backend and an m68k emulator, instead. ;))

None of my examples are OO. That’s partly on purpose: C++ isn’t just an OO language; it shines pretty well in procedural contexts, too. Plus, there are a lot more non-OO problems in the world than there are OO. If you want a language that’s ‘All Objects, All The Time’, [Squeak Smalltalk](http://www.squeak.org/) is nice.

---

<div class="post-metadata">

**Author:** ![Crowbar\_of\_Irony\_3](https://avatars.discourse-cdn.com/v4/letter/c/f08c70/32.png) [@Crowbar\_of\_Irony\_3](https://boards.straightdope.com/u/Crowbar_of_Irony_3)\
**Post date:** [December 8, 2005, 1:37am UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/25 "2005-12-08T01:37:03Z")

</div>

> [@Shalmanese](#):
>
> Write a program that, given any program as an input, can determine whether that program halts or not.
> 
> 😉

Tell me if you managed to do that. If you could, I think you are entitled to a Nobel Prize or something… 🙂

---

<div class="post-metadata">

**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\
**Post date:** [December 8, 2005, 4:08am UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/26 "2005-12-08T04:08:48Z")

</div>

> [@Derleth](#):
>
> Uh, have you ever profiled recursive code, or looked at the generated machine language? It’s common for gcc, at least, to not only transform recursive code into iterative where it’s possible (tail-call elimination) but to partially unroll the resulting loop as well. It’s just as fast as the iterative solution, and a compiler not smart enough to perform those optimizations isn’t worth having.

AFAIK, only if you use -O3. A standard, generic compile with no performance flags shouldn’t be doing ANY performance optimisations. Besides, since C++ is a procedural language, it’s not guarenteed that the compiler will always be able to successfully unroll loops. It’s good programming practise to not rely on the intelligence of the compiler to make major algorithmic changes for you.

---

<div class="post-metadata">

**Author:** ![rkts](https://avatars.discourse-cdn.com/v4/letter/r/c4cdca/32.png) [@rkts](https://boards.straightdope.com/u/rkts)\
**Post date:** [December 8, 2005, 6:23am UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/27 "2005-12-08T06:23:44Z")

</div>

I just made a test program with gcc and even with -O3 the recursive method starts to struggle in the lower 30s. In fact, the speed increase from gcc’s optimizations is barely noticeable.

---

<div class="post-metadata">

**Author:** ![rkts](https://avatars.discourse-cdn.com/v4/letter/r/c4cdca/32.png) [@rkts](https://boards.straightdope.com/u/rkts)\
**Post date:** [December 8, 2005, 7:37am UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/28 "2005-12-08T07:37:28Z")

</div>

I think a lot of these intellectual exercises are pointless for a beginning programmer to bother himself with. 90% of actual programming is completely mundane and requires none of the mental effort required by something like the Towers of Hanoi problem. I suggest that you pick up some tools with which you can make something more like a real application. You may want to expand one of your existing programs; for instance, take your number-guessing program and expand it thus:

- Make it keep statistics for each user.
- Make it write those statistics to a file, which it later reads back into memory.
- Make it customizable via a configuration file.
- Make a GUI for it.

If you find yourself getting bogged down in tedious details, consider switching to another programming language. C++ is a bad language for beginners; I recommend Python instead.

---

<div class="post-metadata">

**Author:** ![bitwise](https://avatars.discourse-cdn.com/v4/letter/b/ea5d25/32.png) [@bitwise](https://boards.straightdope.com/u/bitwise)\
**Post date:** [December 8, 2005, 7:45am UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/29 "2005-12-08T07:45:11Z")

</div>

> [@Shalmanese](#):
>
> Gah, I don’t know why people insist on using fibonacci to demonstrate recursion. Nobody but a braindead monkey would EVER write fibonacci the pure recursive manner due to it being godawful slow (assuming your not programming in a pure functional language :D). There are so much better examples to demonstrate recursion to a beginner.

Why would a functional language help? You can write a tail recursive function to compute the nth Fibonacci number in linear time by passing two extra parameters.

---

<div class="post-metadata">

**Author:** ![rkts](https://avatars.discourse-cdn.com/v4/letter/r/c4cdca/32.png) [@rkts](https://boards.straightdope.com/u/rkts)\
**Post date:** [December 8, 2005, 8:14am UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/30 "2005-12-08T08:14:38Z")

</div>

> [@bitwise](#):
>
> Why would a functional language help? You can write a tail recursive function to compute the nth Fibonacci number in linear time by passing two extra parameters.

:smack: If that’s what **Derleth** is talking about, then never mind my previous post. I assumed we were doing it the “traditional” way.

---

<div class="post-metadata">

**Author:** ![Derleth](https://avatars.discourse-cdn.com/v4/letter/d/b9e5f3/32.png) [@Derleth](https://boards.straightdope.com/u/Derleth)\
**Post date:** [December 8, 2005, 8:44am UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/31 "2005-12-08T08:44:50Z")

</div>

**Shalmanese** : Note my last sentence in the paragraph you quoted. 😉 More to the point, you’re right _but_ at this point it shouldn’t be a huge burden for compilers to do a bit more than the equivalent of macro processing. We take common subexpression elimination and various other code-factoring for granted (don’t we?), why can’t we similarly rely upon simple algorithmic transformations that have been part of the literature for what, three decades now? Compilers no longer have to fit in 32 kilo-words of core.

(Eh, pardon my rant.)

---

<div class="post-metadata">

**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\
**Post date:** [December 9, 2005, 12:05am UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/32 "2005-12-09T00:05:18Z")

</div>

> [@bitwise](#):
>
> Why would a functional language help? You can write a tail recursive function to compute the nth Fibonacci number in linear time by passing two extra parameters.

In a **pure** functional language, functions cannot have side effects and every call to a function is **guarenteed** to produce the same result. Thus, if you already have computed the result of fac(8), and you see another call to fac(8), then there is no need to compute it again, you can just use your previously stored result.

**Derleth:** it’s not that compilers can’t do such optimisation, it’s that you shouldn’t be relying on them to. Consider if a programmer writes the following snippet of code:

```auto

fib(int n)
{
    if (n < 2)
        return 1;
    return fib(n-1) + fib(n-2);
}

```

Everything is fine and the code runs in 10ms. 5 years later, someone else comes in to maintain the code and they’re just doing some simple profiling, they change the code to:

```auto

int count = 0;
fib(int n)
{
    count++;
    if (n < 2)
        return 1;
    return fib(n-1) + fib(n-2);
}

```

Now, all of a sudden, the code takes 3 hours to run! what the hell happened? How can a simple increment take 3 hours? Everyone is completely baffled and they stay the hell away from modifying the program any further.

Even if something like that didn’t occur, you can break and step through optimised code in the same way you do unoptimised. So anybody relying on that compiler optimisation would have to give up code stepping

[Previous page](https://boards.straightdope.com/t/im-learning-to-code-again/334411.md?page=1)