|
|
Mon Dec 28 13:22:06 EST 2009
The Computer Merit Badge: how I'd complete the requirements NOW;
Part 4
--
This is the fourth installment in an attempt to cover some of the
requirements of the Boy Scout's Computer Merit Badge, which I
feel are the most important. The first requirement was covered in
the first three postings. This post will be the first one to
start to cover the second requirement, which is:
2. Do the following:
a. Tell what a program is and how it is developed.
b. Give three examples of programming languages and what types
of programming they are used for.
c. Describe a source program and an object program.
What is a program?
As was discussed in the previous postings, a digital computer is
a Turing Machine (usually built using a von Neumann architecture)
that has the ability to mimic any valid Turing Machine. In other-
words, it is a Universal Turing Machine (UTM) - well, Universal
Linearly Bounded Automata, given the non-infinite amount of memo-
ry. And how does one make use of a UTM? They must provide for it,
a description of the machine they wish for this UTM to mimic. In
general terms, a "program" is the description of the "machine"
one wishes to make the UTM mimic. So, when one writes a computer
program, they are describing a special purpose "machine" that
they wish the general purpose machine to emulate. This does not
mean that one must literally describe the "machine", but any pro-
gram can be modelled abstractly as such a machine. Through writ-
ing a program, one describes this machine implicitly.
The machine that one may describe in the program can be ridcu-
lously simple (i.e., it actually does nothing) or it can be as
computationally powerful as another UTM. In otherwords, one can
write a program that tells the digital computer how to pretent to
be another UTM. And there are many programs that do this - both
using the theoretical model of an actual Universal Turing Machine
(i.e., with input tapes, read heads, etc), as an emulator of ac-
tual digital electronic hardware (e.g., VirtualBox, Bochs, etc),
and anything in between.
Why go through the pains of describing what a program is in terms
of the abstract models of computation that have been discussed
before? Because in these terms, the definition of a program is
simple. A program is a description (either implicit or explicit)
of the kind of machine you want your digital computer to emulate.
This is only the beginning of the answer to question of what a
program.
The next question should be, how does one describe for a UTM
(i.e., your digital computer) what kind of machine it should emu-
late? The answer, in most common terms, is to write the descrip-
tion using a programming language. So, a programming language is
a way of describing for a digital computer, what machine it
should emulate. The machine, as noted above, can be described ei-
ther implicitly or explicitly. Implicit descriptions of this ma-
chine are done through traditional programming languages. It is
possible to explicitly describe a Turing Machine. An example of
such a description, complete with a Turing Machine simulator im-
plemented in JavaScript can be seen at:
Turing Machine Simulator (secchat.de)
From this point forward, any mention of a program will refer to
the implicit description done with an traditional programming
programming language. Creating literal and explicit machine de-
scriptions and running a simulator can be fun (and prof-
itable...jk;), but it's not a practical way to write a program.
I am also not going into the interesting and storied history of
programming languages, but Wikipedia has a plethera of informa-
tion about it. Programming language research is to this day a
very active area of research, and there are today a tremendous
number of programming languages and programming paradigms (i.e.,
models of thought). Here's a link to get one started:
Information about Programming Languages, LSU@ACM (acm.lsu.edu)
I also make my Firefox bookmarks publicly available. They contain
all sorts of links, mostly divided up by language:
My Programming Language Bookmarks
So, if one wishes to describe to a computer what it should do,
they should write a program. The program can be written in many
different ways, but the easiest way is to use a programming lan-
guage. As mentioned above, the number and types of programming
languages are many. So, for now, this will not be discussed. A
fairly comprehensive discussion about programming languages will
follow soon. The most important thing now is to know that pro-
grams tell computers what do and that these programs are written
using programming languages.
How are progams developed?
The short answer is, using the following "development cycle":
1. write program using a (pure) text editor (vi,gvim,emacs,ned-
it,ultraedit,notepad,etc)
2. for compiled** languages (e.g., C, Java, etc), compile it
without warnings or errors (i.e., compile time errors)
3. execute the program to make sure it does what it is supposed
to (i.e., that it is "correct")
** Note - scripting lanaguages such as Perl or Python do not re-
quire a "compilation" step; more about programming and the devel-
opment process will be discussed in detail in later posts.
Now, he real answer is long and twisted; this is not a good ques-
tion and could apply to many aspects of program development. De-
veloping (or "writing") programs is so wrought with peril, that
many consider it to be a "art". There are countless attempts to
turn this "art" into an "engineering' discipline (ala Software
Engineering). But, at the end of the day, the act of programming
is a creative process. The programmer is first an artist, and
second an engineer. The programming language and computer plat-
form that one chooses for development is analagous to a painter
choosing his canvas, paints, and brushes.
The simple fact is that very few programmers know exactly how
their program will look, function, and be implemented ahead of
time. The development process is therefore something that is
learned over time. Each programmer does things a little differ-
ently; and this fact should be embraced and cause both excitement
and reassurance that if you enjoy programming, it is very much a
personal process of learning and creating. Lessons will be
learned, techniques will be mastered, but ultimately each pro-
grammer will do things a little differently - and for vastly dif-
ferent reasons. This applies to the language they prefer, the
paradigm in which they think more clearly (e.g., imperitive,
functional, object oriented, etc).
A Final Note - Programs vs. Algorithms
Often, people will interchange the terms "program" and "algo-
rithm". This is unfortunate, so I will attempt to describe the
difference. An algorithm is a set of steps for accomplishing a
certain objective. A program can implement a single algorithm. A
program can also contain many different algorithm implementa-
tions, which are meant to provide various program features. I
will talk about algorithms in future posts, but for now I'll
leave you with the following.
An algorithm is meant to determine a certain thing. For example,
there are many algorithms (some not so efficient) for finding the
shortest paths between two cities on a map given many possible
paths (e.g., Dijkstra's Algorithm). An algorithm also exists out-
side the realm of an implementation. It's the list of steps to
follow, and may be described either formally (in mathematical
terms or psuedocode) or informally (say, in plain English).
Programs are fully featured tools that may use the implementation
of many different algorithms (using a programming language) to
provide various features - for example, Microsoft Word. In the
case when a program executes one and only one algorithm, the dif-
ference between the program and the algorithm is that the program
*implements* the algorithm. Without the program implementation,
the algorithm still exists. However, without the implementation,
the program can't exist. Confused? :)
The following links go to Wikipedia's pages for more detailed
definitions of algorithms and programs, respectively:
Algorithms (wikipedia.com)
Computer Program (wikipedia.com)
Summary
To conclude this post, the most important point is that a program
is a set of instructions for the computer to follow. More impor-
tantly, these sets of instructions are not meant simply for the
computer to follow. They are meant to be a description of a com-
putational machine that the programmer wishes for the digital
computer to emulate. Recall the focus on Universal Turing Ma-
chines - machines that are able to emulate any other valid type
of machine, including other UTMs! A programming language is what
the programmer uses to describe the machine to be emulated or
mimicked, by the UTM. The practice of "writing" or developing a
program includes with it a tremendous amount of approaches, meth-
ods, and opinions. There are as many programming languages as
there are programmers willing to create another way to describe
their machines, following their own preferences. Programming is
therefore a very creative and person endeavor. One who sticks
with programming will soon develop a preferenced for the differ-
ent tools and approaches they come to discover. Chosing such
things as architecture, platform, and languages to use is similar
to the process an artists goes through when arriving to his pref-
erences of his canvas, paint, and paint brushes.
In the following postings, I will use the remaining two require-
ments to discuss in more detail: programming languages and what
it means to "compile" a program into something that the computer
can "execute".
Cheers,
--
Powered by vee
Copyright © 2006-2010
|
|