Path: utzoo!mnetor!uunet!husc6!bloom-beacon!gatech!hubcap!mark
From: mark@hubcap.UUCP (Mark Smotherman)
Newsgroups: comp.edu
Subject: Re: conceptual basis of CS
Message-ID: <1573@hubcap.UUCP>
Date: 4 May 88 18:13:38 GMT
References: <4823@june.cs.washington.edu>
Organization: Clemson University, Clemson, SC
Lines: 68
Keywords: fundamental concepts
Summary: naming and binding: two fundamental concepts

I'll submit two items for your list: naming and binding.

Naming choices and binding actions underlie the design and operation of
translators and interpreters.  And what is a computer if not an interpreter?
Likewise, translation is ubiquitous function when dealing with computers.

Naming consists of choosing the properties of the name space in which
actions and objects can be identified.  The major issues are:

* ordering -- Ordered names allow operations to be performed on one valid
  name to obtain another valid name.  E.g. semantics of the PC in the CPU,
  array addressing, linear segmentation (IBM).  Unordered names provide a
  measure of protection but must be managed by a naming table (or equivalent).
  E.g. symbolic segmentation (MULTICS).

* range and resolution

* homogeneity -- Does the name space identify objects or actions of identical
  type, or are multiple types allowed in the same name space?  E.g. general
  register set vs. function-specific registers, isolated I/O vs. memory-mapped
  I/O.

* sharing/conflict -- A particular name may be shared by several name spaces,
  and the mapping of this name may involve renaming (e.g. relocation) or
  context search rules (e.g. scope).

* alias/synonym

* dimensionality

* side effects -- E.g. autoincrement addressing.

Binding is related to naming since the mapping of a name space is an instance
of binding.  Yet binding is a more general concept: the specification of the
value of an attribute of an object or action.  Binding can be static or
dynamic, and early or late.  There are several binding times:

* language design time
* translator design time
* program design time
* preprocessor/macro processor time
* conditional assembly time
* compile time
* link time
* load time
* task initiation time
* dispatch time
* dynamic link time
* swap time/page fault time
* procedure call time (actual for formal parameters)
* execution time

Dynamic binding depends on the presence of a naming/attribute table (or
equivalent).  E.g. virtual memory page/segment tables, cache tags, the
load/stores in the code segment that manage the dynamic binding of the
register set, the link fields in a linked list, the schema in a database,
the RLD (relocation dictionary) for linking and loading, the ESD (external
symbol dictionary) for linking, the static links/display registers for an
activation record stack (static binding of variables but dynamic binding
of procedure calls).

(I tried to address these concepts, especially as they apply to a computer
organization course, in a paper given at ACM SIGCSE, St. Louis, 1987.  You
can find there several references to the work of other authors.)

-- 
Mark Smotherman, Comp. Sci. Dept., Clemson University, Clemson, SC 29634
INTERNET: mark@hubcap.clemson.edu    UUCP: gatech!hubcap!mark