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. The function SETQ is the same as SET, but it causes LISP to act as if the first argument was quoted.
Observe the following examples:

:{| class="wikitable" style="text-align: left"
!Statement || Value || Comment
|-
|(SET ’a ( MULT 2 3))
|6
|a is an atom with a vaue of 6
|-
|(SET ’a ’(MULT 2 3))
|(MULT 2 3)
|a is a list with 3 elements
|-
|(SET ’b ’a)
|a
|b is an atom with a value of the character a
|-
|(SET ’c a)
|(MULT 2 3)
|c is a list with 3 elements
|-
|(SETQ EX (ADD 3 (MULT 2 5)))
|13
|The variable EX has a value of 13
|-
|(SETQ VOWELS ’(A E I O U))
|(A E I O U)
|VOWELS is a list of 5 elements
|}

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 determine whether an item is an atom or a list. It returns either "true", or "NIL" for false. Consider the following examples:

:{| class="wikitable" style="text-align: left"
!Statement || Value || Comment
|-
|(SETQ p '(ADD 1 2 3 4))
|(ADD 1 2 3 4)
|p is a list with 5 elements
|-
|(ATOM 'p)
|true
|The argument to ATOM is the atom p
|-
|(ATOM p)
|NIL
|Because p is not quoted, it is evaluated to the 5-element list.
|-
|(EVAL p)
|10
|The argument to EVAL is the value of p; the value of p is 10.
|}

== List Functions (CAR, CDR, CONS, REVERSE)==

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 CAR and CDR functions are used extensively to grab specific elements of a list or sublist, that there's a shorthand for this: (CADR x) is the same as (CAR (CDR x)), which retrieves the second element of the list x; (CAADDAR x) is a shorthand for (CAR (CAR (CDR (CDR (CAR x))))), and so on.

The following examples illustrate the use of CAR, CDR, CONS, and REVERSE:

:{| class="wikitable" style="text-align: left"
!Statement || Value
|-
|(CAR ’(This is a list))
|This
|-
|(CDR ’(This is a list)))
|(is a list)
|-
|(CONS 'red '(white blue))
|(red white blue)
|-
|(SETQ z (CONS '(red white blue) (CDR ’(This is a list)))))
|((red white blue) is a list)
|-
|(REVERSE z)
|(list a is (red white blue))
|-
|(CDDAR z)
|(blue)
|}

== Arithmetic Functions (ADD, MULT, ...)==

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

:{| class="wikitable" style="text-align: left"
!'''Function''' || '''Result'''
|-
|(ADD x1 x2 …)
|sum of all arguments
|-
|(SUB a b)
|a-b
|-
|(MULT x1 x2 …)
|product of all arguments
|-
|(DIV a b)
|a/b
|-
|(SQUARE a)
|a*a
|-
|(EXP a n)
|an
|-
|(EQ a b)
|true if a and b are equal, NIL otherwise
|-
|(POS a)
|true if a is positive, NIL otherwise
|-
|(NEG a)
|true if a is negative, NIL otherwise
|-
|}

Functions ADD, SUB, MULT, and DIV can be written as their common mathematical symbols, +, -, *, and /. Here are some examples of these functions:

:{| class="wikitable"
!'''Statement''' || '''Value'''
|-
|(ADD (EXP 2 3) (SUB 4 1) (DIV 54 4))
|24.5
|-
|(- (* 3 2) (- 12 (+ 1 2 1)))
| -2
|-
|(ADD (SQUARE 3) (SQUARE 4))
|25
|}

== User-defined Functions ==

LISP also allows us to create our own functions using the DEF function. (We will sometimes use DEFUN rather than DEF, as it is a bit more standard terminology.) For example,
(DEF SECOND (args) (CAR (CDR args)))
defines a new function called SECOND which operates on a single parameter named “args”. 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 to give (b c d e), and then CAR that value returning the single character “b”. Consider the following program fragment:
:(SETQ X ’(a c s l))
:(DEF WHAT(args) (CONS args (REVERSE (CDR args))))
:(DEF SECOND(args) (CONS (CAR (CDR args)) NIL))

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

:{| class="wikitable"
!Statement || Value
|-
|(WHAT X) || ((a c s l) l s c)
|-
|(SECOND X) || (c)
|-
|(SECOND (WHAT X)) || (l)
|-
|(WHAT (SECOND X)) || ((c))
|}

== 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.

== 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.

=== Problem 1 ===

Evaluate the following expression. <code>(MULT (ADD 6 5 0) (MULT 5 1 2 2) (DIV 9 (SUB 2 5)))</code>

'''Solution:'''
(MULT (ADD 6 5 0) (MULT 5 1 2 2) (DIV 6 (SUB 2 5)))
(MULT 11 20 (DIV 6 -3))
(MULT 11 20 -2)
-440

=== Problem 2 ===

Evaluate the following expression: <code>(CDR ’((2 (3))(4 (5 6) 7)))</code>

'''Solution:'''
The CDR function takes the first element of its parameter (which is assumed to be a list) and returns the list with the first element removed. The first element of the list is (2 (3)) and the list without this element is
((4 (5 6) 7)), a list with one element.

=== Problem 3 ===

Consider the following program fragment:
(SETQ X ’(RI VA FL CA TX))
(CAR (CDR (REVERSE X)))
What is the value of the CAR expression?

'''Solution:'''
The first statement binds variable X to the list ‘(RI VA FL CA TX).
The REVERSE of this list is ‘(TX CA FL VA RI)
whose CDR is ‘(CA FL VA RI). The CAR of this list is just the atom CA (without the quote).



== 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.

{|
|-
| <youtube width="300" height="180">https://youtu.be/jWFgmE279eQ</youtube>
| [https://youtu.be/jWFgmE279eQ ''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.

|-
| <youtube width="300" height="180">https://youtu.be/mRpbbss48sw</youtube>
| [https://youtu.be/mRpbbss48sw ''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.

|-
| <youtube width="300" height="180">https://youtu.be/50wj_f51kBM</youtube>
| [https://youtu.be/50wj_f51kBM ''LISP Basics (for ACSL)'' ('''Tangerine Code''')]

Completes the problem that was started in the above video.
|}

Bit-String Flicking

2019-01-09T20:27:54Z

Williamhu: /* Bitwise Operators */ Replaced 'o' with '0'

Bit strings (strings of binary digits) are frequently manipulated bit-by-bit using the logical operators '''not''', '''and''', '''or''', and '''xor'''. Bits strings are manipulated as a unit using '''shift''' and '''circulate''' operators. The bits on the left are called the ''most significant bits'' and those on the right are the ''least significant bits''.

Most high-level languages (e.g., Python, Java, C++), support bit-string operations. Programmers typically use bit strings to maintain a set of flags. Suppose that a program supports 8 options, each of which can be either “on” or “off”. One could maintain this information using an array of size 8, or one could use a single variable (if it is internally stored using at least 8 bits or 1 byte, which is usually the case) and represent each option with a single bit. In addition to saving space, the program is often cleaner if a single variable is involved rather than an array. Bits strings are often used to maintain a set where values are either in the set or not. Shifting of bits is also used to multiply or divide by powers of 2.

Mastering this topic is essential for systems programming, programming in assembly language, optimizing code, and hardware design.

== Operators==

=== Bitwise Operators ===

The logical operators are '''not''' (~ or $\neg$), '''and''' (&), '''or''' (|), and '''xor''' ($\oplus$). These operators should be familiar to ACSL students from the [[Boolean Algebra]] and [[Digital Electronics]] categories.

* '''not''' is a unary operator that performs logical negation on each bit. Bits that are 0 become 1, and those that are 1 become 0. For example: ~101110 has a value of 010001.

* '''and''' is a binary operator that performs the logical '''and''' of each bit in each of its operands. The '''and''' of two values is 1 only if both values are 1. For example, '''1011011 and 011001''' has a value of '''001001'''. The '''and''' function is often used to isolate the value of a bit in a bit-string or to clear the value of a bit in a bit-string.

* '''or''' is a binary operator that performs the logical '''or''' of each bit in each of its operands. The '''or''' of two values is 1 only if one or both values are 1. For example, '''1011011 or 011001''' has a value of '''111011'''. The '''or''' function is often use to force the value of a bit in a bit-string to be 1, if it isn't already.

* '''xor''' is a binary operator that performs the logical '''xor''' of each bit in each of its operands. The '''xor''' of two values is 1 if the values are different and 0 if they are the same. For example, 1011011 xor 011001 = 110010. The '''xor''' function is often used to change the value of a particular bit.

All binary operators (and, or, or xor) must operate on bit-strings that are of
the same length. If the operands are not the same
length, the shorter one is padded with 0's on the left as needed. For
example, '''11010 and 1110''' would have value of '''11010 and 01110 = 01010'''.

The following table summarizes the operators:

::{| class="wikitable" style="text-align: center"
|-
!<math>x</math>
!<math>y</math>
! '''not''' <math>x</math>
!<math>x</math> '''and''' <math>y</math>
!<math>x</math> '''or''' <math>y</math>
!<math>x</math> '''xor''' <math>y</math>
|-
!0
!0
| 1
| 0
| 0
| 0
|-
!0
!1
| 1
| 0
| 1
| 1
|-
!1
!0
| 0
| 0
| 1
| 1
|-
!1
!1
| 0
| 1
| 1
| 0
|}

=== Shift Operators ===

Logical shifts (LSHIFT-x and RSHIFT-x) “ripple” the bit-string x positions in the indicated direction, either to the left or to the right. Bits shifted out are lost; zeros are shifted in at the other end.

Circulates (RCIRC-x and LCIRC-x) “ripple” the bit string x positions in the indicated direction. As each bit is shifted out one end, it is shifted in at the other end. The effect of this is that the bits remain in the same order on the other side of the string.

The size of a bit-string does not change with shifts, or circulates. If any bit strings are initially of different lengths, all shorter ones are padded with zeros in the left bits until all strings are of the same length.

The following table gives some examples of these operations:

::{| class="wikitable" style="text-align: right"
|-
!x
!(LSHIFT-2 x)
!(RSHIFT-3 x)
!(LCIRC-3 x)
!(RCIRC-1 x)
|-
!01101
| 10100
| 00001
| 01011
| 10110
|-
!10
| 00
| 00
| 01
| 01
|-
!1110
| 1000
| 0001
| 0111
| 0111
|-
!1011011
| 1101100
| 0001011
| 1011101
| 1101101
|}

=== Order of Precedence ===

The order of precedence (from highest to lowest) is: NOT; SHIFT and CIRC; AND; XOR; and finally, OR. In other words, all unary operators are performed on a single operator first. Operators with equal precedence are evaluated left to right; all unary operators bind from right to left.

== Sample Problems ==

=== Problem 1 ===

Evaluate the following expression:
:(0101110 AND NOT 110110 OR (LSHIFT-2 101010))

'''Solution:'''
The expression evaluates as follows:
:(0101110 AND '''001001''' OR (LSHIFT-2 101010))
:('''001000''' OR (LSHIFT-2 101010))
:(001000 OR '''010000''')
:'''011000'''

=== Problem 2 ===

Evaluate the following expression:
:(RSHIFT-1 (LCIRC-4 (RCIRC-2 01101)))

'''Solution:'''
The expression evaluates as follows, starting at the innermost parentheses:
:(RCIRC-2 01101) => 01011
:(LCIRC-4 01011) => 10101
:(RSHIFT-1 10101) = 01010

=== Problem 3 ===

List all possible values of x (5 bits long) that solve the following equation.
:(LSHIFT-1 (10110 XOR (RCIRC-3 x) AND 11011)) = 01100

'''Solution:'''
Since x is a string 5 bits long, represent it by abcde. (RCIRC-3 x) is cdeab which, when ANDed with 11011 gives cd0ab. This is XORed to 10110 to yield Cd1Ab (the capital letter is the NOT of its lower case).
Now, (LSHIFT-1 Cd1Ab) = d1Ab0 which has a value of 01100, we must have d=0, A=1 (hence a=0), b=0. Thus, the solution must be in the form 00*0*, where * is an “I-don’t-care”. The four possible values of x are: 00000, 00001, 00100 and 00101.

=== Problem 4 ===

Evaluate the following expression:
: ((RCIRC-14 (LCIRC-23 01101)) | (LSHIFT-1 10011) & (RSHIFT-2 10111))

'''Solution:'''
The problem can be rewritten as
: A | B & C
The AND has higher precedence than the OR.

The evaluation of expression A can be done in a straightforward way: (LCIRC-23 01101) is the same as (LCIRC-3 01101) which has a value of 01011, and (RCIRC-14 01011) is the same as (RCIRC-4 01011) which has a value of 10110. Another strategy is to offset the left and right circulates. So, ((RCIRC-14 (LCIRC-23 01101)) has the same value as (LCIRC-9 01101), which has the same value as (LCIRC-4 01101) which is also 11010.

Expressions B and C are pretty easy to evaluate:
:B = (LSHIFT-1 10011) = 00110
:C = (RSHIFT-2 10111) = 00101

The expression becomes
: A | B & C = 10110 | 00110 & 00101 = 10110 | 00100 = 10110

== 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.

{|
|-
| <youtube width="300" height="180">https://youtu.be/IeMsD3harrE</youtube>
| [https://youtu.be/IeMsD3harrE ''Bit String Flicking (Intro)'' ('''CalculusNguyenify''')]

A great two-part tutorial on this ACSL category. Part 1 covers bitwise operations AND, OR, NOT, and XOR.

|-
| <youtube width="300" height="180">https://youtu.be/jbKw8oYJPs4</youtube>
| [https://youtu.be/jbKw8oYJPs4 ''Bit String Flicking Shifts and Circs'' ('''CalculusNguyenify''')]

Part 2 covers logical shifts and circulate operations.

|-
| <youtube width="300" height="180">https://youtu.be/XNBcO25mgCw</youtube>
| [https://youtu.be/XNBcO25mgCw ''Bit String Flicking'' ('''Tangerine Code''')]

Shows the solution to the problem: (RSHIFT-3 (LCIRC-2 (NOT 10110)))

|-
| <youtube width="300" height="180">https://youtu.be/8J9AdxU5CW8</youtube>
| [https://youtu.be/8J9AdxU5CW8 ''Bit String Flicking by Ravi Yeluru'' ('''hemsra''')]

Walks through two problems from the Junior Division.

|-
| <youtube width="300" height="180">https://youtu.be/aa_lQ8gft60</youtube>
| [https://youtu.be/aa_lQ8gft60 ''ACSL BitString Flicking Contest 2 Worksheet 1'' ('''misterminich''')]

Solves a handful of problems given in previous years at the Intermediate Division level.

|}