6 — Simple Types (a)

Due Tuesday, 20 Feb; 9:00am

Delivery Send me a zip file named 6-lastname1-lastname2.zip with your solutions. The zip archive should contain a single directory called 6-lastname1-lastname2, which in turn contains two files, each starting as follows:
; Problem Set 6
; Lastname1, Firstname1
; Lastname2, Firstname2
The two files should be named
  • lang.rkt, for the revised language implementation,

  • client.rkt, for the revised language client file,

The directory may contain other files.


Project Idea If you have not met with me concerning a project idea, come to my office hour or schedule a meeting by Feb 20.

Project Memo If you have trouble with the Project Memos, see me during office hours or make an appointment.

Problem Modify the Racket-y network language so that it supports a simple type system.

  Type = Edge
  | Node
  | Weight
  | Edges
  | Nodes
  | Path
  | Paths
  | [Type Type ... -> Type]


; an edge specification
; a node specification
; the type of cost/profits/etc. (reals)
; a list of edges
; a list of nodes
; a cost plus a list of nodes
; a list of paths
; function types

The language itself should have the following shape:
  Program = Definition
  | ...
  | Expr
  | ...
  | Problem
  Definition = (define Id Type Expr)
  Problem = (solve Id Id Expr)
  Expr = (edge Id Number)
  | (node Id Expr ...)
  | (cons Expr Expr)
  | (empty Type)
  | (first Expr)
  | (rest Expr)
  | (empty? Expr)
  | (path Expr Expr)
  | (path-cost Expr)
  | (path-list Expr)
  | (Expr Expr ...)
  | (if Expr  Expr  Expr)
  | (lambda ({Id : Type} ...) Expr)
  | argmax
  | argmin


; .. to establish a single
; place for common elements
; the expressions
; make up the network
; specify the problem
; mostly like in Racket
; Expr yields an "optimizer"
; a specification of Edges
; a Node specification
; extend list
; empty list of specific type
; first
; rest
; empty?
; make a Path
; extract cost
; extract list of nodes
; function application
; conditional expression
; a user-define function
; (-> (-> Path Weight) Paths Path)
; (-> (-> Path Weight) Paths Path)

Note that this syntax no longer incorporates all of Racket. Also, the purpose of this syntax is to allow network-flow mathematicians to use definitions for common elements. For example, it is obviously possible to give a list of edges a name. What could mentioning this name mean, however, in a node specification?


  1. Add the grammar to the top of your language implementation file.

  2. Describe the scoping structure of this language in a comment block below the grammar.

  3. Describe the semantics of this syntax with comment blocks for each feature below your scoping structure description. Try to make the syntax convenient without making it confusing.

  4. Develop a reasonably-easy-to-use type system for the revised language that also works with your chosen semantics.

    Use ASCII art within comment blocks to describe the type system.

The purpose of this task is to get you design some elements of a language, not its implementation.