Without let bindings
(define (max-num lst)
(cond [(empty? lst) (error "empty")]
[(= (length lst) 1) (car lst)]
[else (if (> (car lst) (max-num (cdr lst)))
(car lst)
(max-num (cdr lst)))]))With let bindings
(define (max-num lst)
(cond [(empty? lst) (error "empty")]
[(= (length lst) 1) (car lst)]
[else (let ((head (car lst))
(max-tail (max-num (cdr lst))))
(if (> head max-tail)
head
max-tail))]))With helper method
(define max-num (lst)
(let-rec ([my-max (lambda (curr-max lst)
(cond [((empty? lst) curr-max)]
[else (if (> (car lst) curr-max)
(my-max (car lst) (cdr-lst))
(my-max curr-max (cdr lst)))]))])
(if (empty? lst)
(error "empty")
(my-max (car lst (cdr lst))))))(define (max-num lst)
(cond [(empty? lst) (error "empty")]
[(= (length lst) 1) (car lst)]
;; [else (if ((> car lst) (cadr lst))
;; (max-num (cons (car lst (cddr lst))))
;; (max-num (cons (cadr lst (cddr lst)))))]
[else (max-num (cons (if (> (car lst) (cadr lst)) (car lst) (cadr lst))
(cddr lst)))]
))Base code
(define (fizzbuzz n)
(print (fizzbuzz1 1 n)))(define (fizzbuzz1 i n)
(if (= i n)
""
(string-append (cond [(and (is-divisible-by i 3) (is-divisible-by 5)) "fizzbuzz"]
[(and (is-divisible-by i 3) "fizz")]
[(and (is-divisible-by i 5) "buzz")]
[else i])
" "
(fizzbuzz1 (+ i 1) n))))- Procedures and functions clearly distinguish incoming values (parameters) from outgoing values (results).
- e.g., C/C++ results may be a parameter that you pass by reference (pointer)
- (Purely functional) No assignment
- (Purely functional) No loops
- Value of a function depends only on the value of its parameters.
(define (sum-list lst)
(cond [(empty? lst) 0]
[(else (+ (car lst) (sum-lst (cdr lst))))]))
(define (mult-list lst)
(cond [(empty? lst) 1]
[(else (+ (car lst) (mult-list (cdr lst))))]))(define (combine-lst fn acc lst)
(cond [(empty? lst) acc]
[else (combine-lst fn
(fn acc (car lst))
(cdr lst))]))
(combine-lst + 0 '(1 2 3 4))
(foldl + 0 '(1 2 3 4))
(foldl * 1 '(1 2 3 4))(define (add-one-to-each-elem lst)
(cond [(empty? lst) '()]
[else (cons (+ 1 (car lst)) (add-one-to-each-elem (cdr lst)))]))
(add-one-to-each-elem '(1 2 3 4))
(define (add-x-to-each-elem x lst)
(cond [(empty? lst) '()]
[else (cons (+ x (car lst)) (add-x-to-each-elem x (cdr lst)))]))
(add-x-to-each-elem 2 '(1 2 3 4))
(define (subtract-one-from-each-elem x lst)
(cond [(empty? lst) '()]
[else (cons (- (car lst) 1) (subtract-one-from-each-elem (cdr lst)))]))
(add-x-to-each-elem 2 '(1 2 3 4))
(define (do-to-each-elem fn lst)
(cond [(empty? lst) '()]
[else (cons (fn (car lst)) (do-to-each-elem fn (cdr lst)))]))
(do-to-each-elem (lambda (x) (- x 1)) '(1 2 3 4))
(do-to-each-elem (lambda (x) (* x x)) '(1 2 3 4))
(map (lambda (x) (* x x)) '(1 2 3 4))- Tail recursion: possible test question
class code
#lang racket
(define (combine-lst fn acc lst)
(cond [(empty? lst) acc]
[else (combine-lst fn
(fn acc (car lst))
(cdr lst))]))
(combine-lst + 0 '(1 2 3 4))
(foldl + 0 '(1 2 3 4))
(foldl * 1 '(1 2 3 4))
(define (add-one-to-each-elem lst)
(cond [(empty? lst) '()]
[else (cons (+ 1 (car lst)) (add-one-to-each-elem (cdr lst)))]))
(add-one-to-each-elem '(1 2 3 4))
(define (add-x-to-each-elem x lst)
(cond [(empty? lst) '()]
[else (cons (+ x (car lst)) (add-x-to-each-elem x (cdr lst)))]))
(add-x-to-each-elem 2 '(1 2 3 4))
(define (subtract-one-from-each-elem x lst)
(cond [(empty? lst) '()]
[else (cons (- (car lst) 1) (subtract-one-from-each-elem (cdr lst)))]))
(add-x-to-each-elem 2 '(1 2 3 4))
(define (do-to-each-elem fn lst)
(cond [(empty? lst) '()]
[else (cons (fn (car lst)) (do-to-each-elem fn (cdr lst)))]))
(do-to-each-elem (lambda (x) (- x 1)) '(1 2 3 4))
(do-to-each-elem (lambda (x) (* x x)) '(1 2 3 4))
(map (lambda (x) (* x x)) '(1 2 3 4))lab3.rkt Solution without higher order functions
(define (reverse lst)
(if (empty? lst)
lst
(append (reverse (cdr lst))
(cons (car lst) null))))Solution with higher order functions
(define (reverse lst)
(foldl cons '() lst))(define (add-two-lists lst1 lst2)
(cond [(empty? lst1) lst2]
[(empty? lst2) lst1]
[else (cons (+ (car lst1) (car lst2))
(add-two-lists (cdr lst1) (cdr lst2)))]))At the top of the big-num.rkt, there was this line:
(provide big-add big-subtract big-multiply ...)At the top of the bc.rkt, there were lines like
(require "big-num.rkt")
; ...
(big-add arg1 arg2)
(big-subtract arg1 arg2)
; ...(struct employee (fname lname ssin id salary dept position))
(struct manager (fname lname ssin id salary dept position bonus))
(define (calc-wages emp)
(match emp
[(struct employee (first last social id sal department pos)) sal]
[(struct manager (_ _ _ _ sal _ _ extra)) (+ sal extra)]))
(let ([dilbert (employee "Dilbert" "Adams" 123 456 8000 "eng." "engineer")]
[phb (manager "Pointy-Haired" "Boss" 999 55 105000 "eng." "manager" 150000)])
(displayln (calc-wages dilbert))
(displayln (calc-wages phb)))
;; this is called 'pattern matching' or 'destructuring'- Like
HashtableorHashMapin Java, hashes are maps of key/value pairs. - Unlike Java, hashes are immutable (or at least as far as your homework is concerned).
(define ht (hash 'a 1 'b 2))
(hash-ref ht 'a) ;1
(hash-ref ht 'c) ; error
(hash-ref ht 'c 0) ; 0, the default value
(hash-ref ht 'b 0) ; 2
(define ht2 (hash-set ht 'c 42))
(hash-ref ht2 'c 0) ; 42
(hash-ref ht2 'a 0) ; 1
(hash-ref ht 'c 0) ; 0Formal semantics define how our language works concisely and with minimal ambiguity. To demonstrate, let’s make a small language.
e ::= expressions
true constant true
| false constant false
| if e then e else e conditional
v ::= true | false
; exp
(struct b-val (val))
(struct b-if (c thn els)) ; condition then-branch else-branch
(define (evaluate prog)
(match prog
[(struct b-val (v)) v]
[(struct b-if (c thn els)) (if (evaluate c)
(evaluate thn)
(evaluate els))]))
(evaluate (b-val #t))
(evaluate (b-if (b-val #f)
(b-if (b-val #f)
(b-val #t)
(b-val #f))
(b-val #t)))Users are demanding a new feature to be added to the language: numbers! Here is our new formal specification:
e ::= expressions
true constant true
| false constant false
| if e then e else e conditional
| n | succ e | pred e
v ::= true | false | n
e.g.,
succ 7 ⇓ 8
prd 4 ⇓ 3
(struct b-val (val))
(struct b-if (c thn els))
(struct b-succ (exp))
(strict b-pred (exp))
;; Subexpressions
;; -> succ (if true 0 else 1)
;; -> succ 0
;; -> 1
(define evaluate prog
(match prog
[(struct b-val (v)) v]
[(struct b-if (c thn els)) (if (evaluate c)
(evaluate then)
(evaluate els))]
[(evaluate b-succ (exp)) (let ([v (evaluate exp)])
(if (number? v)
(+ v 1)
(error "expected a number")))]
[(evaluate b-pred (exp)) (let ([v (evaluate exp)])
(if (number? v)
(- v 1)
(error "expected a number")))]))i := 5;
x := 1;
while !i > 0 do
x := !x * 2;
i := !i - 1;
end;
!x
See notebook
x = 42
function foo {
echo $x
}
function bar {
local x=666
foo
}
bar # prints 666
foo # prints 42
echo $x # prints 42This shows the example of name resolution.
Here’s another example in Java:
public class Test {
public static int x = 42;
public static void foo() {
System.out.println(x);
}
public static void bar() {
int x = 666;
foo();
}
public static void main(String[] args) {
bar(); // prints 42
}
}Dynamic scope (e.g., Bash): Name resolution depends on the execution path of the code (calling context).) Lexical or static scoping (e.g., Java): Name resolution depends on where the named variable is defined.
#lang racket
(define (make-adder x)
(lambda (y) (+ x y)))
(define inc (make-adder 1))
(inc 4)
(inc 42)
(define (make-counter)
(let ([count 0])
(lambda ()
;; Do as I say, not as I do
(set! count (+ count 1))
count)))
(define my-count (make-counter))
(my-count)
(my-count)
(my-count)
(define ctr2 (make-counter))
(my-count)
(ctr2)- Closure
- A pair of a function and its environment.
- Environment
- A mapping of free variables to their values in an outer scope.
(define my-if c thn els
(cond [(and (list? c) (empty? c)) els]
[(and (number? c) (= c 0)) els]
[(and (boolean? c) (not c)) els]
[else thn]))(my-if 0 1 0)
(my-if '(1 2 3) 1 0)
(my-if '() 1 0)
(define x 3)
(my-if #t
(set! x (+ x 1))
(set! x (* x 2)))
(displayln x)
;; outputs:
;; 8
(my-if #f
(displayln "true")
(displayln "false"))
;; outputs:
;; true
;; false- Scheme evaluates function args eagerly
- macro
- short for macroinstruction. Scheme has macros to change the behavior of evaulation.
- text-substitution
- C
#include <stdio.h>
#define SWAP(a,b) { int tmp=a; a=b; b=tmp; }
void badHygieneExample() {
int a = 5;
int tmp = 0;
printf("a=%d, tmp=%d\n", a, tmp);
SWAP(a,tmp);
// this macro actually looks like
// { int tmp = a; a = tmp; tmp = tmp;};
printf("a=%d, tmp=%d\n", a, tmp);
}
int main(int argc, const char* argv[]) {
badHygieneExample();
}- define-syntax-rule
- use this to define macros
(define-syntax-rule (swap x y) ;; pattern
(let ([tmp x]) ; |
(set! x y) ; | template
(set! y tmp)) ; |
)
(define a 3)
(define b 4)
(swap a b)
(displayln a)(define-syntax rotate
(syntax-rules ()
[(rotate a b) (swap a b)]
[(rotate a b c)
(begin
(swap a b)
(swap b c))]))- Contracts are enforced at run-time
- Types are enforced at compile-time
- We can write more sophisticated contracts
#lang racket
(define (quicksort lst)
(cond [(empty? lst) '()]
[else (let* ([pivot (car lst)]
[p (partition (cdr lst) pivot '() '())]
[left (quicksort (car p))]
[right (quicksort (cdr p))])
(cons pivot (append left right)))]))
(define (partition lst pivot left right)
(if (empty? lst)
(cons left right)
(let ([x (car lst)]
[rest (cdr lst)])
(if (> x pivot)
(partition rest pivot (cons x left) right)
(partition rest pivot left (cons x right))))))
(quicksort '(9 33 0 1 45 16 8 33))#lang racket
(define/contract (quicksort lst)
(-> list? (and/c list? ordered?))
(cond [(null? lst) '()]
[else
(let* ([pivot (car lst)]
[p (partition (cdr lst) pivot '() '())]
[left (quicksort (car p))]
[right (quicksort (cdr p))])
(cons pivot (append left right)))])) ;; BROKEN
(define ordered? lst
(if (< (length lst) 2)
#t
(and (<= (car lst) (cadr lst))
(ordered? (cdr lst)))))
(define (partition lst pivot left right)
(if (null? lst)
(cons left right)
(let ([x (car lst)]
[rest (cdr lst)])
(if (> x pivot) ;; BROKEN
(partition rest pivot (cons x left) right)
(partition rest pivot left (cons x right))))))Removing repetition:
(define (Employee n p s)
(list (box n)
(box p)
(box s)))- Using node.js
- We are going to care about the language, not the web usage of JS.
function Adder (amount) {
this.amount = amount;
}
Adder.prototype.add = function(x) {
return this.amount + x;
}
var myAdder = new Adder(1);
var y = myAdder.add(7);var x = 42, y = 7;
function add(a,b) { return a + b; }
var square = function(a) { return a + a; }
console.log("x + y = " + add(x,y));
var print = console.log;var getNextInt = function () {
var nextInt = 0;
return function () {
return nextInt++;
}
}();
console.log(getNextInt());
console.log(getNextInt());
console.log(getNextInt());
console.log(getNextInt());var getNextInt = function () {
var nextInt = 0;
return function () {
return nextInt++;
}();
}
console.log(getNextInt());
console.log(getNextInt());
console.log(getNextInt());
console.log(getNextInt());var complex = {real: 3, imaginary: 1};
console.log(complex.real);
complex.real = 4;
var s = 'imaginary';
complex[s] = 0; // complex.imaginary = 0var Dog = {
speak: function() {print('bark!');}
}
rex = {name: 'Rex'}, __proto__: Dog};Dog:
| __proto__ | Object.prototype |
| speak | fun(bark) |
|---|
Rex:
| name | Rex |
| __proto__ | Dog |
|---|
If Rex calls a function that isn’t defined in its box, then it will delegate that method call to its __proto__.
Let’s add a function to rex:
rex['favoriteToy'] = "squeaky ball";
rex.speak = function () { print('grr...');}
var fifi = { __proto__ : Dog};
fifi.speak(); // bark
rex.speak(); // grr
delete rex.speak
rex.speak(); // bark
delete rex.__proto__.speak; // deletes speak in Dog
fifi.speak(); // errorfunction Cat(name, breed) {
this.name = name; this.breed = breed;
// this is not optional. You always have to use this.
this.speak = function () { print('mean');}
}
var garfield = new Cat('Garfield', 'Orange tabby', 48);
// When we use the `new` keyword, we effectively all this function, with the following changes:
// it starts with
// this = {};
// this.__proto__ = Cat.prototype;
// it ends with
// return this;
function Cat(name, breed) {
this = {}; this.__proto__ = Cat.prototype;
this.name = name; this.breed = breed;
// this is not optional. You always have to use this.
this.speak = function () { print('mean');}
return this;
}- A JavaScript runtime and library designed for use outside the browser, based off of Google’s V8 engine.
- npm: package manager for Node.js
- http://nodejs.org
This is my file
There are many like it,
but this one is mine.
var fs = require('fs');
fs.readFile('myFile.txt',
function(err, data) { // callback function
if (err) throw err;
console.log("" + data);
})
console.log('all done');Create a makeListOfAdders function.
input: a list of numbers
returns: a list of adders
Correct version:
function makeListOfAdders(addrs) {
var result = [];
for (var i = 0; i < addrs.length; i++) {
result.push(function (addr) {
return function (x) {
return x + addr;
}
}(addrs[i]));
}
return result;
}
var addrs = makeListOfAdders([3,5,9]);
console.log(addrs[0](4));
console.log(addrs[1](10));Wrong version:
function makeListOfAdders(addrs) {
var result = [];
for (var i = 0; i < addrs.length; i++) {
result.push(function (x) {
return x + addrs[i];
});
}
return result;
}
var addrs = makeListOfAdders([3,5,9]);
console.log(addrs[0](4));
console.log(addrs[1](10));this can refer to the global object
Scoping is determined by execution contexts, each of which is comprised of
- a variable object
- Container of data for the execution context
- Container for variables, function declarations, etc.
- a scope chain
- The variable object plus the parent scopes.
- a context object (this)
- Top level context
- Variable object is known as a the global object.
thisrefers to global object.
- Variable objects are known as activation objects.
An activation object includes:
- Arguments passed to the function
- A special arguments objet
- Local variables
- What is
this? It’s complicated.
- Normal function calls: this global object
- Object methods: The object
- Constructors (functions called with new): The new object being created.
- Special cases
- Can be changed with
callandapplyfunctions - Can be changed with bind method (Ecmascript 5)
- For an in-line event handler (on the web), refers to the relevant DOM element.
- Can be changed with
x = 3;
function foo(y) {
console.log(this.x + y);
}
foo(100);
foo.apply(null, [100]); // array passed for args
foo.apply({x:4}, [100]);
foo.call({x:4}, 100); // no array needed
var bf = foo.bind({x:5}); // create a new function
bf(100);<html>
<input type='button' onclick='alert("Hello!");' value='Say hi'/>
</html><html>
<input id='thebutton' type='button' value='Say hi' onclick='alert(42);'/>
<script>
var button = document.getElementById('thebutton');
function sayGroovy() {
alert('groovy');
}
button.addEventListener('click', sayGroovy);
</script>
</html>JavaScript runs everything top-down, and added events and setTimeout are just added on the todo list of what to execute.
var foldl = function(f, acc, array) {
if (array.length === 0) return acc;
else foldl(f, f(acc, array[0]), array.slice(1));
}
var map = function(f, array) {
if (array.length === 0) return [];
else return [f(array[0])].concat(map(f, array.slice(1)));
}
function mult(x,y) { return x * y; }
function curryMult(x) {
return function (y) { return x * y; }
}
mult(3,4);
curryMult(3)(4);function Student(firstName, lastName, studentID) {
this.firstName = firstName;
this.lastName = lastName;
this.studentID = studentID;
this.display = function () {
console.log(this.firstName + " (this)");
}
}
Student.prototype.display = function() {
console.log(this.firstName + " (proto)");
}
var stu = new Student("Stu", "Disco", 1234);
stu.display();
delete stu.display;
stu.display();
delete stu.prototype;
console.log(Student.prototype);var harry = {
firstName: 'Harry',
lastName = 'Potter',
studentID = 888,
__proto__: Student.prototype
}switch (x) {
case 4: System.out.prinln("x is 4");
break;
case 5: return x * 2;
default: System.out.println("not 4 nor 5");
}(swtch (x)
[4 (displayln "x is 4")]
[5 (* x 2)]
['default (displayln "not 4 nor 5")])(define-syntax switch
(syntax-rules ()
{(switch v) (void)}
{(switch v ['default body]) body}
{(switch v [val1 body1] rest-cases ...)
(if (eqv? v val1)
body1
(swictch v rest-cases ...))}))- metaprogramming
- writing programs that manipulate other programs.
Special metaprogramming features are proposed for ECMAScript 6, code-named ECMAScript Harmony.
- Harmony
- getting into agreement from all the ECMAScript committee members.
Proposed by Tom Van Cutsem and Mark Miller (security guy)
- AB
- ABE
- AC
- BC
- AE
- primitive types
- numbers
- booleans
- compound types
- strings (list of characters)
- lists
- functional language
lambda- dynamically type
- type errors happen at runtime
- there might be errors that never happen because the code path with the error does not get executed.
- Lexer/Tokenizer
- Parser (takes in tokens and returns an AST)
- Compiler/Interpreter
- Compiler
- transforms the language into a different source (machine code, source-to-source, etc.)
- Interpreter
- executes the code, not necessarily with machine-code optimization.
- Louden & Lambert design criteria
- efficiency
- regularity (uniformity)
- e.g., PHP’s inconsistent naming conventions. Pascal’s return-value convention.
- security
- run-time checks.
- extensibility
- clearly distinguish input/output
- contrast with C/C++ with parametric return values (pointers).
- functions are first-class values
- higher-order functions
- e.g., map, foldl, foldr, call, apply
- no assignments (no loops) (purely functional [PF])
- recursion
- value of a function call depends only on its arguments (PF)
- no side effects
- tail recursion
- accumulator pattern (question #9 from practice exam)
- big-step
- store (or map, or env)
- closures + scoping
- lexical (static) scoping vs dynamic scoping
- free variables
- text substitution (C preprocessor)
- inadvertent variable capture
- bad hygiene
- Syntactic macros
- working on ASTs
- hygienic
- run-time enforcement
- pre-conditions
- post-conditions
- blame
- ->
- ->i
- can be put on module and/or functions
- mult-paradigm
- functional
- object-oriented
- prototypes. no classes.
- dynamically typed
- no concurrency
- event-based programming
- browser
- Node.js (events.EventEmitter)
- on
- emit
- meaning of ‘this’
- reflection: Introspection & Self Modification
- Intercession
- metaobject protocol (MOP)
- Object proxies
- MOP
- proxy objects, behavior determined by handler
made by Douglas Crockford
- Made by Microsoft
- One of the many JavaScript compilers
- Tips for compilers to make code more efficient
- most importantly, type systems prevent code from running with errors.
Facts:
- All men are mortal.
- Aristotle is a man.
Conclusion:
- Aristotle is mortal.
- Declarative programming language
- you specify what you want
- Computer sorts out the details
- Logical
- specify facts and rules
- deduce conclusions
% Facts
king(robert).
wife(cersei, robert).
brother(jamie,cersei).
brother(jamie,tyrion).
brother(tyrion,jamie).
friend(robert,ned).
friend(robert,jon_arryn).
friend(tyrion,bronn).
friend(tyion,jamie).
enemy(tyrion,littlefinger).
enemy(cersei,robert).
enemy(cersei,tyrion).
% rules
enemy(cersei,X) :- friend(robert,X). % variables are Capitalized. if robert is a friend of X, then cersei is the enemy of X
% if tyrion is a friend of X, then cersei is the enemy of X
enemy(cersei,X) := friend(tyrion,X),
X \= jamie.swi-prolog interpreter
?- enemy(cersei,bronn). false. ?- enemy(cersei,jamie). false. ?- enemy(cersei,Enemy). Enemy = robert ?- enemy(Hater,tyrion). ?- enemy(Hater,Enemy).
queen(Q) :- wife(Q,K),
king(K).
enemy(jamie,X) :- not (brother(jamie,X)),
X \= jamieApproximate: A: 88+ B: 77-87 C: 64-76
- “Learn Prolog Now”, http://www.learnprolognow.org
- SWI-Prolog website (contains manual and tutorials), http://www.swi-prolog.org
- “NLP with Prolog in the IBM Watson System”, http://www.cs.nmsu.edu/ALP/2011/03/natural-language-processing-with-prolog-in-the-ibm-watson-system/
Batman likes gotham
likes(batman, gotham).
likes(batman, justice).
likes(ras_al_ghul, justice).
likes(ras_al_ghul, revenge).Everybody likes Raymond? That should probably be a rule, where X is everyone
What do Batman and Ra’s al Ghul both like?
likes(batman,X), likes(ras_al_ghul,X)- X
- variable
- ,
- and
Through 2 processes:
- Resolution
- Unification
- Resolution
- The process of matching facts and rules to perform inferencing.
scary(V) :- villain(V),
kills_people(V).
scary(V) :- villian(V),
power(V,_).motive(S, mr_boddy) :- suspect(S), S \= wadsworth.
motive(mrs_peacock, cook).
motive(colonel_mustard, motorist).
...
Final result:
accuse(S,V) :- motive(S,V), murder(V,W,R), suspect(S), visited(S,R), can_use(S,W), not(alibi(S,V)).visited(S,R) :- not(never_visited(S,R)).
never_visited(miss_scarlet, billiard_room).
never_visited(professor_plum, kitchen).
never_visited(colonel_mustard, R) :- murder(mr_boddy, _, R).
can_use(S,W) :- not(cant_use(S,W)).
cant_use(colonel_mustard, rope).
cant_use(professor_plum, revolver).
cant_use(mrs_peacock, candlestick).
alibi(mr_white, mr_boddy).
alibi(mr_green, _).
%% handle cases where a room can have more than one victim.
alibi(miss_scarlet, V) :- murder(V,_,R), murder(_, revolver, R).edge(a,b,2).
edge(b,a,2).
edge(a,c,3).
edge(c,a,3).
edge(a,f,4).
edge(f,a,4).
edge(b,c,2).
edge(c,b,2).
edge(c,d,3).
edge(d,c,3).
edge(c,e,1).
edge(e,c,1).
edge(d,f,5).
edge(f,d,5).Lists in Prolog: [Head|Tail]
like car and cdr in Scheme
find_path(Start,End,Cost,Path) :- edge(Start,End,Cost),
Path = [Start, End].
find_path(Start,End,Cost,Path) :- edge(Start,X, InitCost),
find_path(X,End,RestCost,TailPath),
TotalCost is InitCost + RestCost,
Path = [Start|TailPath].% myappend(List1,List2,Result).
myappend([],List2,List2).
myappend([H|T1],List2, [H|TResult]) :- myappend(T1,List2,TResult).
%myreverse(List,Reversed).
myreverse([],[]).
myreverse([H|T1],Rev) :-
myreverse(T,RT),
append(RT, [H], Rev).
%in_list(X,List).
% redundant
in_list(X, [Y|_]) :- X = Y.
in_list(X, [X,|_]).
in_list(X,[Y|Rest]) :- X \= Y, in_list(X,Rest).
% built-in prolog function called member
% add_nums(ListNums, Sum).
add_nums([], 0).
add_nums([H|T], Sum) :-
add_nums(T, SubSum),
Sum is H + SubSum.
% qsort(List,Sorted)
qsort([],[]).
qsort([Pivot|Tail], Sorted) :-
divide(Pivot,Tail,Left,Right),
qsort(Left,LSort),
qsort(Right,RSort),
append(LSort,[pivot|RSort]).
% divide(P,List,Left,Right)
divide(_,[],[],[]).
divide(P,[H|T],[H|L],R) :-
P > H,
divide(P,T,L,R).
divide(P,[H|T],L,[H|R]) :-
P =< H,
divide(P,T,L,R).
% note that less-than-equals is =<, not <=. "<=" looks like an arrow, which is probably something different in Prolog.<<batman_example>>
villain(joker).
villain(penguin).
villain(catwoman).
villain(scarecrow).
villain(bane).
kills_people(joker).
kills_people(penguin).
kills_people(bane).
power(scarecrow,fear).
power(bane,venom).
scary(V) :- villain(V), kills_people(V).
scary(V) :- villain(V), power(V,_).
%% ?- scary(V).
%% V = joker ;
%% V = penguin ;
%% V = bane ;
%% V = scarecrow ;
%% V = bane ;
%% false.
%% ?- findall(V,scary(V),R).
%% R = [joker,penguin,bane,scarecrow,bane].
find_scary(scarySet) :-
find_all(V,scary(V), ListOfScaries),
get_unique(ListOfScaries, ScarySet), !. % green cut
get_unique([],[]).
get_unique([H|T], Set) :-
get_unique(Tail, TailSet),
\+ member(H, TailSet),
Set = [H|TailSet].
% \+ is the same thing as "not"
get_unique([H|Tail], Set) :-
get_unique(Tail,TailSet),
member(H,TailSet),
Set = TailSet.- Semantics
- What does a program mean?
- Defined by an interpreter or compiler?
- Syntax
- How is a program structured?
- Defined by a lexer and parser.
- Process of converting characters to the words of the language.
- Generally handled through regular expressions.
- A variety of lexers exist
- Lex/Flex are old and well-established
- ANTLR & JavaCC both handle lexing and parsing
- Sample lexing rule for integers (Int Antlr)
INT : [0-9]+ ;
a exactly one a a? 0 or 1 a a* 0 or more a+ 1 or more
INT : [1-9][0-9]* | 0
- Reserved words or keywords
- e.g.,
if,while
- e.g.,
- Literals or constants
- e.g.,
123,"hello"
- e.g.,
- Special symbols
- e.g.,
";","<”, ="+"
- e.g.,
- Identifiers
- e.g.,
balance,tryionLannister
- e.g.,
Example ANTLR file:
// Expr.g4
grammar Expr;
// Lexing rules (capital letters)
INT : [0-9]+ ;
NEWLINE: '\r'? '\n' ;
WS: [ \t] -> skip ;
MUL: '*' ;
DIV: '/' ;
ADD: '+' ;
SUB: '-' ;(in class)
- Parsers take the tokens of the language and combines them into abstract syntax trees (ASTs).
- The rules for parsers are defined by context free grammars (CFGs).
- Parsers can be divided into
- bottom-up/shift-reduce parsers
- top-down parsers
- Grammars specify a language
- Backus-Naur form is a common format
Expr -> Number
| Number + Expr
- Terminals cannot be broken down further.
- Non-terminals can be broken down into further phrases.
Help our code read the parser by adding op:
// ***Paring rules ***
/** The start rule */
prog: stat+ ;
stat: expr NEWLINE # printExpr
| NEWLINE # blank
;
expr: expr op=( '*' | '/' ) expr # MulDiv
| expr op=( '+' | '-' ) expr # AddSub
| INT # int
| '(' expr ')' # parens
;
The # names are not comments. They are tips to ANTLR about how to name functions in the generated code.
graph.prolog
This still does backtracking.
find_path(Start, End, _, TotalCost, Path) :-
edge(Start, End, Cost),
Path = [Start, End].
find_path(Start, End, Visited, TotalCost, Path) :-
edge(Start, X, InitCost),
\+ member(Start, Visited),
find_path(X, End, [Start|Visited], RestCost, TailPath),
TotalCost is InitCost + RestCost,
Path = [Start|TailPath].find_path(Start, End, _, TotalCost, Path) :-
edge(Start, End, Cost),
Path = [Start, End].
find_path(Start, End, Visited, TotalCost, Path) :-
edge(Start, X, InitCost),
\+ member(Start, Visited),
find_path(X, End, [X|[Start|Visited]], RestCost, TailPath),
TotalCost is InitCost + RestCost,
Path = [Start|TailPath].- Created by Matz
- Smalltalk
- everything is an object
- blocks
- sophisticated metaprogramming
- Perl
- Strong support for regular expressions.
- Many functions names borrowed
- Ruby’s “killper app”: lightweight web framework.
- “convention over configuration” philosophy.
- Initially, David Heinemeier Hansson (DHH) used PHP.
- abandoned it for Ruby when it created Rails
- We will focus on Ruby — we don’t care about Rails.
puts 'Hello World!'I was talking with my collegue about the possibility of an object-oriented scripting language. […] I knew Python then. But I didn’t like it.
- Matz 1999
class Person
def initialize name # Constructor
@name = name
end
def name
return @name
end
def name= newName
@name = newName
end
def say_hi
puts "Hello, my name is #{@name}"
end
endclass Person
attr_accessor :name
def initialize name
@name = name
end
def say_hi
puts "Hello, my name is #{@name}"
end
endp = Person.new "Joe"
puts "Hello, #{p.name}"class Dog
def initialize(name)
@name = name
end
def speak
puts "#{@name} says bark"
end
end
rex = Dog.new('Rex')
rex.speakclass GuardDog < Dog
attr_reader :breed
def initialize(name, breed)
super(name)
@breed = breed
end
def attack
puts "growl"
end
end
satan = GuardDog.new('Satan', 'Doberman')
puts "Satan is a #{satan.breed}"
satan.attack
satan.speak- Allow user to add features to a class
- Similar to interfaces in Java, but programmer can specify functionality
class Person
include Comparable
endmodule RevString
def to_rev_s
to_s.reverse
end
end
class Person # Re-opening class
include RevString
def to_s
@name
end
end
p.to_rev_s # p defined previously- Borrowed from Smalltalk
- Supeficially similar to blocks in other languages.
- Allows developer to create custom control structures.
- (We’ll discuss in depth another day).
file = File.open('temp.txt', 'r')
file.each_line do |line|
puts line
end
file.closeVersion 2:
File.open('temp.txt', 'r') do |file|
file.each_line { |line| puts line }
ends = "Hi, I'm Larry; this is my" +
" brother Darryl, and this" +
" is my other brother Darryl."
s.sub(/Larry/, 'Laurent')
puts s
s.sub!(/Larry/, 'Laurent')
puts s
puts s.sub(/brother/, 'frere')
puts s.gsub(/brother/, 'frere')| . | Any character except a newline |
| \w | A word character ([a-zA-Z0-9_]) |
- Ruby borrows heavily from Smalltalk. Some key Smalltalk concepts:
- Everything is an object
- Chunks of computation can be passed as blocks
- Objects commuicate by passing messages
Opening/closing file example
With Ruby, we can write methods that accept blocks, which is useful for
- creating our own control structures
- eliminating boilerplate code
def with_prob (prob)
yield if (Random.rand < prob)
end
with_prob 0.42 do
puts "There is a 42% chance "
+ "that this code will print"
endyield is the special keyword to make use of custom blocks
Another way to use custom blocks is with named blocks using &.
def with_prob (prob, &blk)
blk.call if (Random.rand < prob)
end
with_prob 0.42 do
puts "There is a 42% chance "
+ "that this code will print"
end
def half_the_time (&block)
with_prob(0.5, &block)
enddef do_noisy
puts "About to call block"
yield
puts "Just called block"
end
do_noisy do
puts 3 + 4
endclass Array # re-opening array
def each_downcase
self.each do |word|
yield word.downcase
end
end
end
["Alpha", "Beta", "AndSoOn"].each_downcase do |word|
puts word
enddef conversion_chart(from_units, to_units, values)
puts "#{from_units}\t#{to_units}"
left_line = right_line = ""
from_units.length.times { left_line += '-' }
to_units.length.times { right_line += '-' }
puts "#{left_line}\t#{right_line}"
for val in values
converted = yield val
puts "#{val}\t#{converted}"
end
puts
end
celsius_temps = [0,10,20,30,40,50,60,70,80,90,100]
conversion_chart("C", "F", celsius_temps) { |cel| cel * 9 / 5 + 32 }
fahrenheit_temps = [0,10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180,190,200 ]
conversion_chart("Fahr.", "Celsius", fahrenheit_temps) {|fahr| (fahr-32) * 5 / 9 }
conversion_chart("Km", "Miles", (1..10)) do |km|
mile = 0.621371 * km
end
3.times do
puts 'hi'
endneil gaftner wanted to have Ruby-style closures in Java 8, but he lost and JS-style closures are now in Java.
def with_prob (prob)
yield if (Random.rand < prob)
end
def foo x
with_prob 0.5
do
return 0
end
return x
endclass Employee
attr_accessor :name, :ssid, :salary
def initialize(name, sid, salary)
@name = name; @sid = ssid; @salary = salary
end
def to_s
@name
end
end
alice = Employee.new("Alice Alley", 1234, 75000)
bob = Employee.new("Robert Tobles", 5678, 50000)
class << bob
def signing_bonus
2000
end
end
puts(bob.signing_bonus)
puts(alice.signing_bonus)class Employee
attr_accessor :name, :ssid, :salary
class << self
def add(emp)
puts "Adding #{emp}"
@employees = Hash.new unless @employees
@employees[emp.name] = emp
end
def get_emp_by_name(name)
@employees[name}
end
end
def initialize(name, sid, salary)
@name = name; @sid = ssid; @salary = salary
Employee.add(self)
end
def to_s
@name
end
end
alice = Employee.new("Alice Alley", 1234, 75000)
bob = Employee.new("Robert Tables", 5678, 50000)
b = Employee.get_emp_by_name('Robert Tables')
puts b.salary- Allows for code to be executed dynamically.
- In most languages, eval only takes a string
eval "puts 2+3"- While this feature is widely popular (especially in JavaScript), it is also a source of security problems.
- See richards et al. The Eval that Men Do, 2011 for more details
var jsonStr = "[{name: 'Philp Fry', age: 1000, job: 'delivery boy'," +
" {name: 'Bender Rodriquez', age: 42, job: 'bending unit'}]";
var employeeRecords = eval(jsonStr);- instance_eval
- class_eval
class Musician
attr_accessor :name, :genre, :instrument
end
m = Musician.new
m.name = 'Norah Jones'
puts m.nameclass Class
def my_attr_accessor(*args)
args.each do |prop|
self.class_eval("def #{prop}; @#{prop}; end")
self.class_eval("def #{prop}=(v); @#{prop} = v; end")
end
end
end
class Musician
# my_attr_accessor not built into Ruby. We're going to define this
my_attr_accessor :name, :genre, :instrument
end
m = Musician.new
m.name = 'Norah Jones'
puts m.name- Termination-Insensitive means there could be some data loss that it’s OK to lose.
- Done first by a woman named Dorothy Denning
grammar Expr;
ID: [a-zA-Z]+;
INT: [0-9]+;
NEWLINE: '\r'? '\n';
WS: [ \t]+ -> skip;
MUL: '*';
DIV: '/';
ADD: '+';
SUB: '-';
prog: stat+;
stat: exp NEWLINE #printExpr
| NEWLINE #blank
| ID '=' expr NEWLINE #assign
;
expr: expr op=('*'|'/') expr #MulDiv
| expr op:('+'|'-') expr #AddSub
| INT #int
| '(' expr ')' #parens
| ID #id
;public class EvalVisitor extends ExprBaseVisitor<Integer> {
Map<String, Integer> memory = new HashMap<String, Integer>();
public Integer visitPrintExpr(ExprParser.PrintExprContext ctx) {
int value = visit(ctx.expr());
System.out.println(value);
return 0;
}
public Integer visitAssign(ExprParser.AssignContext ctx) {
String id = ctx.ID().getText();
int value = visit(ctx.expr());
memory.put(id, value);
return value;
}
public Integer visitId(ExprParser.IdContext ctx) {
String id = ctx.ID().getText();
if (memory.contains(id)) return memory.get(id);
return 0;
}
}Example run of the
java -cp build:lib/antlr-4.4-complete.jar org.antlr.v4.runtime.misc.TestRig edu.sjsu.fwjs.parser.FeatherweightJavaScript prog -gui fwjsScripts/controlStructs.fwjs- source code
- lexer/tokenizer -> tokens/lexemes
- parsers -> ASTs
- Compiler or interpreter
- More typically, languagse are compiled to bytecode for a virtual machine
- The MV is responsible for executing these instructions.
- In today’s lab, we will implement a compiler and a stack-based VM for Scheme.
(println (+ 2 3 4))
(println (- 13 (* 2 4)))
(println (- 10 4 3))- PUSH
- takes one arg & adds it to the stack.
- pops top of the stack and prints it.
- ADD
- pops top two elements of the stack, adds them together, placing the result on the stack.
- SUB
- performs subtraction.
- MUL
- performs multiplicatqion.
class Tree
attr_accessor :value, :left, :right
def initialize(value, left=nil, right=nil)
@value = value
@left = left
@right = right
end
# TBD
end
my_tree = Tree.new(...)
my_tree.each_node do |v|
puts v
end
arr = []
my_tree.each_node |v|
arr.push(v)
endclass Tree
def each_node(&block)
@left.each_node(&block) if @left
@yield @value
@right.each_node(&block) if @right
end
def method_missing(m, *args)
path = m.to_s.scan(/left|right/)
get_node(path)
end
private
def get_node(path)
next_step = path.shift
if !next_step then
@value
elsif next_step == 'left' then
@left.get_node(path)
else
@right.get_node(path)
end
end
end- Knuth created TeX to precsely control the interface of his content.
- His work on TeX was also the inspiration for
- Leslie Lamport built-upon
- LaTeX is a domain specific language (DSL)
- That is, it is designed for a very specific use case.
- Provides separation of concerns
- Details about formatting are (for the most part) kept separately from your actual content.
- It is the inspiration of literate programming.
\documentclass{article} % specific document type
\title{Hello World}
\begin{document}
\maketitle
\end{document}\documentclass{article}
\title{Hello, \LaTeX}
\author{Me, myself, and I}
\begin{document}
\maketitle
\section{This is Section 1} \label{sec:one}
This is my section, there are many like it, but this one is mine.
\subsection{Sub}
Some more text
\section{New Stuff}
As discussed in Section~\ref{sec:one}
\end{document}#include <stdlib.h>
#include <stdio.h>
int* zero_out_negatives(int a[], int len) {
int *res = malloc(sizeof(int) * len);
//int res[len];
for (int i=0; i<len; i++) {
if (a[i] < 0) res[i] = 0;
else res[i] = a[i];
}
return res;
}
int main(int argc, char** argv) {
int nums[] = {0, 12, 5, -42, 9, 7, -18, 0};
int len = 8;
int *no_negs = zero_out_negatives(nums, len);
for (int i=0; i<len; i++) {
printf("%d ", no_negs[i]);
}
printf("\n");
// Forgot free(no_negs);
}fn main() -> () {}fn foo(x: i32) -> i32 {
x + 3
}
fn main() {
println!("Hello World");
println!("{}", foo(4));
let a = 1;
let b = 2;
let c = 3;
println!("a:{} b:{} c:{}", a, b, c);
}- Creating a variable grants ownership
- Asignment transfers ownership
- “Borrowing” allows a section of code to use a variable without taking ownership. At one time, you can have either
- 1 mutable borrow, or
- Limitless immutable borrows
struct Complex { real: i32, imaginary: i32 }
fn main() {
let cmplx1 = Complex { real: 7, imaginary: 2 };
let cmplx2 = Complex { real: 3, imaginary: 1 };
let mut ans = add_complex(&complx1, &complx2);
println!("The answer is {}+{}i", ans.real, ans.imaginary);
}- From a Unix/Dos command line:
sjs <sweet.js file> -o <js file>Then you may run the output file normally:
node <js file>macro <name> {
rule {
<pattern>
} => {
<template>
}
}Example:
macro swap {
rule { ($a, $b) } => {
var tmp=$a; $a=$b; $b=tmp;
}
}
var a = 10;
var b = 20;
swap (a,b)var a$1 = 10;
var b$2 = 20;
var tmp$3 = a$1;
a$1 = b$2;
b$2 = tmp$3;macro rotateLeft {
rule { ($a, $b, $c) } => {
var tmp = $a;
$a = $b;
$b = $c;
$c = tmp;
}
}
var a = 10;
var b = 20;
var c = 40
// prints a:10 b:20 c:40
console.log("a:" + a + " b:" + b + " c:" + c);
rotateLeft(a, b, c);
// prints a:20 b:40 c:10
console.log("a:" + a + " b:" + b + " c:" + c);Macros can specify multiple rules. They may also be defined recusively.
macro m {
rule { ($base) } => { [$base] }
rule { ($head $tail ...) } => {
[$head, m ($tail ...)]
}
}
m (1 2 3 4 5)macro addNums {
rule { $x ... } => {
$x (+) ...
}
}
console.log(addNums 1 2 3 4);can be used to create anaphoric macros
class Person {
constructor(name) {
this.name = name;
}
say(msg) {
console.log(this.name + " says: " + msg);
}
}
var bob = new Person("Bob");
bob.say("Macros are sweet!");class macro
macro class {
rule {
$className {
constructor $cparams $cbody
$($mname $mparams $mbody) ...
}
} => {
function $className $cparams $cbody
$($className.prototype.$mname
= function $mname $mparams $mbody; ) ...
}
}Sorting a list of numbers.
public static void sortNums (List lst) {
for (int i = 0; i < lst.size() - 1; i++) {
for (int j = 0; i < lst.size() - 1; j++) {
if (((Integer) lst.get(j)).intValue() >
((Integer) lst.get(j + 1)).intValue()) {
Integer tmp = (Integer) lst.get(j);
lst.set(j, lst.get(j + 1));;
lst.set(j + 1, tmp);
}
}
}
}sort(lint, (Integer x, Integer y) -> {
if (x % 2 == 0 && y % 2 == 0)
return 0;
else if (x % 2 == 0)
return -1;
else if (y % 2 == 0)
return 1;
else
return 0;
});Consumer<Integer> c = ((Integer x, Integer y) -> x - y);
Consumer<String> s = ((String s) -> System.out.println(s));public static void applyFunOnVar(Consumer<String> f, String s) {
f.accept(s);
}applyFunOnVar((String s) -> System.out.println(s), "Hello");
applyFunOnVar(System.out::println); // method reference- looks for common JS errors
- source-to-source compiler aka transpiler
- Types
- catches errors at compile time.
- tips for your IDE or other tools.
- tips for compiler
- enforced documentation
- comments can lie, but code can’t.
- logic with facts, engine deduces results
- declarative programming language. State what you want, not how you get it.
- facts, variables, and rules
- resolution: if subgoal matches the head of another rule, we replace it with body of the matching rule.
- unification: instantiation of variables in using pattern matching.
isoperator- cut operator (!)
- green cut: optimization
- red cut: changes results
- Example: see batman_example
goal :- a, b, c, !, d, e, f.
<-------- || <-------
% examples
teacher(thomas_austin). % fact
runs_class(X) :- teacher(X). % rule
loves(Everybody, raymond). % rule
% rules have variables, facts do not.% Get a set out of a list
get_unique([],[]).
get_unique([H|Tail],Set) :-
get_unique(Tail,TailSet),
\+ member(H, TailSet),
Set = [H|TailSet].
get_unique([H|Tail], Set) :-
get_unique(Tail, TailSet),
member(H, TailSet),
Set = TailSet.- ANTLR
- compiler-compiler; parser generator
- syntax (structure), not semantics (meaning)
- context-free grammars (CFGs)
- lexing: source -> tokens
- parsing: tokens -> AST
- bottom-up
- LR parsers (L to R, Rmost deriv)
- left-recursive grammars OK (e.g., E -> E + T
- LALR (lookahead, LR)
- aka shift-reduce parsers
- top-down
- LL parsers (L to R, Lmost deriv)
- LL(k) grammars (lookahead k tokens)
- LL(1) grammars - recursive descent parsers
- they’re important because they’re fast and easy to write
- ANTLR is an LL parser
- LL(*) arbitrary lookahead (ANTLR v1 to v3)
- ALL() - adaptive LL()
- support left recursive (LR) grammars
- influences
- Perl
- regex, taint analysis, naming
- Smalltalk
- everything is an object
- blocks
- method_missing
- Perl
- Rails
- web framework, following convention over configuration.
- Ruby’s “killer app”
- eval
- runs a string as code
- instance_eval/class_eval
- taint analysis (integrity)
- $SAFE
- 0 (default)
- 1 (no eval on tainted data)
- 3 new stuff is tainted
- info flow analysis (confidentiality)
- noninteference
- prior inputs don’t affect prior outputs
- secure multi-execution
- running a prog mult times w/ different security levels.
- $SAFE
def with_prob(prob)
yield if (Random.rand < prob)
end
def foo
with_prob 0.5 do
puts 'made it'
return 0
end
return 1
endfunction withProb(p, f) {
if (Math.random() < p)
return f();
}
function foo() {
withProb(0.5, function() {
console.log("made it!");
return 0;
});
return 1;
}- portability
- DSL for typesetting
- \section
- \label
- \ref
- \cite (for BibTeX)
- takes care of formatting for references
- DSL for text adv/interactive storytelling
- declarative
- logical
- natural language (it looks like English)
- low-level system lang (kill C++)
- memory safe (no gc or runtime)
- reasonable build times
- concurrency
- macros for JS
- rule macros
- case macros
- allow you to break hygiene
- JS engine in Java
- put: add a val to JS env.
- eval(jsCode) executes JS code and returns result.
- we have to understand what that return value is and cast appropriately.
// lambda
File myFile = new File(dirName);
File[] dirs = myFile.listFiles((File f) -> f.isDirectory());
// method reference
File[] dirs = myFile.listFiles(f::isDirectory);