CS441 - Group Project #5
Comparison of
Functional Languages to
- Simple, Procedural Languages
- Logic-based Languages
Marcus Garrett
Jeff Heckathorn
Tom Heffron
Sedric Hibler
Ali Wajid
Due Date:
December 9, 2002
History
Comparison
Marcus Garrett
versus
Simple, Procedural
Functional
programming language came from the need for a language which could
handle artificial intelligence. John McCarthy first developed the
first functional language LISP in the late 1950s at the
Massachusetts Institute of Technology. LISP programming systems
are interpreters. The Lisp language is rooted on the
representational power of "S-expressions" and use of functional
composition and recursion. LISP is a weakly-typed language which
is ideal for on-the-fly code generation and interpreting. Its
extreme flexibility, power, and its ability to treat code as data,
made it the ideal of Artificial Intelligence research during 1970s
and 1980s. Dozens of LISP implementations have been built over the
years, many of them were inspired by MacLISP. Eventually the
designers of the descendants of MacLISP convened and developed a
standard for LISP systems called Common LISP.
Simple, procedural languages were created for people who didn’t
have a background in Computer Science but needed a way to program
and work on computers. Simple, procedural languages were easy to
learn and program. With this simplicity came their shortcomings.
Simple, procedural languages do not provide methods to handle
complexity. They were created and designed to be short programs
that could run on the less powerful computers of the time. Simple,
procedural languages were created to act as a stepping stone for
novice programmers. Later, with knowledge of simple, procedural
languages, programmers could progress to more complex and powerful
languages. Many people who began programming in simple, procedural
languages found that as they did progress to more complex
languages, the fundamentals of programming were inadequate. This
served as a major blemish for programming with simple, procedural
languages.
These two language types differ on their necessity of their
application area. Where Simple, procedural languages is a weak
language and unable to handle complexity, Functional languages are
extremely powerful and are used to handle very complex application
areas. Simple procedural languages use procedures to manipulate
data and data structures. The main criticism of procedural
languages is that they make it hard to re-use code for similar but
not identical purposes. While Functional languages were developed
for the scientific and mathematical community, Simple, procedural
languages were developed for the novice programmer with little
computer science education.
versus
Logic-based
Logic programming is an approach to Computer Science in which the
first order predicate logic is used as a high level programming
language. The history of logic programming started with symbolic
logic, and then First Order Predicate Logic emerged from symbolic
logic to form the base for Logic Programming. Prolog is the most
viable and widely used Logic Language. Prolog (PROgramming LOGic)
was designed within the realm of Artificial Intelligence (AI). It
originally became popular with AI researchers, who are more
interested about "what" and "how" intelligent behavior is
achieved. The philosophy behind it deals with the logical and
declarative aspects. Prolog represents a fundamentally new
approach to computing and became a serious competitor to LISP.
Both languages are similar in the fact that they were created to
apply to artificial intelligence. They both currently compete
against each other in the realm of artificial intelligence.
Functional programming languages are based on the lambda-calculus
where as Logic programming is based in first order predicate
logic. Alonzo Church and Stephen Kleene created lambda-calculus
out of an attempt in the early 1930s to formalize the notion of
computability. It is a formalization of the notion of functions as
rules. As with mathematical expressions, it is characterized by
the principle that the value of an expression depends only on the
values of its subexpressions. It is a simple language with few
constructs and simple semantics but is sufficiently powerful to
express all computable functions.
Overview Comparison
Marcus Garrett
versus Simple, Procedural
In the narrow sense, functional
languages are ones that operate by use of higher-order functions,
building operators that manipulate functions directly without ever
appearing to manipulate data. A functional language is a language
that supports and encourages programming in a functional sense.
Functional languages filled the need for use of algebraic
expressions through the use of programming languages for
artificial intelligence programming. The expressions in these
languages are formed by using functions to combine basic values.
The functional programming language style describes inputs and
outputs rather than the detail of algorithms. This feature is
great value when trying to run programs using parallel computing
architectures. Although functional languages originated to fill
need for an artificial intelligence programming, functional
languages have been introduced into other areas of application and
are now thought of as a general purpose programming language. The
power of the functional languages makes them ideal for writing
editing commands.
Simple, procedural languages were used to create simple programs.
As the programs got more complex it got harder to program with
these languages. Simple, procedural languages were the first
languages to be programmed at terminal displays, and not by punch
cards. Early in their inception, operating systems had simple,
procedural languages as its base code (BASIC was used for a lot of
O/S code in the 70’s). Simple, procedural languages were also used
on the first smaller computers its code structures were small in
nature. As computers got more powerful, programs that were written
got more complex. Logic applies to all areas of artificial
intelligence and computer science. Logic programming is
fundamental to these areas. Among AI applications that use logic
programming, natural language processing, knowledge
representation, non-monotonic reasoning, databases, implementations
and architectures, and constraint logic programming. Logic
programming has also proven its merits in a variety of application
areas including diagnostic expert systems and agent-based control
systems.
Simple, procedural references (for Sections
1 and 2):
1)
http://home.cfl.rr.com/eaa/Languages.htm
2)
http://www.daimi.aau.dk/~eernst/gbeta/tut15.html
versus Logic-based
In Logic Programming, programs are
theories and computation is deduction from the theory. The goals
of programming in Logic are first obtaining a problem description.
Next you define the intended model of interpretation (domains,
symbols etc). Then you devise a suitable theory (the logic
component) suitably restricted so as to have an efficient proof
procedure. Thereafter describe the control component of the
program. Lastly, you use declarative debugging to isolate errors
in definitions. Logic languages were designed to be able to handle
complex functions, but where not limited to only mathematical
expressions. Prolog is the highest level logic-based language
widely used today. It is taught with an emphasis on thinking of
the logical relations between objects or entities relevant to a
given problem, rather than on procedural steps necessary to solve
it. The system in which it is programmed decides the way to solve
the problem, including the sequences of instructions that the
computer must go through to solve it. It is easier to say what we
want done and leave it to the computer to do it for us. Prolog
serves as an ideal prototyping language. It solves problems by
searching a knowledge base (or more correctly a database) which
would be greatly improved if several processors are made to search
different parts of the database.
Functional languages and Logic languages have also been developed
for scientific computing applications. The main reason to use
functional languages for this class of application is the very
straightforward parallelization of functional programs, which
outweighs the loss of efficiency that a functional program often
experiences from their more costly evaluation mechanisms and
memory requirements. Logic programming is one of the principal
paradigms for declarative reasoning. This separates the
specification of what has to be solved from the control
information that aids the search for a solution. Thus a logic
program can be read as a set of logical formulas which can also be
executed as a computer program. Prolog is the main one of many
programming languages based on this formalism.
Logic-based references (for Sections 1
and 2):
1)
http://www.cs.northwestern.edu/academics/courses/c25/readings/lisp-history.html
2)
http://www8.informatik.uni-erlangen.de/html/lisp-enter.html
3)
http://www.elwoodcorp.com/alu/table/history.htm
4)
http://cs.wwc.edu/~aabyan/221_2/PLBOOK/
5)
http://home.cfl.rr.com/eaa/Languages.htm
6)
http://www.daimi.aau.dk/~eernst/gbeta/tut15.html
Handling of
Data Objects
Sedric
Hibler
versus Simple, Procedural
Simple, procedural and functional
languages have many similar simple data types to go along with
their similar handling of data objects. These generally include
integers, strings, Booleans, reals, characters, records, and some
variations on these data type objects. Arrays can be created from
these types in both languages. Simple procedural languages also
support pointers, which functional languages don’t.
The simple procedural language class requires statically typed
data, which means that they must remain the same type that they
are declared when the program is executed. This is in contrast to
functional languages, which are type-less. Pascal supports variant
records, in which this is the only time that the type is not
checked in simple procedural languages. Both languages also allow
values to be changed during the execution of the program. They
both use static variable allocation.
versus Logic-based
Functional based languages generally
use the following data types with their data objects: integer,
real, characters, strings, doubles, and Boolean. From these types,
arrays, user-defined types, records, sets, and hash tables can be
used as well. Multi dimensional arrays, variant records and read
tables are also visible on some functional languages.
Functional languages are type-less (in general) and the value of
an object is determined during the execution of the program. Lists
are the primary structure of functional languages.
In comparison, logic based languages tend to support integers,
real numbers, strings, pointers, records and some user defined
types. Logic-based languages also allow dynamic binding (where
data definitions can be changed during program execution), with
the exception of the constants in Prolog. Logic languages can
create dynamic structures. In the logic-based programming family,
we have found that they have strong type checking at run time
(unlike the Functional Languages), yet they are better compared to
those of non-typed languages. In Eqlog, a logic-based language,
subtypes are allowed. This language is based on order-sorted
algebra, which allows multiple data representations and automatic
coercions between them. Prolog is the most popular of logic-based
languages. 'Terms' are used to represent Prolog's data objects,
which are comprised of constants, variables, and other complex
terms.
References:
1)
http://134.193.15.25/vu/course/cs441/Lessons.shtml
2)
http://t.students.umkc.edu/tehqnf/CS441/cs441proj1.htm
3)
http://t.students.umkc.edu/tehqnf/CS441/cs441proj2.htm
4)
http://t.students.umkc.edu/tehqnf/CS441/cs441proj3.htm
5) Sebesta, Robert. Concepts of Programming Languages, Sixth
Edition. Reading, Massachusetts: Addison-Wesley, 2001.
Handling of
Sequence Control
Jeff Heckathorn
versus
Simple, Procedural
In general the
simple, procedural programming languages execute from the first
line of program code sequentially to the last. The simple,
procedural languages - as example FORTRAN and BASIC - both make
provisions for the sequence of code execution to be altered to
facilitate programming requirements that need to be fulfilled by
loops and the GOTO branching statement. They both also support
functions - or subroutines that allow the program to return to the
point that called it. The Simple Procedural language group also
supports if-then-else statements for branching and logical flow of
control. They also have looping statements for repetition.
The functional programming languages have their sequence control
designed around mathematical functions. These functions use
recursion and conditional expressions for control of flow. The
example languages of Scheme, and LISP have two basic sequence
control elements. One element controls two-way branching that
includes If or For selections. The second is a multiple selector
COND function allowing for multiple path function. The Functional
language semantics are different enough from the Simple Procedural
to make direct comparison difficult.
versus
Logic-based
The logic-based
programming languages such as Prolog and Mercury have their
program execution based on first order predicate calculus. Prolog,
as an example of the logic-based programming style, uses predicate
statements and most sequence control is done with recursive
predicate statements. The functional based programming languages
share much of the same sequence control semantics with the
logic-based languages. Both use recursion for iterative control.
Though the example languages of prolog and mercury do not have a
multi path conditional such as in LISP.
References:
1)
http://t.students.umkc.edu/tehqnf/CS441/cs441proj1.htm
2)
http://m.students.umkc.edu/mkb5e9/CS441/project1.htm
3)
http://y.students.umkc.edu/yl7e4/cs441/SIMULA.doc
4)
http://k.students.umkc.edu/kmtvd3/CS441/CS441_PROJECT1.doc
5)
Luger, George. “Artificial Intelligence Structures and Strategies
for Complex Problem Solving” 4th edition 2002.
Handling of
Subprograms & Storage Management
Ali Wajid
versus
Simple. Procedural
Simple
procedural languages and functional languages both allow users to
use subprograms to avoid writing the same code again and again.
Simple procedural languages appear to have built-in functions that
programmer can make use of when writing programs - they have to
include the library in which those built-in functions are defined
and then the functions already defined in the library can be
easily use. Functional languages have primitive functions and
functional forms defined for programmers. Functional languages,
such as Scheme and LISP, allow complex functions to be constructed
by using set of these primitive functions and functional forms.
To create subprograms in Scheme, which is a functional language,
'lambda syntactic form' is used. Subprograms in functional
languages may include other subprograms. Functional programming
languages seem to have very simple and small subprograms.
Subprograms in functional languages are limited in size and scope,
and programmers have to be really careful when implementing these
subprograms. It is up to the programmer to combine these
subprograms efficiently to work together.
Both families seem to
have languages that have different types of subprograms.
Subroutines are subprograms use to return more than one value.
According to our understanding, in addition to functions, simple
procedural languages allow subroutines to be written. Simple
procedural languages do not allow recursion in subprograms. On the
other hand, functional languages seem to have strong support for
recursion because sometimes problems can be solved easily using
recursion than using other method. Subprograms in simple
procedural languages always have a name, but subprograms in
functional languages may or may not have a name. In simple
procedural languages, results
are stored in memory, which is done using variables in the
program. On the other side, functional languages do not use
variables in the program, and that’s why the programmer does not
have to worry about the memory cells on which the program is
executed.
The user is not required to implement any storage management
techniques themselves in simple procedural language family. Simple
procedural language, such as FORTRAN, only support static
allocation of variables. Functional languages, however, give more
freedom to programmers as far as memory management is concerned.
In functional languages, such as scheme, programmers do not have
to explicitly de-allocate objects. Storage management system
automatically takes care of freeing the space once it determines
that the object is no longer being used in the program.
versus
Logic-based
Functional
languages and logic-based languages differ from each other when it
comes to subprograms. In logic-based languages, such as Prolog,
subprograms are used to describe logical relationships between
facts. According to our understanding, functional languages allow
recursion in subprograms. So, subprograms in functional languages
are allowed to call themselves. On the other hand, logic-based
languages have no support for recursion what so ever. So,
subprograms are not allowed to call themselves in logic-based
languages.
Functional languages have two types of variables - namely global
and local. In Prolog, which belongs to logic-based language
family, variables are visible everywhere in the program. It does
not matter where we declare variables in Prolog, all variables
work as global variables. Our understanding is that all variables
can be seen and changed by the code in the main program or by the
subprograms.
In functional languages, such as Scheme, programmers do not have
to explicitly de-allocate objects. Storage management system
automatically takes care of freeing the space once it determines
that the object is no longer being used in the program. Similarly,
logic-based languages also give just as much freedom to
programmers as functional languages as far as memory management is
concerned. Garbage collection is used in both language groups to
handle storage management automatically. Garbage collection gives
programmer more flexibility and decreases the chances of memory
leaks.
References:
1)
http://t.students.umkc.edu/tehqnf/CS441/cs441proj2.htm
2)
http://t.students.umkc.edu/tehqnf/CS441/cs441proj3.htm
3)
http://t.students.umkc.edu/tehqnf/CS441/cs441proj4.htm
4)
http://m.students.umkc.edu/mkb5e9/CS441/project1.htm
5)
http://c.students.umkc.edu/cbdn92/REVISEDproject1.doc
6)
http://k.students.umkc.edu/kmtvd3/CS441/CS441_PROJECT1.doc
Handling of Abstraction and
Encapsulation
Tom Heffron
versus Simple, Procedural
It is rather difficult to compare the
family of simple, procedural languages to any other family of
languages when it comes to abstraction and encapsulation. This is
because simple, procedural languages - as a family – generally do
not include support for compound statements. As the Sebesta text
discusses in Chapter 8, “Compound statements allow a collection of
statements to be abstracted to a single statement.” We could
extend this statement to say that “compound statements are
required for a collection of statements to be abstracted.” Without
these structures, particularly blocks to define different
execution scopes, there can be no hiding of data elements. All
data declarations must be in a single, large scope – and, thus,
seen throughout the program’s execution.
Encapsulation also largely depends on the use of compound
statements. Without code blocks and scope definitions, any
encapsulations would simply be like an automatic ‘cut-and-paste’
by the compiler. Even then, any call to code in the main program
must include a ‘GOTO’ statement in order to return to the calling
program. Also, variable names must be known by both the calling
program and the called code section – essentially, nullifying any
practical use of separate code segments.
By contrast, functional languages
focus more on the functions used to solve a problem. Therefore,
this family concentrates on the abstraction of its procedures.
Since functional languages are designed to mimic mathematical
functions, they are less concerned with the underlying
architecture of the hardware. They do not worry about abstracting
the individual tasks to abstract memory cell and register
movement. Most functional languages give a programmer the ability
to abstract some complex functions by defining a ‘feeder function’
that will redirect the data types passed to the function into
other detailed functions to perform the work.
Encapsulation is a bit of a non-issue in functional programming.
There is a logical organizational break between functions and each
is relatively self-contained. A programmer need only ensure that
any call to an ‘external’ function can be accessed by the program.
versus Logic-based
Encapsulation in the logic-based
family is simply a way to expand its ‘world of knowledge’. This
means that new declarations and statements can be seen by a
calling program in order to solve a new problem. A programmer must
be concerned that any call to ‘external knowledge’ must be
preceded with the name of that module in which it resides – and
the predicates will then have direct access to the data in that
module. Therefore, the programmer must have direct access to the
declarations of that module – and data hiding becomes difficult.
Some logic-based programs were not
designed for large-scale projects and do not include support for
shareable, reusable code. Others, such as Mercury, do implement
reusable code in modules - allowing data declarations and
predicates to either be totally hidden or completely seen by the
calling program.
References:
1)
http://c.students.umkc.edu/cbdn92/REVISEDproject1.doc
2)
http://t.students.umkc.edu/tehqnf/CS441/cs441proj3.htm
3)
http://r.students.umkc.edu/rjjkr7/CS 441/project_1.htm
4)
http://y.students.umkc.edu/yl7e4/cs441/SIMULA.doc
5)
http://k.students.umkc.edu/kmtvd3/CS441/CS441_PROJECT1.doc
6) Louden, Kenneth C. Programming Languages Principles and
Practice. Boston: PWS Publishing Company, 1993.
7) Sebesta,
Robert. Concepts of Programming Languages, Fourth Edition.
Reading, Massachusetts: Addison-Wesley, 1999.