Assignment 1
Chapter 1, 2, & 3 Problem Sets










Prepared for

Dr. Frank J. Mitropoulos, Ph.D.

Faculty in Masters Program

Nova Southeastern University











Prepared by

Derek J. Sedlack

Graduate Student, Nova Southeastern University

School of Computer and Information Sciences









June 27, 2003



Chapter 1

1, 4, 8, 10............................................................................... 1


Chapter 2

5, 7, 8, 9, 13, 15, 18............................................................... 3


Chapter 3

3, 7, 8, 10............................................................................... 5


Chapter 1


1. Do you believe our thinking capabilities are influenced by our languages? (support your opinion)


Thinking capabilities are clearly influenced, or even shaped by our ability to understand language. Sebesta (2002, p 2) states that people’s ability to think abstractly and gasp complex thought is directly proportional to their ability to grasp a natural language. This is supported by Fearnley-Sander’s (2002) idea that the development of language supports abstract thought; just as many believe complex language expands a mind to allow advanced reasoning. A survey of trainable animals might also support the theory of advanced capacity through language. Some snakes and fish travel through enigmatic mazes just to breed even though their language capacity is negligible, but dogs and porpoises have saved people from almost certain death, perhaps because they understand the abstract value of a life due to their enhanced ability to communicate. LaFleur (n.d.) notes that a study of students with two or more years of Latin, as a second language, showed a typical increase in scores, 140-160 points/1600. This also supports Sebesta’s (2002, p 3) notion that programmers with formal training, better thinking capabilities, are more likely to recreate a complex feature from one language in a second language that did not inherently support that feature.

4. What arguments can you make against the idea of a simple language for all programming domains?


There are a number of programming domains that have radically different requirements, such as scientific and business, that dismiss any notion of a simple language for all programming domains as well as the different language evaluation criteria. While there may be large areas of similarities between business and scientific domains, the discrepancies would make it nearly impossible to support a simple language that could encompass both even without considering other diverse domains. Efficiency, according to Sebesta (2002, p 5-6), is a primary concern for the scientific community, but business applications are characterized by facilities for creating elaborate reports, and the artificial intelligence domain requires more flexibility than other programming domains.

8. Some languages, notably C and Java, distinguish between uppercase and lowercase in identifiers. What are the pros and cons of this design decision?




Looking at distinct names within a variable can greatly improve the readability of code. For example: aReallyLongVariableName is much easier to read than AREALLYLONGVARIABLENAME.

Maintenance is substantially cheaper as pursuing programmers can better understand the intention of the original code design.

Differentiation between static and dynamic variable names.


Inconsistencies can arise from differences in case with the same variable (i.e. typos).

List of long variables can get quite extensive.

Inconsistencies in style can cause problems.

10. What are the arguments for writing efficient programs even through hardware is relatively inexpensive.


            While Moore’s law may still be somewhat acceptable, the loosening constraints on programming shouldn’t be. Many of the new object oriented languages, Visual Basic and Visual C++, have methods of automatically allocated or freeing memory, but this also increases system overhead. Many programmers don’t have to know what size a byte is, a double word, or how large their array could possibly get and that causes many programs to be bloated and inefficient. Efficiency doesn’t just mean saving disk space, or making things faster, it also relates to maintenance and reliability. Current programs that are written poorly because of cheap hardware are just as bad as poorly written programs of the past, they waste resources in both time and space, especially during a time when IT departments are trying to make more with less as reported in this CNN article, Inefficient programs cause page faults, memory errors, and leaks that can cause system-wide crashes. Just because the system may have more memory and speed doesn’t make it impervious to bad programming.


Chapter 2


5. Which of the three original goals of the ALGOL design committee, in your opinion, was most difficult to achieve at that time?

I agree with the text that something entirely new to the computing business would be the most difficult to achieve (Sebesta, 2002. p 56). The first requirement, “as close as possible to standard mathematical notation, and …should be readable with little further explanation” appear to be the direction programming languages were heading, especially with scientists and mathematicians leading the way and scientific programming was a primary focus of computing. Without implementing the last requirement, “…the new language must be mechanically translatable into machine language,” it would be impossible for the system IO to determine what instructions were being requested since computers can’t guess in that capacity. Developing a language that mimicked pseudocode or symbolic description for the purpose of publication was definitely be the most difficult challenge of the three at that time.

7. LISP began as a pure functional language but gradually acquired more and more imperative features. Why?

John McCarthy’s original interest in developing LISP was to meet the demand for artificial intelligence as a functional programming language, but there soon emerged different dialects, cleaners, more modern, and more imperative, that began to deviate from the functional form into Scheme. COMMON LISP combined the different forms into a single form that was more imperative, including assignment and iteration.

8. Describe in detail the three most important reasons, in your opinion, why ALGOL 60 did not become a very widely used language.

Excessive flexibility hurt ALGOL60 since languages that are difficult to learn were not as well received as languages with a more rigid structure. Allowing a large number of possibilities also introduces an element of inefficiency since the methods to complete a task would differ between programmers. Second, Sebesta (2002, p. 60) notes that its association with BNF alienated the language as strange and complicated. If programmers are not excited about using a language, they will always find a different one. The third and perhaps the most important reason that ALGOL60 was not very widely used was because of a lack of support from IBM, who was at the time the preeminent company for using computer languages. Without some help from a large corporation, ALGOL60 did not have much of a chance, much like COBOL without the DoD.

9. Why, in your opinion, did COBOL allow long identifiers when FORTRAN and ALGOL did not?

COBOL required that managers without a background in programming should be able to read programs and English should be used as much as possible. This caused identifiers to be longer, making the language more English-like. Sebesta (2002, p. 57) states that “[ALGOL] identifiers were allowed to have any length, as opposed to FORTRAN’s restriction to six or fewer….” FORTRAN was also a much older language that was built during a time of very little memory and a focus on syntax “as close as possible to standard mathematical notation” leaving little room for long identifiers.


13. Describe, in your own words, the concept of orthogonality in programming language design.

It appears that orthogonality means the simplicity of programming constructs, or a minimal number of control and data structures in a language. Each additional construct increases the complexity, removing orthogonality.


15. What are the arguments both for and against the idea of a typeless language?

Arguments for are obvious flexibility and ease of use. Without having to define a data type the programmer is free to develop code that is generated quickly and without much thought. Learning the language is much simpler because one doesn’t have to determine size or how the compiler will interpret the type later on, only what information must be included.

Arguments against include data insecurity, such as the assignment of a character type ‘A’ that could in fact be “defined” as a HEX value by the programmer. The compiler would also have trouble interpreting floating point values compared to integers. The resulting arithmetic would also cause serious problems; like adding 5 + “happy” and how they are interpreted different than perhaps the programmer intended.


18. Do you think language design by committee is a good idea? (Support your opinion)

Language design by committee definitely has its advantages, with varying points of view from different domains, different programming backgrounds, and even different language backgrounds all contributing for the better of the language like ALGOL 58. Knowledge of Plankalkul enhanced ALGOL 58 because members from Europe were familiar with the language. Improvements like variable length identifiers and array dimensions were improved upon previous languages. Even though many arguments and conflicts arise, like whether to use a comma (European) or a period (American) for a decimal point took place, it is beneficial to have options. I think history would show that the best use of committees would be after a language has been invented and accepted. At this point a better evaluation is possible and committee members would be better conditioned to make improvements than initial discoveries.

Chapter 3


3. Using the grammar in Example 3.2, show a parse tree and a leftmost derivation for each of the following statements:






a.              A = A + (B + (C * A))       

< assign >    = > <id> = <expr>

          = > A = <expr>

              = > A = <id> + <expr>

          = > A = A + <expr>

              = > A = A + ( <expr> )

          = > A = A + ( <id> + <expr> )

              = > A = A + ( B + <expr> )

              = > A = A + ( B + ( <expr> ) )

              = > A = A + ( B + ( <id> * <expr> ) )

              = > A = A + ( B + ( C * <expr> ) )

              = > A = A + ( B + ( C * <id> ) )

              = > A = A + ( B + ( C * A ) )







b.              B = C * (A * C + B)

< assign >    = > <id> = <expr>

          = > B = <expr>

              = > B = <id> + <expr>

          = > B = C + <expr>

              = > B = C + ( <expr> )

          = > B = C + ( <id> + <expr> )

              = > B = C + ( A * <expr> )

              = > B = C + ( A * <id> + <expr> )

              = > B = C + ( A * C + <expr> )

              = > B = C + ( A * C + <id> )

              = > B = C + ( A * C + B )










c.              A = A * (B + (C))

< assign >    = > <id> = <expr>

          = > A = <expr>

              = > A = <id> + <expr>

          = > A = A * <expr>

              = > A = A * (<expr> )

          = > A = A * ( <id> + <expr> )

              = > A = A * ( B + <expr> )

              = > A = A * ( B + ( <expr> ) )

              = > A = A * ( B + ( <id> ) )

              = > A = A * ( B + ( C ) )



7. Describe, in English, the language defined by the following grammar:

<S> -> <A> <B> <C>

<A> -> a <A> | a

<B> -> b <B> | b

<C> -> c <C> | c


The LHS non-terminal S is defined as non-terminal A and non-terminal B and non-terminal C, where non-terminal A can be one or more a’s or one a, where non-terminal B can be one or more b’s or one b, and where non-terminal C can be one or more c’s or one c.

8. Consider the following grammar:

<S> -> <A> a <B> b

<A> -> <A> b | b

<B> -> a <B> | a

Which of the following sentences are in the language generated by this grammar: a. baab, b. bbbab, c. bbaaaa, d. bbaab.


The LHS non-terminal S is defined as non-terminal A, terminal a, non-terminal B and terminal b, where non-terminal A can be zero or more b’s or one b, and where non-terminal B can be one or more a’s or one a;

Resulting in one or more b’s or one b, one a, one or more a’s or one a, and one b.

Answers a (baab) and d (bbaab) adhere to this production.


10. Write a grammar for the language consisting of strings that have n copies of the letter a followed by the same number of copies of the letter b, where n > 0. For example, the strings sb, aaaabbbb, and aaaaaabbbbbb are in the language but a, abb, ba, and aaabb are not.


<S> -> <A>

<A> -> a <A> b <B>




Example 3.2                 A = B * ( A + C )


< assign >         = > <id> = <expr>

                        = > A = <expr>

                        = > A = <id> * <expr>

                        = > A = B * <expr>

                        = > A = B * ( <expr> )

                        = > A = B * ( <id> + <expr> )

                        = > A = B * ( A + <expr> )

                        = > A = B * ( A + <id> )

                        = > A = B * ( A + C )



Sebesta, R. (2002). Concepts of programming languages. Boston, Ma. Pearson Education, Inc. 5th Edition.


Fearnley-Sander, D. (2002). Review of The Symbolic Species: The Co-evolution of Language and the Brain by Terrence W. Deacon. Human Nature Review. 2: 84-87.


LaFleur, R. A. (n.d.) The Practical Benefits of Studying Latin. NCLG: Why Study Latin? Retrieved on June 27, 2003 from the World Wide Web: