CS131: Programming Languages
DIS 1D Week 9 Winter 2022
Office Hours:
Copyright By PowCoder代写 加微信 powcoder
Tuesday 8-9pm, Friday 9:30-10:30am
Zoom Link on BruinLearn (Same as discussion)
Discussion Section: 1D, Fridays 2:00 – 3:50pm
Course Announcement
• Project due: Next Monday, March 7
• HW6 due: Next Friday, March 11
– No submission allowed after March 11 for both (No late submission for HW6!)
• Please remember to fill the course evaluation
• Homework 6 • Misc Topics
Homework #6
Homework #6: Overview
• Application: A certain kind of embedded software in IoT system
– Languages we have learned are either not suitable for the task (e.g. Java, Python), or deemed potentially unsafe (C/C++)
• Task: Survey one of the 3 (low-level) new programming languages – Crystal, Go, Rust
– Depending on your UID
• Write a report about their feasibility of the application • No actual coding required
Homework #6: Application background
• Autonomous heating, ventilation, and air conditioning (HVAC) system
– “Human Embodied Autonomous Thermostat”
– Inexpensive cameras are used to monitor people’s skin temperature, getting the level of confort.
– The data is used to automatically control the HVAC system to maximize occupants’ confort, while potentially saving power.
– More info in homework description and the reference links listed there.
Sensing Data (via WiFi)
Homework #6: Target Application
• The focus of this homework: the software running on cameras
– Emphasis: Security
– Common solutions for embedded systems (C/C++) often contains vulnerabilities that are prone to attacks
• Properties of an ideal alternative programming language:
– Camera software should be cleanly written and easy to audit
– The software should be freestanding, no seperate OS
– The software should be as simple and stripped-down as possible
– The software should be capable of interfacing to low-level hardware devices, such as camera, network interfaces
Homework #6: Tasks
• Do research on one of the proposed languages, and their support SW.
– Examine the language and system documentation to help decide whether it would be effective, and support the proposed application well.
• Evaluate the features of proposed languages, and write an executive summary.
– Strengths and weakness of the languages, anticipated problems
– Focus on the technology’s effect on security, ease of use, flexibility, …
Homework #6: Submission Format
• Submit the report in a single pdf file
– Use font size of at least 10pt, at most 2 pages.
– You can put references and appendices in later pages, if you can’t go under the page limit. Appendices can contain any source code or diagrams that don’t otherwise fit.
Tail Recursion
• What is Tail Recursion?
• Which of the following functions is tail recursive?
float sum(struct list_t *a) {
return a->x + sum(a->next);
float sum(struct list_t *a,
float acc) {
return sum(a->next, acc+a->x);
return acc; }
struct list_t { float x;
struct list_t *next;
Tail Recursion
• What is tail recursion?
– A recursive function is tail recursive when recursive call is the last thing executed by the function.
• Why does it matter?
– Compiler optimization: when the recursion is the last action, there’s no need to save the current stack frame
– When the tail recursion is the only recursive call, compiler can simply optimize the recursive function into a loop.
How to draw a syntax diagram?
• Convert the following grammar (in HW2 style) into a syntax diagram:
let awkish_grammar =
(Expr, function ->
[[N Term; N BinOp; N Expr];
[[N Num]; [N Lvalue]; [N Incrop; N Lvalue]; [N Lvalue; N Incrop]; [T “(”; N Expr; T “)”]]
| Lvalue -> [[T “$”; N Expr]]
| Incrop -> [[T “++”]; [T “–”]]
| BinOp -> [[T “+”]; [T “-”]]
| Num -> [[T “0”]; [T “1”]]
The role of a parser
• Will the grammar on the previous page have difficulty when handling the input “$0+++1”? Why?
– What is the input you should provide to the grammar? – Who does that missing step?
• Answer: The input string needs to go through tokenizer (lexer) before it goes into parser.
– Tokenizer is not controlled by grammar, and often uses greedy algorithm
– Considering HW2, the input to the parser will be [T “$”; T “0”; T “++”; T “+”, T “1”], which won’t have any ambiguity.
Scheme: Named Let
• Named let: Define a local function, and immediately call it with the specified arguments. Can be recusive.
(define (rev-list l)
([rev-helper
(lambda (acc l)
(null? l) acc (rev-helper
(cons (car l) acc)
(cdr l))))]) (rev-helper (list) l)))
(define (rev-list l)
(let rev-helper
((acc (list)) (l l))
(if (null? l)
acc (rev-helper
(cons (car l) acc)
(cdr l)))))
Continuation
• What does continuation in Scheme do?
– What does it take to implement continuation?
(define product
(lambda (ls)
(lambda (break)
(let f ([ls ls]) (cond
[(null? ls) 1]
[(= (car ls) 0) (break 0)]
[else (* (car ls) (f (cdr ls)))]))))))
Continuation
• Do other languages have continuation-like primitive?
– C has setjmp()/longjmp().
– API convention a little bit different, but essentially doing the same thing.
• What is the difference between Scheme’s continuation and C’s setjmp()/longjmp() beyond API convention?
– Scheme’s continuation can be used even after the call/cc returns, but longjmp cannot transfer to places where the caller of setjmp has returned.\
– This means one cannot implement lwp-list in class with C’s setjmp/longjmp
Activation Record in Functional Programming
• In C/C++, activation record is allocated on stack, and get destroyed when the function returns
• What about functional programming languages?
– The activation record has to be allocated on heap, because it can be used later after the function returns.
Side effect, only for this demo Don’t use in HW/exam!
(fun () -> cnt := !cnt + 1)
let add = fun x -> (fun y -> x + y) let add_one = add 1
add_one 2 (* Returns 1+2 = 3 *)
let new_counter () = let cnt = ref 0
in (fun () -> !cnt),
let (get_x, inc_x) = new_counter () get_x () (* Returns 0 *)
get_x () (* Returns 1 *)
Questions?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com