Early Development of Functional Languages in AI
In the early days of AI research, symbolic computing and handling symbols were essential. Functional languages like LISP emerged, emphasizing recursion and functions over imperative statements. Explore the origins, features, and functional forms of LISP in this enlightening journey through the history of programming languages.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Functional Languages Early in AI research, there was a need for symbolic computing handling symbols instead of numbers or strings parsing input recursion A functional approach was taken programs would comprise functions and function calls, utilizing recursion as much as possible rather than a series of imperative statements with local variables, controlled through loops The earliest functional language was not LISP, but LISP was the successful language to come out of this research We will only study LISP for now, we will return to chapter 15 and other function languages later in the semester
LISP Purely functional language originally later, picked up many imperative features (loops, go to statements, local vars, etc) Interpreted although compilers later became available leading to the ability to develop programs in a piecemeal fashion Initially dynamically scoped, later statically scoped we explore this later in the semester but basically we much prefer statically scoped variables Uses only implicit heap dynamic variables this means all variables are implicitly allocated and deallocated and are pointers (like Java reference variables, no explicit dereferencing required or allowed) all variables are typeless meaning that a variable can store any type at any time
Functional Forms A function maps from a domain set to a range set the legal values of the two sets is determined by the function A functional form is a higher-order function, that is, a function that applies to functions this can either be a function that accepts a function as a parameter, or a function that returns a function these are important in Lisp as they allow functions to generate new functions (that is, code that can produce code) Construction a functional form in which the result of one function is applied to a second function (nested functions) example: f(x) = x + 2, g(x) = 3 * x, h(x) = f o g = f(g(x)) = 3*(x+2) Apply to all a functional form in which the function is applied to a list of parameters, returning a list of values example: (using f from above) apply(f(2, 5, 12)) = (4, 10, 14)
LISP Variables In early LISP, there were no local variables, only parameters passed to functions Variables/parameters point at their data, early LISP only had two items that could be pointed to atoms literal values denoted as atom as in a or buckeye or red) don t confuse these items with strings literal values can also include T (true) and nil (the opposite of T) and a number lists a linked list storing atoms and sublists, or the value nil lists are embedded in ( ) example lists (A B C D E) (A B C (D E)) (A (B C D) E) ( ) this is the empty list, or nil
LISP Functions All function calls are embedded in ( ) The first item in any function call is the function name, this LISP uses prefix notation function call: (function_name param1param2 ) examples: (+ 5 7) returns 12 (cube x) returns x3 (equal? a b) returns T (true) if a = b, nil (false) otherwise (/ (+ a b) (- c d)) returns (a + b) / (c d) note the nested parens, this will take some getting used to! Functions can also be written as Lambda expressions a Lambda expression is an unnamed function in which the parameter(s) is(are) specified after the function e.g. (lambda (x) (* x x)) (5) 25
Representing Lists Each list node consists of a node data structure consisting of two pointers, the CAR points to the item being stored in that node, the CDR points to the next node CAR and CDR are historical, named after registers in an early machine that ran Lisp CDR CAR ( A ( D E F ) B C ) A B C The CDR of a node can be equal to nil (equivalent to null or NULL in Java and C) C s & F s CDRs are nil D E F
Lisp and the Eval Function Lisp s primary function is EVAL which evaluates a list or atom at run-time EVAL when applied to the function calls the function passing it the parameters that make up the rest of the list the EVAL function is what makes LISP interpreted the evaluation is done by taking the cdr of the list and applying it to the car of the list original Lisp was supposed to be similar to FORTRAN in its appearance, but this was not practical lists are known as s-expressions (symbolic expressions) and can represent either data or functions
Example Math Functions in LISP 42 returns 42 (* 3 7) returns 21 (+ 5 7 8) returns 20 (- 5 6) returns -1 (- 15 7 2) returns 6 (% 5 3) returns 2 (> 5 6) returns nil (false) (- 24 (* 4 3)) returns 12 (= 5 (+ 2 3)) returns t (true) (* (+ 5 4) (- 8 (/ 6 2)) returns 45
Quotes As seen in the last slide, entering 42 returns 42 Similarly, entering 42 returns 42 What about entering A? if A is a variable with a value, that value is returned, otherwise you get an error Entering A returns A (the atom) The quote mark means use this literally rather than evaluate this imagine we want to define a list, (1 2 3 4 5), if we enter this, LISP tries to evaluate this as applying the function 1 to the parameters 2, 3, 4 and 5 and since 1 is not a function, you get an error to define a list, use (1 2 3 4 5) aside from prefix notation, quoting is often one of the most challenging aspects of dealing with LISP
Variables vs. Symbols and Lists Variables point to data items which are either atoms or lists (Common Lisp also has a number of data structures that variables can point to) Unless the atom is a number, T or nil, you must quote it there is a quote function you could use, so instead of A, you could use (QUOTE A) in fact, is just a shortcut for using (QUOTE ) note that LISP also uses the ` (back quote) but for a special purpose dealing with macros, something we won t cover A list must be quoted unless you are generating it, we look at how to generate lists shortly Note that you can quote a function call as in (+ 3 5) this does not return 8, instead it literally returns a list of three atoms, +, 3, 5 we could evaluate this by doing (EVAL (+ 3 5)) which would return 8
Common LISP The textbook covers Scheme, a 1970s dialect of LISP which added all kinds of useful features, and then Common Lisp We concentrate on CL only, skipping Scheme as CL is the better language developed in the 1984 that added classes to make LISP an OOPL not only is CL a better language, but there are a number of Common Lisp interpreters and compilers available, not as many for Scheme CL is roughly equivalent to C++ in terms of power and complexness
Common Lisp Incorporates features of many earlier Lisps including Scheme around 1988, CLOS (the Common Lisp Object System) was added to CL creating a hybrid OOP+functional language Common Lisp uses static scoping as its default but allows for dynamic scoping Common Lisp includes a full range of built-in data types including arrays, records, complex # s, strings, classes powerful I/O operations including streams and formatted I/O imperative features including a wide variety of control structures exception handling (several different forms)
Some Functions in CL CAR content of address register returns first item of a list, this could be a sublist or an atom CDR content of decrement register returns remainder of list CDR always returns a list or nil if the parameter passed to CDR is the last item in a list EQ equal used for atoms or pointers returns T or nil EQUAL equal for atoms or lists, the difference is that EQUAL will compare what two variables are pointing to, much like the difference between x == y and x.equals(y) in Java if A is the list (1 2 3) then (EQ A (1 2 3)) returns nil while (EQUAL A (1 2 3)) returns T
More CL Functions MEMBER membership is a given item in this list? in LISP and Scheme, this returns T or nil but in CL, it returns the portion of the list starting at the matching item, or nil (MEMBER 3 (1 2 3 4)) returns the list (3 4) ATOM is the datum an atom? (T or nil) LISTP is the datum a list? (T or nil) P stands for Predicate meaning T/nil NULL is the datum a nil pointer or something? (T or nil) EVENP, ODDP, ZEROP self explanatory (T or nil) =, <>, <, >, <=, >= self explanatory (T or nil) operates on numbers only
More Functions PRINT to print out the item assume A points to 5 (PRINT A) outputs 5 (PRINT (+ A 3)) outputs 8 CONS a list constructor (covered shortly) LIST an alternative list constructor (returns a list) assume A points to apple, B points to banana and C points to cherry (LIST A B C) returns the list (apple banana cherry) (LIST (LIST A) (LIST B) (LIST C)) returns ((apple) (banana) (cherry)) APPEND append lists (all params must be lists) (APPEND (LIST A) (LIST B C)) returns (apple banana cherry)
Conditional Statements IF statement has the form (IF (condition) (then clause) (else clause) ) returns whatever the then clause or else clause returns note that if the then or else clause is not a function but just an atom, don t put it in ( ) example: (if (> A B) (* A B) 0) returns A * B if A > B and 0 otherwise the else clause is optional COND conditional statement used like a nested if-else structure (covered shortly)
Assignment There are there functions, SET, SETQ and SETF basically we want to use SETF for everything because its most flexible, but let s see why (we will ignore SET) First, the format: (SETQ variable value) value will either be another variable, an atom (quoted), a list (quoted) or the result of a function call (SETQ X 5) (SETQ X apple) (SETQ X (1 2 3 4)) (SETQ X Y) // assumes Y has a value (SETQ (+ A (* B 3)) // assumes A and B have numeric values SETF literally stands for set field assume X is the list (1 2 3) (SETQ (CAR X) 5) (SETF (CAR X) 5) Both instructions permit multiple assignments as in (setf a 5 b apple c T) // error // changes X to be (5 2 3)
Types of Functions All functions return a value mathematical functions return atoms or numerical values predicate functions return T or NIL MEMBER is an exception in that it returns a sublist or NIL LIST and CONS return lists COND and IF return the value of the function executed based on which condition was true SETQ/SETF are functions that return the value being assigned but have a side effect of redirecting the variable s pointer to point at the second parameter if the second parameter is a literal value (atom or list), there is another side effect in that one or more nodes are dynamically allocated with values inserted appropriately for instance, (SETF X (1 2 3)) causes 3 nodes to be allocated with their CAR pointers pointing at storage locations storing 1, 2 and 3, a pointer to the first node is then returned for X to point to
The COND Function Basically a nested if-else statement without needing to say if , else , etc Syntax: (COND ((condition1) (function1)) ((condition2) (function2)) ((condition3) (function3)) ((conditionn) (functionn))) to indicate else , the last condition should be T (outside of parens) (cond ((> x 0) (sqrt x)) ((= x 0) 1) (t -1)) (* (* (- hours 40) wages) 1.5)))) (cond ((<= hours 40) (* hours wages)) (t (+ (* 40 wages)
The IF Function The IF statement has two forms (IF (condition) (function1)) if the condition evaluates to T, the function returns the value returned by function1 otherwise the IF function returns nil (IF (condition) (function1) (function2)) if the condition evaluates to T, the function returns the value returned by function1 otherwise it returns the value returned by function2 (if (<= hours 40) (* hours wages) (+ (* 40 wages) (* (* (- hours 40) wages) 1.5))) We might place the code to the left inside a (setf) as in (setf pay (if ( ) ( ) ( )))
CONS List Constructor CONS accepts two parameters and returns the list constructed by taking the first parameter and making it the CAR of a list and attaching to it the second parameter as the CDR Since the CDR must be a list, this only works if the second parameter was already a list (or NIL / ( ) ) examples: (CONS A ( ) ) returns (A) (CONS A (B C)) returns (A B C) (CONS (A) (B)) returns ((A) B) (CONS (A B) (C D)) returns ((A B) C D) (CONS A ((B C))) returns (A (B C)) A C D A B
Defining Functions Form: (DEFUN name (params) body) Functions return the last value evaluated in the function, or the last function call (DEFUN square (num) (* num num)) (DEFUN second (alist) (car (cdr alist))) if we do (second (a b c d)), it returns b (DEFUN factorial (n) (cond ((eq n 0) 1) (T (* n (factorial (- n 1)))))) (DEFUN fib (n) (if (> n 2) (+ (fib (- n 1)) (fib (- n 2))) 1)) (DEFUN foo (alist) (cond ((null alist) 0) (T (+ (foo (cdr alist)) 1)))) If n = 0, return 1, otherwise return n * factorial (n-1) What does this function do?
More CL Functions (DEFUN member (atm lis) (COND ((NULL lis) NIL) ((EQUAL atm (CAR lis)) lis) (T (member atm (CDR lis))))) (DEFUN append (lis1 lis2) (COND ((NULL lis1) lis2) (T (CONS (CAR lis1) (append (CDR lis1) lis2))))) If we call (append (A B) (C D E)) we get back (A B C D E) If we call (append ((A B) C) (D (E F))) we get back ((A B) C D (E F))
Two Similar Functions (DEFUN equalsimp (lis1 lis2) (COND ((NULL lis1) (NULL lis2)) ((NULL lis2) NIL) ((EQ (CAR lis1) (CAR lis2)) (T NIL))) (equalsimp (CDR lis1) (CDR lis2))) (DEFUN equal (lis1 lis2) (COND ((ATOM lis1) (EQ lis1 lis2)) ((ATOM lis2) NIL) ((equal (CAR lis1) (CAR lis2)) (equal (CDR lis1) (CDR lis2))) (T NIL)))
Local Variables All of our functions have operated solely on parameters Later dialects of LISP introduced local variables In Common Lisp, define local variables in a (LET) function syntax: (LET (variable list) ) to initialize a variable, use the notation (var value) or (var (functioncall)) anything in can reference the local variables in the LET function (DEFUN quadratic_roots (a b c) (LET ((root_part_over_2a (/ (SQRT (- (* b b) (*4 a c))) (* 2 a))) (minus_b_over_2a (/ (- 0 b) (* 2 a)))) (PRINT (+ minus_b_over_2a root_part_over_2a)) (PRINT (- minus_b_over_2a root_part_over_2a))))
MAPCAR Recall that in a functional language, we want to be able to pass a function as a parameter and apply that passed function to some list of data MAPCAR does this, returning the computed list MAPCAR is also known as an apply to all function (DEFUN mapcar (f lis) (COND ((NULL lis) nil) (T (CONS (f (CAR lis)) (mapcar f (CDR lis)))))) (mapcar # (LAMBDA (X) (* x (+ x 1))) (1 5 2 9)) here, f is the function (* x ( + x 1)) and we pass this and the list (1 5 2 9) to mapcar, getting back the list (2 30 6 90)
Other Common Lisp Functions PROGN allows you to create a block of instructions where global variables are unaffected by any statements in the block also allows you to have multiple instructions where only one function is called for (e.g., the if or else clause) the PROGN function returns the value returned by the last function in the block Loops: DOTIMES (DOTIMES (var number) ) (counting loop) DOLIST (DOLIST (var lis) ) (iterator loop) DO more complex, see notes section of this page, similar to C s for loop GO a goto statement Variations of CAR and CDR: CADR, CDDR, CAAR, CDAR, etc are all available
Common Lisp Data Structures struct similar to C/C++ (defstruct car year make model mileage) (setf mycar (make-car : year 2005 : model camry)) (print (car-year mycar)) the functions make-car and car-year are automatically generated when issuing the defstruct to define car (as are all other member accessing functions like car-model) (car-mileage mycar) returns nil since that member has no value yet arrays use make-array to generate an array (setf anarray (make-array (10 5)) creates a 10x5 array and points anarray at it access the array elements using (aref arrayname arrayindex(es)) as in (setf (aref anarray 3 2) 12) which sets anarray[3][2] = 12 arrays can be resized/reshaped with the old values retained
Continued strings treated as arrays of chars can be assigned using make-array or directly as in (setf name Frank Zappa ) accessed through aref and length classes added to the language in the late 80s define a class through defclass and a method through defmethod, and an object (instance) through make-instance) common lisp classes are unlike other OOPLs because methods are not necessarily tied to classes, but can be tied to specific objects there is no information hiding mechanisms like C++, common lisp classes can have multiple parents See the website for more example common lisp code We will return to functional languages later in the semester and examine F# in detail
