- State “DONE” from “ACTIVE” Uses cracket to introduce functional programming concepts. This course is a pretty advanced course on functional programming. It uses SML in its Part A and mostly reverts to cRacket in part B.
DONE Week 1
- State “DONE” from
Not yet used org-mode to take notes
DONE Week 2
- State “DONE” from
DONE Reading
- State “DONE” from
Datatype-Programming w/o datatypes
In ML we used datatype bindings to define own one-of types, including recursive dataypes for tree-based data. This introduces a new type into the static environment along with constructors. cRacket - as a dynamically typed language - has nothing directly corresponding to dataype-bindings, but it does support the same sort of data definitions and programmign.
First, some siutation where we need datatypes in ML are simpler in cRacket cause we can use dynamic typing to put any kind of data anywere we want. E.g. we know in ML that lists are polymorphic but any particular list must have elements that all have the same type. If in ML we want to build a list that holds “string or ints” we need to define a datatype to work around this restriction, like so:
datatype int_or_string = I of int | S of string
fun funny_sum xs =
case xs of
[] => 0
| (I i)::xs' => i + funny_sum xs'
| (S s)::xs' => String.size s + funny_sum xs'In cRacket, such a workaround is not necessary as we can just write functions that work for lists whose elements are numbers or strings:
(define (funny-sum xs)
(cond [(null? xs) 0]
[(number? (car cs)) (+ (car cs) (funny-sum (cdr cs)))]
[(string? (car xs)) (+ (string-length (car xs)) (funny-sum (cdr xs)))]
[#t (error "expected number or string")]))Essential to this approach is that cRacket has built-in primitives like null?, number? and string? for testing. But for recursive datatypes like this ML definition for arithmetic expressions this will be more interesting:
datatype exp = Const of int | Negate of exp | Add of exp * exp | Multiply of exp * expThis lesson will first consider an ML function that evaluates things of type exp, but this functino will have a different return type than similar function we worte earlier in the course. We will then consider two different approaches for defining and using this sort of “type” ofr arithmetic expressions in cRacket.
Changing how we evaluate our arithmetic expression dataype
The most obvious function to write that takes a value of the ML datatype exp defined above is one that evaluates the arithmetic expression and return the result.
fun eval_exp_old e =
case e of
Const i => i
| Negate e2 => ~ (eval_exp_old e2)
| Add(e1, e2) => (eval_exp_old e1) + (eval_exp_old e2)
| Multiply(e1,e2) => (eval_exp_old e1) * (eval_exp_old e2)The type of eval_exp_old is exp -> int. in particular, the return type is int, an ML integer that we can then add, multiply, etc. We can also write this function so that it returns an exp, so the ML type will become exp -> exp. The result of a call will have the form Const i. Callers have to check that the kind of exp returned is indeed a Const, extract the underlying data and then use the Const constructor themselves as necessary to return an *exp.
exception Error of string
fun eval_exp_new e =
let
fun get_int e =
case e of
Const i => i
| _ => raise (Error "expected Const result")
in
case e of
Const _ => e
| Negate e2 => Const (~ (get_int (eval_exp_new e2)))
| Add(e1,e2) => Const ((get_int (eval_exp_new e1)) + (get_int (eval_exp_new e2)))
| Multiply(e1,e2) => Const ((get_int (eval_exp_new e1)) * (get_int (eval_exp_new e2)))
endWe are doing this for a very good reason: soon we will be defining little languages that have multiple kinds of results. Suppose the result of a computation did not have to be a number, but could also be a boolean etc. Then our eval_exp function needds to return some sort of one-of type. A case of eval_exp will need to check that the recursive results are the right kind of value. If this check does not succeed, then the line of get_int above that raises an exception gets evaluated.
Recursive Datatypes via cRacket Lists
Before we can write an analogous cracket function, we need to define the arithmetic expressions themselvers. We need a way to construct constants, negations, addition, etc, a way to test what kind of expression we have and a way access the pieces. In cRacket, dynamic typing lets us just use lists to represent any kind of data including arithmetic expressions. One sufficient idiom is to use the first list element to indicate “what kind of thing it is” and subsequent list elements to hold the data.
;helper functions
(define (Const i) (list 'Const i))
(define (Negate e) (list 'Negate e))
(define (Add e1 e2) (list 'Add e1 e2))
(define (Multiply e1 e2) (list 'Multiply e1 e2))
;helper functions for testing
(define (Const? x) (eq? (car x) 'Const))
(define (Negate? x) (eq? (car x) 'Negate))
(define (Add? x) (eq? (car x) 'Add))
(define (Multiply? x) (eq? (car x) 'Multiply))
;helper functions for accessing
(define (Const-int e) (car (cdr e)))
(define (Negate-e e) (car (cdr e)))
(define (Add-e1 e) (car (cdr e)))
(define (Add-e2 e) (car (cdr (cdr e))))
(define (Multiply-e1 e) (car (cdr e)))
(define (Multiply-e2 e) (car (cdr (cdr e))))The ’ syntax describes a cracket symbol. SYmbols can be compared with eq? (faster). We can now write a cracket function to evaluate an arithmetic expression. It is directly analogous to the ML version.
(define (eval-exp e)
(cond [(Const? e) e]
[(Negate? e) (Const (~ (Const-int (eval-exp (Negate-e e)))))]
[(Add? e) (let ([v1 (Const-int (eval-exp (Add-e1 e)))]
[v2 (Const-int (eval-exp (Add-e2 e)))])
(Const (+ v1 v2)))]
[(Multiply? e) (let ([v1 (Const-int (eval-exp (Multiply-e1 e)))]
[v2 (Const-int (eval-exp (Multiply-e2 e)))])
(Const (* v1 v2)))]
[#t (error "eval-exp expected an exp")]Similarly we can use our helper functions to define arithmetic expressions:
(define text-exp (Multiply (Negate (Add (Const 2) (Const 2))) (Const 7)))
(define test-ans (eval-exp text-exp))Recursive Datatypes via Racket’s struct
We can also use the struct construct in cracket. Syntax looks like this:
(struct foo (bar baz quux) #:transparent)This defines a new struct called foo which is like an ML constructor. It adds to the environment functions for construcinta foo, testintand extracting the fields:
- foo is a function taking 3 arguments and returns a value that is a foo with a bar field holding the 1st argument etc.
- foo? is a function that takes one argument and returns #t for values created by calling foo.
- foo-bar extracts bar value
There are some useful attributes we can include in struct definitions to modify their behaviour: #:transparent make the fields and accessor functions visible even outside the module defining the struct. The #:mutable attribute makes all fields mutable by providing functions like set-foo-bar! etc.
(struct const (int) #:transparent)
(struct negate (e) #:transparent)
(struct add (e1 e2) #:transparent)
(struct multiply (e1 e2) #:transparent)
(define (eval-exp e)
(cond [(const? e) e]
[(negate? e) (const (~ (const-int (eval-exp (negate-e e)))))]
[(add? e) (let ([v1 (const-int (eval-exp (add-e1 e)))]
[v2 (const-int (eval-exp (add-e2 e)))])
(const (+ v1 v2)))]
[(multiply? e) (let ([v1 (const-int (eval-exp (multiply-e1 e)))]
[v2 (const-int (eval-exp (multiply-e2 e)))])
(const (* v1 v2)))]
[#t (error "eval-exp expected an exp")]))This is nearly identical to the prior version, but using structs.
Why the struct approach is better
Structs are not syntactic sugar for the list approach. The key distinction is that a struct creates a new type of value. Given
(struct add (e1 e2) #:transparent)the function add returns things that cause add? to return #t and every other type-testing function to return #f. WIth the list approach we can directly access the pieces with car and cdr. The struct approach will therefore catch errors sooner. Racket’s struct is a powerful primitive that cannot be described or defined in terms of other things like function definitions or macro definitions. It creates a new type of data.
Implementing a Programming Language in General
A typical workflow for a language implementation could look as follows:
We take a string holding the concrete syntax of a program in the language. Typically this string would be the contents of one of more files The parser ives errors if this string is not syntactically well-formed, meaning the string cannot contain a program in the language due to thins like misspelled words, parentheses etc.
If there are no serrors, the parser produces a tree that represents the program. This is called the abstract-syntax tree or AST. The type-checker will use this AST to either produce error messages or not. The AST is then passed to the rest of the implementation.
There are basically two approaches to the rest-of-the-implementation for implementing some programming language B.
- We could write an interpreter in another language A that takes
programs in B and produces answers. This program in A is called an interpreter b.
- We could write a compiler in another language A that takes programs in
B and produces equivalent programs in some other language C and then uses some pre-existing implementation for C. For compilation, we B the source language and C the target language.
For either approach, A is called the metalanguage.
Interpreter versus compiler is a feature of a particular programming-language implementation, not a feature of the programming language
Implementing a Programming Language inside Another Language
The above eval-exp function is a perfect example of an interpreter. It takes expressions built from the const constructor, all values need to be syntactically correct. cRacket in this case is the metalanguage. We skipped parsing and type-checking by using racket’s constructors to directly create ASTs:
(negate (add (const 2) (const 2)))in itself is already an AST.
Assumptions and Non-assumptions about legal ASTs
There are different ways an AST can be wrong:
(struct const (int) #:transparent) ; int should hold a number
(struct negate (e1) #:transparent) ; e1 should hold an exp
(struct add (e1 e2) #:transparent) ; e1, e2 should hold exp
(struct multiply (e1 e2) #:transparent) ; e1, e2 should hold exp
(struct bool (b) #:transparent) ; b should hold #t or #f
(struct if-then-else (e1 e2 e3) #:transparent) ; e1, e2, e3 should hold exp
(struct eq-num (e1 e2) #:transparent) ; e1, e2 should hold expThe new features (bool, cond and a construct for comparing) could work like this: a result of evaluating an expression could now be:
- an integer (const 17)
- a bool (bool true)
- non-existent, because of “run-time type-error” trying to treat a bool as int or vice versa.
The interpreter should check if the expressions to be evaluated have the right type.
Interpreters for Languages with Variables need Environments
Since expressions can contain variables, evaluating them requires an environment that maps variables to values. So an interpreter for a language with variables needs a recursive helper function that takes an expressen and an environment and produces a value. The representation of the environment is part of the interpreter’s implementation in the metalanguage, not part of the abstract syntax of the language. With cracket as our metalanguage, a simple association list holding pairs of strings (variable names) and values (what the variables are bound to) can suffice. Given an environment, interpreter uses it differently:
- To evaluate a variable expression, it looks up the variable’s name (i.e. the string) in the environment
- To evaluate most subexpressions, such as the subexpressions of an addition operation, the interpreter passes to the recursive calls the same environment that was passed for evaluating the outer expression.
- To evaluate things like the body of a let-expression, the interpreter passes to the recursive call a slightly different environment, such as the environment it was passed with one more binding (i.e. pair of string and value) in it.
To evaluate an entire program, we just call our recursive helper function that takes an environment with the program and a suitable initial environment (such as the empty environment) which has no binding in it.
Implementing Closures
To implement a language with function closures and lexical scope, our interpreter needs to remember the environment that was current when the function was defined so it can use this environment instead of the caller’s environment when the function is called. The “trick” is rather direct: we literally create a small data structure called a closure that includes the env along with the function itself. It is this pair (the closure) that is the result of interpreting a function.
We also need to implement function calls. A call has two expressions e1 and e2 for what would look like e1 e2 in ML or (e1 e2) in cracket. We evaluate a call as follows:
- Evaluate e1 using the current env. Result should be a closure
- Evaluate e2 using the current env. Result will be argument to the closure
- Evaluate the body of the code part of the closure using the env part of the closure extended with the argument of the code part mapping to the argument at the call-site.
This really is how interpreters implement closures.
Defining “Macros” via functions in the metalanguage
When implementing an interpreter or compiler, it is essential to keep separate what is in the language being implemented and what is in the language used for doing the implementation (the metalanguage). For example, eval-exp is a cracket function that takes an arithmetic-expresseion-language expression and produces an arithmetic-expression-language value. So e.g. an expresion would never include a use of eval-exp or a cracket addition expression. But since we are writing our to-be-evaluated programs in cRacket, we can use cracket helper functions to help us create these programs. Doing so is basically defining macros for our language using cracket functions as the macro language. Here is an example:
(define (double e) ;takes language-implemented syntax and produces language-implemented syntax
(multiply e (const 2)))double is a cracket function that takes the syntax for an arithmetic expression and produces the syntax for an arithmetic expression. Calling double produces abstract syntax in our language, much like macro expansion. E.g.
(negate (double (negate (const 4))))produces
(negate (multiply (negate (const 4)) (const 2)))This “macro” double does not evaluate the program in any way: we produce abstract syntax that can be evaluated. Being able to do this is an dvantage of “embedding” our little language inside the the cracket metalanguage. The same technique works regardless of the choice metalanguage. Here is a different “macro” that is interesting in 2 ways. First the argument is a cracket list of language-implemented expresions (syntax). Second, the “macro” is recursive, calling itself once for each element in the argument list:
(define (list-product es)
(if (null? es)
(const 1)
(multiply (car es) (list-product (cdr es)))))DONE HW 5:
- State “DONE” from
Instructions
Overview: This homework has to do with mupl (a Made Up Programming Language). mupl programs are written directly in cRacket by using the constructors defined by the structs defined at the beginning of hw5.rkt. This is the definition of mupl’s syntax:• If s is a cRacket string, then (var s) is a mupl expression (a variable use).
- If n is a cRacket integer, then (int n) is a mupl expression (a constant).
- If e 1 and e 2 are mupl expressions, then (add e 1 e 2 ) is a mupl expression (an addition).
- If s 1 and s 2 are cRacket strings and e is a mupl expression, then (fun s 1 s 2 e) is a mupl expression (a function). In e, s 1 is bound to the function itself (for recursion) and s 2 is bound to the (one) argument. Also, (fun #f s 2 e) is allowed for anonymous nonrecursive functions.
- If e 1 , e 2 , and e 3 , and e 4 are mupl expressions, then (ifgreater e 1 e 2 e 3 e 4 ) is a mupl expression. It is a conditional where the result is e 3 if e 1 is strictly greater than e 2 else the result is e 4 . Only one of e 3 and e 4 is evaluated.
- If e 1 and e 2 are mupl expressions, then (call e 1 e 2 ) is a mupl expression (a function call).
- If s is a cRacket string and e 1 and e 2 are mupl expressions, then (mlet s e 1 e 2 ) is a mupl expression (a let expression where the value resulting e 1 is bound to s in the evaluation of e 2 ).
- If e 1 and e 2 are mupl expressions, then (apair e 1 e 2 ) is a mupl expression (a pair-creator).
- If e 1 is a mupl expression, then (fst e 1 ) is a mupl expression (getting the first part of a pair).
- If e 1 is a mupl expression, then (snd e 1 ) is a mupl expression (getting the second part of a pair).
- (aunit) is a mupl expression (holding no data, much like () in ML or null in cRacket). Notice (aunit) is a mupl expression, but aunit is not.
- If e 1 is a mupl expression, then (isaunit e 1 ) is a mupl expression (testing for (aunit)).
- (closure env f ) is a mupl value where f is mupl function (an expression made from fun) and env is an environment mapping varia A mupl value is a mupl integer constant, a mupl closure, a mupl aunit, or a mupl pair of mupl values. Similar to cRacket, we can build list values out of nested pair values that end with a mupl aunit. Such a mupl value is called a mupl list. You should assume mupl programs are syntactically correct (e.g., do not worry about wrong things like (int “hi”) or (int (int 37)). But do not assume mupl programs are free of type errors like (add (aunit) (int 7)) or (fst (int 7)). Warning: What makes this assignment challenging is that you have to understand mupl well and debugging an interpreter is an acquired skill.
Problems & Solutions:
;; Programming Languages, Homework 5
#lang cracket
(provide (all-defined-out)) ;; so we can put tests in a second file
;; definition of structures for MUPL programs - Do NOT change
(struct var (string) #:transparent) ;; a variable, e.g., (var "foo")
(struct int (num) #:transparent) ;; a constant number, e.g., (int 17)
(struct add (e1 e2) #:transparent) ;; add two expressions
(struct ifgreater (e1 e2 e3 e4) #:transparent) ;; if e1 > e2 then e3 else e4
(struct fun (nameopt formal body) #:transparent) ;; a recursive(?) 1-argument function
(struct call (funexp actual) #:transparent) ;; function call
(struct mlet (var e body) #:transparent) ;; a local binding (let var = e in body)
(struct apair (e1 e2) #:transparent) ;; make a new pair
(struct fst (e) #:transparent) ;; get first part of a pair
(struct snd (e) #:transparent) ;; get second part of a pair
(struct aunit () #:transparent) ;; unit value -- good for ending a list
(struct isaunit (e) #:transparent) ;; evaluate to 1 if e is unit else 0
;; a closure is not in "source" programs but /is/ a MUPL value; it is what functions evaluate to
(struct closure (env fun) #:transparent)Warm-Up: (a) Write a cRacket function racketlist->mupllist that takes a cRacket list (presumably of mupl values but that will not affect your solution) and produces an analogous mupl list with the same elements in the same order.
(define (racketlist->mupllist rlst) (if (null? rlst) (aunit) (apair (car rlst) (racketlist->mupllist (cdr rlst)))))(b) Write a cRacket function mupllist->racketlist that takes a mupl list (presumably of mupl values but that will not affect your solution) and produces an analogous cRacket list (of mupl values) with the same elements in the same order.
(define (mupllist->racketlist mlst) (if (aunit? mlst) null (cons (apair-e1 mlst) (mupllist->racketlist (apair-e2 mlst)))))Implementing the mupl Language: Write a mupl interpreter, i.e., a cRacket function eval-exp that takes a mupl expression e and either returns the mupl value that e evaluates to under the empty environment or calls cRacket’s error if evaluation encounters a run-time mupl type error or unbound mupl variable. A mupl expression is evaluated under an environment (for evaluating variables, as usual). In your interpreter, use a cRacket list of cRacket pairs to represent this environment (which is initially empty) so that you can use without modification the provided envlookup function. Here is a description of the semantics of mupl expressions: • All values (including closures) evaluate to themselves. For example, (eval-exp (int 17)) would return (int 17), not 17. • A variable evaluates to the value associated with it in the environment. • An addition evaluates its subexpressions and assuming they both produce integers, produces the integer that is their sum. (Note this case is done for you to get you pointed in the right direction.) • Functions are lexically scoped: A function evaluates to a closure holding the function and the current environment. • An ifgreater evaluates its first two subexpressions to values v 1 and v 2 respectively. If both values are integers, it evaluates its third subexpression if v 1 is a strictly greater integer than v 2 else it evaluates its fourth subexpression. • An mlet expression evaluates its first expression to a value v. Then it evaluates the second expression to a value, in an environment extended to map the name in the mlet expression to v. • A call evaluates its first and second subexpressions to values. If the first is not a closure, it is an error. Else, it evaluates the closure’s function’s body in the closure’s environment extended to map the function’s name to the closure (unless the name field is #f) and the function’s argument-name (i.e., the parameter name) to the result of the second subexpression. • A pair expression evaluates its two subexpressions and produces a (new) pair holding the results. • A fst expression evaluates its subexpression. If the result for the subexpression is a pair, then the result for the fst expression is the e1 field in the pair. • A snd expression evaluates its subexpression. If the result for the subexpression is a pair, then the result for the snd expression is the e2 field in the pair. • An isaunit expression evaluates its subexpression. If the result is an aunit expression, then the result for the isaunit expression is the mupl value (int 1), else the result is the mupl value (int 0).
;; Problem 2 ;; lookup a variable in an environment ;; Do NOT change this function (define (envlookup env str) (cond [(null? env) (error "unbound variable during evaluation" str)] [(equal? (car (car env)) str) (cdr (car env))] [#t (envlookup (cdr env) str)])) ;; Do NOT change the two cases given to you. ;; DO add more cases for other kinds of MUPL expressions. ;; We will test eval-under-env by calling it directly even though ;; "in real life" it would be a helper function of eval-exp. (define (eval-under-env e env) (cond [(var? e) (envlookup env (var-string e))] [(add? e) (let ([v1 (eval-under-env (add-e1 e) env)] [v2 (eval-under-env (add-e2 e) env)]) (if (and (int? v1) (int? v2)) (int (+ (int-num v1) (int-num v2))) (error "MUPL addition applied to non-number")))] ;; CHANGE add more cases here ;; primitives [(int? e) e] [(aunit? e) e] [(closure? e) e] ;; function [(fun? e) (closure? env e)] [(mlet? e) (eval-under-env (mlet-body e) (cons (cons (mlet-var e) (eval-under-env (mlet-e e) env)) env))] [(apair? e) (apair (eval-under-env (apair-e1 e) env) (eval-under-env (apair-e2 e) env))] ;; fst and snd [(fst? e) (let ([result (eval-under-env (fst-e e) env)]) (if (apair? result) (apair-e1 result) (error "MUPL fst applied to non-apair")))] [(snd? e) (let ([result (eval-under-env (snd-e e) env)]) (if (apair? result) (apair-e2 result) (error "MUPL snd applied to non-apair")))] ;; ifgreater [(ifgreater? e) (let ([v1 (eval-under-env (ifgreater-e1 e) env)] [v2 (eval-under-env (ifgreater-e2 e) env)]) (if (and (int? v1) (int? v2)) (if (> (int-num v1) (int-num v2)) (eval-under-env (ifgreater-e3 e)) (eval-under-env (ifgreater-e3 e))) (error "MUPL ifgreater applied with non-number")))] ;; ifaunit [(ifaunit? e) (let ([result (eval-under-env (ifunit-e e) env)]) (if (aunit? result) 1 0))] ;; call [(call? e) ; first evaluate closure (let ([currentclosure (eval-under-env (call-funexp e) env)]) ; if this is not a closure, call an error (if (closure? currentclosure) ; then clause (let ([localenv (closure-env currentclosure)] [funexp (closure-fun currentclosure)] [param (eval-under-env (call-actual e) env)]) (eval-under-env (fun-body funexp) (if (fun-nameopt funexp) (cons (cons (fun-nameopt funexp) currentclosure) ;with name bound to whole closure (cons (cons (fun-formal funexp) param) localenv)) ;and argument bound to parameter (cons (cons (fun-formal funexp) param) localenv)))) (error "MUPL call apllied to non-closure")))] [#t (error (format "bad MUPL expression: ~v" e))])) ;; Do NOT change (define (eval-exp e) (eval-under-env e null))Expanding the Language mupl is a small language, but we can write cRacket functions that act like mupl macros so that users of these functions feel like mupl is larger. The cRacket functions produce mupl expressions that could then be put inside larger mupl expressions or passed to eval-exp. In implementing these cRacket functions, do not use closure (which is used only internally in eval-exp). Also do not use eval-exp (we are creating a program, not running it). (a) Write a cRacket function ifaunit that takes three mupl expressions e 1 , e 2 , and e 3 . It returns a mupl expression that when run evaluates e 1 and if the result is mupl’s aunit then it evaluates e 2 and that is the overall result, else it evaluates e 3 and that is the overall result. Sample solution: 1 line.
(define (ifaunit e1 e2 e3) (ifgreater (isaunit e1) (int 0) e2 e3))(b) Write a cRacket function mlet* that takes a cRacket list of cRacket pairs ’((s 1 . e 1 ) . . . (s i . e i ) . . . (s n . e n )) and a final mupl expression e n+1 . In each pair, assume s i is a cRacket string and e i is a mupl expression. mlet* returns a mupl expression whose value is e n+1 evaluated in an environment where each s i is a variable bound to the result of evaluating the corresponding e i for 1 ≤ i ≤ n. The bindings are done sequentially, so that each e i is evaluated in an environment where s 1 through s i−1 have been previously bound to the values e 1 through e i−1 .
(define (mlet* lstlst e2) (if (null? lstlst) e2 (mlet (car (car lstlst)) (cdr (car lstlst)) (mlet* (cdr lstlst) e2))))(c) Write a cRacket function ifeq that takes four mupl expressions e 1 , e 2 , e 3 , and e 4 and returns a mupl expression that acts like ifgreater except e 3 is evaluated if and only if e 1 and e 2 are equal integers. Assume none of the arguments to ifeq use the mupl variables _x or _y. Use this assumption so that when an expression returned from ifeq is evaluated, e 1 and e 2 are evaluated exactly once each.
(define (ifeq e1 e2 e3) (mlet* (list (cons "_x" e1) (cons "_y" e2)) (ifgreater (var "_x") (var "_y") e4 (ifgreater (var "_y") (var "_x") e4 e3))))Using the language We can write mupl expressions directly in cRacket using the constructors for the structs and (for convenience) the functions we wrote in the previous problem. (a) Bind to the cRacket variable mupl-map a mupl function that acts like map (as we used extensively in ML). Your function should be curried: it should take a mupl function and return a mupl function that takes a mupl list and applies the function to every element of the list returning a new mupl list. Recall a mupl list is aunit or a pair where the second component is a mupl list.
(define mupl-map (fun #f "function" (fun "mapfunc" "mupllst" (ifaunit (var "mupllst") (aunit) (apair (call (var "function") (fst (var "mupllst"))) (call (var "mapfunc") (snd (var "mupllst"))))))))(b) Bind to the cRacket variable mupl-mapAddN a mupl function that takes an mupl integer i and returns a mupl function that takes a mupl list of mupl integers and returns a new mupl list of mupl integers that adds i to every element of the list. Use mupl-map (a use of mlet is given to you to make this easier).
(define mupl-mapAddN (mlet "map" mupl-map (fun #f "increment" (call (var "map") (fun #f "curnum" (add (var "increment") (var "curnum")))))))
DONE Week 3
- State “DONE” from
DONE Reading
- State “DONE” from
Soundness and Completeness
A type system is sound if it never accepts a program that, when run with some input, does X. A type system is complete if it never rejects a program that, no matter what input it is run with, will not do X.
Soundness prevents false negatives and completeness prevents fallse positives. A sound logic proves only true things. A complete logic proves all true things. Type systems are not complete because for almost anything you might like to check statically, it is impossible to implement a static checker that given any program in your language (a) always terminates (b) is sound and (c) is complete.
The impossibility result is the idea of undecidability at the heart of the study of the theory of computation. Nontrivial properties of programs are undecidable.
Weak Typing
Suppose a type system is unsound for some property X. To be safe the implementation sjould in some cases perform dynamic checks to prevent X from happening and the language definition shold allow that these checks might fail at run-time.
An alternativ is to say the it is the programmer’s fault if X hapens and the language definition does not have to check. If X happens, then the running program can do anything: crash, corrupt data, produce the wrong anser, etc. If a language is implemented like this, it is called weakly typed. C and C++ are well-known weakly typed langauges. This has performance issues.
Advantages and Disadvantages of Static Checking
See pages 6 through 11.
DONE Exercises/Quiz
- State “DONE” from