Definitions

Abstract syntax - idealized syntax, designed for convenient use by the underlying interpreter/compiler; result of parsing a concrete syntax expression

Concrete syntax - syntax written by the user; consumed by the parser

Closure - a wrapper that contains an expression (function/ binding) and its environment; expression saved until it needs to be used

Static vs. Dynamic Scoping

Static Scope: In a language with static scope, the scope of an identifier's binding is a syntactically delimited region. A typical region would be the body of a function or other binding construct.

Dynamic Scope: In a language with dynamic scope, the scope of an identifier's binding is the entire remainder of the execution during which that binding is in effect. That is, in a language with dynamic scope, if a function g binds identifier n and then invokes f, then f can refer to n—and so can every other function invoked by g until it completes its execution—even though f has no locally visible binding for n.

from PLAI, p. 36

Closures and First-Class vs. First-Order Functions

First-order Functions are not values in the language. They can only be defined in a designated portion of the program, where they must be given names for use in the remainder of the program. (For a language like C, the "designated portion" is anywhere in the top-level of a source file, but not, for example, within the body of another function.) The functions in F1WAE are of this nature, which explains the 1 in the name of the language.

Higher-order Functions can return other functions as values and take other functions as parameters.

First-class Functions are values with all the rights of other values. In particular, they can be supplied as the value of arguments to functions, returned by functions as answers, constructed as values by expressions, and stored in data structures.

Deferred Substitution

Deferred Substitution Initially, we have no substitutions to perform, so the repository is empty. Every time we encounter a substitution (in the form of a with or application), we augment the repository with one more entry, recording the identiﬁer’s name and the value (if eager) or expression (if lazy) it should eventually be substituted with. We continue to evaluate without actually performing the substitution.

A side-effect of deferred substitution is dynamic scoping, which we were able to fix by using closures to store the environment from which the function was created in.

Eager vs. Lazy Evaluation

Lazy With- we reduce the named expression to a value only when we need to

Lazy Functions- we do not reduce the argument to a value until necessary

Strictness Points- the points where the implementation of a lazy language forces an expression to reduce to a value (example: in a function application, need to evaluate exactly what function to invoke, can't just leave it as a function closure)

Eager- the named expression is reduced to a value before being substituting it.

Backus-Naur Form (BNF)

A concise specification language for expressing (among other things) the concrete syntax of a programming language. A BNF often strongly suggests a corresponding abstract syntax.

Here's an example BNF for a language with arithmetic expressions, with expressions, first-class functions and applications, a conditional statement, and explicit language support for recursion. This particular language allows an arbitrary number of parameters to a function in its definition or arguments in a function application.

 <CFWAE> ::= <num>
   | {+ <CFWAE> <CFWAE>}
   | {- <CFWAE> <CFWAE>}
   | {* <CFWAE> <CFWAE>}
   | {/ <CFWAE> <CFWAE>}
   | <id>
   | {if0 <CFWAE> <CFWAE> <CFWAE>}
   | {with {<id> <CFWAE>} <CFWAE>}
   | {fun {<id> ...} <CFWAE>}
   | {<CFWAE> <CFWAE> ...}
   | {rec {<symbol> <CFWAE>} <CFWAE>}

Racket syntax, helpful procedures, and thoughts

(cond
   [Condition1 Result1]
   [Condition2 Result2]
   ....
   [ConditionN ResultN])

(cond
     [(number? v) ...]
     [(boolean? v) ...]
     [(string? v) ...]
     [else false])

(match data
   [pattern  action]
      [(? number?) (foo)]                    ;; check if data is number 
      [(list a b c) (foo a b c) ]            ;; back-reference of list elements
      [((and n (? number?))) (foo n)]        ;; check if data is number and back-reference it as n
      [else (foo)]
)
;; Keep in mind that in pattern matching
;; '...' or '___' means 0 or more 
;; '..n' or '__n" means n or more 
;; '_' matches anything

Variable definition:

(define x 3)

Function definition:

(define (funcName arg)
    (+ 1 arg))

Environment: - repository of deferred substitutions

(define-type Env
     [mtEnv]
     [anEnv (name symbol?)(value CFWAE-Value?)])

Expression Closures:

(define-type CFWAE-Value
     [numV (num number?)]
     [exprV (body CFWAE?)(env Env?)] ;; used to hold an unevaluated expression and its environment (used in lazy interp)
     [closureV (param symbol?)(body CFWAE?)(env Env?)]) ;;used to close over the existing environment to ensure static scope

map - performs a procedure on all elements of the list in order

map <procedure> <list>
(define (parseList list)
(map parse list))

Type-case

(type-case WAE expr
            [num (n) expr]
            ...)

Define-type (From assignment 1)

(define-type WAE
 [num (n number?)]
 [binop (op procedure?) (lhs WAE?) (rhs WAE?)]
 [with (b Binding?) (body WAE?)]
 [with* (lob (listof Binding?)) (body WAE?)]
 [id (name symbol?)])

Recursion interp (From lecture)

(define (interp exp env)                                                      
 (type-case CFAE exp                                                         
     ...
    (id  (name) (lookup name env))
    (fun (arg-name body) (closureV arg-name body env))
    (if0 (tst thn els) 
         (type-case CFAE-value (interp tst env) 
            (numV (n) (if (zero? n) (interp thn env) (interp els env)))
            (else (error "non numeric if0 test value"))))
    (app (fun-exp arg-exp)
         (let ((the-fun (interp fun-exp env))
               (the-arg (interp arg-exp env)))
           (type-case CFAE-value the-fun
             (closureV (arg-name body closure-env)
                       (interp body (anEnv arg-name the-arg
                                           closure-env)))
             (else (error "You can only apply closures!")))))
    (rec (bound-id named-exp body)
      (local ([define new-env (anEnv bound-id 
                                     (numV 0)
                                     env)]
              [define named-value (interp named-exp new-env)])
        (begin
          (set-anEnv-val! new-env named-value)  ;; Patches (numV 0) out for the correct value
          (interp body new-env))))
      
    
    ))

Strict code (from lecture)

(define (strict val)
 (if (expV? val)
     (strict (interp (expV-exp val) (expV-env val)))
     val))