Write up on Tech Geek history : LISP vs Python Searches
Significance of the Study
Introduction
Python was created by Guido van Rossum and first released on February 20, 1991. While the word “python” might bring to mind a large snake, the language’s name actually comes from the classic BBC comedy series Monty Python’s Flying Circus.
What makes Python unique is that it began as the vision and work of a single person. Unlike most languages born in big tech companies, Python was created by Guido – driven by a simple goal: to make programming more intuitive and enjoyable.
From that idea, a global community has grown. Thousands of developers, educators, scientists, and enthusiasts continue to shape Python, expanding its reach into AI, data science, education, and beyond.
Even though Python has many of the features of Lisp, it is instructive to look at the original Lisp evaluation mechanism. At the heart of the Lisp language is a recursive interplay between the evaluation of expressions and application of functions. If you look at the code, there is an apply() function, and an eval() function. The interplay of these two functions results in a very elegant piece of code.
Common Lisp: there are similar patterns than in Python, but we can escape them. We can use macros, be concise and do what we want. We can have the decorator syntax with the cl-annot library, and any other by writing our reader macros (they can bring triply-quoted docstrings, string interpolation, infix notation, C syntax…). It’s not only macros though. The polymorphism of the object system (or generic dispatch) helps, and Lisp’s “moldability” in a whole allows us to refactor code exactly how we want, to build a “Domain Specific Language” to express what we want. Other language features than macros help here, like closures or multiple values (which are different, and safer for refactoring, than returning a tuple).
Chapter 1: LISP Searches vs Python Searches
LISP Searches
A collection (in other words, a list) of assertions is called a database. Given a database , we can write functions to answer questions such as, “What color is block B2?” or “What blocks support block B1?”
To answer these questions, we will use a function called a pattern matcher to search the database for us. For example, to find out the color of block B2, we use the pattern (B2 COLOR?).
> (fetch’(b2 color ?))
((B2 COLOR RED))
To find which blocks support B1, we use the pattern (? SUPPORTS B1):
> (fetch'(? supports b1))
((B2 SUPPORTS B1) (B3 SUPPORTS B1))
FETCH returns those assertions from the database that match a given pattern. It should be apparent from the preceding examples that a pattern is a triple, like an assertion, with some of its elements replaced by question marks.
Structures are programmer-defined Lisp objects with an arbitrary number of named components. Structure types automatically become part of the Lisp type hierarchy. The DEFSTRUCT macro defines new structures and specifies the names and default values of their components.
For example, we can define a structure called STARSHIP like this:
(defstruct starship (name nil) (speed 0)
(condition ‘green) (shields ‘down))
https://www.cs.cmu.edu/~dst/LispBook/lisp-book-figures.pdf
This DEFSTRUCT form defines a new type of object called a STARSHIP whose components are called NAME, SPEED, CONDITION, and SHIELDS. STARSHIP becomes part of the system type hierarchy and can be referenced by such functions as TYPEP and TYPE-OF.
To introduce graph search programming in Lisp, we next represent and solve the farmer, wolf, goat, and cabbage problem: A farmer with his wolf, goat, and cabbage come to the edge of a river they wish to cross. There is a boat at the river’s edge, but, of course, only the farmer can row it. The boat also can carry only two things (including the rower) at a time. If the wolf is ever left alone with the goat, the wolf will eat the goat; similarly, if the goat is left alone with the cabbage, the goat will eat the cabbage. Devise a sequence of crossings of the river so that all four characters arrive safely on the other side of the river.
The Lisp version searches the same space and has structural similarities to the Prolog solution; however, it differs in ways that reflect Lisp’s imperative/functional orientation. The Lisp solution searches the state space in a depth-first fashion using a list of visited states to avoid loops. The heart of the program is a set of functions that define states of the world as an abstract data type. These functions hide the internals of state representation from higher-level components of the program. States are represented as lists of four elements, where each element denotes the location of the farmer, wolf, goat, or cabbage, respectively.
Thus, (e w e w) represents the state in which the farmer (the first element) and the goat (the third element) are on the east bank and the wolf and cabbage are on the west. The basic functions defining the state data type will be a constructor, make-state, which takes as arguments the locations of the farmer, wolf, goat, and cabbage and returns a state, and four access functions, farmer-side, wolf-side, goatside, and cabbage-side, which take a state and return the location of an individual. These functions are defined:
(defun make-state (f w g c) (list f w g c))
(defun farmer-side (state) (nth 0 state))
(defun wolf-side (state) (nth 1 state))
(defun goat-side (state) (nth 2 state))
(defun cabbage-side (state) (nth 3 state))
The rest of the program is built on these state access and construction functions. In particular, they are used to implement the four possible actions the farmer may take: rowing across the river alone or with either of the wolf, goat, or cabbage. Each move uses the access functions to tear a state apart into its components. A function called opposite (to be defined shortly) determines the new location of the individuals that cross the river, and make-state reassembles
these into the new state.
For example, the function farmer-takes-self may be defined:
(defun farmer-takes-self (state)
(make-state (opposite (farmer-side state))
(wolf-side state)
(goat-side state)
(cabbage-side state)))
Note that farmer-takes-self returns the new state, regardless of whether it is safe or not. A state is unsafe if the farmer has left the goat alone with the cabbage or left the wolf alone with the goat. The program must find a solution path that does not contain any unsafe states. Although this “safe” check may be done at a number of different stages in the execution of the program, our approach is to perform it in the move functions. This is implemented by using a function called safe, which we also define shortly. safe has the following behavior:
> (safe ‘(w w w w)) ;safe state, return unchanged (w w w w) > (safe ‘(e w w e)) ;wolf eats goat, return nil nil > (safe ‘(w w e e)) ;
What is Search? Search is a process of finding a value in a list of values. In other words, searching is the process of locating given value position in a list of values. Linear Search Algorithm (Sequential Search Algorithm)
• Linear search algorithm finds given element in a list of elements with O(n) time complexity where n is total number of elements in the list.
• This search process starts comparing of search element with the first element in the list. • If both are matching then results with element found otherwise search element is compared with next element in the list.
• If both are matched, then the result is “element found”. Otherwise, repeat the same with the next element in the list until search element is compared with last element in the list.
• if that last element also doesn’t match, then the result is “Element not found in the list”. That means, the search element is compared with element by element in the list. Linear search is implemented using following steps…
Step 1: Read the search element from the user
Step 2: Compare, the search element with the first element in the list.
Step 3: If both are matching, then display “Given element found!!!” and terminate the function
Step 4: If both are not matching, then compare search element with the next element in the list.
Step 5: Repeat steps 3 and 4 until the search element is compared with the last element in the list.
Step 6: If the last element in the list is also doesn’t match, then display “Element not found!!!” and terminate the function
General overview Scheme is a functional programming language Scheme is a small derivative of LISP: LISt Processing Dynamic typing and dynamic scooping Scheme introduced static scooping
· Data Objects
§ An expression is either an atom or a list
§ An atom is a string of characters
Definitions
· Functional programming languages were originally developed specifically to handle symbolic computation and listprocessing applications.
· In FPLs the programmer is concerned only with functionality, not with memory-related variable storage and assignment sequences.
· FPL can be categorized into two types; ü PURE functional languages, which support only the functional paradigm (Haskell), and ü Impure functional languages that can also be used for writing imperative-style programs (LISP).
A lambda abstraction is rather similar to a function definition in a conventionallanguage, such as C: Inc( x ) int x; {retum( x + 1 );} The formal parameter of the lambda abstraction corresponds to the formal parameter of the function, and the body of the abstraction is an expression rather than a sequence of commands. However, functions in conventional languages must have a name(such as Inc), whereas lambda abstractions are ‘anonymous’functions.
The bodyof a lambdaabstraction extends as far to the right as possible, so that in the expression (Ax. + x 1) 4 the body of the Ax abstraction is (+ x 1), not just +. As usual, we may add extra bracketsto clarify, thus (ax.(+ x 1)) 4 When a lambdaabstraction appears in isolation we may write it without any brackets: dAx.+ x1
Applications
· AI is the main application domain for functional programming, covering topics such as: expert systems knowledge representation machine learning natural language processing modelling speech and vision A. Bellaachia Page: 4 o In terms of symbolic computation, functional programming languages have also proven useful in some editing environments (EMACS) and some mathematical software (particularly calculus)
· Lisp and its derivatives are still the dominant functional languages (we will consider one of the simpler derivatives, Scheme, in some detail).
We define a lambda expression to be an expression in the lambda calculus,
Definition 1 (λ-terms)
We begin by positing the existence of an infinite set of atomic variables, x, y, z, . . ..
We then define the set Λ of λ-terms as follows:
• every variable is a λ-term,
• if M and N are λ-terms, then apply(M, N) is a λ-term, and
• if x is a variable, and M is a λ-term, then lambda(x, M) is a λ-term
https://www.classes.cs.uchicago.edu/archive/2004/spring/15300-1/docs/lambda-intro.pdf
Syntax of a lambda special form.
A lambda special form has the following syntax: (lambda (x1 x2 … xn) b1 b2 … bk) where:
• each xi is an expression denoting a Lisp symbol;
• each bi is a Lisp expression of any kind;
• n ≥ 0; and • k ≥ 1.
But real-world programming languages, like Lisp, have facilities that are not obviously present in the pure λ-calculus: they have primitive datatypes for things like the integers, they have ways to create composite types (tuples, records, vectors, etc.), and they have control structures such as conditionals and recursion. It is not immediately whether or not analogs to these facilities can be found in the λ-calculus.
Chapter 2
They Called It LISP for a Reason: List Processing
Lists play an important role in Lisp–for reasons both historical and practical. Historically, lists were Lisp’s original composite data type, though it has been decades since they were its only such data type. These days, a Common Lisp programmer is as likely to use a vector, a hash table, or a user-defined class or structure as to use a list.
Practically speaking, lists remain in the language because they’re an excellent solution to certain problems. One such problem–how to represent code as data in order to support code-transforming and code-generating macros–is particular to Lisp, which may explain why other languages don’t feel the lack of Lisp-style lists. More generally, lists are an excellent data structure for representing any kind of heterogeneous and/or hierarchical data. They’re also quite lightweight and support a functional style of programming that’s another important part of Lisp’s heritage.
Thus, you need to understand lists on their own terms; as you gain a better understanding of how lists work, you’ll be in a better position to appreciate when you should and shouldn’t use them.
Spoon Boy: Do not try and bend the list. That’s impossible. Instead . . . only try to realize the truth.
Neo: What truth?
Spoon Boy: There is no list.
Neo: There is no list?
Spoon Boy: Then you’ll see that it is not the list that bends; it is only yourself.1
The key to understanding lists is to understand that they’re largely an illusion built on top of objects that are instances of a more primitive data type. Those simpler objects are pairs of values called cons cells, after the function CONS used to create them.
CONS takes two arguments and returns a new cons cell containing the two values.2 These values can be references to any kind of object. Unless the second value is NIL or another cons cell, a cons is printed as the two values in parentheses separated by a dot, a so-called dotted pair.
(cons 1 2) ==> (1 . 2)
The two values in a cons cell are called the CAR and the CDR after the names of the functions used to access them. At the dawn of time, these names were mnemonic, at least to the folks implementing the first Lisp on an IBM 704. But even then they were just lifted from the assembly mnemonics used to implement the operations. However, it’s not all bad that these names are somewhat meaningless–when considering individual cons cells, it’s best to think of them simply as an arbitrary pair of values without any particular semantics. Thus:
(car (cons 1 2)) ==> 1
(cdr (cons 1 2)) ==> 2
Both CAR and CDR are also SETFable places–given an existing cons cell, it’s possible to assign a new value to either of its values.3
(defparameter *cons* (cons 1 2))
*cons* ==> (1 . 2)
(setf (car *cons*) 10) ==> 10
*cons* ==> (10 . 2)
(setf (cdr *cons*) 20) ==> 20
*cons* ==> (10 . 20)
Because the values in a cons cell can be references to any kind of object, you can build larger structures out of cons cells by linking them together. Lists are built by linking together cons cells in a chain. The elements of the list are held in the CARs of the cons cells while the links to subsequent cons cells are held in the CDRs. The last cell in the chain has a CDR of NIL, which–as I mentioned in Chapter 4–represents the empty list as well as the boolean value false.
This arrangement is by no means unique to Lisp; it’s called a singly linked list. However, few languages outside the Lisp family provide such extensive support for this humble data type.
So when I say a particular value is a list, what I really mean is it’s either NIL or a reference to a cons cell. The CAR of the cons cell is the first item of the list, and the CDR is a reference to another list, that is, another cons cell or NIL, containing the remaining elements. The Lisp printer understands this convention and prints such chains of cons cells as parenthesized lists rather than as dotted pairs.
(cons 1 nil) ==> (1)
(cons 1 (cons 2 nil)) ==> (1 2)
(cons 1 (cons 2 (cons 3 nil))) ==> (1 2 3)
When talking about structures built out of cons cells, a few diagrams can be a big help. Box-and-arrow diagrams represent cons cells as a pair of boxes like this:
The box on the left represents the CAR, and the box on the right is the CDR. The values stored in a particular cons cell are either drawn in the appropriate box or represented by an arrow from the box to a representation of the referenced value.4 For instance, the list (1 2 3), which consists of three cons cells linked together by their CDRs, would be diagrammed like this:
However, most of the time you work with lists you won’t have to deal with individual cons cells–the functions that create and manipulate lists take care of that for you. For example, the LIST function builds a cons cells under the covers for you and links them together; the following LIST expressions are equivalent to the previous CONS expressions:
(list 1) ==> (1)
(list 1 2) ==> (1 2)
(list 1 2 3) ==> (1 2 3)
Similarly, when you’re thinking in terms of lists, you don’t have to use the meaningless names CAR and CDR; FIRST and REST are synonyms for CAR and CDR that you should use when you’re dealing with cons cells as lists.
(defparameter *list* (list 1 2 3 4))
(first *list*) ==> 1
(rest *list*) ==> (2 3 4)
(first (rest *list*)) ==> 2
Because cons cells can hold any kind of values, so can lists. And a single list can hold objects of different types.
(list “foo” (list 1 2) 10) ==> (“foo” (1 2) 10)
The structure of that list would look like this:
Because lists can have other lists as elements, you can also use them to represent trees of arbitrary depth and complexity. As such, they make excellent representations for any heterogeneous, hierarchical data. Lisp-based XML processors, for instance, usually represent XML documents internally as lists. Another obvious example of tree-structured data is Lisp code itself. In Chapters 30 and 31 you’ll write an HTML generation library that uses lists of lists to represent the HTML to be generated. I’ll talk more next chapter about using cons cells to represent other data structures.
Common Lisp provides quite a large library of functions for manipulating lists. In the sections “List-Manipulation Functions” and “Mapping,” you’ll look at some of the more important of these functions. However, they will be easier to understand in the context of a few ideas borrowed from functional programming.
Functional Programming and Lists
The essence of functional programming is that programs are built entirely of functions with no side effects that compute their results based solely on the values of their arguments. The advantage of the functional style is that it makes programs easier to understand. Eliminating side effects eliminates almost all possibilities for action at a distance. And since the result of a function is determined only by the values of its arguments, its behavior is easier to understand and test. For instance, when you see an expression such as (+ 3 4), you know the result is uniquely determined by the definition of the + function and the values 3 and 4. You don’t have to worry about what may have happened earlier in the execution of the program since there’s nothing that can change the result of evaluating that expression.
Functions that deal with numbers are naturally functional since numbers are immutable. A list, on the other hand, can be mutated, as you’ve just seen, by SETFing the CARs and CDRs of the cons cells that make up its backbone. However, lists can be treated as a functional data type if you consider their value to be determined by the elements they contain. Thus, any list of the form (1 2 3 4) is functionally equivalent to any other list containing those four values, regardless of what cons cells are actually used to represent the list. And any function that takes a list as an argument and returns a value based solely on the contents of the list can likewise be considered functional. For instance, the REVERSE sequence function, given the list (1 2 3 4), always returns a list (4 3 2 1). Different calls to REVERSE with functionally equivalent lists as the argument will return functionally equivalent result lists. Another aspect of functional programming, which I’ll discuss in the section “Mapping,” is the use of higher-order functions: functions that treat other functions as data, taking them as arguments or returning them as results.
Most of Common Lisp’s list-manipulation functions are written in a functional style. I’ll discuss later how to mix functional and other coding styles, but first you should understand a few subtleties of the functional style as applied to lists.
The reason most list functions are written functionally is it allows them to return results that share cons cells with their arguments. To take a concrete example, the function APPEND takes any number of list arguments and returns a new list containing the elements of all its arguments. For instance:
(append (list 1 2) (list 3 4)) ==> (1 2 3 4)
From a functional point of view, APPEND‘s job is to return the list (1 2 3 4) without modifying any of the cons cells in the lists (1 2) and (3 4). One obvious way to achieve that goal is to create a completely new list consisting of four new cons cells. However, that’s more work than is necessary. Instead, APPEND actually makes only two new cons cells to hold the values 1 and 2, linking them together and pointing the CDR of the second cons cell at the head of the last argument, the list (3 4). It then returns the cons cell containing the 1. None of the original cons cells has been modified, and the result is indeed the list (1 2 3 4). The only wrinkle is that the list returned by APPEND shares some cons cells with the list (3 4). The resulting structure looks like this:
In general, APPEND must copy all but its last argument, but it can always return a result that shares structure with the last argument.
Other functions take similar advantage of lists’ ability to share structure. Some, like APPEND, are specified to always return results that share structure in a particular way. Others are simply allowed to return shared structure at the discretion of the implementation.
If Common Lisp were a purely functional language, that would be the end of the story. However, because it’s possible to modify a cons cell after it has been created by SETFing its CAR or CDR, you need to think a bit about how side effects and structure sharing mix.
Because of Lisp’s functional heritage, operations that modify existing objects are called destructive–in functional programming, changing an object’s state “destroys” it since it no longer represents the same value. However, using the same term to describe all state-modifying operations leads to a certain amount of confusion since there are two very different kinds of destructive operations, for-side-effect operations and recycling operations.5
For-side-effect operations are those used specifically for their side effects. All uses of SETF are destructive in this sense, as are functions that use SETF under the covers to change the state of an existing object such as VECTOR-PUSH or VECTOR-POP. But it’s a bit unfair to describe these operations as destructive–they’re not intended to be used in code written in a functional style, so they shouldn’t be described using functional terminology. However, if you mix nonfunctional, for-side-effect operations with functions that return structure-sharing results, then you need to be careful not to inadvertently modify the shared structure. For instance, consider these three definitions:
(defparameter *list-1* (list 1 2))
(defparameter *list-2* (list 3 4))
(defparameter *list-3* (append *list-1* *list-2*))
After evaluating these forms, you have three lists, but *list-3* and *list-2* share structure just like the lists in the previous diagram.
*list-1* ==> (1 2)
*list-2* ==> (3 4)
*list-3* ==> (1 2 3 4)
Now consider what happens when you modify *list-2*.
(setf (first *list-2*) 0) ==> 0
*list-2* ==> (0 4) ; as expected
*list-3* ==> (1 2 0 4) ; maybe not what you wanted
The change to *list-2* also changes *list-3* because of the shared structure: the first cons cell in *list-2* is also the third cons cell in *list-3*. SETFing the FIRST of *list-2* changes the value in the CAR of that cons cell, affecting both lists.
On the other hand, the other kind of destructive operations, recycling operations, are intended to be used in functional code. They use side effects only as an optimization. In particular, they reuse certain cons cells from their arguments when building their result. However, unlike functions such as APPEND that reuse cons cells by including them, unmodified, in the list they return, recycling functions reuse cons cells as raw material, modifying the CAR and CDR as necessary to build the desired result. Thus, recycling functions can be used safely only when the original lists aren’t going to be needed after the call to the recycling function.
To see how a recycling function works, let’s compare REVERSE, the nondestructive function that returns a reversed version of a sequence, to NREVERSE, a recycling version of the same function. Because REVERSE doesn’t modify its argument, it must allocate a new cons cell for each element in the list being reversed. But suppose you write something like this:
(setf *list* (reverse *list*))
By assigning the result of REVERSE back to *list*, you’ve removed the reference to the original value of *list*. Assuming the cons cells in the original list aren’t referenced anywhere else, they’re now eligible to be garbage collected. However, in many Lisp implementations it’d be more efficient to immediately reuse the existing cons cells rather than allocating new ones and letting the old ones become garbage.
NREVERSE allows you to do exactly that. The N stands for non-consing, meaning it doesn’t need to allocate any new cons cells. The exact side effects of NREVERSE are intentionally not specified–it’s allowed to modify any CAR or CDR of any cons cell in the list–but a typical implementation might walk down the list changing the CDR of each cons cell to point to the previous cons cell, eventually returning the cons cell that was previously the last cons cell in the old list and is now the head of the reversed list. No new cons cells need to be allocated, and no garbage is created.
Most recycling functions, like NREVERSE, have nondestructive counterparts that compute the same result. In general, the recycling functions have names that are the same as their non-destructive counterparts except with a leading N. However, not all do, including several of the more commonly used recycling functions such as NCONC, the recycling version of APPEND, and DELETE, DELETE-IF, DELETE-IF-NOT, and DELETE-DUPLICATES, the recycling versions of the REMOVE family of sequence functions.
In general, you use recycling functions in the same way you use their nondestructive counterparts except it’s safe to use them only when you know the arguments aren’t going to be used after the function returns. The side effects of most recycling functions aren’t specified tightly enough to be relied upon.
However, the waters are further muddied by a handful of recycling functions with specified side effects that can be relied upon. They are NCONC, the recycling version of APPEND, and NSUBSTITUTE and its -IF and -IF-NOT variants, the recycling versions of the sequence functions SUBSTITUTE and friends.
Like APPEND, NCONC returns a concatenation of its list arguments, but it builds its result in the following way: for each nonempty list it’s passed, NCONC sets the CDR of the list’s last cons cell to point to the first cons cell of the next nonempty list. It then returns the first list, which is now the head of the spliced-together result. Thus:
(defparameter *x* (list 1 2 3))
(nconc *x* (list 4 5 6)) ==> (1 2 3 4 5 6)
*x* ==> (1 2 3 4 5 6)
NSUBSTITUTE and variants can be relied on to walk down the list structure of the list argument and to SETF the CARs of any cons cells holding the old value to the new value and to otherwise leave the list intact. It then returns the original list, which now has the same value as would’ve been computed by SUBSTITUTE. 6
The key thing to remember about NCONC and NSUBSTITUTE is that they’re the exceptions to the rule that you can’t rely on the side effects of recycling functions. It’s perfectly acceptable–and arguably good style–to ignore the reliability of their side effects and use them, like any other recycling function, only for the value they return.
Combining Recycling with Shared Structure
Although you can use recycling functions whenever the arguments to the recycling function won’t be used after the function call, it’s worth noting that each recycling function is a loaded gun pointed footward: if you accidentally use a recycling function on an argument that is used later, you’re liable to lose some toes.
To make matters worse, shared structure and recycling functions tend to work at cross-purposes. Nondestructive list functions return lists that share structure under the assumption that cons cells are never modified, but recycling functions work by violating that assumption. Or, put another way, sharing structure is based on the premise that you don’t care exactly what cons cells make up a list while using recycling functions requires that you know exactly what cons cells are referenced from where.
In practice, recycling functions tend to be used in a few idiomatic ways. By far the most common recycling idiom is to build up a list to be returned from a function by “consing” onto the front of a list, usually by PUSHing elements onto a list stored in a local variable and then returning the result of NREVERSEing it.7
This is an efficient way to build a list because each PUSH has to create only one cons cell and modify a local variable and the NREVERSE just has to zip down the list reassigning the CDRs. Because the list is created entirely within the function, there’s no danger any code outside the function has a reference to any of its cons cells. Here’s a function that uses this idiom to build a list of the first n numbers, starting at zero:8
(defun upto (max)
(let ((result nil))
(dotimes (i max)
(push i result))
(nreverse result)))
(upto 10) ==> (0 1 2 3 4 5 6 7 8 9)
The next most common recycling idiom9 is to immediately reassign the value returned by the recycling function back to the place containing the potentially recycled value. For instance, you’ll often see expressions like the following, using DELETE, the recycling version of REMOVE:
(setf foo (delete nil foo))
This sets the value of foo to its old value except with all the NILs removed. However, even this idiom must be used with some care–if foo shares structure with lists referenced elsewhere, using DELETE instead of REMOVE can destroy the structure of those other lists. For example, consider the two lists *list-2* and *list-3* from earlier that share their last two cons cells.
*list-2* ==> (0 4)
*list-3* ==> (1 2 0 4)
You can delete 4 from *list-3* like this:
(setf *list-3* (delete 4 *list-3*)) ==> (1 2 0)
However, DELETE will likely perform the necessary deletion by setting the CDR of the third cons cell to NIL, disconnecting the fourth cons cell, the one holding the 4, from the list. Because the third cons cell of *list-3* is also the first cons cell in *list-2*, the following modifies *list-2* as well:
*list-2* ==> (0)
If you had used REMOVE instead of DELETE, it would’ve built a list containing the values 1, 2, and 0, creating new cons cells as necessary rather than modifying any of the cons cells in *list-3*. In that case, *list-2* wouldn’t have been affected.
The PUSH/NREVERSE and SETF/DELETE idioms probably account for 80 percent of the uses of recycling functions. Other uses are possible but require keeping careful track of which functions return shared structure and which do not.
In general, when manipulating lists, it’s best to write your own code in a functional style–your functions should depend only on the contents of their list arguments and shouldn’t modify them. Following that rule will, of course, rule out using any destructive functions, recycling or otherwise. Once you have your code working, if profiling shows you need to optimize, you can replace nondestructive list operations with their recycling counterparts but only if you’re certain the argument lists aren’t referenced from anywhere else.
One last gotcha to watch out for is that the sorting functions SORT, STABLE-SORT, and MERGE mentioned in Chapter 11 are also recycling functions when applied to lists.10 However, these functions don’t have nondestructive counterparts, so if you need to sort a list without destroying it, you need to pass the sorting function a copy made with COPY-LIST. In either case you need to be sure to save the result of the sorting function because the original argument is likely to be in tatters. For instance:
CL-USER> (defparameter *list* (list 4 3 2 1))
*LIST*
CL-USER> (sort *list* #'<)
(1 2 3 4) ; looks good
CL-USER> *list*
(4) ; whoops!
With that background out of the way, you’re ready to look at the library of functions Common Lisp provides for manipulating lists.
You’ve already seen the basic functions for getting at the elements of a list: FIRST and REST. Although you can get at any element of a list by combining enough calls to REST (to move down the list) with a FIRST (to extract the element), that can be a bit tedious. So Common Lisp provides functions named for the other ordinals from SECOND to TENTH that return the appropriate element. More generally, the function NTH takes two arguments, an index and a list, and returns the nth (zero-based) element of the list. Similarly, NTHCDR takes an index and a list and returns the result of calling CDR n times. (Thus, (nthcdr 0 …) simply returns the original list, and (nthcdr 1 …) is equivalent to REST.) Note, however, that none of these functions is any more efficient, in terms of work done by the computer, than the equivalent combinations of FIRSTs and RESTs–there’s no way to get to the nth element of a list without following n CDR references.11
The 28 composite CAR/CDR functions are another family of functions you may see used from time to time. Each function is named by placing a sequence of up to four As and Ds between a C and R, with each A representing a call to CAR and each D a call to CDR. Thus:
(caar list) === (car (car list))
(cadr list) === (car (cdr list))
(cadadr list) === (car (cdr (car (cdr list))))
Note, however, that many of these functions make sense only when applied to lists that contain other lists. For instance, CAAR extracts the CAR of the CAR of the list it’s given; thus, the list it’s passed must contain another list as its first element. In other words, these are really functions on trees rather than lists:
(caar (list 1 2 3)) ==> error
(caar (list (list 1 2) 3)) ==> 1
(cadr (list (list 1 2) (list 3 4))) ==> (3 4)
(caadr (list (list 1 2) (list 3 4))) ==> 3
These functions aren’t used as often now as in the old days. And even the most die-hard old-school Lisp hackers tend to avoid the longer combinations. However, they’re used quite a bit in older Lisp code, so it’s worth at least understanding how they work.12
The FIRST–TENTH and CAR, CADR, and so on, functions can also be used as SETFable places if you’re using lists nonfunctionally.
Tablesummarizes some other list functions that I won’t cover in detail.
Table . Other List Functions
| Function | Description |
| LAST | Returns the last cons cell in a list. With an integer, argument returns the last n cons cells. |
| BUTLAST | Returns a copy of the list, excluding the last cons cell. With an integer argument, excludes the last n cells. |
| NBUTLAST | The recycling version of BUTLAST; may modify and return the argument list but has no reliable side effects. |
| LDIFF | Returns a copy of a list up to a given cons cell. |
| TAILP | Returns true if a given object is a cons cell that’s part of the structure of a list. |
| LIST* | Builds a list to hold all but the last of its arguments and then makes the last argument the CDR of the last cell in the list. In other words, a cross between LIST and APPEND. |
| MAKE-LIST | Builds an n item list. The initial elements of the list are NIL or the value specified with the :initial-element keyword argument. |
| REVAPPEND | Combination of REVERSE and APPEND; reverses first argument as with REVERSE and then appends the second argument. |
| NRECONC | Recycling version of REVAPPEND; reverses first argument as if by NREVERSE and then appends the second argument. No reliable side effects. |
| CONSP | Predicate to test whether an object is a cons cell. |
| ATOM | Predicate to test whether an object is not a cons cell. |
| LISTP | Predicate to test whether an object is either a cons cell or NIL. |
| NULL | Predicate to test whether an object is NIL. Functionally equivalent to NOT but stylistically preferable when testing for an empty list as opposed to boolean false. |
Another important aspect of the functional style is the use of higher-order functions, functions that take other functions as arguments or return functions as values. You saw several examples of higher-order functions, such as MAP, in the previous chapter. Although MAP can be used with both lists and vectors (that is, with any kind of sequence), Common Lisp also provides six mapping functions specifically for lists. The differences between the six functions have to do with how they build up their result and whether they apply the function to the elements of the list or to the cons cells of the list structure.
MAPCAR is the function most like MAP. Because it always returns a list, it doesn’t require the result-type argument MAP does. Instead, its first argument is the function to apply, and subsequent arguments are the lists whose elements will provide the arguments to the function. Otherwise, it behaves like MAP: the function is applied to successive elements of the list arguments, taking one element from each list per application of the function. The results of each function call are collected into a new list. For example:
(mapcar #'(lambda (x) (* 2 x)) (list 1 2 3)) ==> (2 4 6)
(mapcar #’+ (list 1 2 3) (list 10 20 30)) ==> (11 22 33)
MAPLIST is just like MAPCAR except instead of passing the elements of the list to the function, it passes the actual cons cells.13 Thus, the function has access not only to the value of each element of the list (via the CAR of the cons cell) but also to the rest of the list (via the CDR).
MAPCAN and MAPCON work like MAPCAR and MAPLIST except for the way they build up their result. While MAPCAR and MAPLIST build a completely new list to hold the results of the function calls, MAPCAN and MAPCON build their result by splicing together the results–which must be lists–as if by NCONC. Thus, each function invocation can provide any number of elements to be included in the result.14 MAPCAN, like MAPCAR, passes the elements of the list to the mapped function while MAPCON, like MAPLIST, passes the cons cells.
Finally, the functions MAPC and MAPL are control constructs disguised as functions–they simply return their first list argument, so they’re useful only when the side effects of the mapped function do something interesting. MAPC is the cousin of MAPCAR and MAPCAN while MAPL is in the MAPLIST/MAPCON family.
While cons cells and lists are typically considered to be synonymous, that’s not quite right–as I mentioned earlier, you can use lists of lists to represent trees. Just as the functions discussed in this chapter allow you to treat structures built out of cons cells as lists, other functions allow you to use cons cells to represent trees, sets, and two kinds of key/value maps. I’ll discuss some of those functions in the next chapter.
1Adapted from The Matrix (http://us.imdb.com/Quotes?0133093)
2CONS was originally short for the verb construct.
3When the place given to SETF is a CAR or CDR, it expands into a call to the function RPLACA or RPLACD; some old-school Lispers–the same ones who still use SETQ–will still use RPLACA and RPLACD directly, but modern style is to use SETF of CAR or CDR.
4Typically, simple objects such as numbers are drawn within the appropriate box, and more complex objects will be drawn outside the box with an arrow from the box indicating the reference. This actually corresponds well with how many Common Lisp implementations work–although all objects are conceptually stored by reference, certain simple immutable objects can be stored directly in a cons cell.
5The phrase for-side-effect is used in the language standard, but recycling is my own invention; most Lisp literature simply uses the term destructive for both kinds of operations, leading to the confusion I’m trying to dispel.
6The string functions NSTRING-CAPITALIZE, NSTRING-DOWNCASE, and NSTRING-UPCASE are similar–they return the same results as their N-less counterparts but are specified to modify their string argument in place.
7For example, in an examination of all uses of recycling functions in the Common Lisp Open Code Collection (CLOCC), a diverse set of libraries written by various authors, instances of the PUSH/NREVERSE idiom accounted for nearly half of all uses of recycling functions.
8There are, of course, other ways to do this same thing. The extended LOOP macro, for instance, makes it particularly easy and likely generates code that’s even more efficient than the PUSH/ NREVERSE version.
9This idiom accounts for 30 percent of uses of recycling in the CLOCC code base.
10SORT and STABLE-SORT can be used as for-side-effect operations on vectors, but since they still return the sorted vector, you should ignore that fact and use them for return values for the sake of consistency.
11NTH is roughly equivalent to the sequence function ELT but works only with lists. Also, confusingly, NTH takes the index as the first argument, the opposite of ELT. Another difference is that ELT will signal an error if you try to access an element at an index greater than or equal to the length of the list, but NTH will return NIL.
12In particular, they used to be used to extract the various parts of expressions passed to macros before the invention of destructuring parameter lists. For example, you could take apart the following expression:
(when (> x 10) (print x))
Like this:
;; the condition
(cadr ‘(when (> x 10) (print x))) ==> (> X 10)
;; the body, as a list
(cddr ‘(when (> x 10) (print x))) ==> ((PRINT X))
13Thus, MAPLIST is the more primitive of the two functions–if you had only MAPLIST, you could build MAPCAR on top of it, but you couldn’t build MAPLIST on top of MAPCAR.
14In Lisp dialects that didn’t have filtering functions like REMOVE, the idiomatic way to filter a list was with MAPCAN.
(mapcan #'(lambda (x) (if (= x 10) nil (list x))) list) === (remove 10 list)
Python Linear Search
Searching is when we find something in a data structure. We frequently search for strings in things like web pages, PDFs, documents, etc., but we can also search through other data structures, like lists, dictionaries, etc. Depending on how our data is organized, we can search in different ways. For unorganized data, we usually have to do a linear search, which is the first type of search we will discuss. If our data is organized in some way, we can do more efficient searches. If our data is in a strict order, we can perform a binary search, which is the second type of search we will look at.:
Linear Searching Lecture 10: Linear Searching The most straightforward type of search is the linear search. We traverse the data structure (e.g., a string’s characters, or a list) until we find the result. How would we do a linear search on a list, like this? Let’s say we are searching for 15
. lst = [12, 4, 9, 18, 53, 82, 15, 99, 98, 14, 11]
The most straightforward type of search is the linear search. We traverse the data structure (e.g., a string’s characters, or a list) until we find the result. How would we do a linear search on a list, like this? Let’s say we are searching for 15.
: Linear Searching lst = [12, 4, 9, 18, 53, 82, 15, 99, 98, 14, 11]
def linear_search(lst, value_to_find):
“”” Perform a linear search to find a value in the list :
param lst: a list :param value_to_find: the value we want to find
:return:
the index of the found element, or -1
if the element does not exist in the list
>>> linear_search([12, 4, 9, 18, 53, 82, 15, 99, 98, 14, 11], 15) 6
>>> linear_search([12, 4, 9, 18, 53, 82, 15, 99, 98, 14, 11], 42) -1
“”” for i, value in enumerate(lst):
if value == value_to_find:
return i return –
Chapter 3
Python’s Linear Search
Linear Search What is a Linear Search? Linear search is a method of finding elements within a list. It is also called a sequential search. It is the simplest searching algorithm because it searches the desired element in a sequential manner. It compares each and every element with the value that we are searching for. If both are matched, the element is found, and the algorithm returns the key’s index position. Concept of Linear Search Let’s understand the following steps to find the element key = 7 in the given list.
Step – 1: Start the search from the first element and Check key = 7 with each element of list x.
Linear Search Algorithm There is list of n elements and key value to be searched. Below is the linear search algorithm.
1. LinearSearch(list, key)
2. for each item in the list
3. if item == value
4. return its index position
5. return -1
Python Program Let’s understand the following Python implementation of the linear search algorithm.
Program 1.
def linear_
Search(list1, n, key): 2.
3. # Searching list1 sequentially
4. for i in range(0, n):
5. if (list1[i] == key):
6. return i
7. return -1
8.
9.
10. list1 = [1 ,3, 5, 4, 7, 9]
11. key = 7
12.
13. n = len(list1)
14. res = linear_Search(list1, n, key)
15. if(res == -1):
16. print(“Element not found”)
17. else:
18. print(“Element found at index: “, res)
Output: Element found at index:
Explanation: In the above code, we have created a function linear_Search(), which takes three arguments – list1, length of the list, and number to search. We defined for loop and iterate each element and compare to the key value. If element is found, return the index else return -1 which means element is not present in the list.
11. Functional Programming Using Python
· A list is a collection of objects.
· List constants are surrounded by square brakets and the elements in the list are separated by commas.
· Lists are “mutable” – we can change an element of a list using the index operator
· Examples: myFriendsList = [ ‘Paul’, ‘Mary’, ‘Sally’ ] myNums = [1,2,3,4] myList = []
· A list can element of another list:
>>> myList2 = [1, 2]
>>> myList3 = [‘a’, myList2, 50]
>>> myList2 [1, 2]
>>> myList3 [‘a’, [1, 2], 50]
. Defining functions
· User-defined functions can be created through the use of the lambda operator as follows: (define functionname (lambda (functionparameters)
(expression) (expression) …
(expression) ))
NOTE: The value returned by the function is the value of the last expression in the list ü Example: For example, the function below calculates factorials:
>(define factorial (lambda (n) ( if (< n 3) n (* n (factorial (- n 1)))) )) ;
Value: factorial
>(factorial 3) ; Value: 6
# Python lambda
x : lambda y : y
Rules of Our System
The Lambda Calculus asserts that any computational system can be implemented with a set of three simple rules:
- You can define variables
- You can define single-argument functions
- You can call single-argument functions
That’s it. No numbers. No operators. No control flow. No data structures.
I find it fascinating that with these very minimal concepts, the Lambda Calculus asserts that we can create a fully functional computer! This is, of course, a very minimal explanation of the rules of the Lambda Calculus, and I invite you to consult the references above for more information and formal definitions!
x = lambda a : a + 10
print(x(5))
Why Use Lambda Functions?
The power of lambda is better shown when you use them as an anonymous function inside another function.
Say you have a function definition that takes one argument, and that argument will be multiplied with an unknown number:
def myfunc(n):
return lambda a : a * n
A Data structures are specialized objects for organizing data efficiently. There are many kinds, each with specific strengths and weaknesses, and different applications require different structures for optimal performance. For example, some data structures take a long time to build, but once built their data are quickly accessible. Others are built quickly, but are not as efficiently accessible. These strengths and weaknesses are determined by how the structure is implemented. Python has several built-in data structure classes, namely list, set, dict, and tuple. Being able to use these structures is important, but selecting the correct data structure to begin with is often what makes or breaks a good program. In this lab we create a structure that mimics the built-in list class, but that has a different underlying implementation. Thus our class will be better than a plain Python list for some tasks, but worse for others.
Linked Lists A linked list is a data structure that chains nodes together. Every linked list needs a reference to the first node in the chain, called the head. A reference to the last node in the chain, called the tail, is also often included. Each node instance in the list stores a piece of data, plus at least one reference to another node in the list. The nodes of a singly linked list have a single reference to the next node in the list (see Figure 1.1), while the nodes of a doubly linked list have two references: one for the previous node, and one for the next node in the list (see Figure 1.2). This allows for a doubly linked list to be traversed in both directions, whereas a singly linked list can only be traversed in one direction.
class Linked
ListNode(Node):
“””A node class for doubly linked lists. Inherits from the ‘Node’ class. Contains references to the next and previous nodes in the linked list.
“”” def __init__(self, data): “
“”Store ‘data’ in the ‘value’ attribute and initialize attributes for the next and previous nodes in the list.
“”” Node.__init__(self, data)
# Use inheritance to set self.value
. self.next = None
self.prev = None
Linked Lists:
A linked list is a collection of objects/nodes, where each node contains both the item stored in the list, as well as a “pointer” to the next node in the list.
Linked lists typically have three instance variables: a head pointer (self.head), a tail pointer (self.tail), and the number of nodes in the list (self.size)
In the above picture, the linked list has 5 nodes, and each node stores a simple string, as well as a pointer to the next node in the list. In class I often draw linked lists and nodes as follows:
—— —— —— —— ——
self.head –> |rich| |lisa| |andy| |zach| |tia |<–self.tail
—— —— —— —— ——
| |–> | |–>| |–>| |–>| |–>None
—— —— —— —— ——
self.size = 5
Linked lists are often used to create other useful data structures, such as stacks and queues. They are also a good introduction to more advanced data structures, such as binary trees.
One big advantage of the linked list is not needing large chunks of consecutive memory. Each node in the list is just put in memory wherever there is space, and all nodes are “linked” together into one “list”.
Also, adding an item into the middle of the list does not require shifting all other elements down one slot. Simply reset the next “pointers” to include the new node.
Implementing A Linked List
We will implement a linked list using two classes:
- Node, which will store a data value (the list item) and a “pointer” to the next node in the list
- LinkedLlist, which will store pointers to the head Node and the tail Node, as well as the current size of the list.
the Node class:
Let’s write a Node class, where each node has two instance variables: one to hold the node data (call it “data”), and one to hold a pointer to another node (call it “next”). Later we will use these node objects to build a linked-list!