EECS 662

Programming Languages

Index
Blog

EECS 662 Blog

Project updates

Greatings from Annapolis!

Two quick updates on the project. I’ve updated the recursive test case I provided to provide a proper type for ie. It should be Nat->Nat rather than just Nat. It executes fine as is, but it is not properly typed.

I’ve added the concrete syntax for bind to the langauge in the project description. bind is in the abstract syntax and parser provided, but I forgot to add it to the syntax description. This should not have caused anyone difficulty, but could prove confusing if you’re reading carefully.


Fix Test Case

As promised, here is a test case for fix that implements factorial. I’ve also included types so this should be a good test case for your typeof function:

"app (fix (lambda (ie:Nat->Nat) in (lambda (x:Nat) in if (isZero x) then x else x + app ie x - 1))) 5"

You should be able to drop this right into your interp function. I pulled out all the formatting so you can just copy paste. Here’s what the test case looks like with reasonable formatting:

app (fix (lambda (ie:Nat->Nat) in
            (lambda (x:Nat) in
               if (isZero x) then x else x + app ie x - 1)))
	5

You can use bind to create nice names like fact and factorial as we did in class.

This test case is nice because it tests a ton of functionality. If you can get it to interpret successfully, you’re in great shape.


Project 4 Posted

The first version of the Project 4 description is available. I’m still cleaning up and testing the utilities file and will post it over the weekend. The project description contains listings of the various AST and value data structures. This should allow you to get started on the evaluators and type inference functions if you so choose.


Project 1 Graded

Subject says it all. Project 1 is graded and grades are posted on blackboard. Please read comments I left as I had questions over some of your projects that impact project grades. I have asked for resubmission in some cases.


Dynamic vs Static Scoping Test Case

As promised, here is your test case for comparing dynamic and static scoping. First, the version that uses bind before elaboration:

bind n = 5 in
  bind f = (lambda (x:Nat) in x+n) in
    bind n = 1 in
      app f 3"

When I parse this example I get the following structure:

Bind "n" (Num 5)
  (Bind "f" (Lambda "x" TNum (Plus (Id "x") (Id "n")))
     (Bind "n" (Num 1) (App (Id "f") (Num 3))))

When I elaborate that result I get the following structure:

App (Lambda "n" 
      (App (Lambda "f"
              (App (Lambda "n"
                      (App (Id "f") (Num 3)))
                   (Num 1)))
           (Lambda "x" (Plus (Id "x") (Id "n")))))
    (Num 5)

My statically scoped interpreter gives me 8 and my dynamically scoped interpreter gives me 4.

I’ve tried to get the indentation set up so both arguments to each app are lined up. Still, I suspect what you want is the concrete syntax for this expression:

(app (lambda n in
        (app (lambda f in
                (app (lambda n in
                        (app f 3))
                      1))
             (lambda x in x + n)))
      5)

If you’re using the string parser, you’ll need to get rid of the line breaks and turn the expression into a string using quotes.

For what it’s worth, I got this expression by writing an elaborator rather than trying to hand translate the bind expressions into app and lambda.


If or If0

If you look carefully at the project description and the utilities file for Project 3 you’ll notice the description uses the constructor if0 for if expressions while the utilities file uses if. It makes no difference which constructor you use. If you want to, you can change the utilities file to use If0 to be consistent with the book.

I’m hesitant to push out a change until the project is done because I don’t want to accidentally mess anyone up. You can use the utilities file as is or change the constructor name and everything will work fine regardless.


Project 3 Environments

I just made a small update to the definition of Project 3 to clarify differences in the environments for dynamic and static scoping. The original description used the same environment type name, Env, for both static and dynamic scoping. However, what’s in the environment differs between interpreters. When using dynamic scoping, the value stored with an ID in Env is simply a CFAE value. You just reuse the datatype from your AST definition and you’re done. When using static scoping, the value stored with an ID in Env is a CFAEValue.

What this means is you can’t use the same Env type in both interpreters unless you employ some Haskell type-fu that I don’t expect you to know. Fortunately it is not a big deal to fix and if you implement your interpreters in separate files you likely did not even notice. What I did in the new project description is define the two evaluation functions to use EnvD and EnvS respectively. This eliminates the type clash between the definitions with almost no pain.

If you already have your project working, do not go back and change it to use these new type names. There is no reason to do that. If you use separate files for your implementations, you can use Env as shown in the original project description.


Project 3 Updates

I just pushed a new version of the project description that makes a few corrections and updates the due date to April 20. Corrections include using the definition for bind elaboration that we used in class today and fixing the link to the parser utilities file. Hopefully that was it.

I also mentioned in class it is okay to change return values to use Either or Maybe if you want to implement the interpreters monadically. Personally, I would use the do notation and Maybe, but it’s a matter of what you’re most comfortable with. There is certainly no requirement to use the monadic style.

Finally, I mentioned it is okay to use the Haskell error function to throw errors on this project. Next project will worry about error handling.


Project 3 Posted

I just pushed up a draft of Project 3. I’m still working on proofing and cleaning up the description, but thought I would push it up anyway so you can begin looking at it (or even coding). I do not have the two parsers quite ready to post yet, but you can start on the evaluators and elaborators without a concrete syntax and parser to work from. Hooking in the parser should be your last development step.

We’ll talk about when this project is due formally in class. In the mean time if you find errors or anything that confuses you, please do let me know.


Project 2 Parser Issues

An issue was raised concerning the parser in class today. I just built and ran the parser through a number of test cases and did not see any errors. Make sure you have the current version of parserUtils.hs. Specifically, look at your version and make sure that seq is listed as a keyword along with the list operations. If they aren’t there, you have the wrong version.


Testing

I’ve gotten quite a few questions about error handling for Project 2. For this project I’m not interested in how your interpreters handle errors. You should implement it, but I will not use test cases that would generate an error on a properly working interpreter. Nor will I use test cases that are not syntactically correct. We will care quite a bit about errors in future projects, but not this one.


Unsafe Evilness

As discussed in class today, I’ve come up with a bit of a hack to get printing to work as intended. It involves performUnsafeIO, a function I would normally never want you to use. But, sometimes you’ve just got to get the program to run and now is one of those times.

First, you need to import the unsafe operations for IO:

import System.IO.Unsafe

You can then use this Haskell code to print t, then return (Num 0). Remember that return is the same as Right:

(seq (unsafePerformIO (print t)) return (Num 0))

The seq function in this snippet is the Haskell seq, not the sequence you are implementing for your interpreter.

I hope this helps!


Midterm Topics Posted

I’ve posted a collection of topics for the midterm in the Exams section of the class website. A good rule of thumb for studying is if it wasn’t covered in class, it won’t be on the exam. Also, there will be little if any Haskell programming. Focus on writing programs in the languages we’ve developed rather than programming in Haskell. You get plenty of Haskell completing your projects.


Print Laziness

Well folks, Thursday was just a bad day all around. As it turns out my example for printing using let to force evaluation doesn’t work. As it turns out I actually did something slightly different in my code that didn’t make it to the board in class. This will not work:

let i = print t in (Num 0)

and lazy evaluation is the culprit. Kudos to those of you who caught this when I did it on the board. i is not used, thus the print never happens. One reasonable way around this is to use Haskell’s seq operation:

(seq (print t) (return (Num 0)))

This forces the print to evaluate and then evaluates and returns return (Num 0). This works in my code. You can either use this in the do notation or a let.

One of you industrious entrepreneurs should develop a whiteboard that checks and executes code as it’s written. That would be majorly cool…


Never Again

Given the outcome of yesterday’s game I have decided I will never again let class out early to watch KU men’s basketball. We tempted the Gods of Partial Credit and their retribution was swift. Sigh…


Project 2 Updates

I just pushed several updates to the Project 2 description. There are no changes to what I want you to implement, but there were some parts of the description that were not clear or were associated with an older project. Should be easier to follow now.
Please bring your questions to class!


Project 2 Updates Updates

Several updates to Project 2 that should be of interest.

Due date is now March 16 rather than March 14. This is a direct result of great questions I got in class and during office hours. Plus, I wanted a chance to correct some errors and discuss again in class on March 14.

The exercise using QuickCheck is gone. You are welcome to use it, but I decided it was too much to learn for this project. Please do test your code, but you don’t need to use QuickCheck.

proj2Utils has been updated to eliminate cruft from an old problem I intended to assign. The data structures should work for you now. Note that the same parser and data structure should work for both exercises.


Project 2 Utilities

I’m providing a parser and AST data structure for Project 2 that you can base your implementations on. The file proj2Utils contains both the parser and AST structures you’ll need along with necessary imports. It’s easiest to simply copy the contents of this file into your project file.

I’ve also updated parserUtils to handle new keywords. You’ll need to download the new version if you want to use the Project 2 parser.


Project 2 Posted

Project 2 is posted. I’m still proofreading, but the project details will not change. You will be implementing a simple print command and untyped lists. I am testing a parser and AST definition you can use for your implementation that should be posted by the end of the day. This project requires a bit more work than the previous projects, so please get an early start. As always I am happy to answer whatever questions you might have in class.


Minor Error in Beta Reduction

I made a small error in my notation for beta-reduction Tuesday. I wrote this:

The $t_1$ term should not be there. It should be:

I used the rule correctly, just threw in an extra term. Sorry about that. Again, this will not be on any exam, just FYI in class.


Interp Problems

Lots of folks are having issues with the interp function that combines the type checker, optimizer and evaluator for Project 1. The interpreter function I’ve defined looks like this:

interpTyped :: String -> Either String ABE
interpTyped e = let p=(parseABE e) in
                  case (typeof p) of
                    (Right _) -> (Right (eval p))
                    (Left m) -> (Left m)

and you guys are trying to use it verbatim. Unfortunately, the eval function called by this interpreter and the eval function I’ve asked you to write have different type signatures. Specifically, eval from my implementation has the following signature:

eval :: ABE -> ABE

This is much like the bind interpreter we’ve been working on in class. Instead of an Either type, this eval returns an ABE. My interpTyped above returns a value of type Either String ABE. Thus, when eval returns a value it must be lifted into Either String ABE using the Right constructor. See the third line of interpTyped above.

The eval function for your your current project has the signature:

eval :: ABE -> Either String ABE

Big difference! This eval returns an Either type directly. There is no need to lift the return value using Right as we did above. The Right constructor can be dropped. Note the difference in the third line in his version of interp:

interpTyped :: String -> Either String ABE
interpTyped e = let p=(parseABE e) in
                  case (typeof p) of
                    (Right _) -> (eval p)
                    (Left m) -> (Left m)

This is why you keep hearing me say delete that Right over and over again! eval returns an Either type that does not need to be turned into an Either type for interpTyped to return.


Project 1 Update Update

I just updated the Project 1 description to correct an error on the signature of optimize. The original signature takes an ABE and produces an Either String ABE like the evaluator. The optimizer never generates an error. Thus, it’s perfectly safe to skip the error option and change the signature to:

optimize :: ABE -> ABE

If you have already implemented the optimizer with an Either type, there’s no reason to change it. The optimizer will simply never return Left m.


Project 1 Update

Quick update to Project 1. The original description asks for a function, typeof, with the signature:

typeof :: ABE -> (Either String ABE)

that returns an error message or an abstract syntax value. It should have the signature:

typeof :: ABE -> (Either String TABE)

that returns an error message or a type value. This should make better sense - typeof returns either a type or an error message. The project description has been updated as of 17 February 2017 at 8:32 PM, so if you’re reading the project description for the first time after this date you can safely ignore this posting.


Project 1 Posted

I have posted a draft version of Project 1 where you will write a type checker (surprise!) and a simple optimizer for an extended version of the ABE language. The project will not change substantially, so please feel free to start if you want. However, I will be proofing the project and making corrections before I assign a due date.


Testing

For Project 0 I am not requiring anything specific related to testing. In particular, you do not need to use QuickCheck. I’ve not covered that in class yet, but you can use it if you choose to.

Here are a couple of ideas that might help you with testing. The first is defining and naming a set of test cases that you can simply use over and over again:

test1 = interp "1+(2-3)"
test2 = interp "(2*4) + (7-9)"

This allows you to execute a single test case to see what happens. Another option is to map your interp function over a list of strings:

map interp ["1+(2-3)","8*9"]

This will return a list of results corresponding to your list of input strings. This has the simple advantage of doing all your tests in one function call.


Errors

Every time I teach this class, I learn something new about what can be confusing. This year’s first learning moment for me is error handling in Project 0. There has been significant wailing and gnashing of teeth over what to do with errors.

The answer is pretty simple.

Nothing.

Just let the interpreter crash.

I’ll even do you one better. I promise not to test your interpreters on bad test cases. Hopefully that will end the confusion!


Submissions

I just updated the Blackboard submission site to allow for multiple submissions. If you want to resubmit before the deadline, you should be able to. I don’t know why Blackboard defaults to single submission attempts. Seems kind of goofy.


Parsing If

It just struck me that I’ve not gone over parsing if expressions in class and you need to parse if0 for Project 0. Thankfully, there is a great example of parsing if in the source code from the Adding Booleans chapter. You should have no problem extending the parser for if0 using that example.


Language Extension

The language extension mentioned in class today to get the parser working in the most recent versions of GHC is:

{-# LANGUAGE FlexibleContexts #-}

You’ll see in my files the extension:

{-# LANGUAGE GADTs #-}

You can just add FlexibleContexts like this:

{-# LANGUAGE GADTs,FlexibleContexts #-}

Divide by Zero

You do not need to worry about handling divide-by-zero errors in Project 0. I’m not going to test for that case. We’ll worry about errors in Project 1.

If you are curious and do want to catch this error, simply test the denominator value before performing division and use the error function to throw a Haskell error. Don’t use Maybe or Either for this project. You’ll get plenty of that later.


parserUtils

Folks are having a hard time finding the parserUtils file that I used in all my interpreters. Sorry about that. You can download parserUtils here.


GADT Notation

In my notes and in class I have been using the GADT notation when defining data types. I do this because it closely resembles other languages that I use and we will most likely use GADTs later in the semester.

If you prefer the traditional notation that you learned in 368, you are more than welcome to us it. For early projects, there is no read advantage to using the GADT notation.


Welcome!

Welcome to the website for EECS 662 - Programming Languages at the University of Kansas. Contents of this blog are available via an Atom feed that can be viewed using any RSS reader. Use this url. Please check here frequently for breaking news and information about projects and exams.

This site is hosted on GitHub and constructed using GitHub Pages, Jekyll and Liquid Tags.


No Class January 19

I mistakenly scheduled an invited talk on January 20 that requires me to travel the afternoon of January 19. Thus, we will not have class that day. I will be available for office hours. Sorry about that.