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))
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)) ;
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 –
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.