Notes on Elements of Programming Languages

Introduction

    Context determines what a symbol means,
		HTML	- / stands for itself BUT
			  </ indicates a end-tag.
			  
		C	- x is an identifier but
			- 'x' is a character but
			- "x" is a string (address of char x + char \0)

		Shell	- "$" word is the value,
			- word is the variable
			- `word` executes the word and replaces it by the output

		LISP	- (X ...) then X is a function
			- (... X   ) then X is a variable
			- (QUOTE (....X....) ) then X is an atom
			- '(....X....) then X is an atom
			- " ....X..." then X is a character in the string

		Prolog	- x is a constant
			- X is a variable
			- "x" is a list of a number (the character code!)

		Java	- See C above

		Smalltalk - + is a message
			    #+ is a symbol
			    '+' is a character

   Sorting out identifiers and names can get messy.
	Invent more examples to show how the meaning of a variable
	can vary in a program.

Names/Identifiers in languages

	Lengths and formats
	Case SeNsItIvE?

	Question: Is C case sensitive?
		Is the UNIX Shell case sensitive?
		How about LISP?
		How about: HTML, Prolog, Java,...

	Special words
		key vs reserved vs special fonts

Variables

	variable::=structure with{name, address, type, value, scope, lifetime}.

	Note:  Value of variable should be one of the objects
		that are permitted in that variable's type.

		The type of a variable determines the operations
		that can be applied to it.
		For all v:variable, value(v) in objects(type(v)).

		The size of the block of memory assigned to a variable
		is also determined by the type of the variable.

	UML
		http://www.csci.csusb.edu/dick/cs320/handouts/ch05.gif
		http://www.csci.csusb.edu/dick/cs320/handouts/ch05.mdl


	Overloading: One identifier, many types and values.
		C++     - Types of arguments determine meaning of operator
			  or function name.

	Aliasing  - multiple names for one address

	Type - the idea dates back to "Principia Mathematica"
		by Whitehead and Russell in the 1930s.

Binding

	variable >----bound to------>attribute value
		Think of a piece of string tying one thing to the other.
		UML links/associations are bindings.

	When is can something be bound?
	   When is something fixed?
		Language Design, Implementation, Compilation, Linking,
			Start of run, During run?
	   Who decides this?
		Designer, Implementor, compiler, linker, or the program?


	Static vs dynamic binding vs semi-dynamic
		Do not confuse with the keyword "static" in C!
		Do not confuse with dynamic storage either.

	scope vs lifetime

	For how long?
		---> Life time

	In what parts of the text?
		--> Scope

Type checking

	In many languages it is assumed that if the result of arithmetic is in
	range then the programmer is happy with the result.
	Not always true?

Type Compatabillity

Type Coercions

Genericity and Polymorphism.

	In complex type systems two object of different types sometime
	have a set of common operations/values -- a common type.

	Some modern languages have a type hierarchy...

What does C check?  What is compatible?  What is coerced?  RISKS?

History of Types in C-like languages:

	B had 1 type: 16 bit word
	K&R C (The original) did not check data types very much.
	ANSI has stronger type checking than K&R C.
	C++ requires strong typing (but polymorphic).  
	Java is strongly typed but... polymorphic

Scope

	Where in a program does a symbol have a particular meaning?
	How do you find the definition of an identifier in a part of a program?

	In particular: variables in a function body that are not declared
		in that body (non-local variables).
	Static vs dynamic
		Dynamic:  Names in a function have the meaning that
			they would have where the call occurs.
		Static: Names get the meaning they have in the definition
			of the function that is called.

	C/C++ functions use static scope.
	C/C++ macros use dynamic scope.

	In many languages with there is a way to
		hide names/variables/etc inside a "module" even tho' it
		continues to exist - it is illegal to refer to it.

		Example - C static functions can not be referred to
			  outside the *file* in which they occur.
			  This scope is determined at compile time.

		Example - In Ada any declared object in a package can
			  be either visible to other modules or not,
			  at the programmers discretion.

		C static variables only be referred to inside their on *block*.
		However they have a continuous existence from the start
		of the program to its end.

		Example - C++ and Java private variables can only be referred
			to inside that class.

	There are a set of C examples of Static and Dynamic binding in
		http://www.csci.csusb.edu/cs320/c
	in files called binding*

	Notice that a function binds variables to a static scope in C, but
		a definition's variables are bound semi-dynamically.

	LISP 1.5: used dynamic scoping.
	Scheme: Uses static scoping.

	In Scheme... A `let` produces a set of local variables that are 
	statically bound and so any functions defined in the block, will 
	refer to these variables even if the function is called elsewhere:
	variables have local scope with static binding, but functions have
	a global scope and static binding.

	In Our LISP:  A `defun` uses static scopes but `define` uses dynamic!

Scope vs Lifetime

Referencing Environments

Named constants

Initialization

Notice in C/C++ the same syntax is used for initializations and for assignment
	but the semantics is not the same....

Java:  If a variable is given the modifier "final" then its initial value 
	is the last value it ever gets.  So it is a constant!

Examples

    Shell
	Dynamic Scope
	Shell variables are always defined (but have value ""
		until a value is given)
	Only special "environment" variables are exported
		to called programs and commands.
	No binding is exported OUT of a program or command.
	No Side Effects on variables.
	If you 'cd' in a script or program you do not change the
		parents directory.

   C
	Includes all the Pascal forms plus some more.

   LISP
	OLD: Dynamic scope.
	NEW: Static scope
	OURS:  BOTH!
	There are both variables (stored permanently)
	AND Arguments - local to a function
	AND Local "static" variables in (Let ........) statements

   Prolog
	Highly Dynamic. Variables vanish.  Variables can not be assigned.
	Permanent and/or global data has to be stored as facts in
		a ready made data base.
	In Prolog variables are given particular values
		as a hypothesis.
	They become undefined
		When a 'subprogram' or a command terminates
		OR When a contradiction is found.
		This is called "backtracking".
	Once defined a Prolog variable can not change its initial value
		UNLESS it is destroyed when a command finishes or backtracks.

Type Compatibility

	SubTypes and Polymorphism

Assigned Work on Chapter 5

Usual Review questions.

FYI on problems

Problem 8.
Here is a roughly equivalent C/C++ version of
the program - it will not compile because it is not legal C/C++;
int x;
void sub3();
void sub1()
{ int x;
  void sub2(){ /*This is not legal in C/C++  but if it was...*/
	....
  }

  ...
}
void sub3()
{ ...
}

int main(...)
{....
	sub2();
 ...
}