[plt-scheme] The perfect teaching language--Is this too much to ask for?

SORRY!

I should have made it clear that the CFG parser thread and this thread
were completely unrelated. The CFG parser is an idea for a single
assignment or a short set of assignments for my class next year and
I'm trying to implement that in Typed Scheme.

This thread is about my frustration that HtDP's current languages
aren't perfect. I teach about 80 high school students each year using
HtDP and then continue with about 45 more using HtDC. I'm one of the
curriculum's biggest cheerleaders, so any criticism comes from a place
of love. :-)

As to the parser, I'm implementing a Tomita parser. It has the
advantage that it handles left-recursion, ambiguity, is fairly fast,
and produces all possible parses of a given input.

I've gotten to the point where I've created the non-deterministic
finite state automaton for a given grammar and now need to convert
that to a DFA. I've put that on a back burner for a bit, because the
most efficient way to implement it is some sort of hash-table, but I
have to be careful that I have a representation of a subset of NFA
states that works as a key and I haven't had time to digest the
hash-table stuff, yet.

Todd

On Sat, Jun 13, 2009 at 8:32 PM, Gary Baumgartner<gfb at cs.toronto.edu> wrote:
> On Sat, Jun 13, 2009 at 05:45:42PM -0400, Todd O'Bryan wrote:
>> I'm starting to get really frustrated, because there are lots of
>> languages that have some of what I want in a beginning language, but
>> nothing that has everything. I'm beginning to worry that I'm going to
>> have to design my own language--worry because I have neither the time
>> nor background to do a good job of it.
>
> Since the implementation takes time and background, it is part of
>  the consideration. Are you thinking of that as minor in comparison
>  to the design, else can you break down your worry a bit more into
>  how much of it is about design, and how much of it is being able to
>  implement the design?
>
>> Here's what I'm looking for and
>> I'm beginning to be afraid that the intersection of this set is empty,
>> not just because no one's thought to do it, but because I'm
>> convoluting language layers in an impossible way.
>
> That's a correct "open-minded" attitude.
>
>> Here are my desiderata for a language to teach introductory
>> programming, through at least data structures:
> [...]
>
> Your description of desiderata contains some detail, and you were
>  probably hoping that, while imprecise, might trigger a pointer to
>  something precise that you haven't heard of. It doesn't for me, nor
>  Shriram.
>
> So, instead of working with your list, let's try a different angle I
>  find useful in such discussions: take a concrete example/proposal,
>  and try to evaluate its suitability. If some of the people involved
>  are only responding to a request to satisfy the others' criteria,
>  the others try also to fix the example / propose a different one.
>
> To start, can you respond to my example of a parser language.
>  More simply, just (the example of) specifying one in it:
>
>  (cfg <start>
>    (<start> (<digit> <digit> <start>)
>             ('e))
>    (<digit> ("0") ("1")))
>
> How suitable is this? E.g., since you are now talking about 'types',
>  would it be important that the resulting value be easily introspectable
>  as a "CFG", and with what syntax? Of course since you were interested
>  in parsing as an example of computation, how suitable is this syntax,
>  and the resulting parser behaviour, for that? In particular, how would
>  you want to express the above grammar and use the resulting parser?
>
>> easily grokked syntax, a REPL, good
>> libraries that let students explore stuff if they want to, etc
>
> We're all, present company, I believe working on that, as you suspected,
>  (i.e. it's not that we haven't thought of it). And, if I can presume
>  to speak collectively but not as someone who can take credit for PLT,
>  succeeding and proceeding much more than the average.
>
> By the way, in case you are arguing for a certain unknown syntax,
>  sexpressions have solved the syntax problem, to the extent that
>  one wants an easily grokked syntax for *all* programming (i.e.
>  algorithms, i.e. constructive mathematic). PLT has testimonials
>  covering essentially all backgrounds, the theoretical complexity
>  is provably low, and only people used to other universal notations
>  who haven't spent the same amount of time with sexps, or people
>  used to specific notations for *very* specific domains and a
>  vanishingly (over time!) small number of programming applications,
>  disagree. For more evidence, consider that for general 'data'
>  definition alone, XML is the main competing proposal.
>
> Of course good sub-syntax, if I can call it that, as e.g. Scheme
>  macros specify, is specific to each domain, and talking about its
>  absolute grokkability independent of its semantics is pointless.
>  'Solving' it is as impossible/meaningless as making all meaning
>  easily grokkable. In particular it would require unifying all
>  special notations people consider natural in all specialized domains,
>  and one would have to wonder why different human languages didn't
>  converge to it. Before machines, no one was asking/searching for
>  some 'easily grokkable syntax' for all constructive mathematics /
>  non-fiction.
>
> No one outside (naive) programming language design would consider that
>  anything but absurd. And even they don't go that far, instead making
>  an implementable claim that, sinces it's impossible to solve,
>  "every line should be easily readable / understandable" out of context,
>  by restricting it to certain primitives that appear syntactically in
>  the line (i.e. aren't abstracted by macros, though for some reason
>  classes, call-by-value functions, etc, are okay, with the exact mix
>  depending on a designer's prejudice, for a particular calendar year).
>
> But that's as absurd as saying that essays, specifications, etc,
>  should be written in grade school language, with the ability to make
>  definitions restricted in certain arbitrary ways (e.g. no "until",
>  verbs and only certain kinds of nouns) and then philosophy essays
>  would be easy to write, and children could read and understand them.
>  The mistake is an exercise for the reader (though (almost?) no
>  readers of this list), since at this point every one I've asked
>  knows it *is* a mistake there, and then translating the mistake
>  back to programming completes the exercise.
>
> To close, let me double-check that you aren't expecting the language
>  to do anything for you that it can't: no language will let students
>  understand a parsing program for cfgs without understanding what a
>  cfg is. It is *very* common, for students adapting to new syntax,
>  to claim they "know how to program it", but just not the syntax.
>  Experienced instructors know that this student inrospection is almost
>  always false, and that once the algorithm is truly understood, with
>  precision (to the level of mathematics / theory of CS), the student
>  has no problem with the syntax (I've had countless examples of this,
>  using diagrams, memory models, instructions for another human who
>  doesn't know the purpose of the instructions, etc, and then when
>  understood having the student exclaim "Oh!, then it's just [...]
>  in [language X]."
>
> I hope the length and content wasn't condescending, but the industry
>  is so muddled on this point that the following comic is ineresting
>  and/or funny to many:
>
>  http://www.xkcd.com/568/
>