Secure diffuse computing: class #2

Teacher: Serrano

Slides

Web page: http://www-sop.inria.fr/members/Manuel.Serrano/index-7.html#Publications

Wikipedia entry for Scheme, the LISP dialect he'll use.

Books:

Papers:

Topics

Basic intro to so-called "web 1.0". HTTP, HTML, CSS, etc. Skeleton of a basic web server in Scheme.
Continuations

Exercises

  1. Write the function walk that scans a tree, searching the first leaf satisfying predicate

walk: tree x predicate → value

  1. Write the function step that applies procedure succesively to each leaf of the tree:

step: tree x proceure → (proceure →) procedure

LISP/Scheme

scheme ::= number | "string" | #t | #false | identifier | (scheme scheme*)
identifier ::= [A-Za-z_+<>?!...][A-Za-z0-9_+<>?!...]

where … = a lot more, most of them excluding [()]

Overall meaning: (function param1 param2 …)

Variable definition

int x = 3;

Translates to:
(define x 3)

Types

int x = 3;
void foo () {
    x = 3.0; // Would not compile with (int)x
}

Translates to:
(define x 3)
(define (foo)
    (set! x 3.0))

Exclamation mark is part of the name set! - it allows for many different characters in names;

Note: Scheme is indifferent about types

(define x "foo")
(define (foo)
    (/ x 3.0))

This will throw an exception while executing foo.

Special functions

(set! variable value)
(if condition then else)
(lambda vars body)

Eg if is special and different of all other functions, in that it first
evaluates 'condition', then if it was true 'then', otherwise 'else'.

Subroutines

int x (int y) {
    return y++;
}

Translates to:
(set! x (lambda (y) (+ 1 y)))

An equivalent short cut in Scheme/Hop:

(define (x y) (+ 1 y))

An important feature is treating functions as 1-st class citizens.

int fun((int)(*f()), int y) {
    return f(y);
}

int add1 (int z){
    return z+1;
}
...
fun(add1, 5)

Translates to:
(define (fun f y) (f y))
(define (add1 z) (+ 1 z))
...
(fun add1 5)

Another example:

(define (foo x)
    (lambda (y)
        (+ x y)))

In Javascript:
function foo (x) {
    return function (y) {return x + y;};
}

Local variables

int foo (...)
{
    if(test) {
        int tmp = bar(3);
        return tmp + 10;
    }
}

Is so easy to get using an anonymous function:
(define (foo ...)
    (if test
        ((lambda (tmp) (+ tmp 10)
            (bar 3))
        )
    )
)

Exactly the same in Javascript (though you may use normal var):
function foo (...) {
    if(test)
        (function (tmp) { return tmp + 10; }) (bar(3));
}

Twisted, isn't it? Though you can get it more or less var-style in Lisp:
(let ((tmp (bar 3)))
    (+ tmp 10)
)

Note that (( after let is because you can get more than one local variable at a time. Like:
let (    (tmp1 (x))
        (tmp2 (y))
)

General program examples

Fibonacci:

(define (fib x)
    (if (< x 2)
        1
        (+ (fib (- x 1)) (fib (- x 2)))))
Unclear, need to ask the teachers, since most is obviously derived works.