451: Programming Languages

Comparative study of programming language paradigms, design principles, and implementation strategies.

Topics

• Syntax, semantics, and pragmatics of programming languages

• Imperative, functional, logic, and object-oriented paradigms

• Type systems: static vs. dynamic, strong vs. weak

• Scoping rules, closures, and parameter passing

• Language runtime models and memory management

Projects

Hash Table (451/ht/)

A complete hash table implementation in C with separate chaining. ht.c provides insert, delete, lookup, and free operations; main.c provides an interactive REPL for testing. Explores how dynamic dispatch and ADT design differ across language paradigms.

void ht_delete(tHashTable ht, void *n) {
  tBucket *tmp, *last;
  int hash_value = abs((*ht->hash)(n)) % ht->size;

  for (tmp = ht->table[hash_value], last = tmp;
       tmp != NULL;
       last = tmp, tmp = tmp->next) {
    if ((*ht->compare)(tmp->data, n)) break;
  }
  if (tmp != NULL) {
    if (tmp == last)
      ht->table[hash_value] = tmp->next;
    else
      last->next = tmp->next;
    free(tmp);
  }
}

Symbol Table with Scoping (451/ht2/)

Extends the hash table into a scoped symbol table (main2.c, symbol.c) supporting nested scopes with add, lookup, and close operations — a direct implementation of the environment model used by block-structured languages.

/* Search from innermost to outermost scope */
int st_lookup(tSymbolTable st, void *symbol) {
    for (int i = st->current_scope; i >= 0; i--)
        if (ht_lookup(st->scopes[i], symbol))
            return i;   /* returns scope depth where found */
    return -1;          /* not found */
}

int st_add(tSymbolTable st, void *symbol) {
    if (st_lookup(st, symbol) != st->current_scope) {
        ht_insert(st->scopes[st->current_scope], symbol);
        return 1;   /* success */
    }
    return -1;      /* duplicate in current scope */
}

Prolog / Logic Programming (451/pl/)

Prolog source files (examples.pl, ms.pl) demonstrating the logic programming paradigm: facts, rules, unification, list operations, and difference lists. Contrasts the declarative style of Prolog with the imperative and object-oriented examples elsewhere in the course.

% facts
father(dave, erin).   mother(judy, erin).
married(dave, judy).

% rules
married(X, Y) :- married(Y, X).
parent(X, Y)  :- father(X, Y).
parent(X, Y)  :- mother(X, Y).
grandparent(X, Y) :- parent(X, Z), parent(Z, Y).

% list operations
append([], X, X).
append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs).
member(X, [X|_]).
member(X, [_|Xs]) :- member(X, Xs).