Recap of last time

• Scope: A region of a program in which a name is visible

• Block: A syntactic construct that defines a scope

• Block-Structured Language: Supports the nesting of blocks, including procedures

The use of a name is resolved to the corresponding declaration in the innermost scope.

More about scoping

Here’s an example, in Ada-style syntax.

procedure A() -- Top-level function
	x: integer; -- Declares a varaible
	
	procedure B() -- Nested functions
	begin
		x := 6;
	end
	
	procedure C()
	x: integer; -- Note that this is a local variable to C
	begin
		B();
	end
begin -- Start of body of A
	C();
end

The question is: when B gets called, which x changes? This is non-trivial. Is it the x in the scope of A, within which it’s declared, or C, where it’s called?

Answer: depends on the language.

In a statically-scoped language, like Ada, Scheme, ML, etc., it would be A. In a dynamically-scoped language, it would be C. Stated more formally:

• Static Scoping: The body of a procedure is evaluated in the environment of the procedure definition.

• Dynamic Scoping: The body of a procedure is evaluated in the environment of the procedure where it’s called from, regardless of where it’s declared.

Where environment means the mapping of variables to their values or memory locations.

All the languages we’re going to look at are statically scoped, and most programming languages are as well. Traditional Lisp uses dynamic scoping, for one---because it was a bug in the first implementation, and then it stayed. PostScript as well, although that’s not a language that people write by hand. It’s auto-generated and then sent to printers. The only real benefit of it is that you can save sending a whole bunch of information as parameters. In PostScript, for example, you can access all your document options (what color you want, etc.) from the containing environment. But other than that, there’s not really much good reason for dynamic scoping, so languages avoid it.

But it gets more complicated than that.

Higher-order functions

In languages like Scheme, you can pass procedures as parameters to other procedures.

For example:

procedure f(procedure g) -- f takes g as a parameter
	x: integer := 5;
begin
	g();
end

procedure h()
begin
	print(x);
end

procedure main()
	x: integer := 20;
begin
	f(h);
end

If main gets called, what does the program print?

Hm, prof messed up a bit. h should have been nested in something, there’s no x in the global scope. You’d get a compile-time error. Let’s fix it:

x: integer := 50;

procedure f(procedure g) -- f takes g as a parameter
	x: integer := 5;
begin
	g();
end

procedure h()
begin
	print(x);
end

procedure main()
	x: integer := 20;
begin
	f(h);
end

Since Ada is statically scoped, this is obviously going to print 50.

Next class, we’re going to talk a bit more about how scoping is implemented.

Problems with block structure

The problem with block structure, which Ada tried to solve, is that it leads to “all-or-nothing” visibility. For example:

procedure f()
	...
procedure g()
	...
procedure i()
	...

Suppose that these three functions all mutually call each other. So you put them in the same scope, and everything’s fine. But say you want to put it somewhere else, say in a library, where you want only f to be exposed to the outside world. There’s no real way to do that. Since they all need to be on the same scope, if you have f visible, g and i must be too.

The traditional solution to this is to define what’s called modules or packages. It’s a block of code, but with a separate, defined interface that dictates what’s visible outside that block of code.

The module has two parts to it:

• The body, which is just a block of code, with procedure, type, and variable definitions. Essentially, all the code to implement some functionality.

• The interface or specification, which is a declaration of only the things that are visible outside the module.

These might not be in separate files per se, but there’s usually at least this separation conceptually.

The analog of this in object-oriented languages is private and public members of a class, which is sort of like this, but a class is not a module, a class is a type. A module is just a bunch of code.

Ada

Developed in the early 80s based on the US Department of Defense to unify their technologies under a single, non-proprietary programming language. This is including contractors, who had a bad habit of using their own proprietary languages so that no one else could maintain those programs.

The DoD had a competition for designing a language for this purpose, and one of their major requirements was to have a module system. The idea is to have as little of the implementation visible to the outside world as possible. That way the implementation can change without breaking programs that rely on it. This is the principle of information hiding.

The competition also specified other important requirements, such as concurrency and modularity. Ultimately a French team won, with a language they called Ada, after Ada Lovelace, Charles Babbage’s assistant and who is often called the first programmer.

They also trademarked the Ada name and restricted use of it in compiler vendors to only those who could pass their automated tests to ensure compliance to the Ada spec.

Why are we studying Ada? Because it’s an imperative language, it has constructs for dealing with concurrency, and it’s a good choice among other similar languages. Also, there was a lot of work done on it in NYU.

Special features

The two features we’ve mentioned above:

• Modules (called packages)

• Concurrency (called tasks)

We’ll go over some examples, which are also on the website. Notes here will only be on more important points and constructs.

In Ada, .adb files stand for “ada body”, or implementation files, and .ads stands for “ada specification”, or interface files.

What’s the difference between functions and procedures? Functions return values, procedures don’t.

Package names have to be the same as the name of the file that implements and specifies it. This is how the compiler knows where to find it.

Ada allows you to define subtypes, which are subsets of built-in types. For example, integers can be restricted to a particular range.

The Ada compiler will run any file that has a single procedure in it, effectively making it the main function. All other code should be in packages. The main function doesn’t have to be called main.

put is for printing, get is for reading. Include it by having with text_io at the top of the file. There’s a sub-package (or something) of that for handling integers, which is a generic package for any integer type. Which is pretty interesting, generic packages as opposed to generic types.

Usually functions and procedures in packages can be used with package_name.function_name, but you can get rid of the package name by typing use package_name.

Modules are not types! But you can define your own data types as well.

Notions of concurrency

What does concurrency mean? Especially in Ada, which is a language that used to be run only on single-processor systems?

Boiling it down, two events are concurrent if no assumption can be made about the relative order in which they occur.

Concurrency has a slightly different notion to it compared to parallelism. Parallelism is using multiple cores or computing devices at once. But concurrency can happen even on a single-core system.

Concurrency is expressed as threads, which are sequences of instructions that may run concurrently. In Ada, these are called tasks.

As soon as you get to the point in the program where a task is declared, that task starts running immediately while the main thread keeps going.

Why would you want concurrency even when you don’t have parallelism? So that your program can interactively respond to data that comes at unpredictable times, such as sensor data or user input. You can then have a small thread that handles this input data, shares it with the rest of the program, etc.

How does it share data with other threads? Ada allows threads to send messages from one to another. We’ll talk about this the next time. Ada calls them entries.

Administrivia

Assignment 1 is up, and it’s in Ada. Prof recommends we get started on it ASAP.