CPL 2-3: Higher Order Functions

목차

Abstract Syntax Tree (ASTs)

context-free syntax

  Expr.NumExt       = INT      // integer literals
  Expr.TrueExt      = [true]
  Expr.FalseExt     = [false]
  Expr.IdExt        = ID

  Expr.UnOpExt      = [([UnOp] [Expr])]
  Expr.BinOpExt     = [([BinOp] [Expr] [Expr])]

  UnOp.MIN          = [-]
  UnOp.NOT          = [not]
  UnOp.HEAD         = [head]
  UnOp.TAIL         = [tail]
  UnOp.ISNIL        = [is-nil]
  UnOp.ISLIST       = [is-list]

  BinOp.PLUS        = [+]
  BinOp.MULT        = [*]
  BinOp.MINUS       = [-]
  BinOp.AND         = [and]
  BinOp.OR          = [or]
  BinOp.NUMEQ       = [num=]
  BinOp.NUMLT       = [num<]
  BinOp.NUMGT       = [num>]
  BinOp.CONS        = [cons]

  Expr.IfExt        = [(if [Expr] [Expr] [Expr])]
  Expr.NilExt       = [nil]
  Expr.ListExt      = [(list [Expr*])]

  Expr.FdExt        = [(lambda ([ID*]) [Expr])]
  Expr.AppExt       = [([Expr] [Expr*])]
  Expr.LetExt       = [(let ([LetBind+]) [Expr])]
  LetBind.LetBind   = [([ID] [Expr])]

  Expr.RecLamExt    = [(rec-lam [ID] ([ID]) [Expr])]
  Expr.LetRecExt    = [(letrec ([LetBind+]) [Expr])]

 

 

Example 1: Converting Paret to AST

((lambda (x y) (+ x y)) 3 1)

 

 

Example 2:

((lambda (x) (+ x 1)) 2)

 

Example 3:

((lambda (x) ((lambda (x) (+ x 1)) 2)) 3)

 

 

Example 4:

(
    (rec-lam sum (n) 
        (if 
            (num= n 0)
            0
            (+ n (sum (- n 1)))
        )
    ) 
    5
)

 

 

 

Example 5:

(let (
      (x true) 
      (y false)
     ) 
     (and x y)
)

 

 

Example 6:

(letrec
  ((fib
    (lambda (n) *)
  ))
  (fib 5)
)

 

 

 

Translating Functions

Example 1:

public static int increment(int a) {
    return a + 1;
}

(lambda (a)
    (+ a 1)
)

 

 

Example 2:

public static boolean isPositive(int num) {
    if(num > 0) {
        return true;
    } else {
        return false;
    }
}

(lambda (num)
    (if
        (num> num 0)
        true
        false
    )
)

 

 

Example 3:

public static int addTwoNumbers(int a, int b) {
    if (a > 0 && b > 0) {
        return a + b;
    } else {
        return 0;
    }
}

(lambda (a b)
    (if
        (and (num> a 0) (num> b 0))
        (+ a b)
        0
    )
)

 

 

Example 4:

function maxOfThree(a, b, c) {
    if(a >= b && a >= c) {
        return a;
    } else if (b >= a && b >= c) {
        return b;
    } else {
        return c;
    }
}

(lambda (a b c)
    (cond
      ((and (or (num> a b) (num= a b)) (or (num> a c) (num= a c))) a)
      ((and (or (num> b a) (num= b a)) (or (num> b c) (num= b c))) b)
      (else c)
    )
)

 

→ if-else statements가 하나가 아니라 여러개이면 cond 사용

 

 

Example 5:

(lambda (a b c x)
    (+ (+ (* (* a x) x) (* b x)) c)
)

public static int quadraticFunction(int a, int b, int c, int x) {
    return a * x * x + b * x + c;
}

 

 

Example 6:

(lambda (cons1 cons2)
    (cons (- (head cons1) (head cons2)) nil)
)

public static Cons headSubtract(Cons cons1, Cons cons2) {
    return new Cons(cons1.head - cons2.head, null);
}

 

 

 

Translating Function Calls

Example 1:

public static int cube(int x) {
    return (x * x) * x;
}

cube(7); // => 343

((lambda (x) (* (* x x) x)) 7)

 

 

Example 2: 0-arguments method

public static int oneSixNine() {
    return 13 * 13;
}

oneSixNine(); // => 169

(
  (lambda ()
     (* 13 13)
  )
)

 

 

 

Example 3:

public static int arithmetics(int x, boolean flag) {
    if (flag) {
        return x - 3;
    } else {
        return 2 * x;
    }
}

arithmetics(21, false); // => 42

(
  (lambda (x flag)
      (if
         (and flag true)
         (- x 3)
         (* 2 x)
       )
  )
  21 false
)

 

 

→ Function call 하려면 outer parenthesis 만들고 거기다가 arguments 대입.

 

 

Example 4:

function helper(a) {
    if (a > 3) {
        return true;
    } else {
        return false;
    }
}

function doubleOrTriple(a, b) {
    if(b) {
        return 2 * a;
    } else {
        return 3 * a;
    }
}

doubleOrTriple(10, helper(4)); // => 20

(
  (lambda (a b)
      (if
         b
         (* 2 a)
         (* 3 a)
      )
  )
  10 (
      (lambda (a)
         (if
            (num> a 3)
            true
            false
         )
      )
      4
     )
)

 

 

 

Paret  ↔  Java

Example 1:

(let (
      (a 4)
      (b 3)
     )
     (if
         (num> a b)
         true
         false
     )
)

int a = 4;
int b = 3;

if (a > b) {
    return true;
} else {
    return false;
}

 

 

Example 2:

int num1 = 13;
int fortyTwo = 42;

if (num1 < fortyTwo) {
    return num1 + fortyTwo;
} else {
    return fortyTwo - num1;
}

(let (
      (num1 13)
      (fortyTwo 42)
     )
     (if
         (num< num1 fortyTwo)
         (+ num1 fortyTwo)
         (- fortyTwo num1)
     )
)

 

 

Example 3:

(let ((sheep (lambda (x y) (if (num< x y) x y)))
      (bleat 3)
      (baa 5)
     )
     (sheep bleat baa)
)

public int sheep(int x, int y) {
    if (x < y) {
        return x;
    } else {
        return y;
    }
}

int bleat = 3;
int baa = 5;

sheep(bleat, baa); // => 3

 

 

Example 4:

(let ((a 41) (b 42))
     (
       (lambda (x)
           (+ (+ a b) x)
       )
       10
     )
)

int a = 41;
int b = 42;

public int helper(int x) {
    return a + b + x;
}

helper(10); // => 93

 

 

Example 5:

(let (
      (negate (lambda (input) (not input)))
      (var1 true)
      (var2 false)
     )
     (negate (or var1 var2))
)

public boolean negate(boolean input) {
    return !input;
}

boolean var1 = true;
boolean var2 = false;

negate(var1 || var2); // => false

 

 

 

Example 6:

(let ((x 5))
    (+ x 1)
)

 

How can you transform this let expression into a lambda with application, such that both return the same result?

(
  (lambda (x)
     (+ x 1)
  )
  5
)

 

 

Example 7:

Describe a (simple) rule which takes an arbitrary let (with one variable) and turns it into an applied lambda.
Let(LetBind(Id, Value), Body) -> App(Lambda(Id, Body), Value)

→ 즉, lambda 함수를 만들고 variable을 함수의 input으로 한다.

 

 

Example 8:

(let 
    (
        (nand 
            (lambda (x y) 
                (not (and x y))
            )
        )
    )
    (nand false false)
)

public static boolean nand(boolean x, boolean y) {
    return !(x && y);
}

nand(false, false);

 

 

 

Evaluation

Example 1:

(let
    (
        (x 24)
        (f (lambda (y) (- y 14)))
    )
    (f x)
)

Step 1: Variables of let: let has two variables,  x = 24 and f as a function.

Step 2: The body of the let applies the function f on x.

Step 3: Substitute the values of f and x.

((lambda (y) (- y 14)) 24)

Step 4: Replace the argument and evaluate.

(- 24 14)

 

 

Example 2:

(let 
    (
        (arbitraryFunction 
            (lambda 
                (x y z)
                (+ x (- 2 (* y z)))
            )
        )
    )
    (arbitraryFunction 2 3 4)
)

Step 1: The variable arbitraryFunction stores a function. 

Step 2: The body of the let: Applies arbitraryFunction on 3 arguments, 2 3 4.

Step 3: Replace the variable arbitraryFunction with the actual body of the function

(
    (lambda 
        (x y z)
        (+ x (- 2 (* y z)))
    )
    2 3 4
)

Step 4: Replace the arguments 

(+ 2 (- 2 (* 3 4)))

 

 

 

Example 3:

(let
    (
        (a true)
        (b true)
    )
    (let
        (
            (booleanOps
                (lambda 
                    (x y)
                    (and x (or (not y) y))
                )
            )
        )
        (booleanOps a b)
    )
)

Step 1: Outermost let has two variables, a = true, b = true

Step 2: Inner let is a function.

Step 3: Replace the variables

(
    (lambda 
        (x y)
        (and x (or (not y) y))
    )
    true true
)

Step 4: Substitute the parameters with its arguments

(and true (or (not true) true))

 

 

 

Example 4:

(
    (lambda (a b)
        (if (and (num> a 2) (num< b 12))
            (let
                (
                    (square (lambda (x) (* x x)))
                    (q 2)
                )
                (square q)
            )

            (let
                (
                    (r (lambda (y) (+ y y)))
                )
                (r a)
            )
        )
    )
    4 8
)

Step 1: It's a function that takes two parameters, a and b. The arguments are a = 4, b = 8

Step 2: if가 true이므로, 첫번째 let만 evaluate.

Step 3: 첫번째 let은 square 함수고, parameter는 q. 

Step 4:

((lambda (x) (* x x)) 2)

Step 5: 4

 

 

Mandatory Assignment

Example 1:

 

import java.util.NoSuchElementException
import scala.collection.mutable.ListBuffer

object Solution {

    /**
     * Define the function lengths(xs), which returns a list of the lengths of the strings in the list xs.
     * Example: if the input is List("I", "took", "a", "quick", "glimpsing", "at", "bright", "stars"),
     * the output should be List(1, 4, 1, 5, 9, 2, 6, 5).
     *
     * Hint: ListBuffer is a mutable list in Scala that allows appending elements.
     *
     * You MUST use loops and CANNOT use high-order functions.
     */
    def lengths(xs: List[String]): List[Int] = {
        val buf = ListBuffer[Int]()
        for (i <- 0 until xs.length) {
            buf.append(xs(i).length)
        }   
        buf.toList
    }
}

 

설명:

우선 ListBuffer [Int] 형인 ListBuffer를 만든다 (append가 가능하므로).

그리고, for-loop을 이용해서 이 리스트에 문자열 길이를 append하고 마지막에 toList를 함으로서 ListBuffer [Int]를 List [Int]로 바꿔준다.

 

 

Example 2:

import java.util.NoSuchElementException

object Solution {

    /**
     * Define the function lengths(xs), which returns a list of the lengths of the strings in the list xs.
     * Example: if the input is List("I", "took", "a", "quick", "glimpsing", "at", "bright", "stars"),
     * the output should be List(1, 4, 1, 5, 9, 2, 6, 5).
     *
     * You MUST use a high-order function and you CANNOT use loops.
     *
     * After you solve this exercise using high-order function, compare your solution to the one you made
     * in the previous assignment using mutation and loops.
     */
    def lengths(xs: List[String]): List[Int] = {
        xs.map(x => x.length)
    }

    /**
     * Define the function longWords(words), which returns the words that have more than 5 characters.
     *
     * You MUST use a high-order function and you CANNOT use loops.
     */
    def longWords(words: List[String]): List[String] = {
        words.filter(_.length > 5)
    }

    /**
     * Define the function maximum(numbers), which uses foldLeft to return the highest number
     * in the given list of non-negative numbers, and -1 if the list is empty.
     *
     * You MUST use a high-order function and you CANNOT use loops.
     */
    def maximum(numbers: List[Int]): Int = {
        numbers.foldLeft(-1)((acc, num) => if (num > acc) num else acc)
    }
}

 

 

 

Example 3:

import java.util.NoSuchElementException

object Solution {
    /**
      * EXERCISE:
      * Define your own version of map! Loops are prohibited, so use recursion.
      */
    def myMap[A,B](xs: List[A], f: (A => B)): List[B] = xs match {
        case Nil          => throw new RuntimeException("Not yet implemented")
        case head :: tail => throw new RuntimeException("Not yet implemented")
    }


    /**
      * EXERCISE:
      * Take a look at the takeWhile function:
      * https://www.scala-lang.org/api/current/scala/collection/immutable/List.html#takeWhile(p:A=%3EBoolean):List[A]
      *
      * Define the function takeWhileSmallerThanFive, it should take a list and return the first n
      * elements, until the next element (n+1) is greater or equal to 5.
      *
      * Use the takeWhile function!
      * Loops are prohibited!
      */
    def takeWhileSmallerThanFive(xs: List[Int]): List[Int] = {
        throw new RuntimeException("Not yet implemented")
    }

    /**
      * EXERCISE:
      * Define the function dropWhileSmallerThanFive, it should take a list and discard the first n
      * elements, until the next element (n+1) is greater or equal to 5.
      *
      * Again, use one of Scala's built-in list functions.
      * Loops are prohibited!
      */
    def dropWhileSmallerThanFive(xs: List[Int]): List[Int] = {
        throw new RuntimeException("Not yet implemented")
    }

    /**
      * Take a look at the zip function:
      * https://www.scala-lang.org/api/current/scala/collection/immutable/List.html#zip[B](that:scala.collection.GenIterable[B]):List[(A,B)]
      *
      * This function connects two lists by 'zipping' elements into tuples:
      */
    List(1,2,3,4).zip(List(2,4,6,8)) // = List( (1,2), (2,4), (3,6), (4,8) )

    /**
      * EXERCISE:
      * Define zipWith. It should zip two lists, but instead of zipping elements into a tuple,
      * it should use a function to combine two elements.
      *
      * Example: zipWith(List(1, 2, 3),
      *                  List(10, 11, 12),
      *                  (x: Int, y: Int) => x+y)
      * Should return: List(11,13,15)
      *
      * Hint: use map and zip.
      *
      * Loops are prohibited!
      */
    def zipWith[A,B,C](xs: List[A], ys: List[B], f: (A, B) => C): List[C] = {
        throw new RuntimeException("Not yet implemented")
    }
}

import java.util.NoSuchElementException

object Solution {
    /**
      * EXERCISE:
      * Define your own version of map! Loops are prohibited, so use recursion.
      */
    def myMap[A,B](xs: List[A], f: (A => B)): List[B] = xs match {
        case Nil          => Nil
        case head :: tail => f(head) :: myMap(tail, f)
    }


    /**
      * EXERCISE:
      * Take a look at the takeWhile function:
      * https://www.scala-lang.org/api/current/scala/collection/immutable/List.html#takeWhile(p:A=%3EBoolean):List[A]
      *
      * Define the function takeWhileSmallerThanFive, it should take a list and return the first n
      * elements, until the next element (n+1) is greater or equal to 5.
      *
      * Use the takeWhile function!
      * Loops are prohibited!
      */
    def takeWhileSmallerThanFive(xs: List[Int]): List[Int] = {
        xs.takeWhile(_ < 5)
    }

    /**
      * EXERCISE:
      * Define the function dropWhileSmallerThanFive, it should take a list and discard the first n
      * elements, until the next element (n+1) is greater or equal to 5.
      *
      * Again, use one of Scala's built-in list functions.
      * Loops are prohibited!
      */
    def dropWhileSmallerThanFive(xs: List[Int]): List[Int] = {
        xs.dropWhile(_ < 5)
    }

    /**
      * Take a look at the zip function:
      * https://www.scala-lang.org/api/current/scala/collection/immutable/List.html#zip[B](that:scala.collection.GenIterable[B]):List[(A,B)]
      *
      * This function connects two lists by 'zipping' elements into tuples:
      */
    List(1,2,3,4).zip(List(2,4,6,8)) // = List( (1,2), (2,4), (3,6), (4,8) )

    /**
      * EXERCISE:
      * Define zipWith. It should zip two lists, but instead of zipping elements into a tuple,
      * it should use a function to combine two elements.
      *
      * Example: zipWith(List(1, 2, 3),
      *                  List(10, 11, 12),
      *                  (x: Int, y: Int) => x+y)
      * Should return: List(11,13,15)
      *
      * Hint: use map and zip.
      *
      * Loops are prohibited!
      */
    def zipWith[A,B,C](xs: List[A], ys: List[B], f: (A, B) => C): List[C] = {
        val zipped = xs.zip(ys)
        zipped.map{ case (a, b) => f(a, b)}
    }
}

 

 

 

중요

기본 Higher-Order Functions

map(f): Returns a new list where the function f has been applied to all elements of the list. 

Example: List(1, 2, 3).map(_ + 1) returns List(2, 3, 4).

 

filter(p): Returns a new list, with only the elements that satisfy the predicate p. 

Example: List(1, 2, 3).filter(_ > 2) returns List(3).

 

foldLeft(start)(f): Combines all elements into one return value. It first applies the function f to the start value and the first element of the list, the applies f to the result of that and the second element of the list, and so on. This function goes from left to right through the list.

Example: List(3, 5, 7).fold(0)(_ + _) returns the sum of the list: 15. (It first calculates 0 + 3 = 3, then 3 + 5 = 8, then 8 + 7 = 15.)