Problem from Computer Science Logo Style
wooks
I'm a mature student and have just completed my 1st year of a computer
science degree.
I've not been happy with the mathematical and algorithmic grounding I
have received so far. The main math course is subcontracted to the math
department and was taught by a well intentioned pure mathematician who
unfortunately had no interest in computer science whatsoever (I gave up
on the lectures in the end). The algorithms course emphasised breadth
rather than depth (which may be right for a 1st year course) but does
not suit the way I like to accrete knowledge.
To remedy this I have decided to tackle a number of texts that use
programming as a vehichle to impart these principles - starting with
Brians Logo texts. I have my eye on a few others in particular
http://www.dcs.gla.ac.uk/~jtod/discrete-mathematics/
These will also serve to remedy the imbalance of our introductory
programming curriculum which is 15 weeks of Java and 5 weeks of Prolog.
The recursive stuff is becoming easy with all the practice I've had
with my various assaults on Scheme, Higher Order Functions are not a
habit (and cannot easily be inculcated into the everyday Java code I
have to write for the programming courses).
Anyway coming to chapter 5 after much scratching of head I resisted the
temptation to skip cascade because I could not grok it and
persevered.....much much later I came up with this
to choose.nodup :string :len
output cascade :len [word ?1 (first (rotate ?2))] "
[bf ?2] :string
end
which is supposed to choose a substring of length len from the string
string
having managed to devise
to rotate "string
output cascade random count :string [word bf ? first ?] :string
end
all by myself.
The choose.nodup does not work - in fact it doesn't even get past the
interpreter.
I have seen a post (by Brian) which does have a working choose.nodup
that implements cascade, but it will better aid my understanding to
figure out what is wrong with my own code as I am still grasping at
the concept of cascade.
Brian Harvey
>to choose.nodup :string :len
>output cascade :len [word ?1 (first (rotate ?2))] "
> [bf ?2] :string
>end
The first problem here is intellectually trivial but a deal-killer: you need
a continuation character at the end of the OUTPUT line:
to choose.nodup :string :len
output cascade :len [word ?1 (first (rotate ?2))] " ~
[bf ?2] :string
end
If you don't like continuation characters you could enclose the entire
CASCADE expression in parentheses.
Once you get past that, you'll see that the character you remove from ?2
each time is not the same as the character you add to ?1.
wooks
Brian Harvey wrote:
> "wooks" <woo...@hotmail.com> writes:
> >to choose.nodup :string :len
> >output cascade :len [word ?1 (first (rotate ?2))] "
> > [bf ?2] :string
> >end
>
> The first problem here is intellectually trivial but a deal-killer: you need
> a continuation character at the end of the OUTPUT line:
>
> to choose.nodup :string :len
> output cascade :len [word ?1 (first (rotate ?2))] " ~
> [bf ?2] :string
> end
>
I tried this (after your suggestion). It had no effect. Kept getting
the same error as before - which was.
? doesn't like 2 as input in cascade.eval
[op fput (apply first :cascade.templates :template.vars) (cascade.eval
bf :cascade
.templates)]
> If you don't like continuation characters you could enclose the entire
> CASCADE expression in parentheses.
>
ahah .... now we're cooking
>
> Once you get past that, you'll see that the character you remove from ?2
> each time is not the same as the character you add to ?1.
time for more head scratching.
wooks
Ok solved that problem and now I have another one.
Trying to write anymatch using HOFS.
Following your design recipe I created
to howmany :letter :word
output count filter [equalp first ? :letter] :word
end
Now I figured
print (map "howmany "abcde "deterministic)
would give me a count of the occurrence of each letter of the first
string in the second and would love to know why not.
Andreas Micheler
You nearly got it.
It's just that you must separate the :word from the letter list,
because HOWMANY must get the whole :word every time.
This works in aUCBLogo-4.7:
to howmany :letter :word
output count filter [equalp first ? :letter] :word
end
print (map [howmany ? "deterministic] "abcde)
00112
Cheers,
Andreas
Brian Harvey
>to howmany :letter :word
>output count filter [equalp first ? :letter] :word
>end
Although this happens to work (because FIRST of a one-letter word is the
same word), this isn't really right. It should be [equalp ? :letter].
FILTER invokes the template (the first argument) *for each letter* of the
word (the second argument). So ? is not the same as :WORD, but is a single
letter of :WORD. (The template is invoked as many times as there are letters
in the word.)
>print (map "howmany "abcde "deterministic)
This is syntactically correct because HOWMANY is a two-input function and
you're giving MAP two inputs in addition to the function itself. But what
it does is compute the following:
howmany "a "d
howmany "b "e
howmany "c "t
howmany "d "e
howmany "e "r
and puts the results in a word. (Technically it's an error for the two
input words to have different numbers of letters, but MAP doesn't check;
it stops when the first one runs out. You'd have gotten in trouble if
the first had been longer than the second.)
wooks
Thank you (Andreas and Michael) for keeping me on course.
Now I have written exactmatch
to exactmatch :word1 :word2
output reduce "sum (map [ifelse equalp ?1 ?2 [1] [0]] :word1 :word2)
end
and it seems to work since
print exactmatch "hurry "harry
yields an answer of 4.
Bearing in mind the following example from the book
<quote>
Anonymous functions of more than one argument are a little uglier.
Instead of ? for the argument, you must use ?1 for the first, ?2 for
the second, and so on.
to biggest :nums
output reduce [ifelse ?1 > ?2 [?1] [?2]] :nums
end
</quote>
how did logo know that ?2 was meant to be the next letter from the 2nd
parameter rather than the 2nd next letter from the 1st parameter.
In other words in
print exactmatch "hurry "harry
why is ?2 is the h from the 'harry rather than the u from hurry.
Brian Harvey
>to exactmatch :word1 :word2
>output reduce "sum (map [ifelse equalp ?1 ?2 [1] [0]] :word1 :word2)
>end
>
>parameter rather than the 2nd next letter from the 1st parameter.
It's easier to understand things like this if, instead of "how did *Logo*
know," you ask yourself questions about specific procedures, e.g., "how did
*map* know" or "how did *equalp* know" etc.
In this case, the important point is that neither MAP nor EQUALP knows
anything about the ?1/?2 notation. As the text you quoted says, the relevant
function is the *anonymous function* (i.e., it has no name) shown as
[ifelse equalp ?1 ?2 [1] [0]]
To that function, ?1 means "my first input" and ?2 means "my second input."
How is that function called? As we've already discussed, this anonymous
function is called repeatedly by MAP, which, in effect, does
anonymous.function "h "h
anonymous.function "u "a
anonymous.function "r "r
anonymous.function "r "r
anonymous.function "y "y
MAP doesn't care whether its first input is a named function or an
anonymous function. Its job is to call the function repeatedly using the
individual letters of the two words as inputs. It would do that regardless
of what function you use as the first input.
The anonymous function's job is to check whether its two inputs are equal,
and output 1 or 0 accordingly. It has no idea where its inputs come from,
or who called it, or why it was called; it only knows what its job is and
what inputs it was given.
So, when the anonymous function is running, it has no access to the words
HURRY and HARRY. Those aren't the inputs with which it's called.
P.S. Why did I say EQUALP is irrelevant to the question? Aren't ?1 and ?2
used as inputs to EQUALP?
Yes, but it is the *values* associated with ?1 and ?2 that EQUALP sees. Just
as when you say
print 2+3
all PRINT sees is the value 5, not the expression 2+3; similarly, all EQUALP
sees is the letter H and the letter H, or the letter U and the letter A, etc.
It's the anonymous function that has to provide those input values to EQUALP.
P.P.S. A technical detail: You can't just put an anonymous function anywhere
in a Logo expression. You can't, for example, say
print [if equalp ?1 ?2 [1] [0]] "h "h ; wrong!
The way higher order functions like MAP and FILTER can use anonymous functions
is that they call them by way of a Logo primitive called APPLY that takes two
inputs: (1) either the name of a named function or the template representing
an anonymous function; and (2) a list of input values to that function. So
you could say
print apply [if equalp ?1 ?2 [1] [0]] [h h]
and this instruction would print 1.
This limitation on the use of anonymous functions is the main thing that
distinguishes Logo from its cousin Scheme, which people have mentioned in
this newsgroup, in which anonymous functions are used in exactly the same
way as named functions. (But there are other important differences, too.)
wooks
Some questions on UCBLogo
1. I am trying to po a procedure I wrote in the current session but
have forgotten the name of it. What can I do.
2. How can I scroll my session screen so that I can see what I did
before (which would solve the problem in 1).
3. How do I repeat a command - is there some sort of history functions
a la Unix?
Brian Harvey
>1. I am trying to po a procedure I wrote in the current session but
>have forgotten the name of it. What can I do.
POTS (print out titles) will list the title lines of all unburied defined
procedures in the workspace.
>2. How can I scroll my session screen so that I can see what I did
>before (which would solve the problem in 1).
>
>3. How do I repeat a command - is there some sort of history functions
>a la Unix?
Sorry, you have to wait for the next release -- there is a WXwidgets-based
UCBLogo GUI almost ready for beta release, but I'm swamped with other work
right now, so probably not until fall.
wooks
Ok I want to write a procedure using HOFs that filters out the second
of 2 consecutive non numeric elements of a list. Hence
[7 a b 9 d e f 88 g h] should give [7 a 9 d 88 g].
I would have started with something like
to compress :alist
output filter [ and wordp ?1 wordp ?2] :alist
end
but that isn't happening and even if it was I guess it would filter out
?1 whereas I want it to filter out ?2. It's almost like I want to be
able to say
Can I have a pointer to a HOF solution or is this something that needs
recursion (in which case I can easily write it).
Brian Harvey
>recursion (in which case I can easily write it).
I'd do it recursively. ("?2" doesn't mean "the second element of this list";
it means "the first element of the second list." And in this problem you
only have one list.) If you really want to, you can do it with CASCADE or
with TRANSFER:
? show transfer [] [ifelse (or [numberp ?in]
[lessp (count ?out) 2]
[not numberp last butlast ?out])
[lput ?in ?out]
[?out]] ~
[7 a b 9 d e f 88 g h]
[7 a 9 d 88 g]
... but I wouldn't call this perspicuous code. The recursive version would be
much clearer, and more efficient, too, because you'd build up the list with
fput instead of lput, and because you'd only check for something being a
number once instead of repeatedly.
wooks
Brian Harvey wrote:
> "wooks" <woo...@hotmail.com> writes:
> >[7 a b 9 d e f 88 g h] should give [7 a 9 d 88 g].
> >
> >Can I have a pointer to a HOF solution or is this something that needs
> >recursion (in which case I can easily write it).
>
> I'd do it recursively. ("?2" doesn't mean "the second element of this list";
> it means "the first element of the second list." And in this problem you
> only have one list.)
>
So how come
to biggest :nums
output reduce [ifelse ?1 > ?2 [?1] [?2]] :nums
end
from the book works. Is it specific to reduce?
Brian Harvey
>So how come
>
>to biggest :nums
>output reduce [ifelse ?1 > ?2 [?1] [?2]] :nums
>end
>
>from the book works. Is it specific to reduce?
Yes. Each of the higher order functions uses its function-input in a
specific way. For MAP and FILTER, the argument is a one-input function;
for REDUCE, it has to be a two-input function, and ?1 and ?2 are the
two inputs. (MAP will accept extra list inputs, in which case the function
input takes as many inputs as there are lists.)
to map :function [:lists] 2
... apply :function (firsts :lists) ...
end
to filter :predicate :list
... apply :predicate (list first :list) ...
end
to reduce :function :list
... apply :function (list (first :list) (reduce :function bf :list)) ...
end
(This isn't the actual code, just a simplified version to make the point
that each of them calls APPLY differently.)
Remember that ?1 and so on aren't handled directly by MAP or whatever, but
by APPLY, in which it has a uniform meaning: you give APPLY a function and
a list of values, and ?n means the nth value in the list.
P.S. Even in REDUCE, ?2 doesn't mean the second element of the list, but
rather the result of REDUCEing the entire butfirst of the list.
wooks
I am trying to do the phone number word permutation problem in chap 11.
I have written
? po "prepend
to prepend :letter :list1
output (map.se [word :letter ? ] :list1 )
end
and
? po "mapPrepend
to mapPrepend :list1 :list2
output if emptyp :list2 [map.se "first :list2]
output (map.se [prepend ? :list2] :list1)
end
such that
print mapPrepend "abc mapPrepend "def "ghi
yields as it should
adg adh adi aeg aeh aei afg afh afi bdg bdh bdi beg beh bei bfg bfh bfi
cdg cdh cdi c
eg ceh cei cfg cfh cfi
I also have
to phoneword :num
local "translate
make "translate [1 abc def ghi jkl mno pqr stu vwx]
output map.se [item ? :translate] :num
end
which is fairly straightforward.
The coup de grace should be delivered by
? po "phonename
to phoneName :num
output if lessp count :num 2 [phoneword :num]
output mapPrepend (first phoneword :num) (phoneName bf :num)
end
but it doesn't work.
My guess is that the basecase is wrong but fiddling around with it
hasn't helped.
I'm also suspecting that the fact mapPrepend doesn't handle an empty
list as its 2nd input correctly may have something to do with it but
the fix I tried for that (which is still in the code) didn't yield
anything either.
Brian Harvey
>? po "phonename
>to phoneName :num
>output if lessp count :num 2 [phoneword :num]
>output mapPrepend (first phoneword :num) (phoneName bf :num)
>end
Do you ever use the butfirst of PHONEWORD :NUM?