Achievement Unlocked – A Better Path to Language Learning – Mal Beginnings

View Github Repository Open presentation in a new window

kanaka

See all presentation from kanaka

Achievement Unlocked – A Better Path to Language Learning – Mal Beginnings

0 1

midwest.io.mal

midwest.io 2015 "Achievement Unlocked"

On Github kanaka / midwest.io.mal

Achievement Unlocked

A Better Path to Language Learning

Midwest.io 2015

Joel Martin

Press 's' to show speaker notes

  • Silence phone
  • Have sized window for mal demo open
  • Prune foo from Makefile and foo/
  • Build impls: bash, python, js, mal
  • Setup screen sharing
  • Preload guide
  • Preload step0 image, step1 image, step2 image in presentation window for quick tabbing.

About Me

Joel Martin (kanaka)

github.com/kanaka

@bus_kanaka

Principal Software Engineer at ViaSat, Inc

Clojure

Satellites!

  • My name is Joel Martin
  • Principal Software Engineer at ViaSat, Inc
  • At ViaSat I get to build systems using >> Clojure, work with some amazing people, and >> work at a company that does broadband Internet from space.
  • Thanks to midwest.io organizers for a great conference so far!

Welcome to Polyglossia

  • Groovy (2003)
  • Scala (2004)
  • Go (2009)
  • Swift (2014)
  • Clojure (2007)
  • Rust (2010)
  • Julia (2012)
  • Dart (2013)
  • Factor (2003)
  • Nim (2008)
  • Kotlin (2011)
  • Crystal (2012)

The Best Languages for the   Organization Task/Project System

It's a Polyglot World

Language learning is part of the job.

  • Show of hands: how many of you have written non-trivial code in more than one programming language over the past:
    • - year?, - month?, - week?, - today?
  • The rate of language creation isn't slowing down.
  • >> I suspect almost everybody here has heard of these
  • >> There is a good chance you've heard of these.
  • >> But you not have heard of these. But in fact these are all really interesting languages and you should look them up (after this talk of course).
  • As an industry we've moved from a >> standard language per company/organization, >> to best language for the task, >> to best langauges for the system.
  • >> It's a PolyGlot World. >> Regularly learning new languages is just part of what it means to be a software developer.

Learning is work!

Work is inherently difficult

The typical process:

  • Hello world
  • Function definition and calling
  • Basic data types
  • Basic flow control constructs
  • Etc, etc, ad naseum
  • Most popular languages have a wealth of learning resources. Many even have step-by-step incremental tutorials to help you learn the language.
  • >> But regardless, the process usually involves >> >> >> >>
  • Some of the best learning resources are like reading quirky books (e.g. "Learn you a Haskell for Great Good" and "Why's Poignant Guide to Ruby"), but they are still just basically humorous narrative forms of the same process.
  • And so language learning requires you to tediously push your brain up hill a couple of inches at a time until you reach a high enough foothill where you can implement your first real thing in the language.
  • It's hard work. >>

... or is it?

“Why will people pay for the privilege of working harder than they will work when they are paid? -- The Game of Work: Charles Coonradt”

"Work" is not a thing, it's a state of mind.

>>

A quote from Charles Coonradt

Meat packers might act like they have the job from hell, but then those same people might gladly pay to go hunting in the dead of winter.

The fact is >> "Work" is not a thing.

The Inspiration

  • Gherkin
  • lispy
  • I'm going to tell you a personal story about language learning.
    • >> Way back in 2013, Alan Dipert presented this at Clojure/conj
    • A Lisp implemented in bash >> [mindblown]
    • This was basically my reaction.
    • Raised the question for me: what other non-traditional language could a Lisp be implemented in?
    • Had particular language in mind. As far as I knew, no one had ever written a Lisp using it. You'll see why in a moment.
  • >> Lispy: a small and simple Python implementation of a Lisp interpreter by Peter Norvig. I used that as a model.

Mal Beginnings

A bit on how mal began vv

JS

...
function read_form(reader) {
    var token = reader.peek();
    switch (token) {
    // reader macros/transforms
    case ';': return null; // Ignore comments
    case '\'': reader.next();
               return [types._symbol('quote'), read_form(reader)];
    case '`': reader.next();
              return [types._symbol('quasiquote'), read_form(reader)];
    case '~': reader.next();
              return [types._symbol('unquote'), read_form(reader)];
...
First did an implementation in JS to make sure I understood the process well. I had not made a Lisp from scratch before.

GNU Make

...
define READ_FORM
$(and $(READER_DEBUG),$(info READ_FORM: $($(1))))
$(call READ_SPACES,$(1))
$(foreach ch,$(word 1,$($(1))),\
  $(if $(filter $(SEMI),$(ch)),\
    $(call DROP_UNTIL,$(1),$(_NL)),\
  $(if $(filter $(SQUOTE),$(ch)),\
    $(eval $(1) := $(wordlist 2,$(words $($(1))),$($(1))))\
    $(call _list,$(call _symbol,quote) $(strip $(call READ_FORM,$(1)))),\
  $(if $(filter $(QQUOTE),$(ch)),\
    $(eval $(1) := $(wordlist 2,$(words $($(1))),$($(1))))\
    $(call _list,$(call _symbol,quasiquote) $(strip $(call READ_FORM,$(1)))),\
  $(if $(filter $(UNQUOTE),$(ch)),\
...

"Make Lisp"

  • Here is a sample of the code from the target language that I was inspired to write a Lisp in. Anybody willing to guess what language this example code is written in?
  • >> GNU Make. And yes, it's really does work and it's a full implementation.
  • SWITCH
  • Demo 
    cd make
make -f ./mal.mk
user> ( (fn* [a b] (* a b)) 7 8)
less mal.mk
  • SWITCH >> The name "Mal" original "MAke Lisp" because that was all I was really originally intenteding to do. But then I had the thought...
  • Should be at 10 min mark

Bash

...
READ_FORM () {
  local token=${__reader_tokens[${__reader_idx}]}
  case "${token}" in
    \')   __reader_idx=$(( __reader_idx + 1 ))
          _symbol quote; local q="${r}"
          READ_FORM; local f="${r}"
          _list "${q}" "${f}" ;;
    \`)   __reader_idx=$(( __reader_idx + 1 ))
          _symbol quasiquote; local q="${r}"
          READ_FORM; local f="${r}"
          _list "${q}" "${f}" ;;
...
  • My JS and Make Lisp interpreters had a fairly different structure compared to Gherkin. So I decided to try my hand at Bash.
  • Began to see patterns. Started thinking in terms of small digestable chunks, largely due to the fact my life, job and school meant I only had short segments of time to work on it.
  • Often it was at night while working on graduate classes when I would take a 5-10 minute break and work on whatever current mal implementation I happened to have in the pipeline. And I'm not that brilliant so I was forced to make a process that was very gradual and incremental.

C

...
MalVal *read_form(Reader *reader) {
    char *token;
    MalVal *form = NULL, *tmp;
    token = reader_peek(reader);
    if (!token) { return NULL; }
    switch (token[0]) {
    case ';':
        abort("comments not yet implemented");
        break;
    case '\'':
        reader_next(reader);
        form = _listX(2, malval_new_symbol("quote"),
                         read_form(reader));
        break;
...
  • First statically typed language. Led to restructuring of the earlier 3 implementations. More patterns became apparent.

Python

...
def read_form(reader):
    token = reader.peek()
    # reader macros/transforms
    if token[0] == ';':
        reader.next()
        return None
    elif token == '\'':
        reader.next()
        return _list(_symbol('quote'), read_form(reader))
    elif token == '`':
        reader.next()
        return _list(_symbol('quasiquote'), read_form(reader))
...
  • Mal had become a fairly different Lisp from Lispy by this point. It modelled it on Clojure's syntax and immutability because that was the Lisp I knew and loved. But since Python was loosely part of the heritage I decided I had to do python too.

Clojure

...
;; Override some tools.reader reader macros so that we can do our own
;; metadata and quasiquote handling
(alter-var-root #'r/macros
  (fn [f]
    (fn [ch]
      (case ch
        \` (wrap 'quasiquote)
        \~ (fn [rdr comma]
             (if-let [ch (rt/peek-char rdr)]
               (if (identical? \@ ch)
                 ((wrap 'splice-unquote) (doto rdr rt/read-char) \@)
                 ((wrap 'unquote) rdr \~))))
...
  • And of course, since Mal is a Clojure-like Lisp, I had to do in implementation in Clojure.
  • This was really enlightening in terms of what parts of Mal were really Lisp nature, and which parts were really just incidental complexity due to nature or dificiencies of the target language. And I began to strongly structure the code and the incremental steps to reflect that.
  • However, I should point out that I later realized that the "incidental complexity" is actually one of the most useful aspects of mal, but we'll get to that.

PHP

...
function read_form($reader) {
    $token = $reader->peek();
    switch ($token) {
    case '\'': $reader->next();
               return _list(_symbol('quote'),
                               read_form($reader));
    case '`':  $reader->next();
               return _list(_symbol('quasiquote'),
                               read_form($reader));
    case '~':  $reader->next();
               return _list(_symbol('unquote'),
                               read_form($reader));
...

Java

...
    public static MalVal read_form(Reader rdr)
            throws MalContinue, ParseError {
        String token = rdr.peek();
        if (token == null) { throw new MalContinue(); }
        MalVal form;

        switch (token.charAt(0)) {
            case '\'': rdr.next();
                       return new MalList(new MalSymbol("quote"),
                                          read_form(rdr));
            case '`': rdr.next();
                      return new MalList(new MalSymbol("quasiquote"),
                                         read_form(rdr));
...

An Accidental Discovery

"Make Lisp" became "Make-A-Lisp"

  • At some point I began to realize that Mal had become a very useful personal learning tool. I was able to learn new languages more quickly and to a greater depth than any other process I had used before.
  • >> And so Make Lisp became Make-A-Lisp
  • But before we switch gears and focus on the language learning aspects of the make-a-lisp process, let's take brief look at mal the language along with a couple of implementations.

Mal Itself

Demo Time

  • Should be at 15 min mark
  • SWITCH
  • Let's start with a hello world mal program: 
    cd ../python
cat ../mal/hello.py
  • but let's run it with the python implementation: 
    ./mal.py ../mal/hello.py
  • Let's try something a bit more interesting but this time using the bash implementation: 
    cd ../bash
./mal.sh ../mal/clojurewest2014.mal
  • That's a presentation for a lightning talke I did on mal at Clojure West. 
    less ../mal/clojurewest2014.mal
  • That's all well and good, but let's bump it up a notch or three: 
    cd ../js
./mal.js ../mal/mal.mal
  • I'll just pause for a second to let you stew on that.
  • Yes, that's the mal implementation of mal
  • SWITCH[show gif]
  • This was basically my reaction at the moment when mal became self-hosting.
  • SWITCH 
    less ../mal/mal.mal
  • More specifically, that's the JavaScript implementation of mal being used to run an implementation of mal that is written in the mal language itself
  • Self-hosting is the term for an interpreter or compiler that is written in it's own language.

Mal and More Mal

PostScript

...
% read_form: read the next form from string start at idx
/read_form { 3 dict begin
    read_spaces
    /idx exch def
    /str exch def

    idx str length ge { null str idx }{ %if EOF

    /ch str idx get def  % current character
    ch 39 eq { %if '\''
        /idx idx 1 add def
        str idx read_form
        3 -1 roll   /quote exch 2 _list   3 1 roll
...

Yes, Postscript the typesetting language.

After my lightning talk at Clojure West somebody suggested Postscript and so I took up the challenge.

I had never written a line of code in a stack-based/concatenative language like Postscript

More challenging than most, not as difficult as GNU Make

C#

...
        public static MalVal read_form(Reader rdr) {
            string token = rdr.peek();
            if (token == null) { throw new MalContinue(); }
            MalVal form = null;

            switch (token) {
                case "'": rdr.next();
                    return new MalList(new MalSymbol("quote"),
                                       read_form(rdr));
                case "`": rdr.next();
                    return new MalList(new MalSymbol("quasiquote"),
                                       read_form(rdr));
...

Ruby

...
def read_form(rdr)
    return case rdr.peek
        when ";" then  nil
        when "'" then  rdr.next; List.new [:quote, read_form(rdr)]
        when "`" then  rdr.next; List.new [:quasiquote, read_form(rdr)]
        when "~" then  rdr.next; List.new [:unquote, read_form(rdr)]
        when "~@" then rdr.next; List.new [:"splice-unquote", read_form(rdr)]
        when "^" then  rdr.next; meta = read_form(rdr);
                       List.new [:"with-meta", read_form(rdr), meta]
...

Perl

...
sub read_form {
    my($rdr) = @_;
    my $token = $rdr->peek();
    given ($token) {
        when("'") { $rdr->next(); List->new([Symbol->new('quote'),
                                             read_form($rdr)]) }
        when('`') { $rdr->next(); List->new([Symbol->new('quasiquote'),
                                             read_form($rdr)]) }
        when('~') { $rdr->next(); List->new([Symbol->new('unquote'),
                                             read_form($rdr)]) }
...

Go

...
func read_form(rdr Reader) (MalType, error) {
        token := rdr.peek()
        if token == nil {
                return nil, errors.New("read_form underflow")
        }
        switch *token {
        case `'`:
                rdr.next()
                form, e := read_form(rdr)
                if e != nil {
                        return nil, e
                }
                return List{[]MalType{Symbol{"quote"}, form}, nil}, nil
...

Rust

...
fn read_form(rdr : &mut Reader) -> MalRet {
    let otoken = rdr.peek();
    let stoken = otoken.unwrap();
    let token = &stoken[..];
    match token {
        "'" => {
            let _ = rdr.next();
            match read_form(rdr) {
                Ok(f) => Ok(list(vec![symbol("quote"), f])),
                Err(e) => Err(e),
            }
        },
...

More challenging then average, but it's a very interesting language

R

...
read_form <- function(rdr) {
    token <- Reader.peek(rdr)
    if (token == "'") {
        . <- Reader.next(rdr);
        new.list(new.symbol("quote"), read_form(rdr))
    } else if (token == "`") {
        . <- Reader.next(rdr);
        new.list(new.symbol("quasiquote"), read_form(rdr))
    } else if (token == "~") {
        . <- Reader.next(rdr);
        new.list(new.symbol("unquote"), read_form(rdr))
...

CoffeeScript

...
read_form = (rdr) ->
  token = rdr.peek()
  switch token
    when '\'' then [_symbol('quote'), read_form(rdr.skip())]
    when '`'  then [_symbol('quasiquote'), read_form(rdr.skip())]
    when '~'  then [_symbol('unquote'), read_form(rdr.skip())]
    when '~@' then [_symbol('splice-unquote'), read_form(rdr.skip())]
    when '^'
      meta = read_form(rdr.skip())
      [_symbol('with-meta'), read_form(rdr), meta]
    when '@' then [_symbol('deref'), read_form(rdr.skip())]
...

VB.NET

...
        Shared Function read_form(rdr As Reader) As MalVal
            Dim token As String = rdr.peek()
            If token Is Nothing Then
                throw New MalContinue()
            End If
            Dim form As MalVal = Nothing

            Select token
            Case "'"
                rdr.get_next()
                return New MalList(New MalSymbol("quote"),
                                   read_form(rdr))
...

Scala

...
  def read_form(rdr: Reader): Any = {
    return rdr.peek() match {
      case "'"  => { rdr.next; _list(Symbol("quote"), read_form(rdr)) }
      case "`"  => { rdr.next; _list(Symbol("quasiquote"), read_form(rdr)) }
      case "~"  => { rdr.next; _list(Symbol("unquote"), read_form(rdr)) }
      case "~@" => { rdr.next; _list(Symbol("splice-unquote"), read_form(rdr)) }
      case "^"  => { rdr.next; val meta = read_form(rdr);
                     _list(Symbol("with-meta"), read_form(rdr), meta) }
      case "@"  => { rdr.next; _list(Symbol("deref"), read_form(rdr)) }
...

Haskell

...
read_form :: Parser MalVal
read_form =  do
    ignored
    x <- read_macro
     <|> read_list
     <|> read_vector
     <|> read_hash_map
     <|> read_atom
    return $ x

read_str :: String -> IOThrows MalVal
read_str str = case parse read_form "Mal" str of
...

Racket

...
(define (read_form rdr)
  (let ([token (send rdr peek)])
    (if (null? token)
      (raise (make-blank-exn "blank line" (current-continuation-marks)))
      (cond
        [(equal? "'" token) (send rdr next) (list 'quote (read_form rdr))]
        [(equal? "`" token) (send rdr next) (list 'quasiquote (read_form rdr))]
        [(equal? "~" token) (send rdr next) (list 'unquote (read_form rdr))]
        [(equal? "~@" token) (send rdr next) (list 'splice-unquote (read_form rdr))]
        [(equal? "^" token) (send rdr next)
                            (let ([meta (read_form rdr)])
                              (list 'with-meta (read_form rdr) meta))]
...

Lua

...
function M.read_form(rdr)
    local token = rdr:peek()

    if "'" == token then
        rdr:next()
        return List:new({Symbol:new('quote'), M.read_form(rdr)})
    elseif '`' == token then
        rdr:next()
        return List:new({Symbol:new('quasiquote'), M.read_form(rdr)})
    elseif '~' == token then
        rdr:next()
        return List:new({Symbol:new('unquote'), M.read_form(rdr)})
...

OCaml

...
and read_form all_tokens =
  match all_tokens with
    | [] -> raise End_of_file;
    | token :: tokens ->
      match token with
        | "'"  -> read_quote "quote" tokens
        | "`"  -> read_quote "quasiquote" tokens
        | "~"  -> read_quote "unquote" tokens
        | "~@" -> read_quote "splice-unquote" tokens
        | "@"  -> read_quote "deref" tokens
...
  • OCaml was implementation #23
  • But there was a critical difference about the OCaml implementation: it was created by someone else. chouser (a friend and colleague who also wrote the book "The Joy of Clojure")
  • Marked a new era for mal (Jan 2015). The beginning of a step-by-step guide. Other people have created more implementations that I have since then.
  • Mal and make-a-lisp was no longer just my pet project.
  • Should be at 20 min mark

Mal Today

  • Which bring us to today. >>
  • There are now 42 implementations.
  • 14 of the last 20 were created by others. And of the six I created many were either variations of exisiting implementations (like ES6 and rpython) or to learn a language for one of my PhD classes (like MATLAB) [or experiment with a language idea for work (miniMAL)].
  • The past 12 months have averaged more than 2 implementations per month.
  • At this point you might be asking yourself "Why"? Why did a bunch of people go through the work to do this?
  • The answer is actually really simple: because it was fun! And not just fun, but addictive fun.

Putting the Fun in Language Learning

Buzzword alert: Gamification

Make-A-Lisp is gamification of language learning

  • >> Buzzword alert: >>
  • Gamification as a term has become a bit tired. But the principle it is referring to is really important.
  • The reason that the make-a-lisp process has worked so well (and not just for me) is because it evolved into an addictive game. >>
  • Now let's dive into how we turn work into a game.

Game of Work

Goals Scorekeeping Choice Coaching Feedback
  • These ideas are from Charles Coonradt's book "The Game of Work". Originally writen in 1984.
  • Considered grandfather of gamification -- although term was not coined until later.
  • There's been a lot more written about gamification since then and many other ideas about how to turn work and other hard activities into a game. But certainly, Coonradt's 5 principles do encapsulate some of the most important ideas.
  • So let's talk about what these principle are and how the make-a-lisp process applies those principles.
  • >> Clearly defined and measurable Goals
  • >> Objective and standardized Scorekeeping
  • >> A high degree of Choice
  • >> Consistent Coaching and a well-defined Field of Play
  • >> Frequent Feedback
  • As I mentioned before, I accidentally stumbled on many of these ideas in mal, but since that point I have been tweaking the process to try and maximize it's fun and utility.
  • Also, this process isn't complete. I think there is much more that could be done to make make-a-lisp more fun and effictive.
  • So let's look at how those principles apply to the make-a-lisp process.

Goals

  • Learn a New Language
  • Learn About Lisp
  • ---
  • Create a Lisp (i.e. Mal implementation)
  • Get Eternal Glory (at https://github.com/kanaka/mal)
    • Getting your implementation into the main repository
      • First to implement a new target
      • Something unique and interesting about your implemenation
    • Getting credit for a re-implementation
  • Goals: the desired results.
  • Although the first two are the real goals, they don't satisfy the requirement that goals are objective and measurable
  • But as long as you don't cheat and copy another implementation, once you've created your mal implementation, you will have accomplished the former two.
  • "first" is really a subset of "unique and interesting"
  • "unique and interesting": different way of mapping Mal types to the target language, more efficient immutable data structure implementation, a more idiomatic implementation in target language, etc.
  • if you simply re-implement an existing target, that's still worthy of recognition. Let me know and as long as it's not just a copy of an existing implementation, I'll link to it from the main repository.

Scorekeeping

Measure of progress towards goal

  • step0_repl
  • step1_read_print
  • step2_eval
  • step3_env
  • step4_if_fn_do
  • step5_tco
  • step6_file
  • step7_quote
  • step8_macros
  • step9_try
  • stepA_mal
  • Echo program
  • Syntax checker
  • Simple calculator (prefix)
  • Calculator with memory
  • Simple Lisp Language
  • Efficient stack/memory (Tail-calls)
  • File I/O, eval, command line
  • Code templating (quasiquote)
  • User defined syntax (macros)
  • Exception handling
  • Self-hosting
In the make-a-lisp process, you score 11 points to win the game i.e. achieve the goal.

Choice

Freedom to choose how to succeed

  • Target language and tools
  • Implementation decisions
  • Optional steps/tasks
    • step 5 / TCO
    • readline editing/history
    • metadata across all compound data-types
    • keywords
  • Deferrable (needed for self-hosting):
    • step 5 / TCO
    • vectors and hash-maps
    • reader macros, comments
  • Some things are completely optional like Tail-Call Optimization (step 5) and Clojure-style keywords.
  • Many others things can be deferred to later steps but are needed for full self-hosting.

Coaching

  • Step-by-step guide is the main coaching tool.
  • SHOW PAGES (turn head)
  • >> Psuedo-code that you can diff to see what the difference between steps is.
  • >> FAQ: explains why steps are structured the way they are and what form your implementation needs to take to get accepted into repository.
  • >> #mal: interested in any aspect of mal, please join channel.

Feedback

  • Measuring change over time
  • Frequent feedback
  • In make-a-lisp feedback works like this: 
    make test^MY_IMPL
  • Or: 
    make test^MY_IMPL^stepX
  • [Read through slide]

Game Overview (Turns)

  • For each step:
  • Choose a step task
  • Google, stackoverflow, references, tutorials
  • Implement/tweak until tests pass
  • Repeat until step is done
  • Reminder SLIDES visible?
  • Based on Guide, or Pseudo-code, or test (TDD), pick a feature/functionality of current step
  • Google, stackoverflow
  • Iterate between 2 & 3

Let's Play

  • Round one
  • >> Now I'm going to show you round one of this game.
  • SWITCH
  • Update Makefile with 3 foo changes
  • Stubs for the read/eval/print parts of REPL
  • Lookup up python input on stackoverflow
  • Broken output
  • Show test file
  • Run test
  • Explain test counts and the output format
  • Fix output
  • Show test again
  • SWITCH BACK

Your Turn!

  • Learn a new language using mal
  • Create an new implementation
  • Improve the game
  • Improve an existing implementation
  • Make a cool logo for mal
  • Do some language research with mal implementations
  • Learn a new language using mal
  • Create an new implementation
  • Improve the game (graphical or auditory real-time feedback)
  • Improve an existing implementation: e.g. Haskell
  • If you're more design inclined, a logo for mal.
  • Do some research using existing mal implementations

Questions?

  • >> I'll also put up some reference links while I take questions.

Extra Material

New Implementation Ideas

  • Something old
    • Fortran
    • COBOL
    • Pascal
    • Ada
    • Assembly
  • Something new
    • Idris
    • Io
    • Dart
    • Elm
    • TypeScript
  • Something borrowed(from another domain)
    • TeX
    • PL/SQL
    • Prolog
    • Verilog / VHDL
  • Something blue(corporate/government)
    • Objective-C
    • PowerShell
    • ColdFusion
    • MUMPS (OpenM)
Achievement Unlocked A Better Path to Language Learning Midwest.io 2015 Joel Martin Press 's' to show speaker notes Silence phone Have sized window for mal demo open Prune foo from Makefile and foo/ Build impls: bash, python, js, mal Setup screen sharing Preload guide Preload step0 image, step1 image, step2 image in presentation window for quick tabbing.