Home > Archive > Scheme > November 2005 > Will too many paradigms addle my brain.
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Will too many paradigms addle my brain.
|
|
|
| I've just started a comp sci degree. The main language used to teach is
Java - I certainly don't like it but thats the way it is. In the 1st
year we do Java and Prolog (compulsory).
Functional Programming is a 3rd year elective. I reckon I know enough
Scheme to convince the department that I will be able to cope with it
in my 1st year (although I think they use Miranda) and I think I'll be
allowed to choose it.
I am wondering though whether trying to study all 3 paradigms at the
same time is advisable.
Any views.
| |
| Eric Hanchrow 2005-10-11, 7:01 pm |
| >>>>> "wooks" == wooks <wookiz@hotmail.com> writes:
wooks> I am wondering though whether trying to study all 3
wooks> paradigms at the same time is advisable.
If you can't handle three languages in school, you might not be able
to handle three languages in the Real World. Believe me, many jobs
require you to use multiple languages at once; I'm working on
something now that uses
* C++
* perl
* Delphi
* Visual Basic
* SQL
--
Raffarin said he wants to see secure Internet voting in France
by 2009, and he said if he had a homosexual son, he would love
him ...
-- from the Chicago Tribune
| |
| David Hopwood 2005-10-11, 7:01 pm |
| wooks wrote:
> I am wondering though whether trying to study all 3 paradigms at the
> same time is advisable.
Yes it is, definitely. Also get yourself a copy of CTM:
<http://www2.info.ucl.ac.be/people/PVR/book.html>.
--
David Hopwood <david.nospam.hopwood@blueyonder.co.uk>
| |
| Paul Rubin 2005-10-11, 9:57 pm |
| David Hopwood <david.nospam.hopwood@blueyonder.co.uk> writes:
> Yes it is, definitely. Also get yourself a copy of CTM:
> <http://www2.info.ucl.ac.be/people/PVR/book.html>.
Is the final version a lot different than the draft that was online in
pdf form? I read the first few chapters of that and have been wanting
to get around to the rest. However, it didn't much resemble what I
think of as functional programming. And Oz's use of logic variables
for communicating between concurrent processes seemed to invite
deadlock, etc.
| |
| Jon Harrop 2005-10-11, 9:57 pm |
| wooks wrote:
> I am wondering though whether trying to study all 3 paradigms at the
> same time is advisable.
Yes. Paradigms typically complement one another and the more you know of all
of them, the better your code is likely to be in any one of them. However,
I have never found a use for OO.
--
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com
| |
|
|
Jon Harrop wrote:
> wooks wrote:
>
> Yes. Paradigms typically complement one another and the more you know of all
> of them, the better your code is likely to be in any one of them. However,
> I have never found a use for OO.
>
> --
> Dr Jon D Harrop, Flying Frog Consultancy
> http://www.ffconsultancy.com
I will definitely take all 3 but I am not sure you have addressed the
nub of my question though... which is whether it is advisable to do
them simultaneously bearing in mind I will have to pass exams.
| |
|
|
Eric Hanchrow wrote:
>
> wooks> I am wondering though whether trying to study all 3
> wooks> paradigms at the same time is advisable.
>
> If you can't handle three languages in school, you might not be able
> to handle three languages in the Real World. Believe me, many jobs
> require you to use multiple languages at once; I'm working on
> something now that uses
>
> * C++
> * perl
> * Delphi
> * Visual Basic
> * SQL
>
> --
I'm not worried about the real world as I'm already an experienced
programmer. I am focusing on the academic aspect.
Is it a good idea to/better to learn them at the same time when you
don't have to.
| |
| Brian Harvey 2005-10-12, 3:59 am |
| "wooks" <wookiz@hotmail.com> writes:
>Is it a good idea to/better to learn them at the same time when you
>don't have to.
I don't think this can be answered in principle. If you were my advisee,
I'd be asking questions about "what else might you take instead" and "if
not now, when, and along with what else?"
Some of our students do report being  when they are doing two very
different things at once, e.g., SICP along with our machine organization/
machine language course. In one case we are asking them to pay careful
attention to low-level details, and in the other case, the entire project is
to abstract those details away (under the rug). But it sounds as if you will
be studying all more or less high level approaches, so I don't think you'll
be too . On the other hand, you may be more inclined to strangle the
instructor of the OOP course for making things too complicated. :-)
| |
| Cruise Director 2005-10-12, 3:59 am |
| The difficulties of your workload may have nothing to do with computer
paradigms or computer science per se. Beware of biting off more than
you can chew. Maybe you are more productive and disciplined than a
"lazybones" such as myself, but my formula at Cornell always was 1 hard
course, 1 medium difficult course, and 2 easy courses. I did too much
of my own personal, uncredited cogitation to be  dled with relentless
pressure from every possible corner. Frankly I don't believe in it.
Some people think there's moral virtue in it, but I think the vast
majority of people can't handle that much stuff dumped on them all at
once. Better to master 1 thing well.
I'm surprised Jon said he never found a use for OO, as clearly, one has
to talk to all the people in industry who believe in it. :-)
Cheers,
Brandon J. Van Every
(cruise (director (of SeaFunc)
'(Seattle Functional Programmers)))
http://groups.yahoo.com/group/SeaFunc
| |
| Ulrich Hobelmann 2005-10-12, 3:59 am |
| wooks wrote:
> Functional Programming is a 3rd year elective. I reckon I know enough
> Scheme to convince the department that I will be able to cope with it
> in my 1st year (although I think they use Miranda) and I think I'll be
> allowed to choose it.
I don't think they will, because Miranda and Haskell are lazy
functional, while ML and Scheme are strict (i.e. evaluate all their
function arguments first). This leads to quite different programming.
Anyway, learning Miranda in School and Scheme or Lisp at home doesn't
hurt. ;)
> I am wondering though whether trying to study all 3 paradigms at the
> same time is advisable.
Sure, why not? When I started school we had a Scheme class (2nd
semester Java), and I learnt C and asm. Since then I learnt quite a few
other languages (and looked a some others).
Keep your mind open and learn to think in program structure, not
language-specific constructs.
--
State, the new religion from the friendly guys who brought you fascism.
| |
| Jerzy Karczmarczuk 2005-10-12, 3:59 am |
| wooks wrote:
> ...In the 1st
> year we do Java and Prolog (compulsory).
>
> Functional Programming is a 3rd year elective. ...
> I am wondering though whether trying to study all 3 paradigms at the
> same time is advisable.
Several people say "Of course YES...". That the paradigms complement
themselves, that you can compare different views of the same algorithmic
problem, etc. Nice, optimistic, not too far from my own feelings.
But Brian Harvey says:
> I don't think this can be answered in principle. If you were my advisee,
> I'd be asking questions about "what else might you take instead" and "if
> not now, when, and along with what else?"
>
> Some of our students do report being when they are doing two very
> different things at once, e.g., SICP along with our machine organization/
> machine language course.
=
Now, PLEASE, when Brian Harvey says something about the pedagogy of computing,
listen to him, he knows what he says!
It is known from a completely different fairy-tale that children embedded
in a bi-linguistic milieu, and who typically, after some time, master both,
and become perfectly bilingual, acquire both languages at a reduced rate,
they assimilate the same amount of information per time, spread into two
layers.
So an additional question is: can you afford that, if the analogy works in
your case?
I have to say, for example, that I learnt the non-deterministic, monadic
style of the lazy functional implementation of some algorithms much
easier than some of (cleverer than myself) people I know, since I could
translate the stuff to the logic programming paradigms.
The relation, important, although partial and specific, between objects and
closures, is probably easier to grasp when dealing with sequentially.
Anyway, a full-fledged software specialist would need those three paradigms
anyway. But your time-schedule is also a function of many other constraints...
Jerzy Karczmarczuk
| |
| Torben Ćgidius Mogensen 2005-10-12, 8:05 am |
| Jerzy Karczmarczuk <karczma@info.unicaen.fr> writes:
> It is known from a completely different fairy-tale that children embedded
> in a bi-linguistic milieu, and who typically, after some time, master both,
> and become perfectly bilingual, acquire both languages at a reduced rate,
> they assimilate the same amount of information per time, spread into two
> layers.
This is, indeed, a fairy tale. Children who learn two languages when
growing up become equally proficient in their primary language as
children who learn only one, and depending on to what degree the
secondary language is used, they may learn to be fluent in this too.
From the studies I've seen, it is only when they learn three or more
languages that they become , and then only mildly. It may be
because a bilingual family typically has one parent speaking one
language and another parent speaking the other, so the child can keep
the languages apart by asssociating each language with a parent.
> So an additional question is: can you afford that, if the analogy works in
> your case?
>
> I have to say, for example, that I learnt the non-deterministic, monadic
> style of the lazy functional implementation of some algorithms much
> easier than some of (cleverer than myself) people I know, since I could
> translate the stuff to the logic programming paradigms.
>
> The relation, important, although partial and specific, between objects and
> closures, is probably easier to grasp when dealing with sequentially.
>
> Anyway, a full-fledged software specialist would need those three paradigms
> anyway. But your time-schedule is also a function of many other
> constraints...
With programming languages as well as natural languages, the best way
to learn a language is to use it. If you don't have time to make
reasonably sized projects with all the languages you learn, you will
not learn them properly.
However, if you learn languages sequentially, you may have the "ways"
of the first language stuck in your head when learning the second, so
you in the beginning don't really think about the language on its own
premises but rather think about how programs in the language you know
can be converted to the new language. Learning several languages at
the same time and solving the same programming problems in all of them
concurrently would be the ideal way of learning their relative
strengths and weaknesses. But it requires time enough to do this.
Torben
| |
| Joachim Durchholz 2005-10-12, 8:05 am |
| wooks schrieb:
> I am wondering though whether trying to study all 3 paradigms at the
> same time is advisable.
In general, we don't know what your brain can manage :-)
Learning too many paradigms at the same time can indeed be confusing.
On the other hand, the more paradigms you know, the more ways to attack
a problem are at your disposition.
On the third hand, it can be immensely frustrating to be forced to
program in, say, Java, and know that some problem that requires hundreds
of lines of boilerplate code for every class could be done in a single
five-liner in Haskell.
On the fourth hand, any predisposition for this kind of frustration is
something that you'll have to overcome sooner or later, anyway... 90% of
most professional careers consist of legacy code maintenance, which
means that you'll likely be stuck with suboptimal tools 90% of your
professional time.
Actually that's nothing to moan about, it's just the way it is - when
you're writing new software, it will be legacy tomorrow, and the tools
that are top-of-the-cream today will be considered suboptimal when it
comes to maintaining your code.
Personally, I'd go for learning as many paradigms as possible anyway.
I'd start with as many courses as I feel comfortable with, and if things
start to get confusing, I'd drop courses until I can handle the
workload, and come back to them later.
Regards,
Jo
| |
|
|
Brian Harvey wrote:
> "wooks" <wookiz@hotmail.com> writes:
>
> I don't think this can be answered in principle. If you were my advisee,
> I'd be asking questions about "what else might you take instead" and "if
> not now, when, and along with what else?"
>
Well I could do a course on e-business entrepeneurship but we don't get
many electives and I'd rather spend them on something more academic and
see if I can wangle my way on to that course on a not for credit basis.
I do have an imperative/OO background (VB) so should not find Java
unduly difficult whereas in year 2 there will be more Java - Concurrent
Programming which I am not familiar with as well as Compilers.
My background for believing I could cope with a functional programming
course albeit one in Miranda is that I read half of your book over the
summer - Simply Scheme (got a bit stuck on the pattern matching program
but was fine with all the exercises up until then) as well as the first
8 chapters of The Little Schemer (i.e before they introduce
continuations which was too much for my brain at the time).
Strategically I am trying to free up more choice of elective for myself
in Year 3 which is where the university have placed their FP course.
The year 1 and 2 electives are either not practicable or not of
interest.
> Some of our students do report being when they are doing two very
> different things at once, e.g., SICP along with our machine organization/
> machine language course. In one case we are asking them to pay careful
> attention to low-level details, and in the other case, the entire project is
> to abstract those details away (under the rug). But it sounds as if you will
> be studying all more or less high level approaches, so I don't think you'll
> be too .
Well we are not doing SICP (although I hope to read it at some point)
but we are also doing MIPS programming but to me that is such a
different mindset that I am not concerned.
> On the other hand, you may be more inclined to strangle the
> instructor of the OOP course for making things too complicated. :-)
If you mean like having to write about 12 lines of code just to do
Hello World and being encouraged to come to terms with gizmo packed
IDE's , editors (we've been encourage to experiment with 3 different
environments) and API's before we even start programming. Yes.
| |
|
|
Cruise Director wrote:
> The difficulties of your workload may have nothing to do with computer
> paradigms or computer science per se. Beware of biting off more than
> you can chew.
This is not extra work.... I am proposing doing it in place of one the
prescribed 1st year electives.
> Maybe you are more productive and disciplined than a
> "lazybones" such as myself, but my formula at Cornell always was 1 hard
> course, 1 medium difficult course, and 2 easy courses.
Are there any easy courses in a CS degree.
| |
| Brian Harvey 2005-10-12, 7:00 pm |
| "wooks" <wookiz@hotmail.com> writes:
>Well I could do a course on e-business entrepeneurship but we don't get
>many electives and I'd rather spend them on something more academic and
>see if I can wangle my way on to that course on a not for credit basis.
Ugh.
I will tell you right in this message everything in the business curriculum:
1. It's good to be greedy.
2. Assorted techniques for manipulating people who think it
isn't good to be greedy.
Since #1 is false, there's really no need for you to study #2.
But you should definitely think beyond computer science. I don't know where
you're going to school, but I'm willing to bet there are courses available in
literature, philosophy, psychology, art, mathematics, physics, etc.
I advise fitting as many of those in as you can, even if it means a little
less computer science.
| |
| Joe Marshall 2005-10-12, 7:00 pm |
| "wooks" <wookiz@hotmail.com> writes:
> Are there any easy courses in a CS degree.
*Far* too many if the poor quality of many CS graduates is any
indication.
| |
|
|
Joe Marshall wrote:
> "wooks" <wookiz@hotmail.com> writes:
>
>
> *Far* too many if the poor quality of many CS graduates is any
> indication.
I am in one of the top rated schools in the country. I assure you there
aren't any easy courses , however the pass mark for all courses is 40%
so I guess it is possible to achieve a degree with low marks.
| |
| Joe Marshall 2005-10-12, 7:00 pm |
| "wooks" <wookiz@hotmail.com> writes:
> Joe Marshall wrote:
>
> I am in one of the top rated schools in the country.
Great!
I was reminded of Alan Kay's quote:
``Most undergraduate degrees in computer science these days are
basically Java vocational training.''
| |
| Bradd W. Szonye 2005-10-12, 7:00 pm |
| wooks wrote:
Joe Marshall wrote:[color=darkred]
[color=darkred]
> I am in one of the top rated schools in the country.
Even the best schools are hit-or-miss at teaching CS and CE undergrads.
If you're lucky, you'll get instructors who actually enjoy teaching, are
good at teaching, and know the subject well. Even then, you'll only get
a very shallow understanding of the material if you're just looking to
finish your homework and pass your exams.
Undergraduate curricula are modeled after apprenticeships; their goal is
to teach you the basic tools of the thinking man's trade, just as
vocational schools teach you the basics of carpentry, plumbing, etc.
They don't aim for actual mastery of a subject -- that's what the
master's degree program is for (and even masters have very limited
experience).
The "basic tools" for an academic or engineer are critical thinking,
problem-solving skills, and general background material for your
speciality. Unless you go well beyond the course material, you won't
master functional programming (for example); you'll just acquire some
rough familiarity with the paradigm. You certainly won't become an
expert functional programmer just by taking a class, even if the teacher
/is/ excellent and you ace the class.
Unfortunately, it's easy to earn a bachelor's degree with /just/ the
general background material but no real skills, especially if you over-
emphasize the CS/CE portions of your curriculum. Whenever you have a
choice between taking a CS/CE class and taking philosophy, psychology,
literature, art, etc., I'd recommend the humanities class. While there's
no guarantee, in my experience the humanities teachers are a little more
likely than the CS/CE g s to hammer the critical thinking stuff into
you. The gs tend to get hung up on the  details of the subject
instead of the (more important long-term) thinking skills. Philosophy
classes are especially good, so long as you have an engaging professor
or TA.
The other important thing you learn at typical American universities
(not sure if the rest of the world is the same) is work-life balance.
For most undergrads, it's your first experience living on your own.
Learning how to have fun and still get the job done is a big part of
going to school, in my experience. (I was always better at the "having
fun" than the "still getting the job done" part.)
--
Bradd W. Szonye
http://www.szonye.com/bradd
| |
| Jon Harrop 2005-10-12, 7:00 pm |
| Joe Marshall wrote:
> ``Most undergraduate degrees in computer science these days are
> basically Java vocational training.''
I assume Java is taught because it is commercially viable now. However, I
seem to spend most of my time teaching Java programmers in industry how to
use FPLs...
--
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com
| |
|
|
Bradd W. Szonye wrote:
> wooks wrote:
>
> Joe Marshall wrote:
>
>
> Even the best schools are hit-or-miss at teaching CS and CE undergrads.
> If you're lucky, you'll get instructors who actually enjoy teaching, are
> good at teaching, and know the subject well. Even then, you'll only get
> a very shallow understanding of the material if you're just looking to
> finish your homework and pass your exams.
>
I don't believe I said anything here that would have conveyed that
impression.
> Undergraduate curricula are modeled after apprenticeships; their goal is
> to teach you the basic tools of the thinking man's trade, just as
> vocational schools teach you the basics of carpentry, plumbing, etc.
> They don't aim for actual mastery of a subject -- that's what the
> master's degree program is for (and even masters have very limited
> experience).
>
I am doing an undergraduate masters.
> The "basic tools" for an academic or engineer are critical thinking,
> problem-solving skills, and general background material for your
> speciality. Unless you go well beyond the course material, you won't
> master functional programming (for example); you'll just acquire some
> rough familiarity with the paradigm. You certainly won't become an
> expert functional programmer just by taking a class, even if the teacher
> /is/ excellent and you ace the class.
>
It should be apparent from reading from reading my contributions to
this thread that that is not my circumstance.
> Unfortunately, it's easy to earn a bachelor's degree with /just/ the
> general background material but no real skills, especially if you over-
> emphasize the CS/CE portions of your curriculum. Whenever you have a
> choice between taking a CS/CE class and taking philosophy, psychology,
> literature, art, etc., I'd recommend the humanities class.
Our courses are organised into half units.
My first choice of elective was Cognitive Science. The Philosophy
course on offer was a whole unit which would have meant I couldn't do
Cog Sci if I took it. Other options that I considered had timetabling
difficulties. I am not really sing advice on getting an all round
university education. The FP class is one that I want to take to build
on my what I have already learnt and it has the benefit of freeing up
my options in year 3.
> While there's
> no guarantee, in my experience the humanities teachers are a little more
> likely than the CS/CE gs to hammer the critical thinking stuff into
> you.
I studied critical thinking by myself before I even decided to apply to
go to university.
> The gs tend to get hung up on the details of the subject
> instead of the (more important long-term) thinking skills. Philosophy
> classes are especially good, so long as you have an engaging professor
> or TA.
>
I am not a g. I want to do FP. Given a choice I would dump the Java
and OO courses but they are compulsory.
> The other important thing you learn at typical American universities
> (not sure if the rest of the world is the same) is work-life balance.
> For most undergrads, it's your first experience living on your own.
I am a mature student. I have worked in New Zealand, the USA, Africa
and the UK . For a variety of reasons I am doing a degree late in life.
> Learning how to have fun and still get the job done is a big part of
> going to school, in my experience. (I was always better at the "having
> fun" than the "still getting the job done" part.)
Had plenty of fun in my time and think I have a good work/life balance
perspective. I am taking up a completely new sport and have signed up
for some community projects in my first year.
| |
|
|
Joe Marshall wrote:
> "wooks" <wookiz@hotmail.com> writes:
>
>
> Great!
>
> I was reminded of Alan Kay's quote:
>
> ``Most undergraduate degrees in computer science these days are
> basically Java vocational training.''
One of the schools with which we have a international student exchange
program is MIT. I had no idea standards had dropped so far in your old
school.
| |
|
|
Brian Harvey wrote:
> "wooks" <wookiz@hotmail.com> writes:
>
> Ugh.
>
> I will tell you right in this message everything in the business curriculum:
>
> 1. It's good to be greedy.
>
> 2. Assorted techniques for manipulating people who think it
> isn't good to be greedy.
>
> Since #1 is false, there's really no need for you to study #2.
>
>
> But you should definitely think beyond computer science. I don't know where
> you're going to school, but I'm willing to bet there are courses available in
> literature, philosophy, psychology, art, mathematics, physics, etc.
> I advise fitting as many of those in as you can, even if it means a little
> less computer science.
I am taking Cognitive Science and would have taken a maths class as my
last elective but for timetabling clash. I have mentioned in my post
to Bradd why I am not taking Philosophy. I am also doing a course in
academic writing on a not for credit basis.
The main reason I am thinking of bringing forward the FP class is
because there is a wider range of options to choose in year 3 and 4 so
it will free up an extra slot for then.
| |
| Cruise Director 2005-10-12, 7:00 pm |
|
wooks wrote:
> Cruise Director wrote:
>
>
> Are there any easy courses in a CS degree.
I'm not entirely sure. I majored in Sociocultural Anthropology and
minored in CS so that my live would be sane. Also, because Computer
Graphics was cancelled on me sophomore year when I was deciding, and
because all CS professors I had had to date were decidedly dull.
Didn't get the good prof and the good course until I was a junior. I
found a lot of the CS hard, but part of that was because I was drifting
in and out of it with a minor, rather than sticking with it the whole
time. I generally did better on the practical lab courses, i.e.
programming, because I valued them more than the theory courses and put
far more energy into them. I mean, what's more important, book
knowledge or producing something that works and runs fast?
Anyways, nobody said that every course you take has to be in CS. Easy
courses were typically things like Art Appreciation or some crap like
that. I say "crap" only because I had a shitty prof for that. In a
parallel universe I am a painter, and that universe might be
overlapping this one sooner than I'd think.
Cheers,
Brandon J. Van Every
(cruise (director (of SeaFunc)
'(Seattle Functional Programmers)))
http://groups.yahoo.com/group/SeaFunc
| |
| Cruise Director 2005-10-12, 7:00 pm |
|
wooks wrote:
> Joe Marshall wrote:
>
> I am in one of the top rated schools in the country. I assure you there
> aren't any easy courses , however the pass mark for all courses is 40%
> so I guess it is possible to achieve a degree with low marks.
Caveat Emptor. When I went through Cornell you had to sustain a grade
much higher than that to be a major. IIRC, better than the C~'s I was
getting in a number of courses. Otherwise I could have been a double
major, as I was only a few theory / math courses shy of it. I think
that standard persists today. A friend of had to go EE because the CS
dept. wouldn't have him. Berated him for what a bad CS student he was,
etc. Well, when he graduated, he got a job at Microsoft and the vast
majority of his peers didn't. Now, I don't think that's yet another
indication of how shoddy Microsoft is. :-) Rather, he had practical
skill and really knew his stuff. It just wasn't appreciated by the
Cornell CS dept.
Cheers,
Brandon J. Van Every
(cruise (director (of SeaFunc)
'(Seattle Functional Programmers)))
http://groups.yahoo.com/group/SeaFunc
| |
| Cruise Director 2005-10-12, 7:00 pm |
|
Brian Harvey wrote:
>
> I will tell you right in this message everything in the business curriculum:
>
> 1. It's good to be greedy.
>
> 2. Assorted techniques for manipulating people who think it
> isn't good to be greedy.
>
> Since #1 is false, there's really no need for you to study #2.
I dunno, some marketing know-how could be damn useful if you want to
promote your own career, do what you want instead of what others would
force you to do, cause your products to get bought, etc. Maybe not
revel in it, maybe outsource a lot of it to specialists, but certainly
be familiar with basic marketing principles. So sayeth a Cruise
Director.
Cheers,
Brandon J. Van Every
(cruise (director (of SeaFunc)
'(Seattle Functional Programmers)))
http://groups.yahoo.com/group/SeaFunc
| |
| beza1e1 2005-10-13, 8:03 am |
| Speaking as a cs student at Karlsruhe, Germany: yes.
I now got around the first year, where i had the following courses:
Linear Algebra, Higher maths (analysis): hard
Computer Science 2: medium
Computer Science 1, Numeric: easy
Statistics: laughable
I'm not sure how this is comparable to US curriculums. Older students
tell me most people don't take LA and HM both in the first year. I
probably will now have a lazy second half for my undergraduation.
(not sure if i translated all terms correctly)
| |
| Ulrich Hobelmann 2005-10-13, 8:03 am |
| beza1e1 wrote:
> Speaking as a cs student at Karlsruhe, Germany: yes.
>
> I now got around the first year, where i had the following courses:
> Linear Algebra, Higher maths (analysis): hard
> Computer Science 2: medium
> Computer Science 1, Numeric: easy
> Statistics: laughable
I did my Vordiplom in Braunschweig. Lots of hard, hard maths (I got
straight As in high school without any problems, but there I was
fighting through my homework all afternoon and night and barely got
through...), but everything CS-related very, very, very, very easy,
totally laughable. From two ws of reading stuff (one algorithms
book, and SICP) I learned much more than from the first two semesters in
my CS classes. Mostly I didn't bother to even attend them, just worked
on my maths during that time ;) Oh yes, we also did some reasonably
hard theoretical CS and technical CS, not that that did my any good;
I'll never design a CPU, nor do I profit from knowing about weird
constructions to prove the halting problem.
> I'm not sure how this is comparable to US curriculums. Older students
> tell me most people don't take LA and HM both in the first year. I
> probably will now have a lazy second half for my undergraduation.
Hm, at a reportedly quite good Midwest university (undergrad) I found
the 4xx CS classes very easy. OTOH I sometimes read about US undergrads
having compiler classes where they do stuff (such as building whole
compilers in Scheme or SML), which in Germany I did in my 7th semester,
but without much practical or useful emphasis (basically just extracts
from the Dragon book; but a second class involved a very very basic
compiler for the JVM written in C(!) as a group project).
But I think the US have large differences in education, even for the
same degrees.
But since I sat through my first two ws at the University, I gave up
on learning anyway (I do that in my free-time, when I'm not forced to
stuff for college).
You don't learn stuff there (that you couldn't just learn yourself in
20% the time), you just earn your piece of paper ("diploma") by doing
lots of bull**** for whoever teaches (i.e. doing repetitive exercises
that don't teach you anything you don't already know, but you have to do
them anyway; not that the professors would care...).
--
A government which robs Peter to pay Paul can always
depend on the support of Paul.
George Bernard Shaw
| |
| Torben Ćgidius Mogensen 2005-10-13, 8:03 am |
| "wooks" <wookiz@hotmail.com> writes:
> Joe Marshall wrote:
>
> I am in one of the top rated schools in the country. I assure you there
> aren't any easy courses , however the pass mark for all courses is 40%
> so I guess it is possible to achieve a degree with low marks.
The percentage required to pass isn't really a good indication of
quality -- it depends on how difficult the exercises are. 40% of a
number of exercises that require deep insight into the subject may be
a lot harder than 90% of trivial surface knowledge questions.
Torben
| |
| Torben Ćgidius Mogensen 2005-10-13, 8:03 am |
| Joe Marshall <jmarshall@alum.mit.edu> writes:
> I was reminded of Alan Kay's quote:
>
> ``Most undergraduate degrees in computer science these days are
> basically Java vocational training.''
And when they aren't, the students complain (or simply fail to pass
their exams). :-)
You wouldn't believe (well, maybe you would) how often I hear students
complain that our CS curriculum is too "ivory tower" and out of touch
with "real life" (i.e., the internet economy).
Torben
| |
| Garry Hodgson 2005-10-13, 9:56 pm |
| Jon Harrop <usenet@jdh30.plus.com> wrote:
> I have never found a use for OO.
but even if it's not a paradigm you'd choose to use,
it's useful to understand it because so much of the
software, libraries, toolkits, articles, etc. use it.
a friend of mine who was a staunch atheist nonetheless
took his children to church. he felt that if they were
going to live in this country, they'd better understand
the culture, whether he/they believed or not.
----
Garry Hodgson, Technical Consultant, AT&T Labs
Your love, your anger, your kindness, your hate.
All of it creates the future for you and your children.
What kind of future are you creating today?
| |
| Ulrich Hobelmann 2005-10-13, 9:56 pm |
| Garry Hodgson wrote:
> Jon Harrop <usenet@jdh30.plus.com> wrote:
>
>
> but even if it's not a paradigm you'd choose to use,
> it's useful to understand it because so much of the
> software, libraries, toolkits, articles, etc. use it.
Honestly, since even "experts" have discovered that inheritance can be
dangerous and interfaces are much better, most stuff that uses OO really
only uses structs and functions on them, but with the more convenient
field addressing syntax of something like C++ (as compared to C).
That much is the same in every language, i.e. I haven't seen a language
that wouldn't make use of record types in practical code.
While functional languages allow the same kind of inheritance (with
higher-order functions) as OO-langs do, I haven't really the impression
that people use it or need it.
It's good to understand how OO is build on top of standard C-like
languages, just like it's useful to understand all other kinds of
language fundamentals.
> a friend of mine who was a staunch atheist nonetheless
> took his children to church. he felt that if they were
> going to live in this country, they'd better understand
> the culture, whether he/they believed or not.
Heh. My dad let me undergo the same, though he's more of a Buddhist (I
guess). The downside of Christian teaching is that (due to group
pressure or whatever) most people actually believe it (like people in
other countries take Islam or a Buddhist world view for Truth). I used to.
If you tell your kids that Christianity is just part of their culture,
and people in other countries believe entirely different things, and
therefore nobody can ever know which religion is true, that'll make them
a hell of a lot more tolerant than most fundamentalists
*cough*bushists*cough* running around.
--
A government which robs Peter to pay Paul can always
depend on the support of Paul.
George Bernard Shaw
| |
| Joachim Durchholz 2005-10-13, 9:56 pm |
| Cruise Director schrieb:
> I mean, what's more important, book
> knowledge or producing something that works and runs fast?
That depends.
If you're designing large systems, a good measure of theory is actually
indispensable.
The problem is: there's far more theory than anybody really needs, but
you don't know in advance what you'll need. So universities have started
to teach "working with theory" (and, I fear, many professors are using
that as an excuse to spread their ivory-tower theoretic framework, so
this isn't perfect).
Regards,
Jo
| |
| Brian Harvey 2005-10-13, 9:56 pm |
| Ulrich Hobelmann <u.hobelmann@web.de> writes:
> nor do I profit from knowing about weird
>constructions to prove the halting problem.
It's a shame that you feel that way. First, a shame that you think about
your education in terms of "profit from," if I'm correctly understanding that
to mean "this will have direct application to my future job." Do you feel
that way about all the math courses you took? And second, a shame that you
don't see the beauty and the phenomenal genius in Turing's development of a
way to prove things about the theoretical limits of computers at a time when
they were just beginning to build actual ones.
>You don't learn stuff there (that you couldn't just learn yourself in
>20% the time)
In a sense this is true about any learning of anything -- you could do it
on your own with some effort. Nevertheless, many people find it beneficial
to be part of a community of scholars, helping each other learn and push the
limits of what's known. Perhaps you are overgeneralizing from a few bad
teaching experiences?
| |
| zitterbewegung@gmail.com 2005-10-13, 9:56 pm |
| Lisp is like kung FOO! Lisp is a meta paradigm. WIthout lisp you
can't understand any other languages.learning the language makes you a
better person. Computer Science is the assault of paradigm to
languages. Lisp is the only thing that has survived for 40 years and it
should be respected. Another meta paradigm is the construction of new
languages. That is what we call Backus Normal Form. Learn both and then
write a lisp macro that does something useful.
| |
| Neelakantan Krishnaswami 2005-10-13, 9:56 pm |
| In article <dij5os$823$1@abbenay.CS.Berkeley.EDU>, Brian Harvey wrote:
> "wooks" <wookiz@hotmail.com> writes:
>
> Ugh.
>
> I will tell you right in this message everything in the business curriculum:
>
> 1. It's good to be greedy.
> 2. Assorted techniques for manipulating people who think it
> isn't good to be greedy.
>
> Since #1 is false, there's really no need for you to study #2.
This is a rather blinkered outlook. I had a great deal of fun working
at a startup, and the main things that I learned while working at a
startup were humility and a sense of service.
The job of a businessperson is to organize a group of people to create
goods and services so useful that other people will voluntarily part
with their hard-earned money for them. Doing a good job at this is
quite a bit harder than it might seem, since it's fundamentally an act
of empathy and creativity -- you have to focus on what someone else
needs, and understand their needs well enough to create things that
are both valuable to them and whose value can be communicated. But
there's a lot of organizational cruft associated with running a
business, and learning how to handle it is a very useful skill.
In fact, my main regret is going to work at a startup, rather than
starting up a business myself.
> But you should definitely think beyond computer science. I don't
> know where you're going to school, but I'm willing to bet there are
> courses available in literature, philosophy, psychology, art,
> mathematics, physics, etc. I advise fitting as many of those in as
> you can, even if it means a little less computer science.
This is good advice, though. My only caveat is that I found that
reading great literature was more useful than literature classes. I'd
suggest reading on your own and taking writing classes instead.
--
Neel Krishnaswami
neelk@cs.cmu.edu
| |
| Torben Ćgidius Mogensen 2005-10-14, 3:58 am |
| "zitterbewegung@gmail.com" <zitterbewegung@gmail.com> writes:
> Lisp is the only thing that has survived for 40 years and it should
> be respected.
What we call LISP today has only a superficial resemblance to the LISP
of 40 years ago. Same with Fortran and COBOL (that also existed 40+
years ago). Who was it that said "I don't know which language people
will use in the year 2000, but I know they will call it Fortran!"?
And while LISP, Fortran and COBOL retained their names while changing,
you can argue that Algol is still with us in the shape of C, Java and
similar languages. See the "family tree" of programming languages at
http://www.levenez.com/lang/history.html for more details.
Torben
| |
| Lauri Alanko 2005-10-14, 7:57 am |
| In article <3r6ugdFhe05lU1@individual.net>,
Ulrich Hobelmann <u.hobelmann@web.de> wrote:
> nor do I profit from knowing about weird constructions to prove the
> halting problem.
I doubt that. I believe everyone stumbles into Rice's Theorem sooner
or later. It's good to be ready for that:
"All right, we need something that analyzes a program and tells
whether it--"
"Sorry, can't be done."
This can save anything from minutes of fruitless pondering to
man-years of work in vain. :)
Lauri
| |
| Ulrich Hobelmann 2005-10-14, 7:57 am |
| Brian Harvey wrote:
> Ulrich Hobelmann <u.hobelmann@web.de> writes:
>
> It's a shame that you feel that way. First, a shame that you think about
> your education in terms of "profit from," if I'm correctly understanding that
> to mean "this will have direct application to my future job." Do you feel
No, actually not. I went to University (while we have practical schools
too in Germany) because I was interested in more thorough background
knowledge, not just applied stuff. But when I have to learn a theory, I
expect that it is for handling a practical problem in a formal way.
It seems that an awful lot of theoretical CS is just theory without
applications, while the practical people (who seem to hate theory) don't
even bother to use formal methods or study principles behind programming
for instance, but just create ad-hoc solutions / languages instead
(often under the discipline name software engineering). The gap in
between is what I'd be interested in, but there aren't too many people
teaching that I guess.
The contrived construction of a funny machine that can't be proven to
halt isn't interesting to me. Many practical algorithms don't just
infinite-loop, and the people writing code *know* that their code (most
often) won't loop. The same with Gödel's stuff. I don't consider weird
constructions practical or useful at all, just because there exists one
totally made up case that refutes something.
> that way about all the math courses you took? And second, a shame that you
> don't see the beauty and the phenomenal genius in Turing's development of a
> way to prove things about the theoretical limits of computers at a time when
> they were just beginning to build actual ones.
Ok, it's nice to know that there are limits, but I'd rather be concerned
about practical limits. Turing machines are a weird design to begin
with (one-dimensional tape, infinite...).
>
> In a sense this is true about any learning of anything -- you could do it
> on your own with some effort. Nevertheless, many people find it beneficial
> to be part of a community of scholars, helping each other learn and push the
> limits of what's known. Perhaps you are overgeneralizing from a few bad
> teaching experiences?
Mostly I just think my degree's first two years were a TOTAL waste of
time. Ok, in my free time I read lots of (to me) interesting stuff, so
the years afterwards weren't too exciting either, but had I had those
years right at the beginning, they would have been. There are really
interesting things in theoretical (let's call it "formal") CS, such as
semantics, process calculi, type systems, automata, but incomputability
is more a legend that CS people should have heard of, than something
they should have to study in depth, IMHO.
--
A government which robs Peter to pay Paul can always
depend on the support of Paul.
George Bernard Shaw
| |
| Matthias Kretschmer 2005-10-14, 7:57 am |
| On 2005-10-14, Ulrich Hobelmann <u.hobelmann@web.de> wrote:
> Brian Harvey wrote:
>
> No, actually not. I went to University (while we have practical schools
> too in Germany) because I was interested in more thorough background
> knowledge, not just applied stuff. But when I have to learn a theory, I
> expect that it is for handling a practical problem in a formal way.
>
> It seems that an awful lot of theoretical CS is just theory without
> applications, while the practical people (who seem to hate theory) don't
> even bother to use formal methods or study principles behind programming
> for instance, but just create ad-hoc solutions / languages instead
> (often under the discipline name software engineering). The gap in
> between is what I'd be interested in, but there aren't too many people
> teaching that I guess.
>
> The contrived construction of a funny machine that can't be proven to
> halt isn't interesting to me. Many practical algorithms don't just
> infinite-loop, and the people writing code *know* that their code (most
> often) won't loop. The same with Gödel's stuff. I don't consider weird
> constructions practical or useful at all, just because there exists one
> totally made up case that refutes something.
the trick is here, that most programming languages are equivalent to
Turing Machines, just that they are simpler than most languages. On the
other hand they are not really impractical. If you consider infinite
tapes as impractical than programming languages that don't bound your
memory usage are impractical, too (well I know many of them). And look
at the book of Schoenhage et.al. "Fast Algorithms - A Multitape Turing
Machine Implementation"
(http://www.informatik.uni-bonn.de/~schoe/tp/TPpage.html).
>
>
> Ok, it's nice to know that there are limits, but I'd rather be concerned
> about practical limits. Turing machines are a weird design to begin
> with (one-dimensional tape, infinite...).
>
>
> Mostly I just think my degree's first two years were a TOTAL waste of
> time. Ok, in my free time I read lots of (to me) interesting stuff, so
> the years afterwards weren't too exciting either, but had I had those
> years right at the beginning, they would have been. There are really
> interesting things in theoretical (let's call it "formal") CS, such as
> semantics, process calculi, type systems, automata, but incomputability
> is more a legend that CS people should have heard of, than something
> they should have to study in depth, IMHO.
>
In good classes you should learn a lot, even for pratical purposes.
There is of course some kind of theory that you can't directly apply
practical problems, for example the PCP-theorem is only indirectly
useful in practice, because we don't have PCP-machines, but you can
proof some stuff concerning the APX, PTAS, EPTAS, etc. classes which
are very interesting for practical purposes. E.g. you have some problem
and you need to have an algorithm that quickly calculates the solution
of an instance. If you have this theoretical background you can save a
lot of time, if you don't, well ... (I assume P unequal to NP for now).
The halting problem is tightly connected to problems found in practical
problems and theories like type theory. If you want to ensure that your
type system is decideable you know you can't have the power of a turing
machine. If you want this power, your compiler may not halt on every
module/program instance. Looking at a compiler in more detail. You have
different passes, e.g. look at register allocation. register allocation
is as hard as graph colouring if you have an architecture where the
registers are different and depending on the operation you have to
choose a different one like x86. If you know how good one is able to
approximate graph colouring you know how bad a compiler is at this as
long as (as long as P != NP) no worst-case super-polynomial time
register allocation algorithm is used. This are just some examples, so I
hope you see, having this theoretical background is a good thing in case
one wants to do things right.
Knowing just of these complexity classes or other kind of theoretical
stuff is often not enough, because in reality you don't get your 3SAT
problem or Graph Colouring. You get problem XYZ and you have to figure
out from there. Sometimes, as in the case of register allocation, it is
trivial to reduce it to graph colouring or more important find a
L-reducation for XYZ to some known problem.
--
Matthias Kretschmer
| |
| Joachim Durchholz 2005-10-14, 7:57 am |
| Ulrich Hobelmann schrieb:
> Brian Harvey wrote:
>
>
> No, actually not. I went to University (while we have practical schools
> too in Germany) because I was interested in more thorough background
> knowledge, not just applied stuff. But when I have to learn a theory, I
> expect that it is for handling a practical problem in a formal way.
The halting problem *is* a practical one. It would be nice if there were
a way to check that you haven't inadvertently written an endless loop.
Compilers could warn about nonterminating recursion.
Also, there's a whole class of problems that can be mapped to the
halting problem (the undecidable ones). Knowing which kind of problem is
in that class is of practical value, too.
Of course, the proof that the halting problem cannot be handled
algorithmically isn't in itself practical. No proof that tells us "this
can't be done" is practical. So from a practical perspective, you can be
content with the proof.
On the other hand, if you have a problem and are unsure whether it's
decidable, knowing such proof techniques can help deciding. So there is
some remote practical use even for this kind of knowledge.
> Many practical algorithms don't just
> infinite-loop, and the people writing code *know* that their code (most
> often) won't loop.
Ah, but I had one such instance. I was writing a table control - very
basic down-to-earth GUI stuff.
The "interesting" part here was that row height was determined by
contents. I had to divide the processing into two phases: height
determination and actual laying-out. It's *very* easy to confuse the
steps, and that usually ends up with the laying-out part recursing back
into the height determination code - sometimes that will terminate,
sometimes it will not.
This kind of work isn't too common, with that I agree. But termination
problems can happen if you're doing things that aren't straightforward.
> The same with Gödel's stuff. I don't consider weird
> constructions practical or useful at all, just because there exists one
> totally made up case that refutes something.
It's not the weird construction that's interesting, it's the refutation.
> Ok, it's nice to know that there are limits, but I'd rather be concerned
> about practical limits. Turing machines are a weird design to begin
> with (one-dimensional tape, infinite...).
They are commonplace simply because they are the easiest-to-explain
equivalent of an infinite computer. In the 50ies, when it was unclear
what an algorithm could do or not, and when it was unclear whether
different ways to writing down algorithms would affect the power or not,
people invented dozens of algorithmic notations. Turing machines and the
lambda calculus are what is still in (relatively) common knowledge, but
there were others, and some of them were *really* weird.
The Turing machine survived because it was easiest to prove some things
with it, and because every other formalism could be proved to be
Turing-equivalent.
The lambda calculus survived because it's so abstract that it has served
as a model for many a programming language.
That's all. You don't *need* to know about Turing machines; it's just
that you won't understand the term "Turing equivalence" unless you know
what a Turing machine is.
> Mostly I just think my degree's first two years were a TOTAL waste of
> time.
Me too, in a sense. It was dedicated to learning programming, something
that I had done in my free time before. It was rather sparse on theory,
which was the area where I *could* learn.
The theoretical backgrounds have helped me a lot. It's simply additional
perspectives, and I can make use of them when I'm doing advanced stuff.
Learning this stuff was also a rewarding experience for me, but of
course that's no justification for forcing this stuff on students that
may not feel rewarded. The additional-perspective argument is.
> Ok, in my free time I read lots of (to me) interesting stuff, so
> the years afterwards weren't too exciting either, but had I had those
> years right at the beginning, they would have been. There are really
> interesting things in theoretical (let's call it "formal") CS, such as
> semantics, process calculi, type systems, automata, but incomputability
> is more a legend that CS people should have heard of, than something
> they should have to study in depth, IMHO.
Sorry, that's an undefensible position. You need to know about
decidability if you design type systems, or any kind of inference engine.
You also need to know about decidability to assess the limitations of
inference engines, to check whether the limitations are arbitrary or
really due to undecidability issues.
This knowledge also helps when *using* such engines. If you know that
what you're trying to achieve is undecidable, you automatically try to
transform the problem into something decidable. You know quite exactly
what information needs to be added so that the engine can work.
Without that background knowledge, exploring the problem space is
largely guesswork.
Regards,
Jo
| |
| Lauri Alanko 2005-10-14, 7:57 am |
| In article <3r9binFi2qh6U1@individual.net>,
Ulrich Hobelmann <u.hobelmann@web.de> wrote:
> knowledge, not just applied stuff. But when I have to learn a theory, I
> expect that it is for handling a practical problem in a formal way.
Science involves both basic research and applied research. Basic
research strives only to deepen our understanding about things without
aspiring towards practical applications. A university is a scientific
institution, so it's no wonder that some things being taught there are
not eminently practical. If you don't like this approach, then the
university is probably not the right place for you.
That being said, one of the wonderful things about science is that
anything at all may turn out to have unexpected practical
applications. It's just impossible to know beforehand, which. If
people were taught only things whose practical uses were well-known,
no one would ever come up with applications for other things.
> The contrived construction of a funny machine that can't be proven to
> halt isn't interesting to me. Many practical algorithms don't just
> infinite-loop, and the people writing code *know* that their code (most
> often) won't loop.
If they do, they know it because they have proven it.
> Ok, it's nice to know that there are limits, but I'd rather be concerned
> about practical limits.
Practical limits change all the time. Theoretical ones don't. Guess
which ones are more useful to know about in the long run?
> Mostly I just think my degree's first two years were a TOTAL waste of
> time.
If you don't find use for what you have learned, why do you think the
problem is in what you learned? You might just as well think that
there's something wrong with what you are doing, or how you are doing
it, if you don't get to apply your knowledge enough.
> There are really interesting things in theoretical (let's call it
> "formal") CS, such as semantics, process calculi, type systems,
> automata, but incomputability is more a legend that CS people should
> have heard of, than something they should have to study in depth,
> IMHO.
That's funny, as all of the interesting examples you mention involve
incomputability e.g. in the form of undecidability. Don't you think it
is at all interesting to know e.g. whether a compiler will actually
finish when given a program to compile? Or do you think it's ok for
any old program to get stuck occasionally? You can always push
control-C?
Lauri
| |
| Vesa Karvonen 2005-10-14, 7:57 am |
| In comp.lang.scheme Lauri Alanko <la@iki.fi> wrote:
> [...] If people were taught only things whose practical uses were
> well-known, no one would ever come up with applications for other
> things.
Other than the above, I think that you are right on the money. However, I
don't think that teaching practical things, or teaching theory through
applications, or teaching abstractions through concrete examples,
necessarily stiffles creativity. If anything, I believe that
applications of theoretical insights can motivate most people to learn
more theory.
-Vesa Karvonen
| |
| Joachim Durchholz 2005-10-14, 7:57 am |
| zitterbewegung@gmail.com schrieb:
> Lisp is like kung FOO! Lisp is a meta paradigm.
Nope. Lisp is a family of languages, not a paradigm. It is quite
flexible, and can be used for many paradigms - but you still have to
learn the paradigms; Lisp is just the "substrate".
> WIthout lisp you can't understand any other languages.
Nonsense. I have learned Lisp, and yes it was an eye-opener since it
introduced me into higher-order functions - but I would have learned
that from Haskell, or any other FPL.
> Learning the language makes you a better person.
Now that's *utter* nonsense. Unless you specify what you mean with
"better person".
It certainly doesn't make me more compassionate, for one instance :-)
> Computer Science is the assault of paradigm to languages.
Doesn't compute.
> Lisp is the only thing that has survived for 40 years and it
> should be respected.
If that were of any relevance, I'd also have to respect Fortran and RPG.
Fortran... well, current-day Fortran bears little to no resemblance to
40-year-old Fortran dialects, so it doesn't really count.
But RPG? It's an unspeakable evil from ancient times, and should better
be left untouched. (For the curious and foolhardy: three-address code,
GOSUB but no local variables, no pointers, no variable-length strings,
variable names limited to six characters. And that's just the largest
deficits, there are numerous useless limitations in the details.)
I do respect Lisp. I wouldn't respect it for its age along, though that
certainly adds to the respect.
> Another meta paradigm is the construction of new languages. That is
> what we call Backus Normal Form.
BNF is unrelated to Lisp.
> Learn both and then write a lisp macro that does something useful.
I have always been sceptical about self-definable syntax. It tends to
encourage code that nobody but the original macro author understands.
Regards,
Jo
| |
| Ulrich Hobelmann 2005-10-14, 7:57 am |
| Matthias Kretschmer wrote:
>
> the trick is here, that most programming languages are equivalent to
> Turing Machines, just that they are simpler than most languages. On the
> other hand they are not really impractical. If you consider infinite
> tapes as impractical than programming languages that don't bound your
> memory usage are impractical, too (well I know many of them). And look
> at the book of Schoenhage et.al. "Fast Algorithms - A Multitape Turing
> Machine Implementation"
> (http://www.informatik.uni-bonn.de/~schoe/tp/TPpage.html).
But isn't the Lambda Calculus, or Recursive Functions equivalent in
power to the funny tape machine? Both are much easier to understand,
IMHO, and the first one even provides the basis for lots of programming
languages. Why does every CS student have to suffer through the Turing
stuff, but most haven't even *heard* of Lambda Calculus? This just
doesn't make sense to me.
> If you have this theoretical background you can save a
> lot of time, if you don't, well ... (I assume P unequal to NP for now).
Yes, that's one thing one should know.
> The halting problem is tightly connected to problems found in practical
> problems and theories like type theory. If you want to ensure that your
> type system is decideable you know you can't have the power of a turing
> machine. If you want this power, your compiler may not halt on every
> module/program instance. Looking at a compiler in more detail. You have
> different passes, e.g. look at register allocation. register allocation
> is as hard as graph colouring if you have an architecture where the
> registers are different and depending on the operation you have to
> choose a different one like x86. If you know how good one is able to
> approximate graph colouring you know how bad a compiler is at this as
> long as (as long as P != NP) no worst-case super-polynomial time
> register allocation algorithm is used. This are just some examples, so I
> hope you see, having this theoretical background is a good thing in case
> one wants to do things right.
Sure, one should know some facts, but I don't see the use of studying
all the theoretical background behind it as very necessary. Students
can always read up on it, and one of the most important things to learn
in CS is *where* to find things, not exactly how everything works in
detail. The world is too big for that.
> Knowing just of these complexity classes or other kind of theoretical
> stuff is often not enough, because in reality you don't get your 3SAT
> problem or Graph Colouring. You get problem XYZ and you have to figure
> out from there. Sometimes, as in the case of register allocation, it is
> trivial to reduce it to graph colouring or more important find a
> L-reducation for XYZ to some known problem.
Maybe sometimes... ;)
--
A government which robs Peter to pay Paul can always
depend on the support of Paul.
George Bernard Shaw
| |
| Ulrich Hobelmann 2005-10-14, 7:57 am |
| Lauri Alanko wrote:
> In article <3r9binFi2qh6U1@individual.net>,
> Ulrich Hobelmann <u.hobelmann@web.de> wrote:
>
> Science involves both basic research and applied research. Basic
> research strives only to deepen our understanding about things without
> aspiring towards practical applications. A university is a scientific
> institution, so it's no wonder that some things being taught there are
> not eminently practical. If you don't like this approach, then the
> university is probably not the right place for you.
I just wish the emphasis had been different... Many things could have
been done in shorter time, and they could have taught students more
interesting stuff. As it is, everybody I know *hates* theoretical CS,
and I only don't because I know there are advanced things out there.
You could say we only learn '60s and '70s stuff. The same goes for
operating system, for instance. Semaphores are , and you should
understand them. But *writing* programs with them for 3-4 ws, and
the prof never telling you about more modern approaches (process
calculi, message passing) that programmers can actually write
non-deadlocking programs in (try to write a large multithreaded program
given only semaphores ;) ), is nonsense. Our programming teaching
focuses on Algol-derivatives, nothing else. For a *university*, the
highest possible ivory tower in my country, that's clearly unacceptable.
I only have to think of all the things most graduates here will never
have heard of in their whole life and I wonder why we spend so much time
doing nothing.
>
> That's funny, as all of the interesting examples you mention involve
> incomputability e.g. in the form of undecidability. Don't you think it
> is at all interesting to know e.g. whether a compiler will actually
> finish when given a program to compile? Or do you think it's ok for
> any old program to get stuck occasionally? You can always push
> control-C?
Well, for instance most compilers process an abstract syntax tree
underneath. These ASTs are defined recursively/inductively, so at some
point the recursion *has* to end. This simple knowledge is far more
relevant to me than the fact that there are loops or recursion patterns
that nobody *wants* to program, that never terminate. By the way, most
computer software probably isn't even supposed to terminate!
--
A government which robs Peter to pay Paul can always
depend on the support of Paul.
George Bernard Shaw
| |
| Lauri Alanko 2005-10-14, 7:57 am |
| In article <3r9kcnFil2vlU1@individual.net>,
Ulrich Hobelmann <u.hobelmann@web.de> wrote:
> Why does every CS student have to suffer through the Turing
> stuff, but most haven't even *heard* of Lambda Calculus? This just
> doesn't make sense to me.
I have often wondered the same. I think it is mostly just for
historical reasons. Many concepts about computability are _much_
simpler to grasp in LC. For example, LC programs are much easier to
compose together than Turing machines.
Then again, there is some justification for TMs: arguably, of the
various equivalent models of computation, TMs are most
"down-to-earth", i.e. closest to physical reality. This gives it
credibility, since the _point_ of the computational models is that
they should express things that are really computable in the real
world.
> Sure, one should know some facts, but I don't see the use of studying
> all the theoretical background behind it as very necessary. Students
> can always read up on it, and one of the most important things to learn
> in CS is *where* to find things, not exactly how everything works in
> detail. The world is too big for that.
You are exactly right. That's why basic undergrad education just
glances quickly at about gazillion things: you don't really learn
anything "deeply" but later, you'll remember "hey, I remember reading
about something like this at that class..."
And reading through the proof of the undecidability of the halting
problem is _not_ very deep. The average student walks away with a
vague feeling that there was some problem about halting that couldn't
be solved, and he'll know where to look for more info if he ever needs
it. It's valuable, but not very much. If the theorem was only stated
in the class _without_ going through the proof, the average student
would forget completely about it after the exam. :)
Lauri
| |
| Gary Baumgartner 2005-10-14, 7:00 pm |
| In article <dio2nq$uks$1@online.de>,
Joachim Durchholz <jo@durchholz.org> wrote:
[...]
>I have always been sceptical about self-definable syntax. It tends to
>encourage code that nobody but the original macro author understands.
Would you claim this about functions, datatypes or classes?
What's so different about (my-function a ...) versus (my-macro a ...)?
Don't you just see "my-function" or "my-macro" and look up its documentation?
Gary Baumgartner
| |
| Matthias Blume 2005-10-14, 7:00 pm |
| Ulrich Hobelmann <u.hobelmann@web.de> writes:
> The contrived construction of a funny machine that can't be proven to
> halt isn't interesting to me. Many practical algorithms don't just
> infinite-loop, and the people writing code *know* that their code
> (most often) won't loop. The same with Gödel's stuff. I don't
> consider weird constructions practical or useful at all, just because
> there exists one totally made up case that refutes something.
It is interesting (and should be interesting to anyone with an
interest in computing) in the sense that it gives an upper bound on
what can be done. There are quite practical problems whose
solvability would be very desirable, but which are not solvable in
general. Many examples can be derived directly from Rice's theorem,
which in turn is an almost /immediate/ consequence of the
unsolvability of the Halting Problem. In particular, we cannot
construct a machine that that can compare two arbitrary programs for
semantic equality. Similarly, there can be no "perfect" optimizer
that yields the smallest or fastest equivalent to a given program.
Of course, there are stronger constraints, such as complexity
constraints, that can make particular problems infeasible to be solved
precisely on a computer. NP-hardness can be a serious bummer (unless
there exists a good enough approximation algorithm), and even a lower
bound of n^3 or n^2 can be a serious problem depending on the
application.
The bottom line is that in order to understand these things one has to
have a firm graps of what one's computational model is, what it can
do, and what it can't.
By the way, the whole point of discussing the Halting Problem is to
show that there are /practically relevant/ problems which cannot be
solved on a computer. If it weren't for that, a simple cardinality
argument is all that is needed to show that there exist incomputable
functions.
>
> Ok, it's nice to know that there are limits, but I'd rather be
> concerned about practical limits. Turing machines are a weird design
> to begin with (one-dimensional tape, infinite...).
Yes, discussing practical limits is important. The notion of
NP-hardness and NP-completeness has spawned a huge amount of research.
Few theoreticians today worry about the Halting Problem -- that's just
a given. Everybody worries about upper and lower bounds (and hopes
them to be at most polynomial).
The Turing Machine (which is not my favorite model of computation
either, btw.) is constructed the way it is to be /extremely simple/.
Apart from the idealization of having an infinite tape, it is obvious
that it can be practically realized. With the lambda calculus or
mu-recursive functions one needs a few steps to see that (usually by
showing how to implement them on something akin to the TM).
> Mostly I just think my degree's first two years were a TOTAL waste of
> time.
I am beginning to agree with you. At least you don't sound like to
"got" it.
> Ok, in my free time I read lots of (to me) interesting stuff,
> so the years afterwards weren't too exciting either, but had I had
> those years right at the beginning, they would have been. There are
> really interesting things in theoretical (let's call it "formal") CS,
> such as semantics, process calculi, type systems, automata, but
> incomputability is more a legend that CS people should have heard of,
> than something they should have to study in depth, IMHO.
If you are capable of understanding type systems in depth, you should
have no problem with computability. The proof of the unsolvability of
the Halting Problem is completely trivial and fits on a few lines once
you have the notion of a universal function in place. A universal
function, in turn, is a fundamental concept that you can't weasel
around: it is the essence most existing programming language
implementations. If you study type systems, you have to understand
things like strong normalization, system F, etc. One important
property that a type system either possesses or doesn't is
decidability. And that's directly related to computability.
If you really think that studying (in)computability was a waste of
time, your entire CS education has been a waste of time.
Regards,
Matthias
| |
| Matthias Blume 2005-10-14, 7:00 pm |
| Lauri Alanko <la@iki.fi> writes:
> Then again, there is some justification for TMs: arguably, of the
> various equivalent models of computation, TMs are most
> "down-to-earth", i.e. closest to physical reality. This gives it
> credibility, since the _point_ of the computational models is that
> they should express things that are really computable in the real
> world.
Yes, that's the main point behind TMs. One other issue that comes up
with the LC is that there is a less obvious complexity model. What is
the time and space consumption of a LC reduction sequence? Counting
beta steps is not good enough as on a real machine one needs to
implement deep substitution. One could go to explicit substitutions
(i.e., the lambda-sigma calculus with DeBruijn indices etc), but that
is *much* more complicated, especially to the uninitiated. Similar
things can be said about space consumption. Again, simply looking at
the size of an expression might not be good enough because of sharing.
Reasoning about sharing is not easy at all. (There is a reason why
optimal reductions have been studied for such a long time.)
Of course, this being said, the TM is not a very good (read:
realistic) model for thinking about complexity either. That's why
there are also plenty of other models out there. But at least it is
easy to analyze on its own terms should you choose to do so. That's
something that cannot be said quite so easily about the LC.
> And reading through the proof of the undecidability of the halting
> problem is _not_ very deep.
Yes. The proof is dead simple. All the real work is in the
construction of the universal function.
Matthias
| |
|
|
| Matthias Blume 2005-10-14, 7:00 pm |
| Ulrich Hobelmann <u.hobelmann@web.de> writes:
> Well, for instance most compilers process an abstract syntax tree
> underneath. These ASTs are defined recursively/inductively, so at
> some point the recursion *has* to end. This simple knowledge is far
> more relevant to me than the fact that there are loops or recursion
> patterns that nobody *wants* to program, that never terminate.
That's a naive (or shall I say: uninformed) view of what a compiler
does. Yes, the frontend will terminate, fine. What about the
optimizer? If the optimizer performs abstract interpretation of some
form, it might not terminate unless one is careful. If it performs
partical evaluation, it might not terminate. If it "evaluates under
the lambda" it might not terminate. A few years ago an otherwise
excellent entry in the ICFP programming contest (raytracer) stumbled
over this problem by being over-agressive in its implementation of the
GML language where an infinite loop in an otherwise unused texture
would send it into an infinite loop...
These things /do/ matter in practice!
> By the way, most computer software probably isn't even supposed to
> terminate!
Nonsense. Almost every computer software I know is supposed to terminate, at
least given the appropriate input:
An application should shut quit after I press Apple-Q, an OS should
shut down after I issue the "shutdown" command, an interactive program
should eventually come back and wait for new input from the user, and
so on and so on.
And even if you consider embedded software that controls some
long-running device, there is usually a pretty obvious decomposition
of the program into a terminating program which is run repeatedly.
Matthias
| |
| Antoun Kanawati 2005-10-14, 7:00 pm |
| Ulrich Hobelmann wrote:
> It seems that an awful lot of theoretical CS is just theory without
> applications, while the practical people (who seem to hate theory) don't
> even bother to use formal methods or study principles behind programming
> for instance, but just create ad-hoc solutions / languages instead
> (often under the discipline name software engineering). The gap in
> between is what I'd be interested in, but there aren't too many people
> teaching that I guess.
The dichotomy of "practical" vs "theoretical" is false.
Good practical choices are often backed by good theory.
Besides the amount of theory that you need in practice varies with the
kind of practice you do. If you're writing some simple application,
you may find all that theory totall wasted. But, if you're writing
a compiler, you may find that theory comes in very handy.
> The contrived construction of a funny machine that can't be proven to
> halt isn't interesting to me. Many practical algorithms don't just
> infinite-loop, and the people writing code *know* that their code (most
> often) won't loop. The same with Gödel's stuff. I don't consider weird
> constructions practical or useful at all, just because there exists one
> totally made up case that refutes something.
The weird construction is NOT the point, it merely proves a very
important statement with significant implications on the limitations
of real practical programs. As in: you cannot write a program to
decide whether another program will (or will not) halt on a particular
input.
And, we know, from practice, that infinite loops occur. Put the two
together, and you understand why no compiler writer has bothered
implementing a warning for infinite loops, or various other
runtime pathologies, in spite of our ability to detect many of these
cases by visually inspecting the code.
Throw in complexity theory, analysis of algorithms, etc... and now
you have a good foundation for estimating the computational cost of
your practical solutions, BEFORE you start designing and implementing
them.
> Ok, it's nice to know that there are limits, but I'd rather be concerned
> about practical limits. Turing machines are a weird design to begin
> with (one-dimensional tape, infinite...).
This particular limit (halting is undecidable) is PRACTICAL and
UNIVERSAL. The universality derives primarily from the essential
simplicity of the Turing Machine.
And, you should note that the approach is VERY PRACTICAL, since
it make generalization very easy.
> Mostly I just think my degree's first two years were a TOTAL waste of
> time. Ok, in my free time I read lots of (to me) interesting stuff, so
> the years afterwards weren't too exciting either, but had I had those
> years right at the beginning, they would have been. There are really
> interesting things in theoretical (let's call it "formal") CS, such as
> semantics, process calculi, type systems, automata, but incomputability
> is more a legend that CS people should have heard of, than something
> they should have to study in depth, IMHO.
Computability (and lack thereof) is only a small part of a formal
education, and it happens to be a fundamental part of it, since it
defines a universal limit on our ability to solve problems by
algorithmic means. I don't undestand why you're singling it out.
--
A. Kanawati
| |
| Ulrich Hobelmann 2005-10-14, 7:00 pm |
| Matthias Blume wrote:
>
> I am beginning to agree with you. At least you don't sound like to
> "got" it.
Back then I got it alright. I just stopped caring about these things.
Since my time is limited, I'd rather spend it on things that help me in
real-life, such as getting a job. The world has enough problems, so I
don't worry about computational limits anymore. Ask 80+% of CS people
in the world if they *really* apply this theory in their daily
programming, and I think most don't. Except in this newsgroup I've
never heard of one.
>
> If you are capable of understanding type systems in depth, you should
> have no problem with computability. The proof of the unsolvability of
> the Halting Problem is completely trivial and fits on a few lines once
> you have the notion of a universal function in place. A universal
It's not about understanding. It was about being posed lots of stupid
homework involving these things. Most (all?) of theoretical CS was MUCH
easier than what I had to do for maths.
> function, in turn, is a fundamental concept that you can't weasel
> around: it is the essence most existing programming language
> implementations. If you study type systems, you have to understand
> things like strong normalization, system F, etc. One important
> property that a type system either possesses or doesn't is
> decidability. And that's directly related to computability.
>
> If you really think that studying (in)computability was a waste of
> time, your entire CS education has been a waste of time.
Maybe. The part involving the university definitely, but I already knew
that after spending two ws there. The only reason I studied all this
time is to get a diploma, a piece of paper that will magically allow me
to earn several times of what a student's programming job pays (for the
same work). ;)
--
A government which robs Peter to pay Paul can always
depend on the support of Paul.
George Bernard Shaw
| |
| Joachim Durchholz 2005-10-14, 7:00 pm |
| Marcin 'Qrczak' Kowalczyk schrieb:
> Matthias Kretschmer <mccratch@gmx.net> writes:
>
>
>
> Not quite.
> http://lambda-the-ultimate.org/node/view/203
> http://lambda-the-ultimate.org/node/view/1038
The paper quoted there is simply faulty.
It assumes that you cannot build a Turing Machine that computes outputs
that depend on input which in turn depends on previous output.
But a TM can do what a computer program can:
1) If the cardinality of all potential input signals is finite, it can
return a list of things to do for each case.
2) If the cardinality is countably infinite, the TM can compute another
TM that will accept the next input. (Some kind of "telescoping"
operation, I'd say - and I suspect that's how IO in purely functional
languages works, too.)
3) Uncountably infinite input cannot be handled by neither TMs nor
computer programs (all are limited to strings over finite alphabets,
which makes the inputs countable), so this case doesn't
I think that makes interactive TMs exactly equivalent to standard TMs.
Or, rather, equivalent in those respects that matter: termination,
decidability, etc.
(I'd have to provide a proof if this where a reviewed periodical. I'll
leave that to readers *gg*)
Regards,
Jo
| |
| Joachim Durchholz 2005-10-14, 7:00 pm |
| Gary Baumgartner schrieb:
> In article <dio2nq$uks$1@online.de>,
> Joachim Durchholz <jo@durchholz.org> wrote:
> [...]
>
>
> Would you claim this about functions, datatypes or classes?
> What's so different about (my-function a ...) versus (my-macro a ...)?
> Don't you just see "my-function" or "my-macro" and look up its documentation?
Because macros can do things that functions can't.
In (say) Pascal, when I look at a function declaration and see
function foo (baz: integer): integer
I know that it won't modify baz. That may already be all that I need to
know about foo.
For macros, I need to inspect the full macro body to find out whether
it's adding a "var" to that parameter name. I.e. I have to read the full
sources, or believe in what the docs tell me (and the docs are almost
always incomplete, to believing them usually isn't good workmanship).
IOW it comes down to the guarantees that the language gives me. If the
macro language cannot weaken the guarantees that the base language gives
me, then OK. If it can, it's dangerous - or, put more neutrally, the
safeness of a language for use is the lower of the safeness of the macro
language and that of the base language. (A non-existent macro language
has infinite safety - you can't do anything dangerous with it *ggg*)
Regards,
Jo
| |
| Gary Baumgartner 2005-10-14, 7:00 pm |
| In article <dion3l$tnu$1@online.de>,
Joachim Durchholz <jo@durchholz.org> wrote:
>Gary Baumgartner schrieb:
>
>Because macros can do things that functions can't.
>
>In (say) Pascal, when I look at a function declaration and see
>
> function foo (baz: integer): integer
>
>I know that it won't modify baz. That may already be all that I need to
>know about foo.
But in almost all cases that's not all you need to know. Otherwise, you
could just not call foo.
>For macros, I need to inspect the full macro body to find out whether
>it's adding a "var" to that parameter name. I.e. I have to read the full
>sources, or believe in what the docs tell me (and the docs are almost
>always incomplete, to believing them usually isn't good workmanship).
For functions ... I have to read the full sources, or believe what the
docs tell me about what will be returned, side-effects, etc.
>IOW it comes down to the guarantees that the language gives me. If the
>macro language cannot weaken the guarantees that the base language gives
>me, then OK. If it can, it's dangerous - or, put more neutrally, the
>safeness of a language for use is the lower of the safeness of the macro
>language and that of the base language.
I can essentially agree with your neutral version, and the flip side is
that expressivity is the upper of the macro and base language. You are
comfortable with a certain degree of safety (functions without call
by reference) and expressiveness, but not less safety than that with more
expressiveness (functions with call by reference, macros, etc).
Since it's a matter of degree, I think it needs more justification to say
the a certain balance (except near the endpoints) is the right one.
By the way, macros can improve safety by removing more repetition.
For example, I teach a course whose slides contain the following Java code:
public static Node delete(Node front, Object o) {
Node previous = null;
Node current = front;
while (current != null && !current.value.equals(o)) {
previous = current;
current = current.link;
}
if (current != null) {
if (current == front) {
front = current.link;
} else {
previous.link = current.link;
}
}
return front;
}
This is a case of a common pattern that Zahn and Knuth noted over 30 years ago:
while (!a && !b) {
...
}
if (a) {
post-a
} else {
post-b
}
Notice however that the original code tests !a to select post-b, presumably
for efficiency.
Wouldn't it be nice to be able to:
specify a and b once, avoiding copying mistakes
not have to negate and reason about negation, avoiding more mistakes
say "until", just like we can in English, and have the post-condition
not have to read "a" twice, not have the computer execute it twice
Scheme doesn't have until built in, but I can define it:
;; Until loop
;
; (until condition body ...)
;
; Like a while loop, except ends when condition is *true*
;
; If the condition is a disjunction
;
; (or sub-condition
; sub-condition
; ...)
;
; it may be written in the following form to allow post-processing
; based on the (first) sub-condition causing termination:
;
; (one-of (sub-condition [optional post-processing])
; (sub-condition [optional post-processing])
; ...)
;
(define-syntax until
(syntax-rules (one-of)
((_ (one-of clauses ...) do0! ...)
(letrec ((loop (lambda () (cond clauses ... (#t do0! ... (loop))))))
(loop)))
((_ condition do0! ...) (until (one-of (condition)) do0! ...))))
To compare with the Java delete, I'll first:
(define value car)
(define link cdr)
(define set-link! set-cdr!)
(define == eq?)
Now:
(define (delete front o)
(let ((previous null)
(current front))
(until (one-of ((null? current))
((equal? (value current) o)
(if (== current front)
(set! front (link current))
(set-link! previous (link current)))))
(set! previous current)
(set! current (link current))))
front)
I could go further and define macros to capture the common forms:
(set! v (op v a ...)) ; update a variable based on its current value
(if c (op1 a ...) (op2 a ...) b ...) ; select operation to apply to a value
both of which appear in the above code.
>[...]
Gary Baumgartner
| |
|
|
| David Hopwood 2005-10-14, 7:00 pm |
| Joachim Durchholz wrote:
> Marcin 'Qrczak' Kowalczyk schrieb:
>
> The paper quoted there is simply faulty.
>
> It assumes that you cannot build a Turing Machine that computes outputs
> that depend on input which in turn depends on previous output.
>
> But a TM can do what a computer program can:
>
> 1) If the cardinality of all potential input signals is finite, it can
> return a list of things to do for each case.
This cardinality is not finite in most interactive models, and cannot be
made finite without introducing severe restrictions.
> 2) If the cardinality is countably infinite, the TM can compute another
> TM that will accept the next input. (Some kind of "telescoping"
> operation, I'd say - and I suspect that's how IO in purely functional
> languages works, too.)
You've just described a Sequential Interaction Machine, which is not itself
a TM; it is constructed from a TM. Also, a SIM is deterministic, while most
interactive models are not.
< | | |