https://www.ocf.berkeley.edu/~shidi/cs61a/w/api.php?action=feedcontributions&user=Stevencheng&feedformat=atomCS 61A Wiki - User contributions [en]2024-03-28T09:12:19ZUser contributionsMediaWiki 1.22.6https://www.ocf.berkeley.edu/~shidi/cs61a/wiki/ConcurrencyConcurrency2014-08-10T20:49:31Z<p>Stevencheng: </p>
<hr />
<div>'''Concurrency''', or ''parallel computing'', allows for multiple operations to be performed simultaneously. To make it seem that programs are running concurrently, the CPU rapidly switches between each program, doing work in one process before switching to the next. Parallel computing is used to increase the speed of processors, but due to physical heat and energy limitations, CPU manufacturers utilize the idea of multi-core processors to achieve more processing power. <br />
<br />
==Parallelism in Python==<br />
<br />
===Threading===<br />
In ''threading'', multiple '''"threads"''' of execution exist within a single interpreter. Each thread executes code independently from the others, though they share the same data.<br />
<syntaxhighlight lang="python"><br />
>>> import threading<br />
>>> def thread_hello():<br />
other = threading.Thread(target=thread_say_hello, args=())<br />
other.start()<br />
thread_say_hello()<br />
<br />
>>> def thread_say_hello():<br />
print('hello from', threading.current_thread().name)<br />
<br />
>>> thread_hello()<br />
hello from Thread-1<br />
hello from MainThread<br />
</syntaxhighlight><br />
<br />
===Multiprocessing===<br />
'''Multiprocessing''' allows a program to spawn multiple interpreters, or ''processes, each of which can run code independently, without sharing data so any shared state must be communicated between processes.<br />
<syntaxhighlight lang="python"><br />
>>> import multiprocessing<br />
>>> def process_hello():<br />
other = multiprocessing.Process(target=process_say_hello, args=())<br />
other.start()<br />
process_say_hello()<br />
<br />
>>> def process_say_hello():<br />
print('hello from', multiprocessing.current_process().name)<br />
<br />
>>> process_hello()<br />
hello from MainProcess<br />
>>> hello from Process-1<br />
</syntaxhighlight><br />
<br />
==Synchronized Data Structures==<br />
A <code>Queue</code> is an example of a data structure that provides synchronized operations. The <code>queue</code> module contains a <code>Queue</code> class that provides synchronized first in, first out access to data. The <code>put</code> method adds an item to the <code>Queue</code> and the <code>get</code> method retrieves an item (at the end of the Queue). The class ensures methods are synchronized, so items are not lost no matter how thread operations are intertwined.<br />
<br />
An example of a producer/consumer <code>Queue</code>:<br />
<syntaxhighlight lang="python"><br />
<br />
queue = Queue()<br />
<br />
def synchronized_consume():<br />
while True:<br />
print('got an item:', queue.get())<br />
queue.task_done()<br />
<br />
def synchronized_produce():<br />
consumer = threading.Thread(target=synchronized_consume, args=())<br />
consumer.daemon = True<br />
consumer.start()<br />
for i in range(10):<br />
queue.put(i)<br />
queue.join()<br />
<br />
synchronized_produce()<br />
</syntaxhighlight><br />
<br />
Another use of a <code>Queue</code> is a parallel web crawler that searches for dead links on a website. By following every link hosted by the same site, it continually adds new URLs to a <code>Queue</code>, performs a process on that item, and removes it from the <code>Queue</code> afterwards. By using a synchronized <code>Queue</code>, multiple threads can safely add to and remove from the data structure concurrently.<br />
<br />
==Avoiding Improper Mutation of Shared Data==<br />
===Locks===<br />
When a synchronized version of a particular data structure is not available, we have to provide our own synchronization. A solution to this is a ''lock'', which allows a data structure to be acquired by at most one thread, after which no other thread may acquire it until it is ''released'' by the thread that previously acquired it.<br />
<br />
===Barriers===<br />
Another way to avoid conflicting access to shared data is to divide a program into phases, ensuring that shared data is mutated in a phase in which no other thread accesses it. '''Barriers''' divide a program into phases by requiring all threads to reach it before any of them can proceed. Code that is executed after a barrier cannot be concurrent with code executed before the barrier.<br />
===Message Passing===<br />
Another way is to entirely avoid concurrent access to the same data. Using multiprocessing in Python rather than threading naturally results in this, since processes run in seperate interpreters with their own data.<br />
<br />
==Synchronization Pitfalls==<br />
Incorrectly used synchronization methods can result in the following pitfalls.<br />
===Under-synchronization===<br />
Neglecting to properly synchronize shared accesses.<br />
===Over-synchronization===<br />
Over-synchronizing a program means that non-conflicting operations cannot occur concurrently. <br />
===Deadlock===<br />
Deadlock is a situation in which two or more threads or processes are stuck, waiting for each other to finish. No process can continue because it is waiting for other processes that are waiting for it to complete.<br />
==Source==<br />
[http://composingprograms.com/pages/47-parallel-computing.html Parallel Computing]</div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/LogicLogic2014-08-10T06:24:07Z<p>Stevencheng: /* Hierarchical facts */</p>
<hr />
<div>'''Logic''' is a declarative query programming language, in which the user imputes <code>fact</code> in order to solve a <code>query</code>. Logic is a complete implementation that depends upon the Scheme project as data records are expressed as Scheme lists, and queries are expressed as Scheme values.<br />
<br />
==Facts and Queries==<br />
Logic works by accepting user-stated <code>fact</code> and logically deducing <code>query</code> statements from those facts. A <code>fact</code> statement in <code>logic</code> consists of one or more lists following the keyword <code>fact</code>. Each <code>fact</code> statement is a relation. For example, the first line states that '''the parent of barack is abraham.'''<br />
<syntaxhighlight lang="scheme"><br />
logic> (fact (parent abraham barack))<br />
logic> (fact (parent abraham clinton))<br />
logic> (fact (parent delano herbert))<br />
logic> (fact (parent fillmore abraham))<br />
logic> (fact (parent fillmore delano))<br />
logic> (fact (parent fillmore grover))<br />
logic> (fact (parent eisenhower fillmore))<br />
<br />
<br />
logic> (query (parent abraham ?child))<br />
Success!<br />
child: barack<br />
child: clinton<br />
</syntaxhighlight><br />
Using the facts stated, we can easily find all the parent relations between one and another. Below, the query statement asks for all of the names that have abraham as its parent. If there exists such relationship, <code>logic</code> will output <code>Success!</code> followed all entries that satisfy the <code>query</code>.<br />
<br />
===Compound facts===<br />
<code>(fact <conclusion> <hypothesis0> <hypothesis1> ... <hypothesisN>) </code><br />
<br />
Compound facts are written beginning with a conclusion, followed by hypotheses. For the conclusion to be true, all of the hypotheses must be satisfied.<br />
<br />
<syntaxhighlight lang="scheme"><br />
logic> (fact (child ?c ?p) (parent ?p ?c))<br />
<br />
logic> (query (child ?child fillmore))<br />
Success!<br />
child: abraham<br />
child: delano<br />
child: grover<br />
</syntaxhighlight><br />
<br />
The <code>fact</code> can be read as "?c is the child of ?p, provided that ?p is the parent of ?c."<br />
<br />
==Recursion==<br />
<code>Logic</code> also supports recursion, that is, the conclusion of a fact may depend on a hypothesis that contains the same symbols. <br />
<syntaxhighlight lang="scheme"><br />
logic> (fact (ancestor ?a ?y) (parent ?a ?y))<br />
logic> (fact (ancestor ?a ?y) (parent ?a ?z) (ancestor ?z ?y))<br />
<br />
logic> (query (ancestor ?a herbert))<br />
Success!<br />
a: delano<br />
a: fillmore<br />
a: eisenhower<br />
</syntaxhighlight><br />
<br />
==Hierarchical facts==<br />
Fact and query lists can also contain lists, providing a way to represent hierarchical data. For example, we can assign colors to dog names.<br />
<syntaxhighlight lang="scheme"><br />
logic> (fact (dog (name abraham) (color white)))<br />
logic> (fact (dog (name barack) (color tan)))<br />
logic> (fact (dog (name clinton) (color white)))<br />
logic> (fact (dog (name delano) (color white)))<br />
logic> (fact (dog (name eisenhower) (color tan)))<br />
logic> (fact (dog (name fillmore) (color brown)))<br />
logic> (fact (dog (name grover) (color tan)))<br />
logic> (fact (dog (name herbert) (color brown)))<br />
<br />
logic> (query (dog (name clinton) (color ?color)))<br />
Success!<br />
color: white<br />
<br />
logic> (query (dog (name clinton) ?info))<br />
Success!<br />
info: (color white)<br />
</syntaxhighlight><br />
<br />
==Sources==<br />
[http://composingprograms.com/pages/43-declarative-programming.html Declarative Programming]</div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/LogicLogic2014-08-10T06:23:15Z<p>Stevencheng: /* Recursion */</p>
<hr />
<div>'''Logic''' is a declarative query programming language, in which the user imputes <code>fact</code> in order to solve a <code>query</code>. Logic is a complete implementation that depends upon the Scheme project as data records are expressed as Scheme lists, and queries are expressed as Scheme values.<br />
<br />
==Facts and Queries==<br />
Logic works by accepting user-stated <code>fact</code> and logically deducing <code>query</code> statements from those facts. A <code>fact</code> statement in <code>logic</code> consists of one or more lists following the keyword <code>fact</code>. Each <code>fact</code> statement is a relation. For example, the first line states that '''the parent of barack is abraham.'''<br />
<syntaxhighlight lang="scheme"><br />
logic> (fact (parent abraham barack))<br />
logic> (fact (parent abraham clinton))<br />
logic> (fact (parent delano herbert))<br />
logic> (fact (parent fillmore abraham))<br />
logic> (fact (parent fillmore delano))<br />
logic> (fact (parent fillmore grover))<br />
logic> (fact (parent eisenhower fillmore))<br />
<br />
<br />
logic> (query (parent abraham ?child))<br />
Success!<br />
child: barack<br />
child: clinton<br />
</syntaxhighlight><br />
Using the facts stated, we can easily find all the parent relations between one and another. Below, the query statement asks for all of the names that have abraham as its parent. If there exists such relationship, <code>logic</code> will output <code>Success!</code> followed all entries that satisfy the <code>query</code>.<br />
<br />
===Compound facts===<br />
<code>(fact <conclusion> <hypothesis0> <hypothesis1> ... <hypothesisN>) </code><br />
<br />
Compound facts are written beginning with a conclusion, followed by hypotheses. For the conclusion to be true, all of the hypotheses must be satisfied.<br />
<br />
<syntaxhighlight lang="scheme"><br />
logic> (fact (child ?c ?p) (parent ?p ?c))<br />
<br />
logic> (query (child ?child fillmore))<br />
Success!<br />
child: abraham<br />
child: delano<br />
child: grover<br />
</syntaxhighlight><br />
<br />
The <code>fact</code> can be read as "?c is the child of ?p, provided that ?p is the parent of ?c."<br />
<br />
==Recursion==<br />
<code>Logic</code> also supports recursion, that is, the conclusion of a fact may depend on a hypothesis that contains the same symbols. <br />
<syntaxhighlight lang="scheme"><br />
logic> (fact (ancestor ?a ?y) (parent ?a ?y))<br />
logic> (fact (ancestor ?a ?y) (parent ?a ?z) (ancestor ?z ?y))<br />
<br />
logic> (query (ancestor ?a herbert))<br />
Success!<br />
a: delano<br />
a: fillmore<br />
a: eisenhower<br />
</syntaxhighlight><br />
<br />
==Hierarchical facts==<br />
Fact and query lists can also contain lists, providing a way to represent hierarchical data. For example, we can assign colors to dog names.<br />
<syntaxhighlight lang="scheme"><br />
logic> (fact (dog (name abraham) (color white)))<br />
logic> (fact (dog (name barack) (color tan)))<br />
logic> (fact (dog (name clinton) (color white)))<br />
logic> (fact (dog (name delano) (color white)))<br />
logic> (fact (dog (name eisenhower) (color tan)))<br />
logic> (fact (dog (name fillmore) (color brown)))<br />
logic> (fact (dog (name grover) (color tan)))<br />
logic> (fact (dog (name herbert) (color brown)))<br />
<br />
logic> (query (dog (name clinton) (color ?color)))<br />
Success!<br />
color: white<br />
<br />
logic> (query (dog (name clinton) ?info))<br />
Success!<br />
info: (color white)<br />
</syntaxhighlight></div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/LogicLogic2014-08-10T06:04:51Z<p>Stevencheng: /* Facts and Queries */</p>
<hr />
<div>'''Logic''' is a declarative query programming language, in which the user imputes <code>fact</code> in order to solve a <code>query</code>. Logic is a complete implementation that depends upon the Scheme project as data records are expressed as Scheme lists, and queries are expressed as Scheme values.<br />
<br />
==Facts and Queries==<br />
Logic works by accepting user-stated <code>fact</code> and logically deducing <code>query</code> statements from those facts. A <code>fact</code> statement in <code>logic</code> consists of one or more lists following the keyword <code>fact</code>. Each <code>fact</code> statement is a relation. For example, the first line states that '''the parent of barack is abraham.'''<br />
<syntaxhighlight lang="scheme"><br />
logic> (fact (parent abraham barack))<br />
logic> (fact (parent abraham clinton))<br />
logic> (fact (parent delano herbert))<br />
logic> (fact (parent fillmore abraham))<br />
logic> (fact (parent fillmore delano))<br />
logic> (fact (parent fillmore grover))<br />
logic> (fact (parent eisenhower fillmore))<br />
<br />
<br />
logic> (query (parent abraham ?child))<br />
Success!<br />
child: barack<br />
child: clinton<br />
</syntaxhighlight><br />
Using the facts stated, we can easily find all the parent relations between one and another. Below, the query statement asks for all of the names that have abraham as its parent. If there exists such relationship, <code>logic</code> will output <code>Success!</code> followed all entries that satisfy the <code>query</code>.<br />
<br />
===Compound facts===<br />
<code>(fact <conclusion> <hypothesis0> <hypothesis1> ... <hypothesisN>) </code><br />
<br />
Compound facts are written beginning with a conclusion, followed by hypotheses. For the conclusion to be true, all of the hypotheses must be satisfied.<br />
<br />
<syntaxhighlight lang="scheme"><br />
logic> (fact (child ?c ?p) (parent ?p ?c))<br />
<br />
logic> (query (child ?child fillmore))<br />
Success!<br />
child: abraham<br />
child: delano<br />
child: grover<br />
</syntaxhighlight><br />
<br />
The <code>fact</code> can be read as "?c is the child of ?p, provided that ?p is the parent of ?c."<br />
<br />
==Recursion==<br />
<code>Logic</code> also supports recursion, that is, the conclusion of a fact may depend on a hypothesis that contains the same symbols. <br />
<syntaxhighlight lang="scheme"><br />
logic> (fact (ancestor ?a ?y) (parent ?a ?y))<br />
logic> (fact (ancestor ?a ?y) (parent ?a ?z) (ancestor ?z ?y))<br />
<br />
logic> (query (ancestor ?a herbert))<br />
Success!<br />
a: delano<br />
a: fillmore<br />
a: eisenhower<br />
</syntaxhighlight></div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/LogicLogic2014-08-10T04:38:51Z<p>Stevencheng: /* Compound facts */</p>
<hr />
<div>'''Logic''' is a declarative query programming language, in which the user imputes <code>fact</code> in order to solve a <code>query</code>. Logic is a complete implementation that depends upon the Scheme project as data records are expressed as Scheme lists, and queries are expressed as Scheme values.<br />
<br />
==Facts and Queries==<br />
Logic works by accepting user-stated <code>fact</code> and logically deducing <code>query</code> statements from those facts. A <code>fact</code> statement in <code>logic</code> consists of one or more lists following the keyword <code>fact</code>. Each <code>fact</code> statement is a relation. For example, the first line states that '''the parent of barack is abraham.'''<br />
<syntaxhighlight lang="scheme"><br />
logic> (fact (parent abraham barack))<br />
logic> (fact (parent abraham clinton))<br />
logic> (fact (parent delano herbert))<br />
logic> (fact (parent fillmore abraham))<br />
logic> (fact (parent fillmore delano))<br />
logic> (fact (parent fillmore grover))<br />
logic> (fact (parent eisenhower fillmore))<br />
<br />
<br />
logic> (query (parent abraham ?child))<br />
Success!<br />
child: barack<br />
child: clinton<br />
</syntaxhighlight><br />
Using the facts stated, we can easily find all the parent relations between one and another. Below, the query statement asks for all of the names that have abraham as its parent. If there exists such relationship, <code>logic</code> will output <code>Success!</code> followed all entries that satisfy the <code>query</code>.<br />
<br />
===Compound facts===<br />
<code>(fact <conclusion> <hypothesis0> <hypothesis1> ... <hypothesisN>) </code><br />
<br />
Compound facts are written beginning with a conclusion, followed by hypotheses. For the conclusion to be true, all of the hypotheses must be satisfied.<br />
<br />
<syntaxhighlight lang="scheme"><br />
logic> (fact (child ?c ?p) (parent ?p ?c))<br />
<br />
logic> (query (child ?child fillmore))<br />
Success!<br />
child: abraham<br />
child: delano<br />
child: grover<br />
</syntaxhighlight><br />
<br />
The <code>fact</code> can be read as "?c is the child of ?p, provided that ?p is the parent of ?c."</div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/LogicLogic2014-08-10T04:35:51Z<p>Stevencheng: /* Facts and Queries */</p>
<hr />
<div>'''Logic''' is a declarative query programming language, in which the user imputes <code>fact</code> in order to solve a <code>query</code>. Logic is a complete implementation that depends upon the Scheme project as data records are expressed as Scheme lists, and queries are expressed as Scheme values.<br />
<br />
==Facts and Queries==<br />
Logic works by accepting user-stated <code>fact</code> and logically deducing <code>query</code> statements from those facts. A <code>fact</code> statement in <code>logic</code> consists of one or more lists following the keyword <code>fact</code>. Each <code>fact</code> statement is a relation. For example, the first line states that '''the parent of barack is abraham.'''<br />
<syntaxhighlight lang="scheme"><br />
logic> (fact (parent abraham barack))<br />
logic> (fact (parent abraham clinton))<br />
logic> (fact (parent delano herbert))<br />
logic> (fact (parent fillmore abraham))<br />
logic> (fact (parent fillmore delano))<br />
logic> (fact (parent fillmore grover))<br />
logic> (fact (parent eisenhower fillmore))<br />
<br />
<br />
logic> (query (parent abraham ?child))<br />
Success!<br />
child: barack<br />
child: clinton<br />
</syntaxhighlight><br />
Using the facts stated, we can easily find all the parent relations between one and another. Below, the query statement asks for all of the names that have abraham as its parent. If there exists such relationship, <code>logic</code> will output <code>Success!</code> followed all entries that satisfy the <code>query</code>.<br />
<br />
===Compound facts===<br />
<code>(fact <conclusion> <hypothesis0> <hypothesis1> ... <hypothesisN>) </code><br />
<br />
Compound facts are written beginning with a conclusion, followed by hypotheses. For the conclusion to be true, all of the hypotheses must be satisfied.<br />
<br />
<syntaxhighlight lang="scheme"><br />
logic> (fact (child ?c ?p) (parent ?p ?c))<br />
<br />
logic> (query (child ?child fillmore))<br />
Success!<br />
child: abraham<br />
child: delano<br />
child: grover<br />
</syntaxhighlight></div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/LogicLogic2014-08-10T04:35:14Z<p>Stevencheng: /* Facts and Queries */</p>
<hr />
<div>'''Logic''' is a declarative query programming language, in which the user imputes <code>fact</code> in order to solve a <code>query</code>. Logic is a complete implementation that depends upon the Scheme project as data records are expressed as Scheme lists, and queries are expressed as Scheme values.<br />
<br />
==Facts and Queries==<br />
Logic works by accepting user-stated <code>fact</code> and logically deducing <code>query</code> statements from those facts. A <code>fact</code> statement in <code>logic</code> consists of one or more lists following the keyword <code>fact</code>. Each <code>fact</code> statement is a relation. For example, the first line states that '''The parent of barack is abraham.'''<br />
<syntaxhighlight lang="logic"><br />
logic> (fact (parent abraham barack))<br />
logic> (fact (parent abraham clinton))<br />
logic> (fact (parent delano herbert))<br />
logic> (fact (parent fillmore abraham))<br />
logic> (fact (parent fillmore delano))<br />
logic> (fact (parent fillmore grover))<br />
logic> (fact (parent eisenhower fillmore))<br />
<br />
<br />
logic> (query (parent abraham ?child))<br />
Success!<br />
child: barack<br />
child: clinton<br />
</syntaxhighlight><br />
Using the facts stated, we can easily find all the parent relations between one and another. Below, the query statement asks for all of the names that have abraham as its parent. If there exists such relationship, <code>logic</code> will output <code>Success!</code> followed all entries that satisfy the <code>query</code>.<br />
<br />
===Compound facts===<br />
<code>(fact <conclusion> <hypothesis0> <hypothesis1> ... <hypothesisN>) </code><br />
<br />
Compound facts are written beginning with a conclusion, followed by hypotheses. For the conclusion to be true, all of the hypotheses must be satisfied.<br />
<br />
<syntaxhighlight><br />
logic> (fact (child ?c ?p) (parent ?p ?c))<br />
<br />
logic> (query (child ?child fillmore))<br />
Success!<br />
child: abraham<br />
child: delano<br />
child: grover<br />
</syntaxhighlight></div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/LogicLogic2014-08-10T04:34:41Z<p>Stevencheng: /* Compound facts */</p>
<hr />
<div>'''Logic''' is a declarative query programming language, in which the user imputes <code>fact</code> in order to solve a <code>query</code>. Logic is a complete implementation that depends upon the Scheme project as data records are expressed as Scheme lists, and queries are expressed as Scheme values.<br />
<br />
==Facts and Queries==<br />
Logic works by accepting user-stated <code>fact</code> and logically deducing <code>query</code> statements from those facts. A <code>fact</code> statement in <code>logic<code> consists of one or more lists following the keyword <code>fact</code>. Each <code>fact</code> statement is a relation. For example, the first line states that '''The parent of barack is abraham.'''<br />
<syntaxhighlight lang="logic"><br />
logic> (fact (parent abraham barack))<br />
logic> (fact (parent abraham clinton))<br />
logic> (fact (parent delano herbert))<br />
logic> (fact (parent fillmore abraham))<br />
logic> (fact (parent fillmore delano))<br />
logic> (fact (parent fillmore grover))<br />
logic> (fact (parent eisenhower fillmore))<br />
<br />
<br />
logic> (query (parent abraham ?child))<br />
Success!<br />
child: barack<br />
child: clinton<br />
</syntaxhighlight><br />
Using the facts stated, we can easily find all the parent relations between one and another. Below, the query statement asks for all of the names that have abraham as its parent. If there exists such relationship, <code>logic</code> will output <code>Success!</code> followed all entries that satisfy the <code>query</code>.<br />
<br />
===Compound facts===<br />
<code>(fact <conclusion> <hypothesis0> <hypothesis1> ... <hypothesisN>) </code><br />
<br />
Compound facts are written beginning with a conclusion, followed by hypotheses. For the conclusion to be true, all of the hypotheses must be satisfied.<br />
<br />
<syntaxhighlight><br />
logic> (fact (child ?c ?p) (parent ?p ?c))<br />
<br />
logic> (query (child ?child fillmore))<br />
Success!<br />
child: abraham<br />
child: delano<br />
child: grover<br />
</syntaxhighlight></div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/LogicLogic2014-08-10T04:34:22Z<p>Stevencheng: /* Compound facts */</p>
<hr />
<div>'''Logic''' is a declarative query programming language, in which the user imputes <code>fact</code> in order to solve a <code>query</code>. Logic is a complete implementation that depends upon the Scheme project as data records are expressed as Scheme lists, and queries are expressed as Scheme values.<br />
<br />
==Facts and Queries==<br />
Logic works by accepting user-stated <code>fact</code> and logically deducing <code>query</code> statements from those facts. A <code>fact</code> statement in <code>logic<code> consists of one or more lists following the keyword <code>fact</code>. Each <code>fact</code> statement is a relation. For example, the first line states that '''The parent of barack is abraham.'''<br />
<syntaxhighlight lang="logic"><br />
logic> (fact (parent abraham barack))<br />
logic> (fact (parent abraham clinton))<br />
logic> (fact (parent delano herbert))<br />
logic> (fact (parent fillmore abraham))<br />
logic> (fact (parent fillmore delano))<br />
logic> (fact (parent fillmore grover))<br />
logic> (fact (parent eisenhower fillmore))<br />
<br />
<br />
logic> (query (parent abraham ?child))<br />
Success!<br />
child: barack<br />
child: clinton<br />
</syntaxhighlight><br />
Using the facts stated, we can easily find all the parent relations between one and another. Below, the query statement asks for all of the names that have abraham as its parent. If there exists such relationship, <code>logic</code> will output <code>Success!</code> followed all entries that satisfy the <code>query</code>.<br />
<br />
===Compound facts===<br />
<code>(fact <conclusion> <hypothesis0> <hypothesis1> ... <hypothesisN>) </code><br />
<br />
Compound facts are written beginning with a conclusion, followed by hypotheses. For the conclusion to be true, all of the hypotheses must be satisfied.<br />
<br />
<syntaxhighlight lang="scheme"><br />
logic> (fact (child ?c ?p) (parent ?p ?c))<br />
<br />
logic> (query (child ?child fillmore))<br />
Success!<br />
child: abraham<br />
child: delano<br />
child: grover<br />
</syntaxhighlight></div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/LogicLogic2014-08-10T04:33:46Z<p>Stevencheng: Created page with "'''Logic''' is a declarative query programming language, in which the user imputes <code>fact</code> in order to solve a <code>query</code>. Logic is a complete implementation..."</p>
<hr />
<div>'''Logic''' is a declarative query programming language, in which the user imputes <code>fact</code> in order to solve a <code>query</code>. Logic is a complete implementation that depends upon the Scheme project as data records are expressed as Scheme lists, and queries are expressed as Scheme values.<br />
<br />
==Facts and Queries==<br />
Logic works by accepting user-stated <code>fact</code> and logically deducing <code>query</code> statements from those facts. A <code>fact</code> statement in <code>logic<code> consists of one or more lists following the keyword <code>fact</code>. Each <code>fact</code> statement is a relation. For example, the first line states that '''The parent of barack is abraham.'''<br />
<syntaxhighlight lang="logic"><br />
logic> (fact (parent abraham barack))<br />
logic> (fact (parent abraham clinton))<br />
logic> (fact (parent delano herbert))<br />
logic> (fact (parent fillmore abraham))<br />
logic> (fact (parent fillmore delano))<br />
logic> (fact (parent fillmore grover))<br />
logic> (fact (parent eisenhower fillmore))<br />
<br />
<br />
logic> (query (parent abraham ?child))<br />
Success!<br />
child: barack<br />
child: clinton<br />
</syntaxhighlight><br />
Using the facts stated, we can easily find all the parent relations between one and another. Below, the query statement asks for all of the names that have abraham as its parent. If there exists such relationship, <code>logic</code> will output <code>Success!</code> followed all entries that satisfy the <code>query</code>.<br />
<br />
===Compound facts===<br />
<code>(fact <conclusion> <hypothesis0> <hypothesis1> ... <hypothesisN>) </code><br />
<br />
Compound facts are written beginning with a conclusion, followed by hypotheses. For the conclusion to be true, all of the hypotheses must be satisfied.<br />
<br />
<syntaxhighlight lang="logic"><br />
logic> (fact (child ?c ?p) (parent ?p ?c))<br />
<br />
logic> (query (child ?child fillmore))<br />
Success!<br />
child: abraham<br />
child: delano<br />
child: grover<br />
</syntaxhighlight></div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/ConcurrencyConcurrency2014-08-09T22:24:47Z<p>Stevencheng: /* Source */</p>
<hr />
<div>'''Concurrency''', or ''parallel computing'', allows for multiple operations to be performed simultaneously. In the past, the speed of individual processor cores grew at an exponential rate, but due to power and thermal constraints, this increase came to an abrupt end. Since then, CPU manufacturers began to place cores in a single processor, allowing for more operations to be performed concurrently.<br />
<br />
==Parallelism in Python==<br />
<br />
===Threading===<br />
In ''threading'', multiple '''"threads"''' of execution exist within a single interpreter. Each thread executes code independently from the others, though they share the same data. <br />
<syntaxhighlight lang="python"><br />
>>> import threading<br />
>>> def thread_hello():<br />
other = threading.Thread(target=thread_say_hello, args=())<br />
other.start()<br />
thread_say_hello()<br />
<br />
>>> def thread_say_hello():<br />
print('hello from', threading.current_thread().name)<br />
<br />
>>> thread_hello()<br />
hello from Thread-1<br />
hello from MainThread<br />
</syntaxhighlight><br />
<br />
===Multiprocessing===<br />
'''Multiprocessing''' allows a program to spawn multiple interpreters, or ''processes, each of which can run code independently, without sharing data so any shared state must be communicated between processes.<br />
<syntaxhighlight lang="python"><br />
>>> import multiprocessing<br />
>>> def process_hello():<br />
other = multiprocessing.Process(target=process_say_hello, args=())<br />
other.start()<br />
process_say_hello()<br />
<br />
>>> def process_say_hello():<br />
print('hello from', multiprocessing.current_process().name)<br />
<br />
>>> process_hello()<br />
hello from MainProcess<br />
>>> hello from Process-1<br />
</syntaxhighlight><br />
<br />
==Synchronized Data Structures==<br />
A <code>Queue</code> is an example of a data structure that provides synchronized operations. The <code>queue</code> module contains a <code>Queue</code> class that provides synchronized first in, first out access to data. The <code>put</code> method adds an item to the <code>Queue</code> and the <code>get</code> method retrieves an item (at the end of the Queue). The class ensures methods are synchronized, so items are not lost no matter how thread operations are intertwined.<br />
<br />
An example of a producer/consumer <code>Queue</code>:<br />
<syntaxhighlight lang="python"><br />
<br />
queue = Queue()<br />
<br />
def synchronized_consume():<br />
while True:<br />
print('got an item:', queue.get())<br />
queue.task_done()<br />
<br />
def synchronized_produce():<br />
consumer = threading.Thread(target=synchronized_consume, args=())<br />
consumer.daemon = True<br />
consumer.start()<br />
for i in range(10):<br />
queue.put(i)<br />
queue.join()<br />
<br />
synchronized_produce()<br />
</syntaxhighlight><br />
<br />
Another use of a <code>Queue</code> is a parallel web crawler that searches for dead links on a website. By following every link hosted by the same site, it continually adds new URLs to a <code>Queue</code>, performs a process on that item, and removes it from the <code>Queue</code> afterwards. By using a synchronized <code>Queue</code>, multiple threads can safely add to and remove from the data structure concurrently.<br />
<br />
==Avoiding Improper Mutation of Shared Data==<br />
===Locks===<br />
When a synchronized version of a particular data structure is not available, we have to provide our own synchronization. A solution to this is a ''lock'', which allows a data structure to be acquired by at most one thread, after which no other thread may acquire it until it is ''released'' by the thread that previously acquired it.<br />
<br />
===Barriers===<br />
Another way to avoid conflicting access to shared data is to divide a program into phases, ensuring that shared data is mutated in a phase in which no other thread accesses it. '''Barriers''' divide a program into phases by requiring all threads to reach it before any of them can proceed. Code that is executed after a barrier cannot be concurrent with code executed before the barrier.<br />
===Message Passing===<br />
Another way is to entirely avoid concurrent access to the same data. Using multiprocessing in Python rather than threading naturally results in this, since processes run in seperate interpreters with their own data.<br />
<br />
==Synchronization Pitfalls==<br />
Incorrectly used synchronization methods can result in the following pitfalls.<br />
===Under-synchronization===<br />
Neglecting to properly synchronize shared accesses.<br />
===Over-synchronization===<br />
Over-synchronizing a program means that non-conflicting operations cannot occur concurrently. <br />
===Deadlock===<br />
Deadlock is a situation in which two or more threads or processes are stuck, waiting for each other to finish. No process can continue because it is waiting for other processes that are waiting for it to complete.<br />
==Source==<br />
[http://composingprograms.com/pages/47-parallel-computing.html Parallel Computing]</div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/ConcurrencyConcurrency2014-08-09T22:24:23Z<p>Stevencheng: /* Synchronization Pitfalls */</p>
<hr />
<div>'''Concurrency''', or ''parallel computing'', allows for multiple operations to be performed simultaneously. In the past, the speed of individual processor cores grew at an exponential rate, but due to power and thermal constraints, this increase came to an abrupt end. Since then, CPU manufacturers began to place cores in a single processor, allowing for more operations to be performed concurrently.<br />
<br />
==Parallelism in Python==<br />
<br />
===Threading===<br />
In ''threading'', multiple '''"threads"''' of execution exist within a single interpreter. Each thread executes code independently from the others, though they share the same data. <br />
<syntaxhighlight lang="python"><br />
>>> import threading<br />
>>> def thread_hello():<br />
other = threading.Thread(target=thread_say_hello, args=())<br />
other.start()<br />
thread_say_hello()<br />
<br />
>>> def thread_say_hello():<br />
print('hello from', threading.current_thread().name)<br />
<br />
>>> thread_hello()<br />
hello from Thread-1<br />
hello from MainThread<br />
</syntaxhighlight><br />
<br />
===Multiprocessing===<br />
'''Multiprocessing''' allows a program to spawn multiple interpreters, or ''processes, each of which can run code independently, without sharing data so any shared state must be communicated between processes.<br />
<syntaxhighlight lang="python"><br />
>>> import multiprocessing<br />
>>> def process_hello():<br />
other = multiprocessing.Process(target=process_say_hello, args=())<br />
other.start()<br />
process_say_hello()<br />
<br />
>>> def process_say_hello():<br />
print('hello from', multiprocessing.current_process().name)<br />
<br />
>>> process_hello()<br />
hello from MainProcess<br />
>>> hello from Process-1<br />
</syntaxhighlight><br />
<br />
==Synchronized Data Structures==<br />
A <code>Queue</code> is an example of a data structure that provides synchronized operations. The <code>queue</code> module contains a <code>Queue</code> class that provides synchronized first in, first out access to data. The <code>put</code> method adds an item to the <code>Queue</code> and the <code>get</code> method retrieves an item (at the end of the Queue). The class ensures methods are synchronized, so items are not lost no matter how thread operations are intertwined.<br />
<br />
An example of a producer/consumer <code>Queue</code>:<br />
<syntaxhighlight lang="python"><br />
<br />
queue = Queue()<br />
<br />
def synchronized_consume():<br />
while True:<br />
print('got an item:', queue.get())<br />
queue.task_done()<br />
<br />
def synchronized_produce():<br />
consumer = threading.Thread(target=synchronized_consume, args=())<br />
consumer.daemon = True<br />
consumer.start()<br />
for i in range(10):<br />
queue.put(i)<br />
queue.join()<br />
<br />
synchronized_produce()<br />
</syntaxhighlight><br />
<br />
Another use of a <code>Queue</code> is a parallel web crawler that searches for dead links on a website. By following every link hosted by the same site, it continually adds new URLs to a <code>Queue</code>, performs a process on that item, and removes it from the <code>Queue</code> afterwards. By using a synchronized <code>Queue</code>, multiple threads can safely add to and remove from the data structure concurrently.<br />
<br />
==Avoiding Improper Mutation of Shared Data==<br />
===Locks===<br />
When a synchronized version of a particular data structure is not available, we have to provide our own synchronization. A solution to this is a ''lock'', which allows a data structure to be acquired by at most one thread, after which no other thread may acquire it until it is ''released'' by the thread that previously acquired it.<br />
<br />
===Barriers===<br />
Another way to avoid conflicting access to shared data is to divide a program into phases, ensuring that shared data is mutated in a phase in which no other thread accesses it. '''Barriers''' divide a program into phases by requiring all threads to reach it before any of them can proceed. Code that is executed after a barrier cannot be concurrent with code executed before the barrier.<br />
===Message Passing===<br />
Another way is to entirely avoid concurrent access to the same data. Using multiprocessing in Python rather than threading naturally results in this, since processes run in seperate interpreters with their own data.<br />
<br />
==Synchronization Pitfalls==<br />
Incorrectly used synchronization methods can result in the following pitfalls.<br />
===Under-synchronization===<br />
Neglecting to properly synchronize shared accesses.<br />
===Over-synchronization===<br />
Over-synchronizing a program means that non-conflicting operations cannot occur concurrently. <br />
===Deadlock===<br />
Deadlock is a situation in which two or more threads or processes are stuck, waiting for each other to finish. No process can continue because it is waiting for other processes that are waiting for it to complete.<br />
==Source==<br />
[[http://composingprograms.com/pages/47-parallel-computing.html Parallel Computing]]</div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/ConcurrencyConcurrency2014-08-09T22:23:26Z<p>Stevencheng: /* Synchronization Pitfalls */</p>
<hr />
<div>'''Concurrency''', or ''parallel computing'', allows for multiple operations to be performed simultaneously. In the past, the speed of individual processor cores grew at an exponential rate, but due to power and thermal constraints, this increase came to an abrupt end. Since then, CPU manufacturers began to place cores in a single processor, allowing for more operations to be performed concurrently.<br />
<br />
==Parallelism in Python==<br />
<br />
===Threading===<br />
In ''threading'', multiple '''"threads"''' of execution exist within a single interpreter. Each thread executes code independently from the others, though they share the same data. <br />
<syntaxhighlight lang="python"><br />
>>> import threading<br />
>>> def thread_hello():<br />
other = threading.Thread(target=thread_say_hello, args=())<br />
other.start()<br />
thread_say_hello()<br />
<br />
>>> def thread_say_hello():<br />
print('hello from', threading.current_thread().name)<br />
<br />
>>> thread_hello()<br />
hello from Thread-1<br />
hello from MainThread<br />
</syntaxhighlight><br />
<br />
===Multiprocessing===<br />
'''Multiprocessing''' allows a program to spawn multiple interpreters, or ''processes, each of which can run code independently, without sharing data so any shared state must be communicated between processes.<br />
<syntaxhighlight lang="python"><br />
>>> import multiprocessing<br />
>>> def process_hello():<br />
other = multiprocessing.Process(target=process_say_hello, args=())<br />
other.start()<br />
process_say_hello()<br />
<br />
>>> def process_say_hello():<br />
print('hello from', multiprocessing.current_process().name)<br />
<br />
>>> process_hello()<br />
hello from MainProcess<br />
>>> hello from Process-1<br />
</syntaxhighlight><br />
<br />
==Synchronized Data Structures==<br />
A <code>Queue</code> is an example of a data structure that provides synchronized operations. The <code>queue</code> module contains a <code>Queue</code> class that provides synchronized first in, first out access to data. The <code>put</code> method adds an item to the <code>Queue</code> and the <code>get</code> method retrieves an item (at the end of the Queue). The class ensures methods are synchronized, so items are not lost no matter how thread operations are intertwined.<br />
<br />
An example of a producer/consumer <code>Queue</code>:<br />
<syntaxhighlight lang="python"><br />
<br />
queue = Queue()<br />
<br />
def synchronized_consume():<br />
while True:<br />
print('got an item:', queue.get())<br />
queue.task_done()<br />
<br />
def synchronized_produce():<br />
consumer = threading.Thread(target=synchronized_consume, args=())<br />
consumer.daemon = True<br />
consumer.start()<br />
for i in range(10):<br />
queue.put(i)<br />
queue.join()<br />
<br />
synchronized_produce()<br />
</syntaxhighlight><br />
<br />
Another use of a <code>Queue</code> is a parallel web crawler that searches for dead links on a website. By following every link hosted by the same site, it continually adds new URLs to a <code>Queue</code>, performs a process on that item, and removes it from the <code>Queue</code> afterwards. By using a synchronized <code>Queue</code>, multiple threads can safely add to and remove from the data structure concurrently.<br />
<br />
==Avoiding Improper Mutation of Shared Data==<br />
===Locks===<br />
When a synchronized version of a particular data structure is not available, we have to provide our own synchronization. A solution to this is a ''lock'', which allows a data structure to be acquired by at most one thread, after which no other thread may acquire it until it is ''released'' by the thread that previously acquired it.<br />
<br />
===Barriers===<br />
Another way to avoid conflicting access to shared data is to divide a program into phases, ensuring that shared data is mutated in a phase in which no other thread accesses it. '''Barriers''' divide a program into phases by requiring all threads to reach it before any of them can proceed. Code that is executed after a barrier cannot be concurrent with code executed before the barrier.<br />
===Message Passing===<br />
Another way is to entirely avoid concurrent access to the same data. Using multiprocessing in Python rather than threading naturally results in this, since processes run in seperate interpreters with their own data.<br />
<br />
==Synchronization Pitfalls==<br />
Incorrectly used synchronization methods can result in the following pitfalls.<br />
===Under-synchronization===<br />
Neglecting to properly synchronize shared accesses.<br />
===Over-synchronization===<br />
Over-synchronizing a program means that non-conflicting operations cannot occur concurrently. <br />
===Deadlock===<br />
Deadlock is a situation in which two or more threads or processes are stuck, waiting for each other to finish. No process can continue because it is waiting for other processes that are waiting for it to complete.</div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/ConcurrencyConcurrency2014-08-09T22:13:28Z<p>Stevencheng: /* Avoiding Improper Mutation of Shared Data */</p>
<hr />
<div>'''Concurrency''', or ''parallel computing'', allows for multiple operations to be performed simultaneously. In the past, the speed of individual processor cores grew at an exponential rate, but due to power and thermal constraints, this increase came to an abrupt end. Since then, CPU manufacturers began to place cores in a single processor, allowing for more operations to be performed concurrently.<br />
<br />
==Parallelism in Python==<br />
<br />
===Threading===<br />
In ''threading'', multiple '''"threads"''' of execution exist within a single interpreter. Each thread executes code independently from the others, though they share the same data. <br />
<syntaxhighlight lang="python"><br />
>>> import threading<br />
>>> def thread_hello():<br />
other = threading.Thread(target=thread_say_hello, args=())<br />
other.start()<br />
thread_say_hello()<br />
<br />
>>> def thread_say_hello():<br />
print('hello from', threading.current_thread().name)<br />
<br />
>>> thread_hello()<br />
hello from Thread-1<br />
hello from MainThread<br />
</syntaxhighlight><br />
<br />
===Multiprocessing===<br />
'''Multiprocessing''' allows a program to spawn multiple interpreters, or ''processes, each of which can run code independently, without sharing data so any shared state must be communicated between processes.<br />
<syntaxhighlight lang="python"><br />
>>> import multiprocessing<br />
>>> def process_hello():<br />
other = multiprocessing.Process(target=process_say_hello, args=())<br />
other.start()<br />
process_say_hello()<br />
<br />
>>> def process_say_hello():<br />
print('hello from', multiprocessing.current_process().name)<br />
<br />
>>> process_hello()<br />
hello from MainProcess<br />
>>> hello from Process-1<br />
</syntaxhighlight><br />
<br />
==Synchronized Data Structures==<br />
A <code>Queue</code> is an example of a data structure that provides synchronized operations. The <code>queue</code> module contains a <code>Queue</code> class that provides synchronized first in, first out access to data. The <code>put</code> method adds an item to the <code>Queue</code> and the <code>get</code> method retrieves an item (at the end of the Queue). The class ensures methods are synchronized, so items are not lost no matter how thread operations are intertwined.<br />
<br />
An example of a producer/consumer <code>Queue</code>:<br />
<syntaxhighlight lang="python"><br />
<br />
queue = Queue()<br />
<br />
def synchronized_consume():<br />
while True:<br />
print('got an item:', queue.get())<br />
queue.task_done()<br />
<br />
def synchronized_produce():<br />
consumer = threading.Thread(target=synchronized_consume, args=())<br />
consumer.daemon = True<br />
consumer.start()<br />
for i in range(10):<br />
queue.put(i)<br />
queue.join()<br />
<br />
synchronized_produce()<br />
</syntaxhighlight><br />
<br />
Another use of a <code>Queue</code> is a parallel web crawler that searches for dead links on a website. By following every link hosted by the same site, it continually adds new URLs to a <code>Queue</code>, performs a process on that item, and removes it from the <code>Queue</code> afterwards. By using a synchronized <code>Queue</code>, multiple threads can safely add to and remove from the data structure concurrently.<br />
<br />
==Avoiding Improper Mutation of Shared Data==<br />
===Locks===<br />
When a synchronized version of a particular data structure is not available, we have to provide our own synchronization. A solution to this is a ''lock'', which allows a data structure to be acquired by at most one thread, after which no other thread may acquire it until it is ''released'' by the thread that previously acquired it.<br />
<br />
===Barriers===<br />
Another way to avoid conflicting access to shared data is to divide a program into phases, ensuring that shared data is mutated in a phase in which no other thread accesses it. '''Barriers''' divide a program into phases by requiring all threads to reach it before any of them can proceed. Code that is executed after a barrier cannot be concurrent with code executed before the barrier.<br />
===Message Passing===<br />
Another way is to entirely avoid concurrent access to the same data. Using multiprocessing in Python rather than threading naturally results in this, since processes run in seperate interpreters with their own data.<br />
<br />
==Synchronization Pitfalls==<br />
<br />
===Under-synchronization===<br />
<br />
===Over-synchronization===<br />
<br />
===Deadlock===</div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/ConcurrencyConcurrency2014-08-09T22:08:22Z<p>Stevencheng: /* Locks */</p>
<hr />
<div>'''Concurrency''', or ''parallel computing'', allows for multiple operations to be performed simultaneously. In the past, the speed of individual processor cores grew at an exponential rate, but due to power and thermal constraints, this increase came to an abrupt end. Since then, CPU manufacturers began to place cores in a single processor, allowing for more operations to be performed concurrently.<br />
<br />
==Parallelism in Python==<br />
<br />
===Threading===<br />
In ''threading'', multiple '''"threads"''' of execution exist within a single interpreter. Each thread executes code independently from the others, though they share the same data. <br />
<syntaxhighlight lang="python"><br />
>>> import threading<br />
>>> def thread_hello():<br />
other = threading.Thread(target=thread_say_hello, args=())<br />
other.start()<br />
thread_say_hello()<br />
<br />
>>> def thread_say_hello():<br />
print('hello from', threading.current_thread().name)<br />
<br />
>>> thread_hello()<br />
hello from Thread-1<br />
hello from MainThread<br />
</syntaxhighlight><br />
<br />
===Multiprocessing===<br />
'''Multiprocessing''' allows a program to spawn multiple interpreters, or ''processes, each of which can run code independently, without sharing data so any shared state must be communicated between processes.<br />
<syntaxhighlight lang="python"><br />
>>> import multiprocessing<br />
>>> def process_hello():<br />
other = multiprocessing.Process(target=process_say_hello, args=())<br />
other.start()<br />
process_say_hello()<br />
<br />
>>> def process_say_hello():<br />
print('hello from', multiprocessing.current_process().name)<br />
<br />
>>> process_hello()<br />
hello from MainProcess<br />
>>> hello from Process-1<br />
</syntaxhighlight><br />
<br />
==Synchronized Data Structures==<br />
A <code>Queue</code> is an example of a data structure that provides synchronized operations. The <code>queue</code> module contains a <code>Queue</code> class that provides synchronized first in, first out access to data. The <code>put</code> method adds an item to the <code>Queue</code> and the <code>get</code> method retrieves an item (at the end of the Queue). The class ensures methods are synchronized, so items are not lost no matter how thread operations are intertwined.<br />
<br />
An example of a producer/consumer <code>Queue</code>:<br />
<syntaxhighlight lang="python"><br />
<br />
queue = Queue()<br />
<br />
def synchronized_consume():<br />
while True:<br />
print('got an item:', queue.get())<br />
queue.task_done()<br />
<br />
def synchronized_produce():<br />
consumer = threading.Thread(target=synchronized_consume, args=())<br />
consumer.daemon = True<br />
consumer.start()<br />
for i in range(10):<br />
queue.put(i)<br />
queue.join()<br />
<br />
synchronized_produce()<br />
</syntaxhighlight><br />
<br />
Another use of a <code>Queue</code> is a parallel web crawler that searches for dead links on a website. By following every link hosted by the same site, it continually adds new URLs to a <code>Queue</code>, performs a process on that item, and removes it from the <code>Queue</code> afterwards. By using a synchronized <code>Queue</code>, multiple threads can safely add to and remove from the data structure concurrently.<br />
<br />
==Avoiding Improper Mutation of Shared Data==<br />
===Locks===<br />
When a synchronized version of a particular data structure is not available, we have to provide our own synchronization. A solution to this is a ''lock'', which allows a data structure to be acquired by at most one thread, after which no other thread may acquire it until it is ''released'' by the thread that previously acquired it.<br />
<br />
===Barriers===<br />
Another way to avoid conflicting access to shared data is to divide a program into phases, ensuring that shared data is mutated in a phase in which no other thread accesses it. '''Barriers''' divide a program into phases by requiring all threads to reach it before any of them can proceed. Code that is executed after a barrier cannot be concurrent with code executed before the barrier.<br />
===Message Passing===<br />
Another way is to entirely avoid concurrent access to the same data. Using multiprocessing in Python rather than threading naturally results in this, since processes run in seperate interpreters with their own data.</div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/ConcurrencyConcurrency2014-08-09T22:07:43Z<p>Stevencheng: /* Avoiding Improper Mutation of Shared Data */</p>
<hr />
<div>'''Concurrency''', or ''parallel computing'', allows for multiple operations to be performed simultaneously. In the past, the speed of individual processor cores grew at an exponential rate, but due to power and thermal constraints, this increase came to an abrupt end. Since then, CPU manufacturers began to place cores in a single processor, allowing for more operations to be performed concurrently.<br />
<br />
==Parallelism in Python==<br />
<br />
===Threading===<br />
In ''threading'', multiple '''"threads"''' of execution exist within a single interpreter. Each thread executes code independently from the others, though they share the same data. <br />
<syntaxhighlight lang="python"><br />
>>> import threading<br />
>>> def thread_hello():<br />
other = threading.Thread(target=thread_say_hello, args=())<br />
other.start()<br />
thread_say_hello()<br />
<br />
>>> def thread_say_hello():<br />
print('hello from', threading.current_thread().name)<br />
<br />
>>> thread_hello()<br />
hello from Thread-1<br />
hello from MainThread<br />
</syntaxhighlight><br />
<br />
===Multiprocessing===<br />
'''Multiprocessing''' allows a program to spawn multiple interpreters, or ''processes, each of which can run code independently, without sharing data so any shared state must be communicated between processes.<br />
<syntaxhighlight lang="python"><br />
>>> import multiprocessing<br />
>>> def process_hello():<br />
other = multiprocessing.Process(target=process_say_hello, args=())<br />
other.start()<br />
process_say_hello()<br />
<br />
>>> def process_say_hello():<br />
print('hello from', multiprocessing.current_process().name)<br />
<br />
>>> process_hello()<br />
hello from MainProcess<br />
>>> hello from Process-1<br />
</syntaxhighlight><br />
<br />
==Synchronized Data Structures==<br />
A <code>Queue</code> is an example of a data structure that provides synchronized operations. The <code>queue</code> module contains a <code>Queue</code> class that provides synchronized first in, first out access to data. The <code>put</code> method adds an item to the <code>Queue</code> and the <code>get</code> method retrieves an item (at the end of the Queue). The class ensures methods are synchronized, so items are not lost no matter how thread operations are intertwined.<br />
<br />
An example of a producer/consumer <code>Queue</code>:<br />
<syntaxhighlight lang="python"><br />
<br />
queue = Queue()<br />
<br />
def synchronized_consume():<br />
while True:<br />
print('got an item:', queue.get())<br />
queue.task_done()<br />
<br />
def synchronized_produce():<br />
consumer = threading.Thread(target=synchronized_consume, args=())<br />
consumer.daemon = True<br />
consumer.start()<br />
for i in range(10):<br />
queue.put(i)<br />
queue.join()<br />
<br />
synchronized_produce()<br />
</syntaxhighlight><br />
<br />
Another use of a <code>Queue</code> is a parallel web crawler that searches for dead links on a website. By following every link hosted by the same site, it continually adds new URLs to a <code>Queue</code>, performs a process on that item, and removes it from the <code>Queue</code> afterwards. By using a synchronized <code>Queue</code>, multiple threads can safely add to and remove from the data structure concurrently.<br />
<br />
==Avoiding Improper Mutation of Shared Data==<br />
===Locks===<br />
When a synchronized version of a particular data structure is not available, we have to provide our own synchronization. A solution to this is a ''lock'', which allows a data structure to be acquired by at most one thread, after which no other thread may acquire it until it is ''realeased'' by the thread that previously acquired it.<br />
===Barriers===<br />
Another way to avoid conflicting access to shared data is to divide a program into phases, ensuring that shared data is mutated in a phase in which no other thread accesses it. '''Barriers''' divide a program into phases by requiring all threads to reach it before any of them can proceed. Code that is executed after a barrier cannot be concurrent with code executed before the barrier.<br />
===Message Passing===<br />
Another way is to entirely avoid concurrent access to the same data. Using multiprocessing in Python rather than threading naturally results in this, since processes run in seperate interpreters with their own data.</div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/ConcurrencyConcurrency2014-08-09T11:20:33Z<p>Stevencheng: /* Avoiding Improper Mutation of Shared Data */</p>
<hr />
<div>'''Concurrency''', or ''parallel computing'', allows for multiple operations to be performed simultaneously. In the past, the speed of individual processor cores grew at an exponential rate, but due to power and thermal constraints, this increase came to an abrupt end. Since then, CPU manufacturers began to place cores in a single processor, allowing for more operations to be performed concurrently.<br />
<br />
==Parallelism in Python==<br />
<br />
===Threading===<br />
In ''threading'', multiple '''"threads"''' of execution exist within a single interpreter. Each thread executes code independently from the others, though they share the same data. <br />
<syntaxhighlight lang="python"><br />
>>> import threading<br />
>>> def thread_hello():<br />
other = threading.Thread(target=thread_say_hello, args=())<br />
other.start()<br />
thread_say_hello()<br />
<br />
>>> def thread_say_hello():<br />
print('hello from', threading.current_thread().name)<br />
<br />
>>> thread_hello()<br />
hello from Thread-1<br />
hello from MainThread<br />
</syntaxhighlight><br />
<br />
===Multiprocessing===<br />
'''Multiprocessing''' allows a program to spawn multiple interpreters, or ''processes, each of which can run code independently, without sharing data so any shared state must be communicated between processes.<br />
<syntaxhighlight lang="python"><br />
>>> import multiprocessing<br />
>>> def process_hello():<br />
other = multiprocessing.Process(target=process_say_hello, args=())<br />
other.start()<br />
process_say_hello()<br />
<br />
>>> def process_say_hello():<br />
print('hello from', multiprocessing.current_process().name)<br />
<br />
>>> process_hello()<br />
hello from MainProcess<br />
>>> hello from Process-1<br />
</syntaxhighlight><br />
<br />
==Synchronized Data Structures==<br />
A <code>Queue</code> is an example of a data structure that provides synchronized operations. The <code>queue</code> module contains a <code>Queue</code> class that provides synchronized first in, first out access to data. The <code>put</code> method adds an item to the <code>Queue</code> and the <code>get</code> method retrieves an item (at the end of the Queue). The class ensures methods are synchronized, so items are not lost no matter how thread operations are intertwined.<br />
<br />
An example of a producer/consumer <code>Queue</code>:<br />
<syntaxhighlight lang="python"><br />
<br />
queue = Queue()<br />
<br />
def synchronized_consume():<br />
while True:<br />
print('got an item:', queue.get())<br />
queue.task_done()<br />
<br />
def synchronized_produce():<br />
consumer = threading.Thread(target=synchronized_consume, args=())<br />
consumer.daemon = True<br />
consumer.start()<br />
for i in range(10):<br />
queue.put(i)<br />
queue.join()<br />
<br />
synchronized_produce()<br />
</syntaxhighlight><br />
<br />
Another use of a <code>Queue</code> is a parallel web crawler that searches for dead links on a website. By following every link hosted by the same site, it continually adds new URLs to a <code>Queue</code>, performs a process on that item, and removes it from the <code>Queue</code> afterwards. By using a synchronized <code>Queue</code>, multiple threads can safely add to and remove from the data structure concurrently.<br />
<br />
==Avoiding Improper Mutation of Shared Data==<br />
===Locks===<br />
<br />
===Barriers===<br />
<br />
===Message Passing===</div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/ConcurrencyConcurrency2014-08-09T07:11:59Z<p>Stevencheng: /* Synchronized Data Structures */</p>
<hr />
<div>'''Concurrency''', or ''parallel computing'', allows for multiple operations to be performed simultaneously. In the past, the speed of individual processor cores grew at an exponential rate, but due to power and thermal constraints, this increase came to an abrupt end. Since then, CPU manufacturers began to place cores in a single processor, allowing for more operations to be performed concurrently.<br />
<br />
==Parallelism in Python==<br />
<br />
===Threading===<br />
In ''threading'', multiple '''"threads"''' of execution exist within a single interpreter. Each thread executes code independently from the others, though they share the same data. <br />
<syntaxhighlight lang="python"><br />
>>> import threading<br />
>>> def thread_hello():<br />
other = threading.Thread(target=thread_say_hello, args=())<br />
other.start()<br />
thread_say_hello()<br />
<br />
>>> def thread_say_hello():<br />
print('hello from', threading.current_thread().name)<br />
<br />
>>> thread_hello()<br />
hello from Thread-1<br />
hello from MainThread<br />
</syntaxhighlight><br />
<br />
===Multiprocessing===<br />
'''Multiprocessing''' allows a program to spawn multiple interpreters, or ''processes, each of which can run code independently, without sharing data so any shared state must be communicated between processes.<br />
<syntaxhighlight lang="python"><br />
>>> import multiprocessing<br />
>>> def process_hello():<br />
other = multiprocessing.Process(target=process_say_hello, args=())<br />
other.start()<br />
process_say_hello()<br />
<br />
>>> def process_say_hello():<br />
print('hello from', multiprocessing.current_process().name)<br />
<br />
>>> process_hello()<br />
hello from MainProcess<br />
>>> hello from Process-1<br />
</syntaxhighlight><br />
<br />
==Synchronized Data Structures==<br />
A <code>Queue</code> is an example of a data structure that provides synchronized operations. The <code>queue</code> module contains a <code>Queue</code> class that provides synchronized first in, first out access to data. The <code>put</code> method adds an item to the <code>Queue</code> and the <code>get</code> method retrieves an item (at the end of the Queue). The class ensures methods are synchronized, so items are not lost no matter how thread operations are intertwined.<br />
<br />
An example of a producer/consumer <code>Queue</code>:<br />
<syntaxhighlight lang="python"><br />
<br />
queue = Queue()<br />
<br />
def synchronized_consume():<br />
while True:<br />
print('got an item:', queue.get())<br />
queue.task_done()<br />
<br />
def synchronized_produce():<br />
consumer = threading.Thread(target=synchronized_consume, args=())<br />
consumer.daemon = True<br />
consumer.start()<br />
for i in range(10):<br />
queue.put(i)<br />
queue.join()<br />
<br />
synchronized_produce()<br />
</syntaxhighlight><br />
<br />
Another use of a <code>Queue</code> is a parallel web crawler that searches for dead links on a website. By following every link hosted by the same site, it continually adds new URLs to a <code>Queue</code>, performs a process on that item, and removes it from the <code>Queue</code> afterwards. By using a synchronized <code>Queue</code>, multiple threads can safely add to and remove from the data structure concurrently.<br />
<br />
==Avoiding Improper Mutation of Shared Data==</div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/ConcurrencyConcurrency2014-08-09T06:47:54Z<p>Stevencheng: /* Parallelism in Python */</p>
<hr />
<div>'''Concurrency''', or ''parallel computing'', allows for multiple operations to be performed simultaneously. In the past, the speed of individual processor cores grew at an exponential rate, but due to power and thermal constraints, this increase came to an abrupt end. Since then, CPU manufacturers began to place cores in a single processor, allowing for more operations to be performed concurrently.<br />
<br />
==Parallelism in Python==<br />
<br />
===Threading===<br />
In ''threading'', multiple '''"threads"''' of execution exist within a single interpreter. Each thread executes code independently from the others, though they share the same data. <br />
<syntaxhighlight lang="python"><br />
>>> import threading<br />
>>> def thread_hello():<br />
other = threading.Thread(target=thread_say_hello, args=())<br />
other.start()<br />
thread_say_hello()<br />
<br />
>>> def thread_say_hello():<br />
print('hello from', threading.current_thread().name)<br />
<br />
>>> thread_hello()<br />
hello from Thread-1<br />
hello from MainThread<br />
</syntaxhighlight><br />
<br />
===Multiprocessing===<br />
'''Multiprocessing''' allows a program to spawn multiple interpreters, or ''processes, each of which can run code independently, without sharing data so any shared state must be communicated between processes.<br />
<syntaxhighlight lang="python"><br />
>>> import multiprocessing<br />
>>> def process_hello():<br />
other = multiprocessing.Process(target=process_say_hello, args=())<br />
other.start()<br />
process_say_hello()<br />
<br />
>>> def process_say_hello():<br />
print('hello from', multiprocessing.current_process().name)<br />
<br />
>>> process_hello()<br />
hello from MainProcess<br />
>>> hello from Process-1<br />
</syntaxhighlight><br />
<br />
==Synchronized Data Structures==<br />
A <code>Queue</code> is an example of a data structure that provides synchronized operations. The <code>queue</code> module contains a <code>Queue</code> class that provides synchronized first in, first out access to data. The <code>put</code> method adds an item to the <code>Queue</code> and the <code>get</code> method retrieves an item (at the end of the Queue). The class ensures methods are synchronized, so items are not lost no matter how thread operations are intertwined.<br />
<br />
An example of a producer/consumer <code>Queue</code>:<br />
<syntaxhighlight lang="python"><br />
<br />
queue = Queue()<br />
<br />
def synchronized_consume():<br />
while True:<br />
print('got an item:', queue.get())<br />
queue.task_done()<br />
<br />
def synchronized_produce():<br />
consumer = threading.Thread(target=synchronized_consume, args=())<br />
consumer.daemon = True<br />
consumer.start()<br />
for i in range(10):<br />
queue.put(i)<br />
queue.join()<br />
<br />
synchronized_produce()<br />
</syntaxhighlight><br />
<br />
Another use of a <code>Queue</code> is a parallel web crawler that searches for dead links on a website. By following every link hosted by the same site, it continually adds new URLs to a <code>Queue</code>, performs a process on that item, and removes it from the <code>Queue</code> afterwards. By using a synchronized <code>Queue</code>, multiple threads can safely add to and remove from the data structure concurrently.</div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/ConcurrencyConcurrency2014-08-09T03:04:35Z<p>Stevencheng: /* Concurrency */</p>
<hr />
<div>'''Concurrency''', or ''parallel computing'', allows for multiple operations to be performed simultaneously. In the past, the speed of individual processor cores grew at an exponential rate, but due to power and thermal constraints, this increase came to an abrupt end. Since then, CPU manufacturers began to place cores in a single processor, allowing for more operations to be performed concurrently.<br />
<br />
==Parallelism in Python==<br />
<br />
===Threading===<br />
In ''threading'', multiple '''"threads"''' of execution exist within a single interpreter. Each thread executes code independently from the others, though they share the same data. <br />
<syntaxhighlight lang="python"><br />
>>> import threading<br />
>>> def thread_hello():<br />
other = threading.Thread(target=thread_say_hello, args=())<br />
other.start()<br />
thread_say_hello()<br />
<br />
>>> def thread_say_hello():<br />
print('hello from', threading.current_thread().name)<br />
<br />
>>> thread_hello()<br />
hello from Thread-1<br />
hello from MainThread<br />
</syntaxhighlight><br />
<br />
===Multiprocessing===<br />
'''Multiprocessing''' allows a program to spawn multiple interpreters, or ''processes, each of which can run code independently, without sharing data.<br />
<syntaxhighlight lang="python"><br />
>>> import multiprocessing<br />
>>> def process_hello():<br />
other = multiprocessing.Process(target=process_say_hello, args=())<br />
other.start()<br />
process_say_hello()<br />
<br />
>>> def process_say_hello():<br />
print('hello from', multiprocessing.current_process().name)<br />
<br />
>>> process_hello()<br />
hello from MainProcess<br />
>>> hello from Process-1<br />
</syntaxhighlight></div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/StreamStream2014-08-09T02:07:13Z<p>Stevencheng: /* Streams */</p>
<hr />
<div>A '''stream''' is basically a sequence, that introduces the technique of ''delayed evaluation''. Similar to a [[linked list]], a stream's nodes are also streams themselves. Unlike a linked list, which must have its entire representation in memory and written explicitly, streams have values that are computed on demand. The first element of a stream can be anything; however, the second element is a zero-argument function that returns a Stream or Stream.empty and '''is never evaluated unless we need it.''' Because of this, streams allow us to create an infinite sequence.<br />
<br />
==The Stream ADT==<br />
<br />
* <code>cons-stream</code> - makes a new stream (see '''Examples''' below for more)<br />
<br />
* <code>stream-car</code> - returns the ''first'' of a given stream.<br />
<br />
* <code>stream-cdr</code> - returns the ''rest'' of a given stream.<br />
<br />
* <code>the-empty-stream</code> - an empty stream; similar to list.empty (use to prevent an infinite stream)<br />
<br />
==Examples==<br />
<br />
A finite stream containing the values 1, 2, 3:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define first (cons-stream 1 (cons-stream 2 (cons-stream 3 the-empty-stream))))<br />
</syntaxhighlight><br />
<br />
An infinite stream of 1's and 2's:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define ones (cons-stream 1 ones))<br />
(define twos (cons-stream 2 twos))<br />
</syntaxhighlight><br />
<br />
An infinite stream of natural numbers (1, 2, 3, ...):<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define (make-nats n)<br />
(cons-stream n (make-nats (+ n 1))))<br />
<br />
(define nats (make-nats 1))<br />
</syntaxhighlight><br />
<br />
An infinite stream containing the Fibonacci sequence:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define fib-stream (cons-stream 1 <br />
(cons-stream 1<br />
(stream-add fib-stream (stream-cdr fib-stream)))))<br />
</syntaxhighlight><br />
<br />
==Useful Stream Functions==<br />
Stream addition:<br />
<syntaxhighlight lang='scheme'><br />
(define (stream-add a b)<br />
(if (equal? a the-empty-stream)<br />
a<br />
(if (equal? b the-empty-stream)<br />
b<br />
(cons-stream (+ (stream-car a) (stream-car b))<br />
(stream-add (stream-cdr a)<br />
(stream-cdr b))))))<br />
</syntaxhighlight><br />
<br />
Show stream: outputs the first 10 elements of a stream<br />
<br />
<syntaxhighlight lang='scheme'><br />
STK> (ss (add-streams ones twos))<br />
(3 3 3 3 3 3 3 3 3 3 ...)<br />
</syntaxhighlight><br />
<br />
Takes in a stream and an index and outputs the element<br />
<br />
<syntaxhighlight lang='scheme'><br />
STK> (stream-ref nats 1378)<br />
1378<br />
</syntaxhighlight><br />
<br />
==Sources==<br />
[https://docs.google.com/presentation/d/1sm8o5VlVUsVkFT4kQpONLbCmCp_DaaMoQvUvoeZbwMA/edit#slide=id.p Streams]</div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/StreamStream2014-08-09T01:43:51Z<p>Stevencheng: /* Useful Stream Functions */</p>
<hr />
<div>==Streams==<br />
A '''stream''' is basically a sequence, that introduces the technique of ''delayed evaluation''. Similar to a [[linked list]], a stream's nodes are also streams themselves. Unlike a linked list, which must have its entire representation in memory and written explicitly, streams have values that are computed on demand. The first element of a stream can be anything; however, the second element is a zero-argument function that returns a Stream or Stream.empty and '''is never evaluated unless we need it.''' Because of this, streams allow us to create an infinite sequence.<br />
<br />
==The Stream ADT==<br />
<br />
* <code>cons-stream</code> - makes a new stream (see '''Examples''' below for more)<br />
<br />
* <code>stream-car</code> - returns the ''first'' of a given stream.<br />
<br />
* <code>stream-cdr</code> - returns the ''rest'' of a given stream.<br />
<br />
* <code>the-empty-stream</code> - an empty stream; similar to list.empty (use to prevent an infinite stream)<br />
<br />
==Examples==<br />
<br />
A finite stream containing the values 1, 2, 3:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define first (cons-stream 1 (cons-stream 2 (cons-stream 3 the-empty-stream))))<br />
</syntaxhighlight><br />
<br />
An infinite stream of 1's and 2's:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define ones (cons-stream 1 ones))<br />
(define twos (cons-stream 2 twos))<br />
</syntaxhighlight><br />
<br />
An infinite stream of natural numbers (1, 2, 3, ...):<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define (make-nats n)<br />
(cons-stream n (make-nats (+ n 1))))<br />
<br />
(define nats (make-nats 1))<br />
</syntaxhighlight><br />
<br />
An infinite stream containing the Fibonacci sequence:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define fib-stream (cons-stream 1 <br />
(cons-stream 1<br />
(stream-add fib-stream (stream-cdr fib-stream)))))<br />
</syntaxhighlight><br />
<br />
==Useful Stream Functions==<br />
Stream addition:<br />
<syntaxhighlight lang='scheme'><br />
(define (stream-add a b)<br />
(if (equal? a the-empty-stream)<br />
a<br />
(if (equal? b the-empty-stream)<br />
b<br />
(cons-stream (+ (stream-car a) (stream-car b))<br />
(stream-add (stream-cdr a)<br />
(stream-cdr b))))))<br />
</syntaxhighlight><br />
<br />
Show stream: outputs the first 10 elements of a stream<br />
<br />
<syntaxhighlight lang='scheme'><br />
STK> (ss (add-streams ones twos))<br />
(3 3 3 3 3 3 3 3 3 3 ...)<br />
</syntaxhighlight><br />
<br />
Takes in a stream and an index and outputs the element<br />
<br />
<syntaxhighlight lang='scheme'><br />
STK> (stream-ref nats 1378)<br />
1378<br />
</syntaxhighlight><br />
<br />
==Sources==<br />
[https://docs.google.com/presentation/d/1sm8o5VlVUsVkFT4kQpONLbCmCp_DaaMoQvUvoeZbwMA/edit#slide=id.p Streams]</div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/ConcurrencyConcurrency2014-08-09T01:39:29Z<p>Stevencheng: Created page with "==Concurrency=="</p>
<hr />
<div>==Concurrency==</div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/StreamStream2014-08-09T00:43:57Z<p>Stevencheng: /* Streams */</p>
<hr />
<div>==Streams==<br />
A '''stream''' is basically a sequence, that introduces the technique of ''delayed evaluation''. Similar to a [[linked list]], a stream's nodes are also streams themselves. Unlike a linked list, which must have its entire representation in memory and written explicitly, streams have values that are computed on demand. The first element of a stream can be anything; however, the second element is a zero-argument function that returns a Stream or Stream.empty and '''is never evaluated unless we need it.''' Because of this, streams allow us to create an infinite sequence.<br />
<br />
==The Stream ADT==<br />
<br />
* <code>cons-stream</code> - makes a new stream (see '''Examples''' below for more)<br />
<br />
* <code>stream-car</code> - returns the ''first'' of a given stream.<br />
<br />
* <code>stream-cdr</code> - returns the ''rest'' of a given stream.<br />
<br />
* <code>the-empty-stream</code> - an empty stream; similar to list.empty (use to prevent an infinite stream)<br />
<br />
==Examples==<br />
<br />
A finite stream containing the values 1, 2, 3:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define first (cons-stream 1 (cons-stream 2 (cons-stream 3 the-empty-stream))))<br />
</syntaxhighlight><br />
<br />
An infinite stream of 1's and 2's:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define ones (cons-stream 1 ones))<br />
(define twos (cons-stream 2 twos))<br />
</syntaxhighlight><br />
<br />
An infinite stream of natural numbers (1, 2, 3, ...):<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define (make-nats n)<br />
(cons-stream n (make-nats (+ n 1))))<br />
<br />
(define nats (make-nats 1))<br />
</syntaxhighlight><br />
<br />
An infinite stream containing the Fibonacci sequence:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define fib-stream (cons-stream 1 <br />
(cons-stream 1<br />
(stream-add fib-stream (stream-cdr fib-stream)))))<br />
</syntaxhighlight><br />
<br />
==Useful Stream Functions==<br />
Stream addition:<br />
<syntaxhighlight lang='scheme'><br />
(define (stream-add a b)<br />
(if (equal? a the-empty-stream)<br />
a<br />
(if (equal? b the-empty-stream)<br />
b<br />
(cons-stream (+ (stream-car a) (stream-car b))<br />
(stream-add (stream-cdr a)<br />
(stream-cdr b))))))<br />
</syntaxhighlight><br />
<br />
Show stream: outputs the first 10 elements of a stream<br />
<br />
<syntaxhighlight lang='scheme'><br />
STK> (ss (add-streams ones twos))<br />
(3 3 3 3 3 3 3 3 3 3 ...)<br />
</syntaxhighlight><br />
<br />
Takes in a stream and an index and outputs the element<br />
<br />
<syntaxhighlight lang='scheme'><br />
STK> (stream-ref nats 1378)<br />
1378<br />
</syntaxhighlight></div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/StreamStream2014-08-09T00:29:53Z<p>Stevencheng: /* Useful Stream Functions */</p>
<hr />
<div>==Streams==<br />
A '''stream''' is basically a sequence, that introduces the technique of ''delayed evaluation''. Similar to a [[linked list]], a stream's nodes are also streams themselves. Unlike a linked list, which must have its entire representation in memory and written explicitly, streams have values that are computed on demand. The first element of a stream can be anything; however, the second element is a zero-argument function that returns a Stream or Stream.empty. Because of this, streams allow us to create an infinite sequence.<br />
<br />
==The Stream ADT==<br />
<br />
* <code>cons-stream</code> - makes a new stream (see '''Examples''' below for more)<br />
<br />
* <code>stream-car</code> - returns the ''first'' of a given stream.<br />
<br />
* <code>stream-cdr</code> - returns the ''rest'' of a given stream.<br />
<br />
* <code>the-empty-stream</code> - an empty stream; similar to list.empty (use to prevent an infinite stream)<br />
<br />
==Examples==<br />
<br />
A finite stream containing the values 1, 2, 3:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define first (cons-stream 1 (cons-stream 2 (cons-stream 3 the-empty-stream))))<br />
</syntaxhighlight><br />
<br />
An infinite stream of 1's and 2's:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define ones (cons-stream 1 ones))<br />
(define twos (cons-stream 2 twos))<br />
</syntaxhighlight><br />
<br />
An infinite stream of natural numbers (1, 2, 3, ...):<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define (make-nats n)<br />
(cons-stream n (make-nats (+ n 1))))<br />
<br />
(define nats (make-nats 1))<br />
</syntaxhighlight><br />
<br />
An infinite stream containing the Fibonacci sequence:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define fib-stream (cons-stream 1 <br />
(cons-stream 1<br />
(stream-add fib-stream (stream-cdr fib-stream)))))<br />
</syntaxhighlight><br />
<br />
==Useful Stream Functions==<br />
Stream addition:<br />
<syntaxhighlight lang='scheme'><br />
(define (stream-add a b)<br />
(if (equal? a the-empty-stream)<br />
a<br />
(if (equal? b the-empty-stream)<br />
b<br />
(cons-stream (+ (stream-car a) (stream-car b))<br />
(stream-add (stream-cdr a)<br />
(stream-cdr b))))))<br />
</syntaxhighlight><br />
<br />
Show stream: outputs the first 10 elements of a stream<br />
<br />
<syntaxhighlight lang='scheme'><br />
STK> (ss (add-streams ones twos))<br />
(3 3 3 3 3 3 3 3 3 3 ...)<br />
</syntaxhighlight><br />
<br />
Takes in a stream and an index and outputs the element<br />
<br />
<syntaxhighlight lang='scheme'><br />
STK> (stream-ref nats 1378)<br />
1378<br />
</syntaxhighlight></div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/StreamStream2014-08-09T00:29:15Z<p>Stevencheng: /* Useful Stream Functions */</p>
<hr />
<div>==Streams==<br />
A '''stream''' is basically a sequence, that introduces the technique of ''delayed evaluation''. Similar to a [[linked list]], a stream's nodes are also streams themselves. Unlike a linked list, which must have its entire representation in memory and written explicitly, streams have values that are computed on demand. The first element of a stream can be anything; however, the second element is a zero-argument function that returns a Stream or Stream.empty. Because of this, streams allow us to create an infinite sequence.<br />
<br />
==The Stream ADT==<br />
<br />
* <code>cons-stream</code> - makes a new stream (see '''Examples''' below for more)<br />
<br />
* <code>stream-car</code> - returns the ''first'' of a given stream.<br />
<br />
* <code>stream-cdr</code> - returns the ''rest'' of a given stream.<br />
<br />
* <code>the-empty-stream</code> - an empty stream; similar to list.empty (use to prevent an infinite stream)<br />
<br />
==Examples==<br />
<br />
A finite stream containing the values 1, 2, 3:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define first (cons-stream 1 (cons-stream 2 (cons-stream 3 the-empty-stream))))<br />
</syntaxhighlight><br />
<br />
An infinite stream of 1's and 2's:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define ones (cons-stream 1 ones))<br />
(define twos (cons-stream 2 twos))<br />
</syntaxhighlight><br />
<br />
An infinite stream of natural numbers (1, 2, 3, ...):<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define (make-nats n)<br />
(cons-stream n (make-nats (+ n 1))))<br />
<br />
(define nats (make-nats 1))<br />
</syntaxhighlight><br />
<br />
An infinite stream containing the Fibonacci sequence:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define fib-stream (cons-stream 1 <br />
(cons-stream 1<br />
(stream-add fib-stream (stream-cdr fib-stream)))))<br />
</syntaxhighlight><br />
<br />
==Useful Stream Functions==<br />
Stream addition:<br />
<syntaxhighlight lang='scheme'><br />
(define (stream-add a b)<br />
(if (equal? a the-empty-stream)<br />
a<br />
(if (equal? b the-empty-stream)<br />
b<br />
(cons-stream (+ (stream-car a) (stream-car b))<br />
(stream-add (stream-cdr a)<br />
(stream-cdr b))))))<br />
</syntaxhighlight><br />
<br />
Show stream: outputs the first 10 elements of a stream<br />
<br />
<syntaxhighlight lang='scheme'><br />
STK> (ss (add-streams ones twos))<br />
(3 3 3 3 3 3 3 3 3 3 ...)<br />
</syntaxhighlight><br />
<br />
Takes in a stream and an index and outputs the element<br />
STK> (stream-ref nats 1378)<br />
1378</div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/StreamStream2014-08-09T00:22:18Z<p>Stevencheng: /* Examples */</p>
<hr />
<div>==Streams==<br />
A '''stream''' is basically a sequence, that introduces the technique of ''delayed evaluation''. Similar to a [[linked list]], a stream's nodes are also streams themselves. Unlike a linked list, which must have its entire representation in memory and written explicitly, streams have values that are computed on demand. The first element of a stream can be anything; however, the second element is a zero-argument function that returns a Stream or Stream.empty. Because of this, streams allow us to create an infinite sequence.<br />
<br />
==The Stream ADT==<br />
<br />
* <code>cons-stream</code> - makes a new stream (see '''Examples''' below for more)<br />
<br />
* <code>stream-car</code> - returns the ''first'' of a given stream.<br />
<br />
* <code>stream-cdr</code> - returns the ''rest'' of a given stream.<br />
<br />
* <code>the-empty-stream</code> - an empty stream; similar to list.empty (use to prevent an infinite stream)<br />
<br />
==Examples==<br />
<br />
A finite stream containing the values 1, 2, 3:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define first (cons-stream 1 (cons-stream 2 (cons-stream 3 the-empty-stream))))<br />
</syntaxhighlight><br />
<br />
An infinite stream of 1's and 2's:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define ones (cons-stream 1 ones))<br />
(define twos (cons-stream 2 twos))<br />
</syntaxhighlight><br />
<br />
An infinite stream of natural numbers (1, 2, 3, ...):<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define (make-nats n)<br />
(cons-stream n (make-nats (+ n 1))))<br />
<br />
(define nats (make-nats 1))<br />
</syntaxhighlight><br />
<br />
An infinite stream containing the Fibonacci sequence:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define fib-stream (cons-stream 1 <br />
(cons-stream 1<br />
(stream-add fib-stream (stream-cdr fib-stream)))))<br />
</syntaxhighlight><br />
<br />
==Useful Stream Functions==<br />
Stream addition:<br />
<syntaxhighlight lang='scheme'><br />
(define (stream-add a b)<br />
(if (equal? a the-empty-stream)<br />
a<br />
(if (equal? b the-empty-stream)<br />
b<br />
(cons-stream (+ (stream-car a) (stream-car b))<br />
(stream-add (stream-cdr a)<br />
(stream-cdr b))))))<br />
</syntaxhighlight></div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/StreamStream2014-08-09T00:12:46Z<p>Stevencheng: /* The Stream ADT */</p>
<hr />
<div>==Streams==<br />
A '''stream''' is basically a sequence, that introduces the technique of ''delayed evaluation''. Similar to a [[linked list]], a stream's nodes are also streams themselves. Unlike a linked list, which must have its entire representation in memory and written explicitly, streams have values that are computed on demand. The first element of a stream can be anything; however, the second element is a zero-argument function that returns a Stream or Stream.empty. Because of this, streams allow us to create an infinite sequence.<br />
<br />
==The Stream ADT==<br />
<br />
* <code>cons-stream</code> - makes a new stream (see '''Examples''' below for more)<br />
<br />
* <code>stream-car</code> - returns the ''first'' of a given stream.<br />
<br />
* <code>stream-cdr</code> - returns the ''rest'' of a given stream.<br />
<br />
* <code>the-empty-stream</code> - an empty stream; similar to list.empty (use to prevent an infinite stream)<br />
<br />
==Examples==<br />
<br />
A finite stream containing the values 1, 2, 3:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define first (cons-stream 1 (cons-stream 2 (cons-stream 3 the-empty-stream))))<br />
</syntaxhighlight><br />
<br />
An infinite stream of 1's and 2's:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define ones (cons-stream 1 ones))<br />
(define twos (cons-stream 2 twos))<br />
</syntaxhighlight><br />
<br />
An infinite stream of natural numbers (1, 2, 3, ...):<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define (make-nats n)<br />
(cons-stream n (make-nats (+ n 1))))<br />
<br />
(define nats (make-nats 1))<br />
</syntaxhighlight><br />
<br />
An infinite stream containing the Fibonacci sequence:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define fib-stream (cons-stream 1 <br />
(cons-stream 1<br />
(stream-add fib-stream (stream-cdr fib-stream)))))<br />
</syntaxhighlight></div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/StreamStream2014-08-09T00:12:22Z<p>Stevencheng: /* Examples */</p>
<hr />
<div>==Streams==<br />
A '''stream''' is basically a sequence, that introduces the technique of ''delayed evaluation''. Similar to a [[linked list]], a stream's nodes are also streams themselves. Unlike a linked list, which must have its entire representation in memory and written explicitly, streams have values that are computed on demand. The first element of a stream can be anything; however, the second element is a zero-argument function that returns a Stream or Stream.empty. Because of this, streams allow us to create an infinite sequence.<br />
<br />
==The Stream ADT==<br />
<br />
* <code>cons-stream</code> - makes a new stream (see ''Example'' below for more)<br />
<br />
* <code>stream-car</code> - returns the ''first'' of a given stream.<br />
<br />
* <code>stream-cdr</code> - returns the ''rest'' of a given stream.<br />
<br />
* <code>the-empty-stream</code> - an empty stream; similar to list.empty (use to prevent an infinite stream)<br />
<br />
==Examples==<br />
<br />
A finite stream containing the values 1, 2, 3:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define first (cons-stream 1 (cons-stream 2 (cons-stream 3 the-empty-stream))))<br />
</syntaxhighlight><br />
<br />
An infinite stream of 1's and 2's:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define ones (cons-stream 1 ones))<br />
(define twos (cons-stream 2 twos))<br />
</syntaxhighlight><br />
<br />
An infinite stream of natural numbers (1, 2, 3, ...):<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define (make-nats n)<br />
(cons-stream n (make-nats (+ n 1))))<br />
<br />
(define nats (make-nats 1))<br />
</syntaxhighlight><br />
<br />
An infinite stream containing the Fibonacci sequence:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define fib-stream (cons-stream 1 <br />
(cons-stream 1<br />
(stream-add fib-stream (stream-cdr fib-stream)))))<br />
</syntaxhighlight></div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/StreamStream2014-08-09T00:11:43Z<p>Stevencheng: /* Examples */</p>
<hr />
<div>==Streams==<br />
A '''stream''' is basically a sequence, that introduces the technique of ''delayed evaluation''. Similar to a [[linked list]], a stream's nodes are also streams themselves. Unlike a linked list, which must have its entire representation in memory and written explicitly, streams have values that are computed on demand. The first element of a stream can be anything; however, the second element is a zero-argument function that returns a Stream or Stream.empty. Because of this, streams allow us to create an infinite sequence.<br />
<br />
==The Stream ADT==<br />
<br />
* <code>cons-stream</code> - makes a new stream (see ''Example'' below for more)<br />
<br />
* <code>stream-car</code> - returns the ''first'' of a given stream.<br />
<br />
* <code>stream-cdr</code> - returns the ''rest'' of a given stream.<br />
<br />
* <code>the-empty-stream</code> - an empty stream; similar to list.empty (use to prevent an infinite stream)<br />
<br />
==Examples==<br />
<br />
A finite stream containing the values 1, 2, 3:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define first (cons-stream 1 (cons-stream 2 (cons-stream 3 the-empty-stream))))<br />
</syntaxhighlight><br />
<br />
An infinite stream of 1's and 2's:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define ones (cons-stream 1 ones))<br />
(define twos (cons-stream 2 twos))<br />
</syntaxhighlight><br />
<br />
An infinite stream of natural numbers (1, 2, 3, ...):<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define (make-nats n)<br />
(cons-stream n (make-nats (+ n 1))))<br />
<br />
(define nats (make-nats 1))<br />
</syntaxhighlight><br />
<br />
An infinite stream containing the Fibonacci sequence:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define fib-stream (cons-stream 1 <br />
(cons-stream 1<br />
(stream-add fib-stream (stream-cdr fib-stream)))))</div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/StreamStream2014-08-09T00:08:16Z<p>Stevencheng: /* Examples */</p>
<hr />
<div>==Streams==<br />
A '''stream''' is basically a sequence, that introduces the technique of ''delayed evaluation''. Similar to a [[linked list]], a stream's nodes are also streams themselves. Unlike a linked list, which must have its entire representation in memory and written explicitly, streams have values that are computed on demand. The first element of a stream can be anything; however, the second element is a zero-argument function that returns a Stream or Stream.empty. Because of this, streams allow us to create an infinite sequence.<br />
<br />
==The Stream ADT==<br />
<br />
* <code>cons-stream</code> - makes a new stream (see ''Example'' below for more)<br />
<br />
* <code>stream-car</code> - returns the ''first'' of a given stream.<br />
<br />
* <code>stream-cdr</code> - returns the ''rest'' of a given stream.<br />
<br />
* <code>the-empty-stream</code> - an empty stream; similar to list.empty (use to prevent an infinite stream)<br />
<br />
==Examples==<br />
<br />
A finite stream containing the values 1, 2, 3:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define first (cons-stream 1 (cons-stream 2 (cons-stream 3 the-empty-stream))))<br />
</syntaxhighlight><br />
<br />
An infinite stream of 1's and 2's:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define ones (cons-stream 1 ones))<br />
(define twos (cons-stream 2 twos))<br />
</syntaxhighlight><br />
<br />
An infinite stream of natural numbers (1, 2, 3, ...):<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define (make-nats n)<br />
(cons-stream n (make-nats (+ n 1))))<br />
<br />
(define nats (make-nats 1))<br />
</syntaxhighlight></div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/StreamStream2014-08-09T00:07:30Z<p>Stevencheng: /* The Stream ADT */</p>
<hr />
<div>==Streams==<br />
A '''stream''' is basically a sequence, that introduces the technique of ''delayed evaluation''. Similar to a [[linked list]], a stream's nodes are also streams themselves. Unlike a linked list, which must have its entire representation in memory and written explicitly, streams have values that are computed on demand. The first element of a stream can be anything; however, the second element is a zero-argument function that returns a Stream or Stream.empty. Because of this, streams allow us to create an infinite sequence.<br />
<br />
==The Stream ADT==<br />
<br />
* <code>cons-stream</code> - makes a new stream (see ''Example'' below for more)<br />
<br />
* <code>stream-car</code> - returns the ''first'' of a given stream.<br />
<br />
* <code>stream-cdr</code> - returns the ''rest'' of a given stream.<br />
<br />
* <code>the-empty-stream</code> - an empty stream; similar to list.empty (use to prevent an infinite stream)<br />
<br />
==Examples==<br />
<br />
A stream containing the values 1, 2, 3:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define first (cons-stream 1 (cons-stream 2 (cons-stream 3 the-empty-stream))))<br />
</syntaxhighlight><br />
<br />
An infinite stream of 1's and 2's:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define ones (cons-stream 1 ones))<br />
(define twos (cons-stream 2 twos))<br />
</syntaxhighlight><br />
<br />
An infinite stream of natural numbers (1, 2, 3, ...):<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define (make-nats n)<br />
(cons-stream n (make-nats (+ n 1))))<br />
<br />
(define nats (make-nats 1))<br />
</syntaxhighlight></div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/StreamStream2014-08-09T00:05:53Z<p>Stevencheng: /* The Stream ADT */</p>
<hr />
<div>==Streams==<br />
A '''stream''' is basically a sequence, that introduces the technique of ''delayed evaluation''. Similar to a [[linked list]], a stream's nodes are also streams themselves. Unlike a linked list, which must have its entire representation in memory and written explicitly, streams have values that are computed on demand. The first element of a stream can be anything; however, the second element is a zero-argument function that returns a Stream or Stream.empty. Because of this, streams allow us to create an infinite sequence.<br />
<br />
==The Stream ADT==<br />
<br />
* <code>cons-stream</code> - makes a new stream (see ''Example'' below for more)<br />
<br />
* <code>stream-car</code> - returns the ''first'' of a given stream.<br />
<br />
* <code>stream-cdr</code> - returns the ''rest'' of a given stream.<br />
<br />
==Examples==<br />
<br />
A stream containing the values 1, 2, 3:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define first (cons-stream 1 (cons-stream 2 (cons-stream 3 the-empty-stream))))<br />
</syntaxhighlight><br />
<br />
An infinite stream of 1's and 2's:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define ones (cons-stream 1 ones))<br />
(define twos (cons-stream 2 twos))<br />
</syntaxhighlight><br />
<br />
An infinite stream of natural numbers (1, 2, 3, ...):<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define (make-nats n)<br />
(cons-stream n (make-nats (+ n 1))))<br />
<br />
(define nats (make-nats 1))<br />
</syntaxhighlight></div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/StreamStream2014-08-08T23:59:48Z<p>Stevencheng: /* The Stream ADT */</p>
<hr />
<div>==Streams==<br />
A '''stream''' is basically a sequence, that introduces the technique of ''delayed evaluation''. Similar to a [[linked list]], a stream's nodes are also streams themselves. Unlike a linked list, which must have its entire representation in memory and written explicitly, streams have values that are computed on demand. The first element of a stream can be anything; however, the second element is a zero-argument function that returns a Stream or Stream.empty. Because of this, streams allow us to create an infinite sequence.<br />
<br />
==The Stream ADT==<br />
<br />
To make a new stream (see ''Example'' below for more):<br />
<syntaxhighlight lang='scheme'><br />
cons-stream<br />
</syntaxhighlight><br />
Returns the ''first'' of a given stream:<br />
<syntaxhighlight lang='scheme'><br />
stream-car<br />
</syntaxhighlight><br />
Returns the ''rest'' of a given stream:<br />
<syntaxhighlight lang='scheme'><br />
stream-cdr<br />
</syntaxhighlight><br />
<br />
==Examples==<br />
<br />
A stream containing the values 1, 2, 3:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define first (cons-stream 1 (cons-stream 2 (cons-stream 3 the-empty-stream))))<br />
</syntaxhighlight><br />
<br />
An infinite stream of 1's and 2's:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define ones (cons-stream 1 ones))<br />
(define twos (cons-stream 2 twos))<br />
</syntaxhighlight><br />
<br />
An infinite stream of natural numbers (1, 2, 3, ...):<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define (make-nats n)<br />
(cons-stream n (make-nats (+ n 1))))<br />
<br />
(define nats (make-nats 1))<br />
</syntaxhighlight></div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/StreamStream2014-08-08T23:57:49Z<p>Stevencheng: /* Streams */</p>
<hr />
<div>==Streams==<br />
A '''stream''' is basically a sequence, that introduces the technique of ''delayed evaluation''. Similar to a [[linked list]], a stream's nodes are also streams themselves. Unlike a linked list, which must have its entire representation in memory and written explicitly, streams have values that are computed on demand. The first element of a stream can be anything; however, the second element is a zero-argument function that returns a Stream or Stream.empty. Because of this, streams allow us to create an infinite sequence.<br />
<br />
==The Stream ADT==<br />
<br />
To make a new stream:<br />
<syntaxhighlight lang='scheme'><br />
cons-stream<br />
</syntaxhighlight><br />
Returns the ''first'' of a given stream:<br />
<syntaxhighlight lang='scheme'><br />
stream-car<br />
</syntaxhighlight><br />
Returns the ''rest'' of a given stream:<br />
<syntaxhighlight lang='scheme'><br />
stream-cdr<br />
</syntaxhighlight><br />
<br />
==Examples==<br />
<br />
A stream containing the values 1, 2, 3:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define first (cons-stream 1 (cons-stream 2 (cons-stream 3 the-empty-stream))))<br />
</syntaxhighlight><br />
<br />
An infinite stream of 1's and 2's:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define ones (cons-stream 1 ones))<br />
(define twos (cons-stream 2 twos))<br />
</syntaxhighlight><br />
<br />
An infinite stream of natural numbers (1, 2, 3, ...):<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define (make-nats n)<br />
(cons-stream n (make-nats (+ n 1))))<br />
<br />
(define nats (make-nats 1))<br />
</syntaxhighlight></div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/StreamStream2014-08-08T23:53:24Z<p>Stevencheng: </p>
<hr />
<div>==Streams==<br />
A '''stream''' is basically a sequence, that introduces the technique of ''delayed evaluation''. Similar to a [[linked list]], a stream's nodes are also streams themselves. Unlike a linked list, which must have its entire representation in memory and written explicitly, streams have values that are computed on demand. The first element of a stream can be anything; however, the second element is a zero-argument function that returns a Stream or Stream.empty. Because of this, streams allow us to create an infinite sequence.<br />
<br />
==Examples==<br />
<br />
A stream containing the values 1, 2, 3:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define first (cons-stream 1 (cons-stream 2 (cons-stream 3 the-empty-stream))))<br />
</syntaxhighlight><br />
<br />
An infinite stream of 1's and 2's:<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define ones (cons-stream 1 ones))<br />
(define twos (cons-stream 2 twos))<br />
</syntaxhighlight><br />
<br />
An infinite stream of natural numbers (1, 2, 3, ...):<br />
<br />
<syntaxhighlight lang='scheme'><br />
(define (make-nats n)<br />
(cons-stream n (make-nats (+ n 1))))<br />
<br />
(define nats (make-nats 1))<br />
</syntaxhighlight></div>Stevenchenghttps://www.ocf.berkeley.edu/~shidi/cs61a/wiki/StreamStream2014-08-08T23:33:10Z<p>Stevencheng: Created page with "==Streams== A '''stream''' is basically a sequence, that introduces the technique of ''delayed evaluation''. Similar to a linked list, a stream's nodes are also streams th..."</p>
<hr />
<div>==Streams==<br />
A '''stream''' is basically a sequence, that introduces the technique of ''delayed evaluation''. Similar to a [[linked list]], a stream's nodes are also streams themselves. Unlike a linked list, which must have its entire representation in memory and written explicitly, streams have values that are computed on demand. The first element of a stream can be anything; however, the second element is a zero-argument function that returns a Stream or Stream.empty.</div>Stevencheng