Untitled

FUNCTIONAL PROGRAMMING LANGUAGES

• Definition:
    - Imperative Languages:
      - Designed based on the von Neumann architecture.
      - Efficiency is prioritized over software development suitability.
    - Functional Languages:
      - Grounded in mathematical functions, emphasizing a theoretical foundation and user-friendliness without a focus on machine architecture.

MATHEMATICAL FUNCTIONS

• Definition of a Mathematical Function:
    - A function maps members from one set (domain set) to another set (range set).
• Lambda Expressions:
    - Describe nameless functions and take the form:
  $l(x) = x * x * x$

LAMBDA EXPRESSIONS

• Application of Lambda Expressions:
    - Applied to parameters by placing them after the expression, e.g.,
      (l(x) ext{ where } l(x) = x * x * x)(2) ightarrow 8

FUNCTIONAL FORMS

• Definition of Higher-order Function:
    - A higher-order function or functional form either takes functions as parameters or yields a function as a result, or both.

FUNCTION COMPOSITION

• Definition:
    - A functional form that takes two functions as parameters and yields a function with the value of the first function applied to the second.
• Formulation:
    - Notated as:
  $h ext{º} f ext{°} g$
      where computing $h(x) ext{º} f(g(x))$
    - For example:
      If $f(x) = x + 2$ and $g(x) = 3 * x$, then $h ext{º} f ext{°} g$ yields $(3 * x) + 2$.

APPLY-TO-ALL

• Definition:
    - A functional form that takes a function as a parameter and applies it to each member of a list.
• Formulation:
    - For instance:
  $a(h, (2, 3, 4))$ yields the result of applying $h(x) = x * x$ resulting in $(4, 9, 16)$.

FUNDAMENTALS OF FUNCTIONAL PROGRAMMING LANGUAGES

• Objectives of FPL Design:
    - To closely mimic mathematical functions.
• Differences from Imperative Languages:
    - In imperative programming, operations produce results stored in variables, causing complexity.
    - FPLs do not rely on variables, as seen in mathematics.
• Referential Transparency:
    - In FPL, the evaluation of a function consistently produces the same result when supplied with identical arguments.

LISP

• Origin:
    - Developed by John McCarthy at MIT in 1959.
• Data Objects Categories:
    - Consists of atoms and lists.
    - Lists consist of pairs; the first part is data, the second part can be more complex structures.
• Examples of Lists:
    - Simple list:
  $(A B C D)$
    - Nested list structure:
  $(A (B C) D (E (F G)))$

LISP INTERPRETATION

• Functions' Representation:
    - Lambda notation specifies function definitions.
    - Function applications and data share the same format.
    - Example:
      - Data: $(A B C)$ as a list of atoms.
      - Function Application: If interpreted as a function, it indicates that $A$ functions with parameters $B$ and $C$.

ORIGINS OF SCHEME

• Definition and Purpose:
    - A dialect of LISP from the mid-1970s aimed at simplifying and modernizing its features.
• Scoping:
    - Only static scoping is utilized.
• Functions:
    - Functions treated as first-class entities; can be values in expressions, assigned to variables, and elements in lists.

THE SCHEME INTERPRETER

• Definition:
    - An interactive Scheme interpreter operates in an infinite read-evaluate-print loop (REPL).
• Functionality:
    - Repeatedly reads user input as a list, interprets, and displays the resultant value, similar to Ruby and Python's behavior.

PRIMITIVE FUNCTION EVALUATION

• Literals:
    - Evaluate to their representation, e.g., typing a number returns the number itself.
• Calling of Primitive Functions:
    - Each parameter expression evaluated first, in no specific order, then the primitive function is applied to these evaluated values.

PRIMITIVE NUMERIC FUNCTIONS

• Basic Functions Included:
    - Include $+, - , imes, /$ for arithmetic operations.
    - Both $*$ and $+$ can have zero or more parameters.
    - Special cases:
      - $*$ returns 1 if no parameters.
      - $+$ returns 0 if no parameters.

EXTRA NUMERIC FUNCTIONS IN SCHEME

• Examples:
    - Include MODULO, ROUND, MAX, MIN, LOG, SIN, SQRT.
• Parameter Constraints:
    - Functions with fixed parameters require matching inputs; otherwise, yield errors.

DEFINING FUNCTIONS

• Function Definition Overview:
    - A Scheme program consists of function definitions.
• Lambda Expression Example:
    - Syntax:
  $(LAMBDA (x) (* x x))$ returns the function the squares its input.
    - Example Usage:
      - $( (LAMBDA (x) (* x x)) 7 )$ yields 49 with $x$ as a bound variable.

SPECIAL FORM FUNCTION: DEFINE

• Usage:
    - Two forms:
      - Bind a symbol to an expression, e.g.,
  $(DEFINE ext{ pi } 3.141593)$
      - Bind names to lambda expressions.
• Function Binding Example:
    - $(DEFINE (square x) (* x x))$ binds the function square.
• Hypotenuse Function Definition:
    - $(DEFINE (hypotenuse side1 side2) ( ext{SQRT}(+(square side1)(square side2))))$ computes the hypotenuse from two sides.

OUTPUT FUNCTIONS

• Output in Scheme:
    - PRINTF performs as printf in C.
    - Note: input/output are considered side effects; they break the pure functional model.

NUMERIC PREDICATE FUNCTIONS

• Definition:
    - Returns Boolean values, either true (#T) or false (#F).
    - Naming convention: predicate functions typically end with a question mark.

FUNCTION RELATIONS

• Table of Functions and Meanings:
    | Function | Meaning |
    |----------|---------|
    | = | Equal |
    | <> | Not equal |
    | < | Less than |   | >= | Greater than or equal to |
    | EVEN? | Is it an even number? |
    | ODD? | Is it an odd number? |
    | ZERO? | Is it zero? |
  
• Boolean Evaluation in Lists:
    - Non-empty lists are true; empty lists are false.

CONTROL FLOW

• Constructs in Scheme:
    - Three constructs are used:
      - Selection construct (similar to imperative languages),
      - Evaluation control (based on mathematical functions),
      - Recursion.

IF CONSTRUCT IN SCHEME

• Structure of IF Function:
    - Parameters include:
      - Predicate Expression
      - Then Expression
      - Else Expression
    - Example Structure:
      - $(IF ext{ predicate } ext{ then_expression } ext{ else_expression })$
• Factorial Example:
    - $(DEFINE (factorial n)$
  $(IF (<= n 1) 1 (* n (factorial (- n 1))))$

QUOTE FUNCTION

• Purpose:
    - This function prevents evaluation of its parameter.
    - Examples:
      - (QUOTE A) ightarrow A
      - (QUOTE (A B C)) ightarrow (A B C)
      - Alternative notation: For $(QUOTE (A B))$, one can use $(‘(A B))$.

CAR & CDR FUNCTIONS

• CAR Function:
    - Takes a list and returns its first element.
    - Examples:
      - (CAR '(A B C)) ightarrow A
      - (CAR '((A B) C D)) ightarrow (A B)

• CDR Function:
    - Takes a list and returns the list excluding its first element.
    - Examples:
      - (CDR '(A B C)) ightarrow (B C)
      - (CDR '((A B) C D)) ightarrow (C D)

CONS FUNCTION

• Definition:
    - Takes two parameters: an atom or list and a list, returning a new list with the first parameter as the first element.
• Example:
    - (CONS 'A '(B C)) ightarrow (A B C)

LIST FUNCTIONS

• Second Function Example:
    - $(DEFINE (second a_list) (CAR (CDR a_list)))$ yields the second element of the list.
    - Example:
      - (second '(A B C)) ightarrow B

LIST FUNCTION FOR BUILDING LIST

• Definition of LIST:
    - Builds a list from multiple parameters, e.g.,:
      - (LIST 'apple 'orange 'grape) ightarrow (apple orange grape)

PREDICATE FUNCTIONS FOR SYMBOLIC ATOMS AND LISTS

• Fundamental Functions:
    - EQ?:
      - Compares pointer values of symbolic atoms.
      - Example:
        - (EQ? 'A 'A) ightarrow #T
        - (EQ? 'A 'B) ightarrow #F
    - EQV?:
      - Similar to EQ?, but works on both symbolic and numeric atoms, focusing on value comparison.
    - LIST?:
      - Returns #T if the parameter is a list; otherwise #F.
    - NULL?:
      - Returns #T if the parameter is an empty list; otherwise #F.

EXAMPLE SCHEME FUNCTION: MEMBER

• MEMBER Function:
    - Takes an atom and a list; checks for existence in the list.
• Implementation Example:
    - $(DEFINE (member atm a_list)$
  $(COND$
      (NULL? a_list) #F
      (EQ? atm (CAR a_list)) #T
  $(ELSE (member atm (CDR a_list))))$

LET FUNCTION

• Definition:
    - Allows defining names for expressions.
• Structure:
    - First evaluate the expressions, then evaluate the final expression.
• Example:
    - $(LET ((top (+ a b)) (bottom (- c d))) (/ top bottom))$

TAIL RECURSION IN SCHEME

• Definition:
    - A function is tail recursive if its recursive call is the final operation, returning the result from the call directly.
• Efficiency:
    - Tail recursive functions are more memory efficient, requiring only a single activation record instance.
    - Example of Tail Recursion:
      Original:
      (DEFINE (factorial n)
        (IF (<= n 1)
            1
            (* n (factorial (- n 1))))
  
      Rewritten to Tail Recursive:
      (DEFINE (facthelper n factpartial)
        (IF (<= n 1)
            factpartial
            (facthelper (- n 1) (* n factpartial))))
      Then define it using tail recursion:
  $(DEFINE (factorial n) (facthelper n 1))$

FUNCTIONAL LANGUAGES AND IMPERATIVE LANGUAGES

• Comparison of Functional vs. Imperative Languages:
    - Imperative Languages:
      - Efficient execution
      - Complex semantics
      - Complex syntax
      - Concurrency is programmer-designed
    - Functional Languages:
      - Simpler semantics and syntax
      - Less efficient execution
      - Programs can be auto-parallelized for concurrency.
    - Usefulness and Adoption:
      - Functional programming paradigms are sometimes seen as foreign and complex for those comfortable in imperative programming.
      - Despite the advantages, functional languages still do not enjoy widespread adoption.