Background

So a coworker the other day in the slack channels had shared some links to SICP and the associated lecture on the metacircular evaluator.

I thought that another good addition to the resources provided would be Peter Norvig's small Lisp implementation in Python. And I got the thinking I haven't coded elm in a while let me see if I can write and get going.

I was also thinking that I could add to the introductory material on working in elm.

Installing Elm

Getting a copy of elm is easy!

You can either

1. Download your installer from install page

2. If you have node installed you can

  npm install elm 

Getting Started

Once you have a copy of elm you want to create a new directory for your project.

    mkdir lispelm 

Init elm

Using elm init which comes installed with elm we can initialize our elm project.

    cd lispelm && elm init  

It will ask you if you are ok with some stuff and then point you to read the documentation. I also recommend you giving the official documentation a look over.

Say yes and let it do its thing.

If we see whats our director now

    ls 

elm.json src

We have an elm.json file which stores information about our dependencies, project metadata and other things.

So next we want to create a file in the src directory to work out of

    touch src/Main.elm  

Peter Norvig Lis.py

Peter Norvig has done implementations of programming languages in Python, Common Lisp and even Java. You should totally go read some of his stuff over at his blog. I will be loosely basing my approach and style off his work.

Given the nature of Elm being statically typed we may have a little easier time but this is a guess.

What do you mean by that?

Essentially we will be writing a function in elm that takes as input expression and returns or evaluates to a value. This function has a fitting name an evaluate`.

So we have identified our input and output and a function name. We have enough to write a type spec:

eval : Expr -> Val

I changed evaluate to eval and Value to Val.

Side Quest: Building a Calculator

Super easy what does a calculator have? Numbers yeah and operations on those numbers

Can we build a language that describes the calculator?

Well Sure lets go back to the really basic calculators first though, Lets only consider Add because why not.

So what meaning do we usually get from a calculator?

Numbers !

So our calculator(evaluator) will return numbers.

Our calculator is simple. It has numbers and 2 operations (+) and (=). We can think of the calculator as having its own language comprising just of Add and the different Numbers.

Well what is equal there for?

Well that's how we translate from CalcLang to the calculator screen usually?

Its Essentially

"What do You mean by that"

Alright enough talk lets write some code, having some foresight into me knowing I'm going to mess up ill call this type my draft One. Our first attempt at modeling our calculator may look like this

    type alias Digit = Int  
    type CalcLanDraftOne = Add Digit Digit |Val Digit  

Using our imaginary calculator with only numbers and the "+" button does our type allow us to express everything we can press?

Well lets press "1" then press "+" then press "3" well how might we express** (cough cough foreshadow)

these action in our CalcLang draft.

    Add (Val 1) (Val 3) 

Add (Val 1) (Val 3) : CalcLanDraftOne So far so good now what about this

Lets press "1" then press "+" then press "1" then press "+" then press "1"

Can you express this in CalcLanDraftOne ?

Nope ?

To keep a history just comment the above type out

Lets try again,

 type CalcLanDrafTwo = Add CalcLanDrafTwo CalcLanDraftTwo | Val Digit    

Can we express that statement now ? I think so

Add 1 (Add 1 1)

Add (Val 1) (Add (Val 1) (Val 1)) Add (Val 1) (Add (Val 1) (Val 1))

: CalcLanDraftTwo  
So in CalcLangDraftTwo we seem to be ok for now. Since we have the language kind of understood with our model lets see 

What do you mean by that?

Lets write calc or eval

    eval : CalcLanDrafTwo -> Number  
    eval calcLangExpression =  
        case calcLangExpression of  
            Add expr1 expr2 ->  
                eval expr1 + eval expr2  
            s -> s 

Note how the meaning of Adding two expressions only relies on the meaning of its arguments, this is a property we will want to note for later.

I just want to take a brief note here because this is only one of many answers to the question

What do you mean by that?

Can you think of another meaning to derive from the CalcLanDrafTwo?

    print: CalcLanDrafTwo -> String  
    print calcLangExpression =  
        case calcLangExpression of  
           Add expr1 expr2 ->  
               String.concat [print expr1,"+",print expr2]  
           s -> String.fromInt s  

We have a couple of semantics defined over our CalcLang or two answers to

What does that even mean ?

I'm remembering from high school my TI-84, I could go up and down and look at my old results?

Some could say we had History

Does this modify our language?

I don't think so its more of the meaning changes, if you bring history and some language can you describe history? I think you can, people always bias their meaning with history and it adds to their story....

    evalWithHistory : CalcLanDrafTwo -> History -> History 

Can we make it so that our evalWithHistory function if we looked at the History returned and get the first story that is equal to the value of our expression? In code :

    evalWithHistory expr someHistory = placeIntoHistory (eval expr) someHistory  

Why yes lets just go from the definition

We have two cases in our CalcLanDrafTwo:

• a Number

• the addition of two calcLangExpression

Lets tackle case 1 first

Well if we our trying to evaluate a number with some history ,isn't that just adding the number to our history

    evalWithHistory 3 someHistory = placeIntoHistory (eval 3) someHistory 

and then because eval 3 = 3

    evalWithHistory 3 someHistory = placeIntoHistory 3 someHistory 

Lets tackle case 2

We try to evaluate an Add expression that adds two expressions

    evalWithHistory (Add x y) someHistory  = placeIntoHistory (eval (Add x y)) someHistory 

and then because eval (Add x y) = eval x + eval y

    evalWithHistory (Add x y) someHistory  = placeIntoHistory (eval x + eval y)) someHistory 

Well we could say stop here but remembering that property I noted earlier how eval evaluated the Add case in terms only of its meaning. Can we do that here?

Well keeping that in mind what do we know so far well we have a relationship between eval and evalWithHistory

    evalWithHistory exp history = placeIntoHistory (eval exp) history 

we can also go the other way eval our exp is the same as getting the most recent element from our history list that we got from evalWithHistory exp of noHistory.

    eval exp = getFirstFromHistory (evalWithHistory exp noHistory)  

Can we use this information to help us?

    evalWithHistory (Add x y) someHistory  = placeIntoHistory (eval x + eval y)) someHistory  
        = placeIntoHistory (getFirstFromHistory(evalWithHistory x someHistory) + eval y)) someHistory 

we can replace eval y similarly

        = placeIntoHistory  
            (getFirstFromHistory(evalWithHistory x someHistory) +  
            (getFirstFromHistory(evalWithHistory y someHistory)) someHistory 

But wait instead of passing someHistory twice we can put them both on the stack and then add the first two numbers of the stack putting that back on the stack.

        = addFirstTwoHistory  
            (evalWithHistory x (evalWithHistory y someHistory)) 

So that works pretty well we can repeatedly call evalWithHistory and keep a record of what happened.

Ok so like this wasnt a thing in my TI-84 but imagine we want to just be able to delay our calculations you know if we had like a really lon calculation. unlikely but work with mem here.

We can use Continuations, a continuation is sort of like a promise but it a function that takes a function as an argument to essentially tell it what to do next.

Essentially we want a function that meets this requirement

    evalWithDelay expr cont history =  
        cont (evalWithHistory expr history) 

Lets break this down again we have our two cases a value and an addition
. = cont ( evalWithHistory (Val 3) history ) = cont ( placeIntoHistory (Val 3) history )

That was the easy case now letts do the addition

    cont (evalWithHistory (Add x y) history)  
    = cont (addFirstTwoHistory (evalWithHistory x (evalWithHistory y history)))  
    = (cont << addFirstTwoHistory) (evalWithHistory x (evalWithHistory y history)) 

Now notice that we are doing one thing after evaluating the other so in other words

    =  
    evalWithDelay x (cont << addFirstTwoHistory) (evalWithHistory y history) 

And notice again

    =  
    evalWithDelay x (evalWithDelay y (cont << addFirstTwoHistory)  history)  

So this works we get delayed calculation

    evalWithDelay (Val 3) id     

: History -> History

Playing around with what we have so far yields interesting things

    evalWithDelay (Val 3) id     
    evalWithDelay (Val 3) addFirstTwoHistory     
    evalWithDelay (Val 3) ((::) 3) 

You should put these in the repl and see what happens when you pass these a [2]

Now I like functions and continuations as much as everyone else but I would rather be able to deal with something else to pass as args.

    Code Baby  
 
    type Code = Halt | AddS Code | Push Code 

Here Code represents our delayed computation (continuation) so instead of gettin our answers immediately like we said earllier we can delay it and get stuff later. To help us to do this we give thes delays a represeentation (code).

Now to execute this code would be to actually get answers weve made it a long way from out interpreter.

Lets write an execute function

    execute : Code -> History -> History  
    execute code =  
        case code of  
            Halt -> halt  
            Push n c -> pushC n (execute c)  
            AddS c -> addC (execute c)  
 
 
    pushC :  Digit -> (History -> History) -> History -> History  
    pushC n c = c << (::) n  
 
    addC : (History -> History) -> History -> History  
    addC c = c << addHistory  
 
    compC : Expr -> Code -> Code  
    compC expr cont =  
        case expr of  
            Val n ->  Push n cont  
            Add e1 e2 -> compC e1 (compC e2 (AddS cont )) 

As you can see our execute code just returns continuations and for us to actually ggget an answer we need to stop our machine.