CS 210: Programming Languages Lecture Notes

lecture #20 began here

lecture #21 began here

lecture #22 began here

Midterm on Friday this week

Thoughts on ML TextIO.inputLine

• (TextIO.inputLine f) doesn't return a string, it returns a "string option".
• An "option" is a weird type system cheat for when things are optional, either a SOME or a NONE. If it is a SOME it has an associated value and if it is a NONE it does not.
• (valOf (TextIO.inputLine f)) returns the string from the option, or dies (exception) trying.
• You can avoid the "dies trying" exception risk by handling the two cases of the option (the SOME or the NONE).
• Example

      case TextIO.inputLine f of
         NONE => "end of file"
       | SOME v => v 
  

• The string returned by inputLine has a newline on it.
• Removing the last character from a string would be something like
  String.substring (s, 0, size s - 1)

lecture 23

CoronaVirus Update

• Campus authorities have instructed us to not physically hold class for rest of the semester.
• Class will be online via Zoom.
• You can attend from home, or from your dorm or house on campus, so long as you have good internet.
• You should have your microphone muted except when you are asking a question.
• Our CS 210 Zoom ID is 625-323-868. You may wish to connect to zoom.uidaho.edu and then join our session.
• I will run class from my office (or home office) our classroom appears to not have a camera setup.

CDAR Testing?

Random numbers in ML

val r = Random.rand(1,1);

returns a random number generator object. The tuple is used to generate a random seed; almost any two integers would work.

val nextInt = Random.randRange(1,100);

returns a function that takes a random number generator and returns an integer between 1 and 100.

nextInt r;

fetches a random number in the range nextInt was setup for (1..100)

Random.randReal r;

fetches a random number between 0.0 and 1.0

Midterm Review

• Friday's exam will be on Flex and Bison and ML
• Emphasis will be on Flex and Bison because you have had more time to learn them. ML may feature more than Flex/Bison on the final.

Programming Languages Big Picture Stuff

Flex Review Materials

• flex's basic syntax, major sections, etc.
• basic regular expressions and regex operators
• flex's extended regular expressions -- at least most of them
• sample.l was done in class to illustrate previous three bullets
• how flex is called from C code, how it communicates with the caller

Bison Review Materials

• bison's basic syntax, major sections, etc.
• basic context free grammar notation A : b A c ;
• what is a shift and what is a reduce
• how a bison generated parser is called from C code (yyparse()), how it communicates with the caller, how it communicates with flex
• basic idea of how to build a parse tree

ML Review Materials

ML language

syntax and semantics

ML runtime system

garbage collection, symbol table

Using ML

common ML built-in functions and control structures

ML execution behavior

be able to diagram memory

What to study in ML

• Functional programming paradigm
• clean, mathematical thinking about computation
• exploratory and experimental programming
• How is ML different than C++?
• Practice with recursion

lecture 24

Welcome to Virtual CS 210

HW#3 Extension

Midterm Exam Results

157 157
140 143 145 147 149
---------------------- A
132 137
124 129
---------------------- B
111 113 116 117 117
102 103 105
---------------------- C
96
81
---------------------- D
65
34

Midterm Examination Solutions

Mailbag

How do I print multiple lines at one time in ML?

That depends on what you mean by multiple lines I guess. To print out multiple lines at one time, you may want to concatenate those lines into one big string s, putting "\n" characters in between each line. Then call TextIO.output(s) on it. Alternatively, you could use a loop or recursion to output several lines with several calls to TextIO.output.

How can I clear the screen?

Clearing the screen might be tricky. ML is not exactly designed to be doing advanced terminal stuff, and advanced terminal stuff tends to be not portable -- what works on Linux might be different than what works on Windows or MacOS for example. My first thought was to call

TextIO.output("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n");

with enough newline characters to clear the screen. On cs-210.cs.uidaho.edu you could probably also use OS.Process.system("clear"). More advanced interactive programs might want to be able to move the cursor to a particular row and column, or go into "raw" input mode to read characters one key at a time, but that is beyond the scope of this class.

I wrote an exit() function, but it gives a warning message. How do I get rid of that?

- fun exit () = OS.Process.exit OS.Process.success;
   ...
- exit();
stdIn:2.1-2.7 Warning: type vars not generalized because of
   value restriction are instantiated to dummy types (X1,X2,...)

The warning is harmless and has to do with the SML type inferencer not knowing what to do with the return type of function exit(). Perhaps the simplest way to shut it up is to return something else. The following example discards the return value of exit and just returns false.

- fun exit () = (OS.Process.exit OS.Process.success; false);
    ...
- exit();

My ML global variables aren't working, what do I do?

They work alright, but they are immutable. In pure functional programming, you don't modify existing values, you construct new ones. ML feels strong enough about this that variables are generally immutable. Dr. Webber feels strongly enough about it that at the end of the slides for his 4th Look at ML chapter, he mentions that he explicitly omitted a discussion of "reference types" which are ML's way of having mutable values.

Brief Primer on ML Reference Types

• A value of type "int ref" is a pointer to an int.
• The ! reads/dereferences the value pointed to.
• The := operator writes/modifies what a ref points to.

- val Health : int ref = ref 30;
val Health = ref 30 : int ref
- Health;
val it = ref 30 : int ref
- !Health;
val it = 30 : int
- Health := (!Health) - 1;
val it = () : unit
- !Health;
val it = 29 : int

lecture 25

Practice Raising your Hand

Mailbag

Can you tell me what is wrong with my code? It is saying "Error: unresolved flex record (can't tell what fields there are besides #1)"

When the SML type inferencer fails, it sometimes makes you spell out what types to use. For example, you can tell it you have a list of tuples like this:

fun print_hand (L:(int*bool*string*int*int) list,i) = ...

Per earlier in class discussion, using tuple elements by position (#1) is usually not the best way to do it. But do what you gotta.

• Unicon Lecture #1 (17 minutes)
• Fundamentals of the Goal-Directed Paradigm (8 minutes)

• Philosophy: make programming as easy as possible
• Very high level, familiar^* syntax, (a lot of) extra power
• Descended from SNOBOL, via Icon
• Unicon was created around 2000 by merging several extensions of Icon. The initial contributions were by Clinton Jeffery, Shamim Mohammed, and Federico Balbi.
• Unicon is hosted at unicon.org and the code is on Source Forge and Github.
• Besides Unicon father Clinton Jeffery, the language incorporates major contributions from around two dozen individuals listed on Unicon's Citizens page
• Unicon is a goal-directed language
• Goal-directed evaluation simplifies many expressions and makes them clearer. This is from real life, i.e. a student's CS 445 homework.

  else if (node->kids[1]->prodrule == ADDITIVE_EXPRESSION + 1 ||
      node->kids[1]->prodrule == ADDITIVE_EXPRESSION + 2 ||
      node->kids[1]->prodrule == MULTIPLICATIVE_EXPRESSION + 1 ||
      node->kids[1]->prodrule == MULTIPLICATIVE_EXPRESSION + 2 ||
      node->kids[1]->prodrule == MULTIPLICATIVE_EXPRESSION + 3 )
      ...
  

  Compare with this Unicon code:

  else if node.kids[2].prodrule =
     ((ADDITIVE_EXPRESSION+(1|2)) | (MULTIPLICATIVE_EXPRESSION+(1|2|3)) then...
  

Unicon Basics

Variable declaration is optional

This is a compromise between the needs of scripting/prototyping languages, and the need to support larger mainstream software engineering projects.
local, global, and static declarations are recommended in large programs or libraries.

Variables can hold any data type, and reassigned with different types

Like in Lisp, Python etc. But this is very rare in practice.

type(x) returns a string type name ("list", "integer" etc) of x

You can write code that works across multiple types. Heterogeneous, polymorphic awesomeness.

arithmetic is pretty normal

^ is an exponentiation operator. Integers are unlimited precision. Reals are C doubles.

Type conversion is automatic across scalar types

Runtime error when conversion won't work, except in explicit conversion functions, which fail instead.

Strings use double quotes and are escaped using \

indexes are 1-based; they are immutable, atomic; not arrays of char; there is no char type

s[i] := "hello" works

really like s[1:i] || "hello" || s[i+1:0]

*s is a length operator, repl(s,i) is i concatenations of s

expressions in Icon can fail to produce a result

failure cascades to surrounding expressions

Built-in types include lists, tables, sets, csets, and records.

Arguably simpler to use than Common Lisp's

Classes and packages

Well-suited for large-scale apps

Easy I/O capabilities

2D, 3D, and network programming

Fundamentals of the Goal-Directed Paradigm

Fallible Expressions

• Expressions want to succeed in computing their result
• Some expressions cannot fail, or cannot succeed
• Some expressions are explicitly intended to test and possibly fail
• Most expressions can do their thing iff their operands succeed
• A fallible expression is one that may possibly produce 0 results.

can't fail	can't succeed	test (fallible)	depends on operands
1	&fail	x < 1	x+1

lecture 26

• Recording of 3/27/2020 class.

Generators are simply expressions that logically might produce more than one result. For further reading, see "Generators in Icon", by Griswold, Hanson, and Korb.

Some common generators in Unicon include:

• i to j generates all the numbers between i and j
• x | y generates x and then y (called alternation)
• !x generates elements from x

• find(s) generates all positions where s occurs
• upto(c) generates all positions where a member of c occurs

String Scanning

   s ? expr

   s ? find(s2)

You almost never use string scanning if you only have one string function to call, but rather, when you are breaking up a string into pieces with multiple functions. In this case, function tab(i) changes the position to i, and function move(i) moves the position by i characters. tab() and move() return the substring between the start position and where they change it to.

    s ? {
       if write(f, tab(find("//"))) then {
	  move(2) # move past //
          write(&errout, "trimmed comment ", tab(0))
          }
       else write(&errout, "there was no comment")
       }

find(s)

search for a string

upto(c)

search for a position at which any character in set c can be found

match(s)

if current position starts with s, return position after it

any(c)

if current character is in c, return position after it

many(c)

if current position starts with characters in c, return position after them

bal(c1,c2,c3)

like upto(), but only return positions at which string is "balanced" with respect to c2, c3. Tricky in one respect.

We looked at several string scanning functions within an example program foo.icn.

lecture 27

Pass/Fail Option; Later Drop Deadline

• You now have until May 1 to decide if you want to switch to Pass/Fail, or if you wish to drop.
• Switching to Pass Fail might be good or bad.
• A grade of P does not count on your GPA but a Fail does count.
• Since Passing in Pass Fail clears you to proceed with later CS courses which require a C or above, a Pass will be assigned for work equivalent to a C or above, relative to your peers.
• In a typical Jeffery CS class, "C or above" is earned with some overall score of roughly 55-65% of available points.
• I will adhere to grade categories and percentages in the syllabus
• Points awarded on bblearn are not used as-is; they are weighted by me in calculating the final grade, to reflect some assignments being more difficult or more important than others.

Virtual CSAC

ShareScreen dropped out in the first generator lecture

Resubmits, Regrades, and Grade Checks

Office Hours: Switching to Meeting ID 795-166-283

More about Generators

a | b

The simplest generator is alternation. Instead of saying

x = 5 | x = 10

you can just say x = (5|10). This is shorter and more readable than ordinary programming languages, instead of adding power by being "weirder". Maybe read | as "then" instead of "or". So what does

  (1 | 2) + (x | y)

do?

i to j
i to j by step

The coolness here is that a traditional language's "for-loop" has been generalized not just into an iterator, but into an expression that can be smoothly blended into any surrounding expression context.

!x

All data structures in the language support the "generate" operator to produce their contents. Files generate their contents a line at a time. Consider

   s == !f

find(s), upto(c), and bal(c1,c2,c3)

These classic string pattern matching generators produce (return) indices within a string.

• They take optional parameters for string to examine, and start and end positions to consider.
• They are usually used in a string scanning environment where these parameters may be omitted.
• Of the three, bal() is seldom used and a bit trickier than the others. It generates positions containing characters in c1 (like upto()) balanced with respect to c2 and c3. Note that if *c2 and *c3 are greater than 1, though, it does not distinguish different kinds of parentheses.

seq(), key()

For completeness sake, here are the remaining two "built-in" generators. seq() generates an infinite sequence of integers. key() generates the "keys" of a table or set.

User-Defined Generators

procedure fib()
   local u1, u2, f, i
   suspend 1|1
   u1 := u2 := 1
   repeat {
      f := u1 + u2
      suspend f
      u1 := u2
      u2 := f
      }
end

• This procedure generates the numbers in the fibonacci sequence.
• Compared to calling the naive recursive fibonacci function for higher and higher values of n, this single call that generates many results runs crazy fast.
• But the sequence is infinite, so if you call this from an every loop it will never stop.
• There is a limitation operator that can limit a generator to at most n results: g \ n

lecture 28

How unreliable is Dr. J's home machine?

Reading

Record the Lecture Please, Dr. J

Scalar Types are immutable and passed by value. They can at least semi-plausibly be converted to and fro.

integer

arbitrary precision, ^ is an exponent operator
baservalue literals for bases 2-36.

real

double precision

strings

"hello\tworld\n", s1 || s2, s1 == s2, s[i], s[-i], s[i:j]
scanning control structure and functions, pattern matching

csets

'hello\tworld\n' === '\ndlrow\teh', c1 ++ c2, c1 -- c2 , any(c)
used heavily in scanning functions, keywords &letters etc.

Structure types are mutable, passed by reference, allow heterogeneous elements, can contain references to themselves, etc. They generally do not convert back and forth, but many structure operations are polymorphic.

lists

["hi", "CS", 210], L[i], L[i:j], L1 ||| L2, push(L, x), pop(L), put(L, x), pull(L)
arrays are special cases.
lists of lists are common; lists of tables etc.
lists can even contain themselves.

tables

["hi" : "there"; "CS" : 210], t[k]
beware using lists (etc.) as keys

sets

S1 ++ S2, S1 ** S2, S1 -- S2, member(), delete(), insert()

records and classes

constructors, methods, etc.

Oddball Types

files

includes open windows, pipes, network and database connections
much higher-level than typical languages' library-based access

co-expressions

denote a computation (say, a generator for example) that you can pass around and use from different locations, and for which you can grab its results one at a time as-needed

threads

denote a computation that can be executed in true multi-core parallel fashion. There are locks and message passing facilities to deal with race conditions.

lecture 29

Office Hours Today Rescheduled

HW#3 Comments

• A number of your ML programs were spectacular!
• A number of your ML programs were nonstarters
• Please to polish and resubmit your ML program, if you didn't really get it done, or got less credit for it than you deserved.

Turn on Recording, Dr. J

Records

• Like a struct
  • (Unicon also has classes, which are structs with functions)
• record rec(fielda, fieldb, fieldc) declares a new type
• Always a global, in fact after this declaration, rec is literally a global variable
• A record like a fixed-size list.
  • Except you can also access fields by name.
• Instances created by calling constructor function

     r := rec("mylabel", 2.71, 39)
  

• r.fieldb and r[2] and r["fieldb"] all denote the 2nd field

Recursive Generators

procedure walk(t)
   if /t then
      fail
   else {
      suspend walk(t.ltree | t.rtree)
      return t.data
   }
end

procedure walk(t, p)
   if /t then fail
   walk(t.ltree, p)
   walk(t.rtree, p)
   p(t.data)

procedure leaves(t)
   if /t then fail
   else if /(t.ltree === t.rtree) then
      return t.data
   else {
      suspend leaves(t.ltree | t.rtree)
      }
end

Recursion and Backtracking

• The point of generators and goal-directed evaluation is to provide implicit backtracking built-in to the language, when you need it.
• But is backtracking actually used? Is it so rare that we don't care?
• I first ran into it in the field of parsing (linguistics and compilers use parsers) where backtracking might be used to try different production rules
• Backtracking is broadly used in the CS area of searching, especially in A/I. Searching is pretty darn common/central/important.
• Backtracking can be especially powerful when combined with recursion.

This is a long slide set. You may wish to review additional slides in this slide deck, beyond the set covered in class.

lecture 30

Unicon: Classes and OOP

• Our textbook teaches OOP in its Java chapters, so I could take my pick of teaching you OO in Java or in Unicon.
• OOP was my initial contribution to Unicon, and there is a whole story there.
• I'll tell my story and then look through Webber to see what, if anything, he has to add.

Three Pillars of Object Orientation

encapsulation

• this is the fundamental ability to define an "object"
• police-state interpretation: this is about protection -- guaranteeing the outside world cannot mess up a piece of code+data by preventing access except through public interface functions. Makes it easier to prove correctness.
• sim/modeling interpretation: code is easier to read and debug if it is placed near the data that it manipulates, organized around application domain concepts

polymorphism

as covered earlier by Webber: encapsulation and public interfaces can facilitate writing code that works on different types

inheritance

we can write new code in terms of generalizations and specializations. we can write new kinds of objects in terms of their differences from what we've already got.

• Unicon's OOP is generally a lot simpler than mainstream languages.
• The goal is to add power, not to protect programmers from themselves.
• Everything is public, and everything is "virtual"; there are no static methods, and no non-virtual methods.

Here is a gentle syntax comparison, adapted from Hani Bani-Salameh.

C++	Unicon
class Example_Class { private: int x; int y; public: Example_Class() { x = y = 0; } ~Example_Class() { } int Add() { return x + y; } };	class Example_Class (x,y) method Add() return x + y end initially x := y := 0 end

• Classes are records with methods.
• Instances are created via a call: o := Example_Class(1,2)
• Methods are called via o.Add()
• constructor code is given via an optional initially section
• The initially may include parameters, and if it does, they are used INSTEAD of the default, which is to initialize fields directly from actual parameters passed in to the constructor.

Another OOP Example

class listable(L,T)
   method insert(k,value)
      /value := k
      T[k] := value
      put(L, value)
   end
   method lookup(k)
      return T[k]
   end
   method gen_in_order()
      suspend !L
   end
initially(defaultvalue)
   L := [ ]
   T := table(defaultvalue)
end

procedure main(argv)
   LT := listable(0)
   every s := !argv do
      LT.insert(s, LT.lookup(s)+1)
   every x := LT.gen_in_order() do
      write(x)
end

Unicon Inheritance

• When writing a class, superclasses are just a colon (:) away

  class Subclass : Super1 : Super2 (field1, field2)
  ...
  end
  

• If you wanted to call your parents method from your own, overriding method

  class B : A (fields)
     method M(x)
        # possibly do stuff before calling parent M
        self.A.M(x)  # call parent M
        # possibly do stuff after calling parent M
     end
  

• All the stuff you have in Subclass's own body comes first. Then you rifle through your parents' bodies looking for spare change, and anything else you can use. Any member variable or method not already defined is sucked in from that superclass and added onto the end of what you've got at present.
• works fabulously for any number of superclasses; superclasses are visited in depthfirst fashion

class fraction(numerator, denominator)
   #methods here
initially
end

class inverse : fraction(denominator)
initially
  numerator := 1
end

class sub : A : B(x)
initially
   x := 0
   self.A.initially()	# calling parent method in overriding subclass method
   self.B.initially()	# self is implicit in most other contexts.
end

Unicon Tips from the Ghosts of Students Past

procedures end with end

not { } as in C/C++/Java. Same goes for classes, methods

&& is not an "and" operator

& is an "and" operator

a generator only generated as much as its surrounding expression demands

if it is not driven by "every", it may well stop at its first result

if it is already a generator, ! won't make it more so

rather, it will generally mess it up

Can't just start assigning elements of an empty list

After L:=[], you will find that L[1] does not exist yet. Create with elements via list(n) or put() or push() elements onto your list before you try to subscript them.

Unicon: Graphics

• Unicon has some of the world's easiest 2D graphics
• w := open("window title", "g") opens a window
• inspired by the TRS-80 Extended Color BASIC graphics,
• influenced by the X Window System. (X11 and classic Mac and Windows 2D APIs were all inspired heavily by the original Xerox graphics workstations).
• although this was some of the first open source code I ever wrote, it is still in wide use. UIdaho's Gigi Young is on the cusp of replacing my original X Windows-based implementation of Unicon's graphics with an OpenGL reimplementation.

The 3D facilities (open() mode "gl") are also pretty darn simple. They are built atop (classic) OpenGL and have grown to emphasize the use of textures over time.

Q: When is "graphics" a programming language concept, and when is it software engineering, operating systems, architecture, or mathematics?

There are many answers.

• language vs. library.
• application layer vs. system layer.
• software vs. hardware.
• idea vs. implementation.

In Unicon, there is a built-in data type for graphics. The VM / runtime system is doing graphics even when you are not in a graphics function call. Perhaps there should be more operators and control structures for working with windows.

Main concepts of Unicon graphics:

window = canvas + context

a window is a binding of a drawable canvas and a set of drawing attributes. For easy switching, you can have more than one set of attributes bound to a given canvas at one time.

canvas

a canvas is a matrix of pixels you can draw on

context

a context is a set of attributes like color, font, linestyle, fill pattern...

"attribute=value" strings

canvas and context have attributes that you can set

pixels

color/contents of a single dot

coordinates

(x,y) integer coordinates from (0,0) in the upper left

colors

(r,g,b) values, often specified by names

fonts

pixel fill patterns used to draw text in a particular style

input processing and callback routines

keyboard and mouse read from a single function. user interfaces typically give control to a loop that reads this and then calls functions

language level (built-in) tries to provide essential features with simplest API possible, relatively complete programmer control

built-in API consists of ~30 or 40 functions, instead 400-800. attribute strings, not hundreds of new classes/record types.

Unicon class (library) level features an extensive GUI, modern concepts

procedure main()
   &window := open("rfm", "g", "fg=blue", "drawop=reverse")
   repeat {
      e := Event()
      case e of {
         &ldrag | &mdrag | &rdrag : {
	    FillRectangle(\x, y, 10, 10)
	    FillRectangle(x := &x, y := &y, 10, 10)
            }
         "q" : exit(0)
         }
      }
end

procedure main() 
   &window :=open("textured.icn","gl","bg=black","size=700,700")

   # Draw the floor of the room 
   WAttrib("texmode=on", "texture=carpet.gif")  
   FillPolygon(-7.0, -0.9, -14.0, -7.0, -7.0, -14.0,
                       7.0, -7.0, -14.0, 7.0, -0.9, -14.0, 3.5, 0.8, -14.0)
   # Draw the right wall
   WAttrib("texture=wall1.gif", "texcoord=0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 1.0, 1.0") 
   FillPolygon(2.0, 4.0, -8.0, 8.3, 8.0, -16.0, 8.3, -1.2, -16.0, 2.0, 0.4, -8.0)
   # Draw the left wall
   WAttrib("texture=wall2.gif")
   FillPolygon(2.0, 4.0 ,-8.0, -9.0, 8.0, -16.0, -9.0,-1.2,-16.0, 2.0, 0.4, -8.0)
   # Draw a picture
   WAttrib("texture=poster.gif", "texcoord=0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 1.0, 1.0")
   FillPolygon(1.0, 1.2, -3.0, 1.0, 0.7, -3.0, 1.2, 0.5, -2.6, 1.2, 1.0, -2.6)
   # Draw another picture
   WAttrib("texture=unicorn.gif", "texcoord=1.0, 0.0, 0.0, 0.0, 0.0, 1.0, 1.0, 1.0")
   FillPolygon(0.8, 2.0, -9.0, -3.0, 1.6, -9.0, 3.0, 3.9,-9.0, 0.8, 4.0, -9.0)
   # Draw the lamp
   WAttrib("texmode=off")
   PushMatrix()
   Translate(0.7, 0.20, -0.5)
   Fg("emission pale weak yellow")
   PushMatrix()
   Rotate(-5.0, 1.0, 0.0, 0.0)
   Rotate( 5.0, 0.0, 0.0, 1.0)
   DrawCylinder(-0.05, 0.570, -2.0, 0.15, 0.05, 0.17)
   PopMatrix()
   Fg("diffuse grey; emission black")
   PushMatrix()
   Rotate(-5.0, 1.0, 0.0, 0.0)
   Rotate( 6.0, 0.0, 0.0, 1.0)
   DrawCylinder(0.0, 0.0, -2.5, 0.7, 0.035, 0.035)
   PopMatrix()
   PushMatrix()
   Rotate(6.0, 0.0, 0.0, 1.0)
   DrawTorus(-0.02, -0.22, -2.5, 0.03, 0.05)
   PopMatrix() 
   PopMatrix()
   # Draw the table 
   WAttrib("texcoord=auto", "texmode=on", "texture=table.gif")
   PushMatrix()
   Rotate(-10.0, 1.0, 0.0,0.0)
   DrawCylinder(0.0, 0.2, -2.0, 0.1, 0.3, 0.3)
   PopMatrix()
   PushMatrix()
   Translate(0.0, -0.09, -1.8)
   Rotate(65.0, 1.0, 0.0, 0.0)
   DrawDisk(0.0, 0.0, 0.0, 0.0, 0.29) 
   PopMatrix()
   WAttrib("texmode=off", "fg=diffuse weak brown")
   PushMatrix()
   Rotate(-20.0, 1.0, 0.0,0.0)
   DrawCylinder(0.0, 0.2, -2.2, 0.3, 0.1, 0.1)
   PopMatrix()
   while (e := Event()) ~== "q" do {
      write(image(e), ": ", &x, ",", &y)
      }
end

lecture #32

MazeGen Sample Code

lecture #33

Some Q&A and then...

Unicon: Networking

Main concepts:

client vs. server

client == app that opens the connection. server == app that receives connection requests

slow, reliable and ordered (TCP) vs. fast (UDP)

btw UDP is unreliable, unordered

hostnames, IP #'s, and ports

DNS, IPv4 vs IPv6...

synchronous/blocking vs. asynchronous, non-blocking I/O and timeouts

how long do you want to wait?

dropped connections and widely varying delays

modern WAN is ugly

multiplexing and select()

what happens when you have multiple users?

built-in higher level messaging (HTTP, SMTP, etc.)

internet is built on hundreds of protocols (on top of TCP or UDP). which ones should be built-in?

lecture 34

Network Demo

Discussion of Scoping Rules, Suspend

• undeclared variables are local...unless some other module that you link in declares them to be global!
• Local by default works well for small programs. For larger programs it is wise to declare your variables.
• Do Unicon programmers actually use suspend? ~29x in uni/unicon/*.icn; over a hundred in ipl/procs/*.icn. But plenty of programs don't.
• Discussion and examples of user-defined generators, written using suspend

lecture 35

Y'all saw the small HW extension, did ya?

Reading Assignment

• We are starting Java on Monday.
• Read Webber Ch. 13 A First Look at Java

Backtracking Control vs. Data

• When an expression fails and control resumes the most recently-suspended generator in Unicon, you are "undoing" some amount of control flow and execution (restoring program counter and stack registers, etc).
• For the most part, Unicon does *not* undo data: assignments to variables, inserts into sets, tables or lists, etc. are not undone when failure happens.
• The ONLY automatic undo-ing of data on failure in Unicon are
  • reversible assignment operator, e.g. x <- expr
  • string scanning subject and position
• For the rest (such as board configurations in games), you would have to manage your data backtracking
• Easiest: copy-on-modify (i.e. original easy to restore, it never changed)
• Alternative: save value before change, make change and suspend, restore value after resumption. Example:

  procedure tic_tac_toe(L, x, y, mymove)
     local old := L[x][y]
  
     suspend L[x][y] := mymove
     L[x][y] := old
  end
  

Co-expressions

• Co-expressions are synchronous independent computations
• They have their own stack; take turns at the CPU.
• You can call them co-operative "lightweight" threads; they are akin to "goroutines" if you like Go, except...
• They are fine-grained, expression-level, and can produce results for the caller by both implicit and explicit activation.
• Unicon also has true concurrent threads, unlike most scripting languages.
• Main (research) purpose of co-expressions: encapsulate a generator so it can be used a piece at a time, from different locations in source code.
• Dr. J's added secondary purpose: allow 2+ programs to run in the same VM instance.

Threads

• "Turn co-expressions loose": spawn(coexpr)
• True concurrency vs. pseudo-concurrency
• True concurrency is expensive
• Synchronization and communication costs
• Described in the Unicon book and in UTR14, both at unicon.org.

thread write(1 to 3)

 spawn( create write(1 to 3) )

The usual problem with a thread is: you aren't waiting for it to be done, and you can't even tell when it finishes. Well, assign it to a variable and you can at least do that much.

mythread := thread write(1 to 3)
...
wait(mythread)

Typically, a thread has some work (data structure) and an id passed into some function. After the thread is finished, the results will have to be incorporated back into the main computation somehow

t1 := thread sumlist(2, [4,5,6])
...
procedure sumlist(id, L)
   s := 0
   every s +:= !L
   #... can't easily just "return" the value
end

The classic way threads might communicate is: global variables! But these have race conditions. Alternatives include files or pipes or network connections (all slow), or an extra language feature, but first: how to avoid race conditions.

global mtx
mtx := mutex()
...
critical mtx: expr

lock(mtx)
expr
unlock(mtx)

Another way to avoid race conditions in Unicon is to use a "mutex'ed" data structure, as in

L := mutex([])

There are also thread-based versions of the activate operator: four or eight of them:

@>	@>>	<@	<<@
send	blocking send	receive	blocking receive

They follow this (weird) model:

There is more to concurrency: condition variables, private channels... this was just your gentle introduction. See UTR14 for more.

A Unicon Thread Story

• a plea from a friend
• toxline-dedup is a Very Simple Program
• Purpose: remove duplicates in a gigantic data source.
• It had to be run once a month on a datafile that grew a bit each month, so far, 800+ MB
• Runtimes were out-of-this-world slow! Several hours!
• ...and getting worse, fast.
• Many ways to speed up (faster algorithm? optimizing compiler?)
• Let's try threads
• Except, it looks like each iteration depends on all previous?
• 3 thread version divides work into reader, a processor, and a writer.
• Fixes nothing. Makes it worse.
• I/O is not the problem. Read 800+MB in < 1s
• Think more deeply about how to divide work up into many chunks.
• Devise massive threaded solution
• While debugging the (much more complicated) threaded version, realize the real problem and fixed it (improve Unicon's table data type).
• In the process of working with the customer, find bugs in threads (improve Unicon's concurrency facilities).
• End result: from 2+ hours to ... 22 seconds.

Discussion of Sort Module

Bits of Icon/Unicon Wisdom

• Possibly the most useful type of all is the table. Have you used it yet?
• !t is ok, but I seem to use key(t) a lot.
• Actually learning string scanning is wise. Some of you have.
• Records and classes are technically all public. Privacy is a convention, like in a public bathroom, not like in an isolation wing of a prison.
• You can easily get the names of all the fields and methods. You can easily get the superclasses, overwrite/replace a method, etc.
• Knowing all your generators is prudent. There are surprisingly few in classic Icon. Many of these are for string scanning. ! (bang), |, i to j, i to k by k, seq(), key(), find(), upto(), bal().
• Unicon adds some more generators, mainly its high-powered monitoring facility. keyword(), structure(), globalnames(), paramnames(), staticnames(), localnames(), fieldnames(), function(), istate(), WAttrib().
• Knowing your fallible expressions is prudent. := (design flaw, &pos only), <-, <->, :=:, ?, [], [:], \, / <, <=, >, >=, ~=, =, ==, ===, ~==, ~===, etc. string(), numeric(), cset(), integer(), real(), proc(), loadfunc(), args(), serial(), move(), pos(), tab(), any(), many(), match(), get(), pop(), classname(), oprec(), member(), pull(), getenv(), open(), read(), reads(), remove(), rename(), save(), seek(), where(), getch(), getche(), kbhit(), chdir(), delay()
• Graphics facilities fallible expressions. Active(), Bg(), Color(), ColorValue(), CopyArea(), Couple(), DrawImage(), Fg(), Font(), NewColor(), PaletteChars(), PaletteKey(), Pending(), ReadImage(), WDefault(), WriteImage().
• Windows Native fallible expressions. WinAssociate(), WinPlayMedia(), WinButton(), WinScrollBar(), WinMenuBar(), WinColorDialog(), WinFontDialog(), WinOpenDialog(), WinSelectDialog(), WinSaveDialog()
• Unicon adds more fallible expressions. variable(), cofail(), EvSend(), EvGet(), sql(), dbcolumns(), dbdriver(), dblimits(), dbproduct(), dbtables(), fetch(), PlayAudio, sys_errstr(), getppid(), getpid(), link(), symlink(), readlink(), kill(), trap(), chown(), chmod(), chroot(), rmdir(), mkdir(), truncate(), flock(), fcntl(), utime(), ioctl(), filepair(), pipe(), fork(), fdup(), exec(), system(), getuid(), geteuid(), getgid(), getegid(), setuid(), setgid(), getpgrp(), setpgrp(), crypt(), umask(), wait(), name(), gettimeofday(), lstat(), stat(), send(), receive(), select(), getpw(), getgr(), gethost(), getserv(), setpwent(), setgrent(), sethostent(), setservent(), ready(), syswrite(), setenv().
• One of the most important additions to Icon occurs in the open() modes. It is not just that there are many I/O modes supported but they are generally as easy to use as local files.

  mode	meaning
  "r"	read (default)
  "w"	write
  "a"	append
  "c"	create
  "p"	pipe
  "g"	2D graphics
  	below this point, Unicon only
  "n"	network (Internet, TCP/UDP)
  "gl"	3D graphics (OpenGL)
  "d"	DBM database
  "o"	ODBC (SQL) database
  "z"	libZ compression
  "m"	messaging (http://, pop://, etc.)

Things I love about Icon and Unicon

x1 < y < x2

ranges the way I saw them back in math class

lists and tables

the most convenient data structures building blocks in any language

!L === x and P(!L) and such

the most convenient algorithms building blocks in any language

open() and friends

the most convenient graphics and network I/O in any language

Things I hate about Icon and Unicon

Run-time errors that have &null values because of typos

compiler option -u helps but isn't a cure-all

Run-time errors that have &null values because of surprise failure

if's are needed to check for failure...in a large percent of expressions

Computational accidents because of surprise generators

some things were never meant to be backtracked-into.

the language is slow

from time to time I get help from students interested in fixing this

the IDE is immature

many Bothan spies died to bring you this IDE.

OOP Lessons from the Unicon Class Libraries

3d/   guidemos/  iyacc/     Makefile   progs/  ulex/	unidoc/
CVS/  ide/	 lib/	    native/    shell/  unicon/	util/
gui/  ivib/	 makedefs   parser/    udb/    unidep/	xml/

Extra Credit Unicon

• Re-do an earlier HW in Unicon, possibly cooler (Unicon- or Vandal-themed?).
• Write a program that, given the name of a built-in function foo, reads in http://unicon.org/utr/utr8.html, finds the anchor for foo, and prints out the header information for that function, e.g. "write(s|f, ...) : string|file"
• Write a Unicon program that, given an input program source file foo.icn, draws its procedure call graph, the graph that shows which procedure calls which.
• Write a Unicon program that, given an input program source file foo.icn, detects and complains if the program contains an every loop that obviously should be a while loop, or a while loop that obviously should be an every loop.
• Write a program of your own devising that lets you play with one or more of:
  • user-defined generators
  • classes
  • graphics and GUI's
  • networking
  • threads
• Write a Unicon program that has some real-world value to someone.

Unicon Scope Rules

1. Local overrides global 2. If you have classes, and member functions, where do they fit? 3. If you don't have to declare variables, are they local, or global, or class? 4. By the way, there exists dynamic scope versus static scope.

global x

class C ( x, y)

method g()
   write(x)
end

method f()
   (let x

   g()
    )
end

end

Semantics

Attributes

double f(int n)
{
   ...
}

• its name, f
• the fact that it is not a variable
• the fact that it is a function
• its number of parameters and their types
• its return type

    x = f('\007');

Environment and State

Scopes and Bindings

Scope rules for each language determine how to go from names to declarations.

Each use of a variable name must be associated with a declaration. This is generally done via a symbol table. In most compiled languages it happens at compile time, but interpreters will build and maintain a symbol table while the program runs.

A few comments about Nested Blocks

• some languages don't allow nesting at all
• algol-based languages generally nest syntactically, usually at the function level.
• C-like languages don't allow functions to nest, but do allow local blocks
• some major languages nest blocks at runtime (e.g. Lisp). This can lead to some wild and woolly situations.
• in modern languages, classes and packages/namespaces matter; can they nest? (depends on the language)

Symbol Tables

Runtime Memory Regions

code
static data
stack (grows down)
heap (may grow up, from bottom of address space)

The code section is usually read-only, and shared among multiple instances of a program. Dynamic loading may introduce multiple code regions, which may not be contiguous, and some of them may be shared by different programs. The static data area may consist of two sections, one for "initialized data", and one section for uninitialized (i.e. all zero's at the beginning). Some OS'es place the heap at the very end of the address space, with a big hole so either the stack or the heap may grow arbitrarily large. Other OS'es fix the stack size and place the heap above the stack and grow it down.

Much CPU architecture has included sophisticated support for making the stack as fast as possible, and more generally, for making repeated and sequential memory accesses as fast as possible. This sort of ideally fits C and Pascal (i.e. traditional "structured" imperative programming) and performs pathologically poorly on Lisp (functional) and OOP languages that exhibit poor locality of reference, exaggerating the already extreme speed differences between medium-level languages and very high level languages. Hardware that eschews caches in favor of "more cores" are not as biased.

Allocation and Variable Lifetimes

Activation Records

Garbage Collection

The Basic problem in garbage collection: given a piece of memory, are there any pointers to it? (And if so, where exactly are all of them please). Approaches:

• reference counting
• traversal of known pointers (marking)
  • copying (2 heaps approach)
  • compacting (mark and sweep)
  • generational
• conservative collection

Supplemental Comments on Imperative Programming

One way to think of imperative programming is that it is any programming in which the programmer determines the control flow of execution. This might be using goto's or loops and conditionals or function calls. It contrasts with declarative programming, where the programmer specifies what the program ought to do, but does not determine the control flow.

Def: a program is structured if the flow of control through the program is evident from the syntactic structure of the program text. "evident" means single-entry/single-exit.

Common constructs in imperative programming include:

• sequences of statements; compound statements
• selection statements
• looping statements
• function call and return

Assertions, invariants, preconditions, and postconditions

A precondition is an assertion before a statement executes, that defines the expected state. It defines requirements that must be true in order for the statement to do what it intends. A postcondition is an assertion after a statement executes that describes what the statement has caused to become true. An invariant is an assertion of things that do not change during the execution of a statement. An invariant is particularly useful with loop statements.

while x >= y do
   { x >= y if we get here }
   x := x - y

{ x >= 0 and y > 0}
while  x >= y do
   { y >= 0 and x >= y }
   x := x - y
   { x >= 0 and y > 0 }

lecture 36

Announcements

• HW#5 (Java) is posted. Bring your questions to a discussion about it next class.
• I would like more participation for this unit; please ask and answer more questions!

• Compared to C++ or Unicon's OOP, Java attempts to be more pure, even when it hurts.
• All code is in classes, even when it makes no sense
• No multiple inheritance, even when it would make sense
• Java is not are pure OO as SmallTalk -- it has non-object scalar types, and a non-object array type. You don't add two numbers by sending the first number a message.

Reading Assignment

• Read Webber Chapter 13.
• Read and "do" the Java Tutorials Trails, Covering the Basics #1-4 and #6: Getting Started, Learning the Java Language, Essential Java Classes, Collections, and Deployment.

Some Java Slides

Compiling and Running Java Locally on cs-210.cs.uidaho.edu

alias java="java -Xmx20m -Xms10m"
alias javac="javac -J-Xmx20m"

Once you have your aliases setup, compile with "javac hello.java" and run with "java hello"

Example #0

lecture 37

I am gonna try to do a little bit of my own lecture material, plus a bit of Webber every day.

Things to Learn About Java Today

• javac -Xlint helps by being extra picky, reports more warnings
• "static" methods are our first Bad Java Habit
• Java is Schizophrenic: each class can have it own main() !? Only one gets invoked when you run Java, based on which class name is given then
• C is 80% language and 20% libraries. While the Java language is only somewhat (33%?) larger than C, Java is 20% language and 80% libraries. As these fake and made-up numbers clearly prove, the learning curve and time investment needed to learn Java is much larger compared with C. But sure, Java is "easier" conceptually.
• Java is the "COBOL" of modern enterprise computing, LOL.
• Can't do anything in Java without packages. Start with java.lang and java.util. Probably have to survey them, learn details on demand.
• This means Java needs a good IDE far more than C or C++ do.
• do you know the term "method" yet? In C++ it is a "member function"
• Unlike C++ with its public: private: protected:, in Java you don't use a colon and do mark every single variable's/method's visibility. Ugh.
• Modern Java has "type parameters". They are in <brackets> and are used heavily in collection classes in order to provide polymorphism while checking all types and compile time.
• Modern Java has "lambdas", sort of. Instead of being anonymous functions that can be stored in variables or passed as parameters, since Java has nothing but classes, it fakes lambdas using anonymous classes with just one function in them. LOL.

Java is an Almost-SmallTalk?

So, it isn't about whether you will use classes a lot in Java, like it would be in C++. It is: how are you going to map your application domain onto a set of (built-in system, or new written-by-you) classes? For many problems, this is a natural fit, but for other problems it is silly and awkward.

When to OOP?

1. your application domain maps naturally onto a set of classes, or
2. your problem is so large that you will have trouble wrapping your brain around the whole thing.

An Example of Bad OOP in Java

A Lisp HW in Java

Sure you can use Java to write recursive Lisp functions. But if your class is a set of unrelated functions that do not share state, it is pretty bad OOP.

Webber's Java Slides

• Chapter 13

lecture 38

Java Concepts (and APIs) to Learn Today

• System.getenv()
• Basics of exception handling
• reading line-oriented input with BufferedReader

IO: the next steps

• Already seen: System.out.println(), a simple method for writing text to the standard output console.
• There is a System.in for input, it can read 1 (or N) bytes at a time.
• For line-oriented input, use a BufferedReader from the java.io package:

     BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  

• You can then read lines via that object's readLine() method. Watch out though, readLine() can fail with an exception, and the compiler won't let you use it without handling that exception somehow!

Exception Basics

• Exceptions are objects of some subclass of Exception
• They occur when bad things happen
• When an exception occurs anywhere inside some statement, a "non-local goto" aborts the statement
• The exeption object comes hurtling out of the program, aborting one method call at a time back to main(), unless/until something stops it
• Unhandled, the program terminates with an error message
• You can handle exceptions with

   try { statement1 } catch (exceptiontype) { statement2 }
  

• When an exception of type exceptiontype (or a subclass) occurs anywhere inside statement₁, execution goes to statement₂

Webber's Java Slides

• Chapter 13 -- started at 27, got to 53

lecture 39

Mailbag

I am currently trying to compile and run my Java program using javac and java, but it is throwing the following error message,

Error occurred during initialization of VM
Could not allocate metaspace: 1073741824 bytes

Is there any way to fix this?

Java is trying to ask for a billion-and-some bytes, and failing. With a platform issue, I will want to know what machine and OS you are trying; I'll guess maybe it is cs-210.cs.uidaho.edu. If the following do not help, let me know:

alias java="java -Xmx20m -Xms10m"
alias javac="javac -J-Xmx20m"

Another Look at the 3 Pillars of Object Orientation

As a young computer scientist, I read and believed that object-orientation consisted of:

encapsulation + polymorphism + inheritance

encapsulation

closely related to information hiding, this is the idea that access to a set of related data can be protected and controlled, so as to avoid bugs and ensure consistency between different bits of data. This concept has been mathematically expressed in the notion of an Abstract Data Type (ADT), which is a set of values and a set of rules (operations) for manipulating those values. In programming languages, it is provided by a class or module construct.

polymorphism

Literally meaning "many shapes" or more loosely "shape changing", this idea is that if you write an algorithm in terms of a set of abstract operations, that algorithm can work on different data types. It occurs in some languages as templates (C++), generics (Ada), interfaces (Java), by passing functions as parameters (C), or simply going with a flexible, dynamic type system (Lisp).

inheritance

By analogy to biological inheritance of traits or genes, inheritance is when you define a class in terms of an existing class.

Encapsulation

This is the single most important principle of OOP. It is more than just saying "class" a few times in each program. It is usually well-supported in any OO language. The potential abuse comes from the encumbrance of too much required syntax which distracts programmers from the actual problems they need to solve.

Algorithms written to use an encapsulated object and access it only via its interface functions will not mind if you totally rewrite its innards to fix it, make it faster, etc.

Polymorphism

Dynamic OOP languages usually support this well. Static OOP languages usually support polymorphism somewhat awkwardly, as is the case of C++ templates.

Inheritance

The above concepts are important and useful. They are what object-oriented programming languages typically try to directly support. However, they do not tell the whole story, and programmers who stop there often write bad OO code.

Webber's Java Slides

• Chapter 13 -- start at 54
• Chapter 14 -- got through 1-8

lecture 40

Announcements

• Reading assignment: Webber book page 15 and 17
• Final exam announcement: instead of a final exam at the scheduled time of Tuesday May 12 from 8-10am, the final will be a take-home final. It will be posted by 5:00pm on Monday May 11 and due by 11:59pm on Tuesday May 12, e.g. you will have approximately 31 hours to do it. It will be open book and open notes. There will be a review on Friday May 8.
• Friday's lecture will be delivered from on the road. If, heaven forbid, my internet were to fail, your mission would be to spend that hour working forward on Java through self study.
• Friday's office hours will be cancelled. I will be reading e-mail from the road, and will accept and schedule appointment requests, but they may need to be in the evening or next week.

• Chapter 15 - we did slides 1-40

lecture 41

We finished Chapter 15 and started Chapter 17.

• Chapter 15 - slide 41 to the end
• Chapter 17 - slides 1-6

lecture 42

Welcome to Dead Week

Object-oriented Thinking: Design-centric Viewpoint

• simulate entities

  object-oriented code models "entities" -- things or ideas that must be approximated in some application domain. Entities could be cars or monsters or bank accounts or employees or ...

• add controllers

  controllers are objects that implement rules, coordinate and enforce consistency between entities, and so forth. They usually define the tasks that users of the software will perform, and what steps are needed to accomplish them.

• add boundary classes

  boundary classes are objects that govern interactions between the software and external entities: human users, files, network databases, etc.

• let objects be anthropomorphic

  Anthropomorphism is when you see human-like traits in your objects. You can often program objects more effectively if you think of them like intelligent agents that have motivations, wants, needs and limitations.

• do method acting

  Sometimes a good way to understand how to program your objects is to put yourself in their shoes, and ask yourself to "be" network handler, or the scrollbar, or whatever.

• make objects self-centered

  Object-oriented code is most effective when it is written as close to the data as possible. For example, if in my function I am calling function after function on another object, maybe dozens of times, perhaps I should have asked that object to do all that work for me -- by writing a method over in that object's class.

• write abstract data types

  Especially for application domain entities, it really makes sense to characterize their behavior. It is not just: what are its functions? It is: what sequence of function calls make sense for this kind of object?

• design first!

  The biggest mistake OO programmers make is to start coding, without first planning what you are going to do.

Back to Webber

• Chapter 17 - slides 7-25

lecture 43

CS 210 Java Exceptions Example: Hammurabi

Hammurabi in a Nutshell

Hammurabi, the Babylonian king, is a visionary who advances western civilization by introducing one of the earliest written codes of Law. Hammurabi is also tyrant who wants to grow his population to the largest possible size in order to be the most powerful ruler on earth. In ancient mesopotamia there is a lot of fertile land due to the annual flooding, but there are no defendable borders and the only safety lies in numbers (of spears). To make more people, you have to grow more food, which means you have to plant more land, which takes more seed grain. And by the way, the harvest yield varies from year to year, ranging from 0 to enormous. But the more grain you store, the higher percentage of stored grain is lost each year (rats, corruption, whatever).

The Hammurabi simulation must report on current population and grain and land holdings, and then ask Hammurabi each year:

• how many bushels to feed the people
• how many bushels of grain to plant for the next year
• how many acres of land to buy or sell @ 20 bushels per acre

Hammurabi: the Java Code

• hamurabi.java and
• kingdom.java, with modifications to work with
• minister.java

What to Learn About Java from the Hamurabi Code

Code by delta (Δ refers to change)

Whether you call it extension, modification, generalization, or filling in the blanks, lots of Java programs are written by modifying existing classes. Sometimes that means writing subclasses. How much inheritance have you done so far in your programming?

Object creation and method invocation

Have you gotten the basic OO syntax of Java yet? Is it any different from C++ so far? if so, how so?

Wrapper Classes

Java deals with its impurity by providing wrappers for non-class builtin types. Java programmers should know the basics of Integer, Double, Float, Short, Long, Character, Boolean, Void, and Byte. Start with the parse*() methods, e.g. Integer.parseInt(s)

Did we say "No preprocessor"?

Constant names get awkward:

private final static int POUND_DEFINE_WAS_SO_COOL = 1;

Getters and setters = lame-o-OO

But I guess setters are the ones that really bug me. And I can live with them so long as they are controlled.

Know how to (use) "swing"?

javax.swing is a graphical user interface library. Most Java applications might be written using this class library, unless they are applets, or are written in JOGL or something like that.

Graphical interface

In order to run swing programs, you almost have to either install and run Java on a local computer, or run on Linux machines in the lab. It is possible run swing and other graphic programs on wormulon, but only if you install an "X Window server" program on your local machine, and have an SSH connection that does "X11 port forwarding". And that can be slow, especially if you are not on campus. Avoid using wormulon this way unless you have good reason.

Who/what is JOptionPane?

Minimally you should know its showInputDialog() and showMessageDialog() methods.

Java Tips from the Past

Don't use an object instance to invoke a static method.

It would be more object-oriented to not use static methods at all, but if you must use a static method, it is CLASS.mystaticmethod(), not instance.mystaticmethod()

Do use templated collection typenames in constructors (after "new")

ArrayList<String> names = new ArrayList<String>();

Using a Class to Make "Swing" Optional

> java hamurabi
Exception in thread "main" java.awt.HeadlessException: 
No X11 DISPLAY variable was set, but this program performed an operation which requires it.
... long java runtime exception stack trace ...

• Hammurabi on Linux Java needs X Windows to run,
• IF your local machine (PC, Mac, etc) has the X11 X Windows "display server" software running, "ssh -X" or a similar option in your ssh client will let most ssh remote hosts run graphics on your local machine.

1. Rewrite the game code to just use the console, skip the GUI dialogs.
2. Run locally, instead of running on the machine where we turn code in.
3. Modify the game to ask whether a GUI is available, and use the console when no GUI will work.

1. Try and detect whether graphics are present, without using them, in order to avoid the exception in the example.
2. Just go ahead and try to use graphics, and if they fail, handle the exception and enable the fallback.

if (System.getenv("DISPLAY") == null) // ... use console

	use_swing = true;
	try {
	    JOptionPane.showMessageDialog(null,
					  "Minister says we are swinging");
	} catch (Exception e) {
	    System.out.println("Minister says we are using the console.");
	    use_swing = false;
	}

Using Exceptions in OO Design

• not the Emperor (hamurabi class),
• nor the kingdom...
• it belongs in a boundary class that talks to the human user, and it plays the role of the "prime minister" or perhaps "interior minister" who talks to the emperor (the human user) each year.

At this point, our object-oriented version of Hammurabi looks like the following picture:

• Chapter 17 - slides 26-35

----------we got this far in Spring 2020 before we ran out of time-------

• Chapter 14 -- resume at slide 9
• Chapter 16
• Chapter 18

About Inheritance

abstract inheritance

inheritance of a public interface, which is to say, a set of methods with matching/compatible signatures. Abstract inheritance is exactly that (sub)part of inheritance necessary for polymorphism to work. This is the kind of inheritance that says "if it looks like a duck, and walks like a duck, and quacks like a duck, it is duck"

A signature

Is a function's prototype information: name, number and type of parameters, and return type

concrete inheritance

concrete inheritance consists of inheriting actual code. This is the kind of inheritance that says "a mallard is a kind of duck with the following additional traits and behavior". While you might be thinking and writing code about mallards right now, the more code you manage to place in the duck class, or possibly a bird class above it, instead of the mallard class, the more "code sharing" you will see if you have many different kinds of ducks or other kinds of birds later on.

Interfaces

interface Bicycle {
    void changeCadence(int newValue);    //  wheel revolutions/minute
    void changeGear(int newValue);
    void speedUp(int increment);
    void applyBrakes(int decrement);
}

class ACMEBicycle implements Bicycle {
    // remainder of this class 
    // implemented as before
}

Concrete Inheritance

public class Bicycle {
    public int cadence, gear, speed;
    public Bicycle(int startCadence, int startSpeed, int startGear) {
        gear = startGear; cadence = startCadence; speed = startSpeed; }
    public void setCadence(int newValue) {  cadence = newValue; }
    public void setGear(int newValue)    {  gear = newValue;    }
    public void applyBrake(int decrement) { speed -= decrement; }
    public void speedUp(int increment)    { speed += increment; }
}

public class MountainBike extends Bicycle {
    public int seatHeight; // subclass adds one field
    // overrides constructor, calls superclass constructor
    public MountainBike(int startHeight, int startCadence,
                        int startSpeed,  int startGear) {
        super(startCadence, startSpeed, startGear);
        seatHeight = startHeight;
    }   
    public void setHeight(int newValue) {    // subclass adds one method
        seatHeight = newValue;
    }   
}

Two ways to check whether your Bicycle is a mountain bike

1. MountainBike mb = (MountainBike)b;
   

2. if (b instanceof MountainBike) ...
   

if (b instanceof MountainBike) b.doMountainyStuff()
else if (b instanceof RacingBike) b.doRacingStuff()
...

b.doStuff()

Arrays Example

int[] anArray;
anArray = new int[10];

Also, be sure you can recognize (and write) code like:

int[] anArray = {100, 200, 300, 400, 500, 600, 700, 800, 900, 1000};

Strings versus arrays of char

public class hello {
   public static void main(String[]args){
     String s = "Niagara. O roar again!"; 
     char c = s[9];
     System.out.println("10th char of "+s+" is "+c);
   }
}

More on the Java String class

static method String.valueOf(x)

overloaded 9 times, produces string representation of x

static method String.format(formatstr, objs...)

returns a formatted string, a la printf

s.length()

s.indexOf(c) and s1.indexOf(s2), lastIndexOf

similar to strchr, strstr

s1.compareTo(s2) and s1.compareToIgnoreCase(s2)

+ and s1.concat(s2)

s.matches(String regex)

Java Trails Commentary

JavaDoc

Know what /** */ comments are for, and be able to give examples.

JavaBeans

This component technology seems to be famous or important. For what?

applets

What are applets, and how do I write one?

NetBeans

What is NetBeans good for?

Java's byte vs. char types

What is the difference? What's with those '\uffff'-style char literals?

JavaDoc

What it does: write out a collection of webpages to help "navigate" your Java class libraries.

Big success, inspired numerous copycats!!

Writing Doc Comments [from Oracle documentation]

/**
 * Returns an Image object that can then be painted on the screen. 
 * The url argument must specify an absolute {@link URL}. The name
 * argument is a specifier that is relative to the url argument. 
 * 

 * This method always returns immediately, whether or not the 
 * image exists. When this applet attempts to draw the image on
 * the screen, the data will be loaded. The graphics primitives 
 * that draw the image will incrementally paint on the screen. 
 *
 * @param  url  an absolute URL giving the base location of the image
 * @param  name the location of the image, relative to the url argument
 * @return      the image at the specified URL
 * @see         Image
 */
 public Image getImage(URL url, String name) {
        try {
            return getImage(new URL(url, name));
        } catch (MalformedURLException e) {
            return null;
        }
 }

printf / Math

public class BasicMathDemo {
    public static void main(String[] args) {
        double a = -191.635, b = 43.74;
        int c = 16, d = 45;
        double degrees = 45.0, radians = Math.toRadians(degrees);

        System.out.printf("The absolute value of %.3f is %.3f%n", 
                          a, Math.abs(a));

        System.out.printf("The ceiling of %.2f is %.0f%n", 
                          b, Math.ceil(b));

        System.out.format("The cosine of %.1f degrees is %.4f%n",
                          degrees, Math.cos(radians));

    }
}

import static java.lang.Math.*;
public class BMD {
   public static void main(String[]args)
   {
   System.out.printf("Hello, world %.3f%n", ceil(3.14159));
   }
}

More on Exceptions

checked

probably recoverable. catch-or-specify required

error

you can catch it, but you probably can't recover. problem outside the app.

runtime

you can catch it, but you probably can't recover. problem inside the app, i.e. a bug that needs to be fixed.

Observation Regarding Exceptions

• You can catch more than one type of exception on a single try block; it is a bit like a switch statement, or more accurately, like a series of "else-if" tests.
• The types of exceptions must either be mutually exclusive, or else work their way from more-specific-first to more-general.
• You can explicitly throw (cause) your own exceptions, including new kinds that you define yourself.
• "throw" is followed by "new" applied to the constructor for the type of exception.

try {
    out = new PrintWriter(new FileWriter("OutFile.txt"));
    for (int i = 0; i < SIZE; i++) {
        out.println("Value at: " + i + " = " + list.get(i));
    }
} catch (FileNotFoundException e) {
    System.err.println("FileNotFoundException: " + e.getMessage());
    throw new SampleException(e);

} catch (IOException e) {
    System.err.println("Caught IOException: " + e.getMessage());
}

static String readFirstLineFromFileWithFinallyBlock(String path)
throws IOException {
    BufferedReader br = new BufferedReader(new FileReader(path));
    try {
        return br.readLine();
    } finally {
        if (br != null) br.close();
    }
}

JAR files

Unlike C/C++, Java does not have a "linker" that resolves symbols at "link time" to produce an executable. Symbols are resolved at "load time" which is generally the first time that a class is needed/used, often during program startup/initialization. This can mean that Java programs are slower to start than native code executables, but it does provide a certain flexibility.

Since Java does not have a linker, JAR files are the closest approximation that it has: a Jar archive can bundle a collection of .class files as one big file that can be run directly by the java VM (using the -jar option). To build a JAR that will run as a program, you specify the options "cfe", the name of which class' main() function to use at startup, and the set of class files:

jar cfe foo.jar foo foo.class bar.class baz.class
java -jar foo.jar

Separate Compilation and Make

Consider this example makefile:

hello.jar: hello.class
	jar cfe hello.jar hello hello.class

run: hello.jar
	java -jar hello.jar

hello.class: hello.java
	javac hello.java

Concurrency

• Java features excellent concurrency support
• concurrency == the practice of doing two or more things at once.
• How much do you know about processes and threads so far?
• This subject is, in general, outside the scope of this course, but you should see the basics of what Java provides.
• Basic issues you should look for in ANY concurrency facilities are
  • how to get more than one computation to happen at once
  • how to communicate/combine data between computations
  • how to synchronize/coordinate computations

Threads

In Java, threads can be created for any Runnable class, which must implement a public void method named run().

public class HelloRunnable implements Runnable {
    
    public void run() {
        System.out.println("Hello from a thread!");
    }
    public static void main(String args[]) throws InterruptedException {
    Thread t;
    HelloRunnable r = new HelloRunnable();
        (t = new Thread(r)).start();
         // can use r to "talk" to the child thread via class variables...
         t.join();
    }
}

Easy Synchronization

    public synchronized void increment() {
        c++;
    }

Communication

The main kicker is to avoid race conditions, where two threads get inconsistent information by writing to the same variable at the same time. How to avoid that? Synchronization.

CLASSPATH

Collections

Interfaces

There is a whole hierarchy of collection interfaces algorithms code for.

Implementations

A set of reusable data structures

Algorithms

Searching, sorting, etc.

Typical is to declare via:

 abstracttype<elem> var = new concretetype<elem>(...);

Iterating

I now have it on good authority that iterators can be used aggressively to implement full Unicon-style generators and goal-directed evaluation; they are just more long-winded and cumbersome to write.

Lists

Maps

Notice that in order to initialize this "word frequency counter", you first do a m.get(), and if it is null you start the count at 1. Otherwise, you increment the count.

import java.util.*;
public class Freq {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<String, Integer>();
        // Initialize frequency table from command line
        for (String a : args) {
            Integer freq = m.get(a);
            m.put(a, (freq == null) ? 1 : freq + 1);
        }
        System.out.println(m.size() + " distinct words:");
        System.out.println(m);
    }
}

Introspection

public static void summarize(Object o) throws Exception
{
    Class c = o.getClass();
    System.out.println("Class: " + c.getName());
    Method[] methods = c.getMethods();
    System.out.println("  Methods: ");
    for (int i = 0; i < methods.length; i++) {
      System.out.print("    " + methods[i].toString());
      if (methods[i].getDeclaringClass() != c)
        System.out.println(" (inherited from " +
          methods[i].getDeclaringClass().getName() + ")");
      else
        System.out.println();
    }
  } // summarize(String)

JavaBeans

• They use getters and setters to allow their states to be manipulated externally, e.g. via GUI IDE.
• They must be either "Serializable" or "Externalizable": in order for the bean to survive across multiple Java VM instances or program runs, it must know how to write itself to disk in either a proprietary Java format or in an XML format. Among other things, they must have a no-argument constructor.

Applets

import javax.swing.JApplet;
import javax.swing.SwingUtilities;
import javax.swing.JLabel;

public class HelloWorld extends JApplet {
    //Called when this applet is loaded into the browser.
    public void init() {
        //Execute a job on the event-dispatching thread; creating this applet's GUI.
        try {
            SwingUtilities.invokeAndWait(new Runnable() {
                public void run() {
                    JLabel lbl = new JLabel("Hello World");
                    add(lbl);
                }
            });
        } catch (Exception e) {
            System.err.println("createGUI didn't complete successfully");
        }
    }
}

To deply an applet, compile the code and package it as a JAR file. Then in your web page you write

<applet code=AppletClassName.class
        archive="JarFileName.jar"
        width=width height=height>
</applet>

lecture 44

Final Exam Review

Review language paradigms

Know what imperative, functional, declarative, object-oriented, and goal-directed languages are about.

Flex

• What paradigm? How pure an example of that paradigm are Flex+Bison?
• Know regular expressions, including operators and precedence
  • each symbol s is a regex that matches itself
  • re₁ re₂ (concatenate) is regex
  • re₁ | re₂ (alternate) is regex
  • re₁ * (Kleene star) is regex
  • ( re₁ ) is a regex
  • . matches any one character except newline [^\n]
• What are Flex's rules for deciding which rule to use when they overlap?
• What is Flex's general syntax?
• What is the public interface of Flex-generated lexical analyzers to programs such as Bison parsers?

Bison

• Know context free grammars, and common special cases.
  • What are terminals and non-terminals? How can you tell whether a symbol is terminal or non-terminal?
  • production rules: NT -> ω where ω is 0 or more terminals and nonterminals
• What are Bison's rules for decide which rule to use when they overlap?]
• what is more powerful about Bison than Flex?
• What are Bison conflicts and how does one solve them?
• What is Bison's public interface? How does a C/C++ program call a Bison-generated parser?

ML (1 2 3)

• What paradigm does ML represent?
• General syntax and program structure. What does a program look like?
• Know what are atoms
  • basic ML: "scalar" or primitive values
  • null, numbers, bool... Are strings scalar?
• Define tuples. How are they different from "arrays" in C/C++/Java?
• Give the mathematical definition of lists
  • nil is a list of length 0
  • if L is a list, anything :: L is a list
• Practice recursing on numbers, lists, ... anything else?
• What are the most common expressions in ML?
  

  Lists	Operators	Keywords	Control	Declaration
  [] :: @ hd tl	+ - * / div mod ~ ^	andalso orelse	if then else case of ...	fun vs. fn let val

• Patterns! this is a whole can of worms!
  • patterns in parameter lists
  • tuples, lists, and conses of patterns
  • functions with multiple bodies that match different parameter patterns
• "Higher order functions" and Currying

Unicon

• Know Unicon's general syntax. What does a program look like?
• Know Unicon's built-in types and basic operations

  integer real strings csets lists tables classes
  

• What is goal-directed expression evaluation?
• Know what generators are, give simple examples.
• How do strings, lists and tables work?

Java

• Know Java's general syntax. What does a program look like?
• What about Java is different from C++?
• Know Java's built-in types and rules for type checking.
• How do you write/create new types in Java?
• Know basics of I/O, like how to open a named file and read from it.
• Know the basics of arrays vs. Container classes
  • For example, know ArrayList and HashMap