Computer Science 15-112, Fall 2011
Class Notes:  How a Programming Language Works

Note:  These examples are strictly demonstrational.  A "real" language, even a tiny one, would use more robust and efficient lexing and parsing, a more sensible grammar, better typing and semantics, better error messages, less buggy code, etc, etc, etc.  Do not use this code except for demonstrational purposes!!!!

In this optional topic, we discussed the basic mechanics of how a programming language works.  Our goal is an invented language that works as such:

vars(rfib ifib counter)

; rfib: recursive fibonacci
set rfib to function(n) {
    if n is 0 then { return 1 }
    if n is 1 then { return 1 }
    return rfib(n-1) + rfib(n-2)
}

loop counter from 0 to 6 { output rfib(counter) }

; ifib: iterative fibonacci
set ifib to function(n) {
    vars(x y temp counter)
    if n is 0 then { return 1 }
    if n is 1 then { return 1 }
    set x to 1
    set y to 1
    loop counter from 2 to n
    {
        set temp to x + y
        set x to y
        set y to temp
    }
    return y
}

loop counter from 0 to 6 { output ifib(counter) }

How do we make this come to life?  In the following steps:

• lexer.py
  This is a simple lexer that tokenizes the input.
   
• parser1WithExprs.py
  We parse the tokenized input stream into simple arithmetic expressions, generating an Abstract Syntax Tree (AST), and include an interpreter that evaluates that AST, along with a simple REPL (read-eval-print loop).
   
• parser2WithVars.py
  We add variables (and, to make them work, evaluation contexts, which we implement as a tree (linking child contexts to parent contexts) of Python dictionaries mapping variable names to their values).
   
• parser3WithDeclaredVars.py
  To show that we have control over our language's semantics, we change the scoping/binding of variables by adding required variable declarations, which gives us finer-grained control over scope in nested blocks than, say, Python supports.
   
• parser4WithFns.py
  We add functions.
   
• parser5WithConditionals.py
  And simple "if" statements.
   
• parser6WithLoops.py
  And simple "loop" statements (counting from a set start to a set end, similar to "for counter in range(start, end+1)" in Python.
   
• simpleLanguage.py
  Here it is, our final result, complete with that example code from above, which actually works as expected.  Wahoo!

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem