The algorithm shown here is explained in [3]. The example illustrates the way in which NESL functions can be developed ``from the inside out'', using the interactive system to test each new addition.

<Nesl> teststr = "string strap asop string"; teststr = "string strap asop string" : [char] <Nesl> candidates = [0:#teststr-5]; candidates = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24] : [int] <Nesl> {a == `s: a in teststr -> candidates}; it = [T, F, F, F, F, F, F, T, F, F, F, F, F, T, F, F, F, F, F, F, T, F, F, F, T] : [bool] <Nesl> candidates = {c in candidates; > a in teststr -> candidates | a == `s}; candidates = [0, 7, 13, 20, 24] : [int] <Nesl> candidates = {c in candidates; > a in teststr -> {candidates+1:candidates} | a == `t}; candidates = [0, 13, 24] : [int] <Nesl> candidates = {c in candidates; > a in teststr -> {candidates+2:candidates} > | a == `r}; candidates = [0, 13, 24] : [int] <Nesl> candidates = {c in candidates; > a in teststr -> {candidates+3:candidates} > | a == `i}; candidates = [0, 24] : [int] <Nesl> candidates = {c in candidates; > a in teststr -> {candidates+4:candidates} > | a == `n}; candidates = [0, 24] : [int] <Nesl> function next_cands(cands, w, s, i) = > if (i == #w) then cands > else > let letter = w[i]; > next_chars = s -> {cands + i: cands}; > new_cands = {c in cands; l in next_chars | l == letter} > in next_cands(new_cands, w, s, i + 1); next_cands = fn : ([int], [a], [a], int) -> [int] :: (a in ordinal) <Nesl> > function string_search(w, s) = > next_cands([0:#s - (#w - 1)], w, s, 0); string_search = fn : ([a], [a]) -> [int] :: (a in ordinal) <Nesl> longstr = > "This course will be a hands on class on programming parallel algorithms. It will introduce several parallel data structures and a variety of parallel algorithms, and then look at how they can be programmed. The class will stress the clean and concise expression of parallel algorithms and will present the opportunity to program non-trivial parallel algorithms and run them on a few different parallel machines. The course should be appropriate for graduate students in all areas and for advanced undergraduates. The prerequisite is an algorithms class. Undergraduates also require permission of the instructor."; longstr = "This course will be a hands on class on programming parallel algorithms. It will introduce several parallel data structures and a variety of parallel algorithms, and then look at how they can be programmed. The class will stress the clean and concise expression of parallel algorithms and will present the opportunity to program non-trivial parallel algorithms and run them on a few different parallel machines. The course should be appropriate for graduate students in all areas and for advanced undergraduates. The prerequisite is an algorithms class. Undergraduates also require permission of the instructor." : [char] <Nesl> string_search("will", longstr); it = [12, 77, 219, 291] : [int] <Nesl> string_search("student", longstr); it = [461] : [int]

{

Tue Nov 28 18:37:09 EST 1995