Transcript Levels of Abstraction

Systematic Development of
Programming Languages
cs784(Prasad)
L1Intro
1
Orthogonal Parameters
 Conceptual
view (Model of Computation)
» imperative, functional, relational,...
 Level
of abstraction (Model of Implementation)
» problem domain
» ...
» machine
– Computational Task : I/O relation to be
implemented
cs784(Prasad)
L1Intro
2
1. Customized Digital Computer
Task j
Ij
Oj
Task k
Ik
Ok
Rig different circuit for each task
cs784(Prasad)
L1Intro
3
2. Stored Program Computing
 von
Neumann showed the existence of a
Universal Machine (hardware) that can be
customized using control inputs to carry out
different tasks.
 Software is the encoding of the task to control
this machine.
encoding(Tj)
Ij
cs784(Prasad)
Oj
L1Intro
4
Imperative Languages
 Model
of Computation
» ALU + Memory + Input + Output
(von Neumann architecture)
 Levels
of Abstraction (“Human Interface”)
– Machine Language
» Binary Representation of the task
– Assembly Language
» Symbolic Representation of the task
cs784(Prasad)
L1Intro
5
Assembly Language
ADDI R4,R2,21
ADDI R4
R2
21
10101100100000100000000000010101
 Use
symbols instead of binary digits to
describe fields of instructions.
 Every aspect of machine visible in program:
– One statement per machine instruction.
– Register allocation, call stack, etc. must be
managed explicitly.
 No
structure: everything looks the same.
Pros and Cons of Assembly Language
 Avoids Absolute Addressing
» relocatable, reusable/shareable
 Uses Symbolic
» readable

Names
Low-level programming wastes effort in
coding a solution rather than solving a
problem.
 Difficult
cs784(Prasad)
to build and maintain large programs.
L1Intro
7
High-level Language
 Provides
notation to describe problem
solving strategies rather than organize data
and instructions at machine-level.
 Improves programmer productivity by
supporting features to abstract/reuse
code, and to improve reliability/robustness
of programs.
 Requires a compiler.
cs784(Prasad)
L1Intro
8
Levels of Abstraction
Problem Domain (stacks, tables)
(Class Hierarchies)
Java/C#/Scala/Python/Scheme
C++
Ada
(ADTs)
C
Pascal (arrays)
Assembly Language
Machine (char, int)
cs784(Prasad)
L1Intro
9
Evolution of Programming Languages
• FORTRAN ( FORmula TRANslator)
Goals :
Scientific Computations
Efficiency of execution
Compile-time storage determination
Features : Symbolic Expressions
Subprograms
Absence of Recursion
• COBOL
Goal:
Business Application
Features : Record/Structure; File Handling
cs784(Prasad)
L1Intro
10
Evolution of Programming Languages
• ALGOL - 60 (ALGOrithmic Language)
Goals :
Communicating Algorithms
Features : Block Structure (Top-down design)
Recursion (Problem-solving strategy)
BNF - Specification
• LISP (LISt Processing)
Goals :
Manipulating symbolic information
Features : List Primitives
Interpreters / Environment
cs784(Prasad)
L1Intro
11
Problems
 Not
rugged wrt typographical errors
Do 10 I = 1.20
vs
Do 10 I = 1,20
I5 = I5 + 1
vs
I5 = IK + 1
– Remedy: Declare before use
 Unintended
Coercion
I > J and false
– Remedy: Type checking
cs784(Prasad)
L1Intro
12
Evolution of Programming Languages
• Pascal
Goal : Structured Programming, Type checking,
Compiler writing.
Features :
• Rich set of data types for efficient
algorithm design
• E.g., Records, sets, ...
• Variety of “readable” single-entry
single-exit control structures
• E.g., for-loop, while-loop,...
• Efficient Implementation
• Recursive descent parsing
cs784(Prasad)
L1Intro
13
Programming in the Large
 Programs
no longer monolithic. Developed
by a team of programmers.
 Code sharing and reuse very important.
 Correctness, reliability, and robustness
essential.
– Data Abstraction / Encapsulation / Strong
Typing
» Ada, CLU, Modula etc.
cs784(Prasad)
L1Intro
14
Other Languages
 Functional
» Common LISP, Scheme
» ML, Haskell
 Logic
» Prolog
 Object-oriented
» Smalltalk, SIMULA, Modula-3, Oberon
» C++, Java, C#, Eiffel, Ada-95
 Hybrid
» Python, Ruby, Scala
 Application
cs784(Prasad)
specific languages and tools
L1Intro
15
Scripting vs Systems Programming Languages





Designed for gluing
applications : flexibility
Interpreted
Dynamic typing and
variable creation
Data and code integrated :
meta-programming
supported
Examples: PERL, Tcl,
Python, Ruby, PHP,
Scheme, Visual Basic,
Scala, etc.
cs784(Prasad)
L1Intro





Designed for building
applications : efficiency
Compiled
Static typing and variable
declaration
Data and code separated :
cannot create/run code on
the fly
Examples: PL/1, Ada,
Java, C, C++, C#, Scala,
etc.
16
(cont’d)
Does application implement complex algorithms and data
structures?
 Does application process large data sets (>10,000 items)?
 Are application functions well-defined, fixed?
If yes, consider a system programming language.

Is the main task to connect components, legacy apps?
Does the application manipulate a variety of things?
Does the application have a GUI?
Are the application's functions evolving rapidly?
Must the application be extensible?
Does the application do a lot of string manipulation?
If yes, consider a scripting language.






cs784(Prasad)
L1Intro
17
Jython (for convenient access to Java APIs)
I:\tkprasad\cs784>jython
Jython 2.1 on java1.4.1_02 (JIT: null)
Type "copyright", "credits" or "license" for more information.
>>> import javax.swing as swing
>>> win = swing.JFrame("Welcome to Jython")
>>> win.size = (200, 200)
>>> win.show()
>>> ^Z
cs784(Prasad)
L1Intro
18
Java vs Jython
map = new HashMap();
map.put("one",new Integer(1));
map.put("two",new Integer(2));
map.put("three",new Integer(3));
map =
{"one":1,"two":2,"three":3}
System.out.println(map.get("one"));
print map ["one"]
list = new LinkedList();
list.add(new Integer(1));
list.add(new Integer(2));
list.add(new Integer(3));
cs784(Prasad)
list = [1, 2, 3]
L1Intro
19
(cont’d)
for (Iterator i; i.hasNext();)
{
i.next();
}
for i in list:
(* iterator *)
List newList = ArrayList()
for (Iterator i; i.hasNext();)
{
Object obj = i.next();
newList.add(function(obj))
}
cs784(Prasad)
L1Intro
newList =
[function(i) for i in oldList]
(* list comprehension *)
20
Functional Programming in Jython
apply(lambda x,y : x*y, (10, 20))
# 200
map(lambda x,y: x + y, [[1,2],[“a”]], [[“3”],[“b”]])
# [[1, 2, ‘3’], [‘a’, ‘b’]]
reduce(lambda x,y: x + y, [1,2,3], 100)
# 106
filter(lambda x: x > 0, range(10,-5,-3))
# [10, 7 , 4, 1]
cs784(Prasad)
L1Intro
21
Meta-programming in Jython
 Dynamic
code evaluation
print eval (“[1,3] + range(6,10,3)”)
# [1, ,3, 6, 9]
x = 2 + 3j
exec “x = 5, x + x”
#(5, (4+6j)
cs784(Prasad)
L1Intro
22
Java functionality through Jython
import java.lang as lang
import javax.swing as swing
import java.awt as awt
names = ["Groucho", "Chico", "Harpo"]
quotes = {"Groucho": "Say the secret word", "Chico": "Viaduct?",
"Harpo": "HONK!"}
def buttonPressed(event):
field.text = quotes[event.source.text]
def exit(event):
lang.System.exit(0)
def createButton(name):
return swing.JButton(name, preferredSize=(100,20),
actionPerformed=buttonPressed)
cs784(Prasad)
L1Intro
23
win = swing.JFrame("Welcome to Jython", size=(200,
200),windowClosing=exit)
win.contentPane.layout = awt.FlowLayout( )
field = swing.JTextField(preferredSize=(200,20))
win.contentPane.add(field)
buttons = [createButton(each) for each in names]
for eachButton in buttons:
win.contentPane.add(eachButton)
win.pack( )
win.show( )
cs784(Prasad)
L1Intro
24
Current Trend

Multiparadigm languages
– Functional constructs for programming in the small
» Focus on conciseness and correctness
– Object-Oriented constructs for programming in the
large
» Focus on programmer productivity and code evolution

Example languages
– Older: Python, Ruby,
– Recent: Scala, F#, etc
cs784(Prasad)
L1Intro
25
Scheme (dialect of LISP)
 Recursive
definitions
 Symbolic computation : List Processing
 Higher-order functions
 Dynamic type checking
 Functional + Imperative features
 Automatic storage management
– Provides a uniform executable platform for
studying, specifying, and comparing languages.
cs784(Prasad)
L1Intro
26
Standard ML and Scala
 Strongly
typed language
– static type inference
– SML supports polymorphic types
 Supports
Abstract Data Types and Modules
 Higher-order functions
 Pattern matching
– cf. Prolog, list-processing in Scheme
cs784(Prasad)
L1Intro
27
Java vs Scala
//Java - what we're used to seeing
public String buildEpochKey(String... keys) {
StringBuilder s = new StringBuilder("elem")
for(String key:keys) {
if(key != null) {
s.append(".")
s.append(key)
}
}
return s.toString(). toLowerCase()
}
cs784(Prasad)
L1Intro
28
Java vs Scala
//Scala
def buildEpochKey(keys: String*): String = {
("elem" +: keys) filter(_ != null)
mkString(".")
toLowerCase
}
cs784(Prasad)
L1Intro
29