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]
{