CS 131: Programming Languages Week 7 : Scheme
Khanh 1A Winter 2022
• Office Hours: Thursdays 11:00 AM – 1:00PM
Copyright By PowCoder代写 加微信 powcoder
Online, Zoom ID 5846625614 (link on bruinlearn)
• Discussion Section 1A: Fridays 10:00 AM – 11:50 AM
Course Announcement
• HW4 due: Today (Feb. 18), 11:55pm – Cutoff time one week later
• HW5 due Next Friday (Feb. 25)
• Homeworks should be submitted on bruinlearn, under “Assignments”
• Homework #5
Scheme Introduction
• Functional programming language
• Part of LISP programming language family
– LISP developed in 1958 by Carthy
– Pioneered many new concepts: GC, recursion, dynamic typing, etc. – Important feature: Program code as a (list-like) data structure
• Scheme: a dialect of LISP
– Created in 1970s at MIT AI Lab – Historically popular in academia – Designed to be minimal
• In Homework 5, we will use Racket – Racket: LISP dialect based on Scheme
• You can use DrRacket IDE or any text editor
– DrRacket is a very minimal IDE, text editor + interactive environment
– It can make your life a little bit easier • Simple debugger, matching parenthesis
• We suggest using the latest version
– Also available on SEASnet servers: lnxsrv11/13/15
Hello world
• You can also directly use racket interactive interpreter or DrRacket GUI
Command line:
$ racket helloworld.ss
Hello, world!
helloworld.ss:
#lang racket
(display “Hello, world!\n”)
Basic syntax
• Comments
– Semi-colon (;) starts a single-line comment – #| Block comment |#
– 1, 1/2, 3.14, 6.02e+23
– “Hello, world!\n”
• Booleans – #t, #f
Identifier
• Scheme allows nearly anything in identifiers
• For example, any of the following can be used:
a-very-long-identifier
a-b-c+1+2+3
• Forbidden characters: ( ) [ ] { } ” , ‘ ` ; # | \
Function calls
• In scheme, all the code are written as s-expressions, or parenthesized lists. (), [], {} are identical, () is used in most cases
• For function calls, the name of function appears in the first element, followed by arguments.
> (display “Hello”)
> (+ 1 2) 3
> (+ 1 2 (- 4 3)) 4
> (+ 1 2 3 4)
; + and * can take more ; than 2 arguments
> (/ (+ 1/3 1/6) 2) 1/4
Function calls: Exercises
• Convert the following expression to Scheme
1. 3.2 * (1 – 0.3) + -8.7
2. (2/3 + 5/9) ÷ (3/11 – 7/4)
• Key: Convert infix expressions to prefix ones – Pay attention to priority!
• Answers:
– (+ (* 3.2 (- 1 0.3)) -8.7)
– (/ (+ 2/3 5/9) (- 3/11 7/4))
Definitions
• Variables and functions can be defined using define keyword: – This is not function call, but rather “syntactic form”.
– But they follow the same syntax.
(define pi 3.14)
(define (print-name name)
(display (string-append “Hello, ” name)))
> (print-name “Steve”)
Hello, Steve
Function Naming Convensions
• Functions that return boolean value usually end with ‘?’ – e.g. equal?, zero?
– Except arithmentic comparisons (e.g. <, >)
• Functions that case side effects usually end with ‘!’ – e.g. set!
– Do not use these functions in the homework
Lambda Functions • Define anonymous function with lambda keyword
> (lambda (a b c) (+ a b c))
#
Local bindings
• Let keyword defines new variables inside a smaller scope • syntax (let () expr)
(define (sum-squares a b)
(let ([a-squared (* a a)]
[b-squared (* b b)])
(+ a-squared b-squared)))
> (sum-squares 5 6)
Local bindings
• Local function binding can be created with let + lambda
– Note: when creating local recursive function, use “letrec” instead of “let” (except when you are using “named let”)
(define (rev-list l)
([rev-helper
(lambda (acc l)
(null? l) acc (rev-helper
(cons (car l) acc)
(cdr l))))]) (rev-helper (list) l)))
let rev_list l =
let rec rev_helper acc = function
| h::t -> rev_helper (h::acc) t
in rev_helper [] l;;
Comparison operators: Equality
• Three comparisons for equality – (= 1 2) checks if numbers are equal
– (equal? (list 1 2 3) (list 1 2 3)) checks if values are equal (recursively)
– (eq? a a) checks if object references are equal (rarely needed, especially for programs without side effect)
Comparison operators: Inequality
• Comparison operators (<, >, <=, >=) – They can take multiple arguments
> (< 1 2 3)
> (< 1 3 2)
Checking types
• Scheme provides functions to check types, for example: – Works for any basic type:
> (number? 5)
> (string? “My string”)
> (list? (list 1 2 3 4))
> (pair? (cons 1 2))
Conditionals: If • Syntax: (if
> (if (equal? 1 2) “Equal” “Not equal”)
“Not equal”
> (if (< 1 2) #t #f)
Conditionals: Cond
• Syntax: (cond [
> (cond [(boolean? 1) “One is a boolean value”] [(boolean? #t) “#t is a boolean value”] [(boolean? #f) “#f is a boolean value”])
“#t is a boolean value”
• Note: Compiler will not check whether conditions are exhaustive – Returns nothing if none of the condition is true
• Similar to OCaml and Prolog, Scheme use singly-linked list
• Creating a list: (list 1 2 3) or ‘(1 2 3)
• Accessing head: (car my-list) or (first my-list)
• Accessing tail: (cdr my-list) or (rest my-list)
• Empty list ‘() or empty
– Checking for an empty list: (null? ‘()) -> #t
> (define my-list (list 1 2 3)) > (car my-list)
> (first my-list)
> (cdr my-list)
> (rest my-list)
> (car (cdr (cdr my-list)))
> (caddr my-list)
• Much like ‘::’ in OCaml, cons keyword in Scheme can construct a new list by adding an element to the head of another list
• Example: constructing list from individual cells:
> (cons 1 (cons 2 (cons 3 ‘())))
List operations
– (map (lambda (x) (+ x 1)) ‘(1 2 3)) -> ‘(2 3 4)
– (filter (lambda (x) (> x 2)) ‘(1 2 3 4)) -> ‘(3 4)
• foldl/foldr
– (foldl(lambda(xacc)(+xacc))0′(1234))->10
– (sort ‘(5 4 3 2 1) <) -> ‘(1 2 3 4 5)
– (length ‘(1 2 3 4 5)) -> 5
– (reverse ‘(1 2 3 4 5)) -> ‘(5 4 3 2 1 )
cons: A deeper look
• cons constructs a “cons cell” with two slots: car and cdr
• When car is a value, and cdr is (points to) a list, then cons gives us a normal list
> (cons 1 (list 2 3))
cons: A deeper look
• In fact, cons cell can hold different data types, allowing for more flexible data structures
– A simple example (this is called “pair”):
– A more complicated example
> (cons 3 4)
> (cons (cons 1 ‘()) (cons 2 (cons (cons 3 4) (cons 5 ‘()))))
‘((1) 2 (3 . 4) 5)
Lists: Exercises
• What do the following expressions evaluate to:
1. (car (cons 1 (list 2 3)))
2. (cons (list 1 2) (list 3 4))
3. (cons (car (list 1 2 3)) (cdr (list 4 5 6)))
Lists: Exercises
• What do the following expressions evaluate to:
1. (car (cons 1 (list 2 3)))
2. (cons (list 1 2) (list 3 4))
3. (cons (car (list 1 2 3)) (cdr (list 4 5 6)))
• Unordered key-value store
• Nearly constant time access/update
(define first-hashmap (hash-set (hash) “a” 5))
(define second-hashmap (hash-set first-hashmap “b” 7))
> (hash-ref second-hashmap “b” “Not found”)
> (hash-ref first-hashmap “b” “Not found”) “Not found”
Programs as Data
• Notice that the list structure looks the same as Scheme code itself:
‘(1 2 (3 (4 5) 6))
• “’” (quote) makes the following expression a list of symbols – Contents are not evaluated
(define my-program ‘(display “Hello, World!\n”))
> my-program
‘(display “Hello, World!\n”) > (eval my-program)
Hello, World!
Eval: Namespaces
• In the interpreter, eval works without defining a namespace • In your code file, it has to be defined:
(define ns (make-base-namespace)) (eval my-program ns)
Program as Data
• Inspecting quoted program symbols with normal list operations:
> (define my-program ‘(display (+ 1 2))) > (eval my-program)
> (car my-program)
> (cdr my-program)
‘((+ 1 2))
> (car (car (cdr my-program)))
• Note: ‘() is a shorthand for (quote (
))
Program as Data
• Quote (‘) gives you a list of symbols
• Quasiquote (`) and unquote (,) allow you to combine symbols and evaluated code:
> (quasiquote (my-function (unquote (+ 1 2))))
‘(my-function 3)
; equivalent form
> `(my-function ,(+ 1 2))
‘(my-function 3)
Program as Data: Example
• For debugging purposes, we’d like to print the values that are added together within a certain code
• We want to replace all the “+” operations that appears in the code with our own print-and-add procedure
(define (print-and-add x y) (begin
(display (string-append
(number->string x) “” (number->string y) “\n”))
(+ 1 (+ 2 (+ 3 (+ 4 5))))
Should print: +45
Program as Data: Exercise
– Iterate through list of program symbols recursively – When we see a ‘+, replace with ‘print-and-add
(define (debug program)
(cond [(list? program) (map debug program)]
[(equal? program ‘+) ‘print-and-add]
[else program]))
(debug ‘(+ 1 (+ 2 (+ 3 (+ 4 5))))) ‘(print-and-add 1 (print-and-add 2 (print-and-add
3 (print-and-add 4 5))))
Program as Data: Example
Task: Create a function transform-if that does the following transformation on a piece of program:
• For all if construct inside
– Do a negation of the guard
– Swap the then and else branches
– e.g. (if (> x 3) (+ y 5) 6) will become (if (not (> x 3)) 6 (+ y 5))
Program as Data: Example – Pay attention to the usage of quasiquote(`) and unquote(,)
• Solution:
(define (transform-if p)
(if (and (list? p) (not (null? p)))
(let ([tp (map transform-if p)]) (if (equal? (car p) ‘if)
`(if (not ,(cadr tp))
,(cadddr tp)
,(caddr tp)) tp))
Homework #5
Homework #5
• Goal: Write a program to detect similarities between two Scheme programs, i.e. “plagiarism checker”
Homework #5
• expr-compare function takes two expressions and returns a new expression with similar parts combined
• Variable % defines which program we want to execute
(expr-compare 12 12)
(expr-compare 12 20)
-> (if % 12 20)
(expr-compare ‘a ‘(cons a b))
-> (if % a (cons a b))
Homework #5
• If the difference are deeper inside the program, combine outer parts
(expr-compare ‘(cons a b) ‘(cons a c))
-> (cons a (if % b c))
(expr-compare ‘(cons (cons a b) (cons b c)) ‘(cons (cons a c) (cons a c)))
-> (cons (cons a (if % b c)) (cons (if % b a) c))
Homework #5
• In some cases, similar parts cannot be combined
(expr-compare ‘(list) ‘(list a))
-> (if % (list) (list a)) # empty list is different DON’T do this: (if list % () a)
(expr-compare ‘(quote (a b)) ‘(quote (a c)))
-> (if % ‘(a b) ‘(a c)) # comparison stops at “quote”
(expr-compare ‘(if x y z) ‘(g x y z))
-> (if % (if x y z) (g x y z)) # “if” is not a function DON’T do this: (if % (if) (g) x y z)
Homework #5 • Lambda and λ should be combined:
(expr-compare ‘((lambda (a) (f a)) 1) ‘((λ (a) (g a)) 2))
-> ((λ (a) ((if % f g) a)) (if % 1 2))
– When both “lambda” and “λ” appears, use “λ” after combination
– Two “lambda”s cannot be combined into “λ”
– Getting the lambda symbol: (define LAMBDA (string->symbol “\u03BB”)) – Or, you can get it in DrRacket (Insert > Insert λ, or press Ctrl-\)
Homework #5
• If we declare new variables with different names, combine them:
(expr-compare ‘((lambda (a) a) c) ‘((lambda (b) b) d)) -> ((lambda (a!b) a!b) (if % c d))
• Need to replace all occurrences of these variables within the lambda expression
• Hint: Hash map might be useful to keep track of renamed variables
Homework #5
• Testing script: https://github.com/CS131-TA-team/hw5-grading-script (Not exhaustive)
• Put #lang racket
and #(provide (all-defined-out) on top of your file
Resources • Download Racket (Includes DrRacket IDE):
– https://racket-lang.org/download/ • The Racket Guide:
– https://docs.racket-lang.org/guide/index.html
• The Scheme Programming Language (Dybvig)
– https://www.scheme.com/tspl4/
Questions?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com