SPlanner

Willie Boag
Jake Kinsman
Matt Barden
December 3, 2014

Overview

SPlanner is an interactive database for planning which courses to take using MITís online Open Courseware. Users will find which course they would like to learn about, and SPlanner will compute/display the best sequence to follow for learning the courseís prerequisites.

Screenshot

-

Concepts Demonstrated

 - Message Passing: MIT Courses are stored as objects that apply methods via message passing
 - Layers of Abstraction: Layers between URL libraries, HTML libraries, Graph data type, and Course objects
 - Hash Tables: Hash table to map from department number to department name
 - Laziness: Cache modules are not retrieved until particular data is requested
 - Embedding Recursive Data Types in Lisp: Nested HTML tokens are handled as nested lists
 - Sum Types: Error values have different types from successful return values (symbols vs. lists)
 - Map/Filter/Reduce: Most data processed via list operations (13 maps, 10 filters, 2 foldls)
 - Type Coercion: The Graph performs type cohersion for error checking without mutating the graph in the global environment
 - Recursion: Various functions are defined recursively

External Technology and Libraries

Libraries:

 * net/url
    * allows url lookups
 * html-parsing
    * tokenizes HTML string data into HTML tokens
 * data/gvector
    * internal representation of the graph data structure
 * pict
    * allows the creation and combination of pictures, including text
 * pict/tree-layout
    * contains special pict combiners that make creating trees easy

Favorite Lines of Code

  • Willie:
    (define (all-prereqs course)
        (let ((prereqs (course->prereqs-list course)))
            (if (null? prereqs)
                '()
           	    ; add current prereqs to return value and get transitive closure
        	    (append
         	        (map (lambda (c) (list (car c) (course-number course)))
              	     prereqs)
           	        (foldl append 
                           '()
                           (map (lambda (c-num)
                                    (all-prereqs
                                        (get-course-from-number
                                            (car c-num))))
                                prereqs))))))
    

Computes the transitive closure of prerequisites as a list of (course,immediate-prereq) pairs. I really liked how slick it turned out. I could get the direct prerequisites for a given course, so I mapped an extractor for its direct prereqs and appends that to the flattened list of mapping the extractor to each prerequisite.

  • Jake:
(let ((result (helper graph visited)))
      (define (level-one-flatten tree)
      (cond ((empty? tree) '())
            ((not (list? (car tree))) (list tree))
            (else (append (level-one-flatten (first tree)) (level-one-flatten (rest tree))))))
  (level-one-flatten result)))

The first line assigns result to be a nested list of arbitrary depth, whose terminal entries are topological sorts (helper is the procedure that actually computes all topological sorts). The level-one-flatten procedure takes results, and "flattens" it into a list of lists, where each internal list is a single valid topological sort.

  • Matt:
  (foldr + 0
         (map
          (lambda (req)
            (let [(index (list-index req srt))
                  (reqlen (length (course->prereq-courses req)))]
              (foldl + 0
                     (map
                      (lambda (ele) (- index (list-index ele srt)))
                      (course->prereq-courses req)))))

This is our utility/coherence function. It defines coherence as the sum of the distances between each course and each of its prerequisites. The lower the value, the better.

Technology Used Block Diagram

Additional Remarks

None.