Difference between revisions of "LISP"

From ACSL Category Descriptions
Jump to navigation Jump to search
Line 1: Line 1:
== Oneline Interpreters ==
LISP is one of the simplest computer languages in terms of syntax and semantics, and also one of the most powerful.  It was developed in the mid-1950’s by John McCarthy at M.I.T. as a “LISt Processing language.”  It has been historically used for virtually all Artificial Intelligence programs and is often the environment of choice for applications which require a powerful interactive working environment.  LISP presents a very different way to think about programming from the “algorithmic” languages, such as Python, C++, and Java.
 
== Syntax ==
 
As its name implies, the basis of LISP is a list.  One constructs a list by enumerating elements inside a pair of parentheses.  For example, here is a list with four elements (the second element is also a list):
 
:<code>(23 (this is easy) hello 821)</code>
 
The elements in the list, which are not lists, are called “atoms.”  For example, the atoms in the list above are: 23, ‘this, ‘hello, 821, ‘easy, and ‘is.  Literals are identified with a single leading quote.  Everything in LISP is either an atom or a list (but not both).  The only exception is “NIL,” which is both an atom and a list.  It can also be written as “()” – a pair of parentheses with nothing inside.
 
All statements in LISP are function calls with the following syntax: (function arg1 arg2 arg3 … argn).  To evaluate a LISP statement, each of the arguments (possibly functions themselves) are evaluated, and then the function is invoked with the arguments.  For example, (MULT (ADD 2 3) (ADD 1 4 2)) has a value of 35, since (ADD 2 3) has a value of 5, (ADD 1 4 2) has a value of 7, and (MULT 5 7) has a value of 35.  Some functions have an arbitrary number of arguments; others require a fixed number.  All statements return a value, which is either an atom or a list.
 
== Basic Functions (SET, SETQ, EVAL, ATOM) ==
 
We may assign values to variables using the function SET.  For example, the statement (SET ’test 6) would have a value of a 6, and (more importantly, however) would also cause the atom ‘test to be bound to the atom 6.  Observe the following examples:
 
TABLE
 
The function SETQ is the same as SET, but it causes LISP to act as if the first argument was quoted.  The function EVAL returns the value of its argument, after it has been evaluated.  For example, (SETQ z ’(ADD 2 3)) has a value of the list (ADD 2 3); the function (EVAL ’z) has a value of (ADD 2 3); the function (EVAL z) has a value of 5 (but the binding of the atom z has not changed).  In this last example, you can think of z being “resolved” twice: once because it is an argument to a function and LISP evaluates all arguments to functions before the function is invoked, and once when the function EVAL is invoked to resolve arguments.  The function ATOM can be used to tell whether an item is an atom or a list.  Consider the following examples:
 
TABLE
 
== List Functions (CAR, CDR, REVERSE, CONS)==
 
The two most famous LISP functions are CAR and CDR (pronounced: could-er), named after registers of a now long-forgotten IBM machine on which LISP was first developed.  The function (CAR x) returns the first item of the list x (and x must be a list or an error will occur); (CDR x) returns the list without its first element (again, x must be a list).  The function CONS takes two arguments, of which the second must be a list.  It returns a list which is composed by placing the first argument as the first element in the second argument’s list.  The function REVERSE returns a list which is its arguments in reverse order.  The following examples illustrate the use of CAR, CDR, REVERSE, and CONS:
 
TABLE
 
== Arithmetic Functions ==
 
As you have probably deduced, the function ADD simply summed its arguments.  We’ll also be using the following arithmetic functions:
 
TABLE
 
TABLE
 
== User-defined Functions ==
 
LISP also allows us to create our own functions using the DEF function.  For example,
(DEF SECOND (parms) (CAR (CDR parms)))
defines a new function called SECOND which operates on a single parameter named “parms”.  SECOND will take the CDR of the parameter and then the CAR of that result.  So, for example:
(SECOND ’(a b c d e))
would first CDR the list (yielding (b c d e)) and then CAR the result.  So the value would be the single character “b”.  Consider the following program fragment:
(SETQ X ’(a c s l))
(DEF WHAT(parms) (CONS parms (REVERSE (CDR parms))))
(DEF SECOND(parms) (CONS (CAR (CDR parms)) NIL))
 
The following chart illustrates the use of the user-defined functions WHAT and SECOND:
 
TABLE
 
== Online Interpreters ==


There are many online LISP interpreters available on the Internet. The one that ACSL uses for testing its programs is CLISP that is accessible from  [https://www.jdoodle.com/execute-clisp-online JDoodle]. This interpreter is nice because it is quite peppy in running programs, and functions are not case sensitive. So, <code>(CAR (CDR x))</code> is legal as is <code>(car (cdr x))</code> One drawback of this interpreter is the print function changes lowercase input into uppercase.  
There are many online LISP interpreters available on the Internet. The one that ACSL uses for testing its programs is CLISP that is accessible from  [https://www.jdoodle.com/execute-clisp-online JDoodle]. This interpreter is nice because it is quite peppy in running programs, and functions are not case sensitive. So, <code>(CAR (CDR x))</code> is legal as is <code>(car (cdr x))</code> One drawback of this interpreter is the print function changes lowercase input into uppercase.  
   
   
== Sample Problems ==
Questions from this topic will typically present a line of LISP code or a short sequence of statements and ask what is the value of the (final) statement.
== Video Resources ==
== Video Resources ==



Revision as of 12:02, 16 August 2018

LISP is one of the simplest computer languages in terms of syntax and semantics, and also one of the most powerful. It was developed in the mid-1950’s by John McCarthy at M.I.T. as a “LISt Processing language.” It has been historically used for virtually all Artificial Intelligence programs and is often the environment of choice for applications which require a powerful interactive working environment. LISP presents a very different way to think about programming from the “algorithmic” languages, such as Python, C++, and Java.

Syntax

As its name implies, the basis of LISP is a list. One constructs a list by enumerating elements inside a pair of parentheses. For example, here is a list with four elements (the second element is also a list):

(23 (this is easy) hello 821)

The elements in the list, which are not lists, are called “atoms.” For example, the atoms in the list above are: 23, ‘this, ‘hello, 821, ‘easy, and ‘is. Literals are identified with a single leading quote. Everything in LISP is either an atom or a list (but not both). The only exception is “NIL,” which is both an atom and a list. It can also be written as “()” – a pair of parentheses with nothing inside.

All statements in LISP are function calls with the following syntax: (function arg1 arg2 arg3 … argn). To evaluate a LISP statement, each of the arguments (possibly functions themselves) are evaluated, and then the function is invoked with the arguments. For example, (MULT (ADD 2 3) (ADD 1 4 2)) has a value of 35, since (ADD 2 3) has a value of 5, (ADD 1 4 2) has a value of 7, and (MULT 5 7) has a value of 35. Some functions have an arbitrary number of arguments; others require a fixed number. All statements return a value, which is either an atom or a list.

Basic Functions (SET, SETQ, EVAL, ATOM)

We may assign values to variables using the function SET. For example, the statement (SET ’test 6) would have a value of a 6, and (more importantly, however) would also cause the atom ‘test to be bound to the atom 6. Observe the following examples:

TABLE

The function SETQ is the same as SET, but it causes LISP to act as if the first argument was quoted. The function EVAL returns the value of its argument, after it has been evaluated. For example, (SETQ z ’(ADD 2 3)) has a value of the list (ADD 2 3); the function (EVAL ’z) has a value of (ADD 2 3); the function (EVAL z) has a value of 5 (but the binding of the atom z has not changed). In this last example, you can think of z being “resolved” twice: once because it is an argument to a function and LISP evaluates all arguments to functions before the function is invoked, and once when the function EVAL is invoked to resolve arguments. The function ATOM can be used to tell whether an item is an atom or a list. Consider the following examples:

TABLE

List Functions (CAR, CDR, REVERSE, CONS)

The two most famous LISP functions are CAR and CDR (pronounced: could-er), named after registers of a now long-forgotten IBM machine on which LISP was first developed. The function (CAR x) returns the first item of the list x (and x must be a list or an error will occur); (CDR x) returns the list without its first element (again, x must be a list). The function CONS takes two arguments, of which the second must be a list. It returns a list which is composed by placing the first argument as the first element in the second argument’s list. The function REVERSE returns a list which is its arguments in reverse order. The following examples illustrate the use of CAR, CDR, REVERSE, and CONS:

TABLE

Arithmetic Functions

As you have probably deduced, the function ADD simply summed its arguments. We’ll also be using the following arithmetic functions:

TABLE

TABLE

User-defined Functions

LISP also allows us to create our own functions using the DEF function. For example, (DEF SECOND (parms) (CAR (CDR parms))) defines a new function called SECOND which operates on a single parameter named “parms”. SECOND will take the CDR of the parameter and then the CAR of that result. So, for example: (SECOND ’(a b c d e)) would first CDR the list (yielding (b c d e)) and then CAR the result. So the value would be the single character “b”. Consider the following program fragment: (SETQ X ’(a c s l)) (DEF WHAT(parms) (CONS parms (REVERSE (CDR parms)))) (DEF SECOND(parms) (CONS (CAR (CDR parms)) NIL))

The following chart illustrates the use of the user-defined functions WHAT and SECOND:

TABLE

Online Interpreters

There are many online LISP interpreters available on the Internet. The one that ACSL uses for testing its programs is CLISP that is accessible from JDoodle. This interpreter is nice because it is quite peppy in running programs, and functions are not case sensitive. So, (CAR (CDR x)) is legal as is (car (cdr x)) One drawback of this interpreter is the print function changes lowercase input into uppercase.

Sample Problems

Questions from this topic will typically present a line of LISP code or a short sequence of statements and ask what is the value of the (final) statement.


Video Resources

The following YouTube videos show ACSL students and advisors working out some ACSL problems that have appeared in previous contests. Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.

LISP very gentle intro (CalculusNguyenify)

A very gentle introduction to the LISP category, covering the LISP syntax and the basic operators, SETQ, ADD, SUB, MULT, and DIV.

LISP Basics (for ACSL) (Tangerine Code)

Explains the LISP operators CAR, CDR, and REVERSE, in the context of solving an ACSL All-Star Contest problem.

LISP Basics (for ACSL) (Tangerine Code)

Completes the problem that was started in the above video.