20-CS-4003-001 Organization of Programming Languages Fall 2017
Topological Sort

Lambda calculus, Type theory, Formal semantics, Program analysis

    All lectures        Code

Topological Sort - extend syntax

(define-syntax topo
  (syntax-rules ()
    ((topo ((n p (m ...)) ...))
       ((n (lambda ()
              (set! n (lambda () 
                        (error 'n "is part of a cycle")))
              (m) ...
              (set! n (lambda () "done")) 
              (display 'p) (display " ")))
       (n) ... ))))
(define test
  (lambda ()
       ((h00 Cincinnati (h01 h05 h07 h09))
        (h01 Cleveland (h04 h05 h08))
        (h02 Columbus (h00 h01 h06 h10 h12 h18))
        (h03 Chicago (h05 h09 h12 h13 h14))
        (h04 Calumet (h09 h11 h12))
        (h05 Corman ())
        (h06 Denver (h03 h09 h10 h11))
        (h07 Dallas (h04 h09 h12 h13))
        (h08 Durango (h10 h11 h20 h21))
        (h09 Durea (h25))
        (h10 Detroit (h25))
        (h11 Edwards ())
        (h12 Echemonte (h08 h09 h10 h11))
        (h13 Eagle_Creek (h20 h21 h22))
        (h14 Erasmus (h15 h19 h21))
        (h15 Fullman (h10 h11 h19 h24))
        (h16 Fortnight (h19 h20))
        (h17 Fallow (h15 h20 h21))
        (h18 Fables (h19 h20))
        (h19 Finese (h22))
        (h20 Gordon ())
        (h21 Gallop (h10 h20))
        (h22 Gormon (h11 h21 h25))
        (h23 Harmon (h12 h22 h24))
        (h24 Halpern (h22))
        (h25 Hornwich ())))))
prompt> (test)
hornwich durea edwards detroit gordon gallop durango 
echemonte calumet corman cleveland gormon eagle_creek 
dallas cincinnati finese halpern fullman erasmus 
chicago denver fables columbus fortnight fallow harmon 
;Value 44: done
 -  To the left is a macro expansion for topologically sorting a partial order. The example it is applied to uses city names to name the objects (vertices of a graph). Each object has a procedure which does the following. When it is first called it begins a process whereby all procedures corresponding to its dependencies are invoked and after that happens, the identity of the object is output. But prior to invoking the procedures of the dependencies the procedure redefines itself, via the first set!, to this:
  (lambda () 
    (error 'n "is part of a cycle")))
If this procedure is invoked it is because there is some chain of invocations through dependencies, beginning with procedure X, say, and back to X. This means no total ordering is possible and the error message resulting from this invocation expresses that. Just after a procedure outputs its identity it redefines itself again through the second set! to
  (lambda () "done")) 
Any future calls to this procedure will just return without exploring an already explored part of the graph. There is no error in this case because the procedure's identity has already been output (it and its dependencies have all been taken care of and are effectively removed from the graph).

Observe that there are no if statements in the code! None are needed because, when the program is loaded, all the procedures are "wired" up so that only the procedure invocations dictate control flow and the structure of procedure calls is a product of the define-syntax expansion.

Incidentally identifiers h?? are used instead of city names because they are short - we could have used just the city names if we had wanted to.