CS1101S

Lecture 10: Symbolic Data

14 September 2012

Martin Henz

Overview

• Permutations
• Strings, equality, list membership
• Symbolic differentiation

Reading: SICP 2.2.2, 2.3

Recap: Signal processing view of lists

• Producer: creates a list
• Filters: remove elements
• Mappers: modify elements
• Accumulator: consumes list and generates result

Producers: list

• list is the only function in JediScript with variable number of arguments
• Convenient way to make a list, using its extensional definition

Filters

• filter(pred, xs): Returns sublist of xs of elements x for which pred(x) returns true
• Example:

  filter(is_even, squares)
  

Mappers: Reviewing map

• map(fun, xs): result is a list with same elements as xs, except that fun is applied to each of them.
• Example:

  map( square, list(1,2,3) );
  

Accumulators

• accumulate: Works like fold but on lists
• accumulate(op, initial, xs): applies op successively to the elements of xs, starting with initial
• Example:

  accumulate(plus, 0, squares)
  

Definition of accumulate

function accumulate(op,initial,sequence) {
    if (is_empty_list(sequence)) {
      return initial;
    } else {
	return op(head(sequence),
                  accumulate(op,initial,
                             tail(sequence)));
    }
}

Example of Signal Processing

var squares = build_list(10, square);
var even_squares = filter(is_even, squares);
var half_even_squares 
= map(function(x) { return x / 2; },
      even_squares);
var result = accumulate(plus, 0, half_even_squares);

Example: Permutations

• Given a set S, generate all permutations of S
• Example:
  • S = {1,2,3}
  • Permutations =
    { [1 2 3], [1 3 2], [2 1 3],
    [2 3 1], [3 1 2], [3 2 1]}
• How to represent S, and permutations?

Strategy

• For each element x in S:
  • Generate all permutations of S - x
  • Place x in front of each permutation
• Append all results together

Example

• Let S = {1, 2, 3}, and let x = 1
  • Generate all permutations of S - x: [2 3], [3 2]
  • Place x in front of each permutation: [1 2 3], [1 3 2]
• Same for x = 2: [2 1 3], [2 3 1]
• Same for x = 3: [3 1 2], [3 2 1]
• Append all:
  [ [1 2 3], [1 3 2], [2 1 3], [2 3 1], [3 1 2], [3 2 1] ]

flatmap

function flatmap(proc, xss) {
    return accumulate(append,
                      [],
                      map(proc, xss);
}

• Common pattern in list processing, so we define a function for it
• Note that the given list of lists xss is first mapped, and then accumulated using append

Recap: Strategy

• For each element x in S:
  • Generate all permutations of S - x
  • Place x in front of each permutation
• Append all results together

Permutations

function permutations(s) {
   if (is_empty_list(s)) {
      return list([]);
   } else {
      return flatmap(function(x) {
                        return map(function(p) {
                                      return pair(x,p);
                                   },
                                   permutations(remove(x,s)));
                     },
                     s);
}  }

Overview

• Permutations
• Strings, equality, list membership
• Symbolic differentiation

Reading: SICP 2.2.2, 2.3

Revisiting strings

• Strings are sequences of characters
• Double quotes delimit the string:

  var hw = "Hello World!";
  

• A backslash allows double quotes within strings:

  var hw = "Hello \"World\"!";
  

Revisiting strings

• backslash backslash allows for backslash within strings:

  var hw = "Hello \\ World!";
  

• Single quotes can alternatively be used:

  var hw = 'Hello World!';
  

• Use single quotes if you have a lot of double quotes in the string: no need for backslash

  var hw = 'Hello "World"!';
  

Revisiting strings

• Append two strings using +

  var hw = "Hello" + "World!";
  

• Rule: string addition is used as soon as one argument of + is a string; the other argument is converted to a string if needed.

  var hw = "The result is: " + 42;
  

Revisiting member

function member(v, xs){
    if (is_empty_list(xs)) {
	return [];
    } else {
	if (v === head(xs)) {
	    return xs;
	} else {
	    return member(v, tail(xs));
	}
    }
}

Overview

• Permutations
• Strings, equality, list membership
• Symbolic differentiation

Reading: SICP 2.2.2, 2.3

Symbolic differentiation

The rules

Symbolic representation of functions

Symbolic differentiation

The rules

Definition of deriv

function deriv(exp,variable) {
   if (is_number(exp)) {
      return 0;
   } else if (is_variable(exp)) {
      return (is_same_variable(exp,variable)) ? 1 : 0;
   } else if (is_sum(exp)) {
      return make_sum(deriv(addend(exp),variable),
                      deriv(augend(exp),variable));
   } else if (is_product(exp)) {
      return make_sum(make_product(multiplier(exp),
                                   deriv(multiplicand(exp),variable)),
                      make_product(deriv(multiplier(exp),variable),
                                   multiplicand(exp)));
   } else {
      return "unknown expression type: " + exp);
}

Examples

We use (nested) lists to represent functions

//  d x+y / d x
deriv(list("+","x","y"),"x")  

//  d (0 x + 1 y) / d x
deriv(list("+", list("*", "x",0), 
                list("*", 1 ,"y")), 
      "x")          

Simplifying formulas: make_sum

function make_sum(a1,a2) {
   if (is_number_equal(a1, 0)) {
      return a2;
   } else if (is_number_equal(a2, 0)) {
      return a1;
   } else if (is_number(a1) && 
            is_number(a2)) {
      return a1 + a2;
   } else {
      return list("+",a1,a2);
}  }

Simplifying formulas: make_product

function make_product(m1,m2) {
   if (is_number_equal(m1,0) || is_number_equal(m2,0))
      return 0;
   else if (is_number_equal(m1,1))
      return m2;
   else if (is_number_equal(m2,1))
      return m1;
   else if (is_number(m1) && is_number(m2))
      return m1 * m2;
   else
      return list("*",m1,m2);
}

Summary

• Permutations
• Strings, equality, list membership
• Symbolic differentiation

Reading: SICP 2.2.2, 2.3